Computational complexity and evolutionary computation

ABSTRACT

Evolutionary algorithms and other nature-inspired search heuristics like ant colony optimization have been shown to be very successful when dealing with real-world applications or problems from combinatorial optimization. In recent years, analyses has shown that these general randomized search heuristics can be analyzed like "ordinary" randomized algorithms and that such analyses of the expected optimization time yield deeper insights in the functioning of evolutionary algorithms in the context of approximation and optimization. This is an important research area where a lot of interesting questions are still open.

The tutorial enables attendees to analyze the computational complexity of evolutionary algorithms and other search heuristics in a rigorous way. An overview of the tools and methods developed within the last 15 years is given and practical examples of the application of these analytical methods are presented.

REFERENCES

• 1: Frank Neumann, Expected runtimes of evolutionary algorithms for the Eulerian cycle problem, Computers and Operations Research, v.35 n.9, p.2750-2759, September, 2008 [doi>10.1016/j.cor.2006.12.009]
• 2: Benjamin Doerr , Daniel Johannsen, Adjacency list matchings: an ideal genotype for cycle covers, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277192]
• 3: Simon Fischer , Ingo Wegener, The one-dimensional Ising model: mutation versus recombination, Theoretical Computer Science, v.344 n.2-3, p.208-225, 17 November 2005 [doi>10.1016/j.tcs.2005.04.002]
• 4: 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]
• 5: Thomas Jansen , Dennis Weyland, Analysis of evolutionary algorithms for the longest common subsequence problem, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277148]
• 6: Tobias Storch, How randomized search heuristics find maximum cliques in planar graphs, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144099]
• 7: 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
• 8: F. Neumann, I. Wegener (2004): Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. In GECCO, 713-724.
• 9: J. Scharnow, K. Tinnefeld, I. Wegener (2004): The analysis of evolutionary algorithms on sorting and shortest paths problems. Journal of Mathematical Modelling and Algorithms 3:349-366.
• 10: C. Witt (2005): Worst-case and average-case approximations by simple randomized search heuristics. In 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS), 44-56.
• 11: Thomas Jansen , R. Paul Wiegand, The Cooperative Coevolutionary (1+1) EA, Evolutionary Computation, v.12 n.4, p.405-434, December 2004 [doi>10.1162/1063656043138905]
• 12: D. Sudholt (2006): Local search in evolutionary algorithms: the impact of the local search frequency. In 17th International Symposium on Algorithms and Computation (ISAAC), 359-368.
• 13: Richard A. Watson , Thomas Jansen, A building-block royal road where crossover is provably essential, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277224]
• 14: Benjamin Doerr , Frank Neumann , Dirk Sudholt , Carsten Witt, On the runtime analysis of the 1-ANT ACO algorithm, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1276964]
• 15: Stefan Droste, Not all linear functions are equally difficult for the compact genetic algorithm, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068124]

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:
computational complexity, evolutionary computation