一个解决集合覆盖问题的二阶段遗传算法  

Two-stage Genetic Algorithm for Set Covering Problem

作　　者：吴志勇[1] 陈韬[1] 王红川[1] 孙乐昌[1] 张旻[2] 李秩[3] 

机构地区：[1]解放军电子工程学院604研究室 [2]解放军电子工程学院309研究室 [3]73677部队

出　　处：《小型微型计算机系统》2011年第4期732-737,共6页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60972161)资助;解放军电子工程学院博士生创新基金项目(CX2007016)资助

摘　　要：针对集合覆盖问题,提出一个高效的可解决大规模数据的二阶段遗传算法.二阶段遗传算法可以分为数据约简阶段和启发式求解阶段,论文形式化地描述了数据约简阶段的相关定义、定理和算法,证明了该约简方法的有效性;并给出了启发式求解阶段中针对集合覆盖问题的遗传算法中选择、交叉、变异算子的设计方法.对Beasley提出的45个测试用例的测试结果验证了二阶段遗传算法的求解效率和求解质量高于其它遗传算法.Paper proposed an efficient two-stage genetic algorithm to solve set covering problem with large scale. Two-stage genetic algorithm can be divided into two stages： the data reduction stage and the heuristic problem solving stage. This paper formally describes related def＇mitions, theorem and algorithms in the data reduction stage and proves the proposed reduction method is useful; then gives the design of selection, crossover, and mutation operator of the genetic algorithm. The results on 45 set covering instances proposed by Beasley verify that the proposed two-stage genetic algorithm is higher than other genetic algorithms both on efficiency and resolution quality.

关 键 词：集合覆盖 约简方法 遗传算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]