Performance analysis of randomised search heuristics operating with a fixed budget

Research output: Contribution to journalArticlepeer-review

59 Citations (SciVal)
135 Downloads (Pure)

Abstract

When for a difficult real-world optimisation problem no good problem-specific algorithm is available often randomised search heuristics are used. They are hoped to deliver good solutions in acceptable time. The theoretical analysis usually concentrates on the average time needed to find an optimal or approximately optimal solution. This matches neither the application in practice nor the empirical analysis since usually optimal solutions are not known and even if found cannot be recognised. More often the algorithms are stopped after some time. This motivates a theoretical analysis to concentrate on the quality of the best solution obtained after a pre-specified number of function evaluations called budget. Using this perspective two simple randomised search heuristics, random local search and the (1+1) evolutionary algorithm, are analysed on some well-known example problems. Upper and lower bounds on the expected quality of a solution for a fixed budget of function evaluations are proven. The analysis shows novel and challenging problems in the study of randomised search heuristics. It demonstrates the potential of this shift in perspective from expected run time to expected solution quality.
Original languageEnglish
Pages (from-to)39-58
Number of pages20
JournalTheoretical Computer Science
Volume545
Early online date17 Jun 2013
DOIs
Publication statusPublished - 14 Aug 2014

Keywords

  • runtime analysis
  • fixed budget computation
  • random local search
  • (1 + 1) EA
  • OneMax
  • leadingOnes
  • jump
  • ridge

Fingerprint

Dive into the research topics of 'Performance analysis of randomised search heuristics operating with a fixed budget'. Together they form a unique fingerprint.

Cite this