代写720 IEEE编程、代做Python，Java，c/c++程序语言

日期：2021-07-12 11:17

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: d.corus@sheffield.ac.uk; p.oliveto@sheffield.ac.uk).

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

(1+(λ, λ)) GA which optimizes the ONEMAX function in

(n