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

Runtime Analysis of the (1+1) EA on Weighted Sums of Transformed Linear Functions

  • Conference paper
  • First Online:
Parallel Problem Solving from Nature – PPSN XVII (PPSN 2022)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13399))

Included in the following conference series:

  • 835 Accesses

Abstract

Linear functions play a key role in the runtime analysis of evolutionary algorithms and studies have provided a wide range of new insights and techniques for analyzing evolutionary computation methods. Motivated by studies on separable functions and the optimization behaviour of evolutionary algorithms as well as objective functions from the area of chance constrained optimization, we study the class of objective functions that are weighted sums of two transformed linear functions. Our results show that the (1+1) EA, with a mutation rate depending on the number of overlapping bits of the functions, obtains an optimal solution for these functions in expected time \(O(n \log n)\), thereby generalizing a well-known result for linear functions to a much wider range of problems.

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

Access this chapter

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

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 109.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 139.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Assimi, H., Harper, O., Xie, Y., Neumann, A., Neumann, F.: Evolutionary bi-objective optimization for the dynamic chance-constrained knapsack problem based on tail bound objectives. In: ECAI, vol. 325, pp. 307–314. IOS Press (2020)

    Google Scholar 

  2. Charnes, A., Cooper, W.W.: Chance-constrained programming. Manage. Sci. 6(1), 73–79 (1959)

    Article  MathSciNet  Google Scholar 

  3. Doerr, B.: Probabilistic tools for the analysis of randomized optimization heuristics. In: Theory of Evolutionary Computation. NCS, pp. 1–87. Springer, Cham (2020)

    Chapter  Google Scholar 

  4. Doerr, B., Doerr, C.: The impact of random initialization on the runtime of randomized search heuristics. Algorithmica 75(3), 529–553 (2016)

    Article  MathSciNet  Google Scholar 

  5. Doerr, B., Doerr, C., Neumann, A., Neumann, F., Sutton, A.M.: Optimization of chance-constrained submodular functions. In: AAAI, pp. 1460–1467. AAAI Press (2020)

    Google Scholar 

  6. Doerr, B., Goldberg, L.A.: Adaptive drift analysis. In: Schaefer, R., Cotta, C., Kołodziej, J., Rudolph, G. (eds.) PPSN 2010. LNCS, vol. 6238, pp. 32–41. Springer, Heidelberg (2010)

    Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  8. Doerr, B., Jansen, T., Sudholt, D., Winzen, C., Zarges, C.: Mutation rate matters even when optimizing monotonic functions. Evol. Comput. 21(1), 1–27 (2013)

    Article  Google Scholar 

  9. Doerr, B., Johannsen, D., Winzen, C.: Drift analysis and linear functions revisited. In: Proceedings of CEC 2010, pp. 1–8. IEEE Press (2010)

    Google Scholar 

  10. Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. In: Proceedings of GECCO 2010, pp. 1449–1456. ACM Press (2010)

    Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  12. Doerr, B., Neumann, F. (eds.): Theory of Evolutionary Computation-Recent Developments in Discrete Optimization. Springer, Cham (2020)

    Google Scholar 

  13. Doerr, B., Sudholt, D., Witt, C.: When do evolutionary algorithms optimize separable functions in parallel? In: FOGA, pp. 51–64. ACM (2013)

    Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  15. Hajek, B.: Hitting-time and occupation-time bounds implied by drift analysis with applications. Adv. Appl. Probab. 13(3), 502–525 (1982)

    Article  MathSciNet  Google Scholar 

  16. He, J., Yao, X.: A study of drift analysis for estimating computation time of evolutionary algorithms. Nat. Comput. 3(1), 21–35 (2004)

    Article  MathSciNet  Google Scholar 

  17. Ishii, H., Shiode, S., Nishida, T., Namasuya, Y.: Stochastic spanning tree problem. Discret. Appl. Math. 3(4), 263–273 (1981)

    Article  MathSciNet  Google Scholar 

  18. Jägersküpper, J.: A blend of Markov-chain and drift analysis. In: Rudolph, G., Jansen, T., Beume, N., Lucas, S., Poloni, C. (eds.) PPSN 2008. LNCS, vol. 5199, pp. 41–51. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  19. Jägersküpper, J.: Combining Markov-chain analysis and drift analysis. Algorithmica 59(3), 409–424 (2011)

    Article  MathSciNet  Google Scholar 

  20. Jansen, T.: Analyzing Evolutionary Algorithms - The Computer Science Perspective. Springer, Cham (2013)

    Google Scholar 

  21. Lehre, P.K., Witt, C.: Tail bounds on hitting times of randomized search heuristics using variable drift analysis. Combinatorics Probab. Comput. 30(4), 550–569 (2021)

    Article  MathSciNet  Google Scholar 

  22. Lengler, J., Martinsson, A., Steger, A.: When does hillclimbing fail on monotone functions: an entropy compression argument. In: ANALCO, pp. 94–102. SIAM (2019)

    Google Scholar 

  23. Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)

    Google Scholar 

  24. Neumann, A., Neumann, F.: Optimising monotone chance-constrained submodular functions using evolutionary multi-objective algorithms. In: Bäck, T., et al. (eds.) PPSN 2020. LNCS, vol. 12269, pp. 404–417. Springer, Cham (2020)

    Chapter  Google Scholar 

  25. Neumann, F., Pourhassan, M., Witt, C.: Improved runtime results for simple randomised search heuristics on linear functions with a uniform constraint. Algorithmica 83(10), 3209–3237 (2021)

    Article  MathSciNet  Google Scholar 

  26. Neumann, F., Sutton, A.M.: Runtime analysis of the (1+1) evolutionary algorithm for the chance-constrained knapsack problem. In: FOGA, pp. 147–153. ACM (2019)

    Google Scholar 

  27. Neumann, F., Witt, C.: Bioinspired Computation in Combinatorial Optimization - Algorithms and Their Computational Complexity. Springer, Cham (2010)

    Google Scholar 

  28. Witt, C.: Tight bounds on the optimization time of a randomized search heuristic on linear functions. Combinatorics Probab. Comput. 22(2), 294–318 (2013)

    Article  MathSciNet  Google Scholar 

  29. Xie, Y., Harper, O., Assimi, H., Neumann, A., Neumann, F.: Evolutionary algorithms for the chance-constrained knapsack problem. In: GECCO, pp. 338–346. ACM (2019)

    Google Scholar 

  30. Xie, Y., Neumann, A., Neumann, F.: Specific single- and multi-objective evolutionary algorithms for the chance-constrained knapsack problem. In: GECCO, pp. 271–279. ACM (2020)

    Google Scholar 

  31. Xie, Y., Neumann, A., Neumann, F.: Heuristic strategies for solving complex interacting stockpile blending problem with chance constraints. In: GECCO, pp. 1079–1087. ACM (2021)

    Google Scholar 

  32. Xie, Y., Neumann, A., Neumann, F., Sutton, A.M.: Runtime analysis of RLS and the (1+1) EA for the chance-constrained knapsack problem with correlated uniform weights. In: GECCO, pp. 1187–1194. ACM (2021)

    Google Scholar 

Download references

Acknowledgments

This work has been supported by the Australian Research Council (ARC) through grant FT200100536 and by the Independent Research Fund Denmark through grant DFF-FNU 8021-00260B.

Author information

Authors and Affiliations

  1. Optimisation and Logistics, School of Computer Science, The University of Adelaide, Adelaide, Australia

    Frank Neumann

  2. DTU Compute, Technical University of Denmark, Kongens Lyngby, Denmark

    Carsten Witt

Authors
  1. Frank Neumann
    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 Frank Neumann .

Editor information

Editors and Affiliations

  1. TU Dortmund, Dortmund, Germany

    Günter Rudolph

  2. Leiden University, Leiden, The Netherlands

    Anna V. Kononova

  3. Shinshu University, Nagano, Japan

    Hernán Aguirre

  4. Technische Universität Dresden, Dresden, Germany

    Pascal Kerschke

  5. University of Stirling, Stirling, UK

    Gabriela Ochoa

  6. Jožef Stefan Institute, Ljubljana, Slovenia

    Tea Tušar

Rights and permissions

Reprints and permissions

Copyright information

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Neumann, F., Witt, C. (2022). Runtime Analysis of the (1+1) EA on Weighted Sums of Transformed Linear Functions. In: Rudolph, G., Kononova, A.V., Aguirre, H., Kerschke, P., Ochoa, G., Tušar, T. (eds) Parallel Problem Solving from Nature – PPSN XVII. PPSN 2022. Lecture Notes in Computer Science, vol 13399. Springer, Cham. https://doi.org/10.1007/978-3-031-14721-0_38

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-14721-0_38

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-14720-3

  • Online ISBN: 978-3-031-14721-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation