TY - JOUR
T1 - On the automatic generation of metaheuristic algorithms for combinatorial optimization problems
AU - Martín-Santamaría, Raúl
AU - López-Ibáñez, Manuel
AU - Stützle, Thomas
AU - Colmenar, J. manuel
PY - 2024/6/6
Y1 - 2024/6/6
N2 - Metaheuristic algorithms have become one of the preferred approaches for solving optimization problems. Finding the best metaheuristic for a given problem is often difficult due to the large number of available approaches and possible algorithmic designs. Moreover, high-performing metaheuristics often combine general-purpose and problem-specific algorithmic components. We propose here an approach for automatically designing metaheuristics using a flexible framework of algorithmic components, from which algorithms are instantiated and evaluated by an automatic configuration method. The rules for composing algorithmic components are defined implicitly by the properties of each algorithmic component, in contrast to previous proposals, which require a handwritten algorithmic template or grammar. As a result, extending our framework with additional components, even problem-specific or user-defined ones, automatically updates the design space. Furthermore, since the generated algorithms are made up of components, they can be easily interpreted. We provide an implementation of our proposal and demonstrate its benefits by outperforming previous research in three distinct problems from completely different families: a facility layout problem, a vehicle routing problem and a clustering problem.
AB - Metaheuristic algorithms have become one of the preferred approaches for solving optimization problems. Finding the best metaheuristic for a given problem is often difficult due to the large number of available approaches and possible algorithmic designs. Moreover, high-performing metaheuristics often combine general-purpose and problem-specific algorithmic components. We propose here an approach for automatically designing metaheuristics using a flexible framework of algorithmic components, from which algorithms are instantiated and evaluated by an automatic configuration method. The rules for composing algorithmic components are defined implicitly by the properties of each algorithmic component, in contrast to previous proposals, which require a handwritten algorithmic template or grammar. As a result, extending our framework with additional components, even problem-specific or user-defined ones, automatically updates the design space. Furthermore, since the generated algorithms are made up of components, they can be easily interpreted. We provide an implementation of our proposal and demonstrate its benefits by outperforming previous research in three distinct problems from completely different families: a facility layout problem, a vehicle routing problem and a clustering problem.
KW - metaheuristics
KW - methodology
KW - reproducibility
KW - automatic configuration
U2 - 10.1016/j.ejor.2024.06.001
DO - 10.1016/j.ejor.2024.06.001
M3 - Article
SN - 0377-2217
JO - European Journal of Operational Research
JF - European Journal of Operational Research
ER -