用伪二叉树法则构造多目标Pareto最优解集的方法  

An Approach to Constructing Multi-Objective Pareto Optimal Solutions Using Pseudo Binary Tree's Rule

作　　者：胡焕耀[1] 董渭清[1] 

机构地区：[1]西安交通大学电子与信息工程学院,西安710049

出　　处：《西安交通大学学报》2009年第2期29-32,共4页Journal of Xi'an Jiaotong University

基　　金：国家自然科学基金资助项目(60773118)

摘　　要：针对多目标进化算法中如何提高非支配集构造效率的问题,提出了一种用伪二叉树法则构造多目标Pareto最优解集的方法.根据多目标解的性质,将解的比较结果分为支配、被支配以及不相关3种类型,再根据解的比较结果生成排序伪二叉树.在每一轮比较中,从进化群体中选出一个个体,将该个体与当前非支配集中的个体进行比较,淘汰被支配的个体,而未被淘汰的个体将插入到非支配集中第一个被淘汰个体的位置.依次进行,直到进化群体中的个体比较完毕,从而生成排序的伪二叉树.同时,在理论上证明了采用该方法获取的非支配集为目标进化群体的最大非支配集,分析得知其在最差情况下的时间复杂度为O(rN2/2).实验结果表明,当目标数较大时(r≥5),在构造非支配集的效率上伪二叉树法要明显优于Deb、Jensen算法及擂台赛法则.To improve the efficiency of huilding a non-dominated set in multi-objective evolution algorithm, an approach called Pseudo binary tree＇s rule is proposed to construct the Pareto optimal solutions. The multi-objective solutions are divided into three types： dominated, non-dominated and irrelevant, based on their natures and comparison results, and then the sorting pseudo binary tree is generated according to the comparison results. An individual in the evolution group is selected in every round of comparison. Then the selected individual is compared with the individuals in the non-dominated set, and those that are dominated are eliminated. If the selected one survives, it replaces the first eliminated individual in the non-dominated set. Repeat the process successively until there is no individual left in the evolution group, and a sorting pseudo binary tree is generated. It is proved in theory that the non-dominated set obtained by the proposed method is the biggest non-dominated set in the objective evolution group, and the worst time complexity is O（rN^2/2）. Experimental results show that when the number of objects is comparatively large （r≥5）, the efficiency of building the non-dominated set using the pseudo binary tree＇s rule is obviously higher than that using Deb＇s algorithm, Jensen＇s algorithm or arena＇s principle.

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

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