一种新角度支配关系的多目标进化算法.pdf

D O I:/j j x a t u e d u c n h t t p:/x b x a t u e d u c n一种新角度支配关系的多目标进化算法张浩楠,过晓芳(西安工业大学 基础学院,西安 )摘要:为了兼顾多目标进化算法求解的收敛性和多样性,文中在分析解群支配以及多样性情况相关理论的基础上,借鉴网格支配和角度支配的优势,提出一种新的支配关系刻画解群在目标空间的分布状况,以较好地在收敛性和多样性间取得平衡;设计了一种新角度支配的多目标进化算法,该算法利用新角度支配关系增强选择压力,维持解群的多样性;比较了在N S GA I I算法框架下,新提出的支配关系与原有两种支配关系的收敛性、多样性以及收敛速度.研究结果表明:文中算法在D T L Z及WF G基准测试集上获得的G D,I G D和S p a c i n g指标性能均得到了提升,并且能够更快地获得高质量解集,故所提出的支配关系能够更有效地平衡收敛性和多样性.关键词:多目标优化;进化算法;e p s i l o n支配;角度支配中图号:T P 文献标志码:A文章编号:()M u l t i O b j e c t i v eE v o l u t i o n a r yA l g o r i t h mb a s e do naN o v e lA n g l eD o m i n a n c eR e l a t i o nZHANGH a o n a n,G U OX i a o f a n g(S c h o o l o fS c i e n c e s,X ia nT e c h n o l o g i c a lU n i v e r s i t y,X ia n ,C h i n a)A b s t r a c t:T h ep a p e r s t u d i e sh o wt oa c h i e v e t h eb a l a n c eb e t w e e n t h e c o n v e r g e n c e a n dd i v e r s i t yo fm u l t i o b j e c t i v ee v o l u t i o n a r ya l g o r i t h m s B a s e do nt h e t h e o r i e so f e v o l u t i o n a r yp o p u l a t i o n sd o m i n a n c er e l a t i o na n dd i v e r s i t y,a n dd r a w i n go nt h ea d v a n t a g e so fg r i dd o m i n a n c er e l a t i o na n da n g l ed o m i n a n c er e l a t i o n,t h i sp a p e rp r e s e n t san o v e l d o m i n a n c e r e l a t i o nt od e s c r i b e t h ed i s t r i b u t i o no f e v o l u t i o n a r yp o p u l a t i o n s i nt h eo b j e c t i v es p a c e,a i m i n ga t a c h i e v i n gab e t t e rb a l a n c eb e t w e e nt h ec o n v e r g e n c ea n dd i v e r s i t y Am u l t i o b j e c t i v ee v o l u t i o n a r ya l g o r i t h mb a s e do nan o v e l a n g l ed o m i n a n c e i sd e v e l o p e d B yu s i n g t h en o v e l a n g l ed o m i n a n c er e l a t i o n,i tc a ni m p r o v et h es e l e c t i o np r e s s u r ea n d m a i n t a i nt h ed i v e r s i t yo fe v o l u t i o n a r yp o p u l a t i o n s I nt h e f r a m e w o r ko fN S GA I Ia l g o r i t h m,t h ec o n v e r g e n c e,d i v e r s i t ya n dc o n v e r g e n c er a t eo ft h en e w l yp r o p o s e dd o m i n a n c e r e l a t i o na r e c o m p a r e dw i t h t h o s eo f t h e e x i s t i n g t w od o m i n a n c e r e l a t i o n s 第 卷第期 年月西安工业大学学报J o u r n a l o fX ia nT e c h n o l o g i c a lU n i v e r s i t yV o l N o F e b 收稿日期:基金资助:国家自然科学基金项目().第一作者:张浩楠(),女,硕士研究生.通信作者:过晓芳(),女,副教授,主要研究方向为最优化理论及其应用、多目标进化算法,E m a i l:g u o x i a o f a n g x a t u e d u c n.引文格式:张浩楠,过晓芳一种新角度支配关系的多目标进化算法J西安工业大学学报,():Z HAN G H a o n a n,GUO X i a o f a n g M u l t i O b j e c t i v eE v o l u t i o n a r yA l g o r i t h mb a s e do naN o v e lA n g l eD o m i n a n c eR e l a t i o nJ J o u r n a l o fX ia nT e c h n o l o g i c a lU n i v e r s i t y,():T h er e s u l t ss h o wt h a tt h ep e r f o r m a n c eo ft h eI G D,G Da n dS p a c i n go b t a i n e db yt h en o v e ld o m i n a n c er e l a t i o no nt h eD T L Za n d WF Gt e s ts u i t e sh a sb e e ni m p r o v e d,w i t hh i g h q u a l i t ys o l u t i o ns e t so b t a i n e dm o r eq u i c k l y I t i sc o n c l u d e dt h a t t h ed o m i n a n c e r e l a t i o np r o p o s e d i nt h i sp a p e r c a nb a l a n c ec o n v e r g e n c ea n dd i v e r s i t ym o r ee f f e c t i v e l y K e yw o r d s:m u l t i o b j e c t i v eo p t i m i z a t i o n;e v o l u t i o n a r ya l g o r i t h m;e p s i l o n d o m i n a n c e;a n g l ed o m i n a n c e在科学研究和工程领域中,经常会遇到同时需要优化多个目标的最优化问题,即多目标优化问题.多目标优化问题中的特点是解之间相互冲突,最优解不是唯一的,而是一组互不支配的折中解,称为P a r e t o最优解.随着目标个数的增加,最优解集合的数量不断增大,算法计算量越来越大,运用传统的多目标优化算法求解变得非常困难.由于多目标进化算法基于种群的特性能够在一次运行中获得一组折中解,并且其不对所求问题需满足的数学性质等做出要求,因此多目标进化算 法 已 广 泛 应 用 于 各 种 多 目 标 优 化 问 题 的 求解 .目前,多目标进化算法求解多目标优化问题大致分为以下三类:基于支配的多目标进化算法 ,基于分解的多目标进化算法 以及基于指标的多目标进化算法 .在求解高维的多目标优化问题的时候,随着优化目标个数的增加,传统的P a r e t o支配无法提供足够的选择压力.基于支配的多目标进化算法能够更好地提高解的选择压力,因此研究者们从不同视角提出了多种改进的支配关系.现阶段,支配关系大致可分为以下几类:基于支配区域扩展的方法.文献 提出了支配,该支配准则的基本思想是在两个目标之间设置折衷率的上、下界,使得种群中性能较差的D R S s被支配,减少种群中非支配解比例,增加选择压力,提升算法的收敛性.但该支配准则中的参数值不易设置,较难找到一个分布、收敛均良好的折中解集.文献 提出了控制支配区域支配方法(C D A S),该方法通过自定义参数S控制解支配区域的扩张或收缩程度,从而达到提升收敛性或增强多样性的目的.但C D A S的参数S在面对不同的问题时不容易确定,并且其难以同时提高解集的收敛性或多样性.文献 针对C D A S中参数不易设置进行改进,提出自控制支配区域支配方法(S C D A S),该算法在比较二者支配关系时,不需使用外部参数S可自行控制每个解的支配面积,实现了解集收敛性和多样性之间更好的平衡.该类方法能够有效地增加解的选择压力,但没有兼顾多样性,会使非支配解集集中在P a r e t o前沿的某一部分,边界解可能会被支配.基于网格的方法.文献 提出了支配.该支配准则通过将目标空间划分为多个超立方体网格,在扩大支配区域的同时,保证每个网格中只存在一个非支配解,既增大选择压力,也维持了分布的均匀性.但采用支配的算法进行进化迭代的过程中,最优前沿上一些极端解容易被其他解支配,导致边界解丢失,多样性不够理想.文献 提出了G r i d支配,该支配方法在 支配需自行设置参数的基础上进行改进,采用自适应网格结构,并且通过解的位置采用单独居中的网格进行计算,在增加算法选择压力的同时,维护种群的多样性.但该支配方法可能会消除相邻的良好收敛解,从而导致算法收敛性能降低.该类方法通过将目标空间划分为多个网格,以保证种群的多样性,同时扩大解的支配区域,从而提高了选择压力,但该类算法的网格规模不易选取,时间复杂度较大.基于小生境的方法.文献 提出了增强支配关系的准则(S D R),该支配方法不需要用户预先定义,根据种群的分布自定义定制支配区域,并在此区域中搜索收敛性最佳的解,从而更好地平衡了解集的收敛性和多样性,但该算法性能差异同领域定制的规则紧密相关.该类方法能够保证解的多样性,但对复杂P a r e t o前沿的求解效果不太理想.基于角度的方法.文献 提出了角度支配(A D支配),该支配方法通过构建由解和各轴节点组成的角度向量进行非支配排序,由于角度向量与坐标轴紧密相关,靠近P F和边界的解具有较高的非支配排序等级.因此A D支配在扩大解的支配区域的同时,又能有效地保持边界解,兼顾了解集的收敛性和分布的广泛性,但采用角度支配时解集均匀性仍可提升.该类方法增加解之间的选择压力,以保证解的收敛性,但解集的多样性不能很好地保证.尽管以上改进的支配关系明显增强了算法求解的性能,但均无法更好地兼顾收敛性和多样性.第期张浩楠,等:一种新角度支配关系的多目标进化算法采用支配和A D支配的算法,都通过扩大解支配区域的方法提高算法的收敛性.基于网格的支配方法确保每个网格中只存在一个非支配解,维持解集分布的均匀性,但存在边界解丢失的问题,导致解集分布广泛性不够理想.A D支配使得靠近P F和边界的解具有较高的非支配排序等级,能有效地保持边界解,维持解集分布多样性,但均匀性仍有提高的余地.基于此,文中将支配与A D支配进行有效结合,拟提出了一种网 格角度支配 关系(E p s i l o n A n g l eD o m i n a n c eR e l a t i o n,A D).该支配关系具有如下特点:A D支配在以上两种支配方法的基础上,进一步扩大解的支配区域,提升算法的收敛性;利用A D支配准则偏好边界解这一特性,A D支配在进化过程中可有效保持边界解,提升解集分布的广泛性;A D支配基于网格的支配方式,保证每个网格中只能有一个非支配解,维持解分布的均匀性.文中将 A D支配嵌入到经典N S G A I I算法框架中代替原有的P a r e t o支配,设计了一种新角度支配关系的多目标进化算法(E p s i l o n A n g l e N S G A I I,A D N S G A I I).新角度支配关系的多目标进化算法文中给出多目标优化相关概念和定义,给出新的角度支配关系定义,将新支配关系嵌入到N S GA I I算法中,提出一种新角度支配关系的多目标进化算法:A D N S GA I I.多目标优化相关概念和定义定义多目标优化问题.多目标问题一般描述为m i nf(x)(f(x),f(x),fm(x),()式中:x(x,x,xn)为n维决策空间中的解;fm(x)为第m个子目标函数.定义P a r e t o支配.对于式()中的MO P问题,设x,y为决策空间中任意两个解,称x支配y(记为xy)当且仅当满足以下条件:fi(x)fi(y),i,mfj(x)fj(y),j,m,()定义 支配.对于式()中的MO P问题,设x,y为决策空间中任意两个解,称x 支配y(记为xy)当且仅当满足以下条件:fi(x)ifi(y),i,mfj(x)ifj(y),j,m()图为 支配概念图,从图中可以看出,若解x,y根据P a r e t o支配关系进行比较,二者之间没有支配关系.但若按 支配关系的定义,解x支配的区域为阴影区域,此时xy.图 支配概念图F i g T h ec o n c e p to f d o m i n a n c er e l a t i o n定义A D支配.对于式()中的MO P问题,设x,y为决策空间中任意两个解,称xA D支配y(记为xa n g l ey)当且仅当满足以下两个条件:axiayi,i,maxjayj,j,m.()式()中每个解构造的角度向量pa(,m)通过ia r c c o sPioPipPioPip求得,o为当前种群的理想点,其中第i个分量zi d e a li定义为zi d e a lim i nnjfi(pj).第i维坐标节点Pi(,k zn a di,),其中k为控制解支配区域的放大系数,它的第i个分量zn a di定义为zn a dim a xnjfi(pj)(n为种群规模),z(zn a d,zn a d,zn a dm).图为A D支配概念图,从图中可以看出,若解x,y根据P a r e t o支配关系进行比较,二者之间没有支配关系.但若按照A D支配关系进行比较,支配区域扩张,此时xa n g l ey.图A D支配概念图F i g T h ec o n c e p to fA Dd o m i n a n c er e l a t i o n西安工业大学学报第 卷 网格角度支配为直观解释所提出的 A D支配的概念,图为此支配关系在两目标空间下的情景,阴影部分为当前种群中任意解x的 A D支配区域.如图所示,假设比较任意两个解x和y间的优劣,若两个解之间距离小于阈值,选用 支配计算其适应度值,以提升接近P a r e t o前沿时解分布的均匀性;若两个解之间距离大于或等于阈值,选用A D支配计算其适应度值,降低了远离P a r e t o前沿时优秀解被支配掉的概率.解x经过 A D支配后的适应度向量为f(x)(f(x),f(x),见定义,而fi(x)的计算见式().图 A D支配概念图F i g T h ec o n c e p to f A Dd o m i n a n c er e l a t i o n定义设x,y为决策空间中任意两个解,x经过 A D支配后的 适 应 度 向 量 的 第i个 分 量fi(x)定义为fi(x)Bi(x)xifi(x)fi(y)ifi(x)fi(y)i,y为任意解,()式中:xi为A D支配中构造的解x的角度向量;Bi(x)为 支配中定义的解x的鉴定向量,x的适应度为f(x)(f(x),f(x),fm(x),i为阈值.定义对于式()中的MO P问题,设x,y为决策空间中任意两个解,称x A D支配y(记为x a n g l ey)当且仅当满足以下条件:fi(x)fi(y),i,mfj(x)fj(y),j,m,()新角度支配关系的多目标进化算法文中以N S GA I I算法为例说明如何将 A D支配整合到基于P a r e t o支配的算法框架中.算法 A D支配方法输入:种群P中任意两个解x、y,解之间的对比阈值输出:x、y之间的 A D支配关系S t e p:计算x、y间欧式距离d.S t e p:计算x、y的角度向量px和py,计算x、y的鉴定向量B(x)和B(y).S t e p:当d时,若xA D支配y,则x A D支配y;若yA D支配x,则y A D支配x;否则,x、y互不 A D支配.S t e p:当d时,若x 支配y,则x A D支配y;若y 支配x,则y A D支配x;否则,x、y互不 A D支配.S t e p:输出任意两个解x、y间的 A D支配关系比较.算法新角度支配关系的多目标进化算法输入:种群规模N,最大迭代次数Tm a x g e n输出:最末代种群Pm a x g e nS t e p:初始化迭代计数器t.S t e p:随机生成种群大小为N的初始种群P.S t e p:根据二元锦标赛选择法构建交配池Pm a t i n g.S t e p:对Pm a t i n g进行交叉、变异操作,产生子代种群Q.S t e p:合并父代种群P和子代种群Q:RPQ.S t e p:根据算法对中间种群R中任意两个解间的 A D支配关系进行比较.S t e p:根据 AD支配关系将种群P划分为l层的非支配层(F,F,Fl).S t e p:当满足PFjN,则PPFj.S t e p:当PFjN,计算Fj的拥挤距离.S t e p:从Fj中删除k个拥挤距离最大的解:kPFjN.S t e p:Fj中保留下的解和P构成新的种群P.S t e p:重复步骤到步骤,直至达到最大迭代次数Tm a x g e n,转至步骤.S t e p:输出最末代种群Pm a x g e n.时间复杂度分析对采用 A D支配的一次种群排序过程来说,N为种群大小,M为目标数,其步骤为:计算每个个体在每个 目标下的角度 值,其 时 间 复 杂 度 为O(NM);计算每个个体在每个目标下的网格适应度值,其时间复杂度为O();进行非支配排序,第期张浩楠,等:一种新角度支配关系的多目标进化算法其时间复杂度为O(N).综上,采用 A D支配的一次种群排序过程的时间复杂度为O(MNN).实验结果与分析文中采用G D,I G D 和S P A C I NG 评价指标,选取D T L Z 和WF G 测试问题集,将A D N S GA I I与其他四种多目标进化算法的性能进行比较.关于对比算法的选取,将支配和A D支配嵌入N S GA I I框架,构造 N S GA I I和A D N S GA I I,作为改进支配关系的对比算法.选择目前新提出的基于参考点支配的R P D N S GA I I和基于差分的多目标进化算法MO E A/D D E作为另外两个对比算法.将五类算法生成解集合的收敛性和分布性进行比较.测试问题、评价指标及其相关参数设置 测试问题文中实验选用个优化目标下的D T L Z和WF G两个系列的测试问题,考察算法求解多目标优化问题的能力.上述两个测试问题集具有多种P a r e t o前沿特征,其中D T L Z测试问题集包含具有非凸、有偏、不连续、多模、混合等问题特性的测试函数,WF G测试问题集包含具有欺骗、偏转、多模等问题特性的测试函数,以及一组包含多种几何结构的形状函数.为了保证实验公正性,文中实验均在C P U GH z、内存 G B的P C上运行,所有算法均在P l a t EMO平台上运行,编程工具为M a t l a bR a.评价指标为综合评估算法的收敛性和多样性,文中采用以下个性能指标,即世代距离(G D)、反转世代距离(I G D)和空间评价方法(S p a c i n g).综合个性能指标,能够很好地度量解集的收敛性和多样性.采用G D度量作为收敛性评价指标,它表示算法所求得的非支配解集P Fk n o w n中的个体与P a r e t o最优解集P Ft r u e之间的距离,其表达式为G D(nidpi)/pn,()式中:n为P Fk n o w n中的向量数;p为;di为所获得解集中向量与P Ft r u e中最近向量之间的欧氏距离.该指标越低,表示算法的收敛性越好.采用I G D评价指标,度量了P a r e t o最优解集P Ft r u e中的个体到算法所求得的非支配解集P Fk n o w n的平均距离,其表达式为I G DjPd jn,()其中,d j m i njPji为P a r e t o最优前沿上的点j到所获得解集P中个体i的最小欧氏距离.I G D越小,表示近似P a r e t o前沿的性能越佳.采用S p a c i n g评价指标,能够衡量算法所求得的非支配解集P Fk n o w n中个体的分布是否均匀,其表达式为S p a c i n g(P)Pi(ddi)P,()其中,di m i nj(|fi(x)fj(x)|fi(x)fj(x)|fim(x)fjm(x)|)(i,j,n),m m为目标数.d为所有di的平均值,P为待评价解集个体数.该指标越低,表示算法的分布性越好.参数设置文中种算法的对比实验均采用以下设置:进化种 群 规 模 为 ,每 次 运 行 最 大 评 估 次 数 为 ,进行交叉操作时使用模拟二进制交叉算子(S B X算子),交叉率pc为,进行变异操作时使用多项式变异算子(PM算子),变异率pm为/n(n为决策变量数目),交叉、变异算子参数c及m均为.另外,采用D T L Z和WF G测试问题时,网格大小取值为 ,放大系数k取值为 ,阈值取值为 .结果与分析为验证 A D支配在多目标优化中的有效性,用 A D支配、A D支配和支配替换N S GA I I算法中的p a r e t o支配,构造 A D N S GA I I、A D N S GA I I以及 N S GA I I算法,将 A D N S GA I I与N S GA I I、A D N S GA I I、R P D N S GA I I以及MO E A/D D E算法进行比较.为减少随机因素对算法性能评估的影响,将上述种算法在所有测试问题上均独立运行 次.表表给出算法性能指标的统计结果,加粗标记为对应指标上表现更好,(/)为一致性检验结果.不同测试问题中的G D比较分析分 析 A D N S GA I I与 N S GA I I、A D N S 西安工业大学学报第 卷GA I I、R P D N S GA I I以及MO E A/D D E在解决多目标优化问题时收敛性上的差别.表给出了上述种算法在D T L Z和WF G测试问题集中 个测试问题上所获得的G D均值与标准差.由表可知,在 个测试问题中,A D N S GA I I获得了个最佳G D均值,R P D N S GA I I获得了个最佳G D均值,A D N S GA I I获得了个最佳G D均值,MO E A/D D E获 得 了个 最 佳G D均 值,N S GA I I没有获得最佳G D均值.同时由一致性检验结 果 可 知,与 N S GA I I、A D N S GA I I、R P D N S GA I I和MO E A/D D E相比,A D N S GA I I分别在、和 个测试问题上有更好的表现.由于使用 A D支配的进化算法在大多数问题上都能获得更好的收敛性,因此使用 A D支配的进化算法在解决多目标优化问题上更能快速、准确得找到最优解集,具备较好的收敛性.表种算法在D T L Z和WF G问题集上获得的G D均值与标准差T a b T h eG Dr e s u l t s(m e a na n dS D)o b t a i n e db yt h e f i v ea l g o r i t h m so nt h eD T L Za n dWF Gt e s t s u i t e s测试问题 A D N S G A I I N S G A I IA D N S GA I IR P D N S GA I IMO E A/D D ED T L Z e (e )e (e )e (e )e (e )e (e )D T L Z e (e )e (e )e (e )e (e )e (e )D T L Z e (e )e (e )e (e )e (e)e (e )D T L Z e (e )e (e )e (e )e (e )e (e )D T L Z e (e )e (e )e (e )e (e )e (e )D T L Z e (e )e (e )e (e )e (e )e (e )D T L Z e (e )e (e )e (e )e (e )e (e )WF G e (e )e (e )e (e )e (e )e (e )WF G e (e )e (e )e (e )e (e )e (e )WF G e (e )e (e )e (e )e (e )e (e )WF G e (e )e (e )e (e )e (e )e (e )WF G e (e )e (e )e (e )e (e )e (e )WF G e (e )e (e )e (e )e (e )e (e )WF G e (e )e (e )e (e )e (e )e (e )WF G e (e )e (e )e (e )e (e )e (e )WF G e (e )e (e )e (e )e (e )e (e )(/)/(/)(/)(/)(/)不同测试问题中的I G D比较分析分析 A D N S G A I I与 N S G A I I、A D N S G A I I、R P D N S G A I I以及MO E A/D D E在在解决多目标优化问题时收敛性和多样性上的差别.表给出了上述种算法在D T L Z和W F G测试问题集中 个测试问题上所获得的I G D均值与标准差.由一致性检验结果可知,在 个测试问题中,与 N S G A I I、A D N S G A I I、R P D N S G A I I和MO E A/D D E相比,A D N S GA I I分别在、和 个测试问题上有更好的表现.由此可见,新提出的算法较之N S GA I I、A D N S GA I I和MO E A/D D E,具有明显较优的综合能力上的优势.关于 A D N S GA I I与R P D N S GA I I的对比分析,A D N S GA I I采用一种将支配和A D支配进行有效结合的支配关系对解集进行排序,R P D N S GA I I采用基于参考点的支配关系,能够使用一组分布良好的参考点对解集进行排序,以上两个算法都能在测试问题上取得相似的效果.综上,使用 A D支配的进化算法,其具有较优的收敛性和多样性之能力.不同测试问题中的S p a c i n g比较分析分 析 A D N S GA I I与 N S GA I I、A D N S GA I I、R P D N S GA I I以及MO E A/D D E在解决多目标优化问题时分布的多样性上的差别.表给出了上述种算法在D T L Z和WF G测试问题集中 个测试问题上所获得的S p a c i n g均值与标准差.由表可知,在 个测试问题中,A D N S GA I I获得了 个最佳S p a c i n g均值,A D N S GA I I获得了个最佳S p a c i n g均值,MO E A/D D E获得了个最佳S p a c i n g均值,R P D N S GA I I和 A D N S GA I I没有获得最佳S p a c i n g均值.同时由一第期张浩楠,等:一种新角度支配关系的多目标进化算法致性检验 结果可 知,与 N S GA I I、A D N S GA I I、R P D N S GA I I和MO E A/D D E相 比,A D N S GA I I分别在、和 个测试问题上有更好的表现.综上所述,使用 A D支配的进化算法求得的解集分布更均匀,A D支配具有更优的多样性保持能力.表种算法在D T L Z和WF G问题集上获得的I G D均值与标准差T a b T h e I G Dr e s u l t s(m e a na n dS D)o b t a i n e db yt h e f i v ea l g o r i t h m so nt h eD T L Za n dWF Gt e s t s u i t e s测试问题 A D N S G A I I N S G A I IA D N S GA I IR P D N S GA I IMO E A/D D ED T L Z e (e )e (e )e (e )e (e )e (e )D T L Z e (e )e (e )e (e )e (e )e (e )D T L Z e(e)e(e)e(e)e (e )e (e)D T L Z e (e )e (e )e (e )e (e )e (e )D T L Z e (e )e (e )e (e )e (e )e (e )D T L Z e (e )e (e )e (e )e (e )e (e )D T L Z e (e )e (e )e (e )e (e )e (e )WF G e (e )e (e )e (e )e (e )e (e )WF G e (e )e (e )e (e )e (e )e (e )WF G e (e )e (e )e (e )e (e )e (e )WF G e (e )e (e )e (e )e (e )e (e )WF G e (e )e (e )e (e )e (e )e (e )WF G e (e )e (e )e (e )e (e )e (e )WF G e (e )e (e )e (e )e (e )e (e )WF G e (e )e (e )e (e )e (e )e (e )WF G e (e )e (e )e (e )e (e )e (e )(/)/(/)(/)(/)(/)表种算法在D T L Z和WF G问题集上获得的S p a c i n g均值与标准差T a b T h eS p a c i n gr e s u l t s(m e a na n dS D)o b t a i n e db yt h e f i v ea l g o r i t h m so nt h eD T L Za n dWF Gt e s t s u i t e s测试问题 A D N S G A I I N S G A I IA D N S GA I IR P D N S GA I IMO E A/D D ED T L Z e (e )e (e )e (e )e (e )e (e )D T L Z e (e )e (e )e (e )e (e )e (e )D T L Z e (e )e (e )e (e )e(e)e (e )D T L Z e (e )e (e )e (e )e (e )e (e )D T L Z e (e )e (e )e (e )e (e )e (e )D T L Z e (e )e (e )e (e )e (e )e (e )D T L Z e (e )e (e )e (e )e (e )e (e )WF G e (e )e (e )e (e )e (e )e (e )WF G e (e )e (e )e (e )e (e )e (e )WF G e (e )e (e )e (e )e (e )e (e )WF G e (e )e (e )e (e )e (e )e (e )WF G e (e )e (e )e (e )e (e )e (e )WF G e (e )e (e )e (e )e (e )e (e )WF G e (e )e (e )e (e )e (e )e (e )WF G e (e )e (e )e (e )e (e )e (e )WF G e (e )e (e )e (e )e (e )e (e )(/)/(/)(/)(/)(/)西安工业大学学报第 卷 不同测试问题中的收敛速度比较为更加直观地比较 A D N S GA I I、N S GA I I和A D N S GA I I的寻优性能,选取个优化目标下的D T L Z和WF G两个问题集作为测试问题,各算法在上述测试问题集上均独立执行 次取均值,每次运行最大评估次数为 ,以获得稳定的G D和S p a c i n g均值.图图 为种算法在上述测试问题上的G D和S p a c i n g指标的进化轨迹图.其中,横坐标为进化代数,纵坐标为指标值.由图图 可以看出,三种算法随评估次数的增加,它们所获得的G D均值和S p a c i n g均值都随进化代数的增长总体上呈下降趋势,并且都能较快地下降至一个相对较小的值,而在后续进化过程中,指标值呈现出缓慢变小的趋势.但对大多数问题而言,A D N S GA I I算法获得的G D均值和S p a c i n g均 值 是 在 三 者 中 下 降 最 快 的.因 此,图图 中各算法获得的轨迹直观地表明了A D N S GA I I算法比其他两种算法能够较快地获得高质量解集.图种算法在维D T L Z、D T L Z 测试函数上的G D、S p a c i n g进化轨迹图F i g T h eG Da n dS p a c i n gr e s u l t so f t h e t h r e ea l g o r i t h m so nt h eD T L Z a n dD T L Z o v e rg e n e r a t i o n s第期张浩楠,等:一种新角度支配关系的多目标进化算法图种算法在维D T L Z、D T L Z 测试函数上的G D、S p a c i n g进化轨迹图F i g T h eG Da n dS p a c i n gr e s u l t so f t h e t h r e ea l g o r i t h m so nt h eD T L Z a n dD T L Z o v e rg e n e r a t i o n s图种算法在维D T L Z、D T L Z 测试函数上的G D、S p a c i n g进化轨迹图F i g T h eG Da n dS p a c i n