Evolutionary algorithms and dynamic programming |
| |
Authors: | Benjamin DoerrAnton Eremeev Frank NeumannMadeleine Theile Christian Thyssen |
| |
Affiliation: | a Algorithms and Complexity, Max-Planck-Institut für Informatik, Saarbrücken, Germanyb Omsk Branch of Sobolev Institute of Mathematics SB RAS, Omsk, Russiac School of Computer Science, University of Adelaide, Adelaide, Australiad Institut für Mathematik, TU Berlin, Berlin, Germanye Fakultät für Informatik, LS 2, TU Dortmund, Dortmund, Germany |
| |
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. |
| |
Keywords: | Combinatorial optimization Dynamic programming Evolutionary algorithms Approximation algorithms |
本文献已被 ScienceDirect 等数据库收录! |
|