Lasting Diversity and Superior Runtime Guarantees for the (μ+1) Genetic Algorithm
share
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-1log 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 cln(n)≤μ≤ n/log 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.
READ FULL TEXT