Classifying Metaheuristics: Towards a unified multi-level classification system
- PDF / 741,917 Bytes
- 17 Pages / 595.276 x 790.866 pts Page_size
- 93 Downloads / 188 Views
(0123456789().,-volV)(0123456789(). ,- volV)
Classifying Metaheuristics: Towards a unified multi-level classification system Helena Stegherr1
•
Michael Heider1 • Jo¨rg Ha¨hner1
Accepted: 12 November 2020 Ó The Author(s) 2020
Abstract Metaheuristics provide the means to approximately solve complex optimisation problems when exact optimisers cannot be utilised. This led to an explosion in the number of novel metaheuristics, most of them metaphor-based, using nature as a source of inspiration. Thus, keeping track of their capabilities and innovative components is an increasingly difficult task. This can be resolved by an exhaustive classification system. Trying to classify metaheuristics is common in research, but no consensus on a classification system and the necessary criteria has been established so far. Furthermore, a proposed classification system can not be deemed complete if inherently different metaheuristics are assigned to the same class by the system. In this paper we provide the basis for a new comprehensive classification system for metaheuristics. We first summarise and discuss previous classification attempts and the utilised criteria. Then we present a multi-level architecture and suitable criteria for the task of classifying metaheuristics. A classification system of this kind can solve three main problems when applied to metaheuristics: organise the huge set of existing metaheuristics, clarify the innovation in novel metaheuristics and identify metaheuristics suitable to solve specific optimisation tasks. Keywords Nature-inspired algorithms Metaheuristic Classification Stochastic optimisation Mathematics Subject Classification 68Q05 90C59
1 Introduction Metaheuristics play an important role in solving complex optimisation problems where mathematical optimisation is infeasible either due to long computation times or incomplete problem definitions. They use a combination of heuristic methods, arranged in a higher level framework, to provide more efficient search space exploration capabilities (Blum and Roli 2003) and can be described as a design pattern, rather than an algorithm (Lones 2014; Krawiec et al. 2018). However, a metaheuristic can not perform equally well on all optimisation problems, as is proven by & Helena Stegherr [email protected] Michael Heider [email protected] Jo¨rg Ha¨hner [email protected] 1
Institute of Computer Science, Organic Computing Group, Eichleitnerstr. 30, 86159 Augsburg, Germany
the No Free Lunch theorems for optimisation (Wolpert and Macready 1997). These and other factors have lead to an explosion in the number of nature-inspired metaheuristics over the past years. So¨rensen criticises this excess in the publication of ‘‘new’’ metaheuristics, especially the focus on metaphors in their design (So¨rensen et al. 2017). While early metaheuristics provided novel ideas and successful strategies to solve complex optimisation problems, more recent contributions lack improvements and are oft
Data Loading...
