Improving the run time of the (1 + 1) evolutionary algorithm with luby sequences

Tobias Friedrich; Francesco Quinzan; Timo Kötzing; Andrew M. Sutton

doi:10.1145/3205455.3205525

Improving the run time of the (1 + 1) evolutionary algorithm with luby sequences

Tobias Friedrich, Francesco Quinzan, Timo Kötzing, Andrew M. Sutton

Computer Science (Duluth)

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

1 Scopus citations

Abstract

In the context of black box optimization, one of the most common ways to handle deceptive attractors is to periodically restart the algorithm. In this paper, we explore the benefits of combining the simple (1+1) Evolutionary Algorithm (EA) with the Luby Universal Strategy - the (1 + 1) EA_U , a meta-heuristic that does not require parameter tuning. We first consider two artificial pseudo-Boolean landscapes, on which the (1 + 1) EA exhibits exponential run time. We prove that the (1 + 1) EA_U has polynomial run time on both instances. We then consider the Minimum Vertex Cover on two classes of graphs. Again, the (1 + 1) EA yields exponential run time on those instances, and the (1 + 1) EA_U finds the global optimum in polynomial time. We conclude by studying the Makespan Scheduling. We consider an instance on which the (1 + 1) EA does not find a (4/3 − )- approximation in polynomial time, and we show that the (1 + 1) EA_U reaches a (4/3 −)-approximation in polynomial time. We then prove that the (1 + 1) EA_U serves as an Efficient Polynomial-time Approximation Scheme (EPTAS) for the Partition Problem, for a (1 +)-approximation with > 4/n.

Original language	English (US)
Title of host publication	GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference
Publisher	Association for Computing Machinery, Inc
Pages	301-308
Number of pages	8
ISBN (Electronic)	9781450356183
DOIs	https://doi.org/10.1145/3205455.3205525
State	Published - Jul 2 2018
Event	2018 Genetic and Evolutionary Computation Conference, GECCO 2018 - Kyoto, Japan Duration: Jul 15 2018 → Jul 19 2018

Publication series

Name	GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference

Other

Other	2018 Genetic and Evolutionary Computation Conference, GECCO 2018
Country/Territory	Japan
City	Kyoto
Period	7/15/18 → 7/19/18

Bibliographical note

Funding Information:
The research leading to these results has received funding from the German Science Foundation (DFG) under grant agreement FR 2988 (TOSU).

Publisher Copyright:
© 2018 Copyright held by the owner/author(s).

Keywords

Combinatorial optimization
Deceptive attractors
Restart strategy

Access

10.1145/3205455.3205525

OpenUrl availability

Full text

Cite this

Friedrich, T., Quinzan, F., Kötzing, T., & Sutton, A. M. (2018). Improving the run time of the (1 + 1) evolutionary algorithm with luby sequences. In GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference (pp. 301-308). (GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference). Association for Computing Machinery, Inc. https://doi.org/10.1145/3205455.3205525

Improving the run time of the (1 + 1) evolutionary algorithm with luby sequences. / Friedrich, Tobias; Quinzan, Francesco; Kötzing, Timo et al.
GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference. Association for Computing Machinery, Inc, 2018. p. 301-308 (GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference).

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

Friedrich, T, Quinzan, F, Kötzing, T & Sutton, AM 2018, Improving the run time of the (1 + 1) evolutionary algorithm with luby sequences. in GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference. GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference, Association for Computing Machinery, Inc, pp. 301-308, 2018 Genetic and Evolutionary Computation Conference, GECCO 2018, Kyoto, Japan, 7/15/18. https://doi.org/10.1145/3205455.3205525

Friedrich T, Quinzan F, Kötzing T, Sutton AM. Improving the run time of the (1 + 1) evolutionary algorithm with luby sequences. In GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference. Association for Computing Machinery, Inc. 2018. p. 301-308. (GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference). doi: 10.1145/3205455.3205525

Friedrich, Tobias ; Quinzan, Francesco ; Kötzing, Timo et al. / Improving the run time of the (1 + 1) evolutionary algorithm with luby sequences. GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference. Association for Computing Machinery, Inc, 2018. pp. 301-308 (GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference).

@inproceedings{1e6803c5e6e14bf0a4db29e52223635d,

title = "Improving the run time of the (1 + 1) evolutionary algorithm with luby sequences",

abstract = "In the context of black box optimization, one of the most common ways to handle deceptive attractors is to periodically restart the algorithm. In this paper, we explore the benefits of combining the simple (1+1) Evolutionary Algorithm (EA) with the Luby Universal Strategy - the (1 + 1) EAU , a meta-heuristic that does not require parameter tuning. We first consider two artificial pseudo-Boolean landscapes, on which the (1 + 1) EA exhibits exponential run time. We prove that the (1 + 1) EAU has polynomial run time on both instances. We then consider the Minimum Vertex Cover on two classes of graphs. Again, the (1 + 1) EA yields exponential run time on those instances, and the (1 + 1) EAU finds the global optimum in polynomial time. We conclude by studying the Makespan Scheduling. We consider an instance on which the (1 + 1) EA does not find a (4/3 − )- approximation in polynomial time, and we show that the (1 + 1) EAU reaches a (4/3 −)-approximation in polynomial time. We then prove that the (1 + 1) EAU serves as an Efficient Polynomial-time Approximation Scheme (EPTAS) for the Partition Problem, for a (1 +)-approximation with > 4/n.",

keywords = "Combinatorial optimization, Deceptive attractors, Restart strategy",

author = "Tobias Friedrich and Francesco Quinzan and Timo K{\"o}tzing and Sutton, {Andrew M.}",

note = "Funding Information: The research leading to these results has received funding from the German Science Foundation (DFG) under grant agreement FR 2988 (TOSU). Publisher Copyright: {\textcopyright} 2018 Copyright held by the owner/author(s).; 2018 Genetic and Evolutionary Computation Conference, GECCO 2018 ; Conference date: 15-07-2018 Through 19-07-2018",

year = "2018",

month = jul,

day = "2",

doi = "10.1145/3205455.3205525",

language = "English (US)",

series = "GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference",

publisher = "Association for Computing Machinery, Inc",

pages = "301--308",

booktitle = "GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference",

}

TY - GEN

T1 - Improving the run time of the (1 + 1) evolutionary algorithm with luby sequences

AU - Friedrich, Tobias

AU - Quinzan, Francesco

AU - Kötzing, Timo

AU - Sutton, Andrew M.

N1 - Funding Information: The research leading to these results has received funding from the German Science Foundation (DFG) under grant agreement FR 2988 (TOSU). Publisher Copyright: © 2018 Copyright held by the owner/author(s).

PY - 2018/7/2

Y1 - 2018/7/2

N2 - In the context of black box optimization, one of the most common ways to handle deceptive attractors is to periodically restart the algorithm. In this paper, we explore the benefits of combining the simple (1+1) Evolutionary Algorithm (EA) with the Luby Universal Strategy - the (1 + 1) EAU , a meta-heuristic that does not require parameter tuning. We first consider two artificial pseudo-Boolean landscapes, on which the (1 + 1) EA exhibits exponential run time. We prove that the (1 + 1) EAU has polynomial run time on both instances. We then consider the Minimum Vertex Cover on two classes of graphs. Again, the (1 + 1) EA yields exponential run time on those instances, and the (1 + 1) EAU finds the global optimum in polynomial time. We conclude by studying the Makespan Scheduling. We consider an instance on which the (1 + 1) EA does not find a (4/3 − )- approximation in polynomial time, and we show that the (1 + 1) EAU reaches a (4/3 −)-approximation in polynomial time. We then prove that the (1 + 1) EAU serves as an Efficient Polynomial-time Approximation Scheme (EPTAS) for the Partition Problem, for a (1 +)-approximation with > 4/n.

AB - In the context of black box optimization, one of the most common ways to handle deceptive attractors is to periodically restart the algorithm. In this paper, we explore the benefits of combining the simple (1+1) Evolutionary Algorithm (EA) with the Luby Universal Strategy - the (1 + 1) EAU , a meta-heuristic that does not require parameter tuning. We first consider two artificial pseudo-Boolean landscapes, on which the (1 + 1) EA exhibits exponential run time. We prove that the (1 + 1) EAU has polynomial run time on both instances. We then consider the Minimum Vertex Cover on two classes of graphs. Again, the (1 + 1) EA yields exponential run time on those instances, and the (1 + 1) EAU finds the global optimum in polynomial time. We conclude by studying the Makespan Scheduling. We consider an instance on which the (1 + 1) EA does not find a (4/3 − )- approximation in polynomial time, and we show that the (1 + 1) EAU reaches a (4/3 −)-approximation in polynomial time. We then prove that the (1 + 1) EAU serves as an Efficient Polynomial-time Approximation Scheme (EPTAS) for the Partition Problem, for a (1 +)-approximation with > 4/n.

KW - Combinatorial optimization

KW - Deceptive attractors

KW - Restart strategy

UR - http://www.scopus.com/inward/record.url?scp=85050633974&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85050633974&partnerID=8YFLogxK

U2 - 10.1145/3205455.3205525

DO - 10.1145/3205455.3205525

M3 - Conference contribution

AN - SCOPUS:85050633974

T3 - GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference

SP - 301

EP - 308

BT - GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference

PB - Association for Computing Machinery, Inc

T2 - 2018 Genetic and Evolutionary Computation Conference, GECCO 2018

Y2 - 15 July 2018 through 19 July 2018

ER -

Improving the run time of the (1 + 1) evolutionary algorithm with luby sequences

Abstract

Publication series

Other

Bibliographical note

Keywords

Access

OpenUrl availability

Other files and links

Fingerprint

Cite this