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

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

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

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

其中，f(x)是目標(biāo)函數(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。當(dāng)G(x)=0 時，稱x為可行解。否則，稱x為不可行解。

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

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

圖1 COPs的一個實(shí)例Fig.1 An example of COPs

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

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

1 ε 約束法

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

其中，

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

2 差分進(jìn)化算法

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

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

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

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

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

選擇：根據(jù)個體的目標(biāo)向量和試驗(yàn)向量的適應(yīng)度值挑選好的個體進(jìn)入下一代。

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

3.1 研究動機(jī)

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

3.2 搜索算法

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

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

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

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

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

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

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

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

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

3.4 PECO

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

算法2PECO

4 仿真實(shí)驗(yàn)

4.1 演示搜索行為

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

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

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

從圖4 中可以得到，當(dāng)最優(yōu)解在可行域內(nèi)時（比如ATF1），PECO 可以從不同的方向進(jìn)入可行域。當(dāng)最優(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 標(biāo)準(zhǔn)測試函數(shù)和參數(shù)設(shè)置

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

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

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

算法1中，在進(jìn)化初期，t/T>α?xí)r，設(shè)置罰系數(shù)為一個較小的值。本節(jié)針對α的5 種不同取值0.30，0.35，0.40，0.42和0.45，分別進(jìn)行25次獨(dú)立實(shí)驗(yàn)，討論α的參數(shù)效應(yīng)。圖5 展示了IEEE CEC 2010 基準(zhǔn)測試函數(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

在進(jìn)化后期，當(dāng)種群的可行解比例Pf >β時，設(shè)置罰系數(shù)為一個較大的值。這里針對β的5 種不同取值0.5，0.6，0.7，0.8 和0.9，討論β的參數(shù)效應(yīng)，實(shí)驗(yàn)結(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é)果對比與分析

為了驗(yàn)證PECO的尋優(yōu)性能，使用實(shí)驗(yàn)中獲得的最小可行目標(biāo)函數(shù)值的平均值（Mean）和標(biāo)準(zhǔn)偏差（std）作為評價指標(biāo)。在IEEE CEC 2010這組測試集中，將PECO與Co-CLPSO[16]、ITLBO[17]、DeCODE[18]、AIS-IRP[19]這4個算法進(jìn)行性能比較，實(shí)驗(yàn)結(jié)果在表2中給出。所有對比算法的實(shí)驗(yàn)結(jié)果均來源于原論文?！?”表示算法在25次運(yùn)行中不能找到任何可行解?！?”“-”和“≈”分別表示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個基準(zhǔn)測試函數(shù)的實(shí)驗(yàn)結(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 個算法進(jìn)行性能比較，實(shí)驗(yàn)結(jié)果在表3中給出，其中LSHADE44是IEEE CEC 2017 競賽中性能最好的算法。在C17、C19、C26、C28 這4 個測試函數(shù)上，PECO 與對比算法均不能找到任何可行解，因此不提供它們的實(shí)驗(yàn)結(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個基準(zhǔn)測試函數(shù)的實(shí)驗(yàn)結(jié)果Table 3 Experimental results of 18 benchmark functions in IEEE CEC 2017

5 結(jié)束語

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