基于节点编码的最小生成树算法

以图论和遗传算法为基础,提出了求最小生成树问题的基于节点编码的遗传算法.该算法采用Prufer数对最小生成树进行编码。初始群体由系统随机产生,在遗传操作中采用单点交叉操作及基本位变异操作。实例表明,该算法可得到多个最优解。

Based on the graphic theory and genetic algorithm. An improved algorithm is introduced to search the minimum spanning tree. This algorithm uses Prufer numbers to encode the minimum spanning tree. The initial population is generated randomly. The one-point crossover operator are designed to improve its speed and efficiency. Some cases show this algorithm can get several optimal solutions.