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

A Novel Genetic Algorithm for Degree Constrained Minimum Spanning Tree Problem

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

Chromosome coding is a key part of GA algorithm. The quality of code affects the performance of GA greatly. The paper presents a novel spanning tree coding method named PC code based on procedure controlling. PC code is a fixed length integer vector. To use PC code for certain spanning tree problem, an effective algorithm is chosen and modified to be controllable. Then PC code controls algorithm＇s running process and gets the one and only spanning tree. In order to solve the degree -constrained minimum spanning tree problem, the paper designs a controllable algorithm for degree -constrained spanning trees called PC -Prim algorithm based on D -Prim algorithm. Finally, a GA algorithm for DCMST problem is given which uses PC -Prim algorithm as PC decoder. Simulation resuits show that this GA algorithm has better precision and shorter running time than its counterparts.