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

陳 偉

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

0 引言

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

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

1 非線性最小二乘估計(jì)的目標(biāo)函數(shù)

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

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

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

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

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

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

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

2.1 遺傳算法簡(jiǎn)介

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

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

2.2 蟻群算法簡(jiǎn)介

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

2.3 混合算法設(shè)計(jì)

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

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

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

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

a.選擇操作。

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

b.交叉操作。

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

c.變異操作。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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

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

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

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

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