Improving the run time of the (1 + 1) evolutionary algorithm with luby sequences
| Autor: | Francesco Quinzan, Tobias Friedrich, Andrew M. Sutton, Timo Kötzing |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
021103 operations research
Job shop scheduling 0211 other engineering and technologies Partition problem Evolutionary algorithm Vertex cover 02 engineering and technology Scheduling (computing) Exponential function Combinatorics 0202 electrical engineering electronic engineering information engineering Combinatorial optimization 020201 artificial intelligence & image processing Time complexity Mathematics |
| Zdroj: | GECCO |
| DOI: | 10.1145/3205455.3205525 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|