A template for designing single-solution hybrid metaheuristics
Manuel López‐Ibáñez, Franco Mascia, Marie‐Éléonore Kessaci, Thomas Stützle · 2014
Single-solution metaheuristics are among the earliest and most successful metaheuristics, with many variants appearing in the literature. Even among the most popular variants, there is a large degree of overlap in terms of actual behavior. Moreover, in the case of hybrids of different metaheuristics, traditional names do not actually reflect how the hybrids are composed. In this paper, we discuss a template for single-solution hybrid metaheuristics. Our template builds upon the Paradiseo-MO framework, but restricts itself to a pre-defined structure based on iterated local search (ILS). The flexibility is given by generalizing the components of ILS (perturbation, local search and acceptance criterion) in order to incorporate components from other metaheuristics. We give precise definitions of these components within the context of our proposed template. The template proposed is flexible enough to reproduce many classical single-solution metaheuristics and hybrids thereof, while at the same time being sufficiently concrete to generate code from a grammar description in order to support automatic design of algorithms. We give examples of three IG-VNS hybrids that can be instantiated from the proposed template.