Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We investigate theoretically how the fitness landscape influences the optimization process of population-based evolutionary algorithms using fitness-proportional selection. Considering the function OneMax, we show that it cannot be optimized in polynomial time with high probability regardless of the population size. This is proved by a generalization of drift analysis. For populations of at most logarithmic size, the negative result transfers to any function with unique optimum. Based on these insights, we investigate the effect of scaling the objective function in combination with a population that is not too small and show that then such algorithms compute optimal solutions for a wide range of problems in expected polynomial time. Finally, relationships with (1+λ)-EAs and (1,λ)-EAs are described.

REFERENCES

• 1: Oliver Giel , Ingo Wegener, Evolutionary Algorithms and the Maximum Matching Problem, Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, p.415-426, February 27-March 01, 2003
• 2: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 3: Edda Happ , Daniel Johannsen , Christian Klein , Frank Neumann, Rigorous analyses of fitness-proportional selection for optimizing linear functions, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389277]
• 4: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 5: J. Jägersküpper and T. Storch. When the plus strategy outperforms the comma strategy -- and when not. In Proceedings of the 2007 IEEE Symposium on Foundations of Computational Intelligence (FOCI 2007), pages 25--32. IEEE Press, 2007.
• 6: Thomas Jansen , Kenneth A. De Jong , Ingo Wegener, On the Choice of the Offspring Population Size in Evolutionary Algorithms, Evolutionary Computation, v.13 n.4, p.413-440, December 2005 [doi>10.1162/106365605774666921]
• 7: P. S. Oliveto, J. He, and X. Yao. Computational complexity analysis of evolutionary algorithms for combinatorial optimization: A decade of results. International Journal of Automation and Computing, 4(3):281--293, 2007.
• 8: Pietro S. Oliveto , Carsten Witt, Simplified Drift Analysis for Proving Lower Bounds in Evolutionary Computation, Proceedings of the 10th international conference on Parallel Problem Solving from Nature: PPSN X, September 13-17, 2008, Dortmund, Germany [doi>10.1007/978-3-540-87700-4_9]
• 9: Ingo Wegener , Carsten Witt, On the Optimization of Monotone Polynomials by Simple Randomized Search Heuristics, Combinatorics, Probability and Computing, v.14 n.1, p.225-247, January 2005 [doi>10.1017/S0963548304006650]
• 10: Carsten Witt, Runtime Analysis of the (μ+1) EA on Simple Pseudo-Boolean Functions, Evolutionary Computation, v.14 n.1, p.65-86, March 2006 [doi>10.1162/106365606776022751]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Performance, Theory

Keywords:
genetic algorithms, running time analysis, selection, theory