原楊飛，黨乾龍，徐 偉，劉玲玲，羅宇婷

西安電子科技大學 數(shù)學與統(tǒng)計學院，西安710126

約束優(yōu)化問題（constrained optimization problems，COPs）在實際生活中普遍存在，涉及到的領域包括汽車設計[1]、電路設計[2]、生產(chǎn)調(diào)度[3]等。不失一般性，一個COP可以表示為：

其中，f(x)是目標函數(shù)，x是一個D維決策變量，S是決策空間，Li和Ui分別是xi(i=1,2,…,D)的上界和下界，gl(x)和hq(x)分別是第l個不等式約束條件和第q個等式約束條件。在COPs 中，等式約束通常被轉(zhuǎn)化為如下的不等式約束來處理：

其中，δ是一個很小的正數(shù)，決策變量x違反所有約束條件的程度為：

其中G(x)≥0。當G(x)=0 時，稱x為可行解。否則，稱x為不可行解。

近年來，求解COPs 的算法主要分為傳統(tǒng)優(yōu)化算法和進化算法兩類。傳統(tǒng)優(yōu)化算法包括簡約梯度法、投影梯度法、序列二次規(guī)劃法和外點及內(nèi)點罰函數(shù)法等。這些算法在求解時需要利用函數(shù)的梯度信息，只適用于可微函數(shù)，而且容易陷入局部最優(yōu)[4]。進化算法是一種基于種群的搜索方法，具有魯棒性強、搜索效率高、適用范圍廣等特點，對函數(shù)性質(zhì)要求低，只依賴目標函數(shù)值，不需要函數(shù)的梯度信息，不易陷入局部最優(yōu)。因此利用進化算法求解COPs 得到了越來越多研究者的關注[5]，這類算法被稱為約束優(yōu)化進化算法。

約束優(yōu)化進化算法包括進化算法和約束處理技術兩部分。在優(yōu)化過程中，進化算法的本質(zhì)是產(chǎn)生子代，而約束處理技術的本質(zhì)是從候選個體中選擇優(yōu)質(zhì)個體進入下一代，進而使種群收斂到最優(yōu)解。圖1給出了COPs的一個實例。

圖1 COPs的一個實例Fig.1 An example of COPs

根據(jù)約束處理技術的不同，可以將約束優(yōu)化進化算法大致分為以下五類：罰函數(shù)法[6]、可行性準則法[7]、ε約束法[8]、多目標優(yōu)化法[9]和混合法[10]。罰函數(shù)法通過給目標函數(shù)f(x)增加一個懲罰項p(x)，將COPs 轉(zhuǎn)化為無約束優(yōu)化問題進行求解。可行性準則由Deb提出，它基于三條準則比較任意兩個個體：（1）一個可行個體和一個不可行個體，選擇可行個體。（2）兩個都是可行個體，選擇目標函數(shù)值小的個體。（3）兩個都是不可行個體，選擇約束違反程度小的個體。ε約束法通過人為設定ε值，將約束違反程度小于ε的個體視為可行個體進行比較，通過這種方式，部分不可行個體被選擇進入下一代，有利于增加種群的多樣性。多目標優(yōu)化法將COPs轉(zhuǎn)化為多目標優(yōu)化問題，然后利用多目標優(yōu)化技術求解轉(zhuǎn)化后的優(yōu)化問題。混合法將幾種約束處理技術組合起來求解COPs。

約束優(yōu)化進化算法的核心是如何有效平衡種群的目標函數(shù)和約束違反程度，為了實現(xiàn)這個目的，本文提出一種基于動態(tài)罰函數(shù)的差分進化算法求解COPs（differential evolution algorithm based on dynamic penalty function to solve COPs，PECO）。對IEEE CEC 2010 和IEEE CEC 2017 兩組基準測試集進行數(shù)值實驗，結(jié)果表明PECO在大多數(shù)測試函數(shù)上性能優(yōu)于其他比較算法。

1 ε 約束法

ε約束法是Takahama和Sakai提出的一種具有代表性的約束處理技術，對于任意兩個個體xi和xj，滿足以下任一條件，xi優(yōu)于xj：

其中，

這里，ε0是初始閾值，t和T分別是種群的當前迭代次數(shù)和最大迭代次數(shù)，λ和p是兩個參數(shù)，ε隨迭代次數(shù)的增加而減小。

2 差分進化算法

1997年Storn和Price提出差分進化算法（differential evolution，DE）[11]，其具有結(jié)構(gòu)簡單、易于實施、魯棒性好、收斂速度快等優(yōu)點。該算法包含初始化、變異、交叉、選擇四個步驟。

初始化：在決策空間S中隨機產(chǎn)生一個初始種群，其中m表示種群大小。

變異：對每個目標向量，利用變異算子產(chǎn)生一個變異向量。常用的變異算子如下：

其中，F(xiàn)是縮放因子。是種群中隨機選擇的三個不同的個體。是種群中最好（罰適應度值最?。┑膫€體。

交叉：目標向量和變異向量采用二項式[12]交叉產(chǎn)生試驗向量。

選擇：根據(jù)個體的目標向量和試驗向量的適應度值挑選好的個體進入下一代。

3 動態(tài)罰函數(shù)法求解約束優(yōu)化問題

3.1 研究動機

罰函數(shù)法是處理約束的一種簡單有效的方法，但罰系數(shù)值在很大程度上依賴于所優(yōu)化的問題，難以選取。為了解決這個問題，提出動態(tài)罰系數(shù)策略，其中罰系數(shù)根據(jù)種群的可行解比例和進化代數(shù)動態(tài)變化。在進化初期采用較小的懲罰系數(shù)，有利于種群的勘探。在進化后期或當種群的可行解比例大于設定的閾值時采用較大的懲罰系數(shù)，有利于種群的開采和收斂。通過這種方式，可以平衡種群的勘探能力和開采能力。DE 在求解COPs時具有優(yōu)化效率高、魯棒性強、收斂速度快等優(yōu)點，因此使用DE作為搜索算法。為了平衡種群的收斂性與多樣性，本文在經(jīng)典DE算法的基礎上，結(jié)合兩種DE變異策略更新種群。

3.2 搜索算法

本文采用兩種DE 變異策略產(chǎn)生試驗向量，第一種是DE/current-to-rand/1 變異策略，第二種是DE/rand-tobest/1/bin變異策略，其方程分別為：

其中，Cr表示交叉概率。randj是(0,1)中隨機產(chǎn)生的一個實數(shù)。jrand是集合{1,2,…,D}中隨機選擇的一個整數(shù)。

式（7）中，當前個體使用種群中隨機選擇的個體的信息指導搜索，有利于增加種群的多樣性，防止種群陷入局部最優(yōu)。式（8）中，使用種群中最好的個體的信息指導搜索，有利于引導種群向精英解靠近，進而加快種群的收斂速度。在本文中，以相同的概率使用這兩個變異策略，通過這種方式，有效平衡了種群在搜索過程中的多樣性和收斂性。

3.3 罰系數(shù)調(diào)整策略

罰函數(shù)法在求解COPs 時，首先COPs 被轉(zhuǎn)化為如下的無約束優(yōu)化問題：

其中ξ是罰系數(shù)。在COPs 中，罰系數(shù)的設置對于平衡種群的目標函數(shù)和約束違反程度是至關重要的。罰系數(shù)過大，種群將以較快的速度進入可行域，忽略了對不可行域的勘探，可能會使種群陷入局部最優(yōu)。罰系數(shù)過小，算法對不可行個體的懲罰力度不足，可能會阻礙種群進入可行域。因此，選取一個恰當?shù)牧P系數(shù)對于求解COPs是非常關鍵的。本文結(jié)合ε約束法提出一種簡單有效的罰系數(shù)調(diào)整策略，其偽代碼如算法1所示。其中Pf是種群中可行個體所占的比例。

算法1罰系數(shù)調(diào)整策略

由算法1 可知，進化初期，種群中的個體大多數(shù)為不可行個體，此時罰系數(shù)ξ被設置為一個較小的值，例如ξ=1。在這種情況下，個體的目標函數(shù)和約束違反程度發(fā)揮著同等重要的作用，一些有著較好目標函數(shù)值或較小約束違反度的不可行個體有機會被選擇進入下一代。這種方式有利于增加種群的多樣性和促進種群對不可行域的勘探。隨著進化的進行，種群中的部分不可行個體變?yōu)榭尚袀€體，當種群的可解比例Pf大于設定的閾值時，罰系數(shù)被設置為一個較大的值。此時，種群中的不可行個體被給予充足的懲罰，有利于種群快速地收斂到可行域。當Pf接近于1時，適當減小罰系數(shù)，有利于種群對可行域邊界的勘探。如圖2所示，此時種群可以從可行域和不可行域兩個方向收斂到最優(yōu)解。此外，對于具有較小可行域或者約束條件比較復雜的優(yōu)化問題，種群可能總是處于不可行域中，為了避免種群滯留在不可行域中，ε約束法被采用。當種群中個體約束違反程度的最小值大于所設的ε值時，罰系數(shù)被設置為一個較大的值，有利于種群快速地進入可行域。

圖2 種群搜索最優(yōu)解的運動軌跡Fig.2 Illustration of population search for optimal solution

3.4 PECO

在求解COPs 時，PECO 首先根據(jù)式（9）將COPs 轉(zhuǎn)化為無約束優(yōu)化問題。接下來，為了平衡種群的目標函數(shù)和約束違反程度，根據(jù)種群的質(zhì)量和進化的代數(shù)動態(tài)地調(diào)整罰系數(shù)。在優(yōu)化過程中，結(jié)合兩個DE 變異策略產(chǎn)生子代。PECO的偽代碼如算法2所示。

算法2PECO

4 仿真實驗

4.1 演示搜索行為

在本節(jié)中，選取如下的三個二維人工測試問題[13]演示PECO的收斂過程：

圖3 給出了ATF1、ATF2 和ATF3 的搜索空間、目標函數(shù)的等高線圖、可行域和最優(yōu)解。其中ATF1 的最優(yōu)解位于可行域的內(nèi)部，ATF2和ATF3的最優(yōu)解位于可行域的邊界上，這里ATF3包含一個等式約束條件。

圖3 ATF1、ATF2和ATF3的搜索空間、目標函數(shù)的等高線圖、可行域和最優(yōu)解Fig.3 Feasible region，search space，contours of objective function，and optimal solution of ATF1，ATF2 and ATF3

從圖4 中可以得到，當最優(yōu)解在可行域內(nèi)時（比如ATF1），PECO 可以從不同的方向進入可行域。當最優(yōu)解在可行域的邊界上時（比如ATF2），PECO可以從可行域和不可行域兩個方向收斂到最優(yōu)解。對于ATF3（包含一個等式約束條件），PECO 可以從可行域的兩端搜索到最優(yōu)解。綜上所述，PECO有能力求解以上三種不同類型的COPs。

圖4 PECO在ATF1、ATF2和ATF3上的收斂過程Fig.4 Evolution process of PECO on ATF1，ATF2 and ATF3

4.2 標準測試函數(shù)和參數(shù)設置

采用IEEE CEC 2010[14]和IEEE CEC 2017[15]兩組基準測試集驗證PECO 的尋優(yōu)性能。IEEE CEC 2010測試集包含18 個測試函數(shù)，IEEE CEC 2017 測試集包含28 個測試函數(shù)，這兩組測試集包含多種不同類型的約束優(yōu)化問題，例如具有較強的非線性、較小的可行域和旋轉(zhuǎn)不變性等特點。表1給出了測試函數(shù)的種群規(guī)模(m)、決策變量的維度(D)和最大函數(shù)評價次數(shù)(maxFES)。在PECO 中，每個測試函數(shù)獨立運行25 次，涉及到的參數(shù)設置如下：p=0.85,λ=10,Gmin=minG(xi),i=1,2,…,m,ε0為初始種群中最大的約束違反值。

表1 測試函數(shù)的參數(shù)設置Table 1 Parameter settings of test functions

4.3 參數(shù)敏感度分析

算法1中，在進化初期，t/T>α時，設置罰系數(shù)為一個較小的值。本節(jié)針對α的5 種不同取值0.30，0.35，0.40，0.42和0.45，分別進行25次獨立實驗，討論α的參數(shù)效應。圖5 展示了IEEE CEC 2010 基準測試函數(shù)C10、C14 和C15，在D=30 時的函數(shù)收斂曲線。從圖5中可知，C10 在α=0.42 時結(jié)果最優(yōu)，C14 在α=0.42 和0.45 時結(jié)果最優(yōu)，C15 在α=0.40 和0.45 時結(jié)果差別不大，找到的解最優(yōu)。

圖5 不同α 值的函數(shù)收斂性能比較Fig.5 Convergence performance comparison of functions with different α values

在進化后期，當種群的可行解比例Pf >β時，設置罰系數(shù)為一個較大的值。這里針對β的5 種不同取值0.5，0.6，0.7，0.8 和0.9，討論β的參數(shù)效應，實驗結(jié)果在圖6 中給出。從圖6 中可以得出，C10 在β=0.8 時結(jié)果最優(yōu)，C14在β=0.8 和0.9時結(jié)果差別不大，找到的解最優(yōu)，C15 在β=0.8 和0.9 時結(jié)果最優(yōu)。綜上所述，在PECO中，α=0.42,β=0.8。

圖6 不同β 值的函數(shù)收斂性能比較Fig.6 Convergence performance comparison of functions with different β values

4.4 結(jié)果對比與分析

為了驗證PECO的尋優(yōu)性能，使用實驗中獲得的最小可行目標函數(shù)值的平均值（Mean）和標準偏差（std）作為評價指標。在IEEE CEC 2010這組測試集中，將PECO與Co-CLPSO[16]、ITLBO[17]、DeCODE[18]、AIS-IRP[19]這4個算法進行性能比較，實驗結(jié)果在表2中給出。所有對比算法的實驗結(jié)果均來源于原論文。“?”表示算法在25次運行中不能找到任何可行解?！?”“-”和“≈”分別表示PECO 在統(tǒng)計性能上優(yōu)于、劣于和相似于對比算法。從表2中可以得出，D=10 時，PECO分別在12個、6個、6個和11個測試函數(shù)上優(yōu)于Co-CLPSO、ITLBO、DeCODE和AIS-IRP。與PECO相比，Co-CLPSO、ITLBO、DeCODE和AISIRP分別在3個、3個、3個和4個測試函數(shù)上占優(yōu)。D=30 時，PECO分別在17個、11個、6個和15個測試函數(shù)上優(yōu)于Co-CLPSO、ITLBO、DeCODE 和AISIRP。而Co-CLPSO、ITLBO、DeCODE和AIS-IRP分別在1個、4個、4個和2個測試函數(shù)上優(yōu)于PECO。此外，與Co-CLPSO、ITLBO 和AIS-IRP 這3 個算法相比，PECO 在高維測試函數(shù)上可以獲得更好的性能。

表2 IEEE CEC 2010中18個基準測試函數(shù)的實驗結(jié)果Table 2 Experimental results of 18 benchmark functions in IEEE CEC 2010

在IEEE CEC 2017 這組測試集中，將PECO 算法與MA_ES[20]、IUDE[21]、LSHADE44[22]、UDE[23]這4 個算法進行性能比較，實驗結(jié)果在表3中給出，其中LSHADE44是IEEE CEC 2017 競賽中性能最好的算法。在C17、C19、C26、C28 這4 個測試函數(shù)上，PECO 與對比算法均不能找到任何可行解，因此不提供它們的實驗結(jié)果。從表3中可以得出，D=10 時，PECO分別在12個、6個、10個和15個測試函數(shù)上優(yōu)于MA_ES、IUDE、LSHADE44和UDE。與PECO相比，MA_ES、IUDE和LSHADE44分別在3個、2個和3個測試函數(shù)上占優(yōu)，同時，UDE不能在任何測試函數(shù)上優(yōu)于PECO。D=30 時，PECO 分別在10個、13 個、14 個和17 個測試函數(shù)上優(yōu)于MA_ES、IUDE、LSHADE44 和UDE。而MA_ES、IUDE、LSHADE44 和UDE分別在4個、4個、3個和1個測試函數(shù)上優(yōu)于PECO。通過上述分析，PECO在整體性能上優(yōu)于其他對比算法。

表3 IEEE CEC 2017中28個基準測試函數(shù)的實驗結(jié)果Table 3 Experimental results of 18 benchmark functions in IEEE CEC 2017

5 結(jié)束語

本文提出了一種基于動態(tài)罰函數(shù)的差分進化算法求解約束優(yōu)化問題。在所提出的算法中，設計了一種與ε約束法相結(jié)合的罰系數(shù)調(diào)整策略，通過這種方式，可以有效平衡種群的目標函數(shù)和約束違反程度。此外，為了平衡種群的多樣性與收斂性，結(jié)合兩種DE 變異策略產(chǎn)生子代。實驗結(jié)果表明，PECO與對比算法相比具有更好的優(yōu)化性能。下一步將設計一個自適應的罰系數(shù)調(diào)整策略提高PECO的尋優(yōu)性能。