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

Chemical Reaction Optimization Algorithm for the Minimum Vertex Cover Problem

给出了基于化学反应优化算法(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.