Population Size vs. Mutation Strength for the (1+λ) EA on OneMax

Christian Gießen; Carsten Witt

doi:10.1145/2739480.2754738

Population Size vs. Mutation Strength for the (1+λ) EA on OneMax

Christian Gießen, Carsten Witt

Department of Applied Mathematics and Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Abstract

The (1+1) EA with mutation probability c/n, where c>0 is an arbitrary constant, is studied for the classical OneMax function. Its expected optimization time is analyzed exactly (up to lower order terms) as a function of c and λ. It turns out that 1/n is the only optimal mutation probability if λ=o(ln n ln ln n/ln ln ln n), which is the cut-off point for linear mnspeed-up. However, if λ is above this cut-off point then the standard mutation probability 1/n is no longer the only optimal choice. Instead, the expected number of generations is (up to lower order terms) independent of c, irrespectively of it being less than 1 or greater. The results are obtained by a careful study of order statistics of the binomial distribution and variable drift theorems for upper and lower bounds.

Original language	English
Title of host publication	Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '15)
Publisher	Association for Computing Machinery
Publication date	2015
Pages	1439-1446
ISBN (Print)	978-1-4503-3472-3
DOIs	https://doi.org/10.1145/2739480.2754738
Publication status	Published - 2015
Event	2015 Genetic and Evolutionary Computation Conference - Madrid, Spain Duration: 11 Jul 2015 → 15 Jul 2015 http://www.sigevo.org/gecco-2015/

Conference

Conference	2015 Genetic and Evolutionary Computation Conference
Country/Territory	Spain
City	Madrid
Period	11/07/2015 → 15/07/2015
Internet address	http://www.sigevo.org/gecco-2015/

Keywords

Runtime Analysis
Populations
Mutation

Access to Document

10.1145/2739480.2754738

OpenUrl availability

Full text

Cite this

@inproceedings{33f07b391ee446e497f70c6bb8ff8dd0,

title = "Population Size vs. Mutation Strength for the (1+λ) EA on OneMax",

abstract = "The (1+1) EA with mutation probability c/n, where c>0 is an arbitrary constant, is studied for the classical OneMax function. Its expected optimization time is analyzed exactly (up to lower order terms) as a function of c and λ. It turns out that 1/n is the only optimal mutation probability if λ=o(ln n ln ln n/ln ln ln n), which is the cut-off point for linear mnspeed-up. However, if λ is above this cut-off point then the standard mutation probability 1/n is no longer the only optimal choice. Instead, the expected number of generations is (up to lower order terms) independent of c, irrespectively of it being less than 1 or greater. The results are obtained by a careful study of order statistics of the binomial distribution and variable drift theorems for upper and lower bounds. ",

keywords = "Runtime Analysis, Populations, Mutation",

author = "Christian Gie{\ss}en and Carsten Witt",

year = "2015",

doi = "10.1145/2739480.2754738",

language = "English",

isbn = "978-1-4503-3472-3",

pages = "1439--1446",

booktitle = "Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '15)",

publisher = "Association for Computing Machinery",

address = "United States",

note = "2015 Genetic and Evolutionary Computation Conference, GECCO 2015 ; Conference date: 11-07-2015 Through 15-07-2015",

url = "http://www.sigevo.org/gecco-2015/",

}

TY - GEN

T1 - Population Size vs. Mutation Strength for the (1+λ) EA on OneMax

AU - Gießen, Christian

AU - Witt, Carsten

PY - 2015

Y1 - 2015

N2 - The (1+1) EA with mutation probability c/n, where c>0 is an arbitrary constant, is studied for the classical OneMax function. Its expected optimization time is analyzed exactly (up to lower order terms) as a function of c and λ. It turns out that 1/n is the only optimal mutation probability if λ=o(ln n ln ln n/ln ln ln n), which is the cut-off point for linear mnspeed-up. However, if λ is above this cut-off point then the standard mutation probability 1/n is no longer the only optimal choice. Instead, the expected number of generations is (up to lower order terms) independent of c, irrespectively of it being less than 1 or greater. The results are obtained by a careful study of order statistics of the binomial distribution and variable drift theorems for upper and lower bounds.

AB - The (1+1) EA with mutation probability c/n, where c>0 is an arbitrary constant, is studied for the classical OneMax function. Its expected optimization time is analyzed exactly (up to lower order terms) as a function of c and λ. It turns out that 1/n is the only optimal mutation probability if λ=o(ln n ln ln n/ln ln ln n), which is the cut-off point for linear mnspeed-up. However, if λ is above this cut-off point then the standard mutation probability 1/n is no longer the only optimal choice. Instead, the expected number of generations is (up to lower order terms) independent of c, irrespectively of it being less than 1 or greater. The results are obtained by a careful study of order statistics of the binomial distribution and variable drift theorems for upper and lower bounds.

KW - Runtime Analysis

KW - Populations

KW - Mutation

U2 - 10.1145/2739480.2754738

DO - 10.1145/2739480.2754738

M3 - Article in proceedings

SN - 978-1-4503-3472-3

SP - 1439

EP - 1446

BT - Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '15)

PB - Association for Computing Machinery

T2 - 2015 Genetic and Evolutionary Computation Conference

Y2 - 11 July 2015 through 15 July 2015

ER -

Population Size vs. Mutation Strength for the (1+λ) EA on OneMax

Abstract

Conference

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this