Aprendizaje para la optimización con Savant Virtual

Autores/as

DOI:

https://doi.org/10.36561/ING.22.4

Palabras clave:

Aprendizaje automático, Optimización, Problema del próximo lanzamiento, Planificación en sistemas de cómputo heterogéneos, Problema de sincronización de autobuses

Resumen

Los problemas de optimización que surgen en múltiples campos de estudio demandan algoritmos eficientes que puedan explotar las plataformas modernas de computación paralela. El notable desarrollo del aprendizaje automático ofrece la oportunidad de incorporar el aprendizaje en algoritmos de optimización para resolver problemas complejos y de grandes dimensiones de manera eficiente. Este artículo explora Savant Virtual, un paradigma que combina aprendizaje automático y computación paralela para resolver problemas de optimización. Savant Virtual está inspirado en el Síndrome de Savant, una condición mental en la que los pacientes se destacan en una habilidad específica muy por encima del promedio. En analogía con el Síndrome de Savant, Savant Virtual extrae patrones de instancias previamente resueltas para aprender a resolver un determinado problema de optimización de forma masivamente paralela. En este artículo, Savant Virtual se aplica a tres problemas de optimización relacionados con la ingenierı́a de software, la planificación de tareas y el transporte público. La eficacia de Savant Virtual se evalúa en diferentes plataformas informáticas y los resultados se comparan con soluciones exactas y aproximadas para instancias tanto sintéticas como realistas de los problemas estudiados. Los resultados muestran que Savant Virtual puede encontrar soluciones precisas, escalar eficazmente en la dimensión del problema y aprovechar la disponibilidad de múltiples recursos de cómputo.

Descargas

Los datos de descargas todavía no están disponibles.

Citas

Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti, A., and Protasi, M. (2012). Complexityand approximation: Combinatorial optimization problems and their approximability properties. Springer Science & Business Media.

Golub, G. H. and Ortega, J. M. (2014). Scientific computing: an introduction with parallel computing.Elsevier.

Darte, A., Robert, Y., and Vivien, F. (2012). Scheduling and automatic parallelization. Springer Science& Business Media.

Golub, G. H. and Ortega, J. M. (2014). Scientific computing: an introduction with parallel computing. Elsevier.

Vlastelica, M., Paulus, A., Musil, V., Martius, G., and Rolıń ek, M. (2020). Differentiation of blackboxcombinatorial solvers. In International Conference on Learning Representations.

Vinyals, O., Fortunato, M., and Jaitly, N. (2015). Pointer Networks. In Advances in Neural InformationProcessing Systems 28, pages 2692–2700.

Pinel, F., Dorronsoro, B., Bouvry, P., and Khan, S. (2013). Savant: Automatic parallelization of ascheduling heuristic with machine learning. In World Congress on Nature and Biologically Inspired Computing, pages 52–57.

Treffert, D. (2006). Extraordinary People: Understanding Savant Syndrome. Iuniverse.

Pring, L. (2005). Savant talent. Developmental medicine and child neurology, 47(7):500–503.

Heaton, P. and Wallace, G. L. (2004). Annotation: The savant syndrome. Journal of child psychologyand psychiatry, 45(5):899–911.

Bagnall, A., Rayward, V., and Whittley, I. (2001). The next release problem. Information and SoftwareTechnology, 43(14):883–890.

Kellerer, H., Pferschy, U., and Pisinger, D. (2004). Springer.

Nemhauser, G. L. and Ullmann, Z. (1969). Discrete Dynamic Programming and Capital Allocation.Management Science, 15(9):494–505.

Harman, M., Krinke, J., Medina-Bulo, I., Palomo, F., Ren, J., and Yoo, S. (2014). Exact scalablesensitivity analysis for the next release problem. ACM Transactions on Software Engineering and Methodology, 23(2):1–31.

Massobrio, R., Nesmachnow, S., Palomo-Lozano, F., and Dorronsoro, B. (2021). Virtual savant as ageneric learning approach applied to the basic independent next release problem. Applied Soft Computing, 108:107374.

Massobrio, R., Nesmachnow, S., and Dorronsoro, B. (2018c). Support Vector Machine Acceleration forIntel Xeon Phi Manycore Processors. In High Performance Computing Latin America Conference, pages 277–290.

Luo, P., Lü, K., and Shi, Z. (2007). A revisit of fast greedy heuristics for mapping a class of independenttasks onto heterogeneous computing systems. Journal of Parallel and Distributed Computing, 67(6):695–714.

de la Torre, J. C., Massobrio, R., Ruiz, P., Nesmachnow, S., and Dorronsoro, B. (2020). Parallel virtualsavant for the heterogeneous computing scheduling problem. Journal of Computational Science, 39:101048.

International Transport Forum (2014). Valuing Convenience in Public Transport. OECD Publishing.

Nesmachnow, S., Muraña, J., Goñi, G., Massobrio, R., and Tchernykh, A. (2020). EvolutionaryApproach for Bus Synchronization. In High Performance Computing Latin America Conference, pages 320–336.

Massobrio, R., Nesmachnow, S., Muraña, J., and Dorronsoro, B. (2022). Learning to optimize timetables for efficient transfers in public transportation systems. Applied Soft Computing, 119:108616.

Descargas

Publicado

2022-06-30

Cómo citar

[1]
R. Massobrio, «Aprendizaje para la optimización con Savant Virtual», Memoria investig. ing. (Facultad Ing., Univ. Montev.), n.º 22, pp. 29–39, jun. 2022.

Número

Sección

Artículos