nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Better Runtime Guarantees via Stochastic Domination

verfasst von : Benjamin Doerr

Erschienen in: Evolutionary Computation in Combinatorial Optimization

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Apart from few exceptions, the mathematical runtime analysis of evolutionary algorithms is mostly concerned with expected runtimes. In this work, we argue that stochastic domination is a notion that should be used more frequently in this area. Stochastic domination allows to formulate much more informative performance guarantees than the expectation alone, it allows to decouple the algorithm analysis into the true algorithmic part of detecting a domination statement and probability theoretic part of deriving the desired probabilistic guarantees from this statement, and it allows simpler and more natural proofs.

As particular results, we prove a fitness level theorem which shows that the runtime is dominated by a sum of independent geometric random variables, we prove tail bounds for several classic problems, and we give a short and natural proof for Witt’s result that the runtime of any \((\mu ,p)\) mutation-based algorithm on any function with unique optimum is subdominated by the runtime of a variant of the \((1 + 1)\) EA on the OneMax function.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Nächstes Kapitel On the Fractal Nature of Local Optima Networks

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

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

Doerr, B., Jansen, T., Witt, C., Zarges, C.: A method to derive fixed budget results from expected optimisation times. In: Genetic and Evolutionary Computation Conference, GECCO 2013, pp. 1581–1588. ACM (2013)

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

Jansen, T., Zarges, C.: Performance analysis of randomised search heuristics operating with a fixed budget. Theoret. Comput. Sci. 545, 39–58 (2014)MathSciNetCrossRef

Borisovsky, P.A., Eremeev, A.V.: Comparing evolutionary algorithms to the (1+1)-EA. Theoret. Comput. Sci. 403, 33–41 (2008)MathSciNetCrossRef

Zhou, D., Luo, D., Lu, R., Han, Z.: The use of tail inequalities on the probable computational time of randomized search heuristics. Theoret. Comput. Sci. 436, 106–117 (2012)MathSciNetCrossRef

Witt, C.: Fitness levels with tail bounds for the analysis of randomized search heuristics. Inf. Process. Lett. 114, 38–41 (2014)MathSciNetCrossRef

Doerr, B., Doerr, C.: A tight runtime analysis of the (1+(\(\lambda \), \(\lambda \))) genetic algorithm on OneMax. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2015, pp. 1423–1430. ACM (2015)

10.

Müller, A., Stoyan, D.: Comparison Methods for Stochastic Models and Risks. Wiley, Hoboken (2002)MATH

11.

Doerr, B., Happ, E., Klein, C.: Crossover can provably be useful in evolutionary computation. Theoret. Comput. Sci. 425, 17–33 (2012)MathSciNetCrossRef

12.

Doerr, B.: Analyzing randomized search heuristics: tools from probability theory. In: Auger, A., Doerr, B. (eds.) Theory of Randomized Search Heuristics, pp. 1–20. World Scientific, Singapore (2011)MATH

13.

Wegener, I.: Theoretical aspects of evolutionary algorithms. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol. 2076, pp. 64–78. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-48224-5_6CrossRef

14.

Janson, S.: Tail bounds for sums of geometric and exponential variables. arXiv e-prints arXiv:1709.08157 (2017)

15.

Scheideler, C.: Probabilistic methods for coordination problems. University of Paderborn, Habilitation thesis (2000). http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.70.1319

16.

Doerr, B., Happ, E., Klein, C.: Tight analysis of the (1+1)-EA for the single source shortest path problem. Evol. Comput. 19, 673–691 (2011)CrossRef

17.

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

18.

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

19.

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

20.

Scharnow, J., Tinnefeld, K., Wegener, I.: The analysis of evolutionary algorithms on sorting and shortest paths problems. J. Math. Model. Algorithms 3, 349–366 (2004)MathSciNetCrossRef

21.

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

22.

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

23.

Oliveto, P.S., Lehre, P.K., Neumann, F.: Theoretical analysis of rank-based mutation - combining exploration and exploitation. In: Congress on Evolutionary Computation, CEC 2009, pp. 1455–1462. IEEE (2009)

24.

Badkobeh, G., Lehre, P.K., Sudholt, D.: Unbiased black-box complexity of parallel search. In: Bartz-Beielstein, T., Branke, J., Filipič, B., Smith, J. (eds.) PPSN 2014. LNCS, vol. 8672, pp. 892–901. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-10762-2_88CrossRef

25.

Doerr, B., Gießen, C., Witt, C., Yang, J.: The (1+\(\lambda \)) evolutionary algorithm with self-adjusting mutation rate. In: Genetic and Evolutionary Computation Conference, GECCO 2017. ACM (2017)

26.

Doerr, B., Doerr, C., Yang, J.: k-bit mutation with self-adjusting k outperforms standard bit mutation. In: Handl, J., Hart, E., Lewis, P.R., López-Ibáñez, M., Ochoa, G., Paechter, B. (eds.) PPSN 2016. LNCS, vol. 9921, pp. 824–834. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-45823-6_77CrossRef

27.

Doerr, B., Doerr, C., Yang, J.: Optimal parameter choices via precise black-box analysis. In: Genetic and Evolutionary Computation Conference, GECCO 2016, pp. 1123–1130. ACM (2016)

28.

Lissovoi, A., Oliveto, P.S., Warwicker, J.A.: On the runtime analysis of generalised selection hyper-heuristics for pseudo-boolean optimisation. In: Genetic and Evolutionary Computation Conference, GECCO 2017, pp. 849–856. ACM (2017)

29.

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

30.

Lehre, P.K., Witt, C.: Black-box search by unbiased variation. Algorithmica 64, 623–642 (2012)MathSciNetCrossRef

31.

de Perthuis de Laillevault, A., Doerr, B., Doerr, C.: Money for nothing: speeding up evolutionary algorithms through better initialization. In: Genetic and Evolutionary Computation Conference, GECCO 2015, pp. 815–822. ACM (2015)

32.

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

33.

Droste, S., Jansen, T., Wegener, I.: A natural and simple function which is hard for all evolutionary algorithms. In: IEEE International Conference on Industrial Electronics, Control, and Instrumentation, IECON 2000, pp. 2704–2709. IEEE (2000)

34.

Jansen, T., Wegener, I.: Evolutionary algorithms - how to cope with plateaus of constant fitness and when to reject strings of the same fitness. IEEE Trans. Evol. Comput. 5, 589–599 (2001)CrossRef

35.

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

36.

Oliveto, P.S., He, J., Yao, X.: Analysis of the (1+1)-EA for finding approximate solutions to vertex cover problems. IEEE Trans. Evol. Comput. 13, 1006–1029 (2009)CrossRef

37.

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

38.

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

39.

Neumann, F., Wegener, I.: Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. Theoret. Comput. Sci. 378, 32–40 (2007)MathSciNetCrossRef

Titel: Better Runtime Guarantees via Stochastic Domination
verfasst von: Benjamin Doerr
Verlag: Springer International Publishing
Buch: Evolutionary Computation in Combinatorial Optimization
Print ISBN: 978-3-319-77448-0

Electronic ISBN: 978-3-319-77449-7

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-77449-7_1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"