非線性最小二乘估計的蟻群遺傳融合算法

陳 偉

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

0 引言

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

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

1 非線性最小二乘估計的目標函數

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

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

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

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

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

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

2 蟻群遺傳混合算法設計

2.1 遺傳算法簡介

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

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

2.2 蟻群算法簡介

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

2.3 混合算法設計

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

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

1)參數的初始化。確定種群規模G，設定交叉概率Pc、變異概率Pm等參數，隨機產生初始種群。

2)定義目標函數和適應度函數，計算每一個體的適應度fi，對種群中的個體執行以下遺傳操作，產生下一代個體:

a.選擇操作。

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

b.交叉操作。

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

c.變異操作。

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

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

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

4)當遺傳算法按照規則執行結束后，選擇適應能力強的個體放入新集合S中，作為優化解的集合。

5)根據優化解生成吸引強度初始分布，按蟻群算法信息素初值設置策略，計算信息素初值。初始化蟻群算法控制參數，設置蟻群算法結束條件，設置最大循環次數nc。

a.初始信息素設置。

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

b.信息素更新規則。

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

c.轉移概率設置。

螞蟻k在t時刻從當前節點i轉移到節點j的轉移概率定義如下:

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

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

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

8)更新全局信息素，更新全局最優解。

9)判斷流程是否結束，若當前進化代數不大于nc，轉6)，否則輸出最優解。

3 應用實例

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

表1 Li的真值和相應的觀測值

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

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

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

4 結語

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

[1] 王新洲.非線性模型參數估計理論與應用[M].武漢:武漢大學出版社，2002:29-31.

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

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

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