基于空間收縮技術(shù)的約束多目標(biāo)進(jìn)化算法

李二超，毛玉燕

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

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

0 引言

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

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

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

1 相關(guān)概念

1.1 約束優(yōu)化問題定義

以最小化問題為例，約束多目標(biāo)優(yōu)化問題可定義為如下形式：

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

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

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

1.2 ε約束處理法

ε約束處理法通過設(shè)定ε值，根據(jù)個體總約束違反度將個體劃分到不同的區(qū)域，不同區(qū)域內(nèi)的個體采用不同的評價標(biāo)準(zhǔn)。該方法使用分段函數(shù)來控制ε，根據(jù)式（6）評價個體的優(yōu)劣：

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

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

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

2 本文算法

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

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

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

對于不可行域較大的問題，很難得到可行解，需要充分利用不可行解的信息。而對于眾多不可行解，部分解對求解Pareto 最優(yōu)解集有利，部分解對尋找Pareto 最優(yōu)解并無任何幫助，此部分解所在區(qū)域成為無潛力不可行域。而過度增加對無潛力不可行域的探索會降低算法性能，因此需要合理對不可行域進(jìn)行搜索。為此，本文在PPS 算法第二階段提出混合約束處理技術(shù)，在改進(jìn)ε約束處理技術(shù)基礎(chǔ)上增加空間收縮技術(shù)。改進(jìn)ε約束處理技術(shù)能夠利用不可行解的信息，空間收縮技術(shù)則對決策變量上下限進(jìn)行調(diào)整，隨著時間的推移，搜索空間逐漸減小。所提混合約束處理技術(shù)能使算法在對不可行域充分探索的同時減少無潛力不可行域?qū)λ惴ㄐ阅艿挠绊懀軌蛴行嵘惴ǖ氖諗啃阅堋?/p>

2.1 MOEA-SST

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

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

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

2.2 自適應(yīng)精英保留策略

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

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

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

2.3 空間收縮技術(shù)

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

空間收縮技術(shù)每隔Ts代執(zhí)行一次，具體過程實現(xiàn)如下：

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

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

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

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

算法3 搜索空間收縮。

3 實驗仿真與分析

3.1 測試函數(shù)與評價指標(biāo)

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

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

3.2 實驗配置與參數(shù)設(shè)置

實驗環(huán)境為Matlab2014b版本，實驗操作平臺為開源平臺PlatEMO［15］。實驗參數(shù)設(shè)置如下：

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

2）差分進(jìn)化參數(shù)：CR=1，f=0.5。

3）種群大?。篘=300，T=30。

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

5）子代最大更新數(shù)目：nr=2。

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

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

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

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

3.3 實驗結(jié)果與分析

3.3.1 算法有效性驗證

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

表3 兩個算法在LIRCMOP系列測試函數(shù)上GD的平均值和標(biāo)準(zhǔn)差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］四個流行的約束多目標(biāo)優(yōu)化算法進(jìn)行對比研究。C-MOEA/D、ToP、C-TAEA、PPS 和CMOEA-SST 在14 個LIRCMOP 測試函數(shù)上獨立運行20 次的GD 和HV 指標(biāo)平均值和標(biāo)準(zhǔn)差如表4、5所示。

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

具體分析如下：

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

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

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

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

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

表4 五個算法在LIRCMOP系列測試函數(shù)上GD的平均值和標(biāo)準(zhǔn)差Tab.4 Average value and standard deviation of GD for five algorithms on LIRCMOP series test functions

表5 五個算法在LIRCMOP系列測試函數(shù)上HV的平均值和標(biāo)準(zhǔn)差Tab.5 Average value and standard deviation of HV for five algorithms on LIRCMOP series test functions

續(xù)表

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

4 結(jié)語

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