摘要
最小顶点覆盖问题是组合最优化问题,在实际应用中有较广泛的应用,是一个NP难问题。针对最小顶点覆盖问题给出了一种混合化学反应优化求解算法。首先根据无向图的邻接矩阵表示法,设计了参与化学反应的分子编码和目标函数;同时把贪心算法思想创造性地融入到化学反应优化算法的四个重要反应算子中,以加快局部较优解的搜索过程;最后通过模拟化学反应中分子势能趋于稳定的过程,在问题的解空间中搜索其最优解。模拟实验结果表明,该算法对于求解无向图的最小顶点覆盖问题是有效的,并且在求解效率等方面有一定的改善。
Minimum vertex cover problem is a combinatorial optimization problem, it has a wide application in the real world,and it is a NP-hard problem. This paper presented a hybrid chemical reaction optimization algorithm for the minimum vertex cover problem. First of all, according to the undirected graph adjacency matrix, it designed chemical reactions molecular coding and the objective function. At the same time, it blended the greedy algorithm thought creatively into the four important operator of chemical reaction optimization algorithm to speed up the search process of local optimal solution. And searched the optimal solution in the solution space by simulating the process of chemical reaction in which potential energy gradually stabilize.The experimental result proves that the algorithm is effective for solving minimum vertex cover problem of undirected graph, and it performs remarkably better in solving efficiency.
作者
郑光勇
徐雨明
李肯立
孙士兵
Zheng Guangyong;Xu Yuming;Li Kenli;Sun Shibin(College of Computer Science & Technology, Hengyang Normal University, Hengyang Hunan 421002, China;College of Information Science & Engineering, Hunan University, Changsha 410082, China;Dept, of Electronic & Information Engineering, Changsha Normal University, Changsha 410100, China;College of Software, Changsha Social Work College, Changsha 410004, China)
出处
《计算机应用研究》
CSCD
北大核心
2016年第9期2669-2672,共4页
Application Research of Computers
基金
湖南省科技厅计划资助项目(2013GK3082)
湖南省自然科学基金项目(2016JJ4002)
关键词
最小顶点覆盖问题
组合优化
无向图
化学反应优化
贪心算法
minimum vertex cover problem
combinatorial optimization
undirected graph
chemical reaction optimization
greedy algorithm
