Top

Published in:

2020 | OriginalPaper | Chapter

Exponential Upper Bounds for the Runtime of Randomized Search Heuristics

Author : Benjamin Doerr

Published in: Parallel Problem Solving from Nature – PPSN XVI

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We argue that proven exponential upper bounds on runtimes, an established area in classic algorithms, are interesting also in evolutionary computation and we prove several such results. We show that any of the algorithms randomized local search, Metropolis algorithm, simulated annealing, and \((1+1)\) evolutionary algorithm can optimize any pseudo-Boolean weakly monotonic function under a large set of noise assumptions in a runtime that is at most exponential in the problem dimension n. This drastically extends a previous such result, limited to the \((1+1)\) EA, the LeadingOnes function, and one-bit or bit-wise prior noise with noise probability at most 1/2, and at the same time simplifies its proof. With the same general argument, among others, we also derive a sub-exponential upper bound for the runtime of the \((1,\lambda )\) evolutionary algorithm on the OneMax problem when the offspring population size \(\lambda \) is logarithmic, but below the efficiency threshold.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Lower Bounds for Non-elitist Evolutionary Algorithms via Negative Multiplicative Drift

next chapter Analysis on the Efficiency of Multifactorial Evolutionary Algorithms

See Section 2 for details on all technical terms used in this introduction.

As common both in classic algorithms and in our field, by runtime we mean the worst-case runtime taken over all input instances.

Akimoto, Y., Morales, S.A., Teytaud, O.: Analysis of runtime of optimization algorithms for noisy functions over discrete codomains. Theor. Comput. Sci. 605, 42–50 (2015)MathSciNetCrossRef

Antipov, D., Doerr, B.: Precise runtime analysis for plateaus. In: Auger, A., Fonseca, C.M., Lourenço, N., Machado, P., Paquete, L., Whitley, D. (eds.) PPSN 2018. LNCS, vol. 11102, pp. 117–128. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-99259-4_10CrossRef

Auger, A., Doerr, B. (eds.): Theory of Randomized Search Heuristics. World Scientific Publishing (2011)

Bian, C., Qian, C., Tang, K.: Towards a running time analysis of the \((1+1)\)-EA for OneMax and LeadingOnes under general bit-wise noise. In: Auger, A., Fonseca, C.M., Lourenço, N., Machado, P., Paquete, L., Whitley, D. (eds.) PPSN 2018. LNCS, vol. 11102, pp. 165–177. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-99259-4_14CrossRef

Bianchi, L., Dorigo, M., Gambardella, L.M., Gutjahr, W.J.: A survey on metaheuristics for stochastic combinatorial optimization. Nat. Comput. 8, 239–287 (2009). https://doi.org/10.1007/s11047-008-9098-4MathSciNetCrossRefMATH

Böttcher, S., Doerr, B., Neumann, F.: Optimal fixed and adaptive mutation rates for the LeadingOnes problem. In: Schaefer, R., Cotta, C., Kołodziej, J., Rudolph, G. (eds.) PPSN 2010. LNCS, vol. 6238, pp. 1–10. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15844-5_1CrossRef

Colin, S., Doerr, B., Férey, G.: Monotonic functions in EC: anything but monotone! In: Genetic and Evolutionary Computation Conference, GECCO 2014, pp. 753–760. ACM (2014)

Dang, D., Lehre, P.K.: Simplified runtime analysis of estimation of distribution algorithms. In: Genetic and Evolutionary Computation Conference, GECCO 2015, pp. 513–518. ACM (2015)

Dang-Nhu, R., Dardinier, T., Doerr, B., Izacard, G., Nogneng, D.: A new analysis method for evolutionary optimization of dynamic and noisy objective functions. In: Genetic and Evolutionary Computation Conference, GECCO 2018, pp. 1467–1474. ACM (2018)

10.

Doerr, B.: Exponential upper bounds for the runtime of randomized search heuristics. CoRR abs/2004.05733 (2020)

11.

Doerr, B., Doerr, C., Ebel, F.: From black-box complexity to designing new genetic algorithms. Theor. Comput. Sci. 567, 87–104 (2015)MathSciNetCrossRef

12.

Doerr, B., Goldberg, L.A.: Adaptive drift analysis. Algorithmica 65, 224–250 (2013). https://doi.org/10.1007/s00453-011-9585-3MathSciNetCrossRefMATH

13.

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

14.

Doerr, B., Le, H.P., Makhmara, R., Nguyen, T.D.: Fast genetic algorithms. In: Genetic and Evolutionary Computation Conference, GECCO 2017, pp. 777–784. ACM (2017)

15.

Doerr, B., Neumann, F. (eds.): Theory of Evolutionary Computation-Recent Developments in Discrete Optimization. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-29414-4CrossRefMATH

16.

Doerr, B., Sutton, A.M.: When resampling to cope with noise, use median, not mean. In: Genetic and Evolutionary Computation Conference, GECCO 2019, pp. 242–248. ACM (2019)

17.

Droste, S.: Analysis of the (1 + 1) EA for a noisy OneMax. In: Deb, K. (ed.) GECCO 2004. LNCS, vol. 3102, pp. 1088–1099. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24854-5_107CrossRef

18.

Droste, S., Jansen, T., Wegener, I.: On the optimization of unimodal functions with the \((1+1)\) evolutionary algorithm. In: Eiben, A.E., Bäck, T., Schoenauer, M., Schwefel, H.-P. (eds.) PPSN 1998. LNCS, vol. 1498, pp. 13–22. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0056845CrossRef

19.

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

20.

Fomin, F.V., Kaski, P.: Exact exponential algorithms. Commun. ACM 56, 80–88 (2013)CrossRef

21.

Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. TTCSAES. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-16533-7CrossRefMATH

22.

Friedrich, T., Kötzing, T., Krejca, M.S., Sutton, A.M.: Robustness of ant colony optimization to noise. In: Genetic and Evolutionary Computation Conference, GECCO 2015, pp. 17–24. ACM (2015)

23.

Friedrich, T., Kötzing, T., Krejca, M.S., Sutton, A.M.: The compact genetic algorithm is efficient under extreme Gaussian noise. IEEE Trans. Evol. Comput. 21, 477–490 (2017)

24.

Garnier, J., Kallel, L., Schoenauer, M.: Rigorous hitting times for binary mutations. Evol. Comput. 7, 173–203 (1999)CrossRef

25.

Gießen, C., Kötzing, T.: Robustness of populations in stochastic environments. Algorithmica 75, 462–489 (2016). https://doi.org/10.1007/s00453-015-0072-0MathSciNetCrossRefMATH

26.

Happ, E., Johannsen, D., Klein, C., Neumann, F.: Rigorous analyses of fitness-proportional selection for optimizing linear functions. In: Genetic and Evolutionary Computation Conference, GECCO 2008, pp. 953–960. ACM (2008)

27.

He, J., Yao, X.: Drift analysis and average time complexity of evolutionary algorithms. Artif. Intell. 127, 51–81 (2001)MathSciNetCrossRef

28.

Jansen, T.: On the brittleness of evolutionary algorithms. In: Stephens, C.R., Toussaint, M., Whitley, D., Stadler, P.F. (eds.) FOGA 2007. LNCS, vol. 4436, pp. 54–69. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-73482-6_4CrossRefMATH

29.

Jansen, T.: Analyzing Evolutionary Algorithms. The Computer Science Perspective. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-17339-4CrossRefMATH

30.

Jansen, T., Wegener, I.: On the analysis of a dynamic evolutionary algorithm. J. Discrete Algorithms 4, 181–199 (2006)MathSciNetCrossRef

31.

Jin, Y., Branke, J.: Evolutionary optimization in uncertain environments - a survey. IEEE Trans. Evol. Comput. 9, 303–317 (2005)CrossRef

32.

Lehre, P.K.: Negative drift in populations. In: Schaefer, R., Cotta, C., Kołodziej, J., Rudolph, G. (eds.) PPSN 2010. LNCS, vol. 6238, pp. 244–253. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15844-5_25CrossRef

33.

Lengler, J.: A general dichotomy of evolutionary algorithms on monotone functions. In: Auger, A., Fonseca, C.M., Lourenço, N., Machado, P., Paquete, L., Whitley, D. (eds.) PPSN 2018. LNCS, vol. 11102, pp. 3–15. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-99259-4_1CrossRef

34.

Lengler, J.: Drift analysis. Theory of Evolutionary Computation. NCS, pp. 89–131. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-29414-4_2CrossRef

35.

Mühlenbein, H.: How genetic algorithms really work: mutation and hill climbing. In: Parallel problem solving from nature, PPSN 1992, pp. 15–26. Elsevier (1992)

36.

Neumann, F., Pourhassan, M., Roostapour, V.: Analysis of evolutionary algorithms in dynamic and stochastic environments. Theory of Evolutionary Computation. NCS, pp. 323–357. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-29414-4_7 CrossRefMATH

37.

Neumann, F., Sutton, A.M.: Parameterized complexity analysis of randomized search heuristics. Theory of Evolutionary Computation. NCS, pp. 213–248. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-29414-4_4CrossRef

38.

Neumann, F., Witt, C.: Bioinspired Computation in Combinatorial Optimization -Algorithms and Their Computational Complexity. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-16544-3CrossRefMATH

39.

Oliveto, P.S., Witt, C.: Improved time complexity analysis of the simple genetic algorithm. Theoret. Comput. Sci. 605, 21–41 (2015)MathSciNetCrossRef

40.

Paixão, T., Heredia, J.P., Sudholt, D., Trubenová, B.: Towards a runtime comparison of natural and artificial evolution. Algorithmica 78, 681–713 (2017)MathSciNetCrossRef

41.

Qian, C., Bian, C., Jiang, W., Tang, K.: Running time analysis of the \({(1+1)}\)-EA for OneMax and LeadingOnes under bit-wise noise. Algorithmica 81, 749–795 (2019)MathSciNetCrossRef

42.

Qian, C., Yu, Y., Zhou, Z.: Analyzing evolutionary optimization in noisy environments. Evol. Comput. 26, 1–41 (2018)CrossRef

43.

Rowe, J.E., Sudholt, D.: The choice of the offspring population size in the (1, \(\lambda \)) evolutionary algorithm. Theoret. Comput. Sci. 545, 20–38 (2014)MathSciNetCrossRef

44.

Sudholt, D.: A new method for lower bounds on the running time of evolutionary algorithms. IEEE Trans. Evol. Comput. 17, 418–435 (2013)CrossRef

45.

Sudholt, D.: Analysing the robustness of evolutionary algorithms to noise:refined runtime bounds and an example where noise is beneficial. Algorithmica (2020, to appear). https://doi.org/10.1007/s00453-020-00671-0

46.

Sudholt, D., Thyssen, C.: A simple ant colony optimizer for stochastic shortest path problems. Algorithmica 64, 643–672 (2012). https://doi.org/10.1007/s00453-011-9606-2MathSciNetCrossRefMATH

47.

Wegener, I., Witt, C.: On the optimization of monotone polynomials by simple randomized search heuristics. Comb. Probab. Comput. 14, 225–247 (2005)MathSciNetCrossRef

48.

Witt, C.: Worst-case and average-case approximations by simple randomized search heuristics. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol. 3404, pp. 44–56. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-31856-9_4CrossRef

49.

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

50.

Xiao, M., Nagamochi, H.: Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs. Theoret. Comput. Sci. 469, 92–104 (2013)MathSciNetCrossRef

Title: Exponential Upper Bounds for the Runtime of Randomized Search Heuristics
Author: Benjamin Doerr
Publisher: Springer International Publishing
Book: Parallel Problem Solving from Nature – PPSN XVI
Print ISBN: 978-3-030-58114-5

Electronic ISBN: 978-3-030-58115-2

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-58115-2_43

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner