PaperlayerView exact revision on arXiv

Source-linked AI summary

Standard Steady State Genetic Algorithms Can Hillclimb Faster than Mutation-only Evolutionary Algorithms

Dogan Corus, Pietro S. Oliveto

arXiv:1708.01571v2cs.NE

TL;DR

The paper asks whether ordinary genetic algorithms can use crossover to hillclimb faster without artificially enforced diversity. It analyzes steady-state GAs on OneMax with a Markov-chain framework and reports at least 25% faster runtime than standard bit mutation-based EAs for moderate population sizes.

  • Problem

    The paper addresses how much crossover contributes to genetic algorithms, including whether it can speed hillclimbing without artificial diversity enforcement.

    Source: §1 · pp. 1–2

  • Method

    A Markov-chain framework bounds standard steady-state GA runtime on OneMax, alongside a lower-bound analysis of a greedy (2+1)S GA.

    Source: §1 · pp. 2–3

  • Results

    For µ ≥3 and µ = o(log n / log log n), standard steady-state GAs are at least 25% faster than unbiased standard bit mutation-based EAs with static mutation rate on OneMax.

    Source: §8 · p. 33

  • Takeaways & Limitations

    Populations can improve exploitation during hillclimbing by increasing the probability of creating and maintaining diversity that crossover can exploit.

    Source: §8 · p. 34

    The optimal population size and mutation rate remain open questions, and the experimentally suggested optimal mutation rate exceeds the rate yielding the best theoretical upper bound.

    Source: §8 · p. 35

Abstract

from arXiv · show

Explaining to what extent the real power of genetic algorithms lies in the ability of crossover to recombine individuals into higher quality solutions is an important problem in evolutionary computation. In this paper we show how the interplay between mutation and crossover can make genetic algorithms hillclimb faster than their mutation-only counterparts. We devise a Markov Chain framework that allows to rigorously prove an upper bound on the runtime of standard steady state genetic algorithms to hillclimb the OneMax function. The bound establishes that the steady-state genetic algorithms are 25% faster than all standard bit mutation-only evolutionary algorithms with static mutation rate up to lower order terms for moderate population sizes. The analysis also suggests that larger populations may be faster than populations of size 2. We present a lower bound for a greedy (2+1) GA that matches the upper bound for populations larger than 2, rigorously proving that 2 individuals cannot outperform larger population sizes under greedy selection and greedy crossover up to lower order terms. In complementary experiments the best population size is greater than 2 and the greedy genetic algorithms are faster than standard ones, further suggesting that the derived lower bound also holds for the standard steady state (2+1) GA.

1 Introduction

The paper asks whether crossover and mutation can accelerate ordinary steady-state GA hillclimbing without artificially preserving diversity. It answers with runtime bounds for OneMax, a lower bound for the two-individual case, and supporting experiments.

1 Introduction

  • For µ ≥3 and µ = o(log n / log log n), the standard steady-state (µ+1) GA has runtime at most (3/4)en log n + O(n) on OneMax with mutation rate 1/n.The bound is faster, up to lower-order terms, than standard bit mutation-only algorithms in the stated population-size range.Source: §1 · p. 2
  • The paper reports better runtime bounds for mutation rates higher than the standard 1/n rate, and gives the best upper bound, 0.72en log n + O(n), at c/n with c = 1.Source: §1 · p. 3
  • A constant probability of population takeover in each generation explains why the upper bound for µ = 2 has a larger leading constant than for µ ≥3.For populations larger than 2, this takeover event does not have a constant probability.Source: §1 · p. 3
  • The greedy (2+1)S GA has a matching lower bound for constant mutation rates c/n, so under greedy selection and semi-greedy crossover it cannot outperform the stated larger-population GAs.Its analysis does not enforce diversity artificially, and crossover succeeds only when parent Hamming distance exceeds 2.Source: §1 · p. 3
  • Experiments find speedups over the (1+1) EA at small n, faster performance for populations larger than 2, and better runtimes at mutation rates c/n with 1.5 ≤ c ≤1.6 than at 1/n.The greedy (2+1)S GA also appears faster than the standard (2+1) GA, consistent with the lower-bound analysis applying to the latter.Source: §1 · p. 3

2 Related Work

Earlier analyses showed crossover benefits for escaping local optima and for OneMax hillclimbing, but some relied on artificial diversity mechanisms or specially designed algorithms. This paper’s context is the question of whether standard steady-state GAs can benefit during hillclimbing without enforced diversity.

2 Related Work

  • For the Jump function, standard steady-state GAs with realistic settings can escape local-optimum plateaus faster than standard bit mutation-only EAs without artificial diversity enforcement.Earlier analyses progressed from an unrealistically low crossover probability to more realistic algorithm characteristics.Source: §2 · p. 4
  • Crossover has also been shown useful on several less artificial problems, where it can help escape local optima with large basins of attraction for mutation.Other analyses used artificially designed Real Royal Road functions, but those functions did not resemble the schemata structures motivating the building block hypothesis.Source: §2 · p. 4
  • For OneMax hillclimbing, prior work showed standard (µ+λ) GAs outperform mutation-only counterparts, but its selection stage artificially enforced diversity.The paper positions its contribution as proving this speedup for standard steady-state GAs without that mechanism.Source: §2 · p. 4

3 Preliminaries

The paper analyzes a steady-state GA that creates one offspring per generation, using a population of size µ, and evaluates its hillclimbing runtime on OneMax. The algorithm combines parent selection, uniform crossover, and standard bit mutation before retaining the best µ solutions.

3 Preliminaries

  • The analyzed steady-state GA has population size µ and one offspring per generation; its runtime is the expected evaluations until an optimum is found.The analysis allows multiple parent-selection mechanisms rather than restricting itself to uniform selection.Source: §3 · p. 4
  • Each generation selects two parents with replacement, applies uniform crossover, then flips each offspring bit with probability c/n.The best µ of the µ+1 solutions survive, with ties broken uniformly at random.Source: §3 · p. 5
  • The (µ+1) EA is the corresponding mutation-only version: it selects one individual for reproduction and applies standard bit mutation without crossover.Otherwise, the two algorithms are identical.Source: §3 · p. 5
  • OneMax assigns each n-bit string its number of 1-bits, making improvement harder as the search approaches the all-ones optimum.The target may be taken as all ones without loss of generality.Source: §3 · p. 5

4 Markov Chain Framework

This section develops a Markov-chain framework for analyzing steady-state GA runtime on OneMax, modeling how diversity is created, exploited, and lost as fitness levels emerge and spread through the population. It bounds the time for a new level to spread and identifies a population-size condition under which takeover time does not alter the runtime’s leading constant.

4 Markov Chain Framework

  • At each fitness level, the chain distinguishes a homogeneous population S1 from a diverse population S2, with transitions between them and absorption upon finding a better level.Mutation creates diversity with probability pd, diversity is lost with relapse probability pr, and improvement probabilities are pm in S1 and pc in S2.Source: §4 · p. 6
  • Standard steady-state GAs can still outperform mutation-only EAs because crossover has a higher chance of improving fitness while diversity remains available, although diversity may relapse before crossover succeeds.Unlike the GA analyzed by Sudholt, diversity is not enforced and can be lost; the framework models this with pr.Source: §4 · p. 7
  • For µ > 2, the framework gives a better upper bound than for µ = 2 because the probability of removing the sole diverse individual is 1/µ and diversity is not lost every generation.This identifies a potential benefit of larger populations that the diversity-enforcing analysis in could not capture.Source: §4 · p. 7
  • When pc > pm, lower bounds on pm, pd, and pc and an upper bound on pr yield an upper bound on expected absorption time from S1.Because S1 has the longer expected absorption time under this condition, it can pessimistically represent the starting state at each fitness level.Source: §4 · pp. 7, 9, 11
  • O(µ log µ) generations suffice for the whole population to reach level at least i when its best individual is at level i and all individuals are at least at level i − 1.Summing level-exit runtimes and whole-population takeover times gives an upper bound on total expected runtime.Source: §4 · p. 12
  • O(µ log µ) generations suffice for the population to consist entirely of individuals at a newly discovered fitness level or higher.When an individual at that level is selected as a parent, crossover produces at least i 1-bits with probability at least 1/4; mutation then leaves the offspring unchanged with probability at least 1/(ec + 1).Source: §4 · p. 12
  • µ = o(log n / log log n) keeps takeover of all fitness levels in expected o(n log n) time, so takeover does not affect the total runtime’s leading constant.For larger populations, the takeover-time upper bound can dominate the runtime unless takeover is asymptotically faster than the expected absorption time of all Markov chains.Source: §4 · p. 13

5 Upper Bound

A Markov-chain analysis bounds the runtime of the steady-state (µ+1) GA on OneMax. For µ=o(log n/log log n), the standard mutation rate gives an upper bound of (3/4)en log n.

5 Upper Bound

  • For µ≥3, the analysis bounds the (µ+1) GA's OneMax runtime using transition probabilities in a Markov-chain framework.The proof compares mutation-only improvement with crossover-assisted transitions and uses the condition pc>pm at sufficiently high fitness levels.Source: §5 · pp. 13–14
  • The analysis places the initial climb to fitness n−n/(4c(1+ec)) within expected O(nµ log µ) time.At higher fitness levels, the analysis establishes pc>pm.Source: §5 · p. 13
  • For µ≥3, the proof bounds the probabilities of losing diversity, making crossover-assisted improvement, and improving by mutation.It uses a conservative model of diversity loss, including a population with only one minority genotype at Hamming distance 2.Source: §5 · pp. 13–15
  • For mutation rate 1/n, the runtime upper bound is (3/4)en log n when µ=o(log n/log log n).The paper also reports the bound with a (1+o(1)) factor.Source: §5 · pp. 16, 19
  • For µ=2, the framework gives a higher runtime upper bound than for larger µ because either individual can take over in the next iteration, increasing the upper bound on pr.For the (2+1) GA, E[T] ≤ 4(c+4)/c (1+o(1)).Source: §5 · pp. 19–20

6 Lower bound

This section analyzes a greedy size-2 GA to determine whether it is slower than GAs with larger populations. Its lower bound matches the larger-population upper bound under greedy selection and semi-greedy crossover.

6 Lower bound

  • The analyzed (2+1)S GA uses no diversity mechanism and does not automatically crossover correctly when parent Hamming distance is exactly 2, so diversity can be lost before successful crossover.If the offspring has the same fitness as its parents and is more than 2 away from every equal-fitness population individual, semi-greedy crossover ORs it with the individual of largest Hamming distance and fitness, then adds the result.Source: §6 · p. 21
  • With two individuals, diversity can be lost by replicating either genotype; with larger populations, loss requires replication of the majority genotype.The section uses this difference to motivate comparing size 2 with populations larger than 2.Source: §6 · pp. 20–21
  • The proof applies a fitness-level method for lower bounds, using bounds on transitions between levels to establish the runtime result.The cited theorem bounds transitions from level i to higher levels using parameters u_i and γ_i,j.Source: §6 · p. 21
  • The analysis treats each phase with diversity as one iteration, ending when crossover reaches a higher fitness level or diversity is lost.It starts from a level near n and models the no-diversity and diversity-present states separately.Source: §6 · p. 22
  • (3/4)en log n − O(n log log n) is a lower bound for the (2+1)S GA at mutation rate 1/n, matching the larger-population upper bound under greedy selection and semi-greedy crossover.The comparison applies to populations up to µ = o(log n / log log n).Source: §6 · p. 28

7 Experiments

Experiments examine whether larger populations and higher mutation rates improve OneMax hillclimbing; performance gains increase with problem size, and mutation rate 1.6 further reduces runtime in the tested settings.

7 Experiments

  • With µ = 5, the (µ+1) GA outperforms the µ = 2 version, and both beat the (1+1) EA even for small problem sizes.These comparisons use uniform parent selection and the standard 1/n mutation rate.Source: §7 · p. 29, Figure 2 · p. 29
  • The theoretical 25% runtime gain over the (1+1) EA is approached more closely as n increases, and the (µ+1) GA is faster for every tested µ.Figure 5 compares runtime gains against the (1+1) EA across population sizes.Source: §7 · p. 31, Figure 5 · p. 33
  • Runtime improves for µ greater than 2 before rising again at larger population sizes, while the best static µ remains unclear.The experiments leave open whether the optimal population size increases slowly with problem size.Source: §7 · p. 31, Figure 4 · p. 31
  • Mutation rate 1.6 further decreases runtime, although c ≈ 1.3 minimizes the proved upper bound for µ = 5.The mutation-rate experiments tested c values from 0.9 to 1.9 over 1000 runs each.Source: §7 · p. 31

8 Conclusion

Whether crossover can make genetic algorithms faster hillclimbers than mutation-only algorithms has been a longstanding question. The paper proves a speedup for standard steady-state GAs on OneMax without enforced diversity, while identifying limits and open questions about the result’s scope and parameters.

Conclusion

  • For OneMax, standard steady-state GAs with µ ≥3 and µ = o(log n/ log log n) are at least 25% faster than unbiased standard bit mutation-based EAs with static mutation rates, even without enforced diversity.The paper’s result concerns this population-size range and problem setting.Source: §8 · p. 33
  • The Markov Chain approach applies to problem classes with equal-fitness plateaus, leaving its applicability to landscapes where every genotype has a different fitness unresolved.The paper leaves open whether this boundary is inherent to the framework or reflects crossover’s usefulness on such landscapes.Source: §8 · p. 34
  • Larger populations can improve exploitation during hillclimbing by increasing the probability of creating and maintaining diversity for crossover to exploit.The paper extends the role of populations beyond exploration to exploitation during hillclimbing.Source: §8 · p. 34
  • The standard 1/n mutation rate may not be optimal for the (µ+1) GA on OneMax; experiments suggest an optimal rate higher than the approximately 1.3/n rate giving the best proved upper bound.For OneMax, lower static rates appear optimal than for jumping large low-fitness valleys, but still above 1/n.Source: §8 · pp. 34–35
  • Whether the optimal population size grows with problem size and at what rate, and what mutation rate is optimal, remain open questions.Experiments suggest a higher optimal mutation rate than the approximately 1.3/n rate that yields the best runtime upper bound.Source: §8 · p. 35
  • Future work includes dynamic adaptation of population size and mutation rate, broader hillclimbing problems, and comparisons with (µ+λ) and generational GAs.The paper specifically identifies royal-road functions, linear functions, and classical combinatorial optimization problems as targets for analysis.Source: §8 · p. 35
Loading 1708.01571v2…