基于人工魚群算法的測量平差參數估計

田勁松,田勁杰

(1.安徽農業大學理學院,安徽合肥 230036； 2.杭州市拱墅區基礎設施建設中心,浙江杭州 310000)

基于人工魚群算法的測量平差參數估計

田勁松1?,田勁杰2

(1.安徽農業大學理學院,安徽合肥 230036； 2.杭州市拱墅區基礎設施建設中心,浙江杭州 310000)

介紹人工魚群算法原理和算法設計的相關技術問題。把人工魚群算法應用到測量平差中，解決平差過程中遇到的法方程系數陣秩虧、病態方程等問題。給出了在測量平差參數估計中利用人工魚群算法，不對法方程求逆的情況下，

人工魚群算法；測量平差；參數估計；目標函數；參數范圍

1 引 言

在測量數據平差處理中,一個實際平差問題,都要選擇建立某種函數模型,函數模型是描述觀測量與未知量之間的數學關系的模型,是客觀實際的本質或特征的模型,數據平差的目的就是為了最優估計函數模型的未知量[1]。經典平差中常用的函數模型有條件平差模型、間接平差模型等,這些函數模型的平差準則均為VTPV=min,在最小二乘原理要求下計算函數極值問題,共同的特點是對法方程系數進行求逆,在此過程中會遇到一些問題:

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

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

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

2 人工魚群算法簡述

2.1 算法原理[3～5]

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

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

式中:i=1,2,…,n,r是[-1,1]區間的隨機數；Step是移動步長；Visual是人工魚感知范圍或距離。

由于環境中同伴的數目是有限的,因此在視野中感知同伴的位置,并相應調整自身位置。動物學家研究發現,魚類通常具有以下幾種行為:聚群行為、追尾行為和隨機行為。魚群算法是利用目標函數來區別個體的好壞,使用目標問題的函數值,對搜索空間有一定的適應能力[5]。

算法的實現涉及10個主要變量和參數:人工魚數N,人工魚個體的狀態位置Xi,人工魚當前所在位置的食物濃度目標函數Yi,個體之間的距離dij,感知距離Visual,人工魚移動最大步長Step,擁擠度因子δ,覓食最大試探次數try_number,當前覓食行為次數n和最大迭代數MAXGEN。

2.2 算法設計

(1)魚群初始化設計

開始設定魚群的數目為N個,目標函數中有t個待優化參數,則要產生t行N列的初始魚群,每列表示一條人工魚的t個參數。本文設計人工魚數為N= 100,最大迭代次數為MAXGEN=200。

(2)覓食行為設計

設人工魚當前位置狀態為Xi,在其感知范圍內隨機選擇一個狀態Xj,如果Xi〉Xj,則向該方向前進一步；反之,則重新選擇狀態Xj,判斷是否滿足前進條件。這樣反復嘗試設定的最大試探次數后,如果仍不滿足前進條件,則隨機移動一步。本文設定最大覓食試探次數try_number=100,移動步長為Step=0.3。

(3)聚群行為設計

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

(4)追尾行為設計

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

(5)隨機行為設計

在視野中隨機選擇一個狀態,然后該方向移動,它是覓食行為的一個缺省行為,即人工魚當前位置狀態為Xi的下一個位置Xinext為:Xinext=Xi+r×Visual。其中, r是[-10,10]區間的隨機數；Visual為感知距離。

3 測量平差參數估計

3.1 函數模型與目標函數設計

通過人工魚最終的分布情況確定最優解的分布,隨著尋優過程的進展,人工魚會聚集到極值點的周圍,全局最優的極值點周圍通常能聚集較多的人工魚[6,7],現把這種思想應用到測量平差參數估計中。根據文獻[1],一般情況下,測量平差模型中觀測值真值與參數真值之間的關系為:

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

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

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

方程組中共有t個變量,n個誤差方程,其中＾x1,＾x2,…,＾xt是待估計的未知系統變量。

用矩陣形式表示為:

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

式中:Nbb=BTPB,We=BTPW。

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

將＾x代入到誤差方程中,即可求得改正數V,從而求得平差結果。但是,在很多情況下,Nbb不是滿秩的或者Nbb的條件數很大,是一個病態方程,無法對法方程系數Nbb求逆。本文利用人工魚群算法,在不對法方程Nbb求逆的情況下,對誤差方程直接進行尋優求解。

3.2 相關符號定義

根據誤差方程一般形式,定義相關符號如下:

4 算例分析

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

圖1 水準網路線圖

在這個算例中,因為沒有已知點高程,導致法方程系數Nbb秩虧[8],無法直接計算出結果,必須要假設參數的真值才能得到最終結果,現在采用人工魚群算法迭代尋優,無須假設參數真值,迭代過程如圖2所示。

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

圖2 迭代過程圖

從圖2中可以看出,采用人工魚群算法尋找目標函數的極大值,整個尋優過程中,當迭代到60代以后,目標函數的極大值保持不變；從0到60代,曲線圖比較陡。說明用本文介紹的方法在平差準則條件下,目標函數收斂速度很快,尋優過程穩定性很好。為了檢驗算法的穩定性,程序共運行了5次,得到5組參數估計值和目標函數值,每次計算結果如表1所示。另外,為了與其他算法計算結果進行比較,取5組參數估計值和目標函數值的平均值作為最終比較對象。

人工魚群算法計算結果 表1

與文獻[8]的計算結果比較如表2所示。

參數估計結果比較 表2

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

(2)算例2(注:為了進行比較,該算例來源于文獻[9])設病態方程系數陣為:

共10個觀測值,3個待定參數解。按間平差方法進行平差,共10個誤差方程,模擬的權均為1,參數真值為X=[10.000 3.000 2.000]T,觀測值Li、觀測值與其近似值之差Wi如表3所示。尋優時,雖然也能迭代到比較理想的結果,但是出現尋優不穩定,目標函數的極大值變化較大的情況。

觀測值與差值 表3

該方程的法方程系數的條件數為2 806,屬于嚴重病態問題[9]。

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

圖3 迭代過程圖

人工魚群算法計算結果 表4

與其他方法計算結果比較如表5所示。

參數估計結果比較 表5

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

5 結 語

由以上討論和兩個算例的結果可以看出:

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

(2)人工魚群算法完全可以應用到測量平差計算中。算法直接針對測量平差中平差模型的目標函數進行優化計算,不管是線性和非線性模型均不需要進行復雜的求導計算。

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

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

[1] 武漢大學測繪學院測量平差學科組.誤差理論與測量平差基礎[M].武漢：武漢大學出版社，2003.

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

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

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

[5] 李曉磊，路飛，田國會等.組合優化問題的人工魚群算法應用[J].山東大學學報·工學版，2004，34(5)：64～67.

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

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

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

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

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

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

寧波市測繪設計研究院中標海洋災害風險及污染調查項目

(本刊訊)2013年11月13日,寧波市測繪設計研究院中標寧波市海洋與漁業執法支隊海洋災害風險及污染調查項目。

該項目調查范圍位于寧波市北侖區。區內的寧波——舟山港已經發展成為國內沿海最大的液體化工儲運基地,一批化學原料、化學制品制造企業及原油加工、倉儲(含天然氣)及石油制品制造企業紛紛落戶寧波沿海,加之風暴潮、海嘯、災害性海浪等海洋災害,給寧波海洋環境污染風險和防災帶來了很大壓力。為此,寧波市海洋與漁業執法支隊決定通過招標,進行陸源入海排污口普查,污染源監測等工作,收集相關數據資料進行對比分析,建設專題管理地理信息系統,掌握污染物來源及分布狀況,掌握歷年海洋災害情況,依法開展海洋環境治理和保護。

該院中標后將發揮由本院建設與維護的“寧波市現代測繪基準體系”技術優勢,實施調查區域的相關基礎地理信息數據采集,并將海堤資料、業務資料、電子地圖等圖像數據匯集入庫。建立地理信息管理平臺,進行數據庫的日常入庫分析、維護和更新。應用三維仿真技術,建立基于風暴潮經驗預報模型和風暴潮數值預報模型,實現對風暴潮、海嘯的數值模擬,同時結合天文潮位數據和長周期海浪等數據,建立起風暴潮、海嘯漫灘預報模型,滿足北侖區流域對海洋災害的風險評估和區劃。

(寧波市測繪設計研究院顧開建供稿)

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—),男,碩士,講師,研究方向:智能算法與大地測量數據處理。

2013年度安徽高校省級自然科學研究項目(KJ2013Z082)；安徽農業大學2012年教學研究項目(JY2012064)。

對誤差方程直接進行尋優求解的思想和步驟。通過實例模擬計算，證明該方法在測量平差計算中是可行的和有效的。