Hostname: page-component-745bb68f8f-b95js Total loading time: 0 Render date: 2025-01-11T04:08:10.076Z Has data issue: false hasContentIssue false
  • English
  • Français

Tight Bounds on the Optimization Time of a Randomized Search Heuristic on Linear Functions†

Published online by Cambridge University Press:  09 January 2013

CARSTEN WITT
CARSTEN WITT*
Affiliation:
DTU Informatics, Technical University of Denmark, 2800 Kgs. Lyngby, Denmark (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

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.

Keywords

Primary 68W20Secondary 68Q25
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 22 , Issue 2 , March 2013 , pp. 294 - 318
Copyright
Copyright © Cambridge University Press 2013

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

An extended abstract of this paper appeared at STACS'12 [27].

References

[1]Auger, A. and Doerr, B. (2011) Theory of Randomized Search Heuristics: Foundations and Recent Developments, World Scientific.CrossRefGoogle Scholar
[2]Bäck, T. (1993) Optimal mutation rates in genetic search. In Proc. International Conference on Genetic Algorithms, ICGA '93, Morgan Kaufmann, pp. 2–8.Google Scholar
[3]Doerr, B., Fouz, M. and Witt, C. (2010). Quasirandom evolutionary algorithms. In Proc. Genetic and Evolutionary Computation Conference, GECCO '10, ACM Press, pp. 1457–1464.CrossRefGoogle Scholar
[4]Doerr, B., Fouz, M. and Witt, C. (2011). Sharp bounds by probability-generating functions and variable drift. In Proc. Genetic and Evolutionary Computation Conference, GECCO '11, ACM Press, pp. 2083–2090.CrossRefGoogle Scholar
[5]Doerr, B. and Goldberg, L. A. (2010). Adaptive drift analysis. In Proc. Parallel Problem Solving from Nature XI, PPSN '10, Vol. 6238 of Lecture Notes in Computer Science, Springer, pp. 32–41.Google Scholar
[6]Doerr, B. and Goldberg, L. A. (2012). Adaptive drift analysis. Algorithmica, in press. Available online: http://www.springerlink.com/content/v0n75x65k016r477Google Scholar
[7]Doerr, B., Johannsen, D. and Winzen, C. (2010). Drift analysis and linear functions revisited. In Proc. Congress on Evolutionary Computation, CEC '10, IEEE Press, pp. 1–8.Google Scholar
[8]Doerr, B., Johannsen, D. and Winzen, C. (2010). Multiplicative drift analysis. In Proc. Genetic and Evolutionary Computation Conference, GECCO '10, ACM Press, pp. 1449–1456.CrossRefGoogle Scholar
[9]Droste, S., Jansen, T. and Wegener, I. (2000). A natural and simple function which is hard for all evolutionary algorithms. In Proc. 26th Annual Conference of the IEEE Industrial Electronics Society, IECON '00, pp. 2704–2709.CrossRefGoogle Scholar
[10]Droste, S., Jansen, T. and Wegener, I. (2002). On the analysis of the (1+1) evolutionary algorithm. Theoret. Comput. Sci. 276 51–81.CrossRefGoogle Scholar
[11]Hajek, B. (1982). Hitting-time and occupation-time bounds implied by drift analysis with applications. Adv. Appl. Probab. 13 502–525.CrossRefGoogle Scholar
[12]He, J. and Yao, X. (2001). Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence 127 57–85.CrossRefGoogle Scholar
[13]He, J. and Yao, X. (2004). A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Computing 3 21–35.CrossRefGoogle Scholar
[14]Jägersküpper, J. (2007). Algorithmic analysis of a basic evolutionary algorithm for continuous optimization. Theoret. Comput. Sci. 379 329–347.CrossRefGoogle Scholar
[15]Jägersküpper, J. (2008). A blend of Markov-chain and drift analysis. In Proc. Parallel Problem Solving from Nature X, PPSN '08, Vol. 5199 of Lecture Notes in Computer Science, Springer, pp. 41–51.Google Scholar
[16]Jägersküpper, J. (2011). Combining Markov-chain analysis and drift analysis: The (1+1) evolutionary algorithm on linear functions reloaded. Algorithmica 59 409–424.CrossRefGoogle Scholar
[17]Lehre, P. K. and Witt, C. (2012). Black-box search by unbiased variation. Algorithmica 64 623–642.CrossRefGoogle Scholar
[18]Marshall, A. W., Olkin, I. and Arnold, B. (2011). Inequalities: Theory of Majorization and its Applications, second edition, Springer.CrossRefGoogle Scholar
[19]Motwani, R. and Raghavan, P. (1995). Randomized Algorithms, Cambridge University Press.CrossRefGoogle Scholar
[20]Mühlenbein, H. (1992). How genetic algorithms really work I: Mutation and hillclimbing. In Proc. Parallel Problem Solving from Nature I, PPSN '92, Elsevier, pp. 15–26.Google Scholar
[21]Neumann, F. and Witt, C. (2010). Bioinspired Computation in Combinatorial Optimization: Algorithms and Their Computational Complexity, Natural Computing Series, Springer.CrossRefGoogle Scholar
[22]Sudholt, D. (2010). General lower bounds for the running time of evolutionary algorithms. In Proc. Parallel Problem Solving from Nature XI, PPSN '10, Vol. 6238 of Lecture Notes in Computer Science, Springer, pp. 124–133.Google Scholar
[23]Sudholt, D. (2012). A new method for lower bounds on the running time of evolutionary algorithms. IEEE Trans. Evolutionary Computation, to appear. Preprint: http://dx.doi.org/10.1109/TEVC.2012.2202241CrossRefGoogle Scholar
[24]Wegener, I. (2001). Methods for the analysis of evolutionary algorithms on pseudo-Boolean functions. In Evolutionary Optimization (Sarker, R., Mohammadian, M. and Yao, X., eds), Kluwer.Google Scholar
[25]Wegener, I. and Witt, C. (2005). On the analysis of a simple evolutionary algorithm on quadratic pseudo-boolean functions. J. Discrete Algorithms 3 61–78.CrossRefGoogle Scholar
[26]Wegener, I. and Witt, C. (2005). On the optimization of monotone polynomials by simple randomized search heuristics. Combin. Probab. Comput. 14 225–247.CrossRefGoogle Scholar
[27]Witt, C. (2012). Optimizing linear functions with randomized search heuristics: The robustness of mutation. In Proc. Symposium on Theoretical Aspects of Computer Science, STACS '12, Leibniz International Proceedings in Informatics, pp. 420–431. Open access: http://drops.dagstuhl.de/opus/volltexte/2012/3392/.Google Scholar