Evolutionary algorithms and dynamic programming

DOI10.1016/J.TCS.2011.07.024zbMATH Open1229.90159arXiv1301.4096OpenAlexW4213327093MaRDI QIDQ652137FDOQ652137

Authors: Benjamin Doerr, F. Neumann, Madeleine Theile, Anton Valentinovich Eremeev, Christian Thyssen 

Publication date: 19 December 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

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. Finally, we show that for a wide class of the so-called DP-benevolent problems (which are known to admit FPTAS) there exists a fully polynomial-time randomized approximation scheme based on an evolutionary algorithm.

Full work available at URL: https://arxiv.org/abs/1301.4096

Recommendations

• On the analysis of a dynamic evolutionary algorithm
• The use of dynamic programming in genetic algorithms for permutation problems
• Some fully polynomial time randomized approximation scheme based on an evolutionary algorithm
• Evolutionary algorithms
• Evolutionary computation in combinatorial optimization

zbMATH Keywords

combinatorial optimizationdynamic programmingapproximation algorithmsevolutionary algorithms

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Dynamic programming (90C39)

Cites Work

• Title not available (Why is that?)
• Introduction to algorithms
• Title not available (Why is that?)
• Introduction to evolutionary computing
• Title not available (Why is that?)
• Scheduling with batching: A review
• A Dynamic Programming Approach to Sequencing Problems
• When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
• Polynomial-Time Approximation Algorithms for the Ising Model
• Title not available (Why is that?)
• STACS 2005
• Title not available (Why is that?)
• How to analyse evolutionary algorithms.
• Title not available (Why is that?)
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• Representations for genetic and evolutionary algorithms. With a foreword by David E. Goldberg.
• The analysis of evolutionary algorithms on sorting and shortest paths problems
• Expected runtimes of evolutionary algorithms for the Eulerian cycle problem
• Randomized local search, evolutionary algorithms, and the minimum spanning tree problem
• Composition Principles for Synthesis of Optimal Multistage Processes
• Approximation of the supply scheduling problem
• Some fully polynomial time randomized approximation scheme based on an evolutionary algorithm
• Multiobjective dynamic programming
• Analysis of a simple evolutionary algorithm for the multiobjective shortest path problem
• Local search, reducibility and approximability of NP-optimization problems

Cited In (6)

• Some fully polynomial time randomized approximation scheme based on an evolutionary algorithm
• A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems
• Darwin's algorithms
• A relation-algebraic view on evolutionary algorithms for some graph problems
• Adaptive evolutionary programming based on reinforcement learning
• Evolution program for deterministic and stochastic optimizations

This page was built for publication: Evolutionary algorithms and dynamic programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q652137)