Article ID: | iaor1999399 |
Country: | Netherlands |
Volume: | 92 |
Issue: | 2 |
Start Page Number: | 387 |
End Page Number: | 401 |
Publication Date: | Jul 1996 |
Journal: | European Journal of Operational Research |
Authors: | Ibaraki Toshihide, Yagiura Mutsunori |
Keywords: | combinatorial analysis |
To deal with computationally hard problems, approximate algorithms are used to provide reasonably good solutions in practical time. Genetic algorithms are an example of the meta-heuristics which were recently introduced and which have been successfully applied to a variety of problems. We propose to use dynamic programming in the process of obtaining new generation solutions in the genetic algorithm, and call it a genetic DP algorithm. To evaluate the effectiveness of this approach, we choose three representative combinatorial optimization problems, the single machine scheduling problem, the optimal linear arrangement problem and the traveling salesman problem, all of which ask to compute optimum permutations of