Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, April 27, 2023, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Marc Kaufmann
Evolutionary algorithms are widely used optimization techniques that are inspired by nature. Fitness landscapes and their difficulty play a crucial role in the performance of these algorithms. In this talk, we investigate the (1:s+1) success rule for controlling the population size of the (1, λ)-Evolutionary Algorithm (EA). Hevia Fajardo and Sudholt showed that this parameter control mechanism can encounter problems for large s if the fitness landscape is too easy, and conjectured that the OneMax benchmark is the worst case, as it is considered the easiest fitness landscape in some well-established sense. We disprove this conjecture by demonstrating that there exist s and ε such that the self-adjusting (1, λ)-EA with the (1:s+1)-rule optimizes OneMax efficiently when started with εn zero-bits, but does not find the optimum in polynomial time on Dynamic BinVal. Our results indicate that there are landscapes where the problem of the (1:s+1)-rule for controlling the population size of the (1, λ)-EA is more severe than for OneMax.The work presented is joint with Maxime Larcher, Johannes Lengler and Xun Zou.
Automatic MiSe System Software Version 1.4803M | admin login