APP下载

约束动态多目标免疫优化算法及性能比较

2018-07-24

安顺学院学报 2018年3期
关键词:子群支配算子

(1、2、3.安顺学院数理学院,贵州 安顺561000)

引言

实际工程优化中,因受外界环境影响,很多系统模型为复杂的约束动态环境优化。如生产调度、工业管理及设计等[1],该类模型需同时优化多个时变目标或约束,通常称为约束动态多目标优化(Constraineddynamicmultiobjectiveoptimization,CDMO)。已有的优化算法直接求解CDMO极其困难[2]。近年来,非约束动态多目标优化 (Unconstraintdynamicmultiobjectiveoptimization,UCDMO)已出现许多成果[3],但对CDMO算法的研究不够成熟,故设计高级算法处理CDMO问题已成为优化领域的重要课题,对解决复杂的工程优化问题具有重要的理论和现实意义。

目前,关于UCDMO算法的研究在国内已出现多个团队,以焦李成、公茂果、尚荣华等学者的研究团队基于克隆选择、量子免疫等原理提出一系列UCDMO算法[4];以王宇平、刘淳安等学者的研究团队基于进化机制提出了一系列UCDMO算法[5];以张著洪等学者的研究团队基于免疫应答原理提出了多种UCDMO算法[6];同时,汪定伟、彭星光及刘敏等学者[7]均在此领域做了研究。在国外,UCDMO倍受关注,2004年Farina等将梯度搜索策略与进化算法结合提出动态多目标邻域搜索算法(DirectionBasedMethod,DBM),该文有力的推动了UCDMO算法的发展,为后来的UCDMO算法提供了测试算例(如FDA1-FDA5)[8]。继后,Deb等[9]改进NSGAII提出动态多目标DNSGAII-A和DNSGAII-B, 数值仿真结果表明了被提出算法的跟踪能力, 但被测试问题的维数较低。然而,CDMO的研究在国际及国内的研究成果非常少。Liu等[10]修改选择和变异算子提出一种CDMO进化算法,算法实际是针对非线性约束动态单目标优化问题而设计,对CDMO问题的处理效果较差。Zhang基于免疫应答原理,通过改进免疫算子、算子模块等,提出了改进的CDMO免疫算法[11],并应用于大量标准测试问题和温室在线控制模型,验证算法求解CDMO的有效性。

免疫算法是基于人工免疫系统的自适应和并行性及群体的多样性等原理而提出的算法,使得其更适合CDMO问题的求解。为此,本文借鉴免疫系统的抗原识别、自适应学习、免疫克隆及并行性等特征,设计自适应亲和算子,优秀抗体克隆,多子群并行进化,特征环境识别等模块,提出一种适用于求解CDMO的免疫算法(Constraintdynamicmultiobjectiveoptimizationimmunealgorithms,CDMOIAs), 并将CDMOIAs与著名的DNSGAII-A、DNSGAII-B及CSADMO[12]用于不同类型的CDMO测试问题进行数值仿真,结果表明,CDMOIAs在跟踪环境速度,所获Pareto有效面分布和执行效果上均呈现较好的优势。

1 问题模型及相关定义

不失一般性,对于极小化CDMO描述为式(1)

minf(x,t)=(f1(x,t),f2(x,t),…,fM(x,t)),

(1)

其中,t∈[0,T]为时间(或称为环境)变量,x=(x1,x2,…,xn)∈Rn为决策变量,g(x,t)为不等式约束(i=1,2,…,p),hj(x,t)(j=p+1,p+2,…,q)为等式约束,li,ui为变量的上下界。

对于环境t, 如果x∈[L,U]满足式(1)中的所有约束,则称x为可行解,所有可行解构成的集合称为可行域Ω(t)⊂Rn,否则称x为不可行解。

定义1:Pareto支配(Dominance)关系

设x,y∈Ω(t),对于∀i∈[1,M],均有f(x,t)≤f1(y,t)且∃j∈[1,M],使得fi(x,t)

定义2:约束违背(Violation)度

设x∈Rn,则x的约束违背度定义为式(2):

(2)

其中

(3)

此式α∈(0,1)为避免所有解为可行解时vk(x)=0使式(2)的分母为0而无意义,β∈(0,1)是处理等式约束的容忍因子。若Vio(x)=0表明x是可行解。

定义3:Pareto约束支配(constraintdominance)关系[9]

对于给定环境t,若x,y∈Rn满足下列条件之一,则称xPareto约束支配y(x与y的约束支配关系记为:xcy)

(1)x∈Ω(t)且y∈Ω(t)且:xy;

(2)x∈Ω(t),但y∉Ω(t);

(3)x∉Ω(t)且y∉Ω(t)且,但Vio(x)

定义4:Pareto约束被支配度

对于环境t,设x∈Rn,结合定义3,则x的Pareto约束被支配度定义为c(x)

(4)

其中,|·|表示集合的基数。

定义5:Pareto有效解及Pareto有效面

给定环境t,称x∈Ω(t)为Pareto有效解,当且仅当∃y∈Ω(t),使得

f(y,t)f(x,t)。所有Pareto有效解构成的集合称为Pareto有效集(记为:POS(t))

POS(t)={x∈Ω(t)|∃y∈Ω(t),f(y,t)f(x,t)}

(5)

所有Pareto有效解对应的目标空间函数值构成的集合称为Pareto有效面(记为),即

POF(t)={f(x,t)|x∈POS(t)}

(6)

2 算法描述及算子设计

设抗体x∈A,其亲和力设计为:

(7)

其中,λ∈(0,1)为调节因子,d(x)表示抗体x的稀疏度,定义为

(8)

其中df(x,y)=‖f(x,t)-f(y,t)‖为目标空间距离。c(x)指Pareto约束被支配度(见定义4)由(7)式知,稀疏度大被支配度小的抗体具有优先选择性,此设计提高抗体的多样性及算法的收敛速度。

2.1 算法描述

输入:初始代数g=1,环境变化幅度τ,变化频率τω,定义当前环境t=τ⎣g/τω」,其中⎣·」为取整。

输出:Pareto有效解集。

Step1:随机生成规模为N的初始抗体群A。初始记忆池M=φ,环境记忆集P(t)=φ,

其中,xi表示抗体i,随机生成xij∈[li,ui];

Step2:判断g≤G。若是, 转入Step3; 否则, 输出结果;

Step3:计算所有抗体αff(x,t)的亲和力αff(x,t)及Pareto约束被支配度c(x),根据群体分离算子将A分成子群,A1,A2…,AL;

Step4:克隆繁殖算子作用A1,获克隆群B1,每个抗体克隆数与其亲和力成正比,总克隆规模为N,并更新记忆池M;

Step5:高斯突变算子作用B1,获突变群C1;多项式突变算子作用Ai=(i=2,3,…,L),获突变群Di(i=2,…,L)。计算突变抗体的亲和力;

Step6:组合群(C1∪D2∪…∪DL)经由免疫选择,亲和力大的抗体被选中构成新抗体群E;

Step7:执行环境判别算子,若环境无变化,则转入Step8;否则转入Step9;

Step8:随机生成[N·η%]新抗体群替代亲和力较低的抗体,构成新抗体群E,转入Step10;

Step9:环境记忆保存当前环境记忆池中优秀抗体构成环境记忆集P(t)(即环境t的Pareto有效解集),产生新环境群E,转入Step10;

Step10:置A←E,g=g+1,转入Step2。

2.2 算子设计

2.2.1 群体分离

假设当前群为A,根据Pareto约束被支配度 (定义4) 由小到大顺序将A分成L个子群,各子群中抗体x的Pareto约束被支配度c(x)与其所在的集合下标满足关系:c(x)=i,∀x∈Ai,Ai为Pareto约束被支配度最小的子群。特别指出,若L>Lmax(设定的阀值),则Lmax未分完的所有抗体统归结到AL max子群。注该分离法与文[13]不同,本文(1)以Pareto约束被支配度为分离准则,(2)限制最大子群数,(3)分得的子群参与了进化。

2.2.2 记忆池更新

记忆池M(|M|≤最大容量μ)保存子群Ai中可行优秀抗体。随着算法的迭代,记忆池中保存的抗体数逐渐增大,更新算子首先删去相同、非可行及被支配抗体,若|M|>μ,其次删去稀疏度小的抗体,直到记忆池中抗体数|M|=μ。

2.2.3 突变

(1)高斯突变

子群Ai采用高斯突变方式,Ai中抗体为较优秀抗体,高斯突变以小概率对抗体进行微小的扰动,提高算法的局部探索能力,使得算法适应于环境变化对可行区域影响小的CDMO问题求解。变异方式为:设抗体x=(x1x2…xn)经高斯突变为y=(y1y2…yn),则对于每个j∈[1,n]。

(10)

(2)多项式突变

多项式突变算子作用于A2-AL,设抗体xi=(x1,x2,…xn)∈Ai(i=2,…L),经高斯突变为yt=(y1,y2,…yn),则对于每个j∈[1,n]。

Step1:取一随机数μj∈U(0,1)。

Step2:计算参数Kj,如下

(11)

Step3:则yj=xj+(lj-uj)Kj,其中ηm为常数,lj,uj,xj为的上下界。

2.2.4 环境判别

环境判别为CDMO算法设计的关键之一,算子设计的是否合理直接影响算法的搜索能力。文[7]通过判别因子与一个比较小的阀值的大小定义环境是否变化。但设计的表达式非常复杂,将目标函数和约束函数同时糅合于一体,对环境判别准确度有一定影响。本文在此基础上对其改进,随机选取记忆池M中m(m<μ)个抗体构成的集合R={r1,r2,…,rn},判别方法如下:

这里g:Vio(·)表示第g代抗体的约束违背度,t=τ⎣g/τω」,σ1,σ2为给定阀值。

2.2.5 新环境群

根据2.2.4判断结果,若环境未变化,则新环境群为当前抗体群,否则随机选取ρ(ρ<|M|)个记忆抗体随机代替当前群体中的抗体构成新环境群。

3 性能评价准则

为了测试CDMOIAs的优越性,设定以下准则评价算法性能:Pareto有效解平均浓度(Adi),Pareto有效面平均覆盖率(Ado),Pareto有效面平均覆盖范围(Acs)。为便于统计分析,设Ak(t)和Bk(t)分别为算法α与b对某问题某环境t执行第k次所获的POF(t)。假设环境总数为T,算法独立执行总次数为K。

(1)Pareto有效解平均浓度

平均浓度(Adi)是度量算法在所有环境中所获Pareto有效解的平均分布性。其定义为

Adi=

(12)

其中,

方程(12)表明:如果Adi的值越小,则所获解集Ak(t)中Pareto有效解在各环境的平均分布性越均匀,抗体多样性越好。

(2)Pareto有效面平均覆盖率

平均支配率(Ado)是评价算法ɑ与b在所有环境中所获Pareto有效面的平均支配程度,其定义为

Ado(ɑ,b)=

(13)

其中,

C(Ai(t),Bj(t))=

(3)Pareto有效面平均覆盖范围

平均覆盖值(Acs)是度量算法在所有环境中所获Pareto有效面的平均覆盖范围. 其定义为

(14)

Acs越大则算法所获的Pareto有效面分布范围越广,Acs算法开采性能强,群体多样性好。

4 数值实验仿真

了评价算法的性能,通过VC++实现CDMOIAs程序, 执行计算机为CPU/4.0GHz和内存4.0GB,选取著名的算法NSGAII-A,NSGAII-B,CSADMO参与比较,七个测试问题作为测试实例,为了减少算法随机性对结果的影响,各算法对每个问题的每个环境分别独立执行K=30次,所获统计结果如表3。

4.1 测试函数

问题1:DCTP1

minf(x,t)=(f1(x,t),f2(x,t))

其中,变量x1∈[0,1],xi∈[-1,1],i=1,2,…,n;参数ɑ1=0.858,b1=0.728,ɑ2=0.541,b2=0.295,环境变化幅度τ=0.05,变化频率τω=500,即问题每隔ιω代变化一次。其Pareto有效面是三条线段构成。对于该问题,在约束g1,g2下,算法获取整个Pareto有效面比较困难,特别是靠近f1值较大处的Pareto点极难获得。

问题2:DCTP2-DCTP7

minf(x,t)=(f1(x,t),f2(x,t))

其中,变量x1∈[0,1],xi∈[-1,1],i=1, 2,…n。参数θ,ɑ,b,c,d,e如表1所示构成不同的问题。在约束条件下DCTP2的Pareto有效面由多个分布均匀的离散线段组成。DCTP3和DCTP4的Pareto有效面是有限个分布均匀的离散点构成,特别DCTP4的Pareto有效点在带状可行域的顶点处,算法极难搜索其Pareto点。而DCTP5的Pareto有效面是由一个曲线弧和一些离散点构成。DCTP6和DCTP7的可行域是很多离散的带状型,Pareto有效面分别由直线和分段块构成,可行域被不同宽度的不可行域分离成很多块。

表1 DCTP2-DCTP7问题中的参数

表2 算法CDMOIAs参数设置

4.2 算法设置

实验中,各算法群体规模N=100,环境总数T=4,环境变化频率tw=500,故最大迭代数G=Ttw=2000,测试问题的维数n=10。算法NSGAII-A,NSGAII-B约束处理策略根据Deb提出的CDP方法[13]。环境变化后,随机插入的个体百分比ζ%=10%。算法CSADMO参数设置如文[12]。算法CDMOIAs参数设置如表2。

4.3 结果分析

表3为各算法对各问题独立执行30次所获各种统计值比较。其中,A_Adr(.,.)(%)为30次独立执行所获的Pareto有效面平均覆盖率,Adi和Acs分别为Pareto有效解的平均覆盖率和覆盖范围。由表4知,观察问题DCTP1,由平均覆盖率A_Adr(CDMOIAs,NSGAII-A)=10.1%,A_Adr(DNSGAII-A,CDMOIAs)=6.8%;A_Adr(CDMOIAs,DNSGAII-B)=11.9%,A_Adr(DNSGAII-B,CDMOIAs) = 5.1%;A_Adr(CDMOIAs,CSADMO)=27.7%,A_Adr(CSADMO,CDMOIAs)=1.9%知,算法CDMOIAs所获Pareto有效解较大的控制其他三算法。由平均浓度Adi均值(Av_Adi)及方差(Var_Adi)知CDMOIAs所获Pareto有效面分布较均匀。且CDMOIAs的Acs均值(Av_Acs)大于DNSGAII-A、DNSGAII-B和CSADMO,此表明CDMOIAs所获Pareto有效解的覆盖范围大,而由Acs方差(Var_Acs)知,CDMOIAs方差小,表明CDMOIAs算法稳定于其他算法。其他问题结果类似,从表3总体统计数据显示,CDMOIAs优越于其他算法。

表3 各算法独立执行K次所获各统计值比较(Av_指均值,Var_指方差)

5 结论及进一步工作

文章基于免疫系统运行机理,提出一种约束动态多目标免疫优化算法,并将其应用于DCTP类问题与同类算法(DNSGAII-A,DNSGAII-B,CSADMO)进行仿真比较,实验结果表明:提出的算法在不同环境所获的Pareto有效面分布性优越于其他算法,快速适应环境变化能力较好,通过统计值比较表明提出的算法在多次执行中稳定性优越于其他算法,所获Pareto有效解的覆盖率及覆盖范围比其他算法好。

虽所获结果表明了提出算法的优越性,但该类问题是一类极难的约束动态多目标优化,其难度与约束函数中函数性态有关,不同的函数对算法的要求不同,故使用更复杂的函数研究算法的性能为我们将来进一步开展的课题。

猜你喜欢

子群支配算子
Schmidt子群为Hall S-拟正规嵌入群的有限群①
有限群的局部化HC-子群①
有限群的弱τσ-嵌入子群
被贫穷生活支配的恐惧
Domestication or Foreignization:A Cultural Choice
关于ss-拟正规子群和c-正规子群
云南省人均可支配收入首次突破2万元
跟踪导练(四)4
一类算子方程的正算子解问题的研究
QK空间上的叠加算子