Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Optimal Mutation Rates for the (1+\(\lambda \)) EA on OneMax Through Asymptotically Tight Drift Analysis

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We study the (1+\(\lambda \)) EA, a classical population-based evolutionary algorithm, with mutation probability c / n, where \(c>0\) and \(\lambda \) are constant, on the benchmark function OneMax, which counts the number of 1-bits in a bitstring. We improve a well-established result that allows to determine the first hitting time from the expected progress (drift) of a stochastic process, known as the variable drift theorem. Using our improved result, we show that upper and lower bounds on the expected runtime of the (1+\(\lambda \)) EA obtained from variable drift theorems are at most apart by a small lower order term if the exact drift is known. This reduces the analysis of expected optimization time to finding an exact expression for the drift. We then give an exact closed-form expression for the drift and develop a method to approximate it very efficiently, enabling us to determine approximate optimal mutation rates for the (1+\(\lambda \)) EA for various parameter settings of c and \(\lambda \) and also for moderate sizes of n. This makes the need for potentially lengthy and costly experiments in order to optimize c for fixed n and \(\lambda \) for the optimization of OneMax unnecessary. Interestingly, even for moderate n and not too small \(\lambda \) it turns out that mutation rates up to 10% larger than the asymptotically optimal rate 1 / n minimize the expected runtime. However, in absolute terms the expected runtime does not change by much when replacing 1 / n with the optimal mutation rate.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

References

  1. Auger, A., Doerr, B. (ed.): Theory of Randomized Search Heuristics: Foundations and Recent Developments. World Scientific Publishing, (2011)

  2. Abramowitz, M., Stegun, I.A.: Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. National Bureau of Standards, Gaithersburg (1964)

    MATH  Google Scholar 

  3. Böttcher, S., Doerr, B., Neumann, F.: Optimal fixed and adaptive mutation rates for the leadingones problem. In Proceedings of Parallel Problem Solving from Nature (PPSN 2010), vol. 6238, pp. 1–10. Springer (2010)

  4. Badkobeh, G., Lehre, P.K., Sudholt, D.: Unbiased black-box complexity of parallel search. In: Parallel Problem Solving from Nature—PPSN XIII—13th International Conference, Ljubljana, Slovenia, September 13–17, 2014. Proceedings, pp. 892–901. (2014)

  5. Chicano, F., Sutton, A.M., Whitley, L.D., Alba, E.: Fitness probability distribution of bit-flip mutation. Evolut. Comput. 23(2), 217–248 (2015)

    Article  Google Scholar 

  6. Doerr, B., Doerr, C., Yang, J .: Optimal parameter choices via precise black-box analysis. In: Proceedings of the 2016 on Genetic and Evolutionary Computation Conference, Denver, CO, USA, July 20–24, 2016, pp. 1123–1130. (2016)

  7. Doerr, B., Fouz, M., Witt, C.: Sharp bounds by probability-generating functions and variable drift. In: Procedings of the Genetic and Evolutionary Computation Conference (GECCO 2011), pp. 2083–2090. ACM Press (2011)

  8. Doerr, B., Goldberg, L.A.: Adaptive drift analysis. Algorithmica 65(1), 224–250 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  9. Droste, S., Jansen, T., Wegener, I.: On the analysis of the (1+1) evolutionary algorithm. Theor. Comput. Sci. 276, 51–81 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  10. Doerr, B., Künnemann, M.: Royal road functions and the (1+\(\lambda \)) evolutionary algorithm: almost no speed-up from larger offspring populations. In: Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2013), pp. 424–431. IEEE Press, (2013)

  11. Doerr, B., Künnemann, M.: Optimizing linear functions with the (1+\(\lambda \)) evolutionary algorithm - different asymptotic runtimes for different instances. Theor. Comput. Sci. 561, 3–23 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  12. Gießen, C., Witt, C.: Population size versus mutation strength for the (1+\(\lambda \)) EA on OneMax. In: Proceedings of GECCO ’15, pp. 1439–1446. ACM Press, (2015)

  13. Gießen, C., Witt, C.: Optimal mutation rates for the (1+\(\lambda \)) EA on onemax. In: Proceedings of the 2016 on Genetic and Evolutionary Computation Conference, Denver, CO, USA, July 20–24, 2016, pp. 1147–1154, (2016)

  14. Hwang, H.-K., Panholzer, A., Rolin, N., Tsai, T.-H., Chen, W.-M.: Probabilistic analysis of the (1+1)-evolutionary algorithm. Evol. Comput. (2017). doi:10.1162/EVCO_a_00212

  15. Jansen, T.: Analyzing Evolutionary Algorithms—The Computer Science Perspective. Natural Computing Series. Springer, Berlin (2013)

    Book  MATH  Google Scholar 

  16. Jansen, T., De Jong, K.A., Wegener, I.: On the choice of the offspring population size in evolutionary algorithms. Evolut. Comput. 13(4), 413–440 (2005)

    Article  Google Scholar 

  17. Johannsen, D.: Random combinatorial structures and randomized search heuristics. Ph.D. thesis, Universität des Saarlandes, Germany, (2010)

  18. Lehre, P.K., Witt, C.: Concentrated hitting times of randomized search heuristics with variable drift. In: Proceedings of ISAAC ’14, Volume 8889 of Lecture Notes in Computer Science, pp. 686–697. Springer, 2014. Full technical report at http://arxiv.org/abs/1307.2559

  19. Mitavskiy, B., Rowe, J.E., Cannings, C.: Theoretical analysis of local search strategies to optimize network communication subject to preserving the total number of links. Int. J. Intell. Comput. Cybern. 2(2), 243–284 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  20. Neumann, F., Witt, C.: Bioinspired Computation in Combinatorial Optimization—Algorithms and Their Computational Complexity. Natural Computing Series. Springer, Berlin (2010)

    MATH  Google Scholar 

  21. Jonathan, E.: Rowe and Dirk Sudholt. The choice of the offspring population size in the (1, \(\lambda \)) evolutionary algorithm. Theoretical Computer Science, 545:20–38, 2014. Preliminary version in Proceedings of GECCO 2012

  22. Skellam, J.G.: The frequency distribution of the difference between two poisson variates belonging to different populations. J. R. Stat. Soc. 109(3), 296–296 (1946)

    Article  MathSciNet  MATH  Google Scholar 

  23. Teerapabolarn, K.: A bound on the poisson-binomial relative error. Stat. Methodol. 4(4), 407–415 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  24. Witt, C.: Tight bounds on the optimization time of a randomized search heuristic on linear functions. Comb Prob. Comput. 22(2):294–318, 2013. Preliminary version in Proceedings of STACS ’12

Download references

Acknowledgements

This work was supported by the Danish Council for Independent Research (DFF), Grant No. 4002-00542.

Author information

Authors and Affiliations

  1. DTU Compute, Technical University of Denmark, 2800 Kgs, Lyngby, Denmark

    Christian Gießen & Carsten Witt

Authors
  1. Christian Gießen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Carsten Witt
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Christian Gießen.

Additional information

A preliminary version of this paper was published at GECCO 2016 [13].

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Gießen, C., Witt, C. Optimal Mutation Rates for the (1+\(\lambda \)) EA on OneMax Through Asymptotically Tight Drift Analysis. Algorithmica 80, 1710–1731 (2018). https://doi.org/10.1007/s00453-017-0360-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-017-0360-y

Keywords

Search

Navigation