On Genetic Algorithms for Combinatorial Problems

本项目的主要目标是研究遗传算法（GAs）在组合优化问题中的能力。在应用GAs解决信道路由问题、模块放置问题和最大独立集问题方面，我们已经得到了各种各样的实验结果。从这些结果中，我们得出结论，GAs是解决问题的好方法。利用遗传算法对染色体进行编码是遗传算法的一个关键问题。我们采用“一个排列编码和一个贪婪解码”的方法。显然，搜索空间被扩大了，因为对于许多问题，可能排列的数量通常大于可能解决方案的数量。然而，通过使用一个好的贪婪算法来解码染色体，通常可以将实际搜索空间限制在可行解的空间内。特别是对于极大独立集问题，它是非常有效的。为了进一步的研究，需要对排列编码和贪婪解码方法的有效性进行理论分析。

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.