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

Chemical Reaction Optimization Algorithm for the Minimum Vertex Cover Problem

作　　者：郑光勇[1,2] 李肯立[2] 潘果[2] 徐雨明[1,2] 蒋伟进[3] 焦铬[1] 

机构地区：[1]衡阳师范学院计算机科学系,湖南衡阳421002 [2]湖南大学信息科学与工程学院,长沙410082 [3]湖南商学院计算机与信息工程学院,长沙410205

出　　处：《小型微型计算机系统》2015年第2期301-305,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61472136)资助;湖南省教育厅科研项目(12C1084)资助;湖南省科技厅计划项目(2013GK3082;2013FJ3077)资助

摘　　要：给出了基于化学反应优化算法(CRO)求解最小顶点覆盖问题的一个新方法.首先根据最小顶点覆盖问题的无向图邻接矩阵,设计了参与化学化反应优化算法的分子编码和适应度函数;同时针对最小顶点覆盖问题的特性创造性地设计了化学反应优化算法中分子操作的四个重要算子;最后通过模拟化学反应中分子势能趋于稳定的过程,在问题的解空间中搜索其最优解.实验结果表明,通过与遗传算法(GA)、蚁群优化算法(ACO)等比较分析,所提的新方法对于求解无向图的最小顶点覆盖问题是有效的,并且与一般遗传算法相比在求解速度等方面有明显的改善.Chemical Reaction Optimization （ CRO ） is proposed for the minimum vertex cover problem in this paper. According to the undirected graph adjacency matrix,chemical reactions molecular coding is designed. The four important operators are designed crea- tively according to the characteristics of problem. The optimal solution is searched in the solution space by Simulating the process of chemical reaction in which potential energy gradually stabilize. Compared with genetic algorithm （ GA ）, ant colony optimization algo- rithm （ ACO ）, and so on, the experimental result proves that the new method is effective for solving minimum vertex cover problem of undirected graph, and it performs remarkably better than the general genetic algorithm in solving speed.

关 键 词：顶点覆盖问题 无向图 化学反应优化 NP完全问题 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]