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

摘要：

给出了基于化学反应优化算法(CRO)求解最小顶点覆盖问题的一个新方法.首先根据最小顶点覆盖问题的无向图邻接矩阵,设计了参与化学化反应优化算法的分子编码和适应度函数;同时针对最小顶点覆盖问题的特性创造性地设计了化学反应优化算法中分子操作的四个重要算子;最后通过模拟化学反应中分子势能趋于稳定的过程,在问题的解空间中搜索其最优解.实验结果表明,通过与遗传算法(GA)、蚁群优化算法(ACO)等比较分析,所提的新方法对于求解无向图的最小顶点覆盖问题是有效的,并且与一般遗传算法相比在求解速度等方面有明显的改善.

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

所属期刊栏目：36

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

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

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

页数：共5页

页码：301-305