一种混合化学反应优化算法求解最小顶点覆盖问题

作     者：郑光勇 徐雨明 李肯立 孙士兵 Zheng Guangyong;Xu Yuming;Li Kenli;Sun Shibin

作者机构：衡阳师范学院计算机科学与技术学院湖南衡阳421002 湖南大学信息科学与工程学院长沙410082 长沙师范学院电子与信息工程系长沙410100 长沙民政职业技术学院软件学院长沙410004 

基　　金：湖南省科技厅计划资助项目(2013GK3082) 湖南省自然科学基金项目(2016JJ4002) 

出 版 物：《计算机应用研究》 (Application Research of Computers)

年 卷 期：2016年第33卷第9期

页      码：2669-2672页

摘      要：最小顶点覆盖问题是组合最优化问题,在实际应用中有较广泛的应用,是一个NP难问题。针对最小顶点覆盖问题给出了一种混合化学反应优化求解算法。首先根据无向图的邻接矩阵表示法,设计了参与化学反应的分子编码和目标函数;同时把贪心算法思想创造性地融入到化学反应优化算法的四个重要反应算子中,以加快局部较优解的搜索过程;最后通过模拟化学反应中分子势能趋于稳定的过程,在问题的解空间中搜索其最优解。模拟实验结果表明,该算法对于求解无向图的最小顶点覆盖问题是有效的,并且在求解效率等方面有一定的改善。

主 题 词：最小顶点覆盖问题 组合优化 无向图 化学反应优化 贪心算法 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

D　O　I：10.3969/j.issn.1001-3695.2016.09.024

馆 藏 号：203187283...