Rigorous analyses of fitness-proportional selection for optimizing linear functions

ABSTRACT

Rigorous runtime analyses of evolutionary algorithms (EAs) mainly investigate algorithms that use elitist selection methods. Two algorithms commonly studied are Randomized Local Search (RLS) and the (1+1) EA and it is well known that both optimize any linear pseudo-Boolean function on n bits within an expected number of O(n log n) fitness evaluations. In this paper, we analyze variants of these algorithms that use fitness proportional selection.

A well-known method in analyzing the local changes in the solutions of RLS is a reduction to the gambler's ruin problem. We extend this method in order to analyze the global changes imposed by the (1+1) EA. By applying this new technique we show that with high probability using fitness proportional selection leads to an exponential optimization time for any linear pseudo-Boolean function with non-zero weights. Even worse, all solutions of the algorithms during an exponential number of fitness evaluations differ with high probability in linearly many bits from the optimal solution.

Our theoretical studies are complemented by experimental investigations which confirm the asymptotic results on realistic input sizes.

REFERENCES

• 1: Stefan Droste , Thomas Jansen , Ingo Wegener, On the analysis of the (1+ 1) evolutionary algorithm, Theoretical Computer Science, v.276 n.1-2, p.51-81, April 6, 2002 [doi>10.1016/S0304-3975(01)00182-7]
• 2: W. Feller. An Introduction to Probability Theory and Its Applications, vol. 1. Wiley, 3rd edition, 1968.
• 3: Oliver Giel , Per Kristian Lehre, On the effect of populations in evolutionary multi-objective optimization, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144114]
• 4: 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
• 5: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 6: George Harik , Erick Cantú-Paz , David E. Goldberg , Brad L. Miller, The gambler's ruin problem, genetic algorithms, and the sizing of populations, Evolutionary Computation, v.7 n.3, p.231-253, Fall 1999 [doi>10.1162/evco.1999.7.3.231]
• 7: Drift analysis and average time complexity of evolutionary algorithms, Artificial Intelligence, v.127 n.1, p.57-85, March 2001 [doi>10.1016/S0004-3702(01)00058-3]
• 8: Jun He , Xin Yao, Towards an analytic framework for analysing the computation time of evolutionary algorithms, Artificial Intelligence, v.145 n.1-2, p.59-97, April 2003 [doi>10.1016/S0004-3702(02)00381-8]
• 9: H. Mühlenbein. How genetic algorithms really work: mutation and hillclimbing. In Proceedings of PPSN '92, pages 15--26. Elsevier, 1992.
• 10: H. Mühlenbein. How genetic algorithms really work: mutation and hillclimbing. In Proceedings of PPSN '92, pages 15--26. Elsevier, 1992.
• 11: F. Neumann and I. Wegener. Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. In Proceedings of GECCO '04, vol. 3102 of LNCS, pages 713--724, 2004.
• 12: F. Neumann and C. Witt. Ant colony optimization and the minimum spanning tree problem. In Electronic Colloquium on Computational Complexity (ECCC), 2006. Report No. 143.
• 13: Günter Rudolph, How mutation and selection solve long-path problems in polynomial expected time, Evolutionary Computation, v.4 n.2, p.195-205, Summer 1996 [doi>10.1162/evco.1996.4.2.195]
• 14: C. Witt. An analysis of the (μ+1) ea on simple pseudoboolean functions. In Proceedings of GECCO '04, vol. 3102 of LNCS, pages 761--773, 2004.
• 15: C. Witt. Worst-case and average-case approximations by simple randomized search heuristics. In Proceedings of STACS '05, vol. 3404 of LNCS, pages 44--56, 2005.

INDEX TERMS

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

General Terms:
Algorithms, Theory

Keywords:
running time analysis, selection, theory