文章基本信息

标题：A Novel Genetic Algorithm for Degree-Constrained Minimum Spanning Tree Problem
本地全文：下载
作者：Lixia Hanr, Yuping Wang
期刊名称：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.
关键词：degree-constrained minimum spanning tree, genetic algorithm, convergence