Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Royal Road Functions and the (1 + λ) Evolutionary Algorithm
Speaker:Marvin Künnemann
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 13 June 2013
Duration:30 Minutes
Building:E1 4
Evolutionary algorithms (EAs) are widely applied in practice, yet most theoretically rigorous analyses of their performance are restricted to rather simple settings, since these processes are highly non-trivial to analyze. We aim to contribute to the theoretical understanding of EAs by examining the runtime of an evolutionary algorithm with a non-trivial offspring population on an interesting test function class.

For a royal road function defined on bit-strings of length n and having block size d \ge log n + (c+1+ε) log d, we prove that the (1+λ) evolutionary algorithm with λ = \Theta(n^c) finds the optimum in an expected number of O((2^d/d^c) (n/d) log (n/d)) generations. As this does not yield the intuitively expected speed-up of λ, we provide a lower bound of O(2^d/d^c) that shows that the (1+λ) EA indeed fails to achieve a high speed-up. Our results indicate that non-trivial offspring populations may help to locate search points outside plateaus, but will not speed-up the search inside plateaus.

Name(s):Marvin Künnemann
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Marvin Künnemann, 06/12/2013 11:36 PM
  • Marvin Künnemann, 06/03/2013 01:16 PM -- Created document.