EUVIMEDEUVIMED entdecken
Crossref

Drift Analysis with Fitness Levels for Elitist Evolutionary Algorithms

Jun He iD, Yuren Zhou

Evolutionary Computation · 15.03.2025 · 33 (1) · 1-25

DOI: 10.1162/evco_a_00349 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Evolutionary Computation, online erschienen am 15.03.2025. Verfasst von Jun He und 1 weiteren Autor:innen. Beteiligte Einrichtung: Department of Computer Science, Nottingham Trent University, Nottingham NG11 8NS, United Kingdom jun.he@ntu.ac.uk. Hauptthemen laut MEDLINE: Algorithms, Biological Evolution, Models, Genetic, Genetic Fitness. Die Arbeit wurde bisher 6-mal zitiert (Crossref) und nennt 34 Literaturangaben.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The fitness level method is a popular tool for analyzing the hitting time of elitist evolutionary algorithms. Its idea is to divide the search space into multiple fitness levels and estimate lower and upper bounds on the hitting time using transition probabilities between fitness levels. However, the lower bound generated by this method is often loose. An open question regarding the fitness level method is what are the tightest lower and upper time bounds that can be constructed based on transition probabilities between fitness levels. To answer this question, we combine drift analysis with fitness levels and define the tightest bound problem as a constrained multiobjective optimization problem subject to fitness levels. The tightest metric bounds by fitness levels are constructed and proven for the first time. Then linear bounds are derived from metric bounds and a framework is established that can be used to develop different fitness level methods for different types of linear bounds. The framework is generic and promising, as it can be used to draw tight time bounds on both fitness landscapes with and without shortcuts. This is demonstrated in the example of the (1+1) EA maximizing the TwoMax1 function.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

AlgorithmsBiological EvolutionModels, GeneticGenetic FitnessComputer SimulationProbability

Stichwörter der Autor:innen

Evolutionary algorithmMarkov chain.algorithm analysisdrift analysisfitness levelshitting time

Autor:innen und Institutionen

  • Department of Computer Science, Nottingham Trent University, Nottingham NG11 8NS, United Kingdom jun.he@ntu.ac.uk.
  • School of Data and Computer Science, Sun Yatsen University, Guangzhou, 510006, China zhouyuren@mail.sysu.edu.cn.

ORCID-Profile: Jun He

Zitieren

APA

He, J., & Zhou, Y. (2025). Drift Analysis with Fitness Levels for Elitist Evolutionary Algorithms. Evolutionary Computation, 33(1), 1-25. https://doi.org/10.1162/evco_a_00349

Vancouver

He J, Zhou Y. Drift Analysis with Fitness Levels for Elitist Evolutionary Algorithms. Evolutionary Computation. 2025;33(1):1-25. doi:10.1162/evco_a_00349

BibTeX
@article{He2025,
  author = {He, Jun and Zhou, Yuren},
  title = {Drift Analysis with Fitness Levels for Elitist Evolutionary Algorithms},
  journal = {Evolutionary Computation},
  year = {2025},
  volume = {33},
  number = {1},
  pages = {1--25},
  doi = {10.1162/evco_a_00349}
}
Kostenlos starten →