基于記憶策略的動態分解約束多目標進化算法

陳創明，溫潔嫦

（廣東工業大學應用數學學院，廣東 廣州 510520）

0 引言

約束多目標優化問題廣泛存在于科學、工程、醫學等眾多領域中[1-4].一般情況下，約束多目標優化問題可以表述為：

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

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

近10年來，基于分解的多目標進化算法得到了充分的發展，在多目標優化領域上取得了大量的成果[14-17].其中，文獻[15]提出一種具有區域保護機制的分解多目標進化算法（M2M）.該方法將一個多目標優化問題分解成多個簡單子多目標優化問題.該方法被設計用于求解無約束的多目標優化問題.對于約束多目標優化問題，該方法的某些子問題由于約束的原因可能只保留了非容許解或者為空集，浪費了計算資源，導致算法的求解效率低下.

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

1 基于記憶與動態分解策略的算法設計

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

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

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

本文使用IGD度量[18]衡量兩個種群的相似度，當IGD值越小時，其兩個種群越相似.一般情況下，IGD度量用于衡量一個多目標進化算法的收斂性能，由式（2）給出：

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

在第二階段中，個體依照基于容許解優先的約束處理方法進行選擇個體，具體步驟如下：

1）當容許解個數大于N時，從中按非支配排序選擇前N個容許解作為下一代種群個體.

2）當容許解個體小于N時，則優先選擇全部容許解，剩下的個數從非容許解中按約束違反程度從小到大選擇，直到種群大小為N.

1.2 動態分解策略

文獻[15]提出的M2M算法是一種具有區域保護機制的分解多目標進化算法.M2M將問題（1）分解成S個簡單的多目標優化子問題，并在一次運行中同時解決這個S個子問題.該算法首先從目標空間上的超平面上均勻取S個單位中心權重向量v1，…，vs，接著將目標空間分成S個子區域Ω1，…，Ω2，其中，Ωi由式（3）表示：

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

該算法將靠近于某一單位中心權重向量的個體規劃為同一個區域，對于約束多目標優化問題，某個區域可能全是非容許解或者這個單位中心權重向量周圍沒有個體而導致這個子區域不存在個體.當M2M遇到某子區域沒有個體時，并從種群中隨機復制其他個體.但是這種做法并不能提升算法的性能，個體的重復復制占用算法的計算資源.針對上述情況，本文提出一種動態分配計算資源的分解策略，具體思想如算法2.

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

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

1.3 本文算法流程

結合章節2.1和2.2，本小節提出本文的算法框架.基于記憶策略的動態分解約束多目標進化算法的具體步驟如下：

1）參數設置及初始化.產生一個大小為N初始種群，在m維超平面上均勻產生N個權

2）重向量以及S個單位中心權重向量.初始化M2M算法的參數，包括子區域的種群大小si，參考點.設置算法停止條件.

3）根據式（1）和式（5）計算種群的目標函數值 F（x）和約束違反程度 G（x）.

4）使用基于DE/RAND/1/BIN[5]的進化算子產生子代種群.

5）將父代種群與子代種群合并到一起，根據式（3）進行分區域，并更新M2M的參數.

6）根據算法1和算法2，將步驟4中分區域后每一個子種群進行選擇操作，選擇si個最優個體進入到下一代.

7）判斷是否滿足算法停止條件.如是，停止算法，并輸出當前種群的容許個體作為求解的約束多目標優化問題的最優解集.否則跳轉到步驟3.

根據式（1），個體x在第i個約束的約束違反程度使用式（4）進行計算：

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

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

2 實驗結果及分析

2.1 對比算法與基準測試問題

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

表1 本文提出的算法與CMOEA/D-CDP、CM2M2的實驗對比結果

本文采用CTP系列約束多目標優化問題[8]作為基準測試問題，并使用1個實際工程優化問題Speed Reducer Design Problem（SRDP）[19]進一步檢驗本文提出算法的性能，該問題包括2個目標函數，7個決策變量，和11個不等式約束.

2.2 評價指標

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

2.3 算法參數設置

本文提出的算法與對比算法的參數設置如下：

1）種群大小N設置為100，運行代數設置為1 000代.

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

4）基于DE/RAND/1/BIN的進化算子的DE參數CR設置為0.1，F設置為0.8.

5）本文提出的算法和對比算法在9個測試問題上分別獨立運行30次.

6）CM2M2的非容許權重數設置為30，容許權重數設置70.

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

2.4 實驗結果與分析

表1展示了本文所出算法與CMOEA/D-CDP、CM2M2基于IGD與HV度量指標的平均值與標準差的實驗對比結果.算法在某一個測試問題求到的結果最優則進行標黑處理.

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

圖1-6展示了三個算法基于IGD值中位數運行的IGD變化曲線.橫坐標generation表示代數，縱坐標表示IGD值，當IGD值為0時表示此時算法的種群全為非容許解.

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

關于圖6，算法CM2M2以及CMOEA/D只收斂到最優邊界的一部分，導致最終得到較差的IGD值.另外，由于SRDP問題的最優邊界具有不規則的形狀，CM2M2出現了不斷震蕩的現象，在進化的過程，當出現少數點在不規則最優邊界部分時，IGD的值則變小.但這部分的個體難以保留，因而IGD的值變大.同樣的情況可以在本文算法上觀察到，但由于本文算法采用動態分解的策略，從而避免該情況惡化的發生.

圖1 CTP1的IGD變化曲線

圖2 CTP2的IGD變化曲線

圖3 CTP6的IGD變化曲線

圖4 CTP7的IGD變化曲線

圖5 CTP8的IGD變化曲線

圖6 SRDP的IGD變化曲線

2.5 算法參數r的敏感性分析

本小節討論本文所提出算法中參數r的敏感度.以CTP6作為測試例子，分別取五個不同的值，即0.001，0.005，0.01，0.05和0.1.對于每個不同的r，本文算法其他參數保持不變，并獨立運行30次，統計IGD與HV值，如表2所示.

表2 參數r的敏感度

參數r用于衡量兩個種群間的相似度，即控制從第一階段跳轉到第二階段所需要的計算資源，其值越大，越容易從第一階段跳轉到第二階段.從表2中可以看出，當參數r小于0.05時，其算法求到的IGD與HV值維持在一定的范圍內，較為穩定.因為，參數r的建議取值范圍為區間（0.001，0.05）.

2.6 算法參數k的敏感性分析

本小節討論本文所提出算法中參數k的敏感度.以CTP6作為測試例子，分別取五個不同的值，即5，10，15，20和25.對于每個不同的k，本文算法其他參數保持不變，并獨立運行30次，統計IGD與HV值，如表3所示.

表3 參數k的敏感度

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

3 結論

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