期刊名称：International Journal of Computer Science and Network Security
印刷版ISSN：1738-7906
出版年度：2006
卷号：6
期号：7A
页码：50-57
出版社：International Journal of Computer Science and Network Security
摘要：A novel genetic algorithm is proposed for degree-constrained Minimum Spanning Tree (short for d-MST) problem in this paper. First, a novel model that transfer d-MST problem into a preference two objective MST problem is presented. Based on this model, a new crossover operator, a local search scheme, a mutation operator and a new selection operator are designed based on the preference of the two objectives. Then, a new genetic algorithm (short for GA) is proposed. Furthermore, the convergence of the proposed algorithm to globally optimal solution with probability one is proved. The simulation results indicate the proposed algorithm is effective.
