一种求解图最小顶点覆盖问题的混合遗传算法

摘要：

图的最小顶点覆盖问题是一个典型的NP-hard组合优化问题,在诸多领域有着重要应用.近年来,传统遗传算法等各种智能优化方法被引入到该问题的求解中来,但效果不理想.文章基于理想浓度模型的机理分析,利用均匀设计抽样的理论和方法,对遗传算法中的交叉操作进行了重新设计,并在分析图的顶点覆盖问题特点的基础上,结合局部搜索策略,给出了一个解决图最小顶点问题的新遗传算法.通过将该算法与简单遗传算法和佳点集遗传算法进行实例仿真模拟比较,可以看出新的算法提高了求解图最小顶点覆盖问题的求解质量、速度和精度.

关键词： Vertices Covering Problems Genetic Algorithm(GA) Uniform Design Sampling(UDS) Genetic Algorithm Based on Uniform Design Sampling(UGA)

作者: 周本达 陈明华

作者单位: 皖西学院数理系,安徽六安 237012 皖西学院计算机科学与技术系,安徽六安 237012

会议类型: 国内会议

会议名称: 第三届中国智能计算大会

会议地点: 济南

会议语种:中文

页码: 417-421

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