Minimum Spanning Tree Problem Research Based on Genetic Algorithm

Minimum spanning tree (MST) problem is of high importance in network optimization, but it is also difficult for the traditional network optimization technique to deal with. In this paper, self-adaptive genetic algorithm (GA) approach is developed to deal with this problem. Without neglecting its network topology, the proposed method adopts the Pru¿fer number as the tree encoding and self-adaptation is used to enable strategy parameters to evolve along with the evolutionary process. Compared with the existing algorithm, the numerical analysis shows the efficiency and effectiveness of such self-adaptive GA approach on the MST problem.