HOMERO – A new holistic methodology for configuration, comparison, and evaluation of metaheuristics

Principal investigators: Abraham Duarte, J. Manuel Colmenar. Funding entities: Ministerio de Ciencia e Innovación (PID2021-126605NB-I00). Duration: 01/01/2022 – 31/12/2024.

Abstract:

Metaheuristics (MHs) are among the most prominent and successful techniques to solve a large amount of complex and computationally hard combinatorial and numerical optimization problems arising in human activities, such as economics (e.g., portfolio selection), industry (e.g., scheduling or logistics), or engineering (e.g., routing). MHs can be seen as general algorithmic frameworks that require relatively few modifications to tackle a specific problem. While MHs do not guarantee the optimality of the obtained solutions (unlike exact algorithms), and do not define how close the obtained solutions are from the optimal ones (unlike approximation algorithms), they do provide “acceptable” solutions in reasonable computing times for hard and complex problems in science and engineering.

Fred Glover coined the term metaheuristic in 1986. He wanted to define “a master process that guides and modifies other subordinate heuristics to explore solutions beyond simple local optimality”. MHs constitute a very diverse family of optimization algorithms including methods such as Tabu Search, Greedy Randomized Adaptive Search Procedures, Scatter Search, Variable Neighborhood Search, Iterated Local Search and Multi-start Methods. In addition, bio-inspired metaheuristics began with Genetic Algorithms, and, among others, they include many different methods like Simulated Annealing, Genetic Programming, Memetic Algorithms, Ant Colony Optimization, and Grammatical Evolution.

Research in MHs has mainly focused on designing effective and efficient algorithms to solve hard optimization problems. This line of research has been definitely very successful, as witnessed by thousands of journal and conference papers, hundreds of authored and edited books, and dedicated national/international conferences. Nevertheless, despite the large amount of knowledge that has been gathered, there is no established holistic methodology to help researchers when designing procedures for optimization problems in: benchmark instance selection, parameter tunning, sensitivity analysis, runtime comparison, and reproducibility, among others. Indeed, we are lacking some of the fundamental understanding of MHs that would allow us to create such a methodology.

The main objective of this project is to develop a holistic methodology with a scientific support for the application of MHs on optimization problems. The methodology will be complemented by a set of open-source software tools that will be accessible to the whole scientific community.

Although a theoretical approach to enlarge the body of knowledge of the metaheuristic foundations will be considered, this research will not be conducted in a purely abstract manner. On the contrary, a problem-driven approach will be followed by choosing application domains in which the use of MHs is particularly promising. Specifically, during the development of the project the following families of problems will be studied: Facility Location, Facility Layout, Graph Partitioning, Energy Consumption Prediction, and Energy Distribution.