PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast Genetic Algorithms

Benjamin Doerr, Huu Phuoc Le, Régis Makhmara, Ta Duy Nguyen

arXiv:1703.03334v2cs.NE

TL;DR

The paper asks whether the standard mutation rate 1/n is justified for multimodal optimization, where escaping local optima may require multi-bit flips. It introduces a power-law heavy-tailed mutation operator and proves that it achieves near-optimal performance across jump sizes, with analogous improvements for vertex cover and matching.

  • Problem

    The paper examines whether the conventional mutation rate 1/n is appropriate for multimodal functions such as Jump_m,n, where optimization requires crossing a fitness valley by flipping m bits.

  • Method

    The proposed operator samples α from a power-law distribution and applies standard-bit mutation with rate α/n, rather than using one fixed rate.

  • Results

    The heavy-tailed operator optimizes every Jump_m,n in expected time only O(m^(β−0.5)) above the m-specific optimum and improves results on vertex cover and matching.

  • Takeaways & Limitations

    Heavy-tailed mutation provides a one-size-fits-all operator with nearly optimal performance on all jump functions and asymptotically equal or better performance on many previously analyzed problems.

  • Takeaways & Limitations

    Small constant-factor deviations from the optimal mutation rate cause an exponential-in-m slowdown, and no randomized rate choice can achieve O(m^0.5 T_opt(m,n)) for all m.

Abstract

from arXiv · show

For genetic algorithms using a bit-string representation of length~$n$, the general recommendation is to take $1/n$ as mutation rate. In this work, we discuss whether this is really justified for multimodal functions. Taking jump functions and the $(1+1)$ evolutionary algorithm as the simplest example, we observe that larger mutation rates give significantly better runtimes. For the $\jump_{m,n}$ function, any mutation rate between $2/n$ and $m/n$ leads to a speed-up at least exponential in $m$ compared to the standard choice. The asymptotically best runtime, obtained from using the mutation rate $m/n$ and leading to a speed-up super-exponential in $m$, is very sensitive to small changes of the mutation rate. Any deviation by a small $(1 \pm \eps)$ factor leads to a slow-down exponential in $m$. Consequently, any fixed mutation rate gives strongly sub-optimal results for most jump functions. Building on this observation, we propose to use a random mutation rate $α/n$, where $α$ is chosen from a power-law distribution. We prove that the $(1+1)$ EA with this heavy-tailed mutation rate optimizes any $\jump_{m,n}$ function in a time that is only a small polynomial (in~$m$) factor above the one stemming from the optimal rate for this $m$. Our heavy-tailed mutation operator yields similar speed-ups (over the best known performance guarantees) for the vertex cover problem in bipartite graphs and the matching problem in general graphs. Following the example of fast simulated annealing, fast evolution strategies, and fast evolutionary programming, we propose to call genetic algorithms using a heavy-tailed mutation operator \emph{fast genetic algorithms}.

1 Introduction

The paper argues that mutation rate 1/n is poorly suited to multimodal jump landscapes because escaping local optima requires rare multi-bit flips. It proposes heavy-tailed mutation rates, which provide near-optimal performance across jump sizes and improve broader optimization guarantees.

  • Motivation: Jump_m,n creates a fitness valley requiring an elitist algorithm to flip m bits from a local-optimum plateau to the global optimum.This makes long-distance jumps the critical search event.
  • Mutation-rate sensitivity: For Jump_m,n, mutation rate m/n is asymptotically optimal, with T_opt(m,n)=(1+o(1))T_m/n.This yields a super-exponential improvement in m over the classic rate 1/n.
  • Mutation-rate sensitivity: Small constant-factor deviations from m/n make expected runtime exponentially larger than T_m/n(m,n), so no fixed rate performs well across jump sizes.Binomial concentration around the selected mutation strength explains this sensitivity.
  • Heavy-tailed mutation: The heavy-tailed operator samples α from a power-law distribution and then applies standard-bit mutation with rate α/n.Sampling mutation strengths spreads probability across different jump sizes.
  • General guarantees: The general runtime bound improves from tight O(n^n) to O(n^β2^n) for pseudo-Boolean functions with a unique optimum.The operator retains constant probability for flipping any fixed number of bits and positive reachability between search points.
  • Heavy-tailed mutation: For any Jump_m,n with m>β−1, the heavy-tailed EA is only O(m^(β−0.5)) slower than the mutation rate optimal for that m.It therefore provides near-optimal performance without knowing the instance-specific jump size.
  • Additional problems: For m=8 and β=1.5, the heavy-tailed operator was at least 2000 times faster than the classic choice for every tested n from 20 through 150.The paper also reports improved bounds for vertex cover in complete bipartite graphs and approximate matching in arbitrary graphs.

2 Related Work

Prior work generally favors mutation rates near 1/n for simple discrete optimization, while dynamic and heavy-tailed mutation choices extend rate adaptation beyond standard fixed settings.

  • Mutation-rate selection: A mutation rate of 1/n is the long-standing recommendation for discrete evolutionary algorithms, though crossover can motivate different rates.The recommended rate flips one bit on average.
  • Static and dynamic rates: For the (1+1) EA, 1/n is uniquely optimal on pseudo-Boolean linear functions, whereas LeadingOnes favors approximately 1.59/n.
  • Static and dynamic rates: Dynamic mutation-rate choices have been proposed, typically beginning with higher rates and reducing them during optimization.Prior theory includes iteration-dependent and fitness-dependent schedules.
  • Static and dynamic rates: Fitness-dependent mutation rates improve known LeadingOnes and OneMax runtimes, while a note in this paper says they cannot significantly improve the best static rate for jump functions.
  • Heavy-tailed operators: Heavy-tailed mutation operators have been studied across heuristic optimization and evolutionary computation, but previously in continuous search spaces; their general usefulness has also been questioned.The cited concern is that large variations may help mainly in a low-dimensional subspace containing good solutions.

3 Preliminaries

The paper studies pseudo-Boolean optimization on bit strings, using Jump functions and the (1+1) EA to examine how mutation operators cross multimodal fitness valleys.

  • Problem setting: The paper restricts attention to pseudo-Boolean functions f:{0,1}^n→R defined on bit strings of length n, with OneMax as a unimodal reference.
  • Jump functions: Jump_m,n modifies OneMax by assigning very low fitness to the final m−1 suboptimal levels, creating a plateau of local optima.
  • Jump functions: On Jump_m,n, an elitist algorithm reaches the local-optimum plateau and must flip exactly the right m bits to reach the global optimum.The paper considers m∈[2..n/2].
  • Prior baselines: Earlier work found T_1/n(m,n)=Θ(n^m+n log n) for the (1+1) EA, while crossover-based GAs obtained improved m-dependence under specific parameter settings.For constant m≥3, one cited GA achieves O(n^(m−1) log n).
  • The (1+1) EA: The standard (1+1) EA starts from a random bit string, mutates each bit independently, and accepts offspring unless its fitness is inferior.
  • The (1+1) EA: Performance is measured by the expected number of fitness evaluations until the optimum is first evaluated, denoted T_p(m,n).Mutation rates are assumed to lie in [0,1/2].

4 Static Mutation Rates

The static-rate analysis shows that mutation rate m/n is asymptotically best for Jump_m,n, whereas rates outside a narrow neighborhood can incur exponentially worse runtimes.

  • Main result: The main result identifies p=m/n as the asymptotically best static mutation rate for Jump_m,n, far from 1/n when m is large.
  • Runtime bounds: Theorem 1 bounds T_p(m,n) using the reciprocal probability p^m(1−p)^(n−m) of the required m-bit jump, plus a lower-order term.
  • Runtime bounds: The simpler bounds give 1/(2p^m(1−p)^(n−m))≤T_p(m,n)≤3/(p^m(1−p)^(n−m)).
  • Rate sensitivity: Any p outside [(1−ε)m/n,(1+ε)m/n] is slower than the optimum by an exponential-in-m factor, showing strong sensitivity to rate misspecification.

5 Design and Analysis of Heavy-tailed Mutation Operators

The paper replaces a fixed mutation rate with a power-law-selected rate, preserving easy one-bit flips while enabling jumps of varying sizes. Analyses show near-optimal performance across jump functions and improvements on several combinatorial problems.

  • Jump functions: The (1+1) FEAβ optimizes Jump_m,n in a runtime only polynomially larger in m than the optimum for the corresponding m.The stated guarantee applies when m ∈ [2..n/2] and m > β−1.
  • Motivation: A small constant-factor error around the optimal m/n mutation rate causes a runtime loss exponential in m, motivating randomized mutation rates.Strong binomial concentration makes suitable multi-bit flips exponentially unlikely when the fixed rate is mismatched.
  • Operator properties: The operator flips one or any other constant number of bits with constant probability, retaining standard-bit mutation’s behavior on easy unimodal regions.It also assigns positive probability to creating any search point from any parent.
  • Operator design: The heavy-tailed operator chooses α ∈ [1..n/2] from a power-law distribution and applies standard-bit mutation at rate α/n.The distribution is intended to avoid concentrating the number of flipped bits around one expected value.
  • Other problems: For OneMax, LeadingOnes, and minimum spanning tree, the heavy-tailed operator preserves established polynomial runtime guarantees, including O(n log n), O(n^2), and O(m^2 log(nw_max)).Parallel (1+λ) results are also given for these problems.
  • Scope: The analysis does not cover m ≤ β−1, and the authors report no indication that larger β values are useful.For β < 3, the omitted case does not occur.
  • Uniform performance: No randomized mutation-rate distribution can achieve a uniformly smaller-than-√m loss factor over all jump functions.Choosing β=1+ε yields a loss factor Θ(m^0.5+ε) for any ε > 0.
  • Combinatorial optimization: The operator improves prior analyses for bipartite vertex cover and general-graph matching because required multi-bit flips occur at higher rates.For vertex cover, the heavy-tailed algorithm avoids the standard algorithm’s difficult transition from a local optimum through an m-bit change.

6 Experiments

Experiments on Jump8,n compare the heavy-tailed operator with the classical (1+1) EA across mutation-distribution parameters β. Smaller β values perform better, with β=1.5 uniformly outperforming the classical algorithm.

  • Experimental setup: For m=8 and n between 20 and 150, the experiment averages optimization iterations over 1000 runs for each β and the classical (1+1) EA.Figure 2 reports the iterations needed to reach the optimum.
  • Results: β=1.5 uniformly outperforms the classical (1+1) EA, while values below β=1.5 show no significant additional performance increase.The experiment depicts only β ≥ 1.5.

7 Conclusions

The conclusions argue that mutation rates above 1/n can substantially improve multimodal optimization, while a power-law-randomized rate provides nearly optimal performance across jump functions. The approach also matches or improves prior guarantees on several problems, but real applications and non-bit-string settings remain open areas.

  • Conclusions: Mutation rates significantly above 1/n perform much better on the paper’s multimodal test cases.The analysis links this to the need for multi-bit flips to leave local optima.
  • Conclusions: A power-law-randomized mutation probability gives nearly optimal performance across all jump functions despite the narrow optimal interval for fixed rates.The authors describe this as a “one size fits all” mutation operator.
  • Broader performance: The heavy-tailed operator achieves asymptotically equal or better performance on many previously analyzed problems.The stated improvements include cases that are massively better.
  • Scope and future work: The approach can be adapted beyond bit strings by replacing Poisson-distributed elementary mutations with a heavy-tailed distribution, but this was not studied in detail.Permutations are given as an example representation.
  • Future work: The paper identifies performance on real applications as an important next step and provides code to facilitate further experiments.The authors point readers to a repository containing the implementation.
Loading 1703.03334v2…