一種基于蟻群算法的山區(qū)GPS高程異常擬合方法

蒲 倫，唐詩華，張紫萍，李宗婉，張 炎

(1. 桂林理工大學測繪地理信息學院，廣西 桂林 541006； 2. 廣西空間信息與測繪重點實驗室，廣西 桂林 541006； 3. 青海省生態(tài)環(huán)境遙感監(jiān)測中心，青海 西寧 810007)

隨著現代測繪技術飛躍發(fā)展，GPS在實際工程中的應用越來越廣泛[1]。為滿足各行業(yè)的建設需求，建立精確可靠的高程基準是測繪行業(yè)必不可少的工作。采用GPS技術能夠精確測定地物點的坐標，但GPS獲取的大地高不能直接用于實際工程，轉換為實際所需的正常高是數據處理的關鍵技術，即高程異常擬合的精度直接影響坐標轉換精度[2]。

GPS高程異常擬合的方法較多，目前常用的擬合方法有多項式曲線擬合法、三次樣條曲線擬合法、平面擬合法及多面函數擬合法等[3]。常規(guī)擬合方法在地勢平緩地區(qū)擬合效果較好，能夠滿足實際精度需求[4]。在地形條件復雜、地勢起伏較大的山區(qū)獲取擬合數據，常規(guī)方法很難滿足實際所需精度要求，往往需要對傳統(tǒng)方法進行一定的改進[5]。多面函數法可以解決山區(qū)GPS高程異常擬合困難問題，但在采用多面函數法擬合時，要提供足夠的特征點才能達到理想的擬合效果[6]。尋找特征點的過程較為煩瑣，為解決特征點選擇困難的問題，本文基于蟻群算法來尋找最佳分布的特征點。利用蟻群算法對多面函數必要參數及其數量進行有效選擇，為模型構建提供可靠依據。

1 蟻群算法基本原理

蟻群算法是由Marco Dorigo在20世紀90年代提出的尋優(yōu)方法，主要是根據螞蟻在尋找食物時通過正反饋尋找最佳路徑的方法[7]。如圖1所示，螞蟻尋找食物過程中能夠在通過的路徑上釋放信息素，螞蟻之間就是以信息素實現信息傳遞，后續(xù)到來的螞蟻傾向于選擇信息素濃度高的路徑，個體之間不斷進行信息交流和傳遞，表現出一種信息正反饋現象[8]。路徑上經過的螞蟻數越多，路徑上留下的信息素就越濃，越能吸引更多的螞蟻選擇此路徑；若路徑長期沒有螞蟻經過，或經過的螞蟻數量太少，會因為信息素逐漸揮發(fā)后濃度降低，螞蟻群體能夠通過這種協(xié)調機制找到通往食物源的最短路徑。

圖1 蟻群選擇路徑示意圖

螞蟻尋找最優(yōu)路徑的過程可以分為3個步驟：①尋找初始路徑，將螞蟻隨機分配到研究區(qū)域中，每只螞蟻從空路徑開始搜索，根據屬性節(jié)點重復選取滿足條件項加入到路徑中，構成完整路徑；②對選擇的路徑剪枝優(yōu)化，去掉與實際不符或不相關節(jié)點，避免影響最優(yōu)路徑篩選；③更新已選路徑的信息素濃度，最佳路徑的信息濃度增加，反之則降低濃度。

1.1 尋找初始路徑

螞蟻根據重復選擇屬性節(jié)點來完成路徑的選擇工作，選取屬性節(jié)點理論上可以任意隨機，但考慮搜索速度及效率問題，以啟發(fā)函數的形式來指引螞蟻選擇路徑顯得很有必要[9]。將啟發(fā)式函數ηij表示為

(1)

式中，啟發(fā)值大小表征選擇路徑能力；K為路徑數量；a為屬性的數量；bi為屬性i的個數；infoTij為選擇屬性節(jié)點時符合條件的可設比例關系式。

給定螞蟻的隨機位置，設置信息素初始濃度值，計算公式表示為

(2)

式中，τij為條件項的信息素濃度。根據啟發(fā)函數和信息素濃度來確定是否選擇某一路徑，可計算對應的概率確定是否選擇。路徑概率公式為

(3)

通過屬性節(jié)點被選中的概率值來判定是否選取為當前路徑，若滿足相應條件即可設為備選路徑，形成一條完整的路徑。

1.2 初始路徑優(yōu)化

構造初始路徑時添加每個屬性節(jié)點，形成完整路徑，條件項過多將對蟻群擇優(yōu)路徑造成一定的干擾，降低了尋優(yōu)路徑的選取質量，此時需要去掉不相關的屬性節(jié)點，由優(yōu)化后的有效性來判斷是否保留有效的屬性節(jié)點。有效性的計算公式定義為

(4)

式中，TP為滿足條件，實測與預測值相同數目；FP為滿足條件，但實測與預測值不同數目；TN為不滿足條件，實測與預測值不同數目；FN為不滿足條件，實測與預測值相同數目。

通過上述有效性決定是否去除某個屬性節(jié)點并保留最佳屬性。設A={條件i，類名，i=1，2，…，n}表示生成的路徑A，可得路徑的剪枝實現步驟為

(1) 計算A的有效性AG。

(2) 移去A中的條件i，形成B路徑，同理計算B的有效性BG。

(3) 比較AG和BG有效性，若AG

(4)i=i+1反復循環(huán)前3個步驟，當執(zhí)行完所有的條件后循環(huán)結束并選擇最優(yōu)路徑。

1.3 信息素更新

構造初始路徑并經過優(yōu)化后得到的路徑，其屬性節(jié)點的信息素濃度都會發(fā)生變化，信息素濃度更新的過程中會考慮最優(yōu)路徑選擇的效率問題，調整信息素濃度的規(guī)則是提高包含在最優(yōu)路徑中的屬性節(jié)點濃度，降低不包含最優(yōu)路徑中的濃度。更新公式為

τi j(t+1)=(1-ρ)·τij(t)+G·τi j(t)

(5)

式中，ρ為信息素的揮發(fā)系數，根據實際需要設置揮發(fā)系數。每次構造路徑都將更新濃度，所有螞蟻不斷重復進行更新。通過循環(huán)迭代，設置停止準則，選出最優(yōu)的路徑后若滿足停止條件則停止循環(huán)，從而獲取最優(yōu)的路徑。

2 多面函數法擬合山區(qū)GPS高程異常

多面函數法是美國Hardy教授在19世紀70年代提出的由若干簡單曲面疊加成復雜連續(xù)曲面的建模方法，任意規(guī)則或不規(guī)則圓滑曲面都可由單值數學面疊加逼近，達到逼近真實模型的效果[10]。適合地形條件復雜、地勢起伏明顯的山區(qū)擬合建模，研究表明任何一個圓滑的曲面都可以通過該方法達到逼近的效果。

2.1 多面函數基本原理

根據多面函數擬合的思想，設f(x,y)為已知曲面函數，若函數φ(x,y)滿足

∑(f(xi,yi)-φ(xi,yi))2=min

(6)

稱φ(x,y)為逼近函數，逼近函數φ(x,y)表示如下

(7)

式中，u為核函數的個數；β為模型系數；Q表示核函數；(xj,yj)為中心節(jié)點。

可選任意函數作為核函數，通常選取對稱型或距離型核函數使計算更方便[11]。常見核函數可以分為兩大類，大體走勢如圖2所示。

圖2 兩種常見類型核函數示意圖

根據圖2可知，空間數據擬合主要分為“鐘”型核函數和“缽”型核函數兩類。多面函數擬合中常用的正雙曲函數、倒雙曲函數及三次曲面函數，其表達式分別為

Q=((x-xj)2+(y-yj)2+δ)1/2

(8)

Q=((x-xj)2+(y-yj)2+δ)-1/2

(9)

Q=((x-xj)2+(y-yj)2)3/2+δ

(10)

式中，δ為核函數光滑因子，用于調節(jié)核函數的形狀。

選取上述核函數建立誤差方程，設有n組觀測值(xi,yi,ζi)，i=1，2，…，n， 則得

(11)

式中，(x0j,y0j)表示中心節(jié)點位置。ζ為對應的觀測值，用A表示核函數矩陣，則改正數V的矩陣形式為

(12)

根據最小二乘原理求得擬合模型的系數項為

(13)

求解擬合模型系數矩陣后代入式(7)即可完成多面函數的擬合模型構建。

2.2 多面函數相關參數設置

2.2.1 選擇核函數

多面函數法的模型求解過程中，核函數的選擇直接關系到擬合的效果，通常根據觀測數據自身較強的相關性來選擇核函數，研究人員對此作了大量研究并得出一般性結論[12-13]。判斷核函數的優(yōu)劣遵循一定原則，擬合值與實際觀測值之間不存在偏差，待測點的估算值平穩(wěn)，避免出現急劇變化的現象等。Hardy教授的研究結果表明對擾動位型調和函數擬合采用倒雙曲面函數，對地形模型非調和型擬合則采用正雙曲面函數實現擬合，管真等對正倒核函數進行了研究[14]。目前對于高程擬合模型構建具有較好擬合效果的核函數主要是正雙曲面函數、倒雙曲面函數和三次曲面核函數。

2.2.2 確定平滑因子

平滑因子δ是改變核函數形狀的重要因素，從圖2可以看出，平滑因子δ取不同的值，核函數的大致走勢可能保持不變，但會影響核函數的細節(jié)變化。齊娜等通過大量試驗發(fā)現隨著平滑因子的遞增，檢核點殘差中誤差先變小后逐漸增大，當結果到達理想狀態(tài)時，平滑因子的值會落在某個區(qū)間范圍[15]。根據計算和經驗確定平滑因子應取0或者較小的正數[16]。

2.2.3 蟻群算法獲取特征點

地形特征點的位置及數量的確定是多面函數中關鍵步驟，其點位選取質量直接影響模型構建的精度高低。對于地勢起伏較大，地形條件復雜區(qū)域，特征點最好選擇合理分布在研究區(qū)域內的代表點[17]。數據分布均勻時可選擇非嚴格數據格網化的點位數據加以補充，進而全面表述地形地物特征。均勻特征點的選取決定了多面函數擬合效果，因此，需要有一種高效合理的方法來找出這些特征點，本文基于蟻群算法尋找復雜地形中的特征點方法。

蟻群算法尋找特征點的總體思路：將若干螞蟻任意分布在研究區(qū)內，設置相同的信息素濃度和揮發(fā)系數；讓每只螞蟻根據啟發(fā)函數或最終目標分別尋找具有代表性的特征點，通過迭代循環(huán)快速確定螞蟻群體的行進路線，對于高程擬合的特征點由明顯特征是山脊線或山谷線附近的點位；更新移動路徑，確定尋找特征點的完整路線；匯集所有特征點并對其密度進行處理，形成最優(yōu)特征點的集合，提供必要的擬合模型參數。

3 算例分析

以西南某山區(qū)GPS觀測數據為例，總面積約100 km2，經計算求得該區(qū)域內GPS高程異常數據的最大值為27.946 m，最小值為19.953 m。收集了500個 GPS水準重合點，從其中的400個數據中尋找最優(yōu)特征點，并完成擬合模型構建，然后用剩余數據檢核驗證擬合模型的精度，綜合分析并合理評定高程異常擬合模型的精度及其穩(wěn)定性。

3.1 獲取多面函數擬合的特征點

多面函數的特征點表征研究區(qū)域的地形地貌特點，用特征點構建擬合模型能夠最大可能接近實際情況。蟻群算法尋找地形復雜地區(qū)的特征點具有明顯優(yōu)勢，通過尋優(yōu)路徑的正反饋原理能夠實現快速搜索的功能，根據實際收集數據及經驗，在研究區(qū)域分配400只螞蟻，完成群體規(guī)模大小設置，每只螞蟻的位置分布完全隨機，通過大量嘗試后給定迭代次數50次，分別尋找范圍內海拔差異較大的點。通過蟻群尋優(yōu)路徑的正反饋機制最終向山脊線或山谷線靠攏，完成路徑的搜索過程，從而快速找出適用于構建擬合模型的最佳特征點。

根據設定規(guī)則可知，初始隨機分配螞蟻的位置沒有任何規(guī)律可循，蟻群找到特征點位的分布后，所有螞蟻向山脊線或山谷線匯集，縮小了整個區(qū)域的特征點分布范圍。蟻群算法找出山脊線和山谷線附近的分布點后，再采用均勻格網法補充少量地勢平緩地區(qū)的特征點，使選取點更能充分合理說明狀況。最后對整體特征點的密度作過濾處理，對于點位密集程度大的地方根據實際情況設置閾值進行篩選，留下最優(yōu)的選擇方案構成特征集合點。

3.2 構建GPS高程異常擬合模型

圖3 蟻群算法建模前后檢測點三維對比

由圖3中擬合前后的三維效果對比圖可知，加入蟻群算法的多面函數擬合模型求解結果同實際檢測點位GPS高程異常值接近，繪圖效果直觀說明建模良好。

3.3 擬合結果精度對比分析

完成擬合模型構建后，分別從擬合模型的內外符合精度進行評價與分析。蟻群算法快速搜索特征點集合，求得多面函數的系數矩陣實現模型構建。對同一組檢核點分別采用蟻群和格網法獲取特征點，然后與蟻群結合均勻格網一同比較分析。從100個檢測點的擬合結果中隨機抽取了15組，殘差對比情況見表1。

表1 不同擬合方法的殘差對比 mm

由表1可知，首先采用蟻群算法尋找的特征主要分布在地形起伏較大的山脊和山谷地區(qū)，未涉及地勢較平緩的區(qū)域，只用這些特征點擬合所得結果不穩(wěn)定，出現明顯的誤差屬于正常現象，故需要利用均勻格網補充平緩研究區(qū)域均勻分布的特征點。從表1第3列數據的擬合結果來看，擬合結果的殘差更加趨于穩(wěn)定，同時殘差波動范圍明顯小于僅使用均勻格網法的擬合殘差。為了避免偶然情況及精度分析的特殊性，對3種不同擬合方式分別求解其內符合精度和外符合精度，選取計算統(tǒng)計的10次擬合結果(見表2)。

表2說明無論是從內符合精度還是外符合精度來看，蟻群算法結合均勻格網獲取多面函數所需的特征點，擬合精度均高于單獨使用其中的一種方法的擬合精度，由大量試驗統(tǒng)計分析求得檢核點的精度σw=±4.4 mm。

表2 不同方法選取多面函數法特征點擬合精度統(tǒng)計 m

除了根據檢核點外符合精度來比對分析，為清晰直觀地說明蟻群算法在山區(qū)GPS高程異常擬合中具有的明顯優(yōu)勢，繪制了檢核點殘差對比圖(如圖4所示)。另外分別用二次曲面和三次曲面擬合相同檢測點的GPS高程異常數據，對比殘差曲線如圖5所示。

圖4清晰展示了蟻群算法尋找特征點的優(yōu)勢，在多面函數建模過程中參數得到了優(yōu)化，模型的穩(wěn)定性比僅用均勻格網結果要好。

根據圖5中殘差曲線走勢可知，常規(guī)方法適用于平緩區(qū)域，而復雜區(qū)域難以滿足實際需求。多面函數擬合法在山區(qū)GPS高程異常擬合中比曲面擬合更加有效可行，同時證明采用蟻群算法優(yōu)化特征點后的擬合方法對于提高模型的精度具有明顯優(yōu)勢。

4 結 語

本文研究了基于蟻群算法的山區(qū)GPS高程異常擬合方法，同曲面擬合模型相比，在地勢起伏較大的山區(qū)選擇多面函數擬合法更為合理。將蟻群算法結合均勻格網共同選取最優(yōu)特征點，然后求解擬合參數并構建多面函數擬合模型。通過算例分析結果表明，基于蟻群算法優(yōu)化多面函數參數的方法有效可行，構建的擬合模型優(yōu)于使用單一方法擬合結果，在一定程度上提高了多面函數擬合模型的精度，具有一定的研究價值。

圖4 均勻格網與加入蟻群算法擬合結果殘差對比

圖5 二次曲面與三次曲面法擬合結果殘差對比