用遗传算法求最小生成树

以图论和遗传算法为基础,给出了一个改进的求最小生成树的算法,提出了＂无性生殖＂的方式,舍弃了逆转算子,改进了换位算子,调整了选择算子,更简单,因而编程更容易,效率更高.使用该算法可以在较短的时间内以较高的概率获得一组最小或次小生成树,而传统算法一般只能得到一个最小生成树.

A Genetic Algorithm to Determine the Minimum Spanning Tree

Based on graphic theory and genetic algorithm,an improved algorithm to determine the minimum spanning tree is given,the ＂asexual reproduction＂ method introduced,the transposition operator abandoned,the transposition operator improved,and the selection operator adjusted,which makes program easier and more efficient. Using the algorithm,we can obtain a group of minimum or less spanning trees in a shorter time and with a higher probability,while using the traditional algorithms,we can only get a minimum spanning tree.