摘要
提出了一种解决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.
出处
《厦门大学学报（自然科学版）》
CAS
CSCD
北大核心
2008年第3期318-322,共5页
Journal of Xiamen University：Natural Science
关键词
通讯网络
Steiner最小树
最小生成树
遗传算法
communication network
Steiner minimum spanning tree,minimum spanning tree
genetic algorithm
