Lasting Diversity and Superior Runtime Guarantees for the (μ+1) Genetic Algorithm

Abstract

Most evolutionary algorithms (EAs) used in practice employ crossover. In contrast, only for few and mostly artificial examples a runtime advantage from crossover could be proven with mathematical means. The most convincing such result shows that the (+1) genetic algorithm (GA) with population size =O(n) optimizes jump functions with gap size k 3 in time O(n^k / + n^k-1 n), beating the (n^k) runtime of many mutation-based EAs. This result builds on a proof that the GA occasionally and then for an expected number of (^2) iterations has a population that is not dominated by a single genotype. In this work, we show that this diversity persist with high probability for a time exponential in (instead of quadratic). From this better understanding of the population diversity, we obtain stronger runtime guarantees, among them the statement that for all c(n) n/ n, with c a suitable constant, the runtime of the (+1) GA on Jump_k, with k 3, is O(n^k-1). Consequently, already with logarithmic population sizes, the GA gains a speed-up of order (n) from crossover.

Tasks

Reproductions