基于遗传算法的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.