On the analysis of the simple genetic algorithm

ABSTRACT

For many years it has been a challenge to analyze the time complexity of Genetic Algorithms (GAs) using stochastic selection together with crossover and mutation. This paper presents a rigorous runtime analysis of the well-known Simple Genetic Algorithm (SGA) for OneMax. It is proved that the SGA has exponential runtime with overwhelming probability for population sizes up to μ≤ n^1/8-ε for some arbitrarily small constant ε and problem size n. To the best of our knowledge, this is the first time non-trivial lower bounds are obtained on the runtime of a standard crossover-based GA for a standard benchmark function. The presented techniques might serve as a first basis towards systematic runtime analyses of GAs.

References

1. A. Auger and B. Doerr eds. Theory of Randomized Seach Heuristics - Foundations and Recent Developments. World Scientific, 2010.
2. B. Doerr, E. Happ, and C. Klein. Crossover can provably be useful in evolutionary computation. In Proc. of GECCO '08, pages 539--546, 2008.
3. B. Doerr, M. Fouz, and C. Witt. Sharp bounds by probability-generating functions and variable drift. In Proc. of GECCO '11, pages 2083--2090, 2011.
4. D. E. Goldberg. Genetic Algorithms in Search, Optimization and machine learning. Addison-Wesley, 1989.
5. E. Happ, D. Johannsen, C. Klein, and F. Neumann. Rigorous Analyses of Fitness-Proportional Selection for Optimizing Linear Functions. In Proc. of GECCO '08, pages 953--960, 2008.
6. J. Jägersküpper and C. Witt. Rigorous runtime analysis of a (μ +1) ES for the Sphere function. In Proc. of GECCO '05, pages 849--856, 2005.
7. T. Jansen and I. Wegener. Real royal road functions: where crossover provably is essential. Discrete Applied Mathematics, 149(1-3):111--125, 2005.
8. T. Kötzing, D. Sudholt, and M. Theile. How crossover helps in pseudo-boolean optimization. In Proc. of GECCO '11, pages 989--996, 2011.
9. P. K. Lehre. Negative drift in populations. In Proc. of PPSN '10, pages 244--253, 2010.
10. P. K. Lehre. Fitness-levels for non-elitist populations. In Proc. of GECCO '11, pages 2075--2082, 2011.
11. F. Neumann, P. S. Oliveto, G. Rudolph, and D. Sudholt. On the effectiveness of crossover for migration in parallel evolutionary algorithms. In Proc. of GECCO '11, pages 1587--1594, 2011.
12. F. Neumann, P. S. Oliveto, and C. Witt. Theoretical analysis of fitness-proportional selection: Landscapes and efficiency. In Proc. of GECCO '09, pages 835--842, 2009.
13. F. Neumann, D. Sudholt, and C. Witt. Analysis of different MMAS ACO algorithms on unimodal functions and plateaus. Swarm Intelligence, 3(1):35--68, 2009.
14. F. Neumann, D. Sudholt, and C. Witt. A few ants are enough: ACO with iteration-best update. In Proc. of GECCO '10, pages 63--70, 2010.
15. F. Neumann and C. Witt. Bioinspired Computation in Combinatorial Optimization - Algorithms and Their Computational Complexity. Springer, 2010.
16. P. S. Oliveto, J. He, and X. Yao. Analysis of population-based evolutionary algorithms for the vertex cover problem. In Proc. of CEC '08, pages 1563--1570, 2008.
17. P. S. Oliveto and C. Witt. Simplified drift analysis for proving lower bounds in evolutionary computation. Algorithmica, 59(3):369--386, 2011.
18. G. Rudolph. Convergence properties of canonical genetic algorithms. IEEE Transactions on Neural Networks, 5(1):96--101, 1994.
19. M. D. Vose. The Simple Genetic Algorithm: Foundations and Theory. MIT Press, 1998.
20. R. A. Watson and T. Jansen. A building-block royal road where crossover is provably essential. In Proc. of GECCO '07, pages 1452--1459, 2007.
21. C. Zarges. On the utility of the population size for inversely fitness proportional mutation rates. In Proc. of FOGA '09, pages 39--46, 2009.

Index Terms

• Theory of computation

  • Design and analysis of algorithms