HOMERO – Una nueva metodología holística para la configuración, comparación y evaluación de metaheurísticas

Investigadores principales: Abraham Duarte, J. Manuel Colmenar. Entidades financiadoras: Ministerio de Ciencia e Innovación (PID2021-126605NB-I00). Duración: 01/01/2022 – 31/12/2024.

Resumen:

Las metaheurísticas (MHs) se encuentran entre las técnicas más destacadas y exitosas para resolver una gran cantidad de problemas de optimización combinatoria y numérica complejos y computacionalmente difíciles que surgen en las actividades humanas, como la economía (por ejemplo, la selección de carteras), la industria (por ejemplo, la programación o la logística), o la ingeniería (por ejemplo, el enrutamiento). Las MHs pueden considerarse marcos algorítmicos generales que requieren relativamente pocas modificaciones para abordar un problema específico. Aunque los MH no garantizan la optimalidad de las soluciones obtenidas (a diferencia de los algoritmos exactos), y no definen lo cerca que están las soluciones obtenidas de las óptimas (a diferencia de los algoritmos de aproximación), proporcionan soluciones “aceptables” en tiempos de computación razonables para problemas difíciles y complejos en ciencia e ingeniería.

Fred Glover acuñó el término metaheurística en 1986. Quería definir “un proceso maestro que guía y modifica otras heurísticas subordinadas para explorar soluciones más allá de la simple optimalidad local”. Las MHs constituyen una familia muy diversa de algoritmos de optimización que incluyen métodos como la búsqueda Tabu, los procedimientos de búsqueda adaptativa aleatoria codiciosa, la búsqueda dispersa, la búsqueda de vecindario variable, la búsqueda local iterada y los métodos de inicio múltiple. Además, las metaheurísticas bioinspiradas comenzaron con los Algoritmos Genéticos y, entre otros, incluyen muchos métodos diferentes como el Recocido Simulado, la Programación Genética, los Algoritmos Meméticos, la Optimización de Colonias de Hormigas y la Evolución Gramatical.

La investigación en MHs se ha centrado principalmente en el diseño de algoritmos eficaces y eficientes para resolver problemas de optimización difíciles. Esta línea de investigación ha tenido mucho éxito, como demuestran los miles de artículos publicados en revistas y congresos, los cientos de libros escritos y editados, y las conferencias nacionales e internacionales dedicadas a ello. Sin embargo, a pesar de la gran cantidad de conocimiento que se ha reunido, no existe una metodología holística establecida que ayude a los investigadores a la hora de diseñar procedimientos para problemas de optimización en: selección de instancias de referencia, ajuste de parámetros, análisis de sensibilidad, comparación de tiempos de ejecución y reproducibilidad, entre otros. De hecho, carecemos de algunos de los conocimientos fundamentales de las MH que nos permitirían crear dicha metodología.

El objetivo principal de este proyecto es desarrollar una metodología holística con un soporte científico para la aplicación de las MH en problemas de optimización. La metodología se complementará con un conjunto de herramientas de software de código abierto que será accesible a toda la comunidad científica.

Aunque se considerará un enfoque teórico para ampliar el cuerpo de conocimientos de los fundamentos metaheurísticos, esta investigación no se llevará a cabo de forma puramente abstracta. Por el contrario, se seguirá un enfoque orientado a la resolución de problemas mediante la elección de dominios de aplicación en los que el uso de las MH sea especialmente prometedor. En concreto, durante el desarrollo del proyecto se estudiarán las siguientes familias de problemas Localización de Instalaciones, Disposición de Instalaciones, Particionamiento de Grafos, Predicción del Consumo de Energía y Distribución de Energía.