nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Precise Runtime Analysis for Plateaus

verfasst von : Denis Antipov, Benjamin Doerr

Erschienen in: Parallel Problem Solving from Nature – PPSN XV

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

To gain a better theoretical understanding of how evolutionary algorithms cope with plateaus of constant fitness, we analyze how the $(1 + 1)$ EA optimizes the n-dimensional $\textsc {Plateau} _k$ function. This function has a plateau of second-best fitness in a radius of k around the optimum. As optimization algorithm, we regard the $(1 + 1)$ EA using an arbitrary unbiased mutation operator. Denoting by $\alpha $ the random number of bits flipped in an application of this operator and assuming $\Pr [\alpha = 1] = \varOmega (1)$, we show the surprising result that for $k \ge 2$ the expected optimization time of this algorithm is

$$ \frac{n^k}{k!\Pr [1 \le \alpha \le k]}(1 + o(1)), $$

that is, the size of the plateau times the expected waiting time for an iteration flipping between 1 and k bits. Our result implies that the optimal mutation rate for this function is approximately k/en. Our main analysis tool is a combined analysis of the Markov chains on the search point space and on the Hamming level space, an approach that promises to be useful also for other plateau problems.

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

Vorheriges Kapitel Level-Based Analysis of the Population-Based Incremental Learning Algorithm

Nächstes Kapitel Ring Migration Topology Helps Bypassing Local Optima

As common in optimization, we reserve the notion unimodal for objective functions such that each non-optimal search point has a strictly better neighbor.

In the usual asymptotic sense, that is, meaning all but a lower order fraction.

We call a mutation rate optimal when it differs from the truly optimal rate at most by lower order terms, that is, e.g. a factor of $(1 \pm o(1))$.

For reasons of space, not all mathematical proofs could fit into this extended abstract. The proofs can be found in [1].

Antipov, D., Doerr, B.: Precise runtime analysis for plateaus (2018). http://arxiv.org/abs/1806.01331

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

Brockhoff, D., Friedrich, T., Hebbinghaus, N., Klein, C., Neumann, F., Zitzler, E.: On the effects of adding objectives to plateau functions. IEEE Trans. Evol. Comput. 13(3), 591–603 (2009)CrossRef

Buzdalov, M., Doerr, B., Kever, M.: The unrestricted black-box complexity of jump functions. Evol. Comput. 24(4), 719–744 (2016)CrossRef

Dang, D.-C., et al.: Emergence of diversity and its benefits for crossover in genetic algorithms. In: Handl, J., Hart, E., Lewis, P.R., López-Ibáñez, M., Ochoa, G., Paechter, B. (eds.) PPSN 2016. LNCS, vol. 9921, pp. 890–900. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-45823-6_83CrossRef

Dang, D.C., et al.: Escaping local optima with diversity mechanisms and crossover. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2016, pp. 645–652. ACM (2016)

Dang, D., Lehre, P.K.: Runtime analysis of non-elitist populations: from classical optimisation to partial information. Algorithmica 75(3), 428–461 (2016)MathSciNetCrossRef

Doerr, B., Doerr, C., Kötzing, T.: Unbiased black-box complexities of jump functions. Evol. Comput. 23(4), 641–670 (2015)CrossRef

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 (2011)

10.

Doerr, B., Hebbinghaus, N., Neumann, F.: Speeding up evolutionary algorithms through asymmetric mutation operators. Evol. Comput. 15, 401–410 (2007)CrossRef

11.

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)CrossRef

12.

Doerr, B., Jansen, T., Klein, C.: Comparing global and local mutations on bit strings. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2008, pp. 929–936. ACM (2008)

13.

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

14.

Doerr, B., Le, H.P., Makhmara, R., Nguyen, T.D.: Fast genetic algorithms. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2017, pp. 777–784. ACM (2017). http://arxiv.org/abs/1703.03334

15.

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

16.

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

17.

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

18.

Jansen, T., Wegener, I.: The analysis of evolutionary algorithms–a proof that crossover really can help. Algorithmica 34(1), 47–66 (2002)MathSciNetCrossRef

19.

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

20.

Lehre, P.K., Witt, C.: Concentrated hitting times of randomized search heuristics with variable drift. In: Ahn, H.-K., Shin, C.-S. (eds.) ISAAC 2014. LNCS, vol. 8889, pp. 686–697. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-13075-0_54CrossRef

21.

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

22.

Meyer, C.D. (ed.): Matrix Analysis and Applied Linear Algebra. Society for Industrial and Applied Mathematics, Philadelphia (2000)

23.

Mironovich, V., Buzdalov, M.: Hard test generation for maximum flow algorithms with the fast crossover-based evolutionary algorithm. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO 2015, pp. 1229–1232. ACM (2015)

24.

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

25.

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

26.

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

Titel: Precise Runtime Analysis for Plateaus
verfasst von: Denis Antipov
Benjamin Doerr
Verlag: Springer International Publishing
Buch: Parallel Problem Solving from Nature – PPSN XV
Print ISBN: 978-3-319-99258-7

Electronic ISBN: 978-3-319-99259-4

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-99259-4_10

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"