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

• 作者: 孙士兵 徐雨明 李肯立 郑光勇
• 来源期刊: 计算机应用研究
• 关键词: 最小顶点覆盖问题 组合优化 无向图 化学反应优化 贪心算法
• 年，卷（期）: 2016,（9）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 2669-2672
• 页数: 4页
• 分类号: TP301.5
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2016.09.024

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李肯立	湖南大学信息科学与工程学院	130	931	16.0	22.0
2	郑光勇	衡阳师范学院计算机科学与技术学院	47	92	4.0	7.0
4	孙士兵	长沙民政职业技术学院软件学院	34	92	6.0	8.0
5	徐雨明	长沙师范学院电子与信息工程系	8	7	2.0	2.0