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

被引：5

作者：

郑光勇 ^{[1
,2
]}

李肯立 ^{[2
]}

潘果 ^{[2
]}

徐雨明 ^{[1
,2
]}

蒋伟进 ^{[3
]}

焦铬 ^{[1
]}

机构：

[1] 衡阳师范学院计算机科学系

[2] 湖南大学信息科学与工程学院

[3] 湖南商学院计算机与信息工程学院

来源：

小型微型计算机系统 | 2015年 / 36卷 / 02期

关键词：

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

D O I：

10.20009/j.cnki.21-1106/tp.2015.02.022

中图分类号：

TP301.6 [算法理论];

学科分类号：

080201 [机械制造及其自动化];

摘要：

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

引用

页码：301 / 305

页数：5

共 7 条

[1]

A DAG scheduling scheme on heterogeneous computing systems using double molecular structure-based chemical reaction optimization [J].

Xu, Yuming ;

Li, Kenli ;

He, Ligang ;

Tung Khac Truong .

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2013, 73 (09) :1306-1322

[2]

Chemical reaction optimization with greedy strategy for the 0–1 knapsack problem.[J].Tung Khac Truong;Kenli Li;Yuming Xu.Applied Soft Computing Journal.2013, 4

[3]

算法设计与分析.[M].郑宗汉;郑晓明编著;.清华大学出版社.2005,

[4]

组合最优化算法和复杂性.[M].刘振宏等译.清华大学出版社.1988,

[5]

一种求解顶点覆盖问题的混合遗传算法 [J].