基于改进遗传算法的集合覆盖问题  

Improved Genetic Algorithm for Set Covering Problem

作　　者：蒋建林[1] 程坤[1] 王璨璨[1] 徐进澎[1] 

机构地区：[1]南京航空航天大学理学院,江苏南京211100

出　　处：《数学的实践与认识》2012年第5期120-126,共7页Mathematics in Practice and Theory

基　　金：国家自然科学基金(11101211);江苏省自然科学基金(BK2011719);南京航空航天大学基本科研业务费专项科研项目(NS2010190)

摘　　要：集合覆盖问题是组合优化中的典型问题,在日常生活中有着广泛的应用.提出了一种改进遗传算法来解决集合覆盖问题.算法对标准遗传算法的改进主要表现在:1)结合启发式算法和随机生成,设计了新的产生初始种群的方法;2)引入修补操作处理不可行解使其转换成可行解;3)对重复个体进行处理再利用;4)对多点交叉进行推广,提出了新的交叉算子;5)针对可行解和不可行解,采取两种自适应多位变异操作.数值实验结果表明该算法对于解决规模较大的集合覆盖问题是有效的.The set covering problem is a typical combination-optimal problem, and it is widely used in our daily life. An improved genetic algorithm is presented for solving set covering problem in this paper. The improvements for standard genetic algorithm include the following aspects： first, this method designs a new way to generate initial population; second, a repair operator is introduced to transform infeasible solutions into feasible solutions; third, this method deals with overlapping individuals and reuses them; fourth, it promotes the multi-point crossover and designs a new crossover operator; fifth, two types of adaptive multi-bit mutation have been taken to deal with the feasible solutions and infeasible solutions： Experimental results show that this algorithm is efficient for solving relatively large set covering problem.

关 键 词：集合覆盖问题 改进遗传算法 启发式多点交叉 自适应多位变异 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]