基于蟻群迭代算法的近似測(cè)地線(xiàn)計(jì)算

龔 燕，楊 潔，吳 微

（大連理工大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，遼寧 大連 116024）

0 引 言

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

基于以上問(wèn)題，本文提出一種蟻群迭代算法計(jì)算近似測(cè)地線(xiàn).

1 算法詳述

1.1 操作假設(shè)

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

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

1.2 蟻群迭代算法具體操作

（1）將A、B兩點(diǎn)之間的地形（如圖1所示）垂直映射到平面上（如圖2所示），在圖2上作適當(dāng)?shù)恼叫尉W(wǎng)格劃分，即將橫縱坐標(biāo)軸進(jìn)行等分操作，用5×5表示分別進(jìn)行五等分，10×10表示分別進(jìn)行十等分，依此類(lèi)推.用蟻群算法在初始網(wǎng)格劃分上找出A、B兩點(diǎn)的最短路徑.

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

（3）重復(fù)步驟（2），反復(fù)迭代適當(dāng)次數(shù)，直到尋找到最佳的測(cè)地線(xiàn)為止.

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

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

1.3 算法詳解

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

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

圖3 計(jì)算網(wǎng)格點(diǎn)之間距離示意圖Fig.3 Schematic diagram of computing the distance between grid points

在1.1操作假設(shè)中已經(jīng)提出，對(duì)于任意的地形，任給兩點(diǎn)總是可以通過(guò)測(cè)量等方法得到其三維坐標(biāo)，從而如式（2）所示計(jì)算出近似距離，那么蟻群迭代算法總是可運(yùn)行的.

最后，為了保證加密前與加密后在計(jì)算網(wǎng)格點(diǎn)之間距離時(shí)的近似程度保持一致，在每一次迭代計(jì)算網(wǎng)格點(diǎn)之間的近似曲面距離時(shí)要對(duì)插入的點(diǎn)數(shù)作適當(dāng)安排.例如，當(dāng)劃分的網(wǎng)格是5×5，計(jì)算兩個(gè)網(wǎng)格點(diǎn)之間的近似曲面距離時(shí)在該兩點(diǎn)之間不包括端點(diǎn)再插入31個(gè)點(diǎn)；加密之后，劃分的網(wǎng)格是10×10，計(jì)算兩個(gè)網(wǎng)格點(diǎn)之間的近似曲面距離時(shí)在該兩點(diǎn)之間則應(yīng)不包括端點(diǎn)再插入15個(gè)點(diǎn)；依此類(lèi)推.

2 結(jié)果討論

2.1 結(jié)果展示

經(jīng)過(guò)驗(yàn)證，用蟻群迭代算法得到的一組最短路徑數(shù)據(jù)呈現(xiàn)先降后升的結(jié)果.如圖4的地形，欲從A點(diǎn)到B點(diǎn)求出一條近似測(cè)地線(xiàn)，網(wǎng)格規(guī)模分別為2×2、4×4、8×8、16×16、32×32、64×64，由每一個(gè)劃分所得到的最短路徑見(jiàn)表1.

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

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

結(jié)果顯示，當(dāng)網(wǎng)格規(guī)模為8×8或16×16時(shí)，最短路徑大小下降到最低程度，再做加密劃分，其大小呈現(xiàn)增長(zhǎng)趨勢(shì).由此可知，蟻群迭代算法自適應(yīng)地尋找到最佳網(wǎng)格規(guī)模為8×8或16×16，此時(shí)所得到的最短路徑為最佳近似測(cè)地線(xiàn)路徑.

再如圖5的地形，欲從A點(diǎn)到B點(diǎn)求出一條近似測(cè)地線(xiàn)，網(wǎng)格規(guī)模分別為5×5、10×10、20×20、40×40、80×80，由每一個(gè)劃分所得到的最短路徑見(jiàn)表2.

再做網(wǎng)格規(guī)模分別為6×6、12×12、24×24、48×48、96×96，由每一個(gè)劃分所得到的最短路徑見(jiàn)表3.

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

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

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

由以上結(jié)果可知，表2的劃分方式當(dāng)網(wǎng)格規(guī)模為40×40時(shí)，得到最短路徑；表3的劃分方式當(dāng)網(wǎng)格規(guī)模為48×48時(shí)，得到最短路徑.綜合比較可知，當(dāng)網(wǎng)格規(guī)模為40×40時(shí)，所得到的最短路徑為最佳近似測(cè)地線(xiàn)路徑.

以上結(jié)果表明在加密到一定程度的時(shí)候繼續(xù)加密已經(jīng)沒(méi)有效果，此時(shí)便已找到了最優(yōu)化的路徑.且結(jié)果路徑圖中還顯示，即使加密過(guò)度之后最短路徑的大小增大，但是很穩(wěn)定地保持了最短路徑的趨向，如圖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 結(jié)果分析

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

3 結(jié) 語(yǔ)

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

［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］ 童 晶，陳正明.三角網(wǎng)格表面近似測(cè)地線(xiàn)的計(jì)算［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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］ 楊 斌，范媛媛，王繼東.點(diǎn)云模型上近似測(cè)地線(xiàn)的計(jì)算［J］.計(jì)算機(jī)應(yīng)用，2011，31（4）：1050－1052，1056.YANG Bin，F(xiàn)AN 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］ 杜培林，屠長(zhǎng)河，王文平.點(diǎn)云模型上測(cè)地線(xiàn)的計(jì)算［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2006，18（3）：438－442.DU Pei－lin，TU Chang－h(huán)e，WANG Wen－ping.Computing geodesics on point clouds［J］.Journal of Computer－Aided Design ＆ Computer Graphics，2006，18（3）：438－442.（in Chinese）