The use of dynamic programming in genetic algorithms for permutation problems

The use of dynamic programming in genetic algorithms for permutation problems

0.00 Avg rating0 Votes
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: ,
Keywords: combinatorial analysis
Abstract:

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 n objects and are known to be NP-hard. Computational results for randomly generated problem instances exhibit encouraging features of genetic DP algorithms.

Reviews

Required fields are marked *. Your email address will not be published.