Improved analysis methods for crossover-based algorithms

ABSTRACT

We deepen the theoretical analysis of the genetic algorithm for the all-pairs shortest path problem proposed by Doerr, Happ and Klein (GECCO 2008). We show that the growth of the paths through crossover operations can be analyzed without the previously used approach of waiting until all paths of a certain length are present in the population. This allows to prove an improved guarantee for the optimization time of O(n^3.25 log^1/4(n). We also show that this bound is asymptotically tight. Besides the mere run-time result, our analysis is a step towards understanding how crossover works and how it can be analyzed with rigorous methods.

REFERENCES

• 1: N. Alon and J. H. Spencer. The Probabilistic Method. Wiley, New York, 1992.
• 2: B. Doerr, E. Happ, and C. Klein. A tight bound for the (1 1)-EA on the single source shortest path problem. In IEEE Congress on Evolutionary Computation 2007, pages 1890--1895, Singapore, 2007. IEEE.
• 3: Benjamin Doerr , Edda Happ , Christian Klein, Crossover can provably be useful in evolutionary computation, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389202]
• 4: W. Feller. An introduction to probability theory and its applications. Vol. I. Third edition. John Wiley&Sons Inc., New York, 1968.
• 5: Jens Scharnow , Karsten Tinnefeld , Ingo Wegener, Fitness Landscapes Based on Sorting and Shortest Paths Problems, Proceedings of the 7th International Conference on Parallel Problem Solving from Nature, p.54-63, September 07-11, 2002
• 6: J. Scharnow, K. Tinnefeld, and I. Wegener. The analysis of evolutionary algorithms on sorting and shortest paths problems. Journal of Mathematical Modelling and Algorithms, pages 349--66, 2004.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
combinatorial optimization, crossover, evolutionary algorithm