求解約束優(yōu)化問(wèn)題改進(jìn)的水波優(yōu)化算法

顧啟元，王俊祥

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

0 引 言

約束優(yōu)化問(wèn)題普遍存在于科學(xué)研究和工程領(lǐng)域中，通常這類(lèi)優(yōu)化問(wèn)題含有多個(gè)線(xiàn)性、非線(xiàn)性約束條件，屬于難處理的一類(lèi)最優(yōu)化問(wèn)題[1]。不失其一般性，約束優(yōu)化問(wèn)題可描述為

(1)

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

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

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

1 標(biāo)準(zhǔn)WWO

WWO算法將待求問(wèn)題的解空間比作為海床，每個(gè)水波類(lèi)比為一個(gè)潛在解Xi。水波適應(yīng)度被定義為關(guān)于水波與海平面垂直距離的函數(shù)：當(dāng)水波越靠近海平面，則適應(yīng)度越高[4]。WWO算法通過(guò)傳播、碎浪和折射3個(gè)操作完成尋優(yōu)過(guò)程。

1.1 傳 播

水波通過(guò)傳播操作完成運(yùn)動(dòng)過(guò)程，第i個(gè)水波Xi更新方程如下

(2)

(3)

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

1.2 碎 浪

為了對(duì)潛在最優(yōu)解鄰近區(qū)域?qū)嵤┚?xì)搜索，對(duì)當(dāng)前新的最優(yōu)解進(jìn)行碎浪操作。具體操作是先隨機(jī)選擇K維，被選擇的每一維按式(4)產(chǎn)生一個(gè)孤立波為Xnew

(4)

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

1.3 折 射

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

(5)

式中：N(u,v) 為高斯隨機(jī)數(shù)，其中u,v分別為均值和方差；Xg為當(dāng)前群體最優(yōu)解；水波Xi根據(jù)式(5)更新后，其波高h(yuǎn)重置為最大值；其波長(zhǎng)按式(6)更新

(6)

2 IWWO求解約束優(yōu)化問(wèn)題

2.1 IWWO

IWWO采用異構(gòu)主從種群結(jié)構(gòu)進(jìn)化，主群負(fù)責(zé)在搜索范圍內(nèi)尋找可行解，從群負(fù)責(zé)接收主群傳遞的可行解，并利用可行解進(jìn)一步尋優(yōu)，提高可行解的質(zhì)量。

2.1.1 主種群更新策略

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

(7)

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

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

(8)

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

在標(biāo)準(zhǔn)WWO中，水波波長(zhǎng)是由水波的適應(yīng)度值、種群中最大適應(yīng)度值和種群中最小適應(yīng)度值確定的。但是在約束問(wèn)題中，對(duì)水波個(gè)體的評(píng)價(jià)不僅僅依賴(lài)適應(yīng)度值，還需考慮該水波是否是可行解，水波波長(zhǎng)只隨適應(yīng)度值而變化是不合適的。因此，設(shè)計(jì)了關(guān)于適應(yīng)度值和約束違反度的水波波長(zhǎng)函數(shù)，該函數(shù)根據(jù)水波進(jìn)化狀態(tài)及時(shí)調(diào)整水波波長(zhǎng)

(9)

式中：φ(X)稱(chēng)為約束違反度，是對(duì)違反約束的度量；通過(guò)式(9) 可知，當(dāng)φ(X)為零時(shí)(即水波為可行解)，波長(zhǎng)的變化與該水波的適應(yīng)度值有關(guān)；當(dāng)φ(X)不為零時(shí)(即水波為不可行解)，為了防止水波波長(zhǎng)下降過(guò)快，波長(zhǎng)的變化是關(guān)于該水波適應(yīng)度值和約束違反度的函數(shù)，φ(X)按式(10)計(jì)算[13]

(10)

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

(11)

難以精確地處理等式約束問(wèn)題，一般將等式約束轉(zhuǎn)化為滿(mǎn)足一定精度的不等式約束來(lái)處理。所以，式(10)中的H(X)按式(12)計(jì)算

(12)

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

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

(13)

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

2.1.2 從種群更新策略

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

(14)

w=1-t/2T

(15)

2.2 約束條件處理

解決約束優(yōu)化問(wèn)題，如何處理約束是獲得最優(yōu)解的關(guān)鍵，ε約束技術(shù)對(duì)擴(kuò)大搜索空間具有良好效果。通過(guò)違反度閾值ε調(diào)節(jié)不可行解和可行解的關(guān)系[13]。當(dāng)0<(X)<ε，水波個(gè)體處于不可行解區(qū)域，稱(chēng)X為優(yōu)秀不可行解。

按照下列準(zhǔn)則評(píng)價(jià)水波個(gè)體的優(yōu)劣：

準(zhǔn)則1水波個(gè)體Xi和Xj均為可行解時(shí)，如果適應(yīng)度值f(Xi)>f(Xj)，則Xi占優(yōu)Xj；

準(zhǔn)則2水波個(gè)體Xi和Xj均為不可行解時(shí)，如果約束違反度φ(Xi)<φ(Xj)，則Xi占優(yōu)Xj；

準(zhǔn)則3水波個(gè)體Xi和Xj，令Xi為可行解，Xj為不可行解。若Xj是優(yōu)秀不可行解，則Xi和Xj中適應(yīng)度值高的個(gè)體占優(yōu)；若Xj不是優(yōu)秀不可行解，則可行解Xi占優(yōu)。

ε約束處理技術(shù)中合適的約束違反度閾值ε利于算法的收斂性。新算法中設(shè)計(jì)一個(gè)自適應(yīng)ε，其值隨著迭代次數(shù)自動(dòng)調(diào)節(jié)的ε松弛度，不僅可以有效利用不可行解的信息提高解質(zhì)量，而且可以幫助提高收斂速度

(16)

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

IWWO算法求解約束優(yōu)化問(wèn)題的流程如算法1所示。

Algorithm 1：IWWO

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

Output：種群最優(yōu)解Xg

步驟1 參數(shù)實(shí)施初始化，在解空間內(nèi)隨機(jī)初始化主群和從群,計(jì)算每個(gè)水波的適應(yīng)度f(wàn)(X)和約束違反度φ(X)；

步驟3 對(duì)主群的每個(gè)水波Xi實(shí)施如下操作：

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

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

步驟5 對(duì)子群的每個(gè)水波Xi實(shí)施如下操作：

3 數(shù)值實(shí)驗(yàn)

為了測(cè)試本文算法在求解約束問(wèn)題的優(yōu)化性能，選取參考文獻(xiàn)[2-4]中24個(gè)標(biāo)準(zhǔn)函數(shù)，這些測(cè)試函數(shù)被廣泛用于測(cè)試求解約束優(yōu)化問(wèn)題的算法。

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

表1 3種水波算法參數(shù)設(shè)置

表2列出了SWWO、SWWO1和IWWO這3種算法求解10個(gè)約束問(wèn)題的實(shí)驗(yàn)結(jié)果。表中函數(shù)名所在的列給出了每個(gè)函數(shù)名和每個(gè)函數(shù)已知最優(yōu)解；表中給出了25次迭代獲得的最優(yōu)解的均值(Mean)、標(biāo)準(zhǔn)差(Std)及依據(jù)均值對(duì)算法的排名(Rank)，其中用粗體表示算法比較中獲得最優(yōu)的結(jié)果。

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

表2 3種水波算法獲得的實(shí)驗(yàn)結(jié)果

IWWO算法在g01，g03，g04，g05，g06，g08和g09這7個(gè)函數(shù)上找到已知最優(yōu)解，說(shuō)明IWWO具有良好的優(yōu)化性能。與SWWO1相比可知，IWWO在10個(gè)函數(shù)的優(yōu)化性能都得到較大的提高。SWWO1和IWWO算法中采用了相同的改進(jìn)波長(zhǎng)更新策略和自適應(yīng)ε約束處理技術(shù)，IWWO獲得更優(yōu)越的性能是因?yàn)镮WWO采用了異構(gòu)主從的種群結(jié)構(gòu)和相應(yīng)的更新策略。第一組實(shí)驗(yàn)結(jié)果表明了文中提出的異構(gòu)主從的種群結(jié)構(gòu)、波長(zhǎng)更新策略和自適應(yīng)ε約束處理技術(shù)對(duì)提高解質(zhì)量是有效的。

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

實(shí)驗(yàn)結(jié)果見(jiàn)表3，表中基于E-BRM遺傳算法的實(shí)驗(yàn)結(jié)果來(lái)自文獻(xiàn)[3]；改進(jìn)的全局人工蜂群算法MGABC實(shí)驗(yàn)結(jié)果來(lái)自文獻(xiàn)[4]；表中‘-’符號(hào)表示文獻(xiàn)沒(méi)有提供該函數(shù)的實(shí)驗(yàn)數(shù)據(jù)；‘NF’符號(hào)表示沒(méi)有找到可行解；對(duì)于每個(gè)函數(shù)，算法獲得的最優(yōu)的均值和標(biāo)準(zhǔn)差加粗表示。

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

表3 24種求解約束優(yōu)化算法對(duì)比實(shí)驗(yàn)結(jié)果

表3(續(xù))

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

4 結(jié)束語(yǔ)

本文提出一種改進(jìn)的水波優(yōu)化算法求解約束優(yōu)化問(wèn)題。算法中設(shè)計(jì)了自適應(yīng)ε約束處理技術(shù)充分利用不可行解信息，增加可行解個(gè)體規(guī)模；設(shè)計(jì)了主-從異構(gòu)種群，以平衡群體的探索和利用。設(shè)計(jì)了水波波長(zhǎng)函數(shù)，使其隨著水波的適應(yīng)度值和違反約束度及時(shí)調(diào)整。與其它算法比較結(jié)果表明本文提出的算法在求解帶有等式約束和不等式約束的優(yōu)化問(wèn)題時(shí)展現(xiàn)了良好的整體優(yōu)化性能。

從實(shí)驗(yàn)結(jié)果分析可知，針對(duì)高維約束優(yōu)化問(wèn)題，雖然本文的提出算法可以找到可行解，但是可行解的精度有待進(jìn)一步提高。下一步工作，將通過(guò)與其它技術(shù)結(jié)合的方法提升高維約束優(yōu)化問(wèn)題解的質(zhì)量。