Font Size: a A A

WCJ Genetic Algorithm For Degree-Constrained Minimum Spanning Tree

Posted on:2009-04-07Degree:MasterType:Thesis
Country:ChinaCandidate:C J WeiFull Text:PDF
GTID:2178360308978596Subject:Basic mathematics
Abstract/Summary:PDF Full Text Request
The minimum spanning tree (MST) problem which has a long history was proposed by Boruvka in 1926. Its aim is to get the optimal distribution of the network. While the degree-constrained minimum spanning tree (DCMST) problem was proposed by Narula and Ho in 1980, we often encounter such problems in social life. For example, the crossroads are always been designed by four roads, the computer network always restricts some nodes. In order to prevent serious problems, linking too many cables is forbidden. This shows the degree-constrained minimum spanning tree problem has practical significance.There are two types of algorithms to solve degree-constrained minimum spanning tree problem, one is the classical algorithm such as the Branch and Bound algorithm; the other is the evolutionary algorithm which has been widely used in recent years, such as the Genetic algorithm, the Ant algorithm. In this paper, a WCJ genetic algorithm for degree-constrained minimum spanning tree problem is given.Genetic coding plays an important role in the genetic algorithm. This paper encodes the tree with Prufer array and designs a Set D, which can fully guarantee the feasibility of the initial population; this paper designs a correction operation to make cross operation's offspring feasible; this paper designs three kinds of mutation operation, they are not only produce the feasible solution, but also avoid the problem of premature convergence. The algorithm's convergence has been proved, series of numerical examples of degree-constrained minimum spanning tree are tested and the results indicate that this algorithm is effective.
Keywords/Search Tags:degree-constrained minimum spanning tree (DCMST), WCJ genetic algorithm, Prufer coding, operation, simulation
PDF Full Text Request
Related items