基于協同進化的約束多目標優化算法

張祥飛，魯宇明，張平生

（南昌航空大學航空制造工程學院，南昌 330063）

0 引言

在實際工程應用中，很多優化問題在優化多個目標的同時還需要處理各種類型的約束，這類問題被稱為約束多目標優化問題（Constrained Multi-objective Optimization Problem，CMOP）。早在十幾年前，研究人員針對CMOP 求解已經提出了以無約束的多目標優化方法加約束處理技術的求解方法［1-3］。隨著科技的發展，實際工程應用中的要求也隨之提高，使用以往的方法已經難以滿足實際使用需求，因此各種新型約束多目標優化算法被陸續提出。文獻［4］中提出了一種多階段的優化方法，在不同的階段采取不同的優化方法；文獻［5］中提出了一種推拉搜索框架，將求解過程分成推拉兩個搜索階段，采用多階段的算法一般具有較快的收斂速度。

由于協同進化算法在求解大規模、高維度和動態優化問題時取得了良好的效果［6-8］，近些年部分研究人員開始運用協同進化的思想求解CMOP，并取得了良好的效果。文獻［9］中設立了面向收斂的存檔和面向多樣性的存檔兩個種群，面向收斂的存檔同時優化約束和目標，面向多樣性的存檔僅優化目標，兩個種群在交配選擇和環境選擇相互合作；文獻［10］中將CMOP 分解成約束單目標優化問題，對每個約束單目標優化問題設置獨立的種群進行演化，同時設置了一個用于收集其他子種群中非劣解的子種群，基于協同進化的算法往往可以獲取良好的結果。

以上兩種類型約束多目標優化算法雖然具有各自的優勢，但也存在一定的不足。例如文獻［4-5］中提出的算法雖然具有良好的收斂速度，但高度依賴決定搜索階段切換的參數大小選取；文獻［9］中算法在高維CMOP 上的平衡收斂性和多樣性具有良好表現，但是在低維優化問題上表現一般。文獻［11］中從MOEA/D 內在機制及約束處理技術的適應性上展開研究，提出了一種權重向量和個體間的重新匹配策略實現對多樣性和收斂性的兼顧。本文借鑒文獻［11］的研究思路，從多階段和協同進化兩種優化方式的互補性展開研究，提出基于協同進化的約束多目標優化算法，通過融合多階段和協同進化這兩種優化方式，具有良好的收斂性能，同時能夠較好地兼顧多樣性和收斂性。

1 相關研究

1.1 CMOP及其相關定義

不失一般性，一個CMOP表達如式（1）所示：

式中：x是一個D維的決策變量；Ω表示決策空間；F(x)由n個實值目標函數組成的目標空間；l和q分別表示不等式和等式約束的數量。

通常情況下，等式約束都會轉化成不等式約束的形式，如式（2）所示：

其中：δ為等式約束的容忍參數，一般設定為0.000 1。

決策變量x的約束違反程度如式（3）所示：

定義1 可行解。決策變量x當且僅當G(x)=0時，決策變量x為可行解，否則決策變量x為不可行解。

定義2 Pareto 支配。決策變量xuPareto 支配決策變量xv，記為xu?xv，當且僅當：

1）?i∈{1，2，…，m}滿足fi(xu)≤fi(xv)；

2）?j∈{1，2，…，m}滿足fj(xu)＜fj(xv)。

定義3 Pareto 最優解。決策變量xu作為Pareto 最優解，當且僅當決策變量xu在整個目標集中為非支配解。

定義4 理想點（ideal point）。理想點z*可表示為z*=(i=1，2，…，n)，決策變量x為可行解。

定義5 極值點（nadir point）。極值點znad可表示為znad=，決策變量x為Pareto最優解。

1.2 約束處理技術

近二十幾年以來，針對單目標優化問題已經有很多約束處理技術被提出，主要有可行性準則、罰函數法、ε 約束處理法和多目標優化法等［12］。但這些約束處理技術一般不能直接運用于求解CMOP，雖然它們通過拓展或修改可以運用于求解CMOP，但這類方法具有很大的局限性，在處理低可行域、強約束和不連續帕累托前沿等類型問題時難以取得良好的效果。

在求解CMOP 上，主要有多階段和協同進化兩種優化方式。多階段優化方式一般是將優化過程劃分為多個階段，不同的階段采用不同的約束處理技術或優化不同的對象，如文獻［4-5］中通過多階段的形式實現了多種約束處理技術的優勢互補。協同進化是指多個對象通過一定的機制和策略開展協同搜索的進化技術，比如多種群、多算法、多操作和多策略集成式進化［13］，這類方法大多采取多種群或多種約束處理技術集成式進化。文獻［14-15］中通過多種群的形式集成了多種約束處理技術，不同的種群采用不同的約束處理技術，然后通過種群之間的各種交互方式實現信息共享，有效地發揮了多種約束處理技術優勢。

2 基于協同進化的約束多目標優化算法

考慮從可行解的搜索階段和協同進化階段入手設計本算法。

1）第一階段，創建多個子種群的穩態演化方法，保證在演化初始階段可以獲取一批高質量可行解，同時保持種群的多樣性；

2）第二階段，基于可行性準則和指定的子種群規模，將種群中的個體分成兩個子種群，并對兩個子種群分別采用網格約束分解和加權轉化單目標的方法引導兩個子種群的進化，分別負責算法的多樣性和收斂性。

綜上所述，給出本文算法的主要步驟：

步驟1 初始化規模為N1+N2的種群P。

步驟2 若種群P中可行解數量小于N1，執行第一階段演化方法；否則，在種群P中選擇N1個可行解為子種群P1，子種群P2=P-P1，執行第二階段演化方法，合并兩個子種群。

步驟3 若滿足算法停止條件，則輸出種群中的可行解；否則，轉步驟2。

2.1 穩態演化方法

由于約束數量、形式及數學特性等方面的影響，一個約束優化問題的可行域可能會非常小或離散，這往往會導致求解該問題的算法收斂效果不佳，甚至無法收斂的情況發生。對于一個約束多目標優化問題來講，在優化多個目標的同時需要處理約束問題，因此在進行多目標優化之前，為配合協同進化，我們需要獲取一個擁有一定數量可行解且具有良好多樣性的種群。因此，本文提出了一種穩態的演化方法。差分進化［16］因其簡單和有效的搜索能力而受到廣泛使用，所以穩態演化選用差分進化作為該方法的搜索引擎。差分進化主要由變異、交叉和選擇組成，其中一般常使用的變異算子如式（4）～（6）所示：

其中：xr1、xr2和xr3是三個相互不同的個體；xbest是種群中最好的個體；F是變異因子。

交叉算子主要在目標向量xi和變異向量vi當中生成實驗向量ui=(ui，1，ui，2，…，ui，D)，二項式交叉算子如式（7）所示：

其中：randj是在[0，1]區間的隨機數；jrand是{1，2，…，D}中隨機的一個整數；CR是交叉因子。

圖1 展示了穩態演化方法的框架：首先將種群隨機地劃分為m個子種群，然后以式（6）、（7）進行變異和交叉操作，得出相應子種群的后代，在每個子種群之間使用約束支配準則（Constrained Dominance Principle，CDP）［1］更新篩選父本與子代，得到一個新的子種群，最后這些新的子種群集成新的種群P。該方法的目的在于保持種群多樣性的同時尋找到高質量的可行解。

圖1 穩態演化結構Fig.1 Steady-state evolution structure

2.2 協同進化策略

在協同進化部分，考慮到CMOP 的Pareto 前沿可能具有各種形狀，例如凸或凹型、連續或不連續等，為了可以更好地維持種群的多樣性，進而獲取完整的Pareto 前沿，本文采用一種基于網格的約束分解方法維持種群的多樣性。相較于當前常用的權值求和、切比雪夫和基于懲罰的邊界交叉（Penaltybased Boundary Intersection，PBI）分解的方法，該方法利用網格系統維持種群的多樣性，在Pareto 前沿為凹型時更具優勢，有助于提升算法的普適性。基于網格的約束分解和加權的方法被分別運用于優化兩個子種群P1和P2，以達到同時兼顧多樣性和收斂性的目的，并結合一定的交互機制實現兩個子種群之間的信息共享，進而實現兩個子種群之間的協同進化。

2.2.1 基于網格的約束分解

基于網格約束分解的方法由文獻［17］針對多目標優化問題（Multi-objective Optimization Problem，MOP）提出，并結合基于分解的排序和字典排序選擇進入下一代的解，該方法能夠較好維持進化過程中種群的多樣性。因此，本文引用文獻［17］的演化方法運用于子種群P1的演化。其中，基于網格的約束分解方法具體介紹如下：

1）網格系統的設置。

首先，各個目標根據理想點和極值點之間區間劃分為K個子區間，則每個子區間的間隔寬度可以定義如式（8）所示：

對于可行解x的第j個目標所在的子區間計算如式（9）所示：

2）約束分解的定義。

約束分解的定義以網格系統為基礎，其中第l個目標上的第k個子問題定義如式（9）所示：

其中：K是一項決定子區間（網格）數量的參數；U表示決策空間中的可行域。

通過將每個目標均勻分成K個區間，把多目標優化問題分解成n×Kn-1個子問題。其中，第l個目標的第k個子問題所包含的解集定義如式（11）所示：

3）基于排序的選擇方法。

基于排序的選擇方法主要由基于分解的排序和字典排序組成，主要用于選擇進入下一代演化的個體。以上部分介紹了約束分解的子問題，每個解集Sl(k)都包含一個解集，基于分解的排序主要對于每個解集Sl(k)按式（11）進行排序，因此每個解都具有n個排序值，然后通過字典排序選擇前N1個解作為下一代的父本種群。如圖2和表1所示，該問題為網格參數K=4 時的雙目標優化問題，經過基于分解的排序后，每個解的排序值如表1 第二列所示（括號前數字為排序值），第三列前7個解為字典排序后選擇的解（標注√）。

圖2 雙目標優化問題在網格系統中所有解的排序Fig.2 Ranking of all solutions of bi-objective optimization problem in grid system

表1 K=4時基于分解的排序和字典排序的過程Tab.1 Procedures of decomposition-based ranking and lexicographic sorting when K=4

2.2.2 加權轉化方法

求解CMOP 最終目的是為了獲取Pareto 前沿，雖然通過加權的方式將CMOP 轉化成約束單目標優化問題僅僅只能獲取該問題Pareto 前沿中的某一個解，但該方式可以顯著地提高算法的收斂性能。設置合適的權值既可以保持算法具有良好的收斂性又能盡可能地搜索到Pareto前沿的中部位置。

在權值的設置上，文獻［4］中提出了一種特殊的加權方式將CMOP 轉化為約束單目標優化問題，該方法顯著地提升了算法的收斂能力。在子種群P2的演化過程中，為提升算法整體收斂能力，同樣也采用類似的加權方法將CMOP 轉化成約束單目標優化問題來處理，并采用式（5）的變異方式和基于可行性準則的約束處理技術對子種群P2進行演化。其中，加權方法如式（12）所示：

2.2.3 交互機制

在協同進化過程中，通過種群間的有效交互方式實現信息共享，可以顯著地改善算法的求解效果。本文基于可行性準則及設定的子種群規模將種群P劃分為兩個子種群P1和P2，并分別采用基于網格的約束分解和加權的方式進行演化。在2.2.1 節中，我們采用文獻［17］的演化方式對子種群P1進行演化，雖然該方法可以較好地維持種群的多樣性，但在約束優化問題中，這種基于網格的演化方法難以跳出不可行域，進而會導致算法無法收斂。為解決該問題，在子種群P2的變異方式中，隨機地選擇子種群P1中構成理想點的個體作為xbest，引導子種群P2向理想點的位置演化，演化過程中子種群P2所獲取的高質量個體通過種群重組的方式進入子種群P1，進而引導子種群P1的進化，并跳出不可行域。

3 實驗與分析

為驗證本文算法的性能，選擇變量維度在6 到16 之間且具有凹和凸型Pareto 前沿的約束多目標優化問題CF［18］和DOC［4］測試問題集進行測試及分析。選擇了基于約束支配準則的非支配排序遺傳算法（Nondominated Sorting Genetic Algorithms Ⅱ based on Constrained Dominance Principle，NSGA-Ⅱ-CDP）［1］和近幾年新提出的約束多目標優化算法：兩階段算法（Two-Phase algorithm，ToP［4］）、推拉搜索算法（Push and Pull Search algorithm，PPS［5］）和約束多目標優化的雙存檔進化算法（Two-Archive Evolutionary Algorithm for Constrained Multiobjective Optimization.C-TAEA）［9］作為對比。

3.1 評價指標

本實驗中選取反向世代距離（Inverted Generational Distance，IGD）和超體積指標（Hypervolume，HV）作為評價指標。IGD 指標衡量的是真實Pareto 前沿中的點到所求得Pareto 前沿近似解集之間最小距離的平均值；HV 指標是指被非支配解集覆蓋的目標空間區域大小。設P*是真實Pareto前沿上均勻采樣的解集，PR是算法求得的Pareto前沿近似解集，其定義分別如式（13）、（14）所示：

其中：dist(x，P)表示個體x∈P*到PR上離其最近個體之間的歐氏距離；|P*|是集合P*中的基數；vol(·)表示勒貝格測度；表示分布在目標空間的參考點，參考點為Pareto 前沿極值點的1.1 倍。IGD 的值越小或HV 值越大，表示該算法具有越好的收斂性和多樣性，也說明PR更加近似Pareto前沿。

3.2 實驗參數設置

設置種群大小N=450，根據文獻［17］中的建議設置子種群N1=300，網格劃分參數K=140，鄰居間隔設置為5；N2=150，穩態演化的子種群劃分數量m=30；所有算法的終止條件為函數評估次數達到300 000；對于所有測試問題集算法獨立運行51次，最后結果取平均值。

3.3 實驗結果及分析

實驗比較了本文算法與NSGA-Ⅱ-CDP、ToP、PPS 和CTAEA 在測試集CF 和DOC 的IGD 和HV 指標的平均值和均方差，結果如表2和表3所示，其中粗體IGD和HV指標結果為五種算法中最優結果，NaN 表示未尋找到可行解，括號內為均方差結果。在測試集中，測試集CF1～CF3 的Pareto 前沿是這些問題在無約束情況下Pareto 前沿的一部分；測試集CF4～CF7的主要難點在于搜索前沿，因為很多Pareto 前沿的點分布在約束邊界位置。相對于前者，測試集CF4～CF7 對算法是否能夠有效兼顧多樣性和收斂性能提出了更高的要求。測試集DOC 同時擁有目標與決策變量之間約束，更符合實際應用需求。

表2 IGD的均值與均方差對比Tab.2 Comparison of mean and mean squared deviation for IGD

表3 HV的均值與均方差對比Tab.3 Comparison of mean and mean squared deviation for HV

與NSGA-Ⅱ-CDP 和C-TAEA 算法相比，對于測試集CF 和DOC，本文算法在IGD和HV指標上均能獲得較好的結果。

與PPS 算法相比，對于CF 測試集中CF3、CF4 和CF7 以及DOC 測試集，本文算法在IGD 指標和HV 指標上獲得較好的結果，而PPS 算法在測試問題CF1、CF2 和CF5 上取得較好結果。

與ToP 算法相比，對于測試集中CF2、CF4 和CF7 以及DOC 測試集，本文算法在IGD 指標和HV 指標上獲得較好結果，對于測試問題CF3，兩種算法在HV 指標上獲得了相似的結果，而ToP算法在測試問題CF1和CF5取得較好結果。

在收斂性和多樣性平衡方面，協同進化過程中，單目標演化起到引導種群進化的作用，多目標演化起到維持種群多樣性的作用，圖3分別描繪了本文算法在DOC1問題上早中晚三個時期的兩個子種群的目標空間中分布情況。從圖中可以看出，在協同進化初期階段，第一階段的穩態演化在搜索到一定的可行解后，種群中的可行解在目標空間分布相對均勻，保持了良好的多樣性；在協同進化中期階段，子種群P2引導子種群P1演化，跳出不可行域，同時子種群P1基于網格約束分解的演化方法主要通過參考點的方式維持種群的多樣性，避免收斂到局部的Pareto 前沿；在協同進化后期階段，子種群P1引導種群演化過程結束，子種群P1中個體逐漸聚集于Pareto 前沿的一個端點，子種群P2采用的多樣性管理措施發揮作用。基于鄰居關系的演化方法和網格多樣性管理方法在維持種群多樣性方面具有良好的優勢，因此，采用單目標和多目標相結合的協同進化方式在兼顧收斂性和多樣性方面具有良好的收斂效果。

圖3 DOC1的協同進化過程Fig.3 Coevolutionary process of DOC1

綜上所述，本文算法在測試集上取得的良好結果，得益于多階段和協同進化兩種優化方式的良好結合，在第一階段的穩態演化以多個子種群分別演化的形式保持種群的多樣性，并搜索高質量的可行解；第二階段的協同進化階段以雙種群協同演化的方式兼顧收斂性和多樣性。其中，兩個子種群分別以基于網格約束分解的方式和加權的方式實現算法的多樣性和收斂性，兩個子種群通過交互機制實現各自所分配任務的協同。因此，本文算法在求解具有低可行域、強約束和不連續Pareto 前沿的測試集DOC 中表現出了良好的優勢，在求解更注重搜索能力的測試集CF時也具有良好的效果。

3.4 參數敏感性分析

3.4.1 子種群數量m

為研究穩態演化中設定的子種群數量對算法性能的影響，分別在測試問題CF1、CF3、DOC1、DOC4 和DOC6 上測試了當m分別為10、15、25、30、45 時的求解效果，以算法獨立運行51 次結果的平均IGD 值作為評價標準，函數評價次數為300 000。測試結果如表4所示，可以看出，本文算法在穩態演化階段中采用具有相對較低敏感性的子種群數量。

表4 m取不同值時的IGD均值對比Tab.4 Comparison of mean values of IGD with different m

3.4.2 子種群規模N2

為研究協同進化中子種群數量對算法性能的影響，本文分別在測試問題CF1、CF3、DOC1、DOC4 和DOC6 上測試了四種子種群規模（N1，N2）組合形式別為（300，50）、（300，100）、（300，150）、（300，200）時求解效果。由于本文采用基于網格約束分解的方法，所以按文獻［17］中的建議設定N1=300。以算法獨立運行51 次結果的平均IGD 值作為評價標準，函數評價次數為300 000。測試結果如表5所示，可以看出，本文算法在穩態演化階段中采用具有相對較低敏感性的子種群數量。

表5 N2取不同值時的IGD均值對比Tab.5 Comparison of mean values of IGD with different N2

4 實例驗證

采用盤式制動設計問題［19］進一步檢驗本文算法的有效性。該問題具有兩個目標，分別是制動器的重量和停止時間；包含四個變量，其中x1和x2分別是制動器內外圈直徑，x3表示嚙合力，x4表示摩擦面的數量；該問題的約束條件分別是半徑之間的最小距離、制動的最大長度、壓力、溫度和扭矩限制，具體優化問題及約束如式（15）所示，其中：x1∈[55，80]，x2∈[75，110]，x3∈[1000，3 000]，x4∈[2，20]。

各算法在該問題上獨立運行51 次，函數評價次數設定為300 000，比較求解結果HV 值的最優值（best）、均值（mean）與標準差（std），參考點按照本文算法獲取的最大極值點的1.1倍設定。

求解結果如表6 所示，可以看出，本文算法較對比算法具有一定的優勢。

表6 五種算法在盤式制動設計問題上的HV指標比較Tab.6 Comparison of five algorithms on disk brake design problem in terms of HV indicator

5 結語

本文提出了一個基于協同進化的約束多目標優化算法，通過網格約束分解和加權的方式實現協同進化，能有效地兼顧進化過程中算法的收斂性和多樣性，并結合穩態演化方法以保證該算法前期具有良好搜索性能，最后通過測試集和實例驗證了算法的有效性。算法的不足之處在于采用基于網格約束分解的方法導致算法種群規模較大，相同評價次數的情況下，本文算法迭代次數偏低，影響求解質量，因此，多樣性管理措施將是未來主要研究方向。