Skip to main content

2020 | OriginalPaper | Buchkapitel

On Non-elitist Evolutionary Algorithms Optimizing Fitness Functions with a Plateau

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

search-config
loading …

Abstract

We consider the expected runtime of non-elitist evolutionary algorithms (EAs), when they are applied to a family of fitness functions \(\text {Plateau} _r\) with a plateau of second-best fitness in a Hamming ball of radius r around a unique global optimum. On one hand, using the level-based theorems, we obtain polynomial upper bounds on the expected runtime for some modes of non-elitist EA based on unbiased mutation and the bitwise mutation in particular. On the other hand, we show that the EA with fitness proportionate selection is inefficient if the bitwise mutation is used with the standard settings of mutation probability.

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!

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!

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!

Anhänge
Nur mit Berechtigung zugänglich
Literatur
2.
Zurück zum Zitat Corus, D., Dang, D., Eremeev, A.V., Lehre, P.K.: Level-based analysis of genetic algorithms and other search processes. IEEE Trans. Evol. Comput. 22(5), 707–719 (2018)CrossRef Corus, D., Dang, D., Eremeev, A.V., Lehre, P.K.: Level-based analysis of genetic algorithms and other search processes. IEEE Trans. Evol. Comput. 22(5), 707–719 (2018)CrossRef
3.
Zurück zum Zitat Dang, D.C., Eremeev, A., Lehre, P.K.: Runtime analysis of fitness-proportionate selection on linear functions. ArXiv 1908.08686 [cs.NE] (2019) Dang, D.C., Eremeev, A., Lehre, P.K.: Runtime analysis of fitness-proportionate selection on linear functions. ArXiv 1908.08686 [cs.NE] (2019)
4.
Zurück zum Zitat Dang, D.C., Lehre, P.K.: Runtime analysis of non-elitist populations: from classical optimisation to partial information. Algorithmica 75(3), 428–461 (2016)MathSciNetCrossRef Dang, D.C., Lehre, P.K.: Runtime analysis of non-elitist populations: from classical optimisation to partial information. Algorithmica 75(3), 428–461 (2016)MathSciNetCrossRef
5.
Zurück zum Zitat Dang, D.C., Lehre, P.K.: Self-adaptation of mutation rates in non-elitist populations. In: Proceedings of PPSN 2016, pp. 803–813 (2016) Dang, D.C., Lehre, P.K.: Self-adaptation of mutation rates in non-elitist populations. In: Proceedings of PPSN 2016, pp. 803–813 (2016)
6.
Zurück zum Zitat Doerr, B., Johannsen, D., Kötzing, T., Lehre, P.K., Wagner, M., Winzen, C.: Faster black-box algorithms through higher arity operators. In: Proceedings FOGA 2011, pp. 163–172 (2011) Doerr, B., Johannsen, D., Kötzing, T., Lehre, P.K., Wagner, M., Winzen, C.: Faster black-box algorithms through higher arity operators. In: Proceedings FOGA 2011, pp. 163–172 (2011)
7.
Zurück zum Zitat Doerr, B., Kötzing, T.: Multiplicative up-drift. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2019, Prague, Czech Republic, 13–17 July 2019, pp. 1470–1478 (2019) Doerr, B., Kötzing, T.: Multiplicative up-drift. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2019, Prague, Czech Republic, 13–17 July 2019, pp. 1470–1478 (2019)
8.
Zurück zum Zitat Droste, S., Jansen, T., Tinnefeld, K., Wegener, I.: A new framework for the valuation of algorithms for black-box optimization. In: FOGA-7, pp. 253–270. Morgan Kaufmann, San Francisco (2003) Droste, S., Jansen, T., Tinnefeld, K., Wegener, I.: A new framework for the valuation of algorithms for black-box optimization. In: FOGA-7, pp. 253–270. Morgan Kaufmann, San Francisco (2003)
9.
Zurück zum Zitat Eremeev, A.: Hitting times of local and global optima in genetic algorithms with very high selection pressure. Yugosl. J. Oper. Res. 27(3), 323–339 (2017)MathSciNetCrossRef Eremeev, A.: Hitting times of local and global optima in genetic algorithms with very high selection pressure. Yugosl. J. Oper. Res. 27(3), 323–339 (2017)MathSciNetCrossRef
10.
Zurück zum Zitat Gnedenko, B.V.: Theory of Probability. Gordon and Breach, London (1997)MATH Gnedenko, B.V.: Theory of Probability. Gordon and Breach, London (1997)MATH
11.
Zurück zum Zitat Hampson, S., Kibler, D.: Plateaus and plateau search in Boolean satisfiability problems: when to give up searching and start again. In: Proceedings of the second DIMACS Implementation Challenge "Cliques, Coloring and Satisfiability, pp. 437–456. American Mathematical Society (1996) Hampson, S., Kibler, D.: Plateaus and plateau search in Boolean satisfiability problems: when to give up searching and start again. In: Proceedings of the second DIMACS Implementation Challenge "Cliques, Coloring and Satisfiability, pp. 437–456. American Mathematical Society (1996)
12.
Zurück zum Zitat Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58(301), 13–30 (1963)MathSciNetCrossRef Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58(301), 13–30 (1963)MathSciNetCrossRef
13.
Zurück zum Zitat Jansen, T., Wegener, I.: On the utility of populations in evolutionary algorithms. In: Proceedings of GECCO 2001, pp. 1034–1041 (2001) Jansen, T., Wegener, I.: On the utility of populations in evolutionary algorithms. In: Proceedings of GECCO 2001, pp. 1034–1041 (2001)
14.
Zurück zum Zitat Lehre, P.K.: Negative drift in populations. In: Proceedings of PPSN 2010, pp. 244–253 (2010) Lehre, P.K.: Negative drift in populations. In: Proceedings of PPSN 2010, pp. 244–253 (2010)
15.
Zurück zum Zitat Lehre, P.K.: Fitness-levels for non-elitist populations. In: Proceedings of GECCO 2011, pp. 2075–2082 (2011) Lehre, P.K.: Fitness-levels for non-elitist populations. In: Proceedings of GECCO 2011, pp. 2075–2082 (2011)
16.
Zurück zum Zitat Lehre, P.K., Özcan, E.: A runtime analysis of simple hyper-heuristics: to mix or not to mix operators. In: Proceedings of FOGA 2013, pp. 97–104 (2013) Lehre, P.K., Özcan, E.: A runtime analysis of simple hyper-heuristics: to mix or not to mix operators. In: Proceedings of FOGA 2013, pp. 97–104 (2013)
18.
Zurück zum Zitat van Nimwegen, E., Crutchfield, J.: Optimizing epochal evolutionary search population-size independent theory. Comput. Meth. Appl. Mech. Eng. 186(2—-4), 171–194 (2000)CrossRef van Nimwegen, E., Crutchfield, J.: Optimizing epochal evolutionary search population-size independent theory. Comput. Meth. Appl. Mech. Eng. 186(2—-4), 171–194 (2000)CrossRef
19.
Zurück zum Zitat Sutton, A.M., Howe, A.E., Whitley, L.D.: Directed plateau search for max-k-sat. In: Proceedings of the Third Annual Symposium on Combinatorial Search, SOCS 2010, Stone Mountain, Atlanta, Georgia, USA, 8–10 July 2010 (2010) Sutton, A.M., Howe, A.E., Whitley, L.D.: Directed plateau search for max-k-sat. In: Proceedings of the Third Annual Symposium on Combinatorial Search, SOCS 2010, Stone Mountain, Atlanta, Georgia, USA, 8–10 July 2010 (2010)
20.
Zurück zum Zitat Witt, C.: Population size versus runtime of a simple evolutionary algorithm. Theor. Comput. Sci. 403(1), 104–120 (2008)MathSciNetCrossRef Witt, C.: Population size versus runtime of a simple evolutionary algorithm. Theor. Comput. Sci. 403(1), 104–120 (2008)MathSciNetCrossRef
Metadaten
Titel
On Non-elitist Evolutionary Algorithms Optimizing Fitness Functions with a Plateau
verfasst von
Anton V. Eremeev
Copyright-Jahr
2020
DOI
https://doi.org/10.1007/978-3-030-49988-4_23