Computer Science – Neural and Evolutionary Computing
Scientific paper
2011-01-04
Computer Science
Neural and Evolutionary Computing
Contains results from our GECCO 2010 and CEC 2010 conference paper
Scientific paper
In this work, we introduce multiplicative drift analysis as a suitable way to analyze the runtime of randomized search heuristics such as evolutionary algorithms. We give a multiplicative version of the classical drift theorem. This allows easier analyses in those settings where the optimization progress is roughly proportional to the current distance to the optimum. To display the strength of this tool, we regard the classical problem how the (1+1) Evolutionary Algorithm optimizes an arbitrary linear pseudo-Boolean function. Here, we first give a relatively simple proof for the fact that any linear function is optimized in expected time $O(n \log n)$, where $n$ is the length of the bit string. Afterwards, we show that in fact any such function is optimized in expected time at most ${(1+o(1)) 1.39 \euler n\ln (n)}$, again using multiplicative drift analysis. We also prove a corresponding lower bound of ${(1-o(1))e n\ln(n)}$ which actually holds for all functions with a unique global optimum. We further demonstrate how our drift theorem immediately gives natural proofs (with better constants) for the best known runtime bounds for the (1+1) Evolutionary Algorithm on combinatorial problems like finding minimum spanning trees, shortest paths, or Euler tours.
Doerr Benjamin
Johannsen Daniel
Winzen Carola
No associations
LandOfFree
Multiplicative Drift Analysis does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Multiplicative Drift Analysis, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiplicative Drift Analysis will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-75336