A method to derive fixed budget results from expected optimisation times

Benjamin Doerr, Thomas Jansen, Carsten Witt, Christine Zarges

Research output: Chapter in Book/Report/Conference proceedingConference Proceeding (Non-Journal item)

47 Citations (SciVal)

Abstract

At last year's GECCO a novel perspective for theoretical performance analysis of evolutionary algorithms and other randomised search heuristics was introduced that concentrates on the expected function value after a pre-defined number of steps, called budget. This is significantly different from the common perspective where the expected optimisation time is analysed. While there is a huge body of work and a large collection of tools for the analysis of the expected optimisation time the new fixed budget perspective introduces new analytical challenges. Here it is shown how results on the expected optimisation time that are strengthened by deviation bounds can be systematically turned into fixed budget results. We demonstrate our approach by considering the (1+1) EA on LeadingOnes and significantly improving previous results. We prove that deviating from the expected time by an additive term of ω(n3/2) happens only with probability o(1). This is turned into tight bounds on the function value using the inverse function. We use three, increasingly strong or general approaches to proving the deviation bounds, namely via Chebyshev's inequality, via Chernoff bounds for geometric random variables, and via variable drift analysis.

Original languageEnglish
Title of host publicationGECCO '13: Proceedings of the 15th annual conference on Genetic and evolutionary computation
EditorsChristian Blum
PublisherAssociation for Computing Machinery
Pages1581-1588
Number of pages8
ISBN (Print)9781450319638
DOIs
Publication statusPublished - 06 Jul 2013
EventGECCO 2013 - Genetic and Evolutionary Computation Conference - Amsterdam, Netherlands
Duration: 06 Jul 201310 Jul 2013

Conference

ConferenceGECCO 2013 - Genetic and Evolutionary Computation Conference
Country/TerritoryNetherlands
CityAmsterdam
Period06 Jul 201310 Jul 2013

Keywords

  • (1+1) EA
  • Fixed budget computation
  • LeadingOnes
  • Runtime analysis
  • Tail bounds

Fingerprint

Dive into the research topics of 'A method to derive fixed budget results from expected optimisation times'. Together they form a unique fingerprint.

Cite this