Abstract: A novel multi-objective evolutionary algorithm on multi-objective minimum spanning tree problem is proposed which is based on a fast elitist Non-dominated Sorting Genetic Algorithm for multi-objective optimization（NSGA-II）.It adopts the edge-sets as the tree encoding and a new crossover operator and a fast elitist non-dominated sorting algorithm to make the GA search give out all Pareto optimal solutions distributed all along the Pareto frontier.The experimental results show that this algorithm has faster convergent speed and better diversity of solutions than the algorithm based on PrimRST.

摘要： 在改进的非支配排序遗传算法（NSGA-II）的基础上，提出了一种新的基于生成树边集合编码的繁殖算子求解多目标最小生成树问题的遗传算法。通过快速非支配排序法，降低了算法的计算复杂度，引入保存精英策略，扩大采样空间。实验结果表明：对于多目标最小生成树问题，边集合编码具有较好的遗传性和局部性，而且基于此繁殖算子的遗传算法在求解效率和解的质量方面都优于基于PrimRST的遗传算法。