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

摘要：

集合覆盖问题是组合优化中的典型问题,在日常生活中有着广泛的应用.提出了一种改进遗传算法来解决集合覆盖问题.算法对标准遗传算法的改进主要表现在:1)结合启发式算法和随机生成,设计了新的产生初始种群的方法；2)引入修补操作处理不可行解使其转换成可行解；3)对重复个体进行处理再利用；4)对多点交叉进行推广,提出了新的交叉算子；5)针对可行解和不可行解,采取两种自适应多位变异操作.数值实验结果表明该算法对于解决规模较大的集合覆盖问题是有效的.

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

所属期刊栏目：42

分类号：TP3;TP1

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

在线出版日期：2012-05-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：120-126