用伪二叉树法则构造多目标Ｐａｒｅｔｏ最优解集的方法

胡焕耀　董渭清

摘要：针对多目标进化算法中如何提高非支配集构造效率的问题，提出了一种用伪二叉树法则构造多目标Pareto最优解集的方法。根据多目标解的性质，将解的比较结果分为支配、被支配以及不相关3种类型，再根据解的比较结果生成排序伪二叉树。在每一轮比较中，从进化群体中选出一个个体，将该个体与当前非支配集中的个体进行比较，淘汰被支配的个体，而未被淘汰的个体将插入到非支配集中第一个被淘汰个体的位置。依次进行，直到进化群体中的个体比较完毕，从而。生成排序的伪二叉树。同时，在理论上证明了采用该方法获取的非支配集为目标进化群体的最大非支配集，分析得知其在最差情况下的时间复杂度为O(rN^{2/2)。实验结果表明，当目标数较大时(r≥5)，在构造非支配集的效率上伪二又树法要明显优于Deb、Jensen算法及擂台赛法则。}

关键词：多目标进化；最优解集；非支配集；伪二叉树法则

中图分类号：TP301文献标志码：文章编号：0253—987X(2009)02—0029—04