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

摘要：

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

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

所属期刊栏目：33

分类号：TP301.5(计算技术、计算机技术)

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

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

页数：共4页

页码：2669-2672