Zhejiang Daxue xuebao. Lixue ban (Mar 2016)

An adaptive memetic algorithm for solving the set covering problem(自适应memetic算法求解集合覆盖问题)

  • LINGeng(林耿),
  • GUANJian(关健)

DOI
https://doi.org/10.3785/j.issn.1008-9497.2016.02.008
Journal volume & issue
Vol. 43, no. 2
pp. 168 – 174

Abstract

Read online

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

Keywords