Do sophisticated evolutionary algorithms perform better than simple ones
2020
Evolutionary algorithms (EAs) come in all shapes and sizes. Theoretical investigations focus on simple, bare-bones EAs while applications often use more sophisticated EAs that perform well on
the problem at hand. What is often unclear is whether a large degree of algorithm sophistication is necessary, and if so, how much
performance is gained by adding complexity to an EA. We address
this question by comparing the performance of a wide range of
theory-driven EAs, from bare-bones algorithms like the (1+1) EA,
a (2+1) GA and simple population-based algorithms to more sophisticated ones like the (1+(λ, λ)) GA and algorithms using fast
(heavy-tailed) mutation operators, against sophisticated and highly
efective EAs from speciic applications. This includes a famous
and highly cited Genetic Algorithm for the Multidimensional Knapsack Problem and the Parameterless Population Pyramid for Ising
Spin Glasses and MaxSat. While for the Multidimensional Knapsack
Problem the sophisticated algorithm performs best, surprisingly, for
large Ising and MaxSat instances the simplest algorithm performs
best. We also derive conclusions about the usefulness of populations, crossover and fast mutation operators. Empirical results are
supported by statistical tests and contrasted against theoretical
work in an attempt to link theoretical and empirical results on EAs.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
28
References
0
Citations
NaN
KQI