Research On Minimum Spanning Tree Algorithm For Degree Constraints Based On Multi - Populations

At present, the rapid social and economic development, reform and innovation of science and technology, use of social resources tend to seek efficient and effective technology solutions, research minimum spanning tree in real life has been more widely used and recognized. Degree-constrained minimum spanning tree (DCMST) problem is a well-known NP-hard problem. Because of the diversity and complexity of the real application problems, often for minimum spanning tree problem to conditions, so this kind of constrained minimum spanning tree problem in actual research fields it has been widely used, such as transportation and computer network design, DCMST implement and utilize problem solving.In this thesis DCMST carried out the following research:This paper is mainly used to achieve the degree of constraint on ant colony algorithm based on populations of intelligent algorithms to improve the method for constructing a minimum spanning tree, the algorithm process includes multiple-colony ant exploration, construction and optimization spanning three parts spanning tree. Multigroup ants found in the search process to find the edge set ant colony algorithm, if the ants find the minimum spanning tree fails, take the first produced for this malpractice and make a new kind of ant ants take only pheromone heuristic search in the search process The policy prevents the ant colony algorithm into a local optimum, then use the set of edges found Kruskal minimum spanning tree algorithm and using local optimization algorithm to local optimization, increase understanding of diversity. In a variety of groups, each ant populations adaptive information exchange through the information entropy, take dynamically changing tactics to increase pheromone and setting interference factor diversity of choice, while adding maximum and minimum ant system algorithm of ant colony algorithm strategy optimized solution in order to accelerate the convergence level and get more solutions. And by a large number of simulation experiments show that the algorithm has obvious advantages in the optimal solution for solving DCMST problem.