田勁松,田勁杰

(1.安徽農(nóng)業(yè)大學(xué)理學(xué)院,安徽合肥 230036； 2.杭州市拱墅區(qū)基礎(chǔ)設(shè)施建設(shè)中心,浙江杭州 310000)

基于人工魚群算法的測(cè)量平差參數(shù)估計(jì)

田勁松1?,田勁杰2

(1.安徽農(nóng)業(yè)大學(xué)理學(xué)院,安徽合肥 230036； 2.杭州市拱墅區(qū)基礎(chǔ)設(shè)施建設(shè)中心,浙江杭州 310000)

介紹人工魚群算法原理和算法設(shè)計(jì)的相關(guān)技術(shù)問題。把人工魚群算法應(yīng)用到測(cè)量平差中，解決平差過程中遇到的法方程系數(shù)陣秩虧、病態(tài)方程等問題。給出了在測(cè)量平差參數(shù)估計(jì)中利用人工魚群算法，不對(duì)法方程求逆的情況下，

人工魚群算法；測(cè)量平差；參數(shù)估計(jì)；目標(biāo)函數(shù)；參數(shù)范圍

1 引 言

在測(cè)量數(shù)據(jù)平差處理中,一個(gè)實(shí)際平差問題,都要選擇建立某種函數(shù)模型,函數(shù)模型是描述觀測(cè)量與未知量之間的數(shù)學(xué)關(guān)系的模型,是客觀實(shí)際的本質(zhì)或特征的模型,數(shù)據(jù)平差的目的就是為了最優(yōu)估計(jì)函數(shù)模型的未知量[1]。經(jīng)典平差中常用的函數(shù)模型有條件平差模型、間接平差模型等,這些函數(shù)模型的平差準(zhǔn)則均為VTPV=min,在最小二乘原理要求下計(jì)算函數(shù)極值問題,共同的特點(diǎn)是對(duì)法方程系數(shù)進(jìn)行求逆,在此過程中會(huì)遇到一些問題:

(1)若法方程系數(shù)陣不是滿秩,無法解算法方程；

(2)法方程系數(shù)陣較大且條件數(shù)很大造成法方程是病態(tài)方程。間接平差時(shí)要選取參數(shù)的近似值,但近似值選取要與真值很接近才能利用最小二乘原理直接取泰勒展開式中的一次項(xiàng)并改換成線性模型[2]。

本文通過研究人工魚群算法,求解測(cè)量平差中的參數(shù)。人工魚群算法屬于求解非線性最小二乘問題算法中的搜索算法[3]。與遺傳算法、蟻群算法等算法類似,關(guān)鍵問題是如何確定有效的參數(shù)搜索范圍。人工魚群算法具有強(qiáng)魯棒性、全局收斂性好的特點(diǎn),在尋優(yōu)的過程中跟蹤記錄個(gè)體的狀態(tài),進(jìn)行分布處理,參數(shù)和初值具有很強(qiáng)的魯棒性。把人工魚群算法應(yīng)用到測(cè)量平差中,解決平差過程中遇到的法方程系數(shù)陣秩虧、病態(tài)方程等問題。直接利用目標(biāo)函數(shù)尋優(yōu)法求解誤差方程參數(shù),從而避免了法方程系數(shù)求逆,使秩虧方程和病態(tài)方程問題的求解有了最優(yōu)結(jié)果。通過實(shí)例模擬計(jì)算并與其他方法比較,證明該方法在最小二乘平差計(jì)算中是可行的和有效的,克服了線性化經(jīng)典平差的不足。

2 人工魚群算法簡(jiǎn)述

2.1 算法原理[3～5]

假設(shè)一條虛擬的人工魚實(shí)體當(dāng)前的位置為X,它的感知范圍為Visual,在某時(shí)刻視點(diǎn)所在位置為Xv,如果該位置的食物濃度高于當(dāng)前位置,則考慮向該位置方向前進(jìn)一步,即達(dá)到位置Xnext；如果位置Xv不比當(dāng)前位置食物濃度更高,則繼續(xù)巡視視野內(nèi)的其他位置。巡視的次數(shù)越多,則對(duì)視野中的狀態(tài)了解的越全面,從而對(duì)周圍的環(huán)境有一個(gè)全方位立體的認(rèn)識(shí),有助于做出相應(yīng)的判斷和決策。對(duì)于狀態(tài)多和無限狀態(tài)的環(huán)境也不必全部遍歷,允許一定的不確定性對(duì)于擺脫局部最優(yōu),從而對(duì)尋找全局最優(yōu)有幫助。

假設(shè)位置X=(x1,x2,…,xn),位置Xv=(xv1,xv2,…,xvn),則魚群尋優(yōu)過程可表示為:

式中:i=1,2,…,n,r是[-1,1]區(qū)間的隨機(jī)數(shù)；Step是移動(dòng)步長(zhǎng)；Visual是人工魚感知范圍或距離。

由于環(huán)境中同伴的數(shù)目是有限的,因此在視野中感知同伴的位置,并相應(yīng)調(diào)整自身位置。動(dòng)物學(xué)家研究發(fā)現(xiàn),魚類通常具有以下幾種行為:聚群行為、追尾行為和隨機(jī)行為。魚群算法是利用目標(biāo)函數(shù)來區(qū)別個(gè)體的好壞,使用目標(biāo)問題的函數(shù)值,對(duì)搜索空間有一定的適應(yīng)能力[5]。

算法的實(shí)現(xiàn)涉及10個(gè)主要變量和參數(shù):人工魚數(shù)N,人工魚個(gè)體的狀態(tài)位置Xi,人工魚當(dāng)前所在位置的食物濃度目標(biāo)函數(shù)Yi,個(gè)體之間的距離dij,感知距離Visual,人工魚移動(dòng)最大步長(zhǎng)Step,擁擠度因子δ,覓食最大試探次數(shù)try_number,當(dāng)前覓食行為次數(shù)n和最大迭代數(shù)MAXGEN。

2.2 算法設(shè)計(jì)

(1)魚群初始化設(shè)計(jì)

開始設(shè)定魚群的數(shù)目為N個(gè),目標(biāo)函數(shù)中有t個(gè)待優(yōu)化參數(shù),則要產(chǎn)生t行N列的初始魚群,每列表示一條人工魚的t個(gè)參數(shù)。本文設(shè)計(jì)人工魚數(shù)為N= 100,最大迭代次數(shù)為MAXGEN=200。

(2)覓食行為設(shè)計(jì)

設(shè)人工魚當(dāng)前位置狀態(tài)為Xi,在其感知范圍內(nèi)隨機(jī)選擇一個(gè)狀態(tài)Xj,如果Xi〉Xj,則向該方向前進(jìn)一步；反之,則重新選擇狀態(tài)Xj,判斷是否滿足前進(jìn)條件。這樣反復(fù)嘗試設(shè)定的最大試探次數(shù)后,如果仍不滿足前進(jìn)條件,則隨機(jī)移動(dòng)一步。本文設(shè)定最大覓食試探次數(shù)try_number=100,移動(dòng)步長(zhǎng)為Step=0.3。

(3)聚群行為設(shè)計(jì)

設(shè)人工魚當(dāng)前位置狀態(tài)為Xi,探索當(dāng)前領(lǐng)域內(nèi)(即dij〈Visual)的伙伴數(shù)目nf及中心位置Xc,如果Yc/nf〉δ×Yi(δ為擁擠度因子),表明伙伴中心有較多的食物并且不太擁擠,則朝伙伴中心的位置方向前進(jìn)一步；否則執(zhí)行覓食行為。本文設(shè)計(jì)擁擠度因子δ為0.618。

(4)追尾行為設(shè)計(jì)

設(shè)人工魚當(dāng)前位置狀態(tài)為Xi,探索當(dāng)前領(lǐng)域內(nèi)(即dij〈Visual)的伙伴數(shù)目nf及伙伴中食物濃度Yi最大的伙伴Xj,如果Yj/nf〉δYi(δ為擁擠度因子),表明伙伴Xj的狀態(tài)具有較高的食物濃度并且周圍不太擁擠,則朝著伙伴Xj的方向前進(jìn)一步,否則執(zhí)行覓食行為。

(5)隨機(jī)行為設(shè)計(jì)

在視野中隨機(jī)選擇一個(gè)狀態(tài),然后該方向移動(dòng),它是覓食行為的一個(gè)缺省行為,即人工魚當(dāng)前位置狀態(tài)為Xi的下一個(gè)位置Xinext為:Xinext=Xi+r×Visual。其中, r是[-10,10]區(qū)間的隨機(jī)數(shù)；Visual為感知距離。

3 測(cè)量平差參數(shù)估計(jì)

3.1 函數(shù)模型與目標(biāo)函數(shù)設(shè)計(jì)

通過人工魚最終的分布情況確定最優(yōu)解的分布,隨著尋優(yōu)過程的進(jìn)展,人工魚會(huì)聚集到極值點(diǎn)的周圍,全局最優(yōu)的極值點(diǎn)周圍通常能聚集較多的人工魚[6,7],現(xiàn)把這種思想應(yīng)用到測(cè)量平差參數(shù)估計(jì)中。根據(jù)文獻(xiàn)[1],一般情況下,測(cè)量平差模型中觀測(cè)值真值與參數(shù)真值之間的關(guān)系為:

L=f(X1,X2,…,Xn)=BX+d(3)

式中:f(X1,X2,…,Xn)是由n個(gè)Xi的非線性函數(shù)組成的n×1維向量,L為觀測(cè)值真值。

一般而言,誤差方程組的一般形式為:

方程組中共有t個(gè)變量,n個(gè)誤差方程,其中＾x1,＾x2,…,＾xt是待估計(jì)的未知系統(tǒng)變量。

用矩陣形式表示為:

解方程組,得到法方程為:

式中:Nbb=BTPB,We=BTPW。

在Nbb滿秩的情況下,＾x有唯一解,得到待定參數(shù)解為:

將＾x代入到誤差方程中,即可求得改正數(shù)V,從而求得平差結(jié)果。但是,在很多情況下,Nbb不是滿秩的或者Nbb的條件數(shù)很大,是一個(gè)病態(tài)方程,無法對(duì)法方程系數(shù)Nbb求逆。本文利用人工魚群算法,在不對(duì)法方程N(yùn)bb求逆的情況下,對(duì)誤差方程直接進(jìn)行尋優(yōu)求解。

3.2 相關(guān)符號(hào)定義

根據(jù)誤差方程一般形式,定義相關(guān)符號(hào)如下:

4 算例分析

(1)算例1(注:為了進(jìn)行比較,該算例來源于文獻(xiàn)[8])。已知一個(gè)水準(zhǔn)網(wǎng),如圖1所示,測(cè)得每段高差為:h1=0.023 m,h2=1.114 m,h3=1.142 m,h4= 0.079 m,h5=0.099 m,h6=1.217 m。根據(jù)路線長(zhǎng)度得到每段的權(quán)重為:p1=2,p2=2,p3=2,p4=1,p5=1,p6=1。各點(diǎn)高程的近似值為:X01=100.780 m,X02= 100.099 m,X03=100.000 m,X04=101.216 m。

圖1 水準(zhǔn)網(wǎng)路線圖

在這個(gè)算例中,因?yàn)闆]有已知點(diǎn)高程,導(dǎo)致法方程系數(shù)Nbb秩虧[8],無法直接計(jì)算出結(jié)果,必須要假設(shè)參數(shù)的真值才能得到最終結(jié)果,現(xiàn)在采用人工魚群算法迭代尋優(yōu),無須假設(shè)參數(shù)真值,迭代過程如圖2所示。

人工魚群算法求解誤差方程的結(jié)果如表1所示(感知距離Visual=2.5,移動(dòng)步長(zhǎng)Step=0.3,擁擠度因子δ=0.618,迭代次數(shù)MAXGEN=200,程序執(zhí)行次數(shù)number=5,待定參數(shù)解個(gè)數(shù)=4)。

圖2 迭代過程圖

從圖2中可以看出,采用人工魚群算法尋找目標(biāo)函數(shù)的極大值,整個(gè)尋優(yōu)過程中,當(dāng)?shù)?0代以后,目標(biāo)函數(shù)的極大值保持不變；從0到60代,曲線圖比較陡。說明用本文介紹的方法在平差準(zhǔn)則條件下,目標(biāo)函數(shù)收斂速度很快,尋優(yōu)過程穩(wěn)定性很好。為了檢驗(yàn)算法的穩(wěn)定性,程序共運(yùn)行了5次,得到5組參數(shù)估計(jì)值和目標(biāo)函數(shù)值,每次計(jì)算結(jié)果如表1所示。另外,為了與其他算法計(jì)算結(jié)果進(jìn)行比較,取5組參數(shù)估計(jì)值和目標(biāo)函數(shù)值的平均值作為最終比較對(duì)象。

人工魚群算法計(jì)算結(jié)果 表1

與文獻(xiàn)[8]的計(jì)算結(jié)果比較如表2所示。

參數(shù)估計(jì)結(jié)果比較 表2

從表1和表2可以看出,在相同的起點(diǎn)上進(jìn)行計(jì)算,本文介紹的方法計(jì)算結(jié)果與秩虧自由網(wǎng)平差計(jì)算結(jié)果接近,但精度明顯要比秩虧自由網(wǎng)平差計(jì)算的精度要高,并且不用對(duì)法方程系數(shù)進(jìn)行廣義逆計(jì)算,計(jì)算速度更快。程序共運(yùn)行5次,每次的參數(shù)估計(jì)值計(jì)算結(jié)果相差很小,目標(biāo)函數(shù)值相同,說明人工魚群算法穩(wěn)定性很好

(2)算例2(注:為了進(jìn)行比較,該算例來源于文獻(xiàn)[9])設(shè)病態(tài)方程系數(shù)陣為:

共10個(gè)觀測(cè)值,3個(gè)待定參數(shù)解。按間平差方法進(jìn)行平差,共10個(gè)誤差方程,模擬的權(quán)均為1,參數(shù)真值為X=[10.000 3.000 2.000]T,觀測(cè)值Li、觀測(cè)值與其近似值之差Wi如表3所示。尋優(yōu)時(shí),雖然也能迭代到比較理想的結(jié)果,但是出現(xiàn)尋優(yōu)不穩(wěn)定,目標(biāo)函數(shù)的極大值變化較大的情況。

觀測(cè)值與差值 表3

該方程的法方程系數(shù)的條件數(shù)為2 806,屬于嚴(yán)重病態(tài)問題[9]。

在文獻(xiàn)[9]中,作者分別用遺傳算法、無偏最小二乘估計(jì)法、奇異值分解法和嶺估計(jì)法計(jì)算出了3個(gè)待定參數(shù)的最優(yōu)值。本文用人工魚群算法對(duì)此例進(jìn)行計(jì)算,迭代尋優(yōu)過程如圖3所示。

圖3 迭代過程圖

人工魚群算法計(jì)算結(jié)果 表4

與其他方法計(jì)算結(jié)果比較如表5所示。

參數(shù)估計(jì)結(jié)果比較 表5

從表4和表5計(jì)算結(jié)果分析,人工魚群法計(jì)算結(jié)果與真值接近,并且程序運(yùn)行5次后,每次的改正值計(jì)算結(jié)果相差很小,目標(biāo)函數(shù)值說明人工魚群算法的穩(wěn)定性很好,雖然遺傳算法計(jì)算結(jié)果與真值差別很小,但是穩(wěn)定性較差。由于法方程系數(shù)陣條件數(shù)很大,是嚴(yán)重的病態(tài)方程,用最小二乘法和奇異值分解法計(jì)算的結(jié)果與真值差別較大,

5 結(jié) 語

由以上討論和兩個(gè)算例的結(jié)果可以看出:

(1)算例1是利用人工魚群算法解決測(cè)量平差模型中由于法方程系數(shù)陣秩虧時(shí)尋找出參數(shù)最優(yōu)解的驗(yàn)證實(shí)例,算例2是利用人工魚群算法解決由于法方程系數(shù)陣較大且條件數(shù)很大造成法方程是病態(tài)方程時(shí)尋找到參數(shù)最優(yōu)解的驗(yàn)證實(shí)例。

(2)人工魚群算法完全可以應(yīng)用到測(cè)量平差計(jì)算中。算法直接針對(duì)測(cè)量平差中平差模型的目標(biāo)函數(shù)進(jìn)行優(yōu)化計(jì)算,不管是線性和非線性模型均不需要進(jìn)行復(fù)雜的求導(dǎo)計(jì)算。

(3)上述兩個(gè)實(shí)例模型中,整個(gè)程序設(shè)計(jì)思路相同,僅目標(biāo)函數(shù)形式不同,只需要修改對(duì)應(yīng)的目標(biāo)函數(shù)和參數(shù)個(gè)數(shù),整個(gè)程序即可運(yùn)行,所以人工魚群算法具有對(duì)初值與參數(shù)搜索范圍選擇不敏感、魯棒性強(qiáng)、收斂速度快和使用靈活等特點(diǎn)。

(4)人工魚群算法屬于求解非線性最小二乘問題算法中的搜索算法一類,與遺傳算法、蟻群算法等算法類似,它們的關(guān)鍵問題如何確定有效的參數(shù)搜索范圍,這限制了很多智能算法包括魚群算法的應(yīng)用。怎樣選取優(yōu)化方法(比如可以進(jìn)行分段優(yōu)化或者混合優(yōu)化)、如何確定有效的參數(shù)搜索范圍等問題都是后續(xù)值得研究的問題。

[1] 武漢大學(xué)測(cè)繪學(xué)院測(cè)量平差學(xué)科組.誤差理論與測(cè)量平差基礎(chǔ)[M].武漢：武漢大學(xué)出版社，2003.

[2] 王穗輝.遺傳算法在非線性最小二乘平差中的應(yīng)用[J].大地測(cè)量學(xué)與地球動(dòng)力學(xué)，2006，26(2)：95～98.

[3] 李曉磊.一種新型的智能優(yōu)化方法-人工魚群算法[D].杭州：浙江大學(xué)，2003.

[4] 李曉磊，薛云燦，路飛等.基于人工魚群算法的參數(shù)估計(jì)方法[J].山東大學(xué)學(xué)報(bào)·工學(xué)版，2004，34(3)：84～87.

[5] 李曉磊，路飛，田國(guó)會(huì)等.組合優(yōu)化問題的人工魚群算法應(yīng)用[J].山東大學(xué)學(xué)報(bào)·工學(xué)版，2004，34(5)：64～67.

[6] 史峰，王輝，郁磊等.Matlab智能算法30個(gè)案例分析[M].北京：北京航空航天大學(xué)出版社，2011.

[7] 王冬冬，周永權(quán).人工魚群算法在求解非線性方程組中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用研究，2007，24(6)：242～244.

[8] 卓力格圖，詹潔暉.MATLAB軟件在測(cè)量平差中的應(yīng)用[J].地殼形變與地震，2000，20(3)：75～80.

[9] 曾群意，歐吉坤.用遺傳算法解算病態(tài)方程[J].大地測(cè)量學(xué)與地球動(dòng)力學(xué)，2003，23(8)：93～97.

[10] 屈利娜，任超，許本意等.基于免疫遺傳算法解算GPS病態(tài)方程[J].海洋測(cè)繪，2011，31(5)：9～11.

[11] 張慧，彭志平，李國(guó)勇.粒子群算法在求解非線性方程組中應(yīng)用[J].茂名學(xué)院學(xué)報(bào)，2008，18(3)：74～79.

寧波市測(cè)繪設(shè)計(jì)研究院中標(biāo)海洋災(zāi)害風(fēng)險(xiǎn)及污染調(diào)查項(xiàng)目

(本刊訊)2013年11月13日,寧波市測(cè)繪設(shè)計(jì)研究院中標(biāo)寧波市海洋與漁業(yè)執(zhí)法支隊(duì)海洋災(zāi)害風(fēng)險(xiǎn)及污染調(diào)查項(xiàng)目。

該項(xiàng)目調(diào)查范圍位于寧波市北侖區(qū)。區(qū)內(nèi)的寧波——舟山港已經(jīng)發(fā)展成為國(guó)內(nèi)沿海最大的液體化工儲(chǔ)運(yùn)基地,一批化學(xué)原料、化學(xué)制品制造企業(yè)及原油加工、倉儲(chǔ)(含天然氣)及石油制品制造企業(yè)紛紛落戶寧波沿海,加之風(fēng)暴潮、海嘯、災(zāi)害性海浪等海洋災(zāi)害,給寧波海洋環(huán)境污染風(fēng)險(xiǎn)和防災(zāi)帶來了很大壓力。為此,寧波市海洋與漁業(yè)執(zhí)法支隊(duì)決定通過招標(biāo),進(jìn)行陸源入海排污口普查,污染源監(jiān)測(cè)等工作,收集相關(guān)數(shù)據(jù)資料進(jìn)行對(duì)比分析,建設(shè)專題管理地理信息系統(tǒng),掌握污染物來源及分布狀況,掌握歷年海洋災(zāi)害情況,依法開展海洋環(huán)境治理和保護(hù)。

該院中標(biāo)后將發(fā)揮由本院建設(shè)與維護(hù)的“寧波市現(xiàn)代測(cè)繪基準(zhǔn)體系”技術(shù)優(yōu)勢(shì),實(shí)施調(diào)查區(qū)域的相關(guān)基礎(chǔ)地理信息數(shù)據(jù)采集,并將海堤資料、業(yè)務(wù)資料、電子地圖等圖像數(shù)據(jù)匯集入庫。建立地理信息管理平臺(tái),進(jìn)行數(shù)據(jù)庫的日常入庫分析、維護(hù)和更新。應(yīng)用三維仿真技術(shù),建立基于風(fēng)暴潮經(jīng)驗(yàn)預(yù)報(bào)模型和風(fēng)暴潮數(shù)值預(yù)報(bào)模型,實(shí)現(xiàn)對(duì)風(fēng)暴潮、海嘯的數(shù)值模擬,同時(shí)結(jié)合天文潮位數(shù)據(jù)和長(zhǎng)周期海浪等數(shù)據(jù),建立起風(fēng)暴潮、海嘯漫灘預(yù)報(bào)模型,滿足北侖區(qū)流域?qū)Ｑ鬄?zāi)害的風(fēng)險(xiǎn)評(píng)估和區(qū)劃。

(寧波市測(cè)繪設(shè)計(jì)研究院顧開建供稿)

Adjustment Parameter Estimation Based on Artificial Fish-Swarm Algorithm

Tian Jinsong1,Tian Jinjie2
(1.Anhui Agricultural University,School of Science,Hefei 230036,China；2.Gongshu District Infrastructure Construction Center of Hangzhou city,Hangzhou 310000,China)

The relevant technology of the artificial fish algorithm principle and algorithm design problems are introduced in the paper.The artificial fish algorithm is applied to the measurement adjustment to solve encountered in the process of adjustment of normal equation coefficientmatrix rank,morbid equations and so on.The thought and steps of the error equation directly solving are given in measurement adjustment parameter estimation using artificial fish algorithm,wrongmethod equation under the condition of inversion,optimization was carried out on the error equation directly solving.Through the example simulation,proved that the method in the measurement adjustment calculation is feasible and effective.

artificial fish-swarm algorithm；measuring adjustment；parameter estimation；objective function；range of parameters

1672-8262(2013)06-134-05

P207

A

2013—06—17

田勁松(1975—),男,碩士,講師,研究方向:智能算法與大地測(cè)量數(shù)據(jù)處理。

2013年度安徽高校省級(jí)自然科學(xué)研究項(xiàng)目(KJ2013Z082)；安徽農(nóng)業(yè)大學(xué)2012年教學(xué)研究項(xiàng)目(JY2012064)。

對(duì)誤差方程直接進(jìn)行尋優(yōu)求解的思想和步驟。通過實(shí)例模擬計(jì)算，證明該方法在測(cè)量平差計(jì)算中是可行的和有效的。