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

• 作者: 吴志勇 孙乐昌 张旻 李秩 王红川 陈韬
• 来源期刊: 小型微型计算机系统
• 学科: 工学
• 关键词: 集合覆盖 约简方法 遗传算法
• 年，卷（期）: 2011,（4）
• 所属期刊栏目: 人工智能与算法研究
• 页码范围: 732-737
• 分类号: TP18
• 字数: 5421字
• 语种: 中文

摘要

针对集合覆盖问题,提出一个高效的可解决大规模数据的二阶段遗传算法.二阶段遗传算法可以分为数据约简阶段和启发式求解阶段,论文形式化地描述了数据约简阶段的相关定义、定理和算法,证明了该约筒方法的有效性;并给出了启发式求解阶段中针对集合覆盖问题的遗传算法中选择、交叉、变异算子的设计方法.对Beasley提出的45个测试用例的测试结果验证了二阶段遗传算法的求解效率和求解质量高于其它遗传算法.