Precision, Local Search and Unimodal Functions

M Dietzfelbinger, Jonathan Rowe, I Wegener, P Woelfel

Research output: Contribution to journalArticle

4 Citations (Scopus)

Abstract

We investigate the effects of precision on the efficiency of various local search algorithms on 1-D unimodal functions. We present a (1+1)-EA with adaptive step size which finds the optimum in O(log n) steps, where n is the number of points used. We then consider binary (base-2) and reflected Gray code representations with single bit mutations. The standard binary method does not guarantee locating the optimum, whereas using the reflected Gray code does so in I similar to((log n)(2)) steps. A(1+1)-EA with a fixed mutation probability distribution is then presented which also runs in O((log n)(2)). Moreover, a recent result shows that this is optimal (up to some constant scaling factor), in that there exist unimodal functions for which a lower bound of Omega((log n)(2)) holds regardless of the choice of mutation distribution. For continuous multimodal functions, the algorithm also locates the global optimum in O((log n)(2)). Finally, we show that it is not possible for a black box algorithm to efficiently optimise unimodal functions for two or more dimensions (in terms of the precision used).
Original languageEnglish
Pages (from-to)301-322
Number of pages22
JournalAlgorithmica
Volume59
Issue number3
Early online date13 Aug 2009
DOIs
Publication statusPublished - 1 Mar 2011

Fingerprint

Dive into the research topics of 'Precision, Local Search and Unimodal Functions'. Together they form a unique fingerprint.

Cite this