基于遗传算法的通讯网络最佳Steiner树构造  

The Optimal Steiner Tree for Communication Network Based on Genetic Algorithm

作　　者：郑健体[1] 吉国力[1] 吴瑞意[2] 

机构地区：[1]厦门大学信息科学与技术学院,福建厦门361005 [2]华侨大学数学系,福建泉州362021

出　　处：《厦门大学学报（自然科学版）》2008年第3期318-322,共5页Journal of Xiamen University：Natural Science

摘　　要：提出了一种解决Steiner最小树问题的自适应遗传算法,将Steiner最小树问题转化成一个组合优化问题,并对部分初始种群的构造给出了一种试探选择方法.通过对通讯网络Steiner最小树问题的实例仿真分析,表明算法能有效地跳出局部极小值并快速地收敛于全局最优值.将其推广到考虑建站费用的极小树问题上,取得了很好的近似解.In order to solve the subject of Steiner minimum spanning tree,an adaptive genetic algorithm is introduced. The Steiner minimum spanning tree is transformed into a combination-optimization problem and a trial-selection method is proposed for the creation of the partial initial population. The application of the algorithm to communication network indicates that it is capable of jumping of the local optimization efficiently and constringing the global optimization quickly. This algorithm is successfully extended to the problem,of which the site-building fee should be considered,and the solution is reasonable.

关 键 词：通讯网络 Steiner最小树 最小生成树 遗传算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]