广义最小生成树的遗传算法求解及应用

介绍了最小生成树的概念,分析了最小生成树在实际应用中的局限性。引入了节点的度的定义,据此提出了广义最小生成树的概念。采用遗传算法来求解最小生成树,并针对普通遗传算法求解该问题的不足,提出了自调整的变异算子和限制父代个体数目的混合选择策略。通过一个有线电视网络的建模与仿真,表明了广义最小生成树模型的适用性。分别采用普通遗传算法和改进后的遗传算法进行求解,并将结果进行比较,证明了改进后的遗传算法的有效性。

Method based on genetic algorithm of solving generalized minimum spanning tree and its application

The concept of minimum spanning tree is introduced and its limitation is analyzed. The cost of the node degree is considered and accordingly the concept of generalized minimum spanning tree (GMST) is presented. Genetic algorithm is used to solve GMST. To correct the shortcomings of simple genetic algorithm in this problem, a self-adjusting mutation operator and a hybrid selection strategy are designed. Through the modelling and simulation of a cable television network, the applicability of GMST is proved. Finally, the improved algorithm and simple algorithm are used to solve the cable television network respectively, and the contrast of their results shows the effectiveness of the improved genetic algorithm.