[1]周荣敏,买文宁,雷延峰..基于遗传算法的最小生成树算法[J].郑州大学学报(工学版),2002,23(01):45-48.[doi:10.3969/j.issn.1671-6833.2002.01.013]
　ZHOU Rongmin,Buy Wen Ning,Lei Yanfeng.Minimal spanning tree algorithm based on genetic algorithm[J].Journal of Zhengzhou University (Engineering Science),2002,23(01):45-48.[doi:10.3969/j.issn.1671-6833.2002.01.013]
点击复制

基于遗传算法的最小生成树算法()
分享到：

《郑州大学学报(工学版)》[ISSN:1671-6833/CN:41-1339/T]

卷:
23卷
期数:
2002年01期
页码:
45-48
栏目:
出版日期:
1900-01-01

文章信息/Info

Title:
Minimal spanning tree algorithm based on genetic algorithm
作者:
周荣敏; 买文宁; 雷延峰.
郑州大学环境与水利学院,河南,郑州,450002, 郑州大学环境与水利学院,河南,郑州,450002, 郑州大学环境与水利学院,河南,郑州,450002
Author(s):
ZHOU Rongmin; Buy Wen Ning; Lei Yanfeng
关键词:
遗传算法;  最小生成树;  进化策略;  网络优化
Keywords:
DOI:
10.3969/j.issn.1671-6833.2002.01.013
文献标志码:
A
摘要:
以图论和遗传算法为基础,提出了一种求最小生成树的改进遗传算法.该算法采用二进制编码表示最小树问题,用深度优先搜索算法进行图的连通性判断,并设计出相应的适应度函数、单亲换位算子和单亲逆转算子以及四种控制性进化策略,以提高算法执行速度和进化效率.与Kruskal 算法相比,该算法能在一次遗传进化过程中获得一批最小生成树,适合于解决不同类型的最小树问题.
Abstract:
Based on graph theory and genetic algorithm, an improved genetic algorithm for finding the minimum spanning tree is proposed. The algorithm uses binary coding to represent the minimum tree problem, uses the depth-first search algorithm to judge the connectivity of the graph, and designs the corresponding fitness function, one-parent transposition operator and single-parent reversal operator, as well as four control evolution strategies to improve the execution speed and evolutionary efficiency of the algorithm. Compared with the Kruskal algorithm, the algorithm can obtain a batch of minimum spanning trees in a single genetic evolution process, which is suitable for solving different types of minimum tree problems.

相似文献/References:

[1]陆森林,任栉翔.基于响应面法的车内噪声分析与优化[J].郑州大学学报(工学版),2017,38(05):65.[doi:10.13705/j.issn.1671-6833.2017.05.002]
　Lu Senlin,Ren Guxiang.Analysis and Optimization of Vehicle Inner Noise Based on Response Surface Method[J].Journal of Zhengzhou University (Engineering Science),2017,38(01):65.[doi:10.13705/j.issn.1671-6833.2017.05.002]
[2]穆瑞杰.基于遗传算法的地铁车站引导标识布点探析[J].郑州大学学报(工学版),2018,39(01):73.[doi:10.13705/j.issn.1671-6833.2018.01.019]
　Mu Ruijie.Analysis of Position Settings for Oriented Identifies of Subway Station[J].Journal of Zhengzhou University (Engineering Science),2018,39(01):73.[doi:10.13705/j.issn.1671-6833.2018.01.019]
[3]蒋佩华,华冰,黄宇,等.基于遗传算法的变质量航天器姿态控制方法 [J].郑州大学学报(工学版),2019,40(04):1.[doi:10.13705/j.issn.1671-6833.2019.04.009]
　Jiang Peihua,Huabing,Huang Yu,et al.The Attitude Control Method of Variable Mass Spacecraft Based on Genetic Algorithm [J].Journal of Zhengzhou University (Engineering Science),2019,40(01):1.[doi:10.13705/j.issn.1671-6833.2019.04.009]
[4]樊一娜,梁伟,黄渝清,等.基于IGA 的配电系统运行损耗与可靠性优化[J].郑州大学学报(工学版),2019,40(05):58.[doi:10.13705/j.issn.1671-6833.2019.05.009]
　Fan Yina,Liang Wei,Huang Yuqing,et al.Optimization of operation loss and reliability of power distribution system based on IGA[J].Journal of Zhengzhou University (Engineering Science),2019,40(01):58.[doi:10.13705/j.issn.1671-6833.2019.05.009]
[5]黄茜,王书勤,邓少鸿,等.不确定环境下救灾部队驻地选址及搜救路径优化[J].郑州大学学报(工学版),2021,42(05):44.[doi:10.13705/j.issn.1671-6833.2021.05.015]
　Huang Qian,Wang Shuqin,Deng Shaohong,et al.Study on Location-Routing Problem of Earthquake Relief Troops in Uncertain Unvironment[J].Journal of Zhengzhou University (Engineering Science),2021,42(01):44.[doi:10.13705/j.issn.1671-6833.2021.05.015]
[6]赵艳敏,霍达..基于遗传模拟退火算法的钢桁架结构优化设计[J].郑州大学学报(工学版),2011,32(06):54.[doi:10.3969/j.issn.1671-6833.2011.06.013]
[7]任松,姜德义,杨春和..基于遗传算法的浅埋隧道开挖地表沉降神经网络预测[J].郑州大学学报(工学版),2006,27(03):46.[doi:10.3969/j.issn.1671-6833.2006.03.011]
　Ren Song,JIANG Deyi,Yang Chunhe.Prediction of surface settlement neural network for shallow buried tunnel excavation based on genetic algorithm[J].Journal of Zhengzhou University (Engineering Science),2006,27(01):46.[doi:10.3969/j.issn.1671-6833.2006.03.011]
[8]杨丽娜,刘刚,王秋生..一种改进的遗传算法及其应用[J].郑州大学学报(工学版),2005,26(03):98.[doi:10.3969/j.issn.1671-6833.2005.03.026]
　Yang Lina,LIU Gang,Wang Qiusheng.An improved genetic algorithm and its application[J].Journal of Zhengzhou University (Engineering Science),2005,26(01):98.[doi:10.3969/j.issn.1671-6833.2005.03.026]
[9]姜景山,李宗坤..改进的遗传算法在土石坝沉降预测中的应用[J].郑州大学学报(工学版),2004,25(04):74.[doi:10.3969/j.issn.1671-6833.2004.04.019]
　JIANG Jingshan,Li Zongkun.Application of improved genetic algorithm in earth-rock dam settlement prediction[J].Journal of Zhengzhou University (Engineering Science),2004,25(01):74.[doi:10.3969/j.issn.1671-6833.2004.04.019]
[10]周荣敏,雷延锋..基于遗传算法的雨水管道系统优化设计[J].郑州大学学报(工学版),2003,24(04):59.[doi:10.3969/j.issn.1671-6833.2003.04.014]
　ZHOU Rongmin,Lei Yanfeng.Optimal design of rainwater pipe system based on genetic algorithm[J].Journal of Zhengzhou University (Engineering Science),2003,24(01):59.[doi:10.3969/j.issn.1671-6833.2003.04.014]

更新日期/Last Update: 1900-01-01