|
|||||
|
|
| 一个解决集合覆盖问题的二阶段遗传算法 | |
| 引用本文： | 吴志勇,陈韬,王红川,孙乐昌,张旻,李秩.一个解决集合覆盖问题的二阶段遗传算法[J].小型微型计算机系统,2011,32(4). |
| 作者姓名： | 吴志勇 陈韬 王红川 孙乐昌 张旻 李秩 |
| 作者单位： | 1. 解放军电子工程学院604研究室,安徽,合肥,230037 2. 解放军电子工程学院309研究室,安徽,合肥,230037 3. 73677部队,江苏,南京,210016 |
| 基金项目： | 国家自然科学基金项目(60972161)资助; 解放军电子工程学院博士生创新基金项目(CX2007016)资助 |
| 摘 要： | 针对集合覆盖问题,提出一个高效的可解决大规模数据的二阶段遗传算法.二阶段遗传算法可以分为数据约简阶段和启发式求解阶段,论文形式化地描述了数据约简阶段的相关定义、定理和算法,证明了该约简方法的有效性;并给出了启发式求解阶段中针对集合覆盖问题的遗传算法中选择、交叉、变异算子的设计方法.对Beasley提出的45个测试用例的测试结果验证了二阶段遗传算法的求解效率和求解质量高于其它遗传算法. |
| 关 键 词： | 集合覆盖 约简方法 遗传算法 |
Two-stage Genetic Algorithm for Set Covering Problem |
|
| WU Zhi-yong,CHEN Tao,WANG Hong-chuan,SUN Le-chang,ZHANG Min,LI Zhi.Two-stage Genetic Algorithm for Set Covering Problem[J].Mini-micro Systems,2011,32(4). | |
| Authors: | WU Zhi-yong CHEN Tao WANG Hong-chuan SUN Le-chang ZHANG Min LI Zhi |
| Affiliation: | WU Zhi-yong1,CHEN Tao1,WANG Hong-chuan1,SUN Le-chang1,ZHANG Min2,LI Zhi31(Division 604,Electronic Engineering Institute of PLA,Hefei 230037,China) 2(Division 309,China)3(Army 73677,Nanjing 210016,China) |
| Abstract: | 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 definitions,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... |
| Keywords: | set covering reduction method genetic algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |