求解最小生成树的一种小生境遗传禁忌算法  

Solution of minimum spanning tree based on niche genetic algorithm Importing Tabu Search

作　　者：欧阳浩[1] 陈波[1] 

机构地区：[1]广西工学院计算机工程系,广西柳州545006

出　　处：《计算机工程与应用》2013年第1期59-61,123,共4页Computer Engineering and Applications

基　　金：广西科技攻关计划项目(桂科攻0992006-13);广西工学院博士基金(院科博11Z05)

摘　　要：针对最小生成树问题,提出了一种小生境遗传禁忌算法。算法中使用Prfer数对生成树进行编码。在选择交叉之前使用小生境技术,使得被选中交叉的个体之间的适应值的距离大于一定的阈值,从而保证了个体的多样性。遗传变异算子使用禁忌搜索算法,提高了遗传算法的局部搜索能力,加快了算法的收敛速度。模拟实验结果证明该算法是有效的。In order to solve the Minimum Spanning Tree （MST） problem, this paper provides a niche Genetic Algorithm （GA） importing Tabu search. The algorithm uses Prüifer number to encode these trees. Before selection and crossover, that the algorithm uses niche to keep the distance of selected trees is bigger than one threshold, so it can guarantee the multiformity of individuals. That mutation of GA uses Tabu search algorithm, can improve the local searching ability, and speed up the convergence for satis-factory results. The simulation results show that this algorithm is effective.

关 键 词：遗传算法 禁忌搜索 小生境 最小生成树 Prfer数 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]