Fixed budget computations: a different perspective on run time analysis

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

33 Citations (SciVal)

Abstract

Randomised search heuristics are used in practice to solve difficult problems where no good problem-specific algorithm is known. They deliver a solution of acceptable quality in reasonable time in many cases. When theoretically analysing the performance of randomised search heuristics one usually considers the average time needed to find an optimal solution or one of a pre-specified approximation quality. This is very different from practice where usually the algorithm is stopped after some time. For a theoretical analysis this corresponds to investigating the quality of the solution obtained after a pre-specified number of function evaluations called budget. Such a perspective is taken here and two simple randomised search heuristics, random local search and the (1+1) evolutionary algorithm, are analysed on simple and well-known example functions. If the budget is significantly smaller than the expected time needed for optimisation the behaviour of the algorithms can be very different depending on the problem at hand. Precise analytical results are proven. They demonstrate novel and interesting challenges in the analysis of randomised search heuristics. The potential of this different perspective to provide a more practically useful theory is shown.
Original languageEnglish
Title of host publicationGECCO '12 Proceedings of the 14th annual conference on Genetic and evolutionary computation
EditorsTerence Soule
PublisherAssociation for Computing Machinery
Pages1325-1332
Number of pages8
ISBN (Print)978-1-4503-1177-9
DOIs
Publication statusPublished - 07 Jul 2012

Fingerprint

Dive into the research topics of 'Fixed budget computations: a different perspective on run time analysis'. Together they form a unique fingerprint.

Cite this