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

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

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

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

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

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

近年來，求解COPs 的算法主要分為傳統(tǒng)優(yōu)化算法和進(jìn)化算法兩類。傳統(tǒng)優(yōu)化算法包括簡約梯度法、投影梯度法、序列二次規(guī)劃法和外點(diǎn)及內(nèi)點(diǎn)罰函數(shù)法等。這些算法在求解時(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ì)是從候選個(gè)體中選擇優(yōu)質(zhì)個(gè)體進(jìn)入下一代，進(jìn)而使種群收斂到最優(yōu)解。圖1給出了COPs的一個(gè)實(shí)例。

圖1 COPs的一個(gè)實(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)增加一個(gè)懲罰項(xiàng)p(x)，將COPs 轉(zhuǎn)化為無約束優(yōu)化問題進(jìn)行求解?？尚行詼?zhǔn)則由Deb提出，它基于三條準(zhǔn)則比較任意兩個(gè)個(gè)體：（1）一個(gè)可行個(gè)體和一個(gè)不可行個(gè)體，選擇可行個(gè)體。（2）兩個(gè)都是可行個(gè)體，選擇目標(biāo)函數(shù)值小的個(gè)體。（3）兩個(gè)都是不可行個(gè)體，選擇約束違反程度小的個(gè)體。ε約束法通過人為設(shè)定ε值，將約束違反程度小于ε的個(gè)體視為可行個(gè)體進(jìn)行比較，通過這種方式，部分不可行個(gè)體被選擇進(jìn)入下一代，有利于增加種群的多樣性。多目標(biāo)優(yōu)化法將COPs轉(zhuǎn)化為多目標(biāo)優(yōu)化問題，然后利用多目標(biāo)優(yōu)化技術(shù)求解轉(zhuǎn)化后的優(yōu)化問題。混合法將幾種約束處理技術(shù)組合起來求解COPs。

約束優(yōu)化進(jìn)化算法的核心是如何有效平衡種群的目標(biāo)函數(shù)和約束違反程度，為了實(shí)現(xiàn)這個(gè)目的，本文提出一種基于動(dòng)態(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ù)，對于任意兩個(gè)個(gè)體xi和xj，滿足以下任一條件，xi優(yōu)于xj：

其中，

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

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

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

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

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

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

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

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

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

3.1 研究動(dòng)機(jī)

罰函數(shù)法是處理約束的一種簡單有效的方法，但罰系數(shù)值在很大程度上依賴于所優(yōu)化的問題，難以選取。為了解決這個(gè)問題，提出動(dòng)態(tài)罰系數(shù)策略，其中罰系數(shù)根據(jù)種群的可行解比例和進(jìn)化代數(shù)動(dòng)態(tài)變化。在進(jìn)化初期采用較小的懲罰系數(shù)，有利于種群的勘探。在進(jìn)化后期或當(dāng)種群的可行解比例大于設(shè)定的閾值時(shí)采用較大的懲罰系數(shù)，有利于種群的開采和收斂。通過這種方式，可以平衡種群的勘探能力和開采能力。DE 在求解COPs時(shí)具有優(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)生的一個(gè)實(shí)數(shù)。jrand是集合{1,2,…,D}中隨機(jī)選擇的一個(gè)整數(shù)。

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

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

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

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

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

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

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

3.4 PECO

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

算法2PECO

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

4.1 演示搜索行為

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

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

圖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)時(shí)（比如ATF1），PECO 可以從不同的方向進(jìn)入可行域。當(dāng)最優(yōu)解在可行域的邊界上時(shí)（比如ATF2），PECO可以從可行域和不可行域兩個(gè)方向收斂到最優(yōu)解。對于ATF3（包含一個(gè)等式約束條件），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 個(gè)測試函數(shù)，IEEE CEC 2017 測試集包含28 個(gè)測試函數(shù)，這兩組測試集包含多種不同類型的約束優(yōu)化問題，例如具有較強(qiáng)的非線性、較小的可行域和旋轉(zhuǎn)不變性等特點(diǎn)。表1給出了測試函數(shù)的種群規(guī)模(m)、決策變量的維度(D)和最大函數(shù)評價(jià)次數(shù)(maxFES)。在PECO 中，每個(gè)測試函數(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ù)為一個(gè)較小的值。本節(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í)的函數(shù)收斂曲線。從圖5中可知，C10 在α=0.42 時(shí)結(jié)果最優(yōu)，C14 在α=0.42 和0.45 時(shí)結(jié)果最優(yōu)，C15 在α=0.40 和0.45 時(shí)結(jié)果差別不大，找到的解最優(yōu)。

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

在進(jìn)化后期，當(dāng)種群的可行解比例Pf >β時(shí)，設(shè)置罰系數(shù)為一個(gè)較大的值。這里針對β的5 種不同取值0.5，0.6，0.7，0.8 和0.9，討論β的參數(shù)效應(yīng)，實(shí)驗(yàn)結(jié)果在圖6 中給出。從圖6 中可以得出，C10 在β=0.8 時(shí)結(jié)果最優(yōu)，C14在β=0.8 和0.9時(shí)結(jié)果差別不大，找到的解最優(yōu)，C15 在β=0.8 和0.9 時(shí)結(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）作為評價(jià)指標(biāo)。在IEEE CEC 2010這組測試集中，將PECO與Co-CLPSO[16]、ITLBO[17]、DeCODE[18]、AIS-IRP[19]這4個(gè)算法進(jìn)行性能比較，實(shí)驗(yàn)結(jié)果在表2中給出。所有對比算法的實(shí)驗(yàn)結(jié)果均來源于原論文?！?”表示算法在25次運(yùn)行中不能找到任何可行解?！?”“-”和“≈”分別表示PECO 在統(tǒng)計(jì)性能上優(yōu)于、劣于和相似于對比算法。從表2中可以得出，D=10 時(shí)，PECO分別在12個(gè)、6個(gè)、6個(gè)和11個(gè)測試函數(shù)上優(yōu)于Co-CLPSO、ITLBO、DeCODE和AIS-IRP。與PECO相比，Co-CLPSO、ITLBO、DeCODE和AISIRP分別在3個(gè)、3個(gè)、3個(gè)和4個(gè)測試函數(shù)上占優(yōu)。D=30 時(shí)，PECO分別在17個(gè)、11個(gè)、6個(gè)和15個(gè)測試函數(shù)上優(yōu)于Co-CLPSO、ITLBO、DeCODE 和AISIRP。而Co-CLPSO、ITLBO、DeCODE和AIS-IRP分別在1個(gè)、4個(gè)、4個(gè)和2個(gè)測試函數(shù)上優(yōu)于PECO。此外，與Co-CLPSO、ITLBO 和AIS-IRP 這3 個(gè)算法相比，PECO 在高維測試函數(shù)上可以獲得更好的性能。

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

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

5 結(jié)束語

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