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 language||English (US)|
|Title of host publication||GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference|
|Publisher||Association for Computing Machinery, Inc|
|Number of pages||8|
|State||Published - Jul 2 2018|
|Event||2018 Genetic and Evolutionary Computation Conference, GECCO 2018 - Kyoto, Japan|
Duration: Jul 15 2018 → Jul 19 2018
|Name||GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference|
|Other||2018 Genetic and Evolutionary Computation Conference, GECCO 2018|
|Period||7/15/18 → 7/19/18|
Bibliographical noteFunding Information:
The research leading to these results has received funding from the German Science Foundation (DFG) under grant agreement FR 2988 (TOSU).
© 2018 Copyright held by the owner/author(s).
- Combinatorial optimization
- Deceptive attractors
- Restart strategy