Evolutionary algorithms and dynamic programming
| Autor: | Madeleine Theile, Benjamin Doerr, Christian Horoba, Anton V. Eremeev, Frank Neumann |
|---|---|
| Rok vydání: | 2011 |
| Předmět: |
FOS: Computer and information sciences
Mathematical optimization Combinatorial optimization Theoretical computer science General Computer Science Computer science Evolutionary algorithm Genetic programming Dynamic programming Evolutionary algorithms Evolutionary computation Theoretical Computer Science Genetic algorithm Computer Science - Data Structures and Algorithms Data Structures and Algorithms (cs.DS) Neural and Evolutionary Computing (cs.NE) Quality control and genetic algorithms Approximation algorithm Computer Science - Neural and Evolutionary Computing Approximation algorithms Memetic algorithm Genetic representation Criss-cross algorithm Randomized rounding Evolutionary programming Computer Science(all) |
| Zdroj: | GECCO |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2011.07.024 |
| Popis: | 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. This is an updated version of journal publication where few misprints are fixed |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect