The Solution and Application of the Generalized Minimum Spanning Tree Based on Genetic Algorithm
Yuan Duan · Xihua Daxue xuebao. Zhexue shehui kexue ban · 2010
The limitation of traditional Minimum Spanning Tree problem was analyzed.The Multi-objective Minimum Spanning Tree problem and Degree-constrained Minimum Spanning Tree problem were integrated to put forward the new concept of Generalized Minimum Spanning Tree(GMST) based on the research of various constrained minimum tree problems and their solution algorithms.The edges of the minimum spanning tree are endowed with multi weights and the degree constraint and implement cost are introduced to meet the actual engineering needs.For the GMST is a combinatorial optimization problem which has multiple extremums,the simple Genetic Algorithm can not find optimal solution of high quality.So,a self-adjusting mutation operator based on maturity of the population and a hybrid selection strategy which can limit the parent individuals are designed.Finally,through the modeling and simulation of a cable television network,the applicability of GMST concept and effectivity of the improved genetic algorithm are proved.The economical arrangement for cable TV network is solved in rural areas.