Evolutionary algorithms and dynamic programming

ABSTRACT

Recently, it has been proven that evolutionary algorithms produce good results for a wide range of combinatorial optimization problems. Some of the considered problems are tackled by evolutionary algorithms that use a representation, which enables them to construct solutions in a dynamic programming fashion. We take a general approach and relate the construction of such algorithms to the development of algorithms using dynamic programming techniques. Thereby, we give general guidelines on how to develop evolutionary algorithms that have the additional ability of carrying out dynamic programming steps.

REFERENCES

• 1: R. E. Bellman and S. E. Dreyfus. Applied Dynamic Programming. Princeton University Press, 1962.
• 2: 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]
• 3: Benjamin Doerr , Nils Hebbinghaus , Frank Neumann, Speeding up evolutionary algorithms through asymmetric mutation operators, Evolutionary Computation, v.15 n.4, p.401-410, Winter 2007 [doi>10.1162/evco.2007.15.4.401]
• 4: 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]
• 5: B. Doerr, C. Klein, and T. Storch. Faster evolutionary algorithms by superior graph representations. In IEEE Symposium on Foundations of Computational Intelligence (FOCI), pages 245--250. IEEE Press, 2007.
• 6: Tobias Friedrich , Nils Hebbinghaus , Frank Neumann , Jun He , Carsten Witt, Approximating covering problems by randomized search heuristics using multi-objective models, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277118]
• 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: M. Held and R. M. Karp. A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematics, 10(1):196--210, 1962.
• 9: Christian Horoba, Analysis of a simple evolutionary algorithm for the multiobjective shortest path problem, Proceedings of the tenth ACM SIGEVO workshop on Foundations of genetic algorithms, January 09-11, 2009, Orlando, Florida, USA [doi>10.1145/1527125.1527140]
• 10: D. I. Kogan. Dynamic programming and discrete multicriterial optimization, 2004. In Russian.
• 11: Zbigniew Michalewicz , David B. Fogel, How to Solve It: Modern Heuristics, Springer-Verlag New York, Inc., Secaucus, NJ, 2004
• 12: 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]
• 13: Frank Neumann , Joachim Reichel, Approximating Minimum Multicuts by Evolutionary Multi-objective Algorithms, 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_8]
• 14: Frank Neumann , Joachim Reichel , Martin Skutella, Computing minimum cuts by randomized search heuristics, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389250]
• 15: Frank Neumann , Ingo Wegener, Randomized local search, evolutionary algorithms, and the minimum spanning tree problem, Theoretical Computer Science, v.378 n.1, p.32-40, June, 2007 [doi>10.1016/j.tcs.2006.11.002]
• 16: G. R. Raidl and B. A. Julstrom. Edge sets: An effective evolutionary coding of spanning trees. IEEE Transactions on Evolutionary Computation, 7(3):225--239, 2003.
• 17: Joachim Reichel , Martin Skutella, Evolutionary algorithms and matroid optimization problems, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277149]
• 18: J. Scharnow, K. Tinnefeld, and I. Wegener. The analysis of evolutionary algorithms on sorting and shortest paths problems. Journal of Mathematical Modelling and Algorithms, 3(4):349--366, 2004.
• 19: Madeleine Theile, Exact Solutions to the Traveling Salesperson Problem by a Population-Based Evolutionary Algorithm, Proceedings of the 9th European Conference on Evolutionary Computation in Combinatorial Optimization, p.145-155, April 15-17, 2009, Tübingen, Germany [doi>10.1007/978-3-642-01009-5_13]
• 20: C. Witt. Worst-case and average-case approximations by simple randomized search heuristics. In Symposium on Theoretical Aspects of Computer Science (STACS), pages 44--56. Springer, 2005.
• 21: Gerhard J. Woeginger, When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?, INFORMS Journal on Computing, v.12 n.1, p.57-74, January 2000 [doi>10.1287/ijoc.12.1.57.11901]

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
combinatorial optimization, dynamic programming, evolutionary algorithms