[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

The Interplay of Population Size and Mutation Probability in the (\(1+\lambda \)) EA on OneMax

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

The (\(1+\lambda \)) EA with mutation probability c / n, where \(c>0\) is an arbitrary constant, is studied for the classical OneMax function. Its expected optimization time is analyzed exactly (up to lower order terms) as a function of c and \(\lambda \). It turns out that 1 / n is the only optimal mutation probability if \(\lambda =o(\ln n\ln \ln n/\ln \ln \ln n)\), which is the cut-off point for linear speed-up. However, if \(\lambda \) is above this cut-off point then the standard mutation probability 1 / n is no longer the only optimal choice. Instead, the expected number of generations is (up to lower order terms) independent of c, irrespectively of it being less than 1 or greater. The theoretical results are obtained by a careful study of order statistics of the binomial distribution and variable drift theorems for upper and lower bounds. Experimental supplements shed light on the optimal mutation probability for small problem sizes.

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
£29.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 includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

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

    MATH  Google Scholar 

  2. 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)

  3. Badkobeh, G., Lehre, P.K., Sudholt, D.: Unbiased black-box complexity of parallel search. In: Proceedings of Parallel Problem Solving from Nature (PPSN 2014), vol. 8672 of Lecture Notes in Computer Science, pp. 892–901 (2014)

  4. 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 

  5. Doerr, B., Fouz, M., Witt, C.: Quasirandom evolutionary algorithms. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2010), pp. 1457–1464. ACM Press (2010)

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

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

    Article  MathSciNet  MATH  Google Scholar 

  8. Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. Algorithmica 64(4), 673–697 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  9. 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)

  10. 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 

  11. Gießen, C., Witt, C.: Population size vs. mutation strength for the (\(1+\lambda \)) EA on OneMax. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO 2015), pp. 1439–1446. ACM Press (2015)

  12. Jägersküpper, J.: Combining Markov-chain analysis and drift analysis—the (1 \(+\) 1) evolutionary algorithm on linear functions reloaded. Algorithmica 59(3), 409–424 (2011). (Preliminary version in Proc. of PPSN’08)

    Article  MathSciNet  MATH  Google Scholar 

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

    MATH  Google Scholar 

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

    Article  Google Scholar 

  15. Johannsen, D.: Random Combinatorial Structures and Randomized Search Heuristics. PhD thesis, Universität des Saarlandes, Germany (2010)

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

  17. 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 

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

    MATH  Google Scholar 

  19. Rowe, J.E., Sudholt, D.: The choice of the offspring population size in the (1, \(\lambda \)) evolutionary algorithm. Theor. Comput. Sci. 545, 20–38 (2014). (Preliminary version in Proc. of GECCO 2012)

  20. Sudholt, D.: Crossover speeds up building-block assembly. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2012), pp. 689–702. ACM Press (2012)

  21. Sudholt, D.: A new method for lower bounds on the running time of evolutionary algorithms. IEEE Trans. Evol. Comput. 17(3), 418–435 (2013). (Preliminary version in Proc. of PPSN’10)

    Article  Google Scholar 

  22. Witt, C.: Runtime analysis of the (\(\mu + 1\)) EA on simple pseudo-Boolean functions. Evol. Comput. 14(1), 65–86 (2006)

    Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

This work was supported by the Danish Council for Independent Research (DFF), Grant No. 4002-00542. The authors thank the anonymous reviewers for their useful comments which helped to improve this work.

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 2015 [11].

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. The Interplay of Population Size and Mutation Probability in the (\(1+\lambda \)) EA on OneMax. Algorithmica 78, 587–609 (2017). https://doi.org/10.1007/s00453-016-0214-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-016-0214-z

Keywords

Search

Navigation