自适应memetic算法求解集合覆盖问题

• 作者: 关健 林耿
• 来源期刊: 浙江大学学报（理学版）
• 学科: 工学
• 关键词: 集合覆盖问题 memetic算法 罚函数 局部搜索 路径重连
• 年，卷（期）: 2016,（2）
• 所属期刊栏目: 数学与计算机科学
• 页码范围: 168-174
• 页数: 7页
• 分类号: O224.1|TP18
• 字数: 6453字
• 语种: 中文
• DOI: 10.3785/j.issn.1008-9497.2016.02.008

摘要

集合覆盖问题是一个经典的NP困难的组合优化问题,有着广泛的应用背景.首先,采用动态罚函数法将集合覆盖问题等价转化为无约束的0-1规划问题.然后,基于集合覆盖问题的结构特征,设计了初始种群构造方法、局部搜索方法、交叉算子、动态变异算子和路径重连策略,提出了一个高效求解该0-1规划问题的自适应memetic算法.该算法有效平衡了集中搜索和多样化搜索.通过45个标准例子测试该算法,并将其结果与现有遗传算法进行了比较,表明该算法能够在可接受的时间内找到高质量的解,能够有效求解大规模集合覆盖问题.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	林耿	闽江学院数学系	24	24	3.0	4.0
2	关健	闽江学院现代教育技术中心	8	4	1.0	2.0