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

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

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

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

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

1 蟻群算法基本原理

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

圖1 蟻群選擇路徑示意圖

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

1.1 尋找初始路徑

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

(1)

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

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

(2)

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

(3)

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

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

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

(4)

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

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

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

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

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

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

1.3 信息素更新

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

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

(5)

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

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

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

2.1 多面函數(shù)基本原理

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

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

(6)

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

(7)

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

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

圖2 兩種常見類型核函數(shù)示意圖

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

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)

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

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

(11)

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

(12)

根據(jù)最小二乘原理求得擬合模型的系數(shù)項為

(13)

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

2.2 多面函數(shù)相關(guān)參數(shù)設(shè)置

2.2.1 選擇核函數(shù)

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

2.2.2 確定平滑因子

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

2.2.3 蟻群算法獲取特征點

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

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

3 算例分析

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

3.1 獲取多面函數(shù)擬合的特征點

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

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

3.2 構(gòu)建GPS高程異常擬合模型

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

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

3.3 擬合結(jié)果精度對比分析

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

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

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

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

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

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

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

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

4 結(jié) 語

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

圖4 均勻格網(wǎng)與加入蟻群算法擬合結(jié)果殘差對比

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