修正免疫克隆約束多目標優(yōu)化算法

修正免疫克隆約束多目標優(yōu)化算法

在一般情況下，首先，列出了限制多目標優(yōu)化的參考形式。其中,x=(x1,…,xn)是n維決策向量,xj是第j個決策變量;X為決策變量空間,u和l為決策變量的上下界;F(x)為目標函數(shù)向量,fi(x)為第i個目標函數(shù)值;gi(x)≤0(i=1,…,q)為第i個不等式約束,hj(x)=0(j=q+1,…,m)為第j個等式約束.通常,等式約束將通過公式(2)轉(zhuǎn)換為不等式約束.其中,e為一個小的松弛度值,根據(jù)情況通常取0.001或者0.0001.當(dāng)x∈X滿足所有的約束條件gi(x)≤0(i=1,…,q)和hj(x)=0(j=q+1,…,m)時,稱x為可行解,所有可行解的集合記為Xf.過去幾年中,一些學(xué)者已經(jīng)提出了許多經(jīng)典的約束多目標優(yōu)化算法.下面首先對約束條件的處理方法進行介紹,之后回顧幾種經(jīng)典的約束多目標優(yōu)化算法.通常,對約束條件的處理有兩種方法:約束偏離值方法和約束偏離度方法.約束偏離值因為實現(xiàn)簡單,使用最多.標準約束偏離值的計算方式如公式(3)所示:其中,cj(x)為第j個約束偏離值,見公式(4);cjmax為第j個約束偏離值的最大值,見公式(5);wj為第j個約束函數(shù)的加權(quán)值,通常;C(x)為個體x的約束偏離值.對約束偏離值的處理方法分為兩種:1)將約束偏離值加到每個個體的目標函數(shù)值上,從而將約束多目標優(yōu)化問題簡化為非約束多目標優(yōu)化問題進行處理;2)將約束偏離值看作一維目標函數(shù)值,從而使目標函數(shù)維數(shù)成為k+1維,之后對新的目標函數(shù)空間進行非約束多目標優(yōu)化.2)約束偏離度方法這種方法用的較少.用變量v標記個體x不滿足的約束條件的個數(shù),處理v的方法類似于處理上述方法1)中約束偏離值的方法.接下來,主要介紹幾種已有的約束多目標優(yōu)化算法.在文獻中,Venkatraman等人將約束優(yōu)化問題分為兩個步驟進行優(yōu)化:第1步尋找可行解,忽略目標函數(shù)值,僅根據(jù)每個個體的約束偏離值對其進行等級分配,當(dāng)種群中出現(xiàn)有可行解時進入第2步;第2步將約束值空間和目標函數(shù)值空間合為一個空間,將問題轉(zhuǎn)化為無約束的多目標問題進行優(yōu)化.該方法比較容易理解和實現(xiàn),但當(dāng)約束函數(shù)條件較多時,優(yōu)化的目標函數(shù)空間迅速變大,從而嚴重影響了算法的性能.在文獻中,Deb等人在NSGA-II中采用一種新的選擇策略,分為3種情況:1)兩個個體都為可行解時,選取非支配的個體;2)兩個個體都為非可行解時,選取約束偏離值小的個體;3)兩個個體中,當(dāng)一個為可行解,一個為非可行解時,選取可行解.這種選擇策略中,所有的可行解支配所有的非可行解.Li等人在文獻中采用了同樣的選擇策略,并通過修正PSO算法來解決約束多目標優(yōu)化問題.文獻中,Geng等人提出了一個對非支配解的修正算子SBMS.修正非支配個體時,需要選擇一個離其最近的可行非支配參考點,同時,在NSGA-II和約束選擇策略的基礎(chǔ)上提出了SMBS_MOEA算法.Chafekar等人在文獻中提出兩個算子:1)OEGADO算子,將約束多目標優(yōu)化問題轉(zhuǎn)換為約束單目標優(yōu)化問題,每個目標函數(shù)都有獨立種群,用GA優(yōu)化各個目標函數(shù)的種群;2)OSGADO算子,用GA依次優(yōu)化同一種群中的各個目標函數(shù).在文獻中,Young分配給每個個體兩個非支配等級:目標函數(shù)空間的非支配等級RO和約束函數(shù)空間的非支配等級RC.每個個體的混合非支配等級如公式(6)所示,其中,uf061為可行解在種群中所占的比例.在文獻中,Liu首先給每個個體分配兩個變量:R(x)和C(x).R(x)為個體x在種群中被支配的抗體的個數(shù)加1,C(x)為公式(3)所求出的約束偏離值.之后為每個個體賦予一個適應(yīng)度值,如公式(7)所示.其中,當(dāng)種群中非支配解的個數(shù)大于所要得到種群的個數(shù)時,則w1=1,w2=0;如果不大于所要得到的種群的個數(shù),則w1=0,w2=1.此時,所有的支配解進入下一代進化.在文獻中,Jaddan用罰函數(shù)法將個體在目標函數(shù)空間和約束函數(shù)空間的兩個非支配等級加入個體的目標函數(shù)空間中,同時加入了個體的約束偏離值,并引入一個自適應(yīng)選擇變量.在文獻中,Singh在模擬退火算法的基礎(chǔ)上,用一種新的選擇策略:1)當(dāng)xold為非可行解、xnew為可行解時,xnew優(yōu)于xold;2)當(dāng)xold為可行解、xnew為非可行解時,xnew被賦予一個被接受的概率;3)當(dāng)xnew和xold都為非可行解時,選擇約束偏離值小的個體.在文獻中,Isaacs等人將每個個體違反約束的個數(shù)合并到目標函數(shù)空間中,在每一代中,將解分為可行解集Sf和非可行解集Sinf,在合并后的目標函數(shù)空間中,對每個解集中的每個個體進行非支配排序.在進行選取下一代時,保留一定的選擇份額給非可行解.以上算法為約束多目標優(yōu)化問題的解提供了多種選擇思路:在處理約束條件時,從最初的可行解支配所有非可行解,到約束偏離值小的非可行解也可能支配可行解;使用的進化算法,從GA,NSGA-II再到PSO等.但是,各種算法求出的最優(yōu)解集的多樣性和逼近性仍有待提高.文獻中,Woldesenbet等人提出的約束多目標進化算法采用了新的約束處理策略,通過一定數(shù)目的懲罰項對目標函數(shù)值進行修正,并從修正后的目標函數(shù)值中選取一定數(shù)目的非支配解集作為父代,然后進行下一代優(yōu)化.同時,還有一個精英種群來儲存進化過程中出現(xiàn)的非支配可行解.這種方法巧妙地解決了可行解和非可行解的選擇問題,在進化種群中,既保留了可行非支配解,又保留了約束偏離值較小且目標函數(shù)值較小的非可行解.免疫克隆算法在求解多目標優(yōu)化問題時,每次選取一定數(shù)目的非支配解集進入下一代優(yōu)化,并且通過克隆選擇策略使得解集能夠保持好的多樣性和收斂性.由于文獻中所提出的約束處理策略能夠很好地應(yīng)用到免疫克隆算法中,所以本文根據(jù)文獻中的約束處理策略,提出一種修正免疫克隆約束多目標優(yōu)化算法.然而,文獻中的約束處理策略也存在不足之處,即通過該約束處理策略,在種群中無可行非支配解時,該策略就已經(jīng)使種群朝著搜索可行解的方向進化.因此,本文沒有采取兩步的策略.這一點在第1節(jié)從理論分析和實驗兩個方面已給出了說明.同時,免疫克隆算法在求解約束多目標優(yōu)化問題時,大多數(shù)文獻的做法是將已求得的可行非支配解進行克隆和變異等操作.而本文算法中,針對約束多目標優(yōu)化問題,通過種群ModNonPop存儲修正后的非支配解,通過種群FeaNonPop存儲可行非支配解集,在進行克隆操作時,我們經(jīng)過大量的實驗發(fā)現(xiàn),如果將種群FeaNonPop也進行克隆,優(yōu)化過程中的可行非支配解集規(guī)模幾乎將成倍上升,給后面的選擇更新操作造成了很大的壓力,從而使算法花費大量時間在選擇更新操作上.所以,本文并沒有將種群FeaNonPop選入克隆操作,從而提高了本文算法的執(zhí)行效率和搜索能力.通過對約束多目標問題的測試,并與文獻中的算法和NSGA-II進行對比,表明本文算法在處理約束多目標優(yōu)化測試問題時,所得解的多樣性、收斂性和均勻性均得到了很大提高,說明本文算法具有很好的多樣性和均勻性保持能力以及較強的收斂能力.本文第1節(jié)詳細介紹本文所提出的免疫克隆約束多目標優(yōu)化算法.第2節(jié)給出約束多目標經(jīng)典測試函數(shù),之后用本文算法、NSGA-II約束多目標優(yōu)化算法和文獻中約束多目標優(yōu)化算法優(yōu)化測試問題,并對測試結(jié)果進行對比分析.第3節(jié)總結(jié)本文的工作.1關(guān)于可行解的尋找本文提出的修正免疫克隆約束多目標優(yōu)化算法仍采用免疫克隆算法的框架,同時在優(yōu)化過程中采用約束處理策略對目標函數(shù)值進行修正.并且,設(shè)置一個大小為N的精英種群,用來存儲可行非支配解集FeaNonPop.本文算法的主要目的是選取可行非支配解集FeaNonPop和目標函數(shù)值修正后的非支配解集ModNonPop.文獻中的算法等采用兩個步驟:1)尋找可行解;2)尋找可行非支配解.本文算法并沒有采用這種方法,原因如下:i)理論分析:通過對以下本文所采用的約束處理策略的分析,當(dāng)種群中無可行解時,約束處理策略給種群施加一個朝著可行解優(yōu)化的趨勢,使種群尋找可行解,這本身就替代了以上所提到的第1)步;通過以上分析,本文直接采用免疫克隆算法的框架進行優(yōu)化.同時,在不同的情況下,通過約束處理策略自適應(yīng)地調(diào)整種群進化趨勢,并針對約束多目標優(yōu)化問題的特點,設(shè)計了克隆、交叉、變異和選擇等算子.1.1非支配解集與精英種群的克隆克隆算子在本文算法中對解的多樣性分布和逼近性起著重要的作用,如文獻.本文算法在對父代抗體種群進行克隆時也采取整體克隆的方法,對父代的優(yōu)勢抗體種群進行n倍克隆,Pop={Pop,…,Pop}.這樣省去了為父代中的每個抗體分配適應(yīng)度值的操作,使得算法更加簡單.本文主要考慮兩種克隆方法:1)克隆非支配解集ModNonPop的同時,將精英種群中的可行非支配解集FeaNonPop復(fù)制進克隆后的種群中,如式(8)所示:其中,將非支配解集ModNonPop克隆n倍,將可行非支配解集FeaNonPop克隆k倍.2)僅僅克隆非支配解集ModNonPop.此時,精英種群只起到一種存儲可行非支配解集FeaNonPop的作用,該克隆過程如式(9)所示:通過大量的實驗結(jié)果表明:方法1)將可行非支配解集FeaNonPop克隆進種群Pop,對優(yōu)化結(jié)果幫助不大.同時,由于可行非支配解集FeaNonPop的引入,使得優(yōu)化過程中的可行非支配解集規(guī)模幾乎成倍上升,給后面的選擇更新操作造成了很大的壓力,從而使算法花費大量時間在選擇更新操作上,即使當(dāng)k為1時也是如此.因此采用方法2),僅僅考慮非支配解集ModNonPop.具體操作過程見表1.1.2ialmoct算子本文采用文獻中模擬二進交叉(SBXcross-over)算子(如公式(10)所示)和多項式變異(polynomialmutation)算子(如公式(12)所示).其中,其中,aik,ajk(i≠j,k=1,…,n)是抗體i,j的第k個決策變量,r,u是分布在之間的隨機數(shù).其中,其中,uf0641=(vk-lk)/(uk-lk),uf0642=(uk-vk)/(uk-lk),u是間分布的隨機數(shù),uk和lk分別為vk的上界和下界.交叉變異操作見表2.1.3選擇正確的非支配抗體原子類本文算法的選擇操作不像NSGA-II那樣對種群每個個體分配非支配等級,然后根據(jù)非支配等級進行個體選擇,而是和文獻中一樣,直接在種群中選取非支配抗體,這樣有利于簡化算法.本文算法包括兩個選擇操作:選取可行非支配解集FeaNonPop和選取目標函數(shù)值修正后的非支配解集ModNonPop.這兩個選擇操作如第1.3.1節(jié)和第1.3.2節(jié)所示.1.3.1選取可行解集的方法首先從當(dāng)代進化種群Pop中根據(jù)每個個體的約束偏離值選取可行解集FeasiblePop,之后將FeaNonPop中的可行非支配解也復(fù)制進可行解集FeasiblePop中,在可行解集FeasiblePop中根據(jù)每個個體的目標函數(shù)值選取可行非支配解集FeaNonPop.表3給出選取可行非支配解集的主要步驟.1.3.2距離值和懲罰項的求解首先,根據(jù)文獻中的約束處理策略,通過距離值(distancevalue)和懲罰項(twopenalties)對當(dāng)代進化種群Pop中每個個體的目標函數(shù)值進行修正,如公式(14)所示.然后,根據(jù)修正后的目標函數(shù)值,從種群Pop中選取非支配解集ModNonPop.具體選擇操作與表3類似.其中,di(x)為個體x的第i維目標函數(shù)的距離值,pi(x)為個體x的第i維目標函數(shù)的懲罰項,fiuf0a2(x)為個體x修正后的第i個目標函數(shù)值.以下簡要介紹距離值和懲罰項的計算方法.根據(jù)種群中是否存在可行解,可以將距離值的求解分為兩種情況:1)不存在可行解時,距離值為非可行解的約束偏離值;2)存在可行解時,距離值是目標函數(shù)和約束偏離值共同作用的結(jié)果.下面為距離值的數(shù)學(xué)計算公式:其中,di(x)為個體x的第i維目標函數(shù)fi(x)的距離值,C(x)為個體x的約束偏離值,uf061為可行解的個數(shù)在種群中所占的比例.f(4)i(x)為個體x的第i維目標函數(shù)fi(x)的歸一化值,歸一化過程如下所示:其中,fimin為種群中第i個目標函數(shù)值的最小值,fimax為種群中第i個目標函數(shù)值的最大值.距離值的作用是:1)對可行解不進行懲罰,僅對非可行解進行懲罰;2)在非可行解中,約束偏離值大的個體受到的懲罰就越大.2)懲罰項可行解的懲罰項值為0,下面討論針對的都是非可行解.假定個體x為非可行解,其懲罰項pi(x)的求解公式如式(17)所示:其中,a為可行解在種群中所占的比例;為個體x的第i維目標函數(shù)fi(x)的歸一化值;Cuf0a2(x)為修正的約束偏離值,如式(18)所示:其中,C(x)為個體x的約束偏離值.在uf061=0即種群中沒有可行解時,懲罰項值為0.此時,僅靠距離值對目標函數(shù)值進行修正;當(dāng)uf061>0時,如果uf061較小即種群中可行解的個數(shù)較少,則懲罰項側(cè)重于對約束函數(shù)空間的懲罰,有利于種群中的非可行解朝可行解的方向進化;如果uf061較大即種群中可行解的個數(shù)較多,則懲罰項側(cè)重于對目標函數(shù)空間的懲罰,有利于種群中個體朝目標函數(shù)值最優(yōu)的方向進化.1.4算法的主要過程本節(jié)給出修正免疫克隆約束多目標優(yōu)化算法的主要流程,見表4.1.5基因參數(shù)所需復(fù)雜度k設(shè)在每一代進化中,種群FeaNonPop和ModNonPop的規(guī)模都為N,克隆倍數(shù)為c,變量的維數(shù)為n,約束維數(shù)為m,目標函數(shù)維數(shù)為k,則:·在每次克隆種群ModNonPop所用的復(fù)雜度為O(cN);uf0b7變異操作所需復(fù)雜度為O(ncN);·計算種群Pop目標函數(shù)值和約束偏離值的時間復(fù)雜度為O(ncN);uf0b7修正種群Pop中個體的目標函數(shù)值所需復(fù)雜度為O(3k(c+1)N+2m(c+1)N);·選取并更新可行非支配解集所需復(fù)雜度為O((2c+6+kc+2k)N+k(c+2)2N2+(c+2)(k+1)Nlog2((c+2)N));2實驗與分析2.1ctp4測試函數(shù)本文選取Deb等人在文獻中提出的6個經(jīng)典的最小化測試問題CTP2~CTP7,這類問題比較容易陷入局部最優(yōu),因而很難收斂到真正的Pareto前端,且這些測試函數(shù)隨約束問題和約束中參數(shù)取值的不同相應(yīng)的測試難度也有所不同.在下面的測試問題中,CTP4測試難度較大.6個測試問題的數(shù)學(xué)模型如式(19)所示:其中,其中,變量范圍x1uf0ce,-5≤xi≤5,i=2,…,10,變量uf071,a,b,c,d,e的取值見表5.CTP2和CTP7最優(yōu)解為間斷的連續(xù)區(qū)域,CTP3~CTP5最優(yōu)解主要考慮幾個離散點,CTP6的最優(yōu)解為連續(xù)區(qū)域.2.2pfk4index,di,n,d,d,d,d本文采用3項測試指標來度量算法的性能,具體如下:1)逼近性度量指標:世代距離(generationaldistance,簡稱GD)世代距離測量所得到的Pareto前端PFknown和真實前端PFtrue之間的距離,世代距離的值越小,說明所求得的Pareto前端PFknown越接近PFtrue,結(jié)果就越好.世代距離的數(shù)學(xué)表達式如公式(21)所示:其中,n是PFknown中個體的個數(shù),p=2,di是PFknown中第i個個體的目標函數(shù)向量到PFtrue中最近的那個個體的歐氏距離.2)分布性度量指標:空間度量(thespacing,簡稱S)空間度量指標用于度量Pareto前端PFknown分布的均勻性,其值越小,說明PFknown上解分布得越均勻.空間度量指標的數(shù)學(xué)表達式如公式(22)所示:其中,di=minj(|f2i(x)-f1j(x)|+|f2i(x)-f2j(x)|),i,j=1,...,n,d是di的均值,n是PFknown中個體的個數(shù).3)多樣性度量指標:修正后的最大展布(MSuf0a2)最大展布用于測量所求的Pareto前端PFknown覆蓋真實前端PFtrue的程度,MSuf0a2的值越大,說明PFknown覆蓋PFtrue的范圍就越大,所求的解集就越好.最大展布MSuf0a2的數(shù)學(xué)表達式如公式(23)所示:其中,是PFknown中第i個目標函數(shù)的最大值和最小值.同樣,是PFtrue中第i個目標函數(shù)的最大值和最小值.由于有些測試問題的Pareto前端是幾個間斷的點,此時,如果再采用空間度量指標和最大展布去測量所求得解集PFknown分布的均勻性和多樣性,已顯得不太合適,所以本文采用文獻中Xiao提出的方法,把測試問題分為3組,對不同組的測試問題采用不同的評價指標.2.3測試結(jié)果仿真與約束單目標優(yōu)化算法和無約束的多目標優(yōu)化算法不同,約束多目標優(yōu)化算法更為復(fù)雜,求解更加困難.為了說明本文算法的性能,將本文算法與NSGA-II約束多目標優(yōu)化算法(以下簡稱NSGA-II算法)和文獻中的算法(以下簡稱“文獻算法”)兩種優(yōu)秀的算法進行對比.NSGA-II算法和文獻中算法參數(shù)的設(shè)置如下:初始種群大小為100,交叉概率為0.9,交叉分布指數(shù)為15,變異概率為0.1,變異分布指數(shù)為20.本文算法的參數(shù)設(shè)置如下:初始種群個數(shù)為400,交叉概率為0.9,交叉分布指數(shù)為15,變異概率為0.1,變異分布指數(shù)為20,最大的可行非支配解集FeaNonPop大小為100,修正非支配解集ModNonPop大小為100.為了選擇合適的進化代數(shù),本文測試了3種算法在不同的測試函數(shù)上的GD指標,代數(shù)范圍在[1000~10000],每隔1000代統(tǒng)計1次,獨立運行50次,取其均值.以CTP2測試函數(shù)為例,如圖1所示.由圖1可以看出,3種算法在進化到6000代時,GD指標趨于穩(wěn)定.根據(jù)該方法,為了得到每種算法在每個測試函數(shù)上的最優(yōu)解,這里設(shè)定3種算法迭代次數(shù)均為10000次,對每個測試問題均獨立運行50次.仿真結(jié)果如圖2和圖3所示.在圖2中,對于CTP2~CTP5這4個測試問題,陰影部分為可行目標空間.測試問題CTP2的Pareto前端都是由許多不連續(xù)區(qū)域的點構(gòu)成,該問題難度較大.由圖2可以看出,對于CTP2,3種算法都能較好地收斂于Pareto前端,且多樣性和均勻性都比較好.而測試問題CTP3~CTP5的Pareto前端由一系列離散的點構(gòu)成,相對于CTP2問題難度更大.如何全面地找到這些點,是測試算法準確度的重要指標.對比圖2可以看出,對于CTP3~CTP5這3種測試問題,3種算法都能較好地收斂于Pareto前端.然而與其他兩種算法相比,本文算法找到的離散解的個數(shù)明顯多于NSGA-II算法和文獻算法所找到的解,說明本文算法具有較強的搜索能力以及較好的保持多樣性的能力.圖3為3種算法關(guān)于CTP6和CTP7的仿真結(jié)果,圖3中陰影部分為這兩個測試問題的可行目標空間.由圖3可以看出,其可行域是一系列不連續(xù)的帶狀區(qū)域.在求解CTP6時,很容易陷入局部最優(yōu),找到的解容易收斂于Pareto前端上方的曲線上;在求解CTP7時,不僅很容易丟失部分可行域,而且也容易陷入局部最優(yōu).比較圖3中3種算法關(guān)于CTP6的仿真結(jié)果可以得出:對于解的多樣性和收斂性,3種算法的結(jié)果相似,但是文獻算法找到的解的均勻性最差,NSGA-II次之,本文算法均勻性最好.對于測試問題CTP7,3種算法都較好地收斂到最優(yōu)約束Pareto前端.為進一步對比幾種算法的性能,根據(jù)第2.2節(jié)給出的評價指標對各測試問題的測試結(jié)果進行測試,并得出50次獨立運行結(jié)果的平均值和標準差,見表6~表8.從表6可以看出,對測試問題CTP2和CTP7,新算法的世代距離和空間分布的均值都明顯小于NSGA-II算法和文獻算法所得的結(jié)果,說明新算法優(yōu)化所得的解集更接近真實PFtrue,同時也說明本文算法所得的解集分布的均勻性比NSGA-II算法和文獻算法要好.3種算法每次都能找到所有的離散區(qū)域.對CTP2測試問題,雖然文獻算法得到的解集空間分布的標準差最小,但其均值最大.尤其是對CTP7測試問題而言,雖然文獻算法得到的世代距離的標準差明顯低于本文算法和NSGA-II算法,但其世代距離的均值明顯高于其余兩種算法.從表7可以看出,對CTP3~CTP5測試問題,本文算法每次運行都能找到離散點的個數(shù)明顯多于NSGA-II算法和文獻算法;尤其是對CTP3問題,本文算法每次運行都能找到全部的離散點,說明本文算法在多樣性保持方面要明顯優(yōu)于NSGA-II算法