基于記憶策略的動(dòng)態(tài)分解約束多目標(biāo)進(jìn)化算法

陳創(chuàng)明，溫潔嫦

（廣東工業(yè)大學(xué)應(yīng)用數(shù)學(xué)學(xué)院，廣東 廣州 510520）

0 引言

約束多目標(biāo)優(yōu)化問題廣泛存在于科學(xué)、工程、醫(yī)學(xué)等眾多領(lǐng)域中[1-4].一般情況下，約束多目標(biāo)優(yōu)化問題可以表述為：

其中D是n維自變量空間，F(xiàn)（x）是m維目標(biāo)函數(shù)向量，同時(shí)滿足所有的約束條件gi（x）和hi（x）的自變量的取值范圍即為容許域.在容許域中的解稱為容許解，反之稱為非容許解.gi（x）是第i個(gè)不等式約束條件，hi（x）是第i個(gè)等式約束條件.

在實(shí)際優(yōu)化問題[5-7]中，約束的存在不僅使可行域變小，同時(shí)還使得整個(gè)進(jìn)化過程變得更加復(fù)雜.這要求一個(gè)算法在解決多目標(biāo)優(yōu)化問題需要具有高效的約束處理方法.文獻(xiàn)[8]提出了2種基于分解的約束多目標(biāo)進(jìn)化算法，即CMOEA/D-CDP和CMOEA/D-SR，這兩個(gè)算法都偏重于選擇容許解.當(dāng)遇到一個(gè)帶嚴(yán)重約束的多目標(biāo)優(yōu)化問題時(shí)，特別是當(dāng)這個(gè)問題的容許域是分開的幾片時(shí)，它們有可能會(huì)陷入其中一個(gè)片容許域中，而很難跳到另外一片容許域中，除非它們靠的很近.文獻(xiàn)[9]提出了一種基于引導(dǎo)權(quán)重的約束多目標(biāo)進(jìn)化算法，該方法通過一組非容許權(quán)重保持非容許解的散布性，從而為算法的尋優(yōu)提供有效的幫助.近年來，在進(jìn)化過程中短暫忽略約束的約束處理方法引起了眾多學(xué)者的關(guān)注[10-13].這類方法在處理約束時(shí)不考慮約束，從而避免進(jìn)化過程約束所帶來的求解困難，接著在某個(gè)階段開始考慮約束，并逐漸收斂到可行域中.該方法在求解約束多目標(biāo)優(yōu)化問題中具體明顯的優(yōu)勢(shì)，但是，當(dāng)不考慮約束的最優(yōu)解邊界與考慮約束的最優(yōu)解邊界不一致時(shí)，這類方法難以收斂大部分考慮約束的最優(yōu)解邊界上.因此，如何有效地收斂到容許域，進(jìn)而尋找最優(yōu)解成為這類方法的痛點(diǎn).

近10年來，基于分解的多目標(biāo)進(jìn)化算法得到了充分的發(fā)展，在多目標(biāo)優(yōu)化領(lǐng)域上取得了大量的成果[14-17].其中，文獻(xiàn)[15]提出一種具有區(qū)域保護(hù)機(jī)制的分解多目標(biāo)進(jìn)化算法（M2M）.該方法將一個(gè)多目標(biāo)優(yōu)化問題分解成多個(gè)簡單子多目標(biāo)優(yōu)化問題.該方法被設(shè)計(jì)用于求解無約束的多目標(biāo)優(yōu)化問題.對(duì)于約束多目標(biāo)優(yōu)化問題，該方法的某些子問題由于約束的原因可能只保留了非容許解或者為空集，浪費(fèi)了計(jì)算資源，導(dǎo)致算法的求解效率低下.

針對(duì)上述問題，本文首先在基于短暫忽略約束的約束處理方法基礎(chǔ)上，引入具有記憶功能的歸檔集，將進(jìn)化過程中的容許解保留下來，并用于指導(dǎo)算法進(jìn)入容許域，避開陷入非容許域中，從而提高算法的求解魯棒性.接著，提出一種動(dòng)態(tài)分配計(jì)算資源的分解策略，對(duì)于具有全是非容許解或者為空集的子問題的計(jì)算資源重新分配到其他子問題中，從而提高算法的求解性能.

1 基于記憶與動(dòng)態(tài)分解策略的算法設(shè)計(jì)

1.1 基于記憶策略的約束處理方法

基于短暫忽略約束的約束處理方法在求解約束多目標(biāo)優(yōu)化問題具有優(yōu)秀的性能，但對(duì)于非容許與容許最優(yōu)界面不一致的問題，求解效果較差.針對(duì)這種情況，本文采用基于兩階段策略與具有記憶功能的歸檔集保存歷史發(fā)現(xiàn)的容許解，在第一階段跳轉(zhuǎn)到第二階段時(shí)將保存在歸檔集中的容許解用于指導(dǎo)算法進(jìn)入容許域，同時(shí)保留當(dāng)前較優(yōu)的非容許解于歸檔集中，用于后續(xù)算法尋優(yōu).具體步驟如算法1.

算法1：基于記憶策略的約束處理方法1）每10代判斷跳轉(zhuǎn)條件：使用式子（2）衡量第1代與第10代之間的相似度，當(dāng)IGD值小于預(yù)先給定的值r時(shí)，則跳轉(zhuǎn)到第二階段.否則保留在第一階段.2）第一階段：在第一階段中，在評(píng)價(jià)個(gè)體間的優(yōu)劣時(shí)只通過目標(biāo)值的非支配關(guān)系進(jìn)行對(duì)比，并將容許解保存到歸檔集A中，當(dāng)A的大小超過種群大小N時(shí)，則使用非支配排序選擇前N個(gè)最優(yōu)個(gè)體.3）第二階段：進(jìn)入第二階段時(shí)，首先將歸檔集中的容許解參與種群選擇操作，替代非容許解，同時(shí)將非容許解中的非支配解保存到歸檔集，并參與后續(xù)進(jìn)化過程，提高求解的質(zhì)量.在該階段中使用基于容許解優(yōu)先的約束處理方法進(jìn)行選擇個(gè)體.

本文使用IGD度量[18]衡量兩個(gè)種群的相似度，當(dāng)IGD值越小時(shí)，其兩個(gè)種群越相似.一般情況下，IGD度量用于衡量一個(gè)多目標(biāo)進(jìn)化算法的收斂性能，由式（2）給出：

其中，P*與P是給定的2個(gè)種群，d（v，P）表示個(gè)體v到種群P的距離.

在第二階段中，個(gè)體依照基于容許解優(yōu)先的約束處理方法進(jìn)行選擇個(gè)體，具體步驟如下：

1）當(dāng)容許解個(gè)數(shù)大于N時(shí)，從中按非支配排序選擇前N個(gè)容許解作為下一代種群個(gè)體.

2）當(dāng)容許解個(gè)體小于N時(shí)，則優(yōu)先選擇全部容許解，剩下的個(gè)數(shù)從非容許解中按約束違反程度從小到大選擇，直到種群大小為N.

1.2 動(dòng)態(tài)分解策略

文獻(xiàn)[15]提出的M2M算法是一種具有區(qū)域保護(hù)機(jī)制的分解多目標(biāo)進(jìn)化算法.M2M將問題（1）分解成S個(gè)簡單的多目標(biāo)優(yōu)化子問題，并在一次運(yùn)行中同時(shí)解決這個(gè)S個(gè)子問題.該算法首先從目標(biāo)空間上的超平面上均勻取S個(gè)單位中心權(quán)重向量v1，…，vs，接著將目標(biāo)空間分成S個(gè)子區(qū)域Ω1，…，Ω2，其中，Ωi由式（3）表示：

j＝1，2，3，…，S，〈F（x），vj〉是 F（x）和 vj之間的夾角.

該算法將靠近于某一單位中心權(quán)重向量的個(gè)體規(guī)劃為同一個(gè)區(qū)域，對(duì)于約束多目標(biāo)優(yōu)化問題，某個(gè)區(qū)域可能全是非容許解或者這個(gè)單位中心權(quán)重向量周圍沒有個(gè)體而導(dǎo)致這個(gè)子區(qū)域不存在個(gè)體.當(dāng)M2M遇到某子區(qū)域沒有個(gè)體時(shí)，并從種群中隨機(jī)復(fù)制其他個(gè)體.但是這種做法并不能提升算法的性能，個(gè)體的重復(fù)復(fù)制占用算法的計(jì)算資源.針對(duì)上述情況，本文提出一種動(dòng)態(tài)分配計(jì)算資源的分解策略，具體思想如算法2.

算法2：基于動(dòng)態(tài)分配計(jì)算資源的分解策略1）每隔k代判斷S個(gè)子區(qū)域中分配情況：當(dāng)算法進(jìn)入第二階段后，每隔10代判斷S個(gè)子區(qū)域的個(gè)體分配情況.2）當(dāng)?shù)趇個(gè)子區(qū)域中存在全部個(gè)體為非容許個(gè)體或者為空：將該子區(qū)域的計(jì)算資源隨機(jī)分配其他子區(qū)域中，即隨機(jī)增加其他子區(qū)域的大小，而該區(qū)域不再用于選擇個(gè)體，保持種群的大小始終為N.

由于第一階段處于搜索的過程，最大程度保留分區(qū)域的機(jī)制，有利于算法尋找出最優(yōu)解區(qū)域，因而在這個(gè)階段中不采用該動(dòng)態(tài)分解策略.當(dāng)算法進(jìn)入到第二階段時(shí)，每隔k代判斷每個(gè)子區(qū)域是否存在全是非容許解或者空的情況.若是，則將該子區(qū)域的選擇個(gè)體次數(shù)隨機(jī)分配到其他子區(qū)域中，提升算法對(duì)計(jì)算資源的利用率.值得注意的是，對(duì)于存在全是非容許解或者空集的子區(qū)域，依然保留著單位中心權(quán)重向量，當(dāng)該子區(qū)域在某一代中被分配到容許個(gè)體時(shí)，則重新用于選擇下一代個(gè)體.

1.3 本文算法流程

結(jié)合章節(jié)2.1和2.2，本小節(jié)提出本文的算法框架.基于記憶策略的動(dòng)態(tài)分解約束多目標(biāo)進(jìn)化算法的具體步驟如下：

1）參數(shù)設(shè)置及初始化.產(chǎn)生一個(gè)大小為N初始種群，在m維超平面上均勻產(chǎn)生N個(gè)權(quán)

2）重向量以及S個(gè)單位中心權(quán)重向量.初始化M2M算法的參數(shù)，包括子區(qū)域的種群大小si，參考點(diǎn).設(shè)置算法停止條件.

3）根據(jù)式（1）和式（5）計(jì)算種群的目標(biāo)函數(shù)值 F（x）和約束違反程度 G（x）.

4）使用基于DE/RAND/1/BIN[5]的進(jìn)化算子產(chǎn)生子代種群.

5）將父代種群與子代種群合并到一起，根據(jù)式（3）進(jìn)行分區(qū)域，并更新M2M的參數(shù).

6）根據(jù)算法1和算法2，將步驟4中分區(qū)域后每一個(gè)子種群進(jìn)行選擇操作，選擇si個(gè)最優(yōu)個(gè)體進(jìn)入到下一代.

7）判斷是否滿足算法停止條件.如是，停止算法，并輸出當(dāng)前種群的容許個(gè)體作為求解的約束多目標(biāo)優(yōu)化問題的最優(yōu)解集.否則跳轉(zhuǎn)到步驟3.

根據(jù)式（1），個(gè)體x在第i個(gè)約束的約束違反程度使用式（4）進(jìn)行計(jì)算：

然后，個(gè)體x的違反約束程度由式（5）給出：

其中，δ是容忍因子，通常取值0.000 1.

2 實(shí)驗(yàn)結(jié)果及分析

2.1 對(duì)比算法與基準(zhǔn)測(cè)試問題

本文算法與CMOEA/D-CDP[2]以及CM2M2[8]進(jìn)行算法對(duì)比（見表1），兩者都采用基于分解的多目標(biāo)進(jìn)化算法.CMOEA/D-CDP采用基于容許解優(yōu)先的約束處理方法，而CM2M2使用一組非容許權(quán)重保持優(yōu)秀的非容許解的散布性，從而達(dá)到更好地利用非容許解，為算法提供更好的進(jìn)化方向.

表1 本文提出的算法與CMOEA/D-CDP、CM2M2的實(shí)驗(yàn)對(duì)比結(jié)果

本文采用CTP系列約束多目標(biāo)優(yōu)化問題[8]作為基準(zhǔn)測(cè)試問題，并使用1個(gè)實(shí)際工程優(yōu)化問題Speed Reducer Design Problem（SRDP）[19]進(jìn)一步檢驗(yàn)本文提出算法的性能，該問題包括2個(gè)目標(biāo)函數(shù)，7個(gè)決策變量，和11個(gè)不等式約束.

2.2 評(píng)價(jià)指標(biāo)

本文采用IGD和HV[20]度量指標(biāo)評(píng)價(jià)約束多目標(biāo)進(jìn)化算法的性能.其中，IGD度量指標(biāo)用于衡量求到的種群與真實(shí)最優(yōu)邊界的相似度，IGD值越小，算法的收斂性能越好.而HV用于同時(shí)衡量算法的收斂性與散布性，HV值越大，說明算法的收斂性與散布性更好.在計(jì)算HV值時(shí)，需要事先給定一個(gè)參考點(diǎn).在本文中，CTP1-CTP8的參考點(diǎn)設(shè)置為真實(shí)最優(yōu)邊界，每一個(gè)目標(biāo)維度的最大值的1.1倍，SRDP的參考點(diǎn)設(shè)置為（3，18）.

2.3 算法參數(shù)設(shè)置

本文提出的算法與對(duì)比算法的參數(shù)設(shè)置如下：

1）種群大小N設(shè)置為100，運(yùn)行代數(shù)設(shè)置為1 000代.

3）用于衡量兩個(gè)種群相似度的參數(shù)r設(shè)置為0.005；所隔代數(shù)k設(shè)置為10.

4）基于DE/RAND/1/BIN的進(jìn)化算子的DE參數(shù)CR設(shè)置為0.1，F(xiàn)設(shè)置為0.8.

5）本文提出的算法和對(duì)比算法在9個(gè)測(cè)試問題上分別獨(dú)立運(yùn)行30次.

6）CM2M2的非容許權(quán)重?cái)?shù)設(shè)置為30，容許權(quán)重?cái)?shù)設(shè)置70.

7）CMOEA/D-CDP與CM2M2剩下的參數(shù)與原文保持一致.

2.4 實(shí)驗(yàn)結(jié)果與分析

表1展示了本文所出算法與CMOEA/D-CDP、CM2M2基于IGD與HV度量指標(biāo)的平均值與標(biāo)準(zhǔn)差的實(shí)驗(yàn)對(duì)比結(jié)果.算法在某一個(gè)測(cè)試問題求到的結(jié)果最優(yōu)則進(jìn)行標(biāo)黑處理.

從表1的結(jié)果觀察可以得出，本文所提出的算法在大部分基準(zhǔn)測(cè)試問題如CTP1、CTP2、CTP6、CTP8以及SRDP上相比于CMOEA/D-CDP與CM2M2求到更優(yōu)的結(jié)果，說明了本文所提算法在這些問題上求到解集的收斂性與散布性更優(yōu).而且在CTP3、CTP5與CTP7求到的HV值也優(yōu)于另外兩個(gè)對(duì)比算法，進(jìn)一步證明了本文所提算法性能的優(yōu)異性.由于CTP6與CTP8具有約束難的特點(diǎn)，特別是CTP8，具有幾片離散容許域，導(dǎo)致CMOEA/D-CDP陷入了局部最優(yōu)區(qū)域中，主要是由于該算法使用了基于容許解優(yōu)先的約束處理方法.對(duì)于CM2M2，在CTP6與CTP8都求到了最優(yōu)邊界，但在這2個(gè)測(cè)試問題上CM2M2的部分子區(qū)域保留的個(gè)體全是非容許的或者為空，浪費(fèi)了計(jì)算資源.由于CM2M2與本文的算法都采用同一種分區(qū)域策略，因此CM2M2在CTP6與CTP8的實(shí)驗(yàn)結(jié)果從側(cè)面驗(yàn)證了本文所提出的基于動(dòng)態(tài)分解的策略的性能.

圖1-6展示了三個(gè)算法基于IGD值中位數(shù)運(yùn)行的IGD變化曲線.橫坐標(biāo)generation表示代數(shù)，縱坐標(biāo)表示IGD值，當(dāng)IGD值為0時(shí)表示此時(shí)算法的種群全為非容許解.

本文所提出算法的性能可以從圖1-6中直接觀察得出.基于記憶功能的動(dòng)態(tài)分解約束多目標(biāo)進(jìn)化算法優(yōu)于另外兩個(gè)對(duì)比算法.對(duì)于圖3與圖5，由于CMOEA/D-CDP陷入了局部最優(yōu)區(qū)域中，導(dǎo)致算法最終得到較大的IGD值.同時(shí)從圖3中可以觀察到，當(dāng)代數(shù)generation達(dá)到100時(shí)，本文所提出的算法得到的IGD值為零，主要由于此時(shí)算法位于第一階段，在進(jìn)行選擇操作時(shí)忽略了約束，從而導(dǎo)致種群全為非容許解，隨著代數(shù)的增加，算法進(jìn)入了第二階段，算法逐漸收斂于最優(yōu)邊界.

關(guān)于圖6，算法CM2M2以及CMOEA/D只收斂到最優(yōu)邊界的一部分，導(dǎo)致最終得到較差的IGD值.另外，由于SRDP問題的最優(yōu)邊界具有不規(guī)則的形狀，CM2M2出現(xiàn)了不斷震蕩的現(xiàn)象，在進(jìn)化的過程，當(dāng)出現(xiàn)少數(shù)點(diǎn)在不規(guī)則最優(yōu)邊界部分時(shí)，IGD的值則變小.但這部分的個(gè)體難以保留，因而IGD的值變大.同樣的情況可以在本文算法上觀察到，但由于本文算法采用動(dòng)態(tài)分解的策略，從而避免該情況惡化的發(fā)生.

圖1 CTP1的IGD變化曲線

圖2 CTP2的IGD變化曲線

圖3 CTP6的IGD變化曲線

圖4 CTP7的IGD變化曲線

圖5 CTP8的IGD變化曲線

圖6 SRDP的IGD變化曲線

2.5 算法參數(shù)r的敏感性分析

本小節(jié)討論本文所提出算法中參數(shù)r的敏感度.以CTP6作為測(cè)試?yán)樱謩e取五個(gè)不同的值，即0.001，0.005，0.01，0.05和0.1.對(duì)于每個(gè)不同的r，本文算法其他參數(shù)保持不變，并獨(dú)立運(yùn)行30次，統(tǒng)計(jì)IGD與HV值，如表2所示.

表2 參數(shù)r的敏感度

參數(shù)r用于衡量兩個(gè)種群間的相似度，即控制從第一階段跳轉(zhuǎn)到第二階段所需要的計(jì)算資源，其值越大，越容易從第一階段跳轉(zhuǎn)到第二階段.從表2中可以看出，當(dāng)參數(shù)r小于0.05時(shí)，其算法求到的IGD與HV值維持在一定的范圍內(nèi)，較為穩(wěn)定.因?yàn)?，參?shù)r的建議取值范圍為區(qū)間（0.001，0.05）.

2.6 算法參數(shù)k的敏感性分析

本小節(jié)討論本文所提出算法中參數(shù)k的敏感度.以CTP6作為測(cè)試?yán)?，分別取五個(gè)不同的值，即5，10，15，20和25.對(duì)于每個(gè)不同的k，本文算法其他參數(shù)保持不變，并獨(dú)立運(yùn)行30次，統(tǒng)計(jì)IGD與HV值，如表3所示.

表3 參數(shù)k的敏感度

參數(shù)k用于算法進(jìn)入到第二階段時(shí)，每隔k代判斷每個(gè)子區(qū)域是否存在全是非容許解或者空的情況.從表3可以看出，本文算法對(duì)該參數(shù)不敏感.

3 結(jié)論

本文提出了一種基于記憶策略的動(dòng)態(tài)分解約束多目標(biāo)進(jìn)化算法.首先引入了具有記憶功能的歸檔集，改進(jìn)了基于短暫忽略非容許解的約束處理方法，從而提高算法的求解魯棒性.結(jié)合基于分解的多目標(biāo)進(jìn)化算法，設(shè)計(jì)了一種動(dòng)態(tài)分配搜索資源的策略，提高算法的尋優(yōu)能力.并將設(shè)計(jì)的算法用于求解約束多目標(biāo)基準(zhǔn)測(cè)試集和1個(gè)工程問題，仿真結(jié)果表明了本文所提出算法的優(yōu)異性能.另外，本文還對(duì)所提算法進(jìn)行了參數(shù)敏感度分析，結(jié)果表明該算法對(duì)參數(shù)r在取值區(qū)間（0.001，0.05）之間不敏感，對(duì)參數(shù)k在取值5～20之間不敏感.