基于蟻群迭代算法的近似測地線計算

龔 燕，楊 潔，吳 微

（大連理工大學 數學科學學院，遼寧 大連 116024）

0 引 言

測地線的計算分為精確計算和近似計算.由于難于求出測地曲率，精確計算方法在實際操作中基本無法運用.近似計算有很多方法，例如Kanai等［1］和童晶等［2］先后對三角網格上的近似測地線算法做了研究.但Kanai等的方法計算精度很低，并且容易陷入局部最優.童晶等針對其容易陷入局部最優的問題進行了改進，提出了三角網格上的迭代細分算法，同時還提高了迭代運算速度和精度，然而該算法的收斂性和給定誤差下的計算復雜度還未做理論的分析，實際運用起來仍然有著一定局限性.楊斌等［3］和杜培林等［4］分別研究了點云模型上的近似測地線計算，但他們的算法均采用固定的網格模型，需要建立目標函數以及求解解析式，精確度不高同時操作難度很大.

基于以上問題，本文提出一種蟻群迭代算法計算近似測地線.

1 算法詳述

1.1 操作假設

假設對于區域ΩR3中任意一點可通過某種方法確定其三維坐標，那么在該區域中，任意兩點之間的近似距離可通過坐標計算求得.例如，任意A、B∈R3，A點坐標為（x1，y1，z1），B點坐標為（x2，y2，z2），則A、B之間的近似距離可通過下式得到：在這樣的條件下，任給某種地形，本文希望用蟻群迭代算法求出給定的兩點之間的近似測地線.

首先將待求兩點之間的地形在相應的垂直映射平面圖上作任意網格劃分，再不斷加密劃分，每一步劃分得到相應的網格模型后都用蟻群算法計算最短路徑，這樣可以通過迭代計算自適應地尋找最佳網格規模，解決網格劃分不適當造成的誤差，并且在計算過程中不需要地形解析式或其他方程式.

1.2 蟻群迭代算法具體操作

（1）將A、B兩點之間的地形（如圖1所示）垂直映射到平面上（如圖2所示），在圖2上作適當的正方形網格劃分，即將橫縱坐標軸進行等分操作，用5×5表示分別進行五等分，10×10表示分別進行十等分，依此類推.用蟻群算法在初始網格劃分上找出A、B兩點的最短路徑.

（2）對上一步的網格劃分作成倍加密劃分，例如上一步網格規模為5×5，則加密至規模10×10，并設置當前蟻群算法的初始信息素與上一步保留信息素比例為1∶1，再用蟻群算法在當前的劃分上找出A、B兩點的最短路徑，且依然保留該路徑上的信息素.

（3）重復步驟（2），反復迭代適當次數，直到尋找到最佳的測地線為止.

圖1 原地形圖Fig.1 Original topographic map

圖2 圖1的垂直映射平面圖Fig.2 Vertical mapping planar graph of Fig.1

1.3 算法詳解

在設計算法中，之所以保留上一步最短路徑上的信息素是為了給下一步迭代以啟示，讓螞蟻們有意識地偏向已有最短路徑周圍繼續尋找更合適的路徑，從而避免在整個范圍內尋找最短路徑的盲目性.但是這樣做容易導致螞蟻們幾乎全部聚集在上一步最短路徑周圍，使得迭代效率大大降低.為解決此問題，本文設置每一步迭代時蟻群算法的初始信息素與保留信息素比例為1∶1，這樣既能合理利用上一步迭代成果的資源，又不影響在整個范圍內尋找最短路徑.該比例的大小是否影響且將如何影響每一步迭代找出的最短路徑，有待進一步討論研究.

另外，在該算法中最關鍵的是獲取網格點所對應的原地形上兩點之間的曲面距離.由于整個地形可能很不規則，無法通過公式得到該距離，但也不可直接用兩點之間的直線距離取而代之，因為初始網格劃分密度通常不會太大，這樣計算可能造成很大的不準確性.本文采取在網格點之間適當增加一些點，然后算出每一小段的直線距離，將其總和作為兩個網格點之間的近似曲面距離的辦法解決這一難題.例如，圖3中的凹凸地形，假設平面上A″、B″兩點是網格點，現需計算A″、B″兩點所對應的原地形圖上A′、B′之間的近似曲面距離，如果直接用連接A′、B′的直線距離代替，在初始網格劃分不太細密的時候計算誤差會較大，所以本文在A″、B″兩點之間再等距插入一些點，例如插入C″點，其中C″點對應原地形圖上的C′點，假 設A′的 坐 標 為（x1，y1，z1），B′的 坐 標 為（x2，y2，z2），C′的坐標為（x3，y3，z3），則A′、B′之間的曲面距離

圖3 計算網格點之間距離示意圖Fig.3 Schematic diagram of computing the distance between grid points

在1.1操作假設中已經提出，對于任意的地形，任給兩點總是可以通過測量等方法得到其三維坐標，從而如式（2）所示計算出近似距離，那么蟻群迭代算法總是可運行的.

最后，為了保證加密前與加密后在計算網格點之間距離時的近似程度保持一致，在每一次迭代計算網格點之間的近似曲面距離時要對插入的點數作適當安排.例如，當劃分的網格是5×5，計算兩個網格點之間的近似曲面距離時在該兩點之間不包括端點再插入31個點；加密之后，劃分的網格是10×10，計算兩個網格點之間的近似曲面距離時在該兩點之間則應不包括端點再插入15個點；依此類推.

2 結果討論

2.1 結果展示

經過驗證，用蟻群迭代算法得到的一組最短路徑數據呈現先降后升的結果.如圖4的地形，欲從A點到B點求出一條近似測地線，網格規模分別為2×2、4×4、8×8、16×16、32×32、64×64，由每一個劃分所得到的最短路徑見表1.

圖4 單峰原地形Fig.4 Original terrain of unimodal

表1 單峰地形的結果Tab.1 The results of unimodal terrain

結果顯示，當網格規模為8×8或16×16時，最短路徑大小下降到最低程度，再做加密劃分，其大小呈現增長趨勢.由此可知，蟻群迭代算法自適應地尋找到最佳網格規模為8×8或16×16，此時所得到的最短路徑為最佳近似測地線路徑.

再如圖5的地形，欲從A點到B點求出一條近似測地線，網格規模分別為5×5、10×10、20×20、40×40、80×80，由每一個劃分所得到的最短路徑見表2.

再做網格規模分別為6×6、12×12、24×24、48×48、96×96，由每一個劃分所得到的最短路徑見表3.

圖5 多峰原地形Fig.5 Original terrain of multimodal

表2 多峰地形的結果1Tab.2 The results of multimodal terrain（1）

表3 多峰地形的結果2Tab.3 The results of multimodal terrain（2）

由以上結果可知，表2的劃分方式當網格規模為40×40時，得到最短路徑；表3的劃分方式當網格規模為48×48時，得到最短路徑.綜合比較可知，當網格規模為40×40時，所得到的最短路徑為最佳近似測地線路徑.

以上結果表明在加密到一定程度的時候繼續加密已經沒有效果，此時便已找到了最優化的路徑.且結果路徑圖中還顯示，即使加密過度之后最短路徑的大小增大，但是很穩定地保持了最短路徑的趨向，如圖6和7所示.

圖6 單峰地形的一組最短路徑Fig.6 The set of shortest paths of unimodal terrain

圖7 多峰地形的一組最短路徑Fig.7 The set of shortest paths of multimodal terrain

2.2 結果分析

網格之所以加密到一定程度便失去加密效果，是因為此時加密過度，使得網格點之間的距離非常小，蟻群迭代算法使用輪盤賭的原則選擇下一步走向，這時螞蟻們很可能會在局部小范圍內繞圈走彎路.另一方面，最短路徑的大小是由該路徑上相鄰網格點之間的距離總和求得的，此時網格點之間距離很小，則總和便會增大，更何況此時已經保持了同一的最短路徑趨向.所以由實驗結果與理論分析可知，蟻群迭代算法確實能有效優化最短路徑，而且該算法相對穩定，如本文中實例情形，一般在網格規模為40×40 時達到最佳效果.由于計算網格點之間的距離時近似程度要保持一致性，在加密過程中不可任意加密，應成倍加密.為了避免可能疏漏的某些網格規模，可通過更改初始劃分密度，得到更多其他的網格規模，例如表3的最優結果為網格規模48×48，再使其與40×40的網格規模作比較，看是否得到更優化的最短路徑，此處不再作詳細示范.

3 結 語

本文提出了一種不依賴于地形解析式的近似測地線計算方法——蟻群迭代算法，該算法采用自適應的方式尋找最佳網格劃分規模，克服了某些算法中固定網格劃分未能達到最佳規模而造成的較大計算誤差，從而能找出更加優化的最短路徑，且在復雜、凹凸不平、障礙物多的地形上尤其適用.但本文對每一步迭代時蟻群算法的初始信息素與上一步迭代的保留信息素比例問題未做詳細探討，在不影響實驗結果的情況下，暫時先設置為1∶1的比例，此問題有待進一步研究.

［1］ Kanai T，Suzuki H.Approximate shortest path on apolyhedral surface and its applications［J］.CAD Computer Aided Design，2001，33（11）：801－811.

［2］ 童 晶，陳正明.三角網格表面近似測地線的計算［J］.計算機輔助設計與圖形學學報，2008，20（2）：180－185.TONG Jing，CHEN Zheng－ming.Approximate geodesics path on triangle mesh ［J］.Journal of Computer－Aided Design ＆ Computer Graphics，2008，20（2）：180－185.（in Chinese）

［3］ 楊 斌，范媛媛，王繼東.點云模型上近似測地線的計算［J］.計算機應用，2011，31（4）：1050－1052，1056.YANG Bin，FAN Yuan－yuan，WANG Ji－dong.Computation of approximate geodesics on point cloud［J］.Journal of Computer Applications，2011，31（4）：1050－1052，1056.（in Chinese）

［4］ 杜培林，屠長河，王文平.點云模型上測地線的計算［J］.計算機輔助設計與圖形學學報，2006，18（3）：438－442.DU Pei－lin，TU Chang－he，WANG Wen－ping.Computing geodesics on point clouds［J］.Journal of Computer－Aided Design ＆ Computer Graphics，2006，18（3）：438－442.（in Chinese）