中文摘要：

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

英文摘要：

Set covering problem is an NP-hard and classical combinatorial optimization problem that has a wide range of real world applications.Firstly,the set covering problem is converted into an equivalent unconstrained 0-1programming problem by the adaptive penalty function method.Then,an efficient adaptive memetic algorithm is proposed to solve the resulting unconstrained 0-1programming problem.It integrates an initial population construction method,a local search method,a crossover operator,an adaptive mutation operator and a path relinking strategy,which are based on the characteristics of the set covering problem.These strategies achieve a good balance between intensification and diversification.The proposed algorithm has been tested on 45 benchmarks from the literatures.Computational results and comparisons with the existing genetic algorithms indicate that the proposed algorithm can find solutions with high quality in a reasonable time,and it is an efficient algorithm for solving the large scale set covering problems.