On Genetic Algorithms for Combinatorial Problems

点击翻译按钮获取中文摘要

A main goal of this project is to investigate the ability of genetic algorithms (GAs) for combinatorial optimization problems. We have obtained various kinds of experiment results in the application of GAs for some problems such as channel routing problem, module placement problem and maximum independent set problem. From these results, we come to a conclusion that GAs are good methods to solve problems.A key point of using GAs is how to encode chromosome from a solution of given problem. We adopt "a permutation encoding and a greedy decoding" method. Apparently, the search space is enlarged since the number of possible permutations is usually larger than that of possible solutions for many problems. However, it is frequently possible to limit the actual search space to the space of feasible solutions by using a good greedy algorithm to decode a chromosome. Especially, it is quite effect in the case of maximum independent set problem.For further research a theoretical analysis is needed to clear the effectiveness of the permutation encoding and the greedy decoding method.