約束動(dòng)態(tài)多目標(biāo)免疫優(yōu)化算法及性能比較

(1、2、3.安順學(xué)院數(shù)理學(xué)院，貴州 安順561000)

引言

實(shí)際工程優(yōu)化中，因受外界環(huán)境影響，很多系統(tǒng)模型為復(fù)雜的約束動(dòng)態(tài)環(huán)境優(yōu)化。如生產(chǎn)調(diào)度、工業(yè)管理及設(shè)計(jì)等[1]，該類模型需同時(shí)優(yōu)化多個(gè)時(shí)變目標(biāo)或約束，通常稱為約束動(dòng)態(tài)多目標(biāo)優(yōu)化(Constraineddynamicmultiobjectiveoptimization,CDMO)。已有的優(yōu)化算法直接求解CDMO極其困難[2]。近年來(lái)，非約束動(dòng)態(tài)多目標(biāo)優(yōu)化 (Unconstraintdynamicmultiobjectiveoptimization，UCDMO)已出現(xiàn)許多成果[3]，但對(duì)CDMO算法的研究不夠成熟，故設(shè)計(jì)高級(jí)算法處理CDMO問(wèn)題已成為優(yōu)化領(lǐng)域的重要課題，對(duì)解決復(fù)雜的工程優(yōu)化問(wèn)題具有重要的理論和現(xiàn)實(shí)意義。

目前，關(guān)于UCDMO算法的研究在國(guó)內(nèi)已出現(xiàn)多個(gè)團(tuán)隊(duì)，以焦李成、公茂果、尚榮華等學(xué)者的研究團(tuán)隊(duì)基于克隆選擇、量子免疫等原理提出一系列UCDMO算法[4]；以王宇平、劉淳安等學(xué)者的研究團(tuán)隊(duì)基于進(jìn)化機(jī)制提出了一系列UCDMO算法[5]；以張著洪等學(xué)者的研究團(tuán)隊(duì)基于免疫應(yīng)答原理提出了多種UCDMO算法[6]；同時(shí)，汪定偉、彭星光及劉敏等學(xué)者[7]均在此領(lǐng)域做了研究。在國(guó)外，UCDMO倍受關(guān)注，2004年Farina等將梯度搜索策略與進(jìn)化算法結(jié)合提出動(dòng)態(tài)多目標(biāo)鄰域搜索算法(DirectionBasedMethod,DBM)，該文有力的推動(dòng)了UCDMO算法的發(fā)展，為后來(lái)的UCDMO算法提供了測(cè)試算例(如FDA1-FDA5)[8]。繼后,Deb等[9]改進(jìn)NSGAII提出動(dòng)態(tài)多目標(biāo)DNSGAII-A和DNSGAII-B, 數(shù)值仿真結(jié)果表明了被提出算法的跟蹤能力, 但被測(cè)試問(wèn)題的維數(shù)較低。然而，CDMO的研究在國(guó)際及國(guó)內(nèi)的研究成果非常少。Liu等[10]修改選擇和變異算子提出一種CDMO進(jìn)化算法，算法實(shí)際是針對(duì)非線性約束動(dòng)態(tài)單目標(biāo)優(yōu)化問(wèn)題而設(shè)計(jì)，對(duì)CDMO問(wèn)題的處理效果較差。Zhang基于免疫應(yīng)答原理，通過(guò)改進(jìn)免疫算子、算子模塊等，提出了改進(jìn)的CDMO免疫算法[11]，并應(yīng)用于大量標(biāo)準(zhǔn)測(cè)試問(wèn)題和溫室在線控制模型，驗(yàn)證算法求解CDMO的有效性。

免疫算法是基于人工免疫系統(tǒng)的自適應(yīng)和并行性及群體的多樣性等原理而提出的算法，使得其更適合CDMO問(wèn)題的求解。為此，本文借鑒免疫系統(tǒng)的抗原識(shí)別、自適應(yīng)學(xué)習(xí)、免疫克隆及并行性等特征，設(shè)計(jì)自適應(yīng)親和算子，優(yōu)秀抗體克隆，多子群并行進(jìn)化，特征環(huán)境識(shí)別等模塊，提出一種適用于求解CDMO的免疫算法(Constraintdynamicmultiobjectiveoptimizationimmunealgorithms，CDMOIAs), 并將CDMOIAs與著名的DNSGAII-A、DNSGAII-B及CSADMO[12]用于不同類型的CDMO測(cè)試問(wèn)題進(jìn)行數(shù)值仿真，結(jié)果表明，CDMOIAs在跟蹤環(huán)境速度，所獲Pareto有效面分布和執(zhí)行效果上均呈現(xiàn)較好的優(yōu)勢(shì)。

1 問(wèn)題模型及相關(guān)定義

不失一般性，對(duì)于極小化CDMO描述為式(1)

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

(1)

其中，t∈[0,T]為時(shí)間(或稱為環(huán)境)變量，x=(x1,x2,…,xn)∈Rn為決策變量，g(x,t)為不等式約束(i=1,2,…,p)，hj(x,t)(j=p+1,p+2,…,q)為等式約束，li,ui為變量的上下界。

對(duì)于環(huán)境t, 如果x∈[L,U]滿足式(1)中的所有約束，則稱x為可行解，所有可行解構(gòu)成的集合稱為可行域Ω(t)?Rn，否則稱x為不可行解。

定義1：Pareto支配(Dominance)關(guān)系

設(shè)x,y∈Ω(t)，對(duì)于?i∈[1,M]，均有f(x,t)≤f1(y,t)且?j∈[1,M]，使得fi(x,t)

定義2：約束違背(Violation)度

設(shè)x∈Rn，則x的約束違背度定義為式(2):

(2)

其中

(3)

此式α∈(0，1)為避免所有解為可行解時(shí)vk(x)=0使式(2)的分母為0而無(wú)意義，β∈(0,1)是處理等式約束的容忍因子。若Vio(x)=0表明x是可行解。

定義3：Pareto約束支配(constraintdominance)關(guān)系[9]

對(duì)于給定環(huán)境t，若x,y∈Rn滿足下列條件之一，則稱xPareto約束支配y(x與y的約束支配關(guān)系記為：xcy)

(1)x∈Ω(t)且y∈Ω(t)且：xy；

(2)x∈Ω(t)，但y?Ω(t)；

(3)x?Ω(t)且y?Ω(t)且，但Vio(x)

定義4：Pareto約束被支配度

對(duì)于環(huán)境t，設(shè)x∈Rn，結(jié)合定義3，則x的Pareto約束被支配度定義為c(x)

(4)

其中，|·|表示集合的基數(shù)。

定義5：Pareto有效解及Pareto有效面

給定環(huán)境t，稱x∈Ω(t)為Pareto有效解，當(dāng)且僅當(dāng)?y∈Ω(t)，使得

f(y,t)f(x,t)。所有Pareto有效解構(gòu)成的集合稱為Pareto有效集(記為:POS(t))

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

(5)

所有Pareto有效解對(duì)應(yīng)的目標(biāo)空間函數(shù)值構(gòu)成的集合稱為Pareto有效面(記為)，即

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

(6)

2 算法描述及算子設(shè)計(jì)

設(shè)抗體x∈A，其親和力設(shè)計(jì)為:

(7)

其中，λ∈(0,1)為調(diào)節(jié)因子，d(x)表示抗體x的稀疏度，定義為

(8)

其中df(x,y)=‖f(x,t)-f(y,t)‖為目標(biāo)空間距離。c(x)指Pareto約束被支配度(見(jiàn)定義4)由(7)式知，稀疏度大被支配度小的抗體具有優(yōu)先選擇性，此設(shè)計(jì)提高抗體的多樣性及算法的收斂速度。

2.1 算法描述

輸入：初始代數(shù)g=1，環(huán)境變化幅度τ，變化頻率τω，定義當(dāng)前環(huán)境t=τ?g/τω」，其中?·」為取整。

輸出：Pareto有效解集。

Step1：隨機(jī)生成規(guī)模為N的初始抗體群A。初始記憶池M=φ，環(huán)境記憶集P(t)=φ，

其中，xi表示抗體i，隨機(jī)生成xij∈[li,ui]；

Step2：判斷g≤G。若是, 轉(zhuǎn)入Step3; 否則, 輸出結(jié)果；

Step3：計(jì)算所有抗體αff(x,t)的親和力αff(x,t)及Pareto約束被支配度c(x)，根據(jù)群體分離算子將A分成子群,A1,A2…,AL；

Step4：克隆繁殖算子作用A1，獲克隆群B1，每個(gè)抗體克隆數(shù)與其親和力成正比，總克隆規(guī)模為N，并更新記憶池M；

Step5：高斯突變算子作用B1，獲突變?nèi)篊1；多項(xiàng)式突變算子作用Ai=(i=2,3,…,L)，獲突變?nèi)篋i(i=2,…,L)。計(jì)算突變抗體的親和力；

Step6：組合群(C1∪D2∪…∪DL)經(jīng)由免疫選擇，親和力大的抗體被選中構(gòu)成新抗體群E；

Step7：執(zhí)行環(huán)境判別算子，若環(huán)境無(wú)變化，則轉(zhuǎn)入Step8；否則轉(zhuǎn)入Step9；

Step8：隨機(jī)生成[N·η%]新抗體群替代親和力較低的抗體，構(gòu)成新抗體群E，轉(zhuǎn)入Step10；

Step9：環(huán)境記憶保存當(dāng)前環(huán)境記憶池中優(yōu)秀抗體構(gòu)成環(huán)境記憶集P(t)(即環(huán)境t的Pareto有效解集)，產(chǎn)生新環(huán)境群E，轉(zhuǎn)入Step10；

Step10：置A←E，g=g+1,轉(zhuǎn)入Step2。

2.2 算子設(shè)計(jì)

2.2.1 群體分離

假設(shè)當(dāng)前群為A，根據(jù)Pareto約束被支配度 (定義4) 由小到大順序?qū)分成L個(gè)子群，各子群中抗體x的Pareto約束被支配度c(x)與其所在的集合下標(biāo)滿足關(guān)系:c(x)=i,?x∈Ai，Ai為Pareto約束被支配度最小的子群。特別指出，若L>Lmax(設(shè)定的閥值)，則Lmax未分完的所有抗體統(tǒng)歸結(jié)到AL max子群。注該分離法與文[13]不同，本文(1)以Pareto約束被支配度為分離準(zhǔn)則，(2)限制最大子群數(shù)，(3)分得的子群參與了進(jìn)化。

2.2.2 記憶池更新

記憶池M(|M|≤最大容量μ)保存子群Ai中可行優(yōu)秀抗體。隨著算法的迭代，記憶池中保存的抗體數(shù)逐漸增大，更新算子首先刪去相同、非可行及被支配抗體，若|M|>μ，其次刪去稀疏度小的抗體，直到記憶池中抗體數(shù)|M|=μ。

2.2.3 突變

(1)高斯突變

子群Ai采用高斯突變方式，Ai中抗體為較優(yōu)秀抗體，高斯突變以小概率對(duì)抗體進(jìn)行微小的擾動(dòng)，提高算法的局部探索能力，使得算法適應(yīng)于環(huán)境變化對(duì)可行區(qū)域影響小的CDMO問(wèn)題求解。變異方式為：設(shè)抗體x=(x1x2…xn)經(jīng)高斯突變?yōu)閥=(y1y2…yn)，則對(duì)于每個(gè)j∈[1,n]。

(10)

(2)多項(xiàng)式突變

多項(xiàng)式突變算子作用于A2-AL，設(shè)抗體xi=(x1,x2,…xn)∈Ai(i=2,…L)，經(jīng)高斯突變?yōu)閥t=(y1,y2,…yn)，則對(duì)于每個(gè)j∈[1,n]。

Step1：取一隨機(jī)數(shù)μj∈U(0,1)。

Step2：計(jì)算參數(shù)Kj，如下

(11)

Step3：則yj=xj+(lj-uj)Kj，其中ηm為常數(shù)，lj,uj,xj為的上下界。

2.2.4 環(huán)境判別

環(huán)境判別為CDMO算法設(shè)計(jì)的關(guān)鍵之一，算子設(shè)計(jì)的是否合理直接影響算法的搜索能力。文[7]通過(guò)判別因子與一個(gè)比較小的閥值的大小定義環(huán)境是否變化。但設(shè)計(jì)的表達(dá)式非常復(fù)雜，將目標(biāo)函數(shù)和約束函數(shù)同時(shí)糅合于一體，對(duì)環(huán)境判別準(zhǔn)確度有一定影響。本文在此基礎(chǔ)上對(duì)其改進(jìn)，隨機(jī)選取記憶池M中m(m<μ)個(gè)抗體構(gòu)成的集合R={r1，r2,…,rn}，判別方法如下：

這里g:Vio(·)表示第g代抗體的約束違背度，t=τ?g/τω」，σ1,σ2為給定閥值。

2.2.5 新環(huán)境群

根據(jù)2.2.4判斷結(jié)果，若環(huán)境未變化，則新環(huán)境群為當(dāng)前抗體群，否則隨機(jī)選取ρ(ρ<|M|)個(gè)記憶抗體隨機(jī)代替當(dāng)前群體中的抗體構(gòu)成新環(huán)境群。

3 性能評(píng)價(jià)準(zhǔn)則

為了測(cè)試CDMOIAs的優(yōu)越性，設(shè)定以下準(zhǔn)則評(píng)價(jià)算法性能：Pareto有效解平均濃度(Adi)，Pareto有效面平均覆蓋率(Ado),Pareto有效面平均覆蓋范圍(Acs)。為便于統(tǒng)計(jì)分析，設(shè)Ak(t)和Bk(t)分別為算法α與b對(duì)某問(wèn)題某環(huán)境t執(zhí)行第k次所獲的POF(t)。假設(shè)環(huán)境總數(shù)為T，算法獨(dú)立執(zhí)行總次數(shù)為K。

(1)Pareto有效解平均濃度

平均濃度(Adi)是度量算法在所有環(huán)境中所獲Pareto有效解的平均分布性。其定義為

Adi=

(12)

其中，

方程(12)表明：如果Adi的值越小，則所獲解集Ak(t)中Pareto有效解在各環(huán)境的平均分布性越均勻，抗體多樣性越好。

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

平均支配率(Ado)是評(píng)價(jià)算法ɑ與b在所有環(huán)境中所獲Pareto有效面的平均支配程度，其定義為

Ado(ɑ,b)=

(13)

其中，

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

(3)Pareto有效面平均覆蓋范圍

平均覆蓋值(Acs)是度量算法在所有環(huán)境中所獲Pareto有效面的平均覆蓋范圍. 其定義為

(14)

Acs越大則算法所獲的Pareto有效面分布范圍越廣，Acs算法開(kāi)采性能強(qiáng)，群體多樣性好。

4 數(shù)值實(shí)驗(yàn)仿真

了評(píng)價(jià)算法的性能，通過(guò)VC++實(shí)現(xiàn)CDMOIAs程序, 執(zhí)行計(jì)算機(jī)為CPU/4.0GHz和內(nèi)存4.0GB，選取著名的算法NSGAII-A，NSGAII-B，CSADMO參與比較，七個(gè)測(cè)試問(wèn)題作為測(cè)試實(shí)例，為了減少算法隨機(jī)性對(duì)結(jié)果的影響，各算法對(duì)每個(gè)問(wèn)題的每個(gè)環(huán)境分別獨(dú)立執(zhí)行K=30次，所獲統(tǒng)計(jì)結(jié)果如表3。

4.1 測(cè)試函數(shù)

問(wèn)題1：DCTP1

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

其中，變量x1∈[0,1],xi∈[-1,1],i=1,2,…,n；參數(shù)ɑ1=0.858，b1=0.728，ɑ2=0.541，b2=0.295，環(huán)境變化幅度τ=0.05，變化頻率τω=500，即問(wèn)題每隔ιω代變化一次。其Pareto有效面是三條線段構(gòu)成。對(duì)于該問(wèn)題，在約束g1，g2下，算法獲取整個(gè)Pareto有效面比較困難，特別是靠近f1值較大處的Pareto點(diǎn)極難獲得。

問(wèn)題2：DCTP2-DCTP7

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

其中，變量x1∈[0,1],xi∈[-1,1],i=1, 2,…n。參數(shù)θ，ɑ，b，c，d，e如表1所示構(gòu)成不同的問(wèn)題。在約束條件下DCTP2的Pareto有效面由多個(gè)分布均勻的離散線段組成。DCTP3和DCTP4的Pareto有效面是有限個(gè)分布均勻的離散點(diǎn)構(gòu)成，特別DCTP4的Pareto有效點(diǎn)在帶狀可行域的頂點(diǎn)處，算法極難搜索其Pareto點(diǎn)。而DCTP5的Pareto有效面是由一個(gè)曲線弧和一些離散點(diǎn)構(gòu)成。DCTP6和DCTP7的可行域是很多離散的帶狀型，Pareto有效面分別由直線和分段塊構(gòu)成，可行域被不同寬度的不可行域分離成很多塊。

表1 DCTP2-DCTP7問(wèn)題中的參數(shù)

表2 算法CDMOIAs參數(shù)設(shè)置

4.2 算法設(shè)置

實(shí)驗(yàn)中，各算法群體規(guī)模N=100，環(huán)境總數(shù)T=4，環(huán)境變化頻率tw=500，故最大迭代數(shù)G=Ttw=2000，測(cè)試問(wèn)題的維數(shù)n=10。算法NSGAII-A，NSGAII-B約束處理策略根據(jù)Deb提出的CDP方法[13]。環(huán)境變化后，隨機(jī)插入的個(gè)體百分比ζ%=10%。算法CSADMO參數(shù)設(shè)置如文[12]。算法CDMOIAs參數(shù)設(shè)置如表2。

4.3 結(jié)果分析

表3為各算法對(duì)各問(wèn)題獨(dú)立執(zhí)行30次所獲各種統(tǒng)計(jì)值比較。其中，A_Adr(.,.)(%)為30次獨(dú)立執(zhí)行所獲的Pareto有效面平均覆蓋率，Adi和Acs分別為Pareto有效解的平均覆蓋率和覆蓋范圍。由表4知，觀察問(wèn)題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算法穩(wěn)定于其他算法。其他問(wèn)題結(jié)果類似，從表3總體統(tǒng)計(jì)數(shù)據(jù)顯示，CDMOIAs優(yōu)越于其他算法。

表3 各算法獨(dú)立執(zhí)行K次所獲各統(tǒng)計(jì)值比較(Av_指均值，Var_指方差)

5 結(jié)論及進(jìn)一步工作

文章基于免疫系統(tǒng)運(yùn)行機(jī)理，提出一種約束動(dòng)態(tài)多目標(biāo)免疫優(yōu)化算法，并將其應(yīng)用于DCTP類問(wèn)題與同類算法(DNSGAII-A,DNSGAII-B,CSADMO)進(jìn)行仿真比較，實(shí)驗(yàn)結(jié)果表明：提出的算法在不同環(huán)境所獲的Pareto有效面分布性優(yōu)越于其他算法，快速適應(yīng)環(huán)境變化能力較好，通過(guò)統(tǒng)計(jì)值比較表明提出的算法在多次執(zhí)行中穩(wěn)定性優(yōu)越于其他算法，所獲Pareto有效解的覆蓋率及覆蓋范圍比其他算法好。

雖所獲結(jié)果表明了提出算法的優(yōu)越性，但該類問(wèn)題是一類極難的約束動(dòng)態(tài)多目標(biāo)優(yōu)化，其難度與約束函數(shù)中函數(shù)性態(tài)有關(guān)，不同的函數(shù)對(duì)算法的要求不同，故使用更復(fù)雜的函數(shù)研究算法的性能為我們將來(lái)進(jìn)一步開(kāi)展的課題。