The (1 + λ) Evolutionary Algorithm with Self-Adjusting Mutation Rate

Benjamin Doerr, Christian Gießen, Carsten Witt*, Jing Yang

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

We propose a new way to self-adjust the mutation rate in population-based evolutionary algorithms in discrete search spaces. Roughly speaking, it consists of creating half the offspring with a mutation rate that is twice the current mutation rate and the other half with half the current rate. The mutation rate is then updated to the rate used in that subpopulation which contains the best offspring. We analyze how the (1 + λ) evolutionary algorithm with this self-adjusting mutation rate optimizes the OneMax test function. We prove that this dynamic version of the (1 + λ) EA finds the optimum in an expected optimization time (number of fitness evaluations) of O(nλ/ log λ+ nlog n). This time is asymptotically smaller than the optimization time of the classic (1 + λ) EA. Previous work shows that this performance is best-possible among all λ-parallel mutation-based unbiased black-box algorithms. This result shows that the new way of adjusting the mutation rate can find optimal dynamic parameter values on the fly. Since our adjustment mechanism is simpler than the ones previously used for adjusting the mutation rate and does not have parameters itself, we are optimistic that it will find other applications.

Original languageEnglish
JournalAlgorithmica
Volume81
Issue number2
Pages (from-to)593–631
ISSN0178-4617
DOIs
Publication statusPublished - 1 Jan 2018

Keywords

  • Evolutionary computation
  • Mutation
  • Runtime analysis
  • Self-adaptation

Cite this

Doerr, Benjamin ; Gießen, Christian ; Witt, Carsten ; Yang, Jing. / The (1 + λ) Evolutionary Algorithm with Self-Adjusting Mutation Rate. In: Algorithmica. 2018 ; Vol. 81, No. 2. pp. 593–631.
@article{9da771a62ba84331992a7bb724df2a6f,
title = "The (1 + λ) Evolutionary Algorithm with Self-Adjusting Mutation Rate",
abstract = "We propose a new way to self-adjust the mutation rate in population-based evolutionary algorithms in discrete search spaces. Roughly speaking, it consists of creating half the offspring with a mutation rate that is twice the current mutation rate and the other half with half the current rate. The mutation rate is then updated to the rate used in that subpopulation which contains the best offspring. We analyze how the (1 + λ) evolutionary algorithm with this self-adjusting mutation rate optimizes the OneMax test function. We prove that this dynamic version of the (1 + λ) EA finds the optimum in an expected optimization time (number of fitness evaluations) of O(nλ/ log λ+ nlog n). This time is asymptotically smaller than the optimization time of the classic (1 + λ) EA. Previous work shows that this performance is best-possible among all λ-parallel mutation-based unbiased black-box algorithms. This result shows that the new way of adjusting the mutation rate can find optimal dynamic parameter values on the fly. Since our adjustment mechanism is simpler than the ones previously used for adjusting the mutation rate and does not have parameters itself, we are optimistic that it will find other applications.",
keywords = "Evolutionary computation, Mutation, Runtime analysis, Self-adaptation",
author = "Benjamin Doerr and Christian Gie{\ss}en and Carsten Witt and Jing Yang",
year = "2018",
month = "1",
day = "1",
doi = "10.1007/s00453-018-0502-x",
language = "English",
volume = "81",
pages = "593–631",
journal = "Algorithmica",
issn = "0178-4617",
publisher = "Springer New York",
number = "2",

}

The (1 + λ) Evolutionary Algorithm with Self-Adjusting Mutation Rate. / Doerr, Benjamin; Gießen, Christian; Witt, Carsten; Yang, Jing.

In: Algorithmica, Vol. 81, No. 2, 01.01.2018, p. 593–631.

Research output: Contribution to journalJournal articleResearchpeer-review

TY - JOUR

T1 - The (1 + λ) Evolutionary Algorithm with Self-Adjusting Mutation Rate

AU - Doerr, Benjamin

AU - Gießen, Christian

AU - Witt, Carsten

AU - Yang, Jing

PY - 2018/1/1

Y1 - 2018/1/1

N2 - We propose a new way to self-adjust the mutation rate in population-based evolutionary algorithms in discrete search spaces. Roughly speaking, it consists of creating half the offspring with a mutation rate that is twice the current mutation rate and the other half with half the current rate. The mutation rate is then updated to the rate used in that subpopulation which contains the best offspring. We analyze how the (1 + λ) evolutionary algorithm with this self-adjusting mutation rate optimizes the OneMax test function. We prove that this dynamic version of the (1 + λ) EA finds the optimum in an expected optimization time (number of fitness evaluations) of O(nλ/ log λ+ nlog n). This time is asymptotically smaller than the optimization time of the classic (1 + λ) EA. Previous work shows that this performance is best-possible among all λ-parallel mutation-based unbiased black-box algorithms. This result shows that the new way of adjusting the mutation rate can find optimal dynamic parameter values on the fly. Since our adjustment mechanism is simpler than the ones previously used for adjusting the mutation rate and does not have parameters itself, we are optimistic that it will find other applications.

AB - We propose a new way to self-adjust the mutation rate in population-based evolutionary algorithms in discrete search spaces. Roughly speaking, it consists of creating half the offspring with a mutation rate that is twice the current mutation rate and the other half with half the current rate. The mutation rate is then updated to the rate used in that subpopulation which contains the best offspring. We analyze how the (1 + λ) evolutionary algorithm with this self-adjusting mutation rate optimizes the OneMax test function. We prove that this dynamic version of the (1 + λ) EA finds the optimum in an expected optimization time (number of fitness evaluations) of O(nλ/ log λ+ nlog n). This time is asymptotically smaller than the optimization time of the classic (1 + λ) EA. Previous work shows that this performance is best-possible among all λ-parallel mutation-based unbiased black-box algorithms. This result shows that the new way of adjusting the mutation rate can find optimal dynamic parameter values on the fly. Since our adjustment mechanism is simpler than the ones previously used for adjusting the mutation rate and does not have parameters itself, we are optimistic that it will find other applications.

KW - Evolutionary computation

KW - Mutation

KW - Runtime analysis

KW - Self-adaptation

U2 - 10.1007/s00453-018-0502-x

DO - 10.1007/s00453-018-0502-x

M3 - Journal article

AN - SCOPUS:85053191860

VL - 81

SP - 593

EP - 631

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 2

ER -