The Use of Dynamic Programming in Genetic Algorithms
for Permutation Problems
Mutsunori Yagiura and Toshihide Ibaraki
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.
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.
genetic algorithm, dynamic programming,
heuristics, combinatorial optimization,
single machine scheduling problem.
European Journal of Operational Research,
Vol. 92 (1996) 387-401.
Back to the Paper List