求解約束優化問題改進的水波優化算法

顧啟元，王俊祥

(重慶文理學院 軟件工程學院，重慶 402160)

0 引 言

約束優化問題普遍存在于科學研究和工程領域中，通常這類優化問題含有多個線性、非線性約束條件，屬于難處理的一類最優化問題[1]。不失其一般性，約束優化問題可描述為

(1)

式中：f(·)為目標函數，lk和uk分別為xk的下界和上界；gi(X)和hj(X)分別表示不等式約束和等式約束；如果存在集合R，R中元素可以使n個g(x)不等式和m個h(x) 等式成立，那么集合R中的元素視為一個可行解。

經典非線性規劃方法求解約束優化問題前提條件是目標函數和約束條件連續且可微。群智能優化算法為非連續、多模態等復雜的約束優化問題提供求解新路徑[2-5]。水波優化算法(water wave optimization，WWO)是一種新型群智能優化范式，由國內學者鄭宇軍提出[6]。WWO算法受淺水波理論模型啟發，水波個體利用傳播、折射和碎浪方式在解空間中有效搜索[7]。WWO算法具有原理簡明、控制參數較少、易于實現等優點。目前WWO已在軟件形式化開發關鍵部件選取[8]和車輛路徑[9]等領域上取得了成功的應用。

WWO在求解無約束問題中已嶄露頭角[10-12]，但是求解約束優化問題鮮有報道。本文嘗試提出改進的WWO算法求解約束優化問題。首先設計了主從異構種群，即兩個種群采用不同的更新方式，主群結合ε約束處理技術實現探索可行解，為了加快收斂速度和增強信息交互，主群中個體可以依概率進行個體間學習。在主群傳播更新方式中，設計了關于水波適應度值和違反約束度的波長函數，利于水波個體根據進化狀態及時調整波長。從群負責利用可行解搜索全局最優解，為了避免早期收斂，從群采用了自適應學習策略以平衡群體的探索和利用。最后設計了隨迭代次數變化的放松約束度，不僅可以充分利用不可行解的信息以獲得可行解，還可以提高算法收斂精度。實驗結果表明，IWWO算法在求解約束問題方面展現出優越性。

1 標準WWO

WWO算法將待求問題的解空間比作為海床，每個水波類比為一個潛在解Xi。水波適應度被定義為關于水波與海平面垂直距離的函數：當水波越靠近海平面，則適應度越高[4]。WWO算法通過傳播、碎浪和折射3個操作完成尋優過程。

1.1 傳 播

水波通過傳播操作完成運動過程，第i個水波Xi更新方程如下

(2)

(3)

式中：μ為波長衰減系數；f(Xi)為個體Xi的適應度值；fmax和fmin分別表示當前群體中最大適應度和最小適應度值；為避免分母為零，設置為一個極小的正數。

1.2 碎 浪

為了對潛在最優解鄰近區域實施精細搜索，對當前新的最優解進行碎浪操作。具體操作是先隨機選擇K維，被選擇的每一維按式(4)產生一個孤立波為Xnew

(4)

式中：β是碎浪系數 (β∈(0.001,0.01))；Xg表示當前種群獲得的最優解；α為N(0,1)高斯隨機數；K通常選取為min(12,D/2)[7](D是水波的總維度)；如果產生所有的孤立波f(Xnew)

1.3 折 射

當水波的波高值遞減為0時，該水波停止進化。為了改善水波停滯情況，水波算法按式(5)實施折射操作

(5)

式中：N(u,v) 為高斯隨機數，其中u,v分別為均值和方差；Xg為當前群體最優解；水波Xi根據式(5)更新后，其波高h重置為最大值；其波長按式(6)更新

(6)

2 IWWO求解約束優化問題

2.1 IWWO

IWWO采用異構主從種群結構進化，主群負責在搜索范圍內尋找可行解，從群負責接收主群傳遞的可行解，并利用可行解進一步尋優，提高可行解的質量。

2.1.1 主種群更新策略

為了增強信息交互加快收斂速度，主種群中水波依概率學習群體中其它個體。主種群中的水波按式(7)更新

(7)

式中：j∈(1,2,…,N)(N為種群規模)；rand(0,1) 是服從[0,1]均勻分布的隨機數；水波個體依概率η實施傳播操作，依概率1-η學習其它個體。η為學習率，其值隨迭代次數變化，按式(8)更新

η=(T-ηmin·t)/T

(8)

式中：t為迭代步數，T為最大迭代步數；ηmin為最小學習率。隨著迭代次數增加，η值由1遞減為ηmin，使得水波個體在進化前期依較大概率進行個體間的相互學習，充分利用優秀個體的信息快速找到可行解；在進化后期，水波個體依較大概率實施傳播操作，利于全局勘探可行解。

在標準WWO中，水波波長是由水波的適應度值、種群中最大適應度值和種群中最小適應度值確定的。但是在約束問題中，對水波個體的評價不僅僅依賴適應度值，還需考慮該水波是否是可行解，水波波長只隨適應度值而變化是不合適的。因此，設計了關于適應度值和約束違反度的水波波長函數，該函數根據水波進化狀態及時調整水波波長

(9)

式中：φ(X)稱為約束違反度，是對違反約束的度量；通過式(9) 可知，當φ(X)為零時(即水波為可行解)，波長的變化與該水波的適應度值有關；當φ(X)不為零時(即水波為不可行解)，為了防止水波波長下降過快，波長的變化是關于該水波適應度值和約束違反度的函數，φ(X)按式(10)計算[13]

(10)

式中的不等式條件G(X)按式(11)計算

(11)

難以精確地處理等式約束問題，一般將等式約束轉化為滿足一定精度的不等式約束來處理。所以，式(10)中的H(X)按式(12)計算

(12)

式中：δ為等式約束的容忍參數(通常取值δ=10-4)。

β=(βmaxT-βmin·t)/T

(13)

其中，βmin、βmax分別為碎浪系數的最小值和最大值。

2.1.2 從種群更新策略

從種群采用自適應的折射算子，主要用于對可行解的局部利用，更新方程如下式

(14)

w=1-t/2T

(15)

2.2 約束條件處理

解決約束優化問題，如何處理約束是獲得最優解的關鍵，ε約束技術對擴大搜索空間具有良好效果。通過違反度閾值ε調節不可行解和可行解的關系[13]。當0<(X)<ε，水波個體處于不可行解區域，稱X為優秀不可行解。

按照下列準則評價水波個體的優劣：

準則1水波個體Xi和Xj均為可行解時，如果適應度值f(Xi)>f(Xj)，則Xi占優Xj；

準則2水波個體Xi和Xj均為不可行解時，如果約束違反度φ(Xi)<φ(Xj)，則Xi占優Xj；

準則3水波個體Xi和Xj，令Xi為可行解，Xj為不可行解。若Xj是優秀不可行解，則Xi和Xj中適應度值高的個體占優；若Xj不是優秀不可行解，則可行解Xi占優。

ε約束處理技術中合適的約束違反度閾值ε利于算法的收斂性。新算法中設計一個自適應ε，其值隨著迭代次數自動調節的ε松弛度，不僅可以有效利用不可行解的信息提高解質量，而且可以幫助提高收斂速度

(16)

式中：t為迭代步數，T為最大迭代步數。由式(16)可知，松弛度ε從ε0開始遞減，在進化初期松弛度有較大的值，提高利用可行域的效率；后期松弛度為0，利于算法及時收斂。

IWWO算法求解約束優化問題的流程如算法1所示。

Algorithm 1：IWWO

Input：待求解問題參數設置(包括問題維度D、迭代總次數T、種群規模N、約束條件適φ(·)、適應度函數f(X) 等)

Output：種群最優解Xg

步驟1 參數實施初始化，在解空間內隨機初始化主群和從群,計算每個水波的適應度f(X)和約束違反度φ(X)；

步驟3 對主群的每個水波Xi實施如下操作：

司馬遷對“至圣”孔子之關注，是出于繼承孔子“作《春秋》”偉大事業的遺志，也是出于對孔子的情感認同。那么司馬遷心中的“至圣”又有著什么樣的內涵？他筆下的“至圣”孔子又有怎樣的特點？

步驟4 若主群更新完畢，則轉向步驟5，否則返回步驟3；

步驟5 對子群的每個水波Xi實施如下操作：

3 數值實驗

為了測試本文算法在求解約束問題的優化性能，選取參考文獻[2-4]中24個標準函數，這些測試函數被廣泛用于測試求解約束優化問題的算法。

第一組實驗設計為了測試算法中改進的策略對求解性能的影響。選取10個測試函數((g01-g10))。對比的算法有標準WWO(SWWO)，SWWO1和IWWO算法，其中SWWO算法采用固定ε值的約束處理技術；SWWO1算法采用文中提出的自適應ε約束處理技術和改進的波長更新策略；為了保證實驗的公平性，設置算法的迭代次數為2×104；所有算法獨立運行25次。算法的具體參數設置見表1。

表1 3種水波算法參數設置

表2列出了SWWO、SWWO1和IWWO這3種算法求解10個約束問題的實驗結果。表中函數名所在的列給出了每個函數名和每個函數已知最優解；表中給出了25次迭代獲得的最優解的均值(Mean)、標準差(Std)及依據均值對算法的排名(Rank)，其中用粗體表示算法比較中獲得最優的結果。

從表2的結果中可以看出，3種算法中IWWO算法獲得優化性能最好，SWWO1優化性能次之，SWWO優化性能最差。與SWWO相比，SWWO1在10個問題上的優化性能都有所提高，特別在g05, g07～g10 5個函數上，SWWO1性能有明顯提高。說明改進的波長更新策略和自適應的ε約束處理技術有助于提高解的質量。

表2 3種水波算法獲得的實驗結果

IWWO算法在g01，g03，g04，g05，g06，g08和g09這7個函數上找到已知最優解，說明IWWO具有良好的優化性能。與SWWO1相比可知，IWWO在10個函數的優化性能都得到較大的提高。SWWO1和IWWO算法中采用了相同的改進波長更新策略和自適應ε約束處理技術，IWWO獲得更優越的性能是因為IWWO采用了異構主從的種群結構和相應的更新策略。第一組實驗結果表明了文中提出的異構主從的種群結構、波長更新策略和自適應ε約束處理技術對提高解質量是有效的。

第二組實驗設計是將最新求解約束問題的算法與本文算法進行對比分析。對比算法有混沌灰狼算法CGWO(2018)[2]，基于E-BRM遺傳算法(2018)[3]和改進的全局人工蜂群算法MGABC(2018)[4]。算法獨立運行25次，最大迭代次數是2×104，種群規模為100；CGWO的實驗參數設置參照文獻[2]。

實驗結果見表3，表中基于E-BRM遺傳算法的實驗結果來自文獻[3]；改進的全局人工蜂群算法MGABC實驗結果來自文獻[4]；表中‘-’符號表示文獻沒有提供該函數的實驗數據；‘NF’符號表示沒有找到可行解；對于每個函數，算法獲得的最優的均值和標準差加粗表示。

從表3可知，對于cec2006的24個測試函數，IWWO算法能夠穩定找到已知最優解的函數共12個(g01，g03，g04，g05，g06，g08，g11，g12，g13，g15，g16，g24)，說明IWWO求解約束問題具有優良的尋優能力和魯棒性。對于函數g17，目前已獲得的最優解8853.5397，IWWO獲得最優解為8853.5371，優于當前最優解。對于g20(問題維度為22)和g22(問題維度為24)兩個高維函數，IWWO可以找到可行解，但是E-BRM和 CGWO算法并沒有找到可行解。表明對于高維復雜約束優化問題，IWWO也具有良好的尋優潛力。

表3 24種求解約束優化算法對比實驗結果

表3(續)

對于g02函數，IWWO排名為第4；對于g10和g18函數，IWWO排名為第2；在其它17個函數上，IWWO排名均為第一。CGWO在g10函數排名第1；E-BRM在g02，g08，g12和g24這4個函數上排名第一；MGABC在 g08，g12，g16，g18和g24這5個函數上排名第一；按平均排名，IWWO得分是1.25，MGABC得分是2.15，E-BRM得分是2.29，CGWO得分是3.08。由平均排名可知，IWWO的優化性能最好，MGABC優化性能次之，CGWO優化性能最差。

4 結束語

本文提出一種改進的水波優化算法求解約束優化問題。算法中設計了自適應ε約束處理技術充分利用不可行解信息，增加可行解個體規模；設計了主-從異構種群，以平衡群體的探索和利用。設計了水波波長函數，使其隨著水波的適應度值和違反約束度及時調整。與其它算法比較結果表明本文提出的算法在求解帶有等式約束和不等式約束的優化問題時展現了良好的整體優化性能。

從實驗結果分析可知，針對高維約束優化問題，雖然本文的提出算法可以找到可行解，但是可行解的精度有待進一步提高。下一步工作，將通過與其它技術結合的方法提升高維約束優化問題解的質量。