论文研究-基于初集排序的Pareto非支配解集构造算法.pdf

所需积分/C币:50 2019-09-20 21:00:08 939KB .PDF
收藏 收藏
举报

论文研究-基于初集排序的Pareto非支配解集构造算法.pdf,  针对具有大型解空间的多目标决策问题,为进一步提高多目标决策的效率,快速且有效的非支配解集构造方法值得探究.给出非支配关系性质、初始非支配解集(简称初集)及非支配解集构造的有关定义与定理.在此基础上,依据有序集理论与运算规则,提出基于初集排序方法的Pareto非支配解集构造算法.该算法应用集合排序的方法,对有序的可行解集与有序
962 系统工程理论与实践 第38卷 如果庄家不被任何其它解支配,则庄家即为非支配个体,否则庄家在该趟比较结束时也被淘汰岀局.继续下 趟比较,直至可行解集为空根据非支配关系不具有传递性的原理,2009年杨平等提出选举法构造非支配 解集,从可行解集中选择两个互不支配的可行解担任竞选个体,再依次从可行解集中选取一个可行解与两个 竞选个体进行比较,败者被淘汰出局,胜者成为新的候选竞选个体.并继续该趟比较,一趟比较后,两个竞选 个体即为非支配解.据此方法进行下一趟比较,直至可行解集为空2.除此之外,一些学者从不同角度提出 些有效的构造方法,如两阶段方法23、目标功效范围法24、聚类图工具2、模糊几何的反演点方法2 和枚举法②27等. 在上述不完全比较方法中,当非支配解片多数时,算法计算时间复杂度接近完全比较的方法.日标排序 方法较为快速,但时间复杂度也为O( m Mlog n),m为目标数,N为可行解空间综合目标排序、排除法和二 叉树等方法的优势,进一步减少支配关系比较次数,本文提出一种基于初始非支配集,并且待比较的可行解 集与非支配解集均有序的构造方法 2 Pareto最优解的定义与定理 因尤需经验和偏好信息,目标函数尤凸性要求, Pareto非支配排序是多目标决策的常用方法之一.以最 小化多目标决策间题为例,具有n个连续型决策变量,X={x2,x2,……,mn},m个目标函数.a个不等式约束 和b个等式约束的多目标决策问题( multi-objective problem.MOP)可表示为141 minF(x)={1(x),f2(x),…,fm(x)} st.G(x)={g1(x),g2(x),……,ga(x)}≤0 H(x)={h1(x),h2(x),…,hb(x)}=0 ∫k(x)为第k个日标函数k=1,2,……,m.9a(x)为第讠个不等式约束,=1,2…,a.h/(x)为第j个等 式约束,=1,2,…,b.基于上述问题,给出相关定义2151821与定理如下 定义1满足公八(1)约東条件的解m;称为多目标决策问题的第i个可行解,可行解集X={|i 1,2,…,N,G(x:)≤0,H(xz)=0},N=X 定义2对于x;可∈X,若k=1,2,…,m,k(x;)<()则称x与x具有支配关系,x:支配x, 记为az}x;若k=1,2,…,m,k(x;)≤(x;),且丑=1,2,…,m,f(x;)<f(x;),称x;弱支配x,记 为 定义3对于,x;∈X,若k,=1,2,…,m,k≠l,使得fk(xz)<f(x1),且f1(a;)<f(x),则称rz 与其有非支配关系,即不存在x2>x,也不存在x1>x2 定义4对于∈X,若x∈Ⅹ, N,j≠i,不存在>x,则称x为非支配解(也称为 Pareto最优解),即不被任一其它可行解支配的解.非支配解集Xf≌X称为 Pareto前沿 定义5对于*∈X.若;∈X,i=1,2,…,N,;≠m*,存在/k(x*)</k(r;),k=1,2,……,m,则称 α*为MOP最优解,即支配任一其它可行解的解 定义6 Pareto得分是比铰两个解的支配关系确定的分值,记为v(x).若 则V(x)=1, V(x)=-1分.反之,V(x)=1,V(x)=-1.若m与m;具有非支配关系,则v(m2)=V(r;)=0.规定目 标值相等的可行解的 Pareto得分为0. 引理支配关系传递性定理1.若h,x;x;∈X,mh1>x2,且x>x,则xh>x 定理1多目标决策冋题的可行解集中至少存在一个非支配解. 证明反证法.假设可行解集不存在非支配解,即所有可行解均为支配解.设∈X为可行解集X的 任一可行解,则一定存在可行解x2,使得x2x,构建支配关系序列为{x2,}.同理,存在可行解xk,使得 xk>x,支配关系序列为{xk,x;,x}.依此查找,直到所有可行解进入支配关系序列.设cn为序列第个 元素、即{x,,xk,x,x}.由支配关系传递性定理可知、x>x,根据假设,xn也是一个支配解,在支配 关系序列中,只有x能够支配xh,即x;>x.这显然与支配关系传递性定理矛盾,故假设不成立,定理1 得证 第4期 汪勇.等:基于初集排序的 Parcto非支配解集构造算法 定理2非支配关系不具有传递性若xh,x,m∈X,mh与x具有非支配关系,;与x;具有非支配关 系,则mh与x具有非支配关系不成立 证明反例法,根据定义3,对于x2,x1∈X,假设玉k,=1,2,…,m,k≠l,使得fk(xh)<k(x2), f(xh)>f1(x;),fk(x2)>fk(x),f1(x;)<f(x)条件成立,则由定义3可知,xh与x:、x与x;具有非支配 关系 当∫k(x1)<(xn),1(x)<f(n)时,上述假设依然成立,则由定义2可知,x>x,即h与x;具 有支配关系 因此,非支配关系不具有传递性定理成立.定理2表明,一个可行解成为非支配解的充要条件是不被任 何其它可行解支配.因而,在构造非支配解集时,须与所有可行解进行支配关系比较 定理3设F是可行解集X的目标排序集,记为 F={k(xm(k,)k(xm(k,)≤(xm(k,+1)h=1,2,…,m,=1,2,……,N} (2) p(k,讠)表示目标k排序集中第i个目标值对应的可行解mn(k在Ⅹ中的位置.若Xa={xmk,1)|k 1,2,…,m},则ⅹa称为初始非支配解集(简称初集),1≤|Xa|≤m 证明当k=1时,由已知条件可知,f1(xp(l,)<f1(an(),2=2,…,N.因此,对于V=1,2,……,m, f(xn(1,)<(xn(1,1)不成立,即不存在xn(1、)>xm(1,1),由定义4可知xn(1,1)是非支配解 同理可证明,当k-2,……,m,xnk,1)均为非支配解.故Xa是非支配解集 当A(xn(k,1)=几1(xp1)时,k≠l,m(k,)=xn(1),因此,1≤|Xa|≤mt 依据定理3,构造初始非支配解集 推论当|Xa|=1时,xp(k)为最优解,且Xa=Xf 证明|Xa=1表明只有一个非支配解 Tp(k,1),k=1,2 (1,1) 2,1) p(m,1)为 同一可行解.设Xk是X关于目标k的排序集,Xk={mn(k=1、2,…,N},对于mp(k,)∈Xk都有 Tp(k,1)>xp(.,),由定义5可知x(k,1)为最优解,显然,仅有一个最优解的非支配解集Xa=Xf 定理4设ⅹ∫(Xa≤r)为当前非支配解集,若可行解x(x∈Xk-Xr)不被X任一非支配解支配 则x也是非支配解 证明反证法,假设x是支配解,则存在一个非支配解y>x,fk(y)<f(x) 因Xk是排序集,在构造非支配解集时,y先于x进入非支配解集Xf,即y∈Xr这与条件x不被Xf 任一非支配解支配矛盾,故假设不成立,x是非支配解 依据可行解的攴配关系判定,应用定理4构造可行解空间的非支配解的完整解集 3非支配解集构造算法 31算法设计 建立一个N×N矩阵M,M由m1,m2…,N两两比较的 Pareto得分构成依次比较n;与”的支配 关系,据定义6给出相应位置的 Pareto得分,直至M所有位置打分完毕按行查找可行解的 Pareto得分情 况,由定义6可知,所有不存在-1得分的行对应的可行解为非支配解.这种通过可行解两两之间完全比较 排序的方法( complete comparison sorting,CCS)是常见的非支配排序方法,时间复杂度为O(mN2),代表算 法有SPEA和NSGA等 M下三角与上三角负对称,因此,只须计算上三角矩阵UTM,应用矩阵转置方法构造M M=(UTM)+UTM UTM)是UTM的转置矩阵,这种非支配解构造方法称为基于矩阵转置的排序方法 matrix composi tion sorting,MCS).此时,时问复杂度为O(mN(N+1)/2),计算复杂度较CCS降低一倍.为计算 Pareto得 分,CCS和MOS需要确定任何两个可行解的支配关系.据定义4,在可行解比较过程中,一旦出现支配关系, 即停止与其它可行解的比较,据此可进一步改进上述两个算法,得到一个不完全比较排序的方法( incomplete comparison sorting,ICS,该算法的平均计算复杂度为OmN2/2).代表算法有目标排序法19、庄家法、擂 964 系统工程理论与实践 第38卷 台赛法12和选举法2等.ICS算法不记录每个可行解的 Pareto得分,适合于构造非支配解集,但不能确 定非劣解集 对于巨型解空问的MOP,上述三类算法的时问复杂度依然较高.借鉴目标排序法、排除法和二叉树法 的思想根据上述定理设计一种新的非支配解集构造算法,称为基于初集排序的构造算法( (initial set sorting, ISS).初集是指初始非支配解集.定理1表明多目标决策问题存在非支配解,它是所有非支配解集构造算法 的前提.应用ISS算法构造非支配解集的过程如图1所示. 按目标1升序排序的可 依次取X 与x左侧 按目标2排序的非支配 行解集(不包含初始非 可行解 初集比较 解集(含按目标1排序的 支配解x1={x,1 初始非支配解) Lp(1.2),……,xp(1,N 支配 支配否 x2,1),…,xp(1),…} 支配 非支配 按插入规则,将非支配/支配否 按査找规则,与x右侧非支 可行解插入X 配解比较目标3至目标m 图1非支配完整解集构造过程 首先,对所有目标进行排序,依据定理3构造初始非支配解集,初始非支配解按照目标顺序逆序排列.初 始非支配解集的构造减少了非支配排序的比较次数.接着,所有可行解按目标1升序排序,构造不包含初始 非支配解的可行解集.最后,依据定理2,依次将叮行解集中的可行解与非支配解集中所有非支配解进行支 配关系比较根据定理4,若为非支配解,则按ISS插入规则将其插入非支配解集.非支配解集由两部分组成, 第一部分为按目标顺序逆序排列的初始非支配解集,此部分不包含按目标1排序的初始非支配解.第二郾分 为按目标2排序的非支配解,包含按目标1排序的初始非支配解.当可行解与第二部分非支配解进行支配关 系比较时,按照ISS查找规则,只需与目标2小于可行解的非支配解比较其余目标的数值关系,进一步减少 非支配排序的比较次数.新增的非支配解按目标2插入到第二部分.ISS算法具体步骤如下: 1)初始参数设定,设置目标数m与可行解空间N,建立目标矩阵如式(4) fi(1) f1(r2) f I ( N) ∫2(x1)/2(x2) 2)初始非支配解集Ⅺr构造.对F按目标值升序排序,γ(K,υ)记录各目标值在原矩阵中的位置,可行解 排序集Xh={mn(k,)k=1,2,…,m,=1,2,…,N} 3)根据Xk,依次将非支配解添加至Xf,Xf={x(k,1k=1,2,…,m}删除Xf中的重复卡支配解 初始非支配解排序规则矩阵X反转,X={xp(k,)k=m,m-1,…,1}.按目标1排序的非支配 解排列在Xr右侧,以便与按目标1排序的可行解集X1比较,Ⅹf|=r 5)判定ⅹ∫中初始非支配解数量.若τ-1,表明可行解集存在唯一最优解,x*-(1):算法结束.否 则,转下一步 6)构造不包含初始非支配解的可行解集Ⅺ1.基于初始非支配解的顺序考虑,选择按日标1排序的解集 X1作为可行解集,删除其中的初始非支配解,X1=X1-Xf,X1={xp(1,)2=1.2,…,N-r}X1是一个 有序集|X1 7)可行解¥1与非支配解集Xr支配关系比较令NS=0,NS为新增的非支配解 8)依次取X1中可行解xp(,),=1,2,…,N-r,与Xr中1,7-1的初始非支配解进行支配关系比 较(除按目标1排序的初始非支配解外的初始非支配解),若x(1、)是支配解,则终止比较,转向X1的下一 可行解,重复此步骤.否则,转下一步 9)査找规则.x(1,与Xf中,r+NS的非支配解进行支配关系比较(包含按目标1排序的初始非文配 解这些非支配解按目标2降序排列令Xf(7)=ms,T∈,+NS],奋找满足条件f2(xnl)≤f2(xp(1, 第4期 汪勇.等:基于初集排序的 Parcto非支配解集构造算法 的非支配解.若查找为空,即xp1,)不在该非支配解序列中,表明xn1,)是非支配解,将xm,x添加到Xr 最右侧,NS=NS+1.否则,记录查找到的非支配解位置RP,转下一步 10)插入规则xm(,)依次与X中[r+RP(1)-1,+NS的非支配解比较目标3至目标m的支配关系, 若,是支配解则终止比较,返回步骤8).否则,xn(1,是非支配解,将其插入到X中第r+RP(1)-2 个非支配解之后,NS一NS+1,返回步骤8),直到X1中所有可行解比较完毕为止 1)输出非支配解集X ISS算法与文献[15]设计的基于性质定理的非支配解集构造方法(NTCM)的区别在于,SS依据有序 集理论与运算规则,减少排序的比较次数.其可行解集与非支配解集均是有序的,非支配解集是由有序初始 非支配解及构造中的有序非支配解集组成.NTCM借鉴的是排除法、庄家法和擂台赛法,按可行解自然顺序 比较支配关系,且构造中的非支配解集不一定是解空间的非支配解,存在当前非支配解. 32时间复杂度分析 根据Kng等提出的非文配排序算法时间复杂度的计算方法冏,分析ISS算法在最坏、平均和最好三种 情形下的时间复杂度 1)最坏情形下时间复杂度 假设所有可行解均为非支配解,并且Ⅹ1的目标1与目标2均为升序排列,此时比较次数最多.X1中可 行解与Xr中[1,-1]的初始非支配解比较次数为 q1(N,m,r)=m(N-r)(r-1) X1中可行解与Xf中{,r+NS的非支配解比较次数为 92(N,m,r)=(m-2)(1+2+…+N-r)=(m-2)(-7)(N-+1)/2 总比较次数为 9(N,m,)=91(N,m,)+92(N,m,r)=m(N-7)(-1)+(m-2)(1+2+…+N-r) (m-2)(N-7)(N-x+1)/2=(m-2)N2+(4r-mr-2)N+2r(1-r) 给定m,当2≤”≤m时,g(N,m,r)≥0,解不等式得: N>2.r=2 2<<m 式(8)表明,解空间应大于等于初始非支配解数量,一般取N≥m.此时,由式(8)可知,ISS时间复杂 度为O(m-2)N2) 2)平均时问复杂度 假设有半数可行解均为非支配解,根据定理4和式(5)、式(6)得非支配解的比较次数为 g1(N,m,)=m(N/2-7)(7-1)+(m-2)(N/2-7)(N/2-7+1)/2 (9) 假设有γ-1个支配解被不包括r(,)的初始非支配解支配,N/2-r+1其余支配解被其余非支配解 支配、且经过一半次数的比较,则支配解的比较次数为 g2(N,m,r)=m(r-1)(r-1)/2+(m-2)(N/2-r+1)(N/2-r+1)/2 (m(x-1)2+(m-2)(N/2-r+1)2)/2 当N≥7,且r→1时,不包括πn(l,1的初始非支配解参与比较次数可忽略不计,因此,根据式(9)和 式(10)得 lin g(N, In, r)=lil (91(N, IL, r)+92(N, IL, r)=(7-2)N/ 4 (11) N→③.T→1 →,7→ 因此,ISS平均时间复杂度为O(m-2)N2/4) 3)最好情形下时问复杂度 当r-1时,ISS不需要进行任何支配关系比较即可获得唯一的非支配解.时间复杂度为O(1).CCS和 MCS时间复杂度保持不变,在只有唯一非支配解时,ICS和NTCM算法最好情况下时间复杂度为O(m(N 1).五个算法在不同情形下的时间复杂度如表1所示 966 系统工程理论与实践 第38卷 表1非支配解集构造算法时间复杂度 非支配解集构造方法 最坏情形下时间复杂度平均时间复杂度最好情形下时间复杂度 完全比较排序(CCS O(mN) O(mN O(mN) 矩阵转置排序(MCS) O(mN(N+1)/2)O(mN(N+1)/2)O(mN(N+1)/2) 不完全比较排序(ICS omnI O(mN2/2) O(m(N-1) 基于性质定理的构造法(NTCM)O(mN(N-1)/2)OmN(N+1)/4)O(m(N-1) 初集排序(ISS) O(m-2)N2) O(m-2)N2/4) O(1) 4算法性能测试实验 41实验设计 选择ZDT1~ZDT3、DILZ1及DTLZ3作为测试函数决策变量数n-100.ZDT1的 Pareto前端是 凸的,ZDT2的 Pareto前端是凹的,ZDT3的 Pareto前端是非连续的.ZDT系列函数形式见式(12) mIn fi(si) min f2()=g(1-(/g)a-((/ g)sin(10rf1)b) ZDT1ZDT3 9(x)=1+9∑ st.0≤xz≤1,t=1,2 ZDTI~ZDT3函数参数分别为a=1/2,b=0;a=2,b=0:a=1/2,b=1 三个目标的DTLZ1函数 Pareto前端是一个线性平面.DTLZ1函数形式见式(13) mIn fi( r) m1m2…mm-1(1+9() 1 nin(a)=2122m-(1-xm-k+1(1+9(x) DTLZ1= (1 (x)=1001-m)+∑(x;-0.5)2-cos(20(x2-0.5)) s.t.0≤x;≤1.=1,2,…,m,m≥3,k=3,4 n DTLZ3函数 Pareto前端是凹的,DTLZ3函数形式见式(14).其中g(x)同DTLZ1函数 min fi(a)=(1+g(a)cos(C1/2)cos(a2/2) f2(a)=(1+g())cos(c1/2)sin(a2/2 DTLZ3 in/(a)=(1+y(x)cos(1x/2)sn(x1/2) 9(x)=1007-m)+∑(x2-0.5)2-cos(207(x2-0.5) i-rrl st.0≤x;<1.t=1,2,…,7 选择CCS的NSGA-算法、ICS的擂台赛法( Arena' s Principle,AP)、MCS以及NTCM作为比较算 法.在相同硬件和软件环境下,测试各个算法非支配解集构造时间,即算法的计算时间.算法程序编程与执行 环境为 Windows7和 Matlab6,1,硬件环境为CPU17GHz,4GB内存的笔记本.ZDT1~ZDT3是双目标 测试函数,每个算法分别按照函数和解空间进行实验解空间设置为N=100,1000,20,05000.共60组实 验.DILZ是高维测试函数,函数目标分别设置为m=3和m=4.每个算法分别按照目标和解空间进行 实验.解空间设置为N=1000,2000,5000,1000共40组实验.NICM和ISS取100次实验结果的平均 值作为最终实验结果,其它算法取10次实验结果的平均值作为最终实验结果.ZDI1~ZD3测试结果见表 2,DTLZ1测试结果见表3 为进一步测试ISS算法在高维目标和不同解空间情形下的时间性能,选择DTLZ1函数进行测试.式(13) 中,分别取m=3,4,8.测试结果见表4所示,m=8时为10次实验结果的平均值,其它数据为50次实验 结果的平均值 42实验分析 1)ZDT1~ZDT3测试结果分析 第4期 汪勇.等:基于初集排序的 Parcto非支配解集构造算法 967 表2非支配解集构造时间(ZDT1~ZDT3测试) 测试函数目标解空间非支配解NSGA- II MCS AP NTCM ISS 100 46 0.05010.03570.02290.01010.0080 1000 121 5.02953.42890.80120.14740.0203 ZDT1 2000 163 21.175413.81692.41490.29870.0329 5000 200 164.097089.72228.56440.83650.1124 100 0.0496 0.03570.02250.01000.0031 1000 122 520423.48350.83370.16600.0213 ZDT 200C 155 21.631013.67192.37120.31420.0399 5000 178.558087.48808.9607094320.1153 100 0.050 0.03430.01680.00370.0003 1000 5.1511 0.71040.09390.0198 ZD 2000 142 21.621513.62572.05080.21840.0374 5000 195 16691391.29448.32660.59530.1030 表3非支配解集构造时间(DTLZ1测试) 测试函数目标解空间非支配解NSGA- I MCS AP NTCM ISS 1000 285 5.3472 3.54121.50700.38500.1063 2000 DTLZI 21.898114.08064.31710.74070.1980 5000 503 166089088.5475172972244310.4023 10000 590 870.3565283.35204583404.57080.7426 1000 570 5.3617 3.6004 2.2835 0.84380.5149 2000 DTLZ 3522876014.22728.5582262161.3494 5000 1640195.198792981340.61210.27714.1635 10000 24749869810353.3289138.002326.21589.1400 表4ISS算法非支配解集构造时间(DTLZ1测试) 目标(m)N=1000N=2800N=4600N=6400N=8200N=10000 0.1063 0.3111 0.4080 0.5549 0.6610 0.7426 4 0.5149 22478 4.0472 7.4560 9.1400 2.3735 14.401 34.224 57.406 86.641 125.796 从表2可知,在相同解空间下,ZDT1~ZDT3三个测试函数的结果基本一致ISS算法构造非支配解集 的计算时间远低于NSGA-I、MCS和AP算法,NSGA-I计算时间是ISs的200倍以上,AP是ISS的 40倍以上.NICM算法构造时间是ISs的7倍以上.图2分别表示不同解空间下(N=100,N=1000 N=5000)的各个算法计算时间比较.从图2可以看出,随着解空间的增大,NS(A-Il与MCS算法所花费的 时间越来越大,前四个算法的计算时间与ISS比值也越来越大.当N=5000时,最长计算时间的NSGA-1l 算法已是ISS算法的1000多倍.表明在两个目标情形下,ISS算法的时间性能随着解空间增大其优势越来 越显著. 网NSGA-I图MCS日AP 团 NSGA-II國 MCS AP ANSGA-II MCS 旦AP 口NTCM■IsS 口NTCM口IsS 口NTCM■IS 0.05 6 1501月 女0.03 100 0.01 50 2 ZDTI ZDT2 ZDT3 (a)N=100 (b)N=1000 (c)N-5000 图2ZDT系列测试函数的算法计算时间 2)DTLZ1测试结果分析 观察表2可知,无论是三目标还是四目标,ISS算法构造非支配解的计算时间依然远低于前三个算法, 968 系统工程理论与实践 第38卷 但相对于ZDT系列测试函数,相同解空间下的时间比值减小.当N=5000,m=3时,最长计算时间的 NSGA-II算法是ISS的400倍以上.当N=5000,m=4时, NSGA-II的计算时间则是ISS的50倍左右 表明随着目标的增多,ISS算法时间性能优势下降.图3分别表示不同解空间下(N=1000,N=2000和 N=5000的DTLZ1测试结果比较.随着解空问的增大,目标数对 NSGA-IL和MCS算法的计算时问影响 不大,对AP影响较大,目标数对ISS算法的计算时间影响最大 西NSGA圆MCS_AP 因NSGA-IMCS 日AP ENSGA- II BMCS日AP 口NTCM口IsS 口NTCM口Iss 口 NTCM DISS 250 65432 200 4 205 150 10 l00 5 50 m=4 m (a)N=1000 (b)N=2000 (c)N=5000 图3DTLZ1测试函数的算法计算时间 3)NTCM算法与ISS算法计算时间比较 NTCM是文猷[15提出的最新的非支配解集构造算法,它与ISS算法比较如图4(a)至图4(c)所示 双目标ZDTⅠ测试见图4(a),ISS算法时间性能眀显优于NTCM算法.随着解空间增大,NTCM计算时间 增加较快,ISS计算时间增加较慢.DTLZ1函数测试(m=3)见图4(b)二者时间差距缩小、.DTLZ1函数 测试时(π=4)见图4(∞),二者时间差距进一步缩小.随着解空间增大,ISS计算时间明显增加,但NTCM 最短时问也是ISS的两倍.该组实验表明,随着解空间的增大,尽管ISS算法计算时问明显增加,但相对于 NTCM算法仍具有明显优势. 140 30 n!=3 一NTCM NTCM NTCM -ISS 0.5 10 10010002005000900000 10 l0002000500010000 028466482100 (a)ZDT1解空间 (b)DTLZ(m=3)解空间 (c)DTLZ1(m=4)解空间 解空间(X100) (d) ISS(dTLz1) 图4NTCM与ISS算法计算时间 4)目标与解空间对ISS算法时间性能影响分析 从表4可知、ISS算法计算时问随着目标与解空问的增加而增加.当解空问N=1000时,8个目标的非 支配解集构造时间大约是4个目标的4.6倍左右.N-10000时,约为10.4倍.由表1知,平均情况下,算法 计算时间与目标呈线性增加趋势.图4(d)是不同目标及解空间情形的时间曲线,计算时间基本呈线性关系 当仉=3和侃=4时,解空间的増大对ISS计算时间影响并不显著,但当π=8时,算法计算时间增加明 显.由此可见.日标维数是影响ISS算法计算时间的重要因索. 5)ISS算法构造的非支配解集分析 采用ISS算法构造ZDT1(N=500)、DTLZ1(N=1000)和DTLZ3(N=2000测试函数的非支陀解 集,N=100,并绘制可行解分布如图5所示.ZDT1是连续凸集,图5(a)圆圈表示非支配解,位于可行解 边界、构成 Pareto前沿.图5(b)表示DTLz1测试函数的可行解区域,圆圈表示非支配解,位于可行解区域 下部图5(c)表示的是测试函数DILZ3的可行解分布,星号表示支配解,圆圈表示非支配解.由于非支配 解数量极少,位于支配解下方,不易观察.通过三个测试函数的非支配解集构造,从支配解与非支配解图形分 布来看,ISS算法能够找到所有的非支配解,表明ISS算法是有效的. 第4期 汪勇.等:基于初集排序的 Parcto非支配解集构造算法 4000 6000 4000 2000 2000 0 0人 6000 15000 目标200302000 3000 7500 15000 0.5 7500 目标1 目标20 目标1 (a)ZDT1 (b)dtlz1 (cDTLZ3 图5三个测试函数的可行解分布 5结论 实验表明,基于初集排序方法的非支配解集构造算法能够有效且快速构造非支配解集.在最坏情形下, 设计的算法时间性能明显优于快速排序、排除法和擂台赛法等非支配排序方法.对于低维多目标决策问题, 解空间的变化对算法时间性能影响不大,在较大解空间情形下,算法的计算时间具有明显的优势.日标对算 法性能影响较大,随着目标旳增加,算法时间性能有所下降.对于2~4个目标的决策问题,设计的算法计算 敚率仍然数倍于NTCM方法.从算法设计的原理上分析,无论目标如何增加,算法的时问性能均优于参与比 较的典型的非支配排序方法.在ISS算法基础上,快速多目标优化方法值得进一步探讨.同时,探索应用多目 标排序与集合论方法解决高维多目标问题非支配解集的构造效率. 参考文献 1 Costa J P Computing non-dominated solutions in MOLFPJ. European Journal of Operational Research, 2007, 181(3):1464-1475 2 Lindroth P, Patriksson M, Stromberg A B. Approximating the Pareto optimal set using a reduced set of objective functions J]. European Journal of Operational Research, 2010, 207 (3: 1519-1534 3]李志强,蔺想红.多日标优化非支配集构造方法的研究进展[J计算机工程与应用,2013,49(19):31-35 Li Z Q, Lin X H. Research advance of multi-objective optimization non-dominated set construction methodsJI Computer Engineering and Applications, 2013, 49(19): 31-35 4 Srinivas N, Deb K. Multi-objective optimization using non-dominated sorting in genetic algorithmsJ. Evolu tionary Computation, 1994, 23): 221-248 5 Deb K, Pratap A, Agarwal S. et al. A fast and elitist multi-objective genetic algorithm: NSGA-IIJ. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197 6 Kung HT, Luccio R, Preparata F P On the computational complexity of finding the maxima of a set of vectors J Journal of the Association for Computing Machinery, 1975, 22(4):469-476 7 Jensen M 'T. Reducing the run-time complexity of multi-objective F As: The NSGA-II and other aIgorithmsJI IEEE Transactions on Evolutionary Computation, 2003, 7(5 : 503-515 8 Deb K, Mohan M, Mishra S. Evaluating the epsilon-domination based multi-objective evolutionary algorithm for a quick computation of Pareto-optimal solutions J]. Evolutionary Computation, 2005, 13 (4 ):501-525 9 Shukla P K, Deb K. On finding Multiple Pareto-optiimal solutions using classical and evolutionary generating methods. European Journal of Operational Research, 2007, 1813):1630-1652 10 Mendoza J E, Lopez M E, Coello C A C, et al. Microgenetic multiobjective reconfiguration algorithm considering power losses and reliability indices for medium voltage distribution networkJ. IET Generation, Transmission Distribution: 2009, 3(9):825-840 11 Gen M. Lin L. Multiob jective evolutionary algorithm for manufacturing scheduling problems: State-of-the-art survey J. Journal of Intelligent Manufacturing, 2014, 25(5 :849-866 12 Lin C H, Lin P L. Improving the non-dominated sorting genetic algorithm using a gene-therapy method for multi-objective optimizationJ. Journal of Computational Science, 2014, 5(2): 170-183 13 Zechman E M, Giacomoni M H, Shafiee M E. An evolutionary algorithm approach to generate distinct sets of non-dominated solutions for wicked problems J. Engineering Applications of Artificial Intelligence, 2013, 26(5) 1442-1457 14 Chen Y, Peng B, Hao X H, et al. Fast approach of Pareto-optimal solution recommendation to multi-objective optimal design of serpentine-chanlel heat sinkJ. Applied Therinal Engineering, 2014, 70(1):263-273

...展开详情
试读 11P 论文研究-基于初集排序的Pareto非支配解集构造算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
weixin_38744435 欢迎大家使用并留下宝贵意见
2019-09-20
  • 至尊王者

    成功上传501个资源即可获取
关注 私信 TA的资源
上传资源赚积分,得勋章
最新推荐
论文研究-基于初集排序的Pareto非支配解集构造算法.pdf 50积分/C币 立即下载
1/11
论文研究-基于初集排序的Pareto非支配解集构造算法.pdf第1页
论文研究-基于初集排序的Pareto非支配解集构造算法.pdf第2页
论文研究-基于初集排序的Pareto非支配解集构造算法.pdf第3页

试读结束, 可继续读1页

50积分/C币 立即下载 >