| 一种新的求解度约束最小生成树的遗传算法 |
| |
| 引用本文： | 来卫国,李鸥,程军. 一种新的求解度约束最小生成树的遗传算法[J]. 计算机仿真, 2008, 25(8) |
| |
| 作者姓名： | 来卫国 李鸥 程军 |
| |
| 作者单位： | 信息工程大学信息工程学院通信工程系,河南,郑州,450002;信息工程大学信息工程学院通信工程系,河南,郑州,450002;信息工程大学信息工程学院通信工程系,河南,郑州,450002 |
| |
| 摘 要： | 染色体编码是遗传算法的关键内容,编码的优劣并直接影响算法的性能.提出了基于过程控制的生成树编码方法--PC编码.PC码为定长的整数向量,使用PC编码求解特定生成树问题时,首先选定的一个有效算法,并将修改为可控算法,然后用编码向量控制算法的运行过程,从面得到唯一生成树.为了求解度约束最小生成树(DCMST)问题,在D-Prim算法的基础上,设计r过程可控的度约束生成树构造PC-Prim算法.给出了以PC-Prim算法作为译码器的求解DC-MST问题的遗传算法.仿真结果表明遗传算法求解精度和运行时间均优于参与其他算法.
|
| 关 键 词： | 度约束 最小生成树 遗传算法 过程控制 |
A Novel Genetic Algorithm for Degree Constrained Minimum Spanning Tree Problem |
| |
| LAI Wei-guo,LI Ou,CHENG Jun. A Novel Genetic Algorithm for Degree Constrained Minimum Spanning Tree Problem[J]. Computer Simulation, 2008, 25(8) |
| |
| Authors: | LAI Wei-guo LI Ou CHENG Jun |
| |
| Affiliation: | LAI Wei-guo,LI Ou,CHENG Jun(Communication Engineering Department,Information Engineering College of Information Engineering University of PLA,Zhengzhou Henan 450002,China) |
| |
| Abstract: | 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 tr... |
| |
| Keywords: | Degree constrained Minimum spanning tree Genetic algorithm Procedure control |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
