遗传算法在GIS中的应用

摘要：随着计算机技术的不断发展，伴随其发展起来的GIS技术也不断提高并为各行各业应用。将数学、计算机科学和信息科学领域知识联系起来应用于地学研究，可以有效提高GIS空间数据分析和地理空间问题模拟的准确度。遗传算法是实现地理空间问题决策化工具。

关键词：GIS技术；遗传算法；地理空间问题

引言

随着GIS应用水平的不断提高，人们逐渐开始关注地理数据的模糊性、不确定性及其分析方法，显然，传统基于确定型数据分析模型已经不能有效地解答这一问题。同时，越来越多的复杂应用问题也对GIS空间分析功能提出了更高的要求。因此，把数学、计算机科学和信息科学领域的智能计算机技术引入地学研究，将模糊数学、神经网络、遗传算法等人工智能技术与GIS相结合，把不确定性的数据处理转换成可靠的、精确的知识和信息分析，把具有高度复杂性的客观世界的本质特征加以抽象和建模，以提高GIS空间数据分析和空间问题模拟的准确度。遗传算法算是其中一种较常用的方法，利用遗传算法模拟或求解地理空间问题可以解决GIS工程中的许多难题，提高GIS对非线性问题的解决能力，可以对多方面地理问题进行优化决策，最终得出较为可靠的结果。遗传算法是实现地理空间问题决策自动化的有力工具。

1.遗传算法介绍

遗传算法是根据达尔文的进化论模仿自然界生物进化得到的一种全局优化方法。与传统的搜索方法不同，遗传 算法是基于自然选择和种群基因的一种随机搜索算法[1]。

遗传算法在实现上有两种方法：一种是种群杂交，即选择一定数量的父代，不管王与后，任何两个个体都可以杂交，任何两个父代X个体杂交后产生一个相对优生的Y个体，第二代的Y个体再如同其父代一样进行杂交，一代一代地遗传下去，直至达到最优解；另一种是一王数后的杂交，在父代个体中，选择一个最优的父个体X，分别与其他的母个体Y杂交，优生子个体Y1，再在Y1中选择一个最优的个体X1作为王，丢弃不良的一个个体后，再新娶一个后Z。新王与后Z再进行杂交，一代一代进行下去，直至产生最优解。这两种方法各有其优缺点，对于选择范围较小的优化问题，种群杂交的收敛速度更快些，而对于选择范围较大的优化问题，一王数后的杂交更有利于人工控制，并且易于收敛[1]。

2.遗传算法在GIS中的应用

2.1并行遗传算法在软件可靠性优化中的应用

对于软件的可靠性优化，也就是在完全固定的资源模式之下，找出一种能够将软件的各方面性能进行更完善分配的对策，从而使得运行的系统有更高的稳定性和可靠度，为企业在生产过程中提供更高的经济利益。而遗传算法在这个过程中，能够很好地将软件运用模拟生物化的方法来进行搜索，从而优化使用方案，在解决这个问题上，遗传算法显示出了自身强大的优势[2]。

并行遗传算法是在传统遗传算法的基础上进行改进以提高其运算速度。一般而言，它通过运用迁移策略和适应度函数可以有效地抑制早熟现象，在接近收敛时能够继续优化，并获得局部最优解。

2.2混合 DNA 遗传算法在实际应急救援路径方案设计中的应用

由于 DNA 计算和遗传算法有着诸多的相似之处，将 DNA 计算引入遗传算法进行改进，提出几种新型的交叉算子和几种新型的变异算子，并通过TSP 问题验证了该算法的有效性。TSP 问题是目前研究最为广泛的组合优化问题之一，其问题复杂性方面属于 NP 难题，对于其近似算法的研究一直是一个世界性的重要课题。遗传算法解答的有效性和全局最优的概率都明显高于早期的启发性算法，因而值得探索和研究，但标准遗传算法存在收敛速度缓慢，容易早熟的问题，针对这一问题，提出了一类新的混合遗传求解该类 NP 问题。仿真结果表明，该算法能够快速收敛到问题的近似最优解，并能很好地维持种群的多样性。因此，该方法对实际应急救援路径方案的设计具有一定的参考价[3]值。

应急物资配送问题的研究是一项复杂的系统工程，通过研究多个配送点和多个需求点之间配送一次即可满足需求的情形，将应急物资指挥中心的物资发放问题转换成为了多旅行商的问题，并应用了混合 DNA 遗传算法和新提出的交叉算子和变异算子，最后通过计算机的 Matlab 软件进行仿真求出应急物资配送的最优解，同时印证本算法的合理性和可行性。但是不考虑道路约束以及应急点的时间限制性等，有待进步加强研究[3]。

2.3基于改进的遗传算法的航空运输系统的设计与实现

研究国内外航空运输业的发展历程，尤其是航空运输系统的发展历程，对主流航空运输系统的设计模式有一定的了解后重点研究配送过程中飞行路线的优化问题。飞行路线的优化是航空运输业最需要解决、优化的问题，为了有效解决飞行路线的优化，使系统适合国内用户使用习惯及行业现状。

对遗传算法进行改进，设计并实现了一个基于 B/S 结构的航空运输系统。该系统包含了前台登录、后台管理、航班信息管理、客户信息管理、发货管理、报表管理等功能。其中发货管理部分将遗传算法应用并实现到本系统上，最终给出一个合理、有效的基于遗传算法的航空运输系统。这样一个系统对于减少企业运营成本、改善经营状况有着很大的帮助[4]。

2.4基于遗传算法的动态路径优化

随着我国社会的不断发展，交通环境不断恶化，这都成为影响社会发展的消极因素。路径优化可以帮助出行者寻找出合适的行驶路径，实现交通流在整个城市路网中各路段上的最优分配，这对于解决城市交通拥挤、提高运行效率和行车安全系数、减少能源消耗以及改善交通环境等来说都具有非常积极的意义。

对路网的建立和动态路径优化算法进行了深入研究，将道路上的实时交通流信息转化为路权，并用改进的遗传算法动态地进行路径优化，建立动态路网模型。改进的遗传算法避免了车辆在行驶中进入拥挤区域，减少了车辆的排队等候时间，提高了路径优化的动态性和实时性[5]。

2.5优化遗传算法的模糊聚类在图像分割算法中的应用

图像分割是需要进度对多种像素进行对比分割，将图形中的像素进行归类分布，采用聚类的方法分析得出图形的分割阈值，这种模糊类聚的计算方法在图形分割中是一种常用的算法。将遗传算法应用到各种图形的分割计算中，对于模糊C均值 （FCM） 迭代计算，运用遗传算法，能够有效的解决这一问题。在一般的图形分割中，运用遗传算法能够提高 FCM 算法的计算速度，图形分割的有效性，但不能有效的对变异率 Pm 和交叉率Pc进行控制，不能够自行调节像素搜索和分割的结果，影响分割的准确性和结果的正确性，需要遗传算法进行优化，改变计算的约束条件，提高算法的准确性[6]。

在图像分割时，采用优化遗传算法，能够有效的对图像分割的约束条件和相关的交叉参数进行设置，通过对对 FCM图像分割算法的分析，最终得出函数的优化条件，说明了遗传算法的模糊聚类在图像分割有效性[6]。

3.总结

通过对遗传算法的研究，发现遗传算法与传统的搜索算法不同，主要表现在以下几个方面：（1）遗传算法作用于一个参数集的编码而不是参数本身，二进制和十进制是两种广泛采用的遗传算法编码方式；（2）遗传算法是一种多解并行搜索机制，使其能以较大的概率找到整体最优解；（3）遗传算法用一个适应度函数来引导搜索，因而能应用到不同的问题中而不要求该问题受到某些特殊约束，入系统的连续性和可微性等；（4）遗传算法使用随即转移规则而不是确定性的转移规则。因此，遗产算法被应用于各行各业，尤其是地理问题的空间分析中，可以解决很多传统算法无法解决的问题。

参考文献

[1] 王平刘湘南黄方. GIS空间分析原理与方法， 科学出版社， 284-323.

[2] 周政. 并行遗传算法在软件可靠性优化中的应用[J]. 华章. 2013（19）： 323.

[3] 闻玉刚. 混合DNA遗传算法及其在组合优化中的应用[D]. 辽宁科技大学， 2013.

[4] 高庆. 基于改进的遗传算法的航空运输系统的设计与实现[D]. 吉林大学， 2013.

[5] 李云. 基于遗传算法的动态路径优化[D]. 太原理工大学， 2013.

[6] 范瑜. 论优化遗传算法的模糊聚类在图像分割算法应用[J]. 电子测试. 2013（05）： 279-281.