The use of dynamic programming in genetic algorithms for permutation problems |
| |
Institution: | 1. The Key Laboratory of Intelligent Computing & Signal Processing, Anhui University, Hefei 230039, China;2. Co-Innovation Center for Information Supply & Assurance Technology, Anhui University, Hefei 230601, China;1. Department of Computer Control and Management Engineering, Sapienza University, Rome, Italy;2. Dir. for Methodology and Statistical Process Design, Istat, Rome, Italy;3. Fondazione Ugo Bordoni, Rome, Italy |
| |
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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|