趙紅杰，柏繼云，馬力

（1.東北農(nóng)業(yè)大學(xué)理學(xué)院，哈爾濱 150030；2.東北農(nóng)業(yè)大學(xué)工程學(xué)院，哈爾濱 150030）

遺傳擴(kuò)展蟻群算法用于馬斯京根模型參數(shù)估計

趙紅杰1，柏繼云1，馬力2

（1.東北農(nóng)業(yè)大學(xué)理學(xué)院，哈爾濱 150030；2.東北農(nóng)業(yè)大學(xué)工程學(xué)院，哈爾濱 150030）

文章針對擴(kuò)展蟻群算法收斂速度慢，易陷入局部最優(yōu)缺點(diǎn)，對擴(kuò)展蟻群算法提出改進(jìn)策略，引入遺傳算法產(chǎn)生初始解，加入局部細(xì)搜策略。根據(jù)解的權(quán)重改進(jìn)解存儲器中每個解權(quán)值，增加解的方向性，快速獲得最優(yōu)解，通過多個典型函數(shù)尋優(yōu)確定方法有效性。利用改進(jìn)后算法解決洪水演算馬斯京根模型參數(shù)估計問題，通過與現(xiàn)有馬斯京根模型參數(shù)估計方法對比，驗(yàn)證算法具有更好優(yōu)化性能，為精確估計馬斯京根模型參數(shù)提供更有效方法。

遺傳算法；擴(kuò)展蟻群算法；連續(xù)空間優(yōu)化；馬斯京根模型；參數(shù)估計

Dorigo等首次提出用于求解連續(xù)空間優(yōu)化問題的最新蟻群優(yōu)化算法—擴(kuò)展蟻群算法（Extended ant colony algorithm-ACOE）[1-2]，該算法通過引入解存儲器作為信息素模型，將基本蟻群算法的離散概率選擇方式連續(xù)化，將蟻群算法擴(kuò)展到連續(xù)空間優(yōu)化問題上。ACOE按照蟻群算法框架設(shè)計，簡單易行。但ACOE仍然采用隨機(jī)方式產(chǎn)生初始解，初始信息素匱乏，僅通過一次搜索中解存儲器中解的目標(biāo)函數(shù)值的大小構(gòu)建信息素，解方向不夠明確，易陷入局部最優(yōu)。因此，本文針對ACOE算法的缺點(diǎn)進(jìn)行三點(diǎn)改進(jìn)，引入能產(chǎn)生豐富解的遺傳算法[3]產(chǎn)生初始解，并加入局部細(xì)搜策略避免陷入局部最優(yōu)，根據(jù)解的重要性改進(jìn)解存儲器中每個解權(quán)值，增加解方向性，快速獲得最優(yōu)解，將此改進(jìn)算法稱為改進(jìn)遺傳擴(kuò)展蟻群算法（Genetic algorithmextended ant colony optimization，GAACOE）。

馬斯京根模型是河道洪水預(yù)報的重要模型并廣泛應(yīng)用[4]。馬斯京根模型參數(shù)估計是運(yùn)用馬斯京根模型進(jìn)行預(yù)報的前提。傳統(tǒng)確定模型參數(shù)方法主要有試錯法[5]、圖解法[6]、最小二乘法[7]等計算量大、計算過程繁瑣、受經(jīng)驗(yàn)制約等，結(jié)果精度不高。近年來，智能優(yōu)化算法逐步應(yīng)用到流域水文模型參數(shù)的率定優(yōu)選上。常用的有遺傳算法、粒子群算法等[8-11]，這些算法克服水文系統(tǒng)受天文、氣象、氣候、下墊面、人文活動等眾多因素影響而表現(xiàn)出的高維、多峰值、非線性、不連續(xù)、非凸性和帶噪聲等復(fù)雜特征，對流域水文模型參數(shù)進(jìn)行全局優(yōu)選，尋找最優(yōu)解。本文采用改進(jìn)的遺傳擴(kuò)展蟻群算法優(yōu)化參數(shù)，并與這些智能算法對比，驗(yàn)證其優(yōu)越性和實(shí)用性。

1 遺傳擴(kuò)展蟻群算法

1.1 擴(kuò)展蟻群算法簡介

ACOE算法主要包括初始化解存儲器、通過高斯核概率密度函數(shù)構(gòu)造可行解及信息素更新3個步驟[1-2]。

1.1.1 解存儲器初始化

表1 ACOE的解存儲器結(jié)構(gòu)Table 1 Archive of solutions kept by ACOE

1.1.2 對高斯核概率密度函數(shù)采樣構(gòu)建可行解

1.1.3 信息素更新

將上面m只螞蟻采樣得到的m個解向量與原解存儲器T中的解一起組成一個臨時解向量，并將這個臨時解向量按目標(biāo)函數(shù)排序，取前K個解向量加入解存儲器T里，以保持其長度K不變。確保只有最優(yōu)解能夠存儲在解存儲器中，使解存儲器里的解能更好地引導(dǎo)搜索。

1.2 改進(jìn)遺傳擴(kuò)展蟻群算法

1.2.1 利用遺傳算法產(chǎn)生初始解

遺傳算法[3]是以達(dá)爾文的生物進(jìn)化論和孟德爾的遺傳變異理論為基礎(chǔ)構(gòu)建的一種概率搜索算法，將問題的可行解編碼為一個二進(jìn)制串，稱之為染色體。遺傳算法首先生成多個初始染色體種群，并基于種群反復(fù)迭代執(zhí)行選擇、交叉、變異的遺傳操作獲得問題的最優(yōu)解[12]。遺傳操作可以使問題很快收斂到問題的較優(yōu)解，但遺傳算法缺少反饋操作，很難獲得全局最優(yōu)解。因此本文利用遺傳算法產(chǎn)生ACOE算法的初始解信息，利用遺傳算法快速的全局搜索特性，獲得ACOE算法的初始解存儲器。

設(shè)置遺傳算法迭代次數(shù)為t（tb＜t＜tc），其中tb為最小遺傳迭代次數(shù)，tc為最大遺傳迭代次數(shù)。計算每次迭代時的進(jìn)化率R=-fi（s）--fi+1（s），如果連續(xù)3代進(jìn)化率R均滿足0＜R＜Rmin，則終止遺傳算法，進(jìn)入蟻群算法。其中-fi（s）為遺傳算法第i次迭代后得到的適應(yīng)度函數(shù)平均值，Rmin為給定的最小閾值。

1.2.2 在ACOE算法中增加局部細(xì)搜索

ACOE算法的另一個缺點(diǎn)是算法容易陷入局部最優(yōu)，為避免算法陷入局部最優(yōu)，同時也為增加搜索精度，本節(jié)引入變尺度局部細(xì)搜索策略，在迭代的每一步對ACOE算法迭代最優(yōu)解進(jìn)行局部細(xì)搜。

式中，t為迭代次數(shù)，aj≤Xj≤bj，j=1，2，…，n是優(yōu)化問題解空間，很顯然，rti會隨著迭代次數(shù)的增加而單調(diào)遞減，因而稱為變尺度搜索，然后，在搜索區(qū)域內(nèi)利用均勻分布隨機(jī)產(chǎn)生一定數(shù)量的解，對剛產(chǎn)生的自變量，進(jìn)行函數(shù)值比較，若找到優(yōu)于全局的最優(yōu)螞蟻，則設(shè)為全局最優(yōu)螞蟻。

1.2.3 解存儲器的構(gòu)建和更新

1.3 遺傳擴(kuò)展蟻群算法（GAACOE）流程

Step1：GA初始化：選取種群規(guī)模M，概率Pc和Pm，最大迭代次數(shù)、最小迭代次數(shù)、最小進(jìn)化率R，以隨機(jī)分布產(chǎn)生M個初始種群。

Step2：對個體進(jìn)行適應(yīng)度評價，適應(yīng)度函數(shù)取為目標(biāo)函數(shù)值；

Step3：進(jìn)行遺傳操作產(chǎn)生新的群體；

Step4：返回Step2，對新群體解碼進(jìn)行適應(yīng)度評價；

Step5：由最小最大迭代次數(shù)或最小進(jìn)化率決定算法終止時刻，若滿足條件，轉(zhuǎn)Step6，否則轉(zhuǎn)Step3；

Step6：將遺傳算法獲得的最優(yōu)解作為ACOE解存儲器的初始解：在遺傳算法最后一代選擇適應(yīng)函數(shù)最高的K/2個個體組成一個矩陣S1，同時以均勻分布隨機(jī)產(chǎn)生K/2個個體組成矩陣S2，與S1合成一個維數(shù)為K×N的新矩陣S，N為決策變量的維數(shù)；

Step7以矩陣為解存儲器的初始解，利用擴(kuò)展蟻群算法ACOE求解，在每一次迭代后，利用式（4）求半徑執(zhí)行局部細(xì)搜策略，運(yùn)行ACOE算法G代。

2 仿真分析

本文應(yīng)用改進(jìn)擴(kuò)展蟻群算法（GAACOE）和擴(kuò)展蟻群算法（ACOE）以及標(biāo)準(zhǔn)遺傳算法（SGA），選用典型函數(shù)進(jìn)行仿真實(shí)驗(yàn)，所有仿真均在奔騰4 CPU和MATALAB 7.0環(huán)境下運(yùn)行。為了便于比較，本文仍然選擇文獻(xiàn)[1]實(shí)例。

2.1 參數(shù)選擇

對照文獻(xiàn)[1]，ACOE算法初始參數(shù)選擇：螞蟻數(shù)目m=70，解存儲器容量K=45，參數(shù)ξ=1，q= 0.001。SGA參數(shù)：種群規(guī)模為M=50，輪盤賭選擇，單點(diǎn)交叉，單點(diǎn)變異，交叉概率pc=0.90和變異概率pm=0.10-[1:1:M]·（0.01）/M。GAACOE參數(shù)選擇：遺傳部分參數(shù)取種群規(guī)模為M=35，交叉概率pc=0.90和變異概率Pm=0.10-[1:1:M]*（0.01）/M，最大迭代次數(shù)200、最小迭代次數(shù)100、最小進(jìn)化率R=10；ACOE算法部分螞蟻數(shù)目m=70，解存儲器容量K=45，參數(shù)ξ=1，q=0.0001。限定步數(shù)均為max= 400。

2.2 Rosenbrock（R5）函數(shù)

N=5，-10≤xi≤10，該函數(shù)形勢復(fù)雜，決策變量較多，搜索空間較大，當(dāng)xi=1時取得全局最小值0，當(dāng)函數(shù)值為0.0001時取得成功。

分別用GAACOE、ACOE、SGA對該函數(shù)求全局最小值進(jìn)行10次仿真，仿真結(jié)果對比見表2。

圖1是利用GAACOE算法對Rosenbrock（R5）函數(shù)做400次尋優(yōu)，從圖中可以看出，GA和改進(jìn)ACOE算法在110代進(jìn)行了交接，算法利用GA產(chǎn)生的最優(yōu)種群和一部分隨機(jī)產(chǎn)生的種群，構(gòu)成ACOE算法的初始解存儲器，利用加入局部細(xì)搜策略的ACOE算法進(jìn)行余下迭代。ACOE算法利用GA提供的豐富初始種群信息，迅速獲得Rosenbrock（R5）的最優(yōu)解，加入的局部細(xì)搜策略使迭代速度更快。

為比較算法優(yōu)劣，利用GAACOE、ACOE、SGA方法分別對Rosenbrock（R5）函數(shù)做10次試驗(yàn)，每次仍然迭代400次，圖2是利用3種方法獲得的平均性能曲線。由圖2可知，遺傳算法產(chǎn)生的初始解非常豐富，平均值并不低，但是當(dāng)采用擴(kuò)展蟻群算法進(jìn)行迭代后，豐富的初始解產(chǎn)生作用，ACOE很快收斂到最優(yōu)解，說明初始信息素積累的重要性。表明，經(jīng)過遺傳算法確定初始種群后的改進(jìn)擴(kuò)展蟻群算法方向明確，收斂速度快，而且搜索全局最優(yōu)解的能力很強(qiáng)。

表2 函數(shù)極值問題優(yōu)化結(jié)果(10次試驗(yàn))Table 2 Optimization results of function extremum(10 experiments)

圖1 最優(yōu)解曲線Fig.1 Optimal solution curve

當(dāng)決策變量數(shù)量更多時，取N=10，即Rosenbrock（R10）函數(shù)，運(yùn)行ACOE算法10次，每次迭代1 000次，最優(yōu)解│f1（x）│≤0.02的次數(shù)為0次，迭代2 000次，獲得最優(yōu)解的次數(shù)是3次；運(yùn)行GAACOE算法迭代1 000次，運(yùn)行算法10次，獲得最優(yōu)解的次數(shù)是8次，說明GAACOE算法對于求解維數(shù)較多的連續(xù)函數(shù)具有較強(qiáng)的尋優(yōu)能力。

圖2 平均適應(yīng)度曲線Fig.2 Average fitness curve

3 馬斯京根模型參數(shù)優(yōu)化

3.1 馬斯京根模型介紹

河道洪水演算包括水力學(xué)和水文學(xué)兩類方法。水力學(xué)方法以圣維南方程組的求解為基礎(chǔ)，適用于有準(zhǔn)確河道地形和河床觀測數(shù)據(jù)的河段，當(dāng)這些資料條件缺乏時，水文學(xué)方法就成為洪水演算的另一種重要方法。在水文學(xué)中，馬斯京根（Muskingum）法是河道洪水演算的一種重要方法。馬斯京根法由Mc.Carthy提出，并在美國馬斯京根河上首先應(yīng)用，馬斯京根法依據(jù)的基本原理為水量平衡方程和槽蓄方程[8-11]，基本方程為：

式中，W為河段的槽蓄量，t為時間，I和Q分別為河段的入流量、出流量，Q為儲流量，x和K分別為流量比重因子和槽蓄系數(shù)。將上式的微分方程離散化后得到離散的差分形式為：

式中，Q（i）和Q（i）分別為第i個演算時段的演算出流量和實(shí)測出流量，I（i）為第i個演算時段的入流量，n為演算時段個數(shù)，c0，c1和c2為流量演算系數(shù)，且滿足c0+c1+c2=1。顯然，使用馬斯京根模型的一個重要問題是模型參數(shù)c0，c1和c2的估計，并且該最優(yōu)估計問題是一個非線性的參數(shù)優(yōu)化問題。

3.2 馬斯京根模型參數(shù)優(yōu)化對比

本文選用與文獻(xiàn)[8-11]相同的適應(yīng)度函數(shù)，并采用相同的實(shí)例，進(jìn)行比較。

3.2.1 優(yōu)化的適應(yīng)度函數(shù)

優(yōu)化模型：

優(yōu)化的適應(yīng)度函數(shù)：

上式中，h（1-c0-c1）為懲罰項(xiàng)，當(dāng)約束條件1-c0-c1∈（0，1）滿足時其取值為0，否則取值為106。

3.2.2 應(yīng)用實(shí)例

以文獻(xiàn)[13]中的例2南運(yùn)河稱鉤灣至臨清段河段1960年8月的一次洪水過程資料為例，該河段長83.8 km，中間無支流匯入，兩岸有大堤控制，在輸水時沿岸有堤水灌溉，較大降雨時有澇水排入，但對洪水的影響很小，演算時段取12 h。

GAACOE初始參數(shù)選擇：螞蟻數(shù)目m=70，解存儲器容量K=45，參數(shù)ξ=1，q=0.0001，轉(zhuǎn)角步長初值θ0=0.05π，變異概率pm=0.05。限定步數(shù)仍為Max=500。重復(fù)運(yùn)行10次。

將優(yōu)化結(jié)果與文獻(xiàn)[8-11]中的改進(jìn)粒子群算法（APSO）、免疫粒子群算法（IPSO）、蟻群算法（ACO）進(jìn)行對比，結(jié)果見表3。

從表3中所列的各項(xiàng)指標(biāo)看，遺傳擴(kuò)展蟻群算法（GAACOE）演算流量的平均絕對誤差和平均相對誤差都較其他算法有大幅度減少。由此可見，使用遺傳擴(kuò)展蟻群算法對馬斯京根模型參數(shù)進(jìn)行優(yōu)化的精度很高。

表3 馬斯京根模型各參數(shù)估計方法的結(jié)果比較（1960年）Table 3 Parameters of Muskingum model by using different methods(1960 year)

根據(jù)1960年的洪水分析得到三組流量演算系數(shù)對1961年稱鉤灣的入流過程進(jìn)行演算，將文獻(xiàn)[8-11]的方法改進(jìn)粒子群算法（APSO）、蟻群算法（ACO）、多智能體遺傳算法（MAGA）和本文方法的計算結(jié)果列于表4。從表4中所列的各項(xiàng)評價指標(biāo)來看，本文方法比其他算法具有更好的優(yōu)化性能，求得的適應(yīng)度函數(shù)值、平均絕對誤差和平均相對誤差等評價指標(biāo)均小于其他算法。

由表3、4可見，改進(jìn)遺傳擴(kuò)展蟻群算法就演算出流量過程與實(shí)測出流量過程的擬合綜合效果而言，本文算法的求解結(jié)果明顯優(yōu)于改進(jìn)粒子群算法（APSO）、免疫粒子群算法（IPSO）、蟻群算法（ACO）、多智能體遺傳算法（MAGA）等優(yōu)化方法，可應(yīng)用于各種自然災(zāi)害模型的優(yōu)化問題。

表4 南運(yùn)河稱鉤灣至臨清段河段各參數(shù)估計方法的流量演算結(jié)果比較（1961年）Table 4 Flow routing results of the Nanyunhe River by using different methods(1961 year)

4 討論與結(jié)論

本文結(jié)合遺傳算法和擴(kuò)展蟻群算法優(yōu)點(diǎn)，提出新的改進(jìn)遺傳擴(kuò)展蟻群算法（GAACOE）。遺傳擴(kuò)展蟻群算法使用遺傳算法產(chǎn)生初始解，避免解單一性。本文針對擴(kuò)展蟻群算法僅通過解存儲器中解的目標(biāo)函數(shù)值大小構(gòu)建信息素的不足，根據(jù)解重要性給出解存儲器中每個解權(quán)值以增加解方向性，使算法能快速獲得最優(yōu)解，并在每次迭代中加入變尺度局部細(xì)搜策略，能夠快速有效地跳出局部最優(yōu)解。

本研究結(jié)果表明，GAACOE算法在收斂速度和收斂精度上均優(yōu)于ACOE、SGA算法。本文將這種算法應(yīng)用于洪水演算馬斯京根參數(shù)估計最優(yōu)化問題。設(shè)計非參數(shù)優(yōu)化估計模型，利用擴(kuò)展蟻群優(yōu)化尋優(yōu)，演算出流量過程與實(shí)測出流量過程的擬合程度為優(yōu)化準(zhǔn)則，使演算流量接近實(shí)際。

[1]Socha K,Dorigo M.Ant colony optimization for continuous domains[J].European Journal of Operational Research,2008,185 (3):1155-1173.

[2]李士勇,柏繼云.連續(xù)函數(shù)尋優(yōu)的改進(jìn)量子擴(kuò)展蟻群算法[J].哈爾濱工程大學(xué)學(xué)報,2012,33(1):80-84.

[3]Holland J H.Adaptation in natural and artificial systems[M].Ann Arbor:University of Michigan Press,1992.

[4]芮孝芳.Muskingum法及其分段連續(xù)演算的若干理論探討[J].水科學(xué)進(jìn)展,2002,13(6):682-688.

[5]王光生,寧方貴,肖飛.實(shí)用水文預(yù)報方法[M].北京:中國水利水電出版社,2008.

[6]長江水利委員會主編.水文預(yù)報方法[M].北京:水利電力出版社, 1993.

[7]翟國靜.馬斯京根模型參數(shù)估計方法探討[J].水文,1997(3):40-43.

[8]李明明,李承軍,張銘.改進(jìn)PSO法在馬斯京根模型參數(shù)估計中的應(yīng)用[J].人民長江,2008,39(3):60-62.

[9]甘麗云,付強(qiáng),孫穎娜,等.基于免疫粒子群算法的馬斯京根模型參數(shù)識別[J].水文,2010,30(3):43-46.

[10]魯帆,蔣云鐘,王浩,等.多智能體遺傳算法用于馬斯京根模型參數(shù)估計[J].水利學(xué)報,2007,38(3):289-294.

[11]詹士昌,徐婕.蟻群算法在馬斯京根模型參數(shù)估計中的應(yīng)用[J].自然災(zāi)害學(xué)報,2005,14(5):20-24.

[12]王曉紅.蟻群算法與遺傳算法結(jié)合使用方法論[J].中國水運(yùn), 2008,8(8):131-132.

[13]翟國靜.馬斯京根流量演進(jìn)系數(shù)的直接優(yōu)選法[J].河北工程技術(shù)高等?？茖W(xué)校學(xué)報,1996(2):6-11.儀器儀表學(xué)報,2005:1135-1139.

Genetic extended ant colony algorithm for parameter estimation of Muskingum routing model

ZHAO Hongjie1,BAI Jiyun1,MA Li2(1.School of Science, Northeast Agricultural University,Harbin 150030,China;2.School of Engineering,Northeast Agricultural University,Harbin 150030,China)

According to extended ant colony algorithm converging slowly and easily falling into local optimum,it presented some improved strategies:introduced genetic algorithm to produce the initial solution and join the local fine search strategy to avoid ants in local optimum and the weight of each solution improved by its'importance of the memory to get the optimal solution quickly and increase the direction.This paper used the improved algorithm to solve flood routing problem by parameter estimation of Muskingum routing model，by comparison with the existing parameter estimation of Muskingum routing method,validated algorithm has better optimize performance,and provide a more effective way to accurately estimating the parameters of Muskingum routing model.

genetic algorithm;extended ant colony algorithm;optimization of continuous space; Muskingum routing model;parameter estimation

TP18

A

1005-9369（2014）08-0118-06

2013-04-24

黑龍江省青年科學(xué)基金（QC2011C045）

趙紅杰（1977-），女，講師，碩士，研究方向?yàn)閼?yīng)用數(shù)學(xué)。E-mail:zhaohongjie77@163.com

時間2014-7-18 15:02:04[URL]http://www.cnki.net/kcms/detail/23.1391.S.20140718.1502.009.html

趙紅杰,柏繼云,馬力.遺傳擴(kuò)展蟻群算法用于馬斯京根模型參數(shù)估計[J].東北農(nóng)業(yè)大學(xué)學(xué)報,2014,45(8):118-123.

Zhao Hongjie,Bai Jiyun,Ma Li.Genetic extended ant colony algorithm for parameter estimation of Muskingum routing model[J].Journal of Northeast Agricultural University,2014,45(8):118-123.(in Chinese with English abstract)