陳 偉

(武漢科技大學(xué)城市建設(shè)學(xué)院，湖北 武漢 430070)

0 引言

近年來，現(xiàn)代智能優(yōu)化算法，因其高效的優(yōu)化性能、無需特殊新問題等優(yōu)點，受到各領(lǐng)域的廣泛關(guān)注和應(yīng)用。諸如神經(jīng)網(wǎng)絡(luò)、遺傳算法、蟻群算法、模擬退火、禁忌搜索、粒子群優(yōu)化算法等。這些算法大大豐富了現(xiàn)代優(yōu)化技術(shù)，也為具有非線性、多極值等特點的復(fù)雜函數(shù)及組合優(yōu)化問題提供了切實可行的解決方法，但是每一種算法都有其自身的優(yōu)勢和缺陷，如何優(yōu)勢互補融合各類智能算法已成為研究重點。

遺傳算法(Genetic Algorithm)是模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法。蟻群算法(Ant Colony Algorithm)是一種源于大自然生物世界的新型仿生類算法，20世紀90年代初由意大利學(xué)者Dorigo依照螞蟻覓食原理設(shè)計而成的一種群體智能算法。由于該算法具有與其他算法比較易于結(jié)合等特點，諸多的改進算法被研究者提出以改善其本身的性能，與遺傳算法結(jié)合是目前較流行的改進方法之一。本文利用遺傳算法與蟻群算法的優(yōu)勢互補，將基于蟻群算法的混合遺傳算法用于非線性最小二乘估計中。

1 非線性最小二乘估計的目標函數(shù)

由文獻[1]知測量數(shù)據(jù)處理中的非線性模型，可用數(shù)學(xué)公式表示為:

其中，f(X)為未知參數(shù)向量X的函數(shù)，f(X)=(f1(X)，f2(X)，…，fn(X))T;L為n×1的觀測向量;X為t×1的未知參數(shù)向量;Δ為n×1的觀測誤差向量。

非線性模型式(1)相應(yīng)的誤差方程可寫為:

設(shè)觀測值的權(quán)矩陣為n×n的對稱正定矩陣P，則式(1)的非線性最小二乘估計問題可轉(zhuǎn)化為:

由于LTPL為一常量，所以式(3)等價于:

式(4)即為非線性最小二乘估計的目標函數(shù)。

2 蟻群遺傳混合算法設(shè)計

2.1 遺傳算法簡介

遺傳算法(Genetic Algorithm)最初是由美國的J.Holland教授于1975年受生物進化論的啟發(fā)提出的，它是模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法。在遺傳算法中，將代表問題的解用染色體編碼，種群為若干染色體的集合，代表問題解空間中若干解的集合，適應(yīng)度為染色體的評價值，代表對解質(zhì)量優(yōu)劣的評價標準。在初始種群產(chǎn)生后，按照適者生存，優(yōu)勝劣汰的原理，在每一代選擇性能優(yōu)異的個體，對其使用交叉、變異算子，產(chǎn)生出新的種群，如此不停迭代，最終尋找到最佳適應(yīng)環(huán)境的個體;最后，將染色體解碼，即可得到問題的最優(yōu)解。

標準的遺傳算法一般由以下幾部分組成:參數(shù)編碼、初始種群的設(shè)定、適應(yīng)度函數(shù)的設(shè)計、遺傳算子(選擇、交叉、變異)的設(shè)計以及控制參數(shù)設(shè)定等。

2.2 蟻群算法簡介

蟻群算法(Ant Colony Algorithm)是一種模擬蟻群覓食行為，采用信息素指引螞蟻前進時方向，并利用正反饋機制進行搜索的計算智能算法。算法由許多螞蟻共同完成，每只螞蟻在候選解的空間獨立搜索解，在所尋得的解上留下一定的信息素，并且感知其他螞蟻釋放的信息素，傾向于選擇信息素濃度較高的節(jié)點。大量螞蟻的集體行為表現(xiàn)出一種信息正反饋現(xiàn)象:某一節(jié)點上走過的螞蟻越多，后者選擇此節(jié)點的概率越大。

2.3 混合算法設(shè)計

為了克服兩種算法各自的缺陷，形成優(yōu)勢互補。蟻群遺傳融合算法的基本思路是將遺傳算法引入到蟻群算法的初始信息素設(shè)置中，首先利用遺傳算法的快速性、隨機性、全局收斂性，產(chǎn)生有關(guān)問題的初始信息素分布，從而彌補了蟻群算法初期信息素匱乏導(dǎo)致搜索初期信息素積累時間較長的缺陷，加快了求解速度。接著采用蟻群算法，充分利用蟻群算法的并行性、正反饋機制、求解效率高等優(yōu)點進行求解。該混合算法的關(guān)鍵是保證遺傳算法和蟻群算法在最佳時機融合。本文采用的方法是:設(shè)置遺傳算法的最小迭代次數(shù)nmin和最大迭代次數(shù)nmax，在遺傳算法迭代過程中比較個體適應(yīng)度值的變化，如果個體的適應(yīng)度值變化較小，則說明此時遺傳算法優(yōu)化速度已較低，此時可終止遺傳算法過程，進入蟻群算法。

非線性最小二乘估計的蟻群遺傳混合算法設(shè)計步驟如下:

1)參數(shù)的初始化。確定種群規(guī)模G，設(shè)定交叉概率Pc、變異概率Pm等參數(shù)，隨機產(chǎn)生初始種群。

2)定義目標函數(shù)和適應(yīng)度函數(shù)，計算每一個體的適應(yīng)度fi，對種群中的個體執(zhí)行以下遺傳操作，產(chǎn)生下一代個體:

a.選擇操作。

選擇算子采用輪盤賭選擇方法，個體適應(yīng)度越大，其被選中的概率就越高，反之亦然。若群體規(guī)模為G，按計算出群體中各個個體選擇概率后，就可以決定哪些個體被選出。

b.交叉操作。

本文采用實數(shù)編碼，交叉操作采用算術(shù)交叉算子，首先隨機確認參與交叉的父代，并且進行兩兩配對，父代中的個體X和Y按照式(5)產(chǎn)生兩個新的個體:

c.變異操作。

采用均勻變異算子。個體Xi的各基因位以變異概率Pm發(fā)生變異，即按概率Pm用區(qū)間[Xmin，Xmax]中均勻分布的隨機數(shù)代替原有值。

3)反復(fù)執(zhí)行第2)步操作，直至滿足遺傳算法結(jié)束條件。設(shè)置最小迭代次數(shù)nmin和最大迭代次數(shù)nmax，在遺傳算法的迭代過程中同時統(tǒng)計進化率，其公式為:

在設(shè)定的迭代次數(shù)范圍內(nèi)，若連續(xù)三次進化率都小于最小進化率時，則停止遺傳算法迭代過程，進入蟻群算法。

4)當遺傳算法按照規(guī)則執(zhí)行結(jié)束后，選擇適應(yīng)能力強的個體放入新集合S中，作為優(yōu)化解的集合。

5)根據(jù)優(yōu)化解生成吸引強度初始分布，按蟻群算法信息素初值設(shè)置策略，計算信息素初值。初始化蟻群算法控制參數(shù)，設(shè)置蟻群算法結(jié)束條件，設(shè)置最大循環(huán)次數(shù)nc。

a.初始信息素設(shè)置。

本文采用比利時學(xué)者Thomas提出來的最大最小螞蟻系統(tǒng)(MMAS)中的方法。信息素的初值設(shè)為 τS=τC+τG，其中，τC為根據(jù)具體求解問題給定的吸引強度常數(shù);τG為遺傳算法求解結(jié)果轉(zhuǎn)換的吸引強度。

b.信息素更新規(guī)則。

τij(t)表示t時刻在路徑ij上殘留的信息量，用參數(shù)ρ表示信息素蒸發(fā)率，螞蟻完成一次循環(huán)后各路徑上的信息量更新規(guī)則為:τij(t+1) = (1 － ρ) τij(t) + Δτij(t); Δτij(t)=其中，Q為常數(shù);Lmax為當前搜索的最長路徑的集合;E為當前最短路徑上的路徑集合。

c.轉(zhuǎn)移概率設(shè)置。

螞蟻k在t時刻從當前節(jié)點i轉(zhuǎn)移到節(jié)點j的轉(zhuǎn)移概率定義如下:

其中，ηij為邊路徑(i，j)的能見度，一般取為1/dij;路徑能見度的相對重要性為β(β≥0);路徑軌跡的相對重要性為α(α≥0);allowed是第k只螞蟻下一步可以選擇的路徑集。

6)將m只螞蟻置于各自的初始節(jié)點，計算每只螞蟻的轉(zhuǎn)移概率Pij，根據(jù)轉(zhuǎn)移概率移動每只螞蟻到下一個節(jié)點，并進行信息素局部更新。

7)判斷所有螞蟻是否已形成完整路徑，如還沒有形成完整路徑則轉(zhuǎn)6)，否則，執(zhí)行8)。

8)更新全局信息素，更新全局最優(yōu)解。

9)判斷流程是否結(jié)束，若當前進化代數(shù)不大于nc，轉(zhuǎn)6)，否則輸出最優(yōu)解。

3 應(yīng)用實例

本例取自參考文獻[1]例2-1-1。已知非線性模型為Li=x1eix2，其中參數(shù)x1和x2的真值為 X=(5.420 136 187，－0.254 361 89)T。Li的5個真值(用參數(shù)的真值X算得)和相應(yīng)的5個同精度獨立觀測值見表1。觀測值的中誤差σ0=±0.007 833。

表1 Li的真值和相應(yīng)的觀測值

觀測方程為:Li=x1eix2+Δi(i=1，2，3，4，5)。

根據(jù)式(4)可知本例的目標函數(shù)為:

按照本文非線性最小二乘估計的蟻群遺傳混合算法的思想和步驟編程實現(xiàn)本例的參數(shù)估計，其結(jié)果為:X=(5.422 735 546，－0.255 670 691)T，‖ΔX‖ =0.002 910 147。從計算結(jié)果可看出，用蟻群遺傳混合算法計算出來的結(jié)果與真值相差很小。

4 結(jié)語

本文嘗試將遺傳算法和蟻群算法進行有效融合，并將該混合算法用于非線性的參數(shù)估計中。該混合算法利用遺傳算法和蟻群算法的優(yōu)勢互補，使求解過程盡量避免了陷入局部最優(yōu)同時提高了搜索效率，對解決非線性參數(shù)估計問題有一定的應(yīng)用價值，值得進一步研究。

[1] 王新洲.非線性模型參數(shù)估計理論與應(yīng)用[M].武漢:武漢大學(xué)出版社，2002:29-31.

[2] 申利民，高 潔.基于遺傳蟻群融合算法的測試用例最小化研究[J].計算機工程，2012，38(16):57-64.

[3] 曹騰飛，符云清，鐘明洋.融合遺傳蟻群算法的Web服務(wù)組合研究[J].計算機系統(tǒng)應(yīng)用，2012，21(6):81-85.

[4] 陳 偉，張從海.混合模擬退火——遺傳算法在參數(shù)估計中的應(yīng)用[J].地理空間信息，2007，5(2):99-101.