Evolutionary algorithms and dynamic programming
From MaRDI portal
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.
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
Cites work
- scientific article; zbMATH DE number 2130220 (Why is no real title available?)
- scientific article; zbMATH DE number 3174053 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1962832 (Why is no real title available?)
- scientific article; zbMATH DE number 194544 (Why is no real title available?)
- scientific article; zbMATH DE number 5686753 (Why is no real title available?)
- A Dynamic Programming Approach to Sequencing Problems
- Analysis of a simple evolutionary algorithm for the multiobjective shortest path problem
- Approximation of the supply scheduling problem
- Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
- Composition Principles for Synthesis of Optimal Multistage Processes
- Expected runtimes of evolutionary algorithms for the Eulerian cycle problem
- How to analyse evolutionary algorithms.
- Introduction to algorithms
- Introduction to evolutionary computing
- Local search, reducibility and approximability of NP-optimization problems
- Multiobjective dynamic programming
- Polynomial-Time Approximation Algorithms for the Ising Model
- Randomized local search, evolutionary algorithms, and the minimum spanning tree problem
- Representations for genetic and evolutionary algorithms. With a foreword by David E. Goldberg.
- STACS 2005
- Scheduling with batching: A review
- Some fully polynomial time randomized approximation scheme based on an evolutionary algorithm
- The analysis of evolutionary algorithms on sorting and shortest paths problems
- When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
Cited in
(6)- Adaptive evolutionary programming based on reinforcement learning
- Darwin's algorithms
- Some fully polynomial time randomized approximation scheme based on an evolutionary algorithm
- Evolution program for deterministic and stochastic optimizations
- A relation-algebraic view on evolutionary algorithms for some graph problems
- A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems
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)
