約束動態多目標免疫優化算法及性能比較

(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有效解的覆蓋率及覆蓋范圍比其他算法好。

雖所獲結果表明了提出算法的優越性，但該類問題是一類極難的約束動態多目標優化，其難度與約束函數中函數性態有關，不同的函數對算法的要求不同，故使用更復雜的函數研究算法的性能為我們將來進一步開展的課題。