改進混合蛙跳算法在馬斯京根模型參數優化中的應用

楊 柳

(華北水利水電大學水利學院，鄭州 450046)

0 引 言

馬斯京根模型是水文上根據上游河道水情推算下游河道水情的一種應用廣泛的河道洪水演算方法，在水庫調水和防洪中扮演著十分重要的作用[1]。由GT.麥卡錫于1938年提出該方法，并首次在美國馬斯京根河使用，故稱為馬斯京根模型[2]。若要更準確的演算河道洪水流量，其模型參數的精確性對演算結果有著很重要的影響。最早的馬斯京根模型參數尋優有試錯法[3]、非線性規劃法[4]、最小面積法[5]和最小二乘法[6]等，然而這些方法在實際的洪水演算中較復雜，且不滿足洪水演算所必需的穩定性及高效性。因此，近年來國內外學者將人工智能算法引入馬斯京根模型參數的估算中，也得到了一定的優化效果，如傳統蛙跳算法、遺傳算法、差分進化算法等[7-9]。然而由于馬斯京根洪水演算法的近似性以及這些人工智能算法本身的缺陷等，使得演算效果并不理想。

混合蛙跳算法(SFLA)是在局部更新的基礎上通過全局搜索最優解的啟發式協同搜索算法，已廣泛應用于多個研究領域[10-12]。但傳統SFLA容易陷入局部最優且計算精度不滿足要求，在處理復雜函數尋優問題上結果并不理想。因此，眾多學者在處理有約束函數優化問題上，對SFLA進行了改進，如張瀟丹[13]等通過免疫接種和模擬退火思想引入SFLA中，將有約束函數轉化為無約束函數，其計算精度和魯棒性均有所提高；張友華[14]等受PSO算法啟發，在SFLA引入異步時變學習因子，可以明顯改善SFLA的尋優效率和精度；這些改進方案為混合蛙跳算法在有約束函數優化問題上的研究提供了有益的參考依據。鑒于此，本文在SFLA的基礎上，引入歐式距離對青蛙個體重新分組，再經rand/1/bin變異算子生成新個體，增加算法迭代后期的個體多樣性，將解決全局性優化問題較好的ε-DE算法[15]與易陷入局部最優SFLA算法相結合，有效避免了算法運行中后期陷入局部最優，將改進后算法應用于馬斯京根模型參數優化問題中，為模型的參數尋優提供新的思路，以期提供流域水文模型的演算效率和精度。

1 馬斯京根模型

馬斯京根模型目前仍廣泛應用于河道洪水驗算問題中，以水量平衡方程、槽蓄方程分別代替連續方程和水動力學方程[16]。其轉換后的方程為：

(1)

式中：W為槽蓄量，m3；I、Q為河段的入、出流量，m3/s；Q′為示儲流量，m3/s；x為河流比重因子；K為蓄槽系數，h。

對式(1)進行差分，即：

(2)

(3)

c0+c1+c2=1

(4)

由式(3)可知馬斯京根模型要演算河道洪水流量，首先應確定參數K、x或c0、c1、c2的值。若要對K、x優化，則要求K、x呈單一關系，最早的參數優選方法有試錯法、最小二乘法等，在K、x的值確定以后，按照式(3)求解c0、c1、c2，再通過式(2)進行洪水演算。但是這種線性關系對實際的河道洪水演算并不成立，且演算結果往往誤差較大。因而本文在混合蛙跳算法的基礎上進行改進，直接對流量演算系數c0、c1、c2進行尋優,然后利用下式反求K、x。

K=[(c1+c2)/(c1+c0)]Δt

(5)

x=(c1+c0)/2(c1+c2)+c0/(c0-1)

(6)

2 改進混合蛙跳算法優化模型

2.1 基本混合蛙跳算法

SFLA首先在可行域內生成P只青蛙構成初始群體，第i只青蛙代表問題的解為Xi=(xi1，xi2，…，xiD)，D為解的維數，求解每只青蛙的目標函數初始值f(Xi)，將每只青蛙的初始值按遞減順序排序，再將青蛙群劃分成m個種群，每個種群含n只青蛙。對每個族群，將目標初始值最優解記為Xb,最差解記為Xw，而在青蛙群體中將函數最優解記為Xg[10]。在算法迭代中，只對族群中的Xw進行更新，其策略為：

Dj=rand(Xb-Xw)

(7)

newXw=oldXw+Dj

(8)

式中：j=1，2,…，D；-Dmax≤Dj≤Dmax,Dmax表示青蛙移動最大步長。更新迭代后，如果新的解newXw優于原來的解oldXw，則代替原來族群中的解。否則，用Xg代替Xb重復執行更新策略：

Dj=rand(Xg-Xw)

(9)

重復此更新策略至滿足局部更新次數。當全部子群的局部搜索完成后，合并所有子群中的青蛙，然后根據函數適應度值降序排列再次劃分子群，最后重復局部搜索，直至滿足算法結束條件為止。

2.2 改進混合蛙跳算法

Deb比較準則中規定種群只在可行域內進化，為了更好的處理有約束優化問題，鄭建國等[15]提出一種改進的差分進化算法ε-DE，通過新的比較機制對可行域邊界的非可行解進行充分利用，在可行域與非可行域兩側逼近最優解。新的比較機制其思想主要有兩方面：①使得部分逼近可行域邊界的非可行解有勝出的可能性；②隨著迭代次數的累計，這部分非可行解的信息逐漸減少。本文引入ε-DE算法對SFLA算法進行改進。

2.2.1ε-DE算法

(1)基本概念。

①懲罰函數：已知約束等式Fi(X)，作轉換|Fi(X)|-δ≤0，其中δ為容忍因子，一般取值0.000 1。將各個體X在第i個約束條件上的約束違反程度記為Gi[17]：

(10)

個體約束違反程度通過下式計算：

(11)

此時將約束優化問題轉化為f(X)=F(X)+σG(X),其中σ為罰因子，G(X)為約束違反程度，σG(X)為懲罰項。

②種群約束允許放松程度ε(gen)，表示種群進化到gen代時，個體X違反約束程度G(X)的界限[15]。

(12)

式中：θ2表示每進化一代，ε(gen)減小的比例，取1.035。

在種群進化過程中，若0

(2)兩青蛙個體優選準則。約束優化問題與全局性優化問題不同，前者是將解的尋找空間劃分為非可行域和可行域。ε-DE的設計目有兩個：①找到或接近可行域；②在約束范圍內找到最優解。為了實現該算法的設計目的，提供一下3個準則: 若兩個均為可行解，則函數適應度值小的勝出；若兩個均為非可行解，則G(X)小的取勝；若其中一個為可行解，一個為非可行解，則分兩種情況討論：情形1：若非可行解為可接受解，則比較二者的函數適應度值，小的勝出；情形2：若非可行解為不可接受解，則可行解勝出。根據以上比較準則，可設計兩個青蛙個體的比較函數Prior(X1，X2)[18]，即：

P(X1,X2)=

(13)

若函數Prior(X1，X2)返回值等于1，則X1優于X2，返回值等于0，則X1劣于X2。

對于最優解位于可行域邊界的問題，利用改進算法比較準則中的第3條第一種情形，期望種群在非可行域與可行域兩側逐漸逼近最優解。對于可行域占整個尋優空間比例太小的問題，利用比較準則中的第3條第二種情形，期望通過非可行解的剔除，無限逼近可行域。

隨著迭代次數的累計，種群ε(gen)不斷減小，篩選更接近可行域邊界的非可行解提供進化相關信息。當ε(gen)=0時，進化過程只在可行域內進行。

2.2.2 SFLA算法改進

(1)歐式距離的引入。在SFLA算法中對青蛙分群按其適應度值的高低進行。該方法的不足是可能會使得相距較遠的個體分在同一個族群中，從而影響算法的更新效率，因此本文引入歐式距離對青蛙劃分族群。

Step1：在初始群體內任意選取一只青蛙X；

Step2：在初始群體中依次挑選離青蛙X最近的P-1只青蛙，和青蛙X共同組成一個族群；

Step3：在初始種群中除去已挑選的P只青蛙；

Step4：重復Step1～Step3，直至將所有青蛙分為m個族群，每個族群的青蛙數量為n。

(14)

式中：r1、r2和r3為集合{1,2，…，n}中異于i的3個整數；F是DE控制參數。

(15)

(16)

式中：rand是一個[0,1]的隨機數；jrand是[1,n]的一個隨機整數；CR為雜交概率。

2.2.3ε-DE-SFLA算法流程

Step1：參數初始化。

Step1-1：種群規模P，族群數量m，族群內青蛙數量n，族群局部更新迭代次數N，最大允許跳動步長D，全局混合更新迭代次數G，隨機初始化蛙群的位置；

Step1-2：求解每只青蛙的適應度值f(Xi)。根據歐式距離法將n只青蛙分為m個族群，并標記每個族群中獲得最優適應度值的青蛙Xb。

Step2：更新種群。

Step2-1：統計當前種群可行解比例，每次迭代過程中，在[0,1]區間內任意生成一個數rand，若rand值小于此時種群內可行解所占比例時，繼續下一步，否則跳轉到Step2-3；

Step2-2：將P只青蛙視為一個種群，按照式(13)～(16)產生新個體，將父代和子代合并，從中再次選擇P只青蛙。先在可行解中根據目標函數值由小到大挑選，若可行解的數量小于種群規模時，從非可行解中按G(X)由小到大選擇補齊，達到種群規模P為止。跳躍執行Step3；

Step2-3：按照歐式距離法再將P只青蛙分為m個族群，并設置族群，計K為1；

Step2-4：對第K個族群，按照式(13)～(16)產生新的青蛙個體y,并與該族群中的最優解Xb比較，按照ε-DE算法更新每個族群當前最優解；

Step2-5：若未達到族群設置最大迭代次數，令K=K+1，當K≤m時，跳轉執行Step2-4。

Step3：若達到算法結束條件，輸出種群當前最優解，退出循環，否則跳轉執行Step2。

2.3 函數測試

本文選取Griewank和Ackley函數對改進前后的混合蛙跳算法進行測試分析，為了提高算法計算結果的精度，每個函數均連續運行20次。設混合迭代次數G=100，種群規模P=30,族群個數m=5，族群內青蛙個體n=30，族群內進化代數N=10，分別用SFLA和ε-DE-SFLA對以上兩個函數進行測試，計算結果見表1，函數測試的進化曲線見圖1。

表1 函數測試尋優結果

圖1 兩種函數測試結果

由表1可見，相較于傳統SFLA，ε-DE-SFLA在最優解計算過程中，尋優精度都有明顯的提高。同時，由圖1可知，對每個測試函數，ε-DE-SFLA的進化曲線在縱軸上較SFLA下降更快，表明ε-DE-SFLA無論是在求解精度還是速度上相比SFLA均有明顯提高。

3 改進蛙跳算法在馬斯京根模型中的應用

以實際出流與演算出流的離差平方和最小為判據，則馬斯京根模型參數優化目標函數為：

(17)

約束條件為：

g1:c0∈[0,1]

(18)

g2:c1∈[0,1]

(19)

g3:1-c0-c1∈[0,1]

(20)

將g1、g2視為變量取值范圍，對于約束g3采用懲罰函數法進行處理，則懲罰適應值函數為：

minf=F(X)+h(g3(c0,c1))

(21)

式中：h(g3(c0,c1))為懲罰項，當約束g3滿足時取值為0，否則取值為106。

于是則可采用ε-DE-SFLA求解馬斯京根模型的參數。對于ε-DE-SFLA的參數設置為：種群規模P=100，族群個數為m=10,每個族群更新的次數Lmax=10，雜交概率CR=1/s，s為自變量空間的維數。本文仍采用文獻[16]中例2的某一次洪水數據進行演算，演算時段取12 h，并將本文算法與其他文獻的優選方法如傳統混合蛙跳算法[7]、加速遺傳算法[16]和最小二乘法[6]等進行比較，結果見表2。同時，采用平均絕對誤差評價以上4種方法的演算精度結果見表3。

根據表2、表3可知，改進后的-DE-SFLA算法與已有算法相比，平均絕對誤差更小，表明改進后的算法在馬斯京根模型參數優化中具有更好的計算精度。

表2 實測數據與演算結果對比 m3/s

表3 馬斯京根模型參數優化值與精度評價

4 結 論

傳統SFLA中以青蛙個體的適應度值高低進行族群劃分，此方法可能會使群體中距離甚遠的青蛙劃分在同一族群中，從而導致局部迭代效率低且易陷入局部最優。針對該缺點，本文將ε-DE算法與SFLA算法相結合，同時引入歐氏距離來劃分族群，并采用rand/1/bin 的差分雜交變異算子產生新個體，提高算法局部更新效率。對于有約束優化問題，將ε-DE算法與SFLA算法相結合，可使算法在更新迭代過程中能充分利用種群中非可行解的信息，始終保持算法在迭代過程中個體信息的多樣性，進而有效提高算法的精度和運行效率。在對馬斯京根模型參數優化應用中，也驗證了ε-DE-SFLA算法具備較好的尋優能力，體現了該算法在處理有約束優化問題時的優越性和魯棒性。

□