基于遗传算法的最小生成树算法

以图论和遗传算法为基础 ,提出了一种求最小生成树的改进遗传算法 .该算法采用二进制编码表示最小树问题 ,用深度优先搜索算法进行图的连通性判断 ,并设计出相应的适应度函数、单亲换位算子和单亲逆转算子以及四种控制性进化策略 ,以提高算法执行速度和进化效率 .与Kruskal算法相比 ,该算法能在一次遗传进化过程中获得一批最小生成树 ,适合于解决不同类型的最小树问题

Minimum Spanning Tree Algorithms Based on Genetic Algorithms

Based on the graphic theory and genetic algorithm ,an improved genetic algorithm is introduced to search the minimum spanning trees. This algorithm uses binary code to represent the problem of minimum spanning trees and uses the depth first searching method to determine the connectivity of the graph.The corresponding fitness function, single parent transposition operator, single parent reverse operators and four kinds of controlling evolutionary strategies are designed to improve its speed and efficiency.In comparison with kruskal algorithm, it can acquire a set of minimum spanning trees during one genetic evolutionary process and is applicable to solving different kinds of minimum spanning tree problems.