動態罰函數法求解約束優化問題

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

西安電子科技大學 數學與統計學院，西安710126

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

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

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

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

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

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

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

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

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

1 ε 約束法

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

其中，

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

2 差分進化算法

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

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

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

其中，F是縮放因子。是種群中隨機選擇的三個不同的個體。是種群中最好（罰適應度值最小）的個體。

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

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

3 動態罰函數法求解約束優化問題

3.1 研究動機

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

3.2 搜索算法

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

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

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

3.3 罰系數調整策略

罰函數法在求解COPs 時，首先COPs 被轉化為如下的無約束優化問題：

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

算法1罰系數調整策略

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

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

3.4 PECO

在求解COPs 時，PECO 首先根據式（9）將COPs 轉化為無約束優化問題。接下來，為了平衡種群的目標函數和約束違反程度，根據種群的質量和進化的代數動態地調整罰系數。在優化過程中，結合兩個DE 變異策略產生子代。PECO的偽代碼如算法2所示。

算法2PECO

4 仿真實驗

4.1 演示搜索行為

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

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

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

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

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

4.2 標準測試函數和參數設置

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

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

4.3 參數敏感度分析

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

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

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

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

4.4 結果對比與分析

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

表2 IEEE CEC 2010中18個基準測試函數的實驗結果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 個算法進行性能比較，實驗結果在表3中給出，其中LSHADE44是IEEE CEC 2017 競賽中性能最好的算法。在C17、C19、C26、C28 這4 個測試函數上，PECO 與對比算法均不能找到任何可行解，因此不提供它們的實驗結果。從表3中可以得出，D=10 時，PECO分別在12個、6個、10個和15個測試函數上優于MA_ES、IUDE、LSHADE44和UDE。與PECO相比，MA_ES、IUDE和LSHADE44分別在3個、2個和3個測試函數上占優，同時，UDE不能在任何測試函數上優于PECO。D=30 時，PECO 分別在10個、13 個、14 個和17 個測試函數上優于MA_ES、IUDE、LSHADE44 和UDE。而MA_ES、IUDE、LSHADE44 和UDE分別在4個、4個、3個和1個測試函數上優于PECO。通過上述分析，PECO在整體性能上優于其他對比算法。

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

5 結束語

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