[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]马欢张建伟赵进超.求解VRPSDP的变邻域混合遗传算法[J].郑州大学学报(工学版),2015,36(03):120.[doi:10.3969/ j. issn.1671 -6833.2015.03.026]
　MA Huan,ZHANG Jian-wei,ZHAO Jin-chao,et al.A Hybrid Genetic and Variable Neighborhood Descent Algorithm for VehicleRouting Problem with Simultaneous Delivery and Pickup[J].Journal of Zhengzhou University (Engineering Science),2015,36(01):120.[doi:10.3969/ j. issn.1671 -6833.2015.03.026]
[2]左士伟,杨胡萍,张扬,等.基于改进遗传算法的电力系统无功优化[J].郑州大学学报(工学版),2015,36(06):66.[doi:10.3969/j. issn.1671 -6833.2015.06.013]
　YANG Huping,Ll Weiren,ZUO Shiwei,et al.Reactive Power Optimization by Improved Genetic Algorithm Method[J].Journal of Zhengzhou University (Engineering Science),2015,36(01):66.[doi:10.3969/j. issn.1671 -6833.2015.06.013]
[3]陆森林,任栉翔.基于响应面法的车内噪声分析与优化[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]
[4]蒋建东,王忆,张灵娟,等.基于遗传算法的背靠背换流站控制系统参数优化[J].郑州大学学报(工学版),2015,36(01):6.[doi:10.3969/ j. issn.1671 -6833.2015.01. 002]
　JIANG Jian-dong,WANG Yi,ZHANG Ling-juan,et al.Parameter Optimization of Control System for Back to Back Converter Station based on Genetic Algorithm[J].Journal of Zhengzhou University (Engineering Science),2015,36(01):6.[doi:10.3969/ j. issn.1671 -6833.2015.01. 002]
[5]穆瑞杰.基于遗传算法的地铁车站引导标识布点探析[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]
[6]蒋佩华,华冰,黄宇,等.基于遗传算法的变质量航天器姿态控制方法 [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]
[7]樊一娜,梁伟,黄渝清,等.基于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]
[8]黄茜,王书勤,邓少鸿,等.不确定环境下救灾部队驻地选址及搜救路径优化[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]
[9]赵艳敏,霍达..基于遗传模拟退火算法的钢桁架结构优化设计[J].郑州大学学报(工学版),2011,32(06):54.
　ZHAO Yan-min,HUO Da.Optimal Design of Steel Truss Structure Based on Genetic Simulated Annealing Algorithm[J].Journal of Zhengzhou University (Engineering Science),2011,32(01):54.
[10]任松,姜德义,杨春和..基于遗传算法的浅埋隧道开挖地表沉降神经网络预测[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]

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