化学反应优化算法求解最小顶点覆盖问题 |
| |
作者姓名: | 郑光勇 李肯立 潘果 徐雨明 蒋伟进 焦铬 |
| |
作者单位: | 衡阳师范学院计算机科学系;湖南大学信息科学与工程学院;湖南商学院计算机与信息工程学院 |
| |
基金项目: | 国家自然科学基金项目(61472136)资助;湖南省教育厅科研项目(12C1084)资助;湖南省科技厅计划项目(2013GK3082,2013FJ3077)资助 |
| |
摘 要: | 给出了基于化学反应优化算法(CRO)求解最小顶点覆盖问题的一个新方法.首先根据最小顶点覆盖问题的无向图邻接矩阵,设计了参与化学化反应优化算法的分子编码和适应度函数;同时针对最小顶点覆盖问题的特性创造性地设计了化学反应优化算法中分子操作的四个重要算子;最后通过模拟化学反应中分子势能趋于稳定的过程,在问题的解空间中搜索其最优解.实验结果表明,通过与遗传算法(GA)、蚁群优化算法(ACO)等比较分析,所提的新方法对于求解无向图的最小顶点覆盖问题是有效的,并且与一般遗传算法相比在求解速度等方面有明显的改善.
|
关 键 词: | 顶点覆盖问题 无向图 化学反应优化 NP完全问题 |
本文献已被 CNKI 等数据库收录! |
|