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

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

0 引言

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

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

近10年來(lái)，基于分解的多目標(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)化問(wèn)題分解成多個(gè)簡(jiǎn)單子多目標(biāo)優(yōu)化問(wèn)題.該方法被設(shè)計(jì)用于求解無(wú)約束的多目標(biāo)優(yōu)化問(wèn)題.對(duì)于約束多目標(biāo)優(yōu)化問(wèn)題，該方法的某些子問(wèn)題由于約束的原因可能只保留了非容許解或者為空集，浪費(fèi)了計(jì)算資源，導(dǎo)致算法的求解效率低下.

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

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

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

基于短暫忽略約束的約束處理方法在求解約束多目標(biāo)優(yōu)化問(wèn)題具有優(yōu)秀的性能，但對(duì)于非容許與容許最優(yōu)界面不一致的問(wèn)題，求解效果較差.針對(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í)只通過(guò)目標(biāo)值的非支配關(guān)系進(jìn)行對(duì)比，并將容許解保存到歸檔集A中，當(dāng)A的大小超過(guò)種群大小N時(shí)，則使用非支配排序選擇前N個(gè)最優(yōu)個(gè)體.3）第二階段：進(jìn)入第二階段時(shí)，首先將歸檔集中的容許解參與種群選擇操作，替代非容許解，同時(shí)將非容許解中的非支配解保存到歸檔集，并參與后續(xù)進(jìn)化過(guò)程，提高求解的質(zhì)量.在該階段中使用基于容許解優(yōu)先的約束處理方法進(jìn)行選擇個(gè)體.

本文使用IGD度量[18]衡量?jī)蓚€(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將問(wèn)題（1）分解成S個(gè)簡(jiǎn)單的多目標(biāo)優(yōu)化子問(wèn)題，并在一次運(yùn)行中同時(shí)解決這個(gè)S個(gè)子問(wèn)題.該算法首先從目標(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)化問(wèn)題，某個(gè)區(qū)域可能全是非容許解或者這個(gè)單位中心權(quán)重向量周圍沒(méi)有個(gè)體而導(dǎo)致這個(gè)子區(qū)域不存在個(gè)體.當(dāng)M2M遇到某子區(qū)域沒(méi)有個(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.

由于第一階段處于搜索的過(guò)程，最大程度保留分區(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)化問(wèn)題的最優(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è)試問(wèn)題

本文算法與CMOEA/D-CDP[2]以及CM2M2[8]進(jìn)行算法對(duì)比（見(jiàn)表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)化問(wèn)題[8]作為基準(zhǔn)測(cè)試問(wèn)題，并使用1個(gè)實(shí)際工程優(yōu)化問(wèn)題Speed Reducer Design Problem（SRDP）[19]進(jìn)一步檢驗(yàn)本文提出算法的性能，該問(wè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值越大，說(shuō)明算法的收斂性與散布性更好.在計(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）用于衡量?jī)蓚€(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è)試問(wèn)題上分別獨(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è)試問(wèn)題求到的結(jié)果最優(yōu)則進(jìn)行標(biāo)黑處理.

從表1的結(jié)果觀察可以得出，本文所提出的算法在大部分基準(zhǔn)測(cè)試問(wèn)題如CTP1、CTP2、CTP6、CTP8以及SRDP上相比于CMOEA/D-CDP與CM2M2求到更優(yōu)的結(jié)果，說(shuō)明了本文所提算法在這些問(wèn)題上求到解集的收斂性與散布性更優(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è)試問(wèn)題上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問(wèn)題的最優(yōu)邊界具有不規(guī)則的形狀，CM2M2出現(xiàn)了不斷震蕩的現(xiàn)象，在進(jìn)化的過(guò)程，當(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)?，分別取五個(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用于衡量?jī)蓚€(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)樱謩e取五個(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è)工程問(wèn)題，仿真結(jié)果表明了本文所提出算法的優(yōu)異性能.另外，本文還對(duì)所提算法進(jìn)行了參數(shù)敏感度分析，結(jié)果表明該算法對(duì)參數(shù)r在取值區(qū)間（0.001，0.05）之間不敏感，對(duì)參數(shù)k在取值5～20之間不敏感.