@article{LenglerOprisSudholt2024, author = {Lengler, Johannes and Opris, Andre and Sudholt, Dirk}, title = {Analysing Equilibrium States for Population Diversity}, series = {Algorithmica (ISSN: 1432-0541)}, volume = {86}, journal = {Algorithmica (ISSN: 1432-0541)}, number = {7}, publisher = {Springer US}, address = {New York}, issn = {0178-4617}, doi = {10.1007/s00453-024-01226-3}, url = {http://nbn-resolving.de/urn:nbn:de:101:1-2406282100292.409184699704}, pages = {2317 -- 2351}, year = {2024}, 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 (μ+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.}, language = {en} } @article{HeviaFajardoSudholt2023, author = {Hevia Fajardo, Mario Alejandro and Sudholt, Dirk}, title = {Self-adjusting Population Sizes for Non-elitist Evolutionary Algorithms: why Success Rates Matter}, series = {Algorithmica}, volume = {86}, journal = {Algorithmica}, number = {2}, publisher = {Springer Nature}, address = {Berlin}, doi = {10.1007/s00453-023-01153-9}, url = {http://nbn-resolving.de/urn:nbn:de:101:1-2023102616463077837436}, pages = {526 -- 565}, year = {2023}, abstract = {Evolutionary algorithms (EAs) are general-purpose optimisers that come with several parameters like the sizes of parent and offspring populations or the mutation rate. It is well known that the performance of EAs may depend drastically on these parameters. Recent theoretical studies have shown that self-adjusting parameter control mechanisms that tune parameters during the algorithm run can provably outperform the best static parameters in EAs on discrete problems. However, the majority of these studies concerned elitist EAs and we do not have a clear answer on whether the same mechanisms can be applied for non-elitist EAs. We study one of the best-known parameter control mechanisms, the one-fifth success rule, to control the offspring population size λ in the non-elitist (1, λ) EA. It is known that the (1, λ) EA has a sharp threshold with respect to the choice of λ where the expected runtime on the benchmark function OneMax changes from polynomial to exponential time. Hence, it is not clear whether parameter control mechanisms are able to find and maintain suitable values of λ. For OneMax we show that the answer crucially depends on the success rates (i. e. a one-(s + 1)-th success rule). We prove that, if the success rate is appropriately small, the self-adjusting (1, λ) EA optimises OneMax in O(n) expected generations and O(n log n) expected evaluations, the best possible runtime for any unary unbiased black-box algorithm. A small success rate is crucial: we also show that if the success rate is too large, the algorithm has an exponential runtime on OneMax and other functions with similar characteristics.}, language = {en} }