摘要
给出了基于化学反应优化算法(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.
出处
《小型微型计算机系统》
CSCD
北大核心
2015年第2期301-305,共5页
Journal of Chinese Computer Systems
基金
国家自然科学基金项目(61472136)资助
湖南省教育厅科研项目(12C1084)资助
湖南省科技厅计划项目(2013GK3082
2013FJ3077)资助
关键词
顶点覆盖问题
无向图
化学反应优化
NP完全问题
vertex cover problem
undirected graph
chemical reaction optimization
NP-complete problem