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

作     者：郑光勇 李肯立 潘果 徐雨明 蒋伟进 焦铬 ZHENG Guang-yong;LI Ken-li;PAN Guo;XU Yu-ming;JIANG Wei-jin;JIAO Ge

作者机构：衡阳师范学院计算机科学系湖南衡阳421002 湖南大学信息科学与工程学院长沙410082 湖南商学院计算机与信息工程学院长沙410205 

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

出 版 物：《小型微型计算机系统》 (Journal of Chinese Computer Systems)

年 卷 期：2015年第36卷第2期

页      码：301-305页

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

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

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

核心收录：

馆 藏 号：203742503...