论文部分内容阅读
以图论和遗传算法为基础,提出了求解最小生成树问题的遗传算法。该算法解决了常用二进制编码不能正确表达最小生成树的问题,利用Prufer数对生成树进行编码;在遗传操作中对变异算子进行了改进,避免了由于变异产生大量不可行解。从而提高了遗传算法的效率;通过数值试验,表明该算法简单,高效,收敛率高。
Based on graph theory and genetic algorithm, a genetic algorithm for solving the minimum spanning tree problem is proposed. The algorithm solves the problem that common binary codes can not correctly express the minimum spanning tree, and uses the Prufer number to encode the spanning tree. The mutation operator is improved in the genetic operation to avoid a large number of infeasible solutions due to the mutation. Thus improving the efficiency of genetic algorithm; Numerical experiments show that the algorithm is simple, efficient, and high convergence rate.