求解多目标最小生成树的一种改进的非支配排序遗传算法

摘要

在改进的非支配排序遗传算法(NSGA-Ⅱ)的基础上,提出了一种基于生成树边集合编码求解多目标最小生成树问题的进化算法.通过快速非支配排序法,降低了算法的计算复杂度,引入保存精英策略,扩大采样空间.实验结果表明:对于多目标最小生成树问题,边集合编码具有较好的遗传性和局部性,而且基于边集合编码的进化算法在求解效率和解的质量方面都优于基于Prüfer编码的进化算法.