Tight Bounds on the Optimization Time of a Randomized Search Heuristic on Linear Functions - Danish National Research Database-Den Danske Forskningsdatabase

^{1} Department of Applied Mathematics and Computer Science, Technical University of Denmark^{2} Algorithms and Logic, Department of Applied Mathematics and Computer Science, Technical University of Denmark

DOI:

10.1017/S0963548312000600

Abstract:

The analysis of randomized search heuristics on classes of functions is fundamental to the understanding of the underlying stochastic process and the development of suitable proof techniques. Recently, remarkable progress has been made in bounding the expected optimization time of a simple evolutionary algorithm, called (1+1) EA, on the class of linear functions. We improve the previously best known bound in this setting from (1.39+o(1))en ln n to en ln n+O(n) in expectation and with high probability, which is tight up to lower-order terms. Moreover, upper and lower bounds for arbitrary mutation probabilities p are derived, which imply expected polynomial optimization time as long as p = O((ln n)/n) and p = Ω(n −C ) for a constant C > 0, and which are tight if p = c/n for a constant c > 0. As a consequence, the standard mutation probability p = 1/n is optimal for all linear functions, and the (1+1) EA is found to be an optimal mutation-based algorithm. Furthermore, the algorithm turns out to be surprisingly robust since the large neighbourhood explored by the mutation operator does not disrupt the search.

Type:

Journal article

Language:

English

Published in:

Combinatorics, Probability and Computing, 2013, Vol 22, Issue 2, p. 294-318