基于遺傳算法的Skyline最佳路徑分析研究

郝 婧，周海兵

1.中國地質大學（北京） 信息工程學院，北京 100083

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

在虛擬現實技術和網絡技術飛速發展下，三維地理信息系統在城市規劃和房產應用等領域的應用優勢明顯，其中最佳路徑分析功能更顯得尤為重要。

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

1 基本原理

1.1 最佳路徑

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

1.2 遺傳算法

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

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

1）選擇算子

把優化的個體直接遺傳到下一代或者通過交叉產生新的個體再遺傳到下一代。判斷個體優良與否的標準就是各自的適應值。這符合達爾文適者生存的原則。

2）交叉算子

把2個父代個體的部分優秀結構進行重組而生成新個體的操作。交叉能使遺傳算法的搜索能力飛躍提高，是算法中的核心。

3）變異算子

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

2 算法設計

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

2.1 空間柵格化

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

2.2 初始化種群

2.2.1 個體編碼方法

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

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

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

2.2.2 初始種群的產生

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

{1，2，3，4，8}

{1，5，6，7，8}

2.2.3 適應度函數設計

最佳路徑分析是以基于坡度的空間最短距離作為個體適應度函數：

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

圖1 區域柵格化

2.3 遺傳算子設計

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

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

這種交叉方式不會產生間斷路徑。

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

3 結果測試與分析

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

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

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

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

[1]王小平,曹立明.遺傳算法-理論、應用與軟件實現[M].西安:西安交通大學出版社,2002.

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