基于空間收縮技術的約束多目標進化算法

李二超，毛玉燕

（蘭州理工大學電氣工程與信息工程學院，蘭州 730050）

（?通信作者電子郵箱lecstarr@163.com）

0 引言

多目標優化問題（Multi-objective Optimization Problem，MOP）在實際科研和工程實踐中應用非常廣泛，然而許多實際問題往往伴隨各種各樣約束條件的限制［1］，這些約束條件導致搜索空間的拓撲結構變得十分復雜，如可行域狹小、存在多個不連通可行域等。例如，環境經濟電力調度［2］、機器人抓手優化［3］等。這類帶約束條件的多目標優化問題統稱為約束多目標優化問題（Constrained Multi-objective Optimization Problem，CMOP）。不同于MOP，求解CMOP 對目標函數優化的同時還需要滿足約束條件，而優越的無約束進化算法在求解約束優化問題時一籌莫展，因此，對約束多目標進化算法（Constrained Multi-objective Evolutionary Algorithm，CMOEA）的研究具有非常重要的理論價值和實際意義

約束優化進化算法中，根據處理約束方法的不同可以將約束處理機制大致分為六類：罰函數法、可行性準則、隨機排序法、ε約束處理法［4］、多目標優化法和混合法［1］。CMOEA 根據進化算法中保留解的方式可以分為基于支配和基于分解兩類。基于支配的算法如C-NSGA-Ⅲ［5］、NSGA-Ⅱ-CDP［6］等。基于分解的算法如C-MOEA/D［7］、MOEA/D-Epsilon［8］、MOEA/DCDP［9］等。上述算法均過分強調可行解，忽略了不可行解攜帶的信息。為克服此缺點，平衡CMOEA 收斂性、多樣性和可行性，兩階段、多存檔集的進化算法開始用于求解CMOP。Liu等［10］提出了針對目標函數和決策空間約束的兩階段搜索算法ToP；Li 等［11］提出了雙歸檔集進化算法C-TAEA（Two-Archive Evolutionary Algorithm for Constrained multi-objective optimization）；Cai 等［12］提出兩 階段算法PPS（Push and Pull Search）用于求解不可行域較大問題，第一階段不考慮約束條件得到無約束Pareto 前沿，第二階段考慮約束條件和目標函數將無約束Pareto 前沿拉至約束Pareto 前沿。上述算法在處理約束優化問題中均取得了顯著的成果，但在不可行域較大時，對不可行域的搜索過多或過少都會引起算法性能下降。上述算法在追求對不可行域充分探索的同時，增加了對無潛力不可行域的搜索，使算法效率降低且收斂精度不高。

對于不可行域較大的約束優化問題，為減少對無潛力不可行域的搜索，提高算法收斂性、多樣性和可行性的平衡能力，本文在PPS 算法基礎上提出一種混合約束處理技術，將ε約束處理法與空間收縮技術相結合，在進化過程中調整決策變量上下限，減少無潛力不可行域的影響。

1 相關概念

1.1 約束優化問題定義

以最小化問題為例，約束多目標優化問題可定義為如下形式：

其中：x=(x1，x2，…，xD)∈Ω是包含D個決策變量的解，Ω∈RD是決策空間；F：Ω→RM由M個目標函數組成；gj(x)為q個不等式約束，hj(x)為m-q個等式約束。

在約束優化問題中，通常將等式約束轉化為不等式約束，因此，個體x在每個約束條件上的約束違反程度為：

其中δ為等式約束的容忍參數，個體x總約束違反度為：

1.2 ε約束處理法

ε約束處理法通過設定ε值，根據個體總約束違反度將個體劃分到不同的區域，不同區域內的個體采用不同的評價標準。該方法使用分段函數來控制ε，根據式（6）評價個體的優劣：

其中：k為當前代數，Tc為控制代數，cp控制ε減小速率，ε(0)的定義如式（5）。

其中：xθ為種群中個體按約束違反度升序排序后第0.05N個個體。

其中：v1、v2表示兩個解的約束違反度，f1、f2表示兩個解的目標函數值，公式的前兩行表示當兩個解的約束違反度都小于ε或者兩個解約束違反度值大于ε但相等時，根據目標函數值選擇目標函數值更小的解；其他情況，即兩個解約束違反度值有一個或者兩個都大于等于ε 且不相等時，根據約束違反度值選擇約束違反度更小的解。

2 本文算法

本文提出的基于空間收縮技術的約束多目標優化算法（Constrained Multi-Objective Evolutionary Algorithm based on Space Shrinking Technique，CMOEA-SST）首先對PPS 中兩階段的過渡種群進行改進，提出自適應精英保留策略；然后在PPS 算法第二階段加入空間收縮技術，對決策變量的上下限進行調整，縮小搜索空間，減少對無潛力不可行的搜索。

PPS算法在第一階段得到無約束Pareto前沿，在第二階段則將無約束Pareto 前沿進一步進化到有約束Pareto 前沿。這種搜索機制雖然能夠快速跨越不可行域，但是對于無約束Pareto 前沿和有約束Pareto 前沿分離的優化問題（如圖1 所示），Push 階段結束時種群為無約束Pareto 前沿，由圖1 可知，此時種群中并不含有約束Pareto前沿上的任何解，種群的收斂性和可行性較差。因此，本文提出精英保留策略，保留Push階段進化過程中的高質量解，并在Push階段完成時，自適應替換種群中部分解。自適應精英保留策略能夠增加求解有無約束Pareto 前沿分離問題時Pull 階段初始種群的多樣性和可行性。

圖1 有無約束的Pareto前沿分離示意圖Fig.1 Schematic diagram of unconstrained and constrained Pareto front separation

對于不可行域較大的問題，很難得到可行解，需要充分利用不可行解的信息。而對于眾多不可行解，部分解對求解Pareto 最優解集有利，部分解對尋找Pareto 最優解并無任何幫助，此部分解所在區域成為無潛力不可行域。而過度增加對無潛力不可行域的探索會降低算法性能，因此需要合理對不可行域進行搜索。為此，本文在PPS 算法第二階段提出混合約束處理技術，在改進ε約束處理技術基礎上增加空間收縮技術。改進ε約束處理技術能夠利用不可行解的信息，空間收縮技術則對決策變量上下限進行調整，隨著時間的推移，搜索空間逐漸減小。所提混合約束處理技術能使算法在對不可行域充分探索的同時減少無潛力不可行域對算法性能的影響，能夠有效提升算法的收斂性能。

2.1 MOEA-SST

算法1 描述了本文算法CMOEA-SST 的主要框架，其中第3）～6）行為初始化參數，包括初始種群、參考點、搜索狀態及其他參數；第8）行執行Push 階段精英保留策略，將精英個體保存在Xsst中；第9）行計算l代進化以來理想點和最差點的最大變化率，其中理想點和最差點的變化率根據式（7）、（8）求取；第11）～19）行判斷搜索過程是否切換，當最大變化率小于φ(φ取0.001)且搜索過程為Push 階段時，搜索過程進行切換，并判斷是否應該啟動精英保留策略，其中第14）～17）行執行精英保留策略；第21）行更新ε值，采用改進的ε約束處理法，更新方法如式（9）所示，滿足前期搜索過程中ε迅速減小，使得種群快速穿越不可行域，后期ε減小率降低，可以更徹底地搜索可行解；第28）～30）行采用差分進化操作［13］生成一個新解，并對該解進行修復改進；第34）～41）行更新鄰域，根據兩階段搜索過程不同，Push階段以聚合函數值gte(x|λ，z*)=為判斷依據，選擇gte小的解，Pull 階段則根據gte、v（x）、ε(k)（ε約束處理法）選擇個體；第42）～44）行為空間收縮技術，具體流程如算法3 所示；第45）行更新迭代次數；第46）行根據個體的非支配等級和擁擠度距離更新可行的非支配解集合NS。

其中rfk為第k代種群中可行解的比例。

算法1 CMOEA-SST的一般框架。

2.2 自適應精英保留策略

PPS 算法兩階段搜索過程雖然能夠充分探索不可行域，但當優化問題的無約束Pareto和約束Pareto前沿分離時，第二階段初始種群中不包含可行解，并且隨著有無約束Pareto 前沿的距離越大，第二階段初始種群表現出的可行性越差。因此，本文采用自適應精英保留策略對PPS 兩階段的過渡種群進行改進，以提升算法Pull階段初始種群的多樣性和可行性。

自適應精英保留策略主要思想：在Push 階段保留約束違反度小于ε(0)的非支配保存，當Push階段完成時，以當前種群中可行解比例作為啟動精英保留策略的依據，當可行解比例小于0.5時，隨機剔除種群中N/6個體，并按約束違反度從小到大的原則選擇N/6個精英解進行補充。具體過程如算法2所示。

算法2 保留Push階段精英個體。

2.3 空間收縮技術

空間搜索技術是反向收縮帕累托存檔進化策略（Inverted-Shrinkable Pareto Archived Evolution Strategy，ISPAES）［14］的重要組成部分，在進化過程中，利用可行域周圍個體所攜帶的全局信息將搜索精力集中在更小的搜索空間上。

空間收縮技術每隔Ts代執行一次，具體過程實現如下：

1）選擇0.15N個最佳個體。針對每一個約束條件，從種群中刪除該約束條件最差的個體，直至所剩個體數量為0.15N。

2）求取決策變量最值。從所選的最佳個體集合中求取每一個決策變量的最大最小值。

3）根據當前種群中最佳個體決策變量的最值對搜索空間進行縮小，決定新的決策變量上下限。每一個決策變量的搜索區間必須比之前決策變量的搜索區間減小(1-0.9(1/n))%。更多關于空間收縮技術的細節參考文獻［14］。

本文將空間收縮技術嵌入Pull 階段，用于平衡搜索過程中對可行域和不可行域的探索，減少對無潛力不可行域的搜索，能在平衡算法收斂性和多樣性的同時有效提升算法的收斂性能。具體過程如算法3所示。

算法3 搜索空間收縮。

3 實驗仿真與分析

3.1 測試函數與評價指標

為測試CMOEA-SST 的性能，選擇LIRCMOP 系列測試問題，根據文獻［4］將LIRCMOP 系列測試函數的信息總結為表1。為了測試不同算法性能，選擇世代距離（Generational Distance，GD）和超體積（Hypervolume，HV）作為評價指標。其中：GD為收斂性評價指標，GD值越小表示所求解集與真實前沿越接近，算法的收斂性越好；HV 為綜合性評價指標，HV值越大，算法的綜合性能越好。

表1 LIRCMOP系列測試函數信息Tab.1 Information of LIRCMOP series test functions

3.2 實驗配置與參數設置

實驗環境為Matlab2014b版本，實驗操作平臺為開源平臺PlatEMO［15］。實驗參數設置如下：

1）變異概率Pm=1/n（n為決策變量的維數）；多項式變異分布指標為20。

2）差分進化參數：CR=1，f=0.5。

3）種群大小：N=300，T=30。

4）終止條件：每個算法獨立運行20 次，評價次數為300 000。

5）子代最大更新數目：nr=2。

6）PPS 參數設置與原論文保持一致：Tc=800，α=0.95，τ=0.1，cp=2，l=20。

7）為保證比較的公平性，C-MOEA/D、C-TAEA、ToP 算法參數均與原論文一致。

8）空間收縮技術參數：為合理設置收縮間隔Ts，將Ts分別設為30、40、50，并將獨立運行20次的平均結果進行對比。設置不同Ts的算法在LIRCMOP2、LIRCMOP6、LIRCMOP8、LIRCMOP10、LIRCMOP12、LIRCMOP14 上的HV 值如表2 所示。從表2 可以看出，當Ts為40 時，所得Pareto 解集在LIRCMOP2、LIRCMOP5、LIRCMOP8、LIRCMOP12、LIRCMOP14 上的HV 值均最好。因此，為了保持種群良好的性能，Ts設置為40。

表2 不同Ts的對比測試結果Tab.2 Comparison test results with different Ts

3.3 實驗結果與分析

3.3.1 算法有效性驗證

為驗證本文中混合約束處理技術的有效性，將PPS 算法與采用混合約束處理技術的PPS 算法（記為PPS-s）進行比較。表3 展示了PPS 與PPS-s 在LIRCMOP 測試問題上的GD 值，結果顯示混合約束處理技術使得原始算法收斂性顯著提升。

表3 兩個算法在LIRCMOP系列測試函數上GD的平均值和標準差Tab.3 Average value and standard deviation of GD for two algorithms on LIRCMOP series test functions

3.3.2 算法性能驗證

為驗證所提算法的性能，選擇C-MOEA/D［7］、ToP［10］、CTAEA［11］、PPS［12］四個流行的約束多目標優化算法進行對比研究。C-MOEA/D、ToP、C-TAEA、PPS 和CMOEA-SST 在14 個LIRCMOP 測試函數上獨立運行20 次的GD 和HV 指標平均值和標準差如表4、5所示。

對表4分析可得，CMOEA-SST 在LIRCMOP1～LIRCMOP 5、LIRCMOP7、LIRCMOP8、LIRCMOP11、LIRCMOP12共9個測試函數上所得結果明顯優于對比算法，說明CMOEA-SST表現出較好的收斂性。對表5 分析可得，CMOEA-SST 在LIRCMOP2、LIRCMOP5～LIRCMOP12 共9 個測試問題上表現良好。綜合而言，CMOEA-SST 在求解不可行域較大問題上具有顯著的優越性。

具體分析如下：

LIRCMOP1～LIRCMOP4測試問題在整個搜索空間中可行域極小并且有約束Pareto 前沿和無約束Pareto 前沿分離，由GD 指標可得，CMOEA-SST 在求解此類問題時表現出較好的收斂性，主要原因是空間收縮技術能夠不斷縮小搜索空間，繼而增加Pareto前沿附近區域的搜索，使得所有Pareto最優解更接近于真實前沿。但是對于離散的LIRCMOP 問題而言，CMOEA-SST 的綜合指標比PPS 差。圖2、3 顯示了在LIRCMOP1 和LIRCMOP3 上運行20 次后的平均結果：LIRCMOP1 問題上，C-MOEA/D、ToP、C-TAEA 沒有得到Pareto前沿，CMOEA-SST 所得解集分布情況比PPS 要好；LIRCMOP3問題上，C-TAEA 完全沒有接近真實Pareto 前沿，ToP 和CMOEA/D 只求得Pareto 前沿的一部分，CMOEA-SST 和PPS 所得解集的分布不均勻，還需進一步研究。

圖2 各算法在LIRCMOP1測試函數上的仿真結果Fig.2 Simulation results of each algorithm on LIRCMOP1 test function

LIRCMOP5～LIRCMOP12測試問題具有較大不可行域，由表5 可知，所提算法在這8 個測試問題上綜合指標優于其余4個算法，由表4 可得CMOEA-SST 在LIRCMOP5、LIRCMOP7、LIRCMOP8、LIRCMOP11、LIRCMOP12 共5 個測試問題上取得了較好的收斂性。LIRCMOP6 有無約束的前沿相同、LIRCMOP9、LIRCMOP10 約束Pareto 前沿為無約束前沿的一部分，本文采用的精英保留策略在求解此類問題時，能夠增加Pull階段初始種群的多樣性，因此表現出優越的綜合性能，同時作為代價Pull階段原初始種群中部分收斂性能優良解被替換，會相應降低算法的收斂性。從表4 可得，CMOEA-SST 在LIRCMOP6 和LIRCMOP9、LIRCMOP10 問題上收斂性雖然優于前三個對比算法，卻略差于原PPS算法，仿真結果與理論分析一致。對于三目標的問題LIRCMOP13、LIRCMOP14，本文算法表現較差。圖4、5 展示了LIRCMOP9 和LIRCMOP12 的運行結果，由圖可知，僅有CMOEA-SST 能夠在兩個問題上求得Pareto前沿，其余算法只能獲得Pareto前沿的一部分或者完全沒有接近真實前沿。

圖3 各算法在LIRCMOP3測試函數上的仿真結果Fig.3 Simulation results of each algorithm on LIRCMOP3 test function

圖4 各算法在LIRCMOP9測試函數上的仿真結果Fig.4 Simulation results of each algorithm on LIRCMOP9 test function

表4 五個算法在LIRCMOP系列測試函數上GD的平均值和標準差Tab.4 Average value and standard deviation of GD for five algorithms on LIRCMOP series test functions

表5 五個算法在LIRCMOP系列測試函數上HV的平均值和標準差Tab.5 Average value and standard deviation of HV for five algorithms on LIRCMOP series test functions

續表

圖5 各算法在LIRCMOP12測試函數上的仿真結果Fig.5 Simulation results of each algorithm on LIRCMOP12 test function

4 結語

本文針對不可行域較大約束優化問題的求解，為平衡算法的收斂性、分布性和可行性，合理探索不可行域，考慮PPS算法求解此類問題時對不可行域充分探索的優勢，結合自適應精英保留策略和空間收縮技術提出一種基于空間收縮技術的約束多目標進化算法。該算法將進化算法分為兩階段，在Push 階段不考慮約束條件得到無約束Pareto 前沿，Push 階段完成時自適應啟動精英保留策略，提高Pull 階段初始種群的多樣性和可行性。Pull 搜索階段增加空間收縮技術，每隔40代對決策變量上下限進行調整，縮小搜索空間，減少無潛力不可行域對算法性能的影響。綜合分析本文算法與其他4 個約束多目標算法在LIRCMOP 系列測試函數上的仿真結果可知，本文算法在不可行域較大問題上表現良好；但該算法在求解三目標問題時出現了性能退化問題，如何提高算法在三目標及高維多目標問題上的性能是我們接下來的工作。