Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Kongresse
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Veranstaltungskalender Awards MyNewsletter Firmensuche
Kunden Login
Über Einzelzugang informieren
Über Unternehmenszugang informieren
Referenzkunden
Elektrische Antriebe und Energiesysteme 2025 | 26 + 27 März 2025

19. Internationaler MTZ-Fachkongress Zukunftsantriebe

Seien Sie bei der Konferenz dabei! Dort treffen Experten aus der Automobilindustrie, Energieerzeugung und Stromnetzbetrieb auf Vertreter aus Politik und Wissenschaft. Diskutiert werden wichtige Themen der Branche.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Kapitel lesen Erstes Kapitel lesen

2024 | OriginalPaper | Buchkapitel

Empirical Evaluation of Evolutionary Algorithms with Power-Law Ranking Selection

verfasst von : Duc-Cuong Dang, Anton V. Eremeev, Xiaoyu Qin

Erschienen in: Intelligent Information Processing XII

Verlag: Springer Nature Switzerland

Einloggen

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

search-config
loading …

Abstract

It has been proven that non-elitist evolutionary algorithms (EAs) with proper selection mechanisms, including the recently proposed power-law ranking selection, can efficiently escape local optima on a broad class of problems called SparseLocalOpt \(_{\alpha ,\varepsilon }\), where elitist EAs fail. However, those theoretical upper bounds on the runtime are not tight as they require large populations and a tight balance between mutation rates and selection pressure to keep the algorithms operating near the so-called “error threshold”. This paper empirically clarifies the significance of these theoretical requirements and makes a series of performance comparisons between the non-elitist EA using power-law ranking selection and other EAs on various benchmark problems.
Our experimental results show that non-elitist EAs optimise the Funnel problem with deceptive local optimum significantly faster with power-law ranking selection than with tournament selection. Furthermore, power-law selection outperforms UMDA and the (1+1) EA in our experiments on the NK-Landscape and Max k-Sat problems, but yields to the \((\mu ,\lambda )\)-selection, tournament selection, and the self-adaptive MOSA-EA. On the unicost set cover problems, the EA with power-law selection shows competitive results.

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 Entity Relation Joint Extraction with Data Augmentation Based on Large Language Model
Nächstes Kapitel An Indicator Based Evolutionary Algorithm for Multiparty Multiobjective Knapsack Problems
Literatur
1.
Baker, J.E.: An analysis of the effects of selection in genetic algorithms. Ph.D. thesis, Vanderbilt University (1989)
2.
Beasley, J.E.: OR-Library: distributing test problems by electronic mail. J. Oper. Res. Soc. 41(11), 1069–1072 (1990)CrossRef
3.
Buzdalov, M., Doerr, B.: Runtime analysis of the \((1 + (\lambda ,\lambda ))\) genetic algorithm on random satisfiable 3-CNF formulas. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 1343–1350. ACM, Berlin Germany (2017)
4.
Corus, D., Dang, D.C., 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
5.
Dang, D.C., Eremeev, A., Lehre, P.K.: escaping local optima with non-elitist evolutionary algorithms. In: Proceedings of AAAI 2021. AAAI Press, Palo Alto, California USA (2020)
6.
Dang, D.C., Eremeev, A., Lehre, P.K.: Non-elitist evolutionary algorithms excel in fitness landscapes with sparse deceptive regions and dense valleys. In: Proceedings of the GECCO, pp. 1133–1141. GECCO ’21, ACM, New York, NY, USA (2021)
7.
Dang, D.C., Eremeev, A., Lehre, P.K., Qin, X.: Fast non-elitist evolutionary algorithms with power-law ranking selection. In: Proceedings of GECCO, pp. 1372–1380. GECCO ’22, ACM, New York, NY, USA (2022)
8.
9.
Doerr, B., Doerr, C., Ebel, F.: From black-box complexity to designing new genetic algorithms. Theoret. Comput. Sci. 567, 87–104 (2015)MathSciNetCrossRef
10.
Doerr, B., Le, H.P., Makhmara, R., Nguyen, T.D.: Fast genetic algorithms. In: Proceedings of the GECCO, pp. 777–784. ACM, Berlin Germany (2017)
11.
Gao, C., Yao, X., Weise, T., Li, J.: An efficient local search heuristic with row weighting for the unicost set covering problem. Eur. J. Oper. Res. 246(3), 750–761 (2015)MathSciNetCrossRef
12.
Goldberg, D.E., Deb, K.: A comparative analysis of selection schemes used in genetic algorithms. In: Proceedings of the First Workshop on Foundations of Genetic Algorithms, pp. 69–93. Morgan Kaufmann (1990)
13.
Harik, G., Lobo, F., Goldberg, D.: The compact genetic algorithm. IEEE Trans. Evol. Comput. 3(4), 287–297 (1999)CrossRef
14.
Hevia Fajardo, M.A.H., Sudholt, D.: Self-adjusting population sizes for non-elitist evolutionary algorithms: why success rates matter. In: Proceedings of GECCO, pp. 1151–1159. ACM, Lille France (2021)
15.
16.
Lehre, P.K., Qin, X.: Self-adaptation via Multi-objectivisation: a theoretical study. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 1417–1425. ACM, Boston, USA (2022)
17.
Lehre, P.K., Yao, X.: On the impact of mutation-selection balance on the runtime of evolutionary algorithms. IEEE Trans. Evol. Comput. 16(2), 225–241 (2012)CrossRef
18.
19.
Ochoa, G.: Error thresholds in genetic algorithms. Evol. Comput. 14(2), 157–182 (2006)CrossRef
20.
21.
Sudholt, D., Witt, C.: Update Strength in EDAs and ACO: how to avoid genetic drift. In: Proceedings of the Genetic and Evolutionary Computation Conference 2016, pp. 61–68. ACM, Denver Colorado USA (2016)
22.
Vose, M.D.: A linear algorithm for generating random numbers with a given distribution. IEEE Trans. Softw. Eng. 17(9), 972–975 (1991)MathSciNetCrossRef
23.
Walker, A.J.: New fast method for generating discrete random numbers with arbitrary frequency distributions. Electron. Lett. 10(8), 127–128 (1974)CrossRef
Metadaten
Titel
Empirical Evaluation of Evolutionary Algorithms with Power-Law Ranking Selection
verfasst von
Duc-Cuong Dang
Anton V. Eremeev
Xiaoyu Qin
Copyright-Jahr
2024
Buch
Intelligent Information Processing XII

Print ISBN: 978-3-031-57807-6

Electronic ISBN: 978-3-031-57808-3

Copyright-Jahr: 2024

DOI
https://doi.org/10.1007/978-3-031-57808-3_16

Premium Partner

    Bildnachweise