=Paper=
{{Paper
|id=Vol-3007/2021-short-1
|storemode=property
|title=Analysing Metaheuristic Components
|pdfUrl=https://ceur-ws.org/Vol-3007/2021-short-1.pdf
|volume=Vol-3007
|authors=Helena Stegherr,Jörg Hähner
|dblpUrl=https://dblp.org/rec/conf/lifelike/StegherrH21
}}
==Analysing Metaheuristic Components==
https://ceur-ws.org/Vol-3007/2021-short-1.pdf
Analysing Metaheuristic Components
Helena Stegherr and Jörg Hähner
University of Augsburg, 86159 Augsburg, Germany
helena.stegherr@informatik.uni-augsburg.de
Abstract able for the given optimisation problem? This question re-
sults from the No free lunch theorem, which states that no
The vast number of nature-inspired metaheuristics makes it metaheuristic performs best on all problems (Wolpert and
increasingly difficult to keep an overview of efficient and in-
novative developments. Especially novel approaches based Macready, 1997). To some extent, this also led to an increas-
on obscure metaphors and lacking rigorous evaluation are ing amount of different metaheuristics, hybrids and variants,
often—and usually rightfully—disregarded in research and with more than 300 approaches by 2020, summarised in a
application. However, even among established approaches, presumably non-exhaustive list by Molina et al. (2020). As
new developments are hard to detect and integrating them most of those are strongly metaphor-based, it is hard to de-
into the current set of methods is not an easy task. Altogether,
finding a suitable metaheuristic for the problem at hand is ag- tect innovative and efficient strategies that could be advan-
gravated in all application domains, including Lifelike Com- tageous for the given problem. However, falling back to
puting Systems. In this paper, we present ways that can facil- well known approaches, e. g. evolutionary algorithms, might
itate extracting relevant information on metaheuristics. The restrict performance as more suitable strategies exist. Al-
approach is centred around a unified view on metaheuristics, together, this results in a necessity to facilitate the assess-
with a focus on their components as the relevant parts deter-
mining the performance and the behaviour of metaheuristic ment of metaheuristics in terms of their functionality, per-
frameworks and algorithms. We furthermore describe strate- formance and behaviour.
gies for the conceptual and empirical analysis of those com- In this paper, we argue on the importance of conceptual
ponents. This procedure can be applied in different levels of and empirical analysis of metaheuristic components, based
detail and is therefore adaptable to the respective goals of the
on a unified framework, and present our research agenda
investigation of different metaheuristics. Its advantages and
problems are discussed and we conclude that this is one pos- on this behalf. We first specify how such a unified frame-
sible and useful way to gain a better understanding of existing work can be described and utilised. The next section pro-
metaheuristics and to deal with new approaches. vides insights into conceptual ways to analyse metaheuris-
tics based on their components and how this can be comple-
mented by empirical studies. The advantages and problems
Introduction
of the approach itself and in relation to Lifelike Systems are
Metaheuristics are capable of successfully approximating discussed and we end on a short conclusion and illustrate
solutions of black-box optimisation problems where exact options for future work.
optimisers are not applicable. This makes them suitable for
a number of tasks, from engineering to biology/medicine,
A Unified View on Metaheuristics
but also within more complex computing systems (Hussain
et al., 2018). In Lifelike Systems, metaheuristics are of- The development of a unified concept for metaheuristics ul-
ten utilised to optimise the parameters of other components, timately results from the demand of more standardisation,
especially machine learning components, enabling the self- reusability, knowledge on components and consistency in
improvement mechanism of these systems. These parameter descriptions (Swan et al., 2015; Sörensen, 2015). In recent
optimisation problems can differ in their often unknown fit- years, some detailed unification strategies were presented,
ness landscapes and the task is complicated by the dynam- each of them with a different goal in mind: from providing a
ically changing environment in which lifelike systems are basis for describing metaheuristics (Bandaru and Deb, 2016)
deployed. Additionally, there can be several areas in the to finding inherent strategies in metaheuristics (Chicco and
system that require an optimiser, e. g. learning components, Mazza, 2020), but also to construct new algorithms (Song
other optimisers or the environment itself. and Fong, 2016), to compare (de Armas et al., 2021) and
For all application areas of metaheuristics, there arises the evaluate (Cruz-Duarte et al., 2020) metaheuristics in terms
same initial question: Which metaheuristic is the most suit- of their components. Ultimately, the unification facilitates
Copyright ©2021 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
deriving differences and similarities of metaheuristics, en- ators, thus assisting in the assembly of algorithms for the
ables the transfer of features and the construction of combi- given problem, but also in the development of hybrid algo-
nations of metaheuristics (Bandaru and Deb, 2016). rithms and hyperheuristics.
Based on these approaches towards a unified metaheuris-
tic framework, a component-based concept is depicted in Analysis of Metaheuristic Components
Figure 1. It combines the ideas of Bandaru and Deb (2016)
and de Armas et al. (2021) and is applicable to both, a con- With a unified framework as a basis for dissecting meta-
ceptual comparison of metaheuristics based on their compo- heuristics, the resulting components can be further analysed
nents, and the empirical analysis of the specific implementa- to determine their respective capabilities. This can be by a
tions. The main components identified are those for initial- purely conceptual analysis, enabling a rough assessment of
isation, selection, solution generation, replacement and up- the functioning and the features of the components and their
date of solution, archiving and termination. Their structure operators, or by empirical studies based on an component-
and their common operators delineate the different meta- based implementation with operator exchange facilities.
heuristic frameworks as defined by Sörensen and Glover
(2013). A specific metaheuristic algorithm is then deter- Conceptual Analysis
mined by using individual operators for each component, A conceptual analysis aims at finding common features of
usually depending on the problem. Additionally, more than components, operators and their different possible combi-
one operator can be inherent to one component, especially nations. General features inherent to metaheuristic compo-
for the generation and archiving mechanisms. nents and their operators are often included in classifica-
tion approaches as they order metaheuristics according to
their capabilities which are related to their structure (Molina
Initialisation
et al., 2020; Stork et al., 2020; Fausto et al., 2019; Stegherr
et al., 2020). Furthermore, they are intended to facilitate
the selection of an appropriate algorithm for a given prob-
lem, for example by matching the fitness function and the
Selection corresponding fitness landscape to algorithm classes (Stork
et al., 2020). Ultimately, the algorithms should be classi-
fied by their performance on different optimisation prob-
Archiving
lems (Woodward and Swan, 2010). This, however, requires
detailed experiments to determine the respective algorithm
Generation performances.
Among those criteria used for the classification of meta-
heuristics, some directly relate to metaheuristic components
and the resulting algorithmic features. These features can
Replacement be related to the specific search procedures utilised, e. g.
& Update neighbourhood search, hill climbing or population-based
search (Lones, 2014, 2019). They are, however, not neces-
sarily determined by one single component or operator but
can result from a specific combination of those. Addition-
Termination ally, one component and even one operator can utilise sev-
eral search procedures. Other algorithmic features depend-
ing on these functional parts of a metaheuristic and describ-
Figure 1: Unified component view on metaheuristics ing the overall capabilities of the approach are presented
(adapted from Bandaru and Deb (2016); de Armas et al. by Chicco and Mazza (2020). They include, for example,
(2021)). the use of elitism, selection and self-adaptation strategies.
Again, these features can result from a combination of oper-
The advantages of such a unified view on metaheuristics ators and one operator can contribute to several features.
are manifold. On the one hand, it facilitates the analysis of Another way to analyse metaheuristic components is pro-
existing algorithms independent of their metaphor. On the vided by Blum and Roli (2003). They classify operators by
other hand, the descriptions of new approaches can be ori- their intensification and diversification behaviour in terms of
ented towards a unified framework to allow an easier grasp its dependency on the objective function, any other function
of their concepts. Implementation-wise, it enables a modu- or randomness. In this case, operators are analysed individ-
lar approach for the construction of metaheuristic algorithms ually, but can be compared to other operators for the same
and an unproblematic exchange of components and oper- component.
A conceptual analysis of metaheuristic components and tics on specific problems. Furthermore, it can give hints as to
algorithm-specific operators according to features such as which theoretical analyses are important to perform first. In
those presented here does not only allow for a better terms of the overall analysis of metaheuristic components,
overview of metaheuristic strategies but also facilitates the it allows specifying and quantifying the conceptual analysis.
selection of appropriate algorithms. It enables the construc- Especially the utilisation of a unified structure for the evalu-
tion of profiles for operators and their combinations within ation of different component and operator combinations fa-
a component structure, which can be used for comparing cilitates the analysis and comparison of metaheuristics inde-
different metaheuristics but also readily present the features pendent of their frameworks and metaphors.
that might be required for the problem at hand. Further-
more, in combination with problem-specific information, it
directly aids in choosing a suitable algorithm. Advantages and Problems of a
Component-based View on Metaheuristics
Empirical Analysis
The goal of an empirical component analysis is to provide The analysis of metaheuristic components based on a uni-
problem-specific and generalised information on the perfor- fied framework provides several possibilities. First, it helps
mance and behaviour of metaheuristics. It enables a more to bring structure to the vast field of metaheuristics by deter-
application-oriented comparison of algorithms than the con- mining common features of the different approaches. This
ceptual analysis and complements it by presenting important allows to systematically analyse metaheuristics according to
knowledge for matching algorithms to optimisation prob- the capabilities of their components and respective opera-
lems as described by Woodward and Swan (2010). tors. Furthermore, standardising the description of meta-
To this end, the empirical analysis of metaheuristic com- heuristics by focussing on their components’ features re-
ponents has to focus on measuring performance, as well as duces the dependence on metaphors and provides a basis for
the search behaviour of the algorithms. Performance mea- the presentation of novel approaches. The empirical analysis
sures include the quality of the found solution and the bud- adds further advantages. Problem-specific knowledge can be
get (Halim et al., 2020), while behavioural measures are, gained on the performance and behaviour of metaheuristics
e. g. the solution similarity and the intensification and diver- depending on their components, and in some cases operators
sification rates (Scheibenpflug et al., 2012). Furthermore, may even prove to be generally well suited or not applica-
the operators of the respective components have to be eval- ble at all. These analyses make it easier for Lifelike System
uated in different combinations, as these combinations can engineers to evaluate whether the metaheuristics are a good
exhibit mutually reinforcing effects on performance and be- fit for the given problem. Additionally, components and op-
haviour. This is facilitated by the use of a unified framework erators within a unified framework can provide an easy way
instead of the individual metaheuristics, as well as the trans- to configure and change (e. g. hybridise) metaheuristic algo-
fer of operators for one component from one algorithm to rithms depending on the problem at hand, without having to
another. The overall analysis has to be performed according construct each algorithm individually.
to benchmarking guidelines to provide valid results (LaTorre However, there still are some problems. It remains to be
et al., 2020; Bartz-Beielstein et al., 2020). determined if a component analysis based on these concepts
A first evaluation in a unified framework with a focus is feasible. This concerns the unification approach, which
on the performance of the algorithms is provided by Cruz- might not be viable for all metaheuristics, as well as the em-
Duarte et al. (2020), showing that some operators can be pirical analysis, which is extensive when aiming at analysing
responsible for the overall performance on a specific prob- all or even most existing component structures and their re-
lem. Another empirical analysis of performance and inten- spective operators. In addition, it might not be worth the
sification and diversification behaviour, focussed on differ- effort if the often criticised strongly metaphor-related meta-
ent operator combinations of Genetic Algorithms, was per- heuristics do not provide any new insights or useful features.
formed by Scheibenpflug and Wagner (2013). They showed For the conceptual analysis, it is still questionable how rele-
that the combination of operators can result in different be- vant the gathered information on features is for applications
haviour than the individual operators would suggest. These but also for comparisons. Furthermore, empirical studies
studies show how much information and understanding on that aim at providing problem-specific information require
metaheuristic algorithms can be gained by analysing their knowledge on the problems and their characteristics as well,
components. Increasing the number of operators and com- which is still a research area needing attention. Altogether,
binations and extending the performance and behavioural the information gathered by this approach might not be suf-
measurements will provide further comprehensive insights. ficient to effectively facilitate the selection of appropriate
Next to the general gain of knowledge, an empirical com- algorithms, neither in Lifelike Systems nor for any other op-
ponent analysis bridges the gap until theoretical proofs are timisation problem. Last but not least, no conceptual or em-
presented for the behaviour and applicability of metaheuris- pirical analysis is as good as a formal theoretical approach.
Conclusion Chandrasekaran, S., Eftimov, T., Fischbach, A., Kerschke,
P., Cava, W. L., Lopez-Ibanez, M., Malan, K. M., Moore,
The field of metaheuristic research becomes less and less
J. H., Naujoks, B., Orzechowski, P., Volz, V., Wagner, M.,
transparent in terms of new approaches and extensions to and Weise, T. (2020). Benchmarking in Optimization: Best
existing algorithms or frameworks. This makes it increas- Practice and Open Issues. arXiv:2007.03488.
ingly difficult to assess the features and capabilities of the
respective algorithms and therefore the selection of a suit- Blum, C. and Roli, A. (2003). Metaheuristics in combinatorial
optimization. ACM Computing Surveys, 35(3):268–308.
able approach. While this problem could be alleviated by
extensive theoretical analyses of metaheuristics, this again Chicco, G. and Mazza, A. (2020). Metaheuristic Optimization of
is a difficult task requiring time and expertise. Power and Energy Systems: Underlying Principles and Main
Another approach to analyse metaheuristics more com- Issues of the ‘Rush to Heuristics’. Energies, 13(19):5097.
prehensively while extensive theory is not yet available is Cruz-Duarte, J. M., Ortiz-Bayliss, J. C., Amaya, I., Shi, Y.,
described in this paper. It is based on a unified understand- Terashima-Marı́n, H., and Pillay, N. (2020). Towards a Gen-
ing of metaheuristics revealing common components. These eralised Metaheuristic Model for Continuous Optimisation
components and their respective operators, which define in- Problems. Mathematics, 8(11):2046.
dividual algorithms, can be analysed conceptually as well
de Armas, J., Lalla-Ruiz, E., Tilahun, S. L., and Voß, S. (2021).
as empirically. The analyses provide different levels of de- Similarity in metaheuristics: a gentle step towards a compar-
tail and, when combined, can offer a comprehensive view ison methodology. Natural Computing.
on metaheuristics. Furthermore, utilising a unified struc-
ture for metaheuristics presents an efficient basis for imple- Fausto, F., Reyna-Orta, A., Cuevas, E., Andrade, Á. G., and Perez-
mentation, hybridisation and even the development of hyper- Cisneros, M. (2019). From ants to whales: metaheuristics for
all tastes. Artificial Intelligence Review, 53(1):753–810.
heuristics, as operators can be exchanged easily before and
during the optimisation process. Altogether, it facilitates the Halim, A. H., Ismail, I., and Das, S. (2020). Performance assess-
application of suitable metaheuristics in all domains, includ- ment of the metaheuristic optimization algorithms: an ex-
ing Lifelike Systems. haustive review. Artificial Intelligence Review, 54(3):2323–
2409.
The execution of metaheuristic component analyses in
a unified framework can follow different approaches, as Hussain, K., Salleh, M. N. M., Cheng, S., and Shi, Y. (2018). Meta-
shown by Cruz-Duarte et al. (2020) or de Armas et al. heuristic research: a comprehensive survey. Artificial Intelli-
(2021). However, none of them include extensive concep- gence Review, 52(4):2191–2233.
tual comparisons and empirical evaluations of performance
LaTorre, A., Molina, D., Osaba, E., Ser, J. D., and Herrera, F.
and behaviour yet. We want to align our approach with the (2020). Fairness in Bio-inspired Optimization Research: A
structure presented in this paper. To this end, we already Prescription of Methodological Guidelines for Comparing
examined classification systems to utilise their criteria for a Meta-heuristics. arXiv:2004.09969.
conceptual analysis of metaheuristic components (Stegherr
Lones, M. A. (2014). Metaheuristics in nature-inspired algorithms.
et al., 2020). In terms of empirical analysis, we estab-
In Proceedings of the 2014 conference companion on Genetic
lished our basic unified structure and determined the ex- and evolutionary computation companion - GECCO Comp
perimental design necessary for empirical component anal- '14. ACM Press.
yses (Stegherr et al., 2021). The next steps include the ex-
amination of metaheuristics and their components and their Lones, M. A. (2019). Mitigating Metaphors: A Comprehensible
Guide to Recent Nature-Inspired Algorithms. SN Computer
incorporation into a unified framework. Furthermore, the Science, 1(49).
respective operators will be reassembled to provide differ-
ent combinations and to determine their influences in these Molina, D., Poyatos, J., Del Ser, J., Garcı́a, S., Hussain, A., and
combinations. Then, the combinations will be analysed con- Herrera, F. (2020). Comprehensive Taxonomies of Nature-
and Bio-inspired Optimization: Inspiration versus Algorith-
ceptually to detect important common features, as well as
mic Behavior, Critical Analysis and Recommendations. Cog-
in large experiments to evaluate their performance and be- nitive Computation.
haviour on different optimisation problems. Though this ap-
proach can be extensive in terms of the number of included Scheibenpflug, A. and Wagner, S. (2013). An Analysis of the Inten-
components and its feasibility for all metaheuristics still has sification and Diversification Behavior of Different Operators
for Genetic Algorithms. In Computer Aided Systems Theory
to be shown, it will ultimately provide comprehensive infor- - EUROCAST 2013, pages 364–371. Springer Berlin Heidel-
mation on metaheuristics and their applicability. berg.
References Scheibenpflug, A., Wagner, S., Pitzer, E., Burlacu, B., and Affen-
Bandaru, S. and Deb, K. (2016). Metaheuristic Techniques. In zeller, M. (2012). On the analysis, classification and pre-
Decision Sciences, pages 693–750. CRC Press. diction of metaheuristic algorithm behavior for combinatorial
optimization problems. 24th European Modeling and Simu-
Bartz-Beielstein, T., Doerr, C., van den Berg, D., Bossek, J., lation Symposium, EMSS 2012, pages 368–372.
Song, Q. and Fong, S. (2016). Brick-Up Metaheuristic Algorithms.
In 2016 5th IIAI International Congress on Advanced Applied
Informatics (IIAI-AAI). IEEE.
Sörensen, K. (2015). Metaheuristics-the metaphor exposed. Inter-
national Transactions in Operational Research, 22(1):3–18.
Stegherr, H., Heider, M., and Hähner, J. (2020). Classifying Meta-
heuristics: Towards a unified multi-level classification sys-
tem. Natural Computing.
Stegherr, H., Heider, M., Luley, L., and Hähner, J. (2021). De-
sign of Large-Scale Metaheuristic Component Studies. To be
published in the 2021 Genetic and Evolutionary Computation
Conference Companion (GECCO ’21 Companion).
Stork, J., Eiben, A. E., and Bartz-Beielstein, T. (2020). A new
taxonomy of global optimization algorithms. Natural Com-
puting.
Swan, J., Adriaensen, S., Bishr, M., Burke, E. K., Clark, J. A., De
Causmaecker, P., Durillo, J., Hammond, K., Hart, E., John-
son, C. G., Kocsis, Z. A., Kovitz, B., Krawiec, K., Martin, S.,
Merelo, J. J., Minku, L. L., Özcan, E., Pappa, G. L., Pesch, E.,
Garcia-Sànchez, P., Schaerf, A., Sim, K., Smith, J., Stützle,
T., Stefan, V., Wagner, S., and Yao, X. (2015). A Research
Agenda for Metaheuristic Standardization. pages 1–3. Paper
presented at MIC 2015: the XI Metaheuristics International
Conference, Agadir, United Kingdom.
Sörensen, K. and Glover, F. W. (2013). Metaheuristics. In Ency-
clopedia of Operations Research and Management Science,
pages 960–970. Springer US.
Wolpert, D. H. and Macready, W. G. (1997). No free lunch the-
orems for optimization. IEEE Transactions on Evolutionary
Computation, 1(1):67–82.
Woodward, J. R. and Swan, J. (2010). Why classifying search al-
gorithms is essential. In 2010 IEEE International Conference
on Progress in Informatics and Computing. IEEE.