Skip to main navigation Skip to search Skip to main content

Multiplicative drift analysis

  • Max-Planck-Institut fur Informatik

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

67 Citations (Scopus)

Abstract

Drift analysis is one of the strongest tools in the analysis of evolutionary algorithms. Its main weakness is that it is often very hard to find a good drift function. In this paper, we make progress in this direction. We prove 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 objective value. Our drift theorem immediately gives natural proofs for the best known run-time bounds for the (1+1) Evolutionary Algorithm computing minimum spanning trees and shortest paths, since here we may simply take the objective function as drift function. As a more challenging example, we give a relatively simple proof for the fact that any linear function is optimized in time O(n log n). In the multiplicative setting, a simple linear function can be used as drift function (without taking any logarithms). However, we also show that, both in the classical and the multiplicative setting, drift functions yielding good results for all linear functions exist only if the mutation probability is at most c/n for a small constant c.

Original languageEnglish
Title of host publicationProceedings of the 12th Annual Genetic and Evolutionary Computation Conference, GECCO '10
Pages1449-1456
Number of pages8
DOIs
Publication statusPublished - 27 Aug 2010
Externally publishedYes
Event12th Annual Genetic and Evolutionary Computation Conference, GECCO-2010 - Portland, OR, United States
Duration: 7 Jul 2010 → 11 Jul 2010

Publication series

NameProceedings of the 12th Annual Genetic and Evolutionary Computation Conference, GECCO '10

Conference

Conference12th Annual Genetic and Evolutionary Computation Conference, GECCO-2010
Country/TerritoryUnited States
CityPortland, OR
Period7/07/10 → 11/07/10

Keywords

  • Running time analysis
  • Theory

Fingerprint

Dive into the research topics of 'Multiplicative drift analysis'. Together they form a unique fingerprint.

Cite this