Degree Constrained Minimum Spanning Tree Of Genetic Algorithms Research Questions

Degree constrained minimum spanning tree (DCMST) case is a common problem in network optimization. In recent years, the degree constrained minimum spanning tree has been widely used in designing computer networks, communication networks and transportation network and many other fields. In addition, Many network design relate to the degree constrained minimum spanning. For example, when designing communications networks, the network topology is to find a spanning tree of the connected graph, minimize the cost of network construction is to find the minimum spanning tree, and less load of each node is the node’s degree constraints. However, the solving of the degree constrained minimum spanning tree is proved to be an NP-hard problem, up to now it has still unable to find an exact algorithm for large-scale DCMST problem.This article introduced the classical algorithms, heuristics and modern optimization algorithm for solving the DCMST problem. It designed a genetic algorithm for solving the degree constrained minimum spanning tree problem In non-complete graph, for which constructed a new coding method, fitness function, the initialization method and genetic operators. In order to accelerate progress, it also designed an optimization operator, and achieved good results.