Crossover can provably be useful in evolutionary computation

ABSTRACT

We show that the natural evolutionary algorithm for the all-pairs shortest path problem is significantly faster with a crossover operator than without. This is the first theoretical analysis proving the usefulness of crossover for a non-artificial problem.

REFERENCES

• 1: C. W. Ahn and R. Ramakrishna. A genetic algorithm for shortest path routing problem and the sizing of populations. IEEE Trans. Evolutionary Computation, 6:566--579, 2002.
• 2: N. Alon and J. H. Spencer. The Probabilistic Method. Wiley, 2nd edition, 2000.
• 3: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 4: B. Doerr, E. Happ, and C. Klein. A tight bound for the (11)-EA on the single source shortest path problem. In Proc. of CEC '07, pages 1890--1895. IEEE Press, 2007.
• 5: S. Fischer and I. Wegener. The Ising model on the ring: Mutation versus recombination. In Proc. of GECCO '04, volume 3102 of LNCS, pages 1113--1124. Springer, 2004.
• 6: Robert W. Floyd, Algorithm 97: Shortest path, Communications of the ACM, v.5 n.6, p.345, June 1962 [doi>10.1145/367766.368168]
• 7: Proceedings of the 5th International Conference on Genetic Algorithms, June 1993
• 8: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 9: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 10: J. Inagaki, M. Haseyama, and H. Kitajima. A genetic algorithm for determining multiple routes and its applications. In Proc. of ISCAS '99, pages 137--140. IEEE Press, 1999.
• 11: Thomas Jansen , Ingo Wegener, On the Analysis of Evolutionary Algorithms - A Proof That Crossover Really Can Help, Proceedings of the 7th Annual European Symposium on Algorithms, p.184-193, July 16-18, 1999
• 12: Thomas Jansen , Ingo Wegener, Real royal road functions: where crossover provably is essential, Discrete Applied Mathematics, v.149 n.1-3, p.111-125, 1 August 2005 [doi>10.1016/j.dam.2004.02.019]
• 13: Mark Jerrum , Alistair Sinclair, The Markov chain Monte Carlo method: an approach to approximate counting and integration, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 14: Donald B. Johnson, Efficient Algorithms for Shortest Paths in Sparse Networks, Journal of the ACM (JACM), v.24 n.1, p.1-13, Jan. 1977 [doi>10.1145/321992.321993]
• 15: S. Kirkpatrick, D. Gelatt Jr., and M. P. Vecchi. Optimization by simulated annealing. Science, 220:671--680, 1983.
• 16: Suihong Liang , A. Nur Zincir-Heywood , Malcolm I. Heywood, Intelligent Packets For Dynamic Network Routing Using Distributed Genetic Algorithm, Proceedings of the Genetic and Evolutionary Computation Conference, p.88-96, July 09-13, 2002
• 17: S. Liang, A. N. Zincir-Heywood, and M. I. Heywood. Adding more intelligence to the network routing problem: AntNet and Ga-agents. Appl. Soft Comput., 6:244--257, 2006.
• 18: Kurt Mehlhorn , Stefan Näher, LEDA: a platform for combinatorial and geometric computing, Cambridge University Press, New York, NY, 1999
• 19: N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, and E. Teller. Equations of state calculations by fast computing machines. J. Chemical Physics, 21:1087--1091, 1953.
• 20: Melanie Mitchell , John H. Holland, When Will a Genetic Algorithm Outperform Hill Climbing?, Proceedings of the 5th International Conference on Genetic Algorithms, p.647, June 01, 1993
• 21: Yuval Rabani , Yuri Rabinovich , Alistair Sinclair, A computational view of population genetics, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.83-92, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225088]
• 22: Y. Rabinovich and A. Wigderson. An analysis of a simple genetic algorithm. In Proc. of ICGA '94, pages 215--221, 1991.
• 23: Yuri Rabinovich , Avi Wigderson, Techniques for bounding the convergence rate of genetic algorithms, Random Structures & Algorithms, v.14 n.2, p.111-138, March 1999 [doi>10.1002/(SICI)1098-2418(199903)14:2<111::AID-RSA1>3.0.CO;2-6]
• 24: J. Scharnow, K. Tinnefeld, and I. Wegener. The analysis of evolutionary algorithms on sorting and shortest paths problems. J. Math. Model. Algorithms, 3:349--366, 2004.
• 25: Tobias Storch , Ingo Wegener, Real royal road functions for constant population size, Theoretical Computer Science, v.320 n.1, p.123-134, 12 June 2004 [doi>10.1016/j.tcs.2004.03.047]
• 26: Dirk Sudholt, Crossover is provably essential for the Ising model on trees, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068202]
• 27: Stephen Warshall, A Theorem on Boolean Matrices, Journal of the ACM (JACM), v.9 n.1, p.11-12, Jan. 1962 [doi>10.1145/321105.321107]
• 28: I. Wegener. Simulated annealing beats metropolis in combinatorial optimization. In Proc. of ICALP '05, volume 3580 of LNCS, pages 589--601. Springer, 2005.
• 29: I. Wegener and T. Jansen. The analysis of evolutionary algorithms -- a proof that crossover really can help. Algorithmica, 34:47--66, 2002.

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:
analysis, combinatorial optimization, crossover, evolutionary computation