On the automatic generation of metaheuristic algorithms for combinatorial optimization problems

Raúl Martín-Santamaría, Manuel López-Ibáñez, Thomas Stützle, J. manuel Colmenar

Research output: Contribution to journalArticlepeer-review

Abstract

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.
Original languageEnglish
JournalEuropean Journal of Operational Research
Early online date6 Jun 2024
DOIs
Publication statusE-pub ahead of print - 6 Jun 2024

Keywords

  • metaheuristics
  • methodology
  • reproducibility
  • automatic configuration

Fingerprint

Dive into the research topics of 'On the automatic generation of metaheuristic algorithms for combinatorial optimization problems'. Together they form a unique fingerprint.

Cite this