郝 婧，周海兵

1.中國地質(zhì)大學(xué)（北京） 信息工程學(xué)院，北京 100083

2.北京東方道邇信息技術(shù)有限公司，北京 100080

在虛擬現(xiàn)實技術(shù)和網(wǎng)絡(luò)技術(shù)飛速發(fā)展下，三維地理信息系統(tǒng)在城市規(guī)劃和房產(chǎn)應(yīng)用等領(lǐng)域的應(yīng)用優(yōu)勢明顯，其中最佳路徑分析功能更顯得尤為重要。

Skyline 是目前國際上應(yīng)用最廣泛、技術(shù)最領(lǐng)先的三維GIS平臺，在海量數(shù)據(jù)方面功能尤其強大。由于數(shù)據(jù)計算量大，Skyline的最佳路徑分析時間較長并且對硬件要求較高。本文旨在從算法上改進(jìn)Skyline的最佳路徑分析功能，使該軟件日臻完美。

1 基本原理

1.1 最佳路徑

Skyline中的最佳路徑，是指在地形坡度基礎(chǔ)上兩點之間的最短空間距離。

1.2 遺傳算法

遺傳算法是一種基于自然遺傳和進(jìn)化而形成的自適應(yīng)全局優(yōu)化搜索算法，具有魯棒性強、并行性強、應(yīng)用性強等顯著特點。

遺傳算法的操作算法主要有：

1）選擇算子

把優(yōu)化的個體直接遺傳到下一代或者通過交叉產(chǎn)生新的個體再遺傳到下一代。判斷個體優(yōu)良與否的標(biāo)準(zhǔn)就是各自的適應(yīng)值。這符合達(dá)爾文適者生存的原則。

2）交叉算子

把2個父代個體的部分優(yōu)秀結(jié)構(gòu)進(jìn)行重組而生成新個體的操作。交叉能使遺傳算法的搜索能力飛躍提高，是算法中的核心。

3）變異算子

對群體中的個體串的某些基因值進(jìn)行改動，變異概率不能大于0.5，否則退化為隨機搜索。變異提高了局部搜索能力，也保持了種群多樣性。

2 算法設(shè)計

本文使用遺傳算法進(jìn)行最佳路徑分析，首先對分析空間進(jìn)行柵格化，其次用柵格排列初始化種群，最后用遺傳算子進(jìn)行操作，最終得到最佳路徑。

2.1 空間柵格化

將不可通過區(qū)域用凸多邊形描述，根據(jù)坡度的梯度單調(diào)性變化和不可通過區(qū)域進(jìn)行柵格劃分，其中包含不可通過區(qū)域的柵格為障礙柵格，反之則為自由柵格。本文只對自由柵格進(jìn)行編號，如圖1所示。

2.2 初始化種群

2.2.1 個體編碼方法

由起始位置A到終點位置B的路徑就表示一個個體，以圖1中紅色路徑為例為例，則該個體用柵格序號法表示為：

{ 1，5，6，7，8 }，

每次最佳路徑分析的區(qū)域不同，選擇可變長度的染色體進(jìn)行編碼。

2.2.2 初始種群的產(chǎn)生

本文選取一系列隨機產(chǎn)生并且不一定連續(xù)的柵格連接A和B。這樣既可以降低初始種群的困難。根據(jù)初始種群產(chǎn)生原則，如圖1所示，以下路徑都可以作為初始種群的個體編碼示例：

{1，2，3，4，8}

{1，5，6，7，8}

2.2.3 適應(yīng)度函數(shù)設(shè)計

最佳路徑分析是以基于坡度的空間最短距離作為個體適應(yīng)度函數(shù)：

式中，n為該個體的柵格總和，表示第i個柵格直線距離，表示第i個柵格的坡度。

圖1 區(qū)域柵格化

2.3 遺傳算子設(shè)計

1）選擇算子。本文個體選擇概率基于排序的適應(yīng)度分配，采用輪盤賭選擇法。

2）交叉算子。本文選擇重合點交叉，隨機選取兩個個體，柵格序號相同點進(jìn)行交叉。

這種交叉方式不會產(chǎn)生間斷路徑。

3）變異算子。本文采用單點變異操作，這樣既能降低了計算量，又保證最佳路徑的求解。

3 結(jié)果測試與分析

為了驗證算法合理性，本文以某區(qū)域的FLY為例（Skyline軟件特有的三維影像文件）。區(qū)域包括1765個坡度區(qū)域、1204個路段和132個三維模型。

測試參數(shù)中，種群大小為50，遺傳代數(shù)為100，變異概率為0.002。

經(jīng)測試基于遺傳算法的的最佳路徑更加優(yōu)化，而且在相同的硬件條件下分析時間比單純使用Skyline軟件少2～3s。如圖2，為基于遺傳算法的Skyline最佳路徑分析測試圖，其中紅色矩形區(qū)域為起始位置，黑色路徑為最優(yōu)路徑。

圖2 基于遺傳算法的skyline最佳路徑分析

[1]王小平,曹立明.遺傳算法-理論、應(yīng)用與軟件實現(xiàn)[M].西安:西安交通大學(xué)出版社,2002.

[2]馬艷麗,裴玉龍.基于混沌神經(jīng)網(wǎng)絡(luò)的駕駛員動態(tài)路徑誘導(dǎo)算法研究[J].交通運輸系統(tǒng)工程與信息,2007,7(1):57-60.