Cited By
View all- Lorenz J(2021)Restart Strategies in a Continuous SettingTheory of Computing Systems10.1007/s00224-021-10041-065:8(1143-1164)Online publication date: 1-Nov-2021
Improving the run time of the (1 + 1) evolutionary algorithm with luby sequences
Pages 301 - 308
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.
References
[1]
Axel de Perthuis de Laillevault, Benjamin Doerr, and Carola Doerr. 2015. Money for Nothing: Speeding Up Evolutionary Algorithms Through Better Initialization. In Proc. of GECCO '15. 815--822.
[2]
Stefan Droste, Thomas Jansen, and Ingo Wegener. 2002. On the analysis of the (1+1) evolutionary algorithm. Theoretical Computer Science 276, 1--2 (2002), 51--81.
[3]
Matteo Fischetti and Michele Monaci. 2014. Exploiting Erraticism in Search. Operations Research 62, 1 (2014), 114--122.
[4]
Tobias Friedrich, Timo Kötzing, and Markus Wagner. 2017. A Generic Bet-and-Run Strategy for Speeding Up Stochastic Local Search. In Proc. of AAAI. 801--807.
[5]
Tobias Friedrich, Pietro Simone Oliveto, Dirk Sudholt, and Carsten Witt. 2009. Analysis of Diversity-Preserving Mechanisms for Global Exploration. Evolutionary Computation 17, 4 (2009), 455--476.
[6]
Alex S. Fukunaga. 1998. Restart Scheduling for Genetic Algorithms. In Proc. of PPSN. 357--366.
[7]
András György and Levente Kocsis. 2011. Efficient Multi-Start Strategies for Local Search Algorithms. Journal of Artificial Intelligence Research 41 (2011). 407--444.
[8]
Jun He, Xin Yao, and Jin Li. 2005. A comparative study of three evolutionary algorithms incorporating different amounts of domain knowledge for node covering problem. IEEE Trans. Systems, Man, and Cybernetics, Part C 35, 2 (2005). 266--271.
[9]
Xiaohua Hu, Ronald Shonkwiler, and Marcus C. Spruill. 1994. Random restarts in global optimization. Technical Report 110592-015. School of Mathematics. Georgia Institute of Technology.
[10]
Sami Khuri and Thomas Bäck. 1994. An Evolutionary Heuristic for the Minimum Vertex Cover Problem. In Proc. KI-94 Workshop Genetic Algorithms Within Framework Evol. Comput. 86--90.
[11]
Timo Kötzing, Dirk Sudholt, and Madeleine Theile. 2011. How crossover helps in pseudo-boolean optimization. In Proc. of GECCO. 989--996.
[12]
Jure Leskovec and Julian J. Mcauley. 2012. Learning to Discover Social Circles in Ego Networks. In Proc. of NIPS. 539--547.
[13]
Andrei Lissovoi, Dirk Sudholt, Markus Wagner, and Christine Zarges. 2017. Theoretical Results on Bet-and-run As an Initialisation Strategy. In Proc. of GECCO. 857--864.
[14]
Helena Ramalhinho Lourenço, Oliver C. Martin, and Thomas Stützle. 2003. Iterated Local Search. 320--353.
[15]
Michael Luby, Alistair Sinclair, and David Zuckerman. 1993. Optimal Speedup of Las Vegas Algorithms. Inform. Process. Lett. 47, 4 (1993), 173--180.
[16]
Sean Luke. 2001. When Short Runs Beat Long Runs. In Proc. of GECCO. 74--80.
[17]
Malik Magdon-Ismail and Amir F. Atiya. 2000. The Early Restart Algorithm. Neural Computation 12, 6 (2000), 1303--1312.
[18]
Heinz Mühlenbein. 1992. How Genetic Algorithms Really Work: Mutation and Hillclimbing. In Proc. of PPSN-II. 15--26.
[19]
Pietro Simone Oliveto, Jun He, and Xin Yao. 2009. Analysis of the (1+1) -EA for Finding Approximate Solutions to Vertex Cover Problems. IEEE Trans. Evolutionary Computation 13, 5 (2009), 1006--1029.
[20]
Carsten Witt. 2005. Worst-Case and Average-Case Approximations by Simple Randomized Search Heuristics. In Proc. of STACS. 44--56.
Index Terms
- Improving the run time of the (1 + 1) evolutionary algorithm with luby sequences
Recommendations
The ($$1+\lambda $$1+ý) Evolutionary Algorithm with Self-Adjusting Mutation Rate
We propose a new way to self-adjust the mutation rate in population-based evolutionary algorithms in discrete search spaces. Roughly speaking, it consists of creating half the offspring with a mutation rate that is twice the current mutation rate and ...
A novel quantum-inspired evolutionary algorithm for solving combinatorial optimization problems
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computationIn this paper, we propose a novel quantum-inspired evolutionary algorithm, called NQEA, for solving combinatorial optimization problems. NQEA uses a new Q-bit update operator to increase the balance between the exploration and exploitation of the search ...
Analysis of speedups in parallel evolutionary algorithms and ( 1 + λ ) EAs for combinatorial optimization
Evolutionary algorithms are popular heuristics for solving various combinatorial problems as they are easy to apply and often produce good results. Island models parallelize evolution by using different populations, called islands, which are connected ...
Comments
Information & Contributors
Information
Published In
July 2018
1578 pages
Copyright © 2018 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 02 July 2018
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- Swenson College of Science and Engineering, University of Minnesota Duluth
- Hasso Plattner Institute
Conference
GECCO '18
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 100Total Downloads
- Downloads (Last 12 months)6
- Downloads (Last 6 weeks)0
Reflects downloads up to 16 Jan 2025
Other Metrics
Citations
Cited By
View all- Lorenz J(2021)Restart Strategies in a Continuous SettingTheory of Computing Systems10.1007/s00224-021-10041-065:8(1143-1164)Online publication date: 1-Nov-2021
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in