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

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationGECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference
PublisherAssociation for Computing Machinery, Inc
Pages301-308
Number of pages8
ISBN (Electronic)9781450356183
DOIs
StatePublished - Jul 2 2018
Event2018 Genetic and Evolutionary Computation Conference, GECCO 2018 - Kyoto, Japan
Duration: Jul 15 2018Jul 19 2018

Publication series

NameGECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference

Other

Other2018 Genetic and Evolutionary Computation Conference, GECCO 2018
CountryJapan
CityKyoto
Period7/15/187/19/18

Keywords

  • Combinatorial optimization
  • Deceptive attractors
  • Restart strategy

Fingerprint Dive into the research topics of 'Improving the run time of the (1 + 1) evolutionary algorithm with luby sequences'. Together they form a unique fingerprint.

Cite this