一种新的求解度约束最小生成树的遗传算法

被引：5

作者：

来卫国

李鸥

程军

机构：

[1] 信息工程大学信息工程学院通信工程系

来源：

计算机仿真 | 2008年 / 08期

关键词：

度约束; 最小生成树; 遗传算法; 过程控制;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

摘要：

染色体编码是遗传算法的关键内容,编码的优劣并直接影响算法的性能。提出了基于过程控制的生成树编码方法——PC编码。PC码为定长的整数向量,使用PC编码求解特定生成树问题时,首先选定的一个有效算法,并将修改为可控算法,然后用编码向量控制算法的运行过程,从而得到唯一生成树。为了求解度约束最小生成树(DCMST)问题,在D-Prim算法的基础上,设计了过程可控的度约束生成树构造PC-Prim算法。给出了以PC-Prim算法作为译码器的求解DC-MST问题的遗传算法。仿真结果表明遗传算法求解精度和运行时间均优于参与其他算法。

引用

页码：162 / 165

页数：4

共 5 条

[1] Minimum-weight degree-con-strained spanning tree problem:Heuristics and implementation onan SIMD parallel machine. B Boldon,N Deo,N Kumar. Technical Report CS-TR-95-02 . 1995
[2] A weighted coding in a genetic algo-rithm for the degree-constrained minimum spanning tree problem. RAIDL G R,JULSTROM B A. Proceedings of the 2000 ACM Symposium on Applied Computing 2000 . 2000
[3] Degree-constrained minimum spanning tree. Subhash C. NarulaCesar A. Ho. Computers and Operations Research . 1980
[4] An efficient evolutionary algorithmfor the degree-con-strained minimum panning tree problem. G R Raidl. Proc.of the 2000IEEE congress on evolutionary computation . 2000
[5] A new evolutionary approach to the degreeconstrained minimum spanning tree problem. Knowles J,Come D. IEEE Transac-tions on Evolutionary Computation . 2000

← 1 →