The 1/5-th rule with rollbacks: on self-adjustment of the population size in the (1 + (λ, λ)) GA

A. O. Bassin; Maxim Buzdalov

doi:10.1145/3319619.3322067

The 1/5-th rule with rollbacks: on self-adjustment of the population size in the (1 + (λ, λ)) GA

A. O. Bassin, Maxim Buzdalov

ITMO University

Research output: Chapter in Book/Report/Conference proceeding › Conference Proceeding (Non-Journal item)

11 Citations (Scopus)

Abstract

Self-adjustment of parameters can significantly improve the performance of evolutionary algorithms. A notable example is the (1 + (λ, λ)) genetic algorithm, where the adaptation of the population size helps to achieve the linear runtime on the OneMax problem. However, on problems which interact badly with the self-adjustment procedure, its usage can lead to performance degradation compared to static parameter choices. In particular, the one fifth rule is able to raise the population size too fast on problems which are too far away from the perfect fitness-distance correlation.

We propose a modification of the one fifth rule in order to have less negative impact in scenarios when the original rule reduces the performance. Our modification, while still having a good performance on OneMax, both theoretically and in practice, also shows better results on linear functions with random weights and on random satisfiable MAX-SAT instances.

Original language	English
Title of host publication	GECCO '19
Subtitle of host publication	Proceedings of the Genetic and Evolutionary Computation Conference Companion
Editors	Manuel López-Ibáñez
Publisher	Association for Computing Machinery
Pages	277-278
Number of pages	2
ISBN (Print)	978-1-4503-6748-6, 1450367488
DOIs	https://doi.org/10.1145/3319619.3322067
Publication status	Published - 13 Jul 2019
Externally published	Yes
Event	GECCO 2019: The Genetic and Evolutionary Computation Conference - Prague, Czech Republic Duration: 13 Jul 2019 → 17 Jul 2019 https://gecco-2019.sigevo.org

Conference

Conference	GECCO 2019: The Genetic and Evolutionary Computation Conference
Country/Territory	Czech Republic
City	Prague
Period	13 Jul 2019 → 17 Jul 2019
Internet address	https://gecco-2019.sigevo.org

Keywords

(1 + (λ,λ)) ga
linear functions
max-sat
parameter adaptation

Access to Document

10.1145/3319619.3322067

Permanent link

Persistent link

Cite this

@inproceedings{490addb324c84d468a792e0d9a4c8d79,

title = "The 1/5-th rule with rollbacks: on self-adjustment of the population size in the (1 + (λ, λ)) GA",

abstract = "Self-adjustment of parameters can significantly improve the performance of evolutionary algorithms. A notable example is the (1 + (λ, λ)) genetic algorithm, where the adaptation of the population size helps to achieve the linear runtime on the OneMax problem. However, on problems which interact badly with the self-adjustment procedure, its usage can lead to performance degradation compared to static parameter choices. In particular, the one fifth rule is able to raise the population size too fast on problems which are too far away from the perfect fitness-distance correlation.We propose a modification of the one fifth rule in order to have less negative impact in scenarios when the original rule reduces the performance. Our modification, while still having a good performance on OneMax, both theoretically and in practice, also shows better results on linear functions with random weights and on random satisfiable MAX-SAT instances.",

keywords = "(1 + (λ,λ)) ga, linear functions, max-sat, parameter adaptation",

author = "Bassin, {A. O.} and Maxim Buzdalov",

year = "2019",

month = jul,

day = "13",

doi = "10.1145/3319619.3322067",

language = "English",

isbn = "978-1-4503-6748-6",

pages = "277--278",

editor = "L{\'o}pez-Ib{\'a}{\~n}ez, {Manuel }",

booktitle = "GECCO '19",

publisher = "Association for Computing Machinery",

address = "United States of America",

note = "GECCO 2019: The Genetic and Evolutionary Computation Conference ; Conference date: 13-07-2019 Through 17-07-2019",

url = "https://gecco-2019.sigevo.org",

}

Bassin, AO & Buzdalov, M 2019, The 1/5-th rule with rollbacks: on self-adjustment of the population size in the (1 + (λ, λ)) GA. in M López-Ibáñez (ed.), GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference Companion. Association for Computing Machinery, pp. 277-278, GECCO 2019: The Genetic and Evolutionary Computation Conference, Prague, Czech Republic, 13 Jul 2019. https://doi.org/10.1145/3319619.3322067

The 1/5-th rule with rollbacks: on self-adjustment of the population size in the (1 + (λ, λ)) GA. / Bassin, A. O.; Buzdalov, Maxim.
GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference Companion. ed. / Manuel López-Ibáñez. Association for Computing Machinery, 2019. p. 277-278.

Research output: Chapter in Book/Report/Conference proceeding › Conference Proceeding (Non-Journal item)

TY - GEN

T1 - The 1/5-th rule with rollbacks: on self-adjustment of the population size in the (1 + (λ, λ)) GA

AU - Bassin, A. O.

AU - Buzdalov, Maxim

PY - 2019/7/13

Y1 - 2019/7/13

N2 - Self-adjustment of parameters can significantly improve the performance of evolutionary algorithms. A notable example is the (1 + (λ, λ)) genetic algorithm, where the adaptation of the population size helps to achieve the linear runtime on the OneMax problem. However, on problems which interact badly with the self-adjustment procedure, its usage can lead to performance degradation compared to static parameter choices. In particular, the one fifth rule is able to raise the population size too fast on problems which are too far away from the perfect fitness-distance correlation.We propose a modification of the one fifth rule in order to have less negative impact in scenarios when the original rule reduces the performance. Our modification, while still having a good performance on OneMax, both theoretically and in practice, also shows better results on linear functions with random weights and on random satisfiable MAX-SAT instances.

AB - Self-adjustment of parameters can significantly improve the performance of evolutionary algorithms. A notable example is the (1 + (λ, λ)) genetic algorithm, where the adaptation of the population size helps to achieve the linear runtime on the OneMax problem. However, on problems which interact badly with the self-adjustment procedure, its usage can lead to performance degradation compared to static parameter choices. In particular, the one fifth rule is able to raise the population size too fast on problems which are too far away from the perfect fitness-distance correlation.We propose a modification of the one fifth rule in order to have less negative impact in scenarios when the original rule reduces the performance. Our modification, while still having a good performance on OneMax, both theoretically and in practice, also shows better results on linear functions with random weights and on random satisfiable MAX-SAT instances.

KW - (1 + (λ,λ)) ga

KW - linear functions

KW - max-sat

KW - parameter adaptation

UR - http://arxiv.org/abs/1904.07284

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85070613890&origin=resultslist

U2 - 10.1145/3319619.3322067

DO - 10.1145/3319619.3322067

M3 - Conference Proceeding (Non-Journal item)

SN - 978-1-4503-6748-6

SN - 1450367488

SP - 277

EP - 278

BT - GECCO '19

A2 - López-Ibáñez, Manuel

PB - Association for Computing Machinery

T2 - GECCO 2019: The Genetic and Evolutionary Computation Conference

Y2 - 13 July 2019 through 17 July 2019

ER -

The 1/5-th rule with rollbacks: on self-adjustment of the population size in the (1 + (λ, λ)) GA

Abstract

Conference

Keywords

Access to Document

Permanent link

Other files and links

Fingerprint

Cite this