Speeding up evolutionary algorithms through restricted mutation operators

Benjamin Doerr; Nils Hebbinghaus; Frank Neumann

doi:10.1007/11844297_99

Speeding up evolutionary algorithms through restricted mutation operators

Benjamin Doerr
, Nils Hebbinghaus
, Frank Neumann

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

Abstract

We investigate the effect of restricting the mutation operator in evolutionary algorithms with respect to the runtime behavior. For the Eulerian cycle problem; we present runtime bounds on evolutionary algorithms with a restricted operator that are much smaller than the best upper bounds for the general case. It turns out that a plateau that both algorithms have to cope with is left faster by the new algorithm. In addition, we present a lower bound for the unrestricted algorithm which shows that the restricted operator speeds up computation by at least a linear factor.

Original language	English
Title of host publication	Parallel Problem Solving from Nature, PPSN IX - 9th International Conference, Procedings
Publisher	Springer Verlag
Pages	978-987
Number of pages	10
ISBN (Print)	3540389903, 9783540389903
DOIs	https://doi.org/10.1007/11844297_99
Publication status	Published - 1 Jan 2006
Externally published	Yes
Event	9th International Conference on Parallel Problem Solving from Nature, PPSN IX - Reykjavik, Iceland Duration: 9 Sept 2006 → 13 Sept 2006

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4193 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	9th International Conference on Parallel Problem Solving from Nature, PPSN IX
Country/Territory	Iceland
City	Reykjavik
Period	9/09/06 → 13/09/06

Access to Document

10.1007/11844297_99

Cite this

Doerr, B., Hebbinghaus, N., & Neumann, F. (2006). Speeding up evolutionary algorithms through restricted mutation operators. In Parallel Problem Solving from Nature, PPSN IX - 9th International Conference, Procedings (pp. 978-987). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4193 LNCS). Springer Verlag. https://doi.org/10.1007/11844297_99

Doerr, Benjamin ; Hebbinghaus, Nils ; Neumann, Frank. / Speeding up evolutionary algorithms through restricted mutation operators. Parallel Problem Solving from Nature, PPSN IX - 9th International Conference, Procedings. Springer Verlag, 2006. pp. 978-987 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{48e84c1d44c4464f9871b945c1d821f5,

title = "Speeding up evolutionary algorithms through restricted mutation operators",

abstract = "We investigate the effect of restricting the mutation operator in evolutionary algorithms with respect to the runtime behavior. For the Eulerian cycle problem; we present runtime bounds on evolutionary algorithms with a restricted operator that are much smaller than the best upper bounds for the general case. It turns out that a plateau that both algorithms have to cope with is left faster by the new algorithm. In addition, we present a lower bound for the unrestricted algorithm which shows that the restricted operator speeds up computation by at least a linear factor.",

author = "Benjamin Doerr and Nils Hebbinghaus and Frank Neumann",

year = "2006",

month = jan,

day = "1",

doi = "10.1007/11844297\_99",

language = "English",

isbn = "3540389903",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "978--987",

booktitle = "Parallel Problem Solving from Nature, PPSN IX - 9th International Conference, Procedings",

note = "9th International Conference on Parallel Problem Solving from Nature, PPSN IX ; Conference date: 09-09-2006 Through 13-09-2006",

}

Doerr, B, Hebbinghaus, N & Neumann, F 2006, Speeding up evolutionary algorithms through restricted mutation operators. in Parallel Problem Solving from Nature, PPSN IX - 9th International Conference, Procedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4193 LNCS, Springer Verlag, pp. 978-987, 9th International Conference on Parallel Problem Solving from Nature, PPSN IX, Reykjavik, Iceland, 9/09/06. https://doi.org/10.1007/11844297_99

Speeding up evolutionary algorithms through restricted mutation operators. / Doerr, Benjamin; Hebbinghaus, Nils; Neumann, Frank.
Parallel Problem Solving from Nature, PPSN IX - 9th International Conference, Procedings. Springer Verlag, 2006. p. 978-987 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4193 LNCS).

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

TY - GEN

T1 - Speeding up evolutionary algorithms through restricted mutation operators

AU - Doerr, Benjamin

AU - Hebbinghaus, Nils

AU - Neumann, Frank

PY - 2006/1/1

Y1 - 2006/1/1

N2 - We investigate the effect of restricting the mutation operator in evolutionary algorithms with respect to the runtime behavior. For the Eulerian cycle problem; we present runtime bounds on evolutionary algorithms with a restricted operator that are much smaller than the best upper bounds for the general case. It turns out that a plateau that both algorithms have to cope with is left faster by the new algorithm. In addition, we present a lower bound for the unrestricted algorithm which shows that the restricted operator speeds up computation by at least a linear factor.

AB - We investigate the effect of restricting the mutation operator in evolutionary algorithms with respect to the runtime behavior. For the Eulerian cycle problem; we present runtime bounds on evolutionary algorithms with a restricted operator that are much smaller than the best upper bounds for the general case. It turns out that a plateau that both algorithms have to cope with is left faster by the new algorithm. In addition, we present a lower bound for the unrestricted algorithm which shows that the restricted operator speeds up computation by at least a linear factor.

U2 - 10.1007/11844297_99

DO - 10.1007/11844297_99

M3 - Conference contribution

AN - SCOPUS:33750226315

SN - 3540389903

SN - 9783540389903

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 978

EP - 987

BT - Parallel Problem Solving from Nature, PPSN IX - 9th International Conference, Procedings

PB - Springer Verlag

T2 - 9th International Conference on Parallel Problem Solving from Nature, PPSN IX

Y2 - 9 September 2006 through 13 September 2006

ER -

Doerr B, Hebbinghaus N, Neumann F. Speeding up evolutionary algorithms through restricted mutation operators. In Parallel Problem Solving from Nature, PPSN IX - 9th International Conference, Procedings. Springer Verlag. 2006. p. 978-987. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/11844297_99

Speeding up evolutionary algorithms through restricted mutation operators

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this