Analysing Equilibrium States for Population Diversity
Open Access
- 16 April 2024
- journal article
- research article
- Published by Springer Nature in Algorithmica
- Vol. 86 (7) , 2317-2351
Abstract
Population diversity is crucial in evolutionary algorithms as it helps with global exploration and facilitates the use of crossover. Despite many runtime analyses showing advantages of population diversity, we have no clear picture of how diversity evolves over time. We study how the population diversity of $$(\mu +1)$$ algorithms, measured by the sum of pairwise Hamming distances, evolves in a fitness-neutral environment. We give an exact formula for the drift of population diversity and show that it is driven towards an equilibrium state. Moreover, we bound the expected time for getting close to the equilibrium state. We find that these dynamics, including the location of the equilibrium, are unaffected by surprisingly many algorithmic choices. All unbiased mutation operators with the same expected number of bit flips have the same effect on the expected diversity. Many crossover operators have no effect at all, including all binary unbiased, respectful operators. We review crossover operators from the literature and identify crossovers that are neutral towards the evolution of diversity and crossovers that are not.
Keywords
Funding Information
- Universität Passau
This publication has 64 references indexed in Scilit:
- Population Diversity Leads to Short Running Times of Lexicase Selection2022
- On Non-elitist Evolutionary Algorithms Optimizing Fitness Functions with a Plateau2020
- The Benefits of Population Diversity in Evolutionary Algorithms: A Survey of Rigorous Runtime Analyses2019
- Niching in Evolutionary Algorithms2012
- Negative Drift in Populations2010
- A Combination Genetic Algorithm with Applications on Portfolio Optimization2006
- The Underlying Similarity of Diversity Measures Used in Evolutionary Computation2003
- The Analysis of Evolutionary Algorithms—A Proof That Crossover Really Can HelpAlgorithmica, 2002
- The algebra of genetic algorithmsAnnals of Mathematics and Artificial Intelligence, 1994
- Measuring biological diversityEnvironmental and Ecological Statistics, 1994