Abstract: 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?fer 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 satisfactory results. The simulation results show that this algorithm is effective.

Key words: Genetic Algorithm（GA）, Tabu search algorithm, niche, Minimum Spanning Tree（MST）, Pr?fer number

摘要： 针对最小生成树问题，提出了一种小生境遗传禁忌算法。算法中使用Pr?fer数对生成树进行编码。在选择交叉之前使用小生境技术，使得被选中交叉的个体之间的适应值的距离大于一定的阈值，从而保证了个体的多样性。遗传变异算子使用禁忌搜索算法，提高了遗传算法的局部搜索能力，加快了算法的收敛速度。模拟实验结果证明该算法是有效的。

关键词: 遗传算法, 禁忌搜索, 小生境, 最小生成树, Pr?fer数