Research On The Degree Constrained Minimum Spanning Tree Problem Based On Partheno-Genetic Algorithm

Minimum spanning tree problem is a classic problem in combinatorial optimization, and has a wide range of applications in communications network design and shortest connections,etc. In practice, the degree of the vertex spanning often need to meet certain conditions. For example, in order to prevent bringing vulnerability from node failure in the communication network design,the degree of nodes must satisfy certain restrictions. Minimum spanning tree with the degree of vertex constraint problem is called degree constrained minimum spanning tree problem.Genetic algorithms is a heuristic search algorithm, it provides an effective way for the degree constrained minimum spanning tree problem The paper proposed partheno-genetic algorithm to solve the problem that combining with the idea of genetic algorithms and considering the characteristics of the degree constrained minimum spanning tree problem,and designed a new coding scheme and corresponding genetic manipulation.Finally, it proposed partheno-genetic algorithm to solve the degree constrained minimum spanning tree problem in complete figure.Based on the improved prufer coding proposed a new way of encoding and decoding, so that the decoding process is static, the operating efficiency of the algorithm was improved, and by analysis of the new coding structure of the tree can be visually drawn. Designed a new mutation operator, the new operator maintained to the diversity of the population, and made future generations to retain a good quality from parent. Designed two local optimization operator that optimized to improve the quality, while improving the search efficiency.