EUVIMEDEUVIMED entdecken
Crossref

The Cost of Randomness in Evolutionary Algorithms: Crossover Can Save Random Bits

Carlo Kneissl, Dirk Sudholt iD

Evolutionary Computation · 2025

DOI: 10.1162/evco_a_00365 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Evolutionary Computation, 2025. Verfasst von Carlo Kneissl und 1 weiteren Autor:innen. Beteiligte Einrichtung: Chair of Algorithms for Intelligent Systems, University of Passau, Passau, Germany car.kneissl@gmail.com. Hauptthemen laut MEDLINE: Algorithms, Models, Genetic, Biological Evolution.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Evolutionary algorithms make countless random decisions during selection, mutation and crossover operations. These random decisions require a steady stream of random numbers. We analyze the expected number of random bits used throughout a run of an evolutionary algorithm and refer to this as the cost of randomness. We give general bounds on the cost of randomness for mutation-based evolutionary algorithms using 1-bit flips or standard mutations using either a naive or a common, more efficient implementation that uses Θ(logn) random bits per mutation. Uniform crossover is a potentially wasteful operator as the number of random bits used equals the Hamming distance of the two parents, which can be up to n. However, we show for a (2+1) Genetic Algorithm that is known to optimize the test function ONEMAX in roughly (e/2)nlnn expected evaluations, twice as fast as the fastest mutation-based evolutionary algorithms, that the total cost of randomness during all crossover operations on ONEMAX is only Θ(n). A more pronounced effect is shown for the common test function JUMPk, where there is an asymptotic decrease both in the number of evaluations and in the cost of randomness. Consequently, the use of crossover can reduce the cost of randomness below that of the fastest evolutionary algorithms that only use standard mutations.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

AlgorithmsModels, GeneticBiological EvolutionMutationComputer Simulation

Stichwörter der Autor:innen

Evolutionary algorithmscrossoverpopulation diversityruntime analysistheory

Autor:innen und Institutionen

  • Chair of Algorithms for Intelligent Systems, University of Passau, Passau, Germany car.kneissl@gmail.com.
  • Chair of Algorithms for Intelligent Systems, University of Passau, Passau, Germany dirk.sudholt@uni-passau.de.

ORCID-Profile: Dirk Sudholt

Zitieren

APA

Kneissl, C., & Sudholt, D. (2025). The Cost of Randomness in Evolutionary Algorithms: Crossover Can Save Random Bits. Evolutionary Computation. https://doi.org/10.1162/evco_a_00365

Vancouver

Kneissl C, Sudholt D. The Cost of Randomness in Evolutionary Algorithms: Crossover Can Save Random Bits. Evolutionary Computation. 2025. doi:10.1162/evco_a_00365

BibTeX
@article{Kneissl2025,
  author = {Kneissl, Carlo and Sudholt, Dirk},
  title = {The Cost of Randomness in Evolutionary Algorithms: Crossover Can Save Random Bits},
  journal = {Evolutionary Computation},
  year = {2025},
  doi = {10.1162/evco_a_00365}
}
Kostenlos starten →