720 IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 22, NO. 5, OCTOBER 2018
Standard Steady State Genetic Algorithms Can
Hillclimb Faster Than Mutation-Only
Evolutionary Algorithms
Dogan Corus, Member, IEEE, and Pietro S. Oliveto , Senior Member, IEEE
Abstract—Explaining to what extent the real power of genetic
algorithms (GAs) lies in the ability of crossover to recombine indi-
viduals into higher quality solutions is an important problem in
evolutionary computation. In this paper we show how the inter-
play between mutation and crossover can make GAs 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 GAs to hillclimb the
ONEMAX function. The bound establishes that the steady-state
GAs are 25% faster than all standard bit mutation-only evolu-
tionary 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 two 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 GAs are faster than standard
ones, further suggesting that the derived lower bound also holds
for the standard steady state (2 + 1) GA.
Index Terms—Algorithms design and analysis, genetic algo-
rithms (GAs), Markov processes, stochastic processes.
I. INTRODUCTION
GENETIC algorithms (GAs) rely on a population of indi-viduals that simultaneously explore the search space.
The main distinguishing features of GAs from other random-
ized search heuristics is their use of a population and crossover
to generate new solutions. Rather than slightly modifying the
current best solution as in more traditional heuristics, the idea
behind GAs is that new solutions are generated by recom-
bining individuals of the current population (i.e., crossover).
Such individuals are selected to reproduce probabilistically
according to their fitness (i.e., reproduction). Occasionally,
Manuscript received November 15, 2016; revised April 13, 2017,
July 7, 2017, and August 3, 2017; accepted August 5, 2017. Date of publi-
cation September 26, 2017; date of current version September 28, 2018. This
work was supported by EPSRC under Grant EP/M004252/1. (Corresponding
author: Pietro S. Oliveto.)
The authors are with the Rigorous Research Team, Algorithms Group,
Department of Computer Science, University of Sheffield, Sheffield S1 4DP,
U.K. (e-mail: mailto:[email protected]; mailto:[email protected]).
This paper has supplementary downloadable multimedia material available
at http://ieeexplore.ieee.org provided by the authors.
Color versions of one or more of the figures in this paper are available
online at http://ieeexplore.ieee.org.
Digital Object Identifier 10.1109/TEVC.2017.2745715
random mutations may slightly modify the offspring produced
by crossover. The original motivation behind these mutations
is to avoid that some genetic material may be lost forever, thus
allowing to avoid premature convergence [16], [18]. For these
reasons the GA community traditionally regards crossover as
the main search operator while mutation is considered a “back-
ground operator” [1], [16], [19] or a “secondary mechanism
of genetic adaptation” [18].
Explaining when and why GAs are effective has proved to
be a nontrivial task. Schema theory and its resulting building
block hypothesis [18] were devised to explain such working
principles. However, these theories did not allow to rigor-
ously characterize the behavior and performance of GAs.
The hypothesis was disputed when a class of functions (i.e.,
Royal Road), thought to be ideal for GAs, was designed and
experiments revealed that the simple (1+1) EA was more
efficient [20], [27].
Runtime analysis approaches have provided rigorous proofs
that crossover may indeed speed up the evolutionary process
of GAs in ideal conditions (i.e., if sufficient diversity is avail-
able in the population). The JUMP function was introduced by
Jansen and Wegener [22] as a first example, where crossover
considerably improves the expected runtime compared to
mutation-only evolutionary algorithms (EAs). The proof
required an unrealistically small crossover probability to allow
mutation alone to create the necessary population diversity
for the crossover operator to then escape the local optimum.
Dang et al. [6] recently showed that the sufficient diversity,
and even faster upper bounds on the runtime for not too large
jump gaps, can be achieved also for realistic crossover proba-
bilities by using diversity mechanisms. Further examples that
show the effectiveness of crossover have been given for both
artificially constructed functions and standard combinatorial
optimization problems (see the next section for an overview).
Excellent hillclimbing performance of crossover-based GAs
has been also proved. Doerr et al. [8], [9] proposed a
WX：codehelp