Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

Date and Time: Thursday, April 27, 2023, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Marc Kaufmann

OneMax is not the Easiest Function for Fitness Improvements

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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login