Abstract: We consider a simple genetic algorithm (SGA) with fitnessproportionate selection, bitwise mutation, and crossover, and obtain upper bounds on its expected optimization time on Royal Road function [4]. E[T] is the expected runtime, i.e. the expected number of individuals produced and evaluated until an optimal genotype is found for the first time. We first derive an upper bound on the expected optimization time of the SGA with mutation probability χ/n2, where χ > 0 is a constant, crossover probability pc < 1, and population sizeλ = Ω(n ln n), applying the improved level-based theorem of Doerr and Kotzing [2], we obtain E[T] = On2a1λlog(na1)+n2r+1ar+1 1 log n . In the case of crossover probability pc = 1 and exponentially scaled fitness dRR(x) with constant base d such, that dεcr > 5eχ (where εcr is a lower bound on the crossover gain), the level-based theorem of Corus et al. [1] yields E[T] = O(nλlnλ + nr+1). This bound extends the linearfunction result of [3] to all Royal Road functions and shows that the SGA with exponential scaling and crossover achieves a polynomial expected optimization time for any constant r. At r = 1 both bounds reduce to the previously known estimates for linear functions from [3]. The results of experiments with the SGA with and without a single elite individual are also discussed.

Cite: Груздев Н.А.
Upper Bounds on Optimization Time of Genetic Algorithm on Royal Road Functions
Springer Optimization and Its Applications. 2026.

Identifiers: No identifiers