The Cost of Randomness in Evolutionary Algorithms: Crossover Can Save Random Bits
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.
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)
Stichwörter der Autor:innen
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}
}
EUVIMED