改进的单亲遗传算法在汇水盆地三维建模中的应用研究

论文摘要

汇水盆地在地球化学、地质勘测等领域的研究中占有重要地位。在地球化学勘探中,经常要用汇水盆地来圈定和研究区域化探异常;在选择水库坝址、市政建设时,也需要考虑汇水盆地地形对其各方面的影响。以往,汇水盆地大多是用手工从地形等高线图上提取的二维平面图,人工绘制的汇水盆地精度差,且费时费力又不直观。 随着 GIS 相关技术研究的逐渐深入和广泛,使用计算机进行汇水盆地的自动提取已经应用于实际的地质勘测工作中。早期,在用爬山算法对汇水盆地进行建模时,常常会因为初始点选在局部最优解的区域,而使算法陷入局部最优解,最终无法绘制出完整的汇水盆地。在这种情况下,遗传算法的全局优化能力为问题的解决指出了方向。 遗传算法模拟自然界中绝大部分生物的双亲繁殖方式,利用交叉、变异等遗传算子繁殖后代。由于遗传算法对搜索空间无特殊要求,无需求导,具有运算简单,收敛速度快等优点,并且其本身具有较强的鲁棒性和适应性,因此在各个领域得到了广泛的应用。但目前遗传算法还存在对复杂问题搜索效率低,易陷入“早熟收敛”及局部寻优能力差等缺点,对其不断完善和改进获得新的算法已成为学者们的重要研究方向之一。 单亲遗传算法是一种全新的遗传算法,它采用序号编码,不使用传统遗传算法常用的交换算子,所有的遗传操作均在一条染色体上进行,即只通过单个个体繁殖后代。它采用全新的遗传算子,如基因换位、基因倒位、基因移位等,实现了传统算子的功能。由于单亲遗传算法不使用交叉算子,即使种群中各个个体均相同,也不影响遗传迭代的进行。摆脱了对初始种群多样性的要求,不存在“早熟收敛”问题。 在实际中利用计算机对汇水盆地进行建模时,由于汇水盆地的传统的定义缺乏量化表示,因而很难对汇水盆地进行自动提取,因此本文提出一种新形式的、基于点的汇水盆地定义。同时,本文的研究又在此定义基础上,针对其特点,提出了一种提取汇水盆地三维模型的改进的单亲遗传算法。 在该算法中,引入了“宽容选择”等机制,简化了遗传操作过程,提高了计算效率,且不要求初始群体的多样性,也有效地克服了“早熟收敛”现象。算法很好地解决了以往用爬山算法对汇水盆地进行三维建模时陷入局部极小点而无法绘制出比较完整的汇水盆地的问题。 由于当前的地理信息系统的数据通常被组织在二维平面中,一般只能处理地球表面的信息,当需要处理三维空间的属性和数值变化时（地质、地球物理、地球化学、水文工程、大气等）,就必须建立真三维地理信息系统。地理信息系统从二维向三维方向发展己经成为不可逆转的趋势。 在本论文研究的对比仿真实验中,采用 OpenGL 和基于.NET 技术的 VC++,针对GTOPO30（全球的数字高程模型）建立了基于全球数据地表模型的实验原型系统。在此平台下,算法的程序实现针对真实世界地形的 DEM 数据进行了实际测试,结果证明该算法是有效的,而且真实感较强。这也证明,三维 GIS 理论和技术使汇水盆地的提取完全超越了原来手工提取,其效果更真实,数据涵义更丰富。而且,该实验对以后更广泛、更深入的 GIS 相关研究也具有一定的理论和实践的指导意义。

论文目录

• 摘要
• Abstract05
• 目录
• 引言
• 第一章 GIS 概述
• 1.1 GIS 简介
• 1.1.1 GIS 的产生
• 1.1.2 GIS 的发展
• 1.2 二维GIS 到三维GIS 转变
• 1.3 三维GIS 发展及研究现状
• 1.3.1 三维GIS 的发展
• 1.3.2 三维GIS 主要技术难点和研究现状及主要进展
• 1.4 GIS 发展趋势及方向
• 第二章 三维可视化与三维地形建模研究
• 2.1 三维可视化概述
• 2.1.1 三维可视化的背景知识
• 2.1.2 三维可视化的基本概念及发展现状
• 2.2 三维地形表现形式
• 2.3 数字高程模型与数字地面模型简介
• 2.3.1 三维DEM 的用途
• 2.3.2 DEM 生成方法
• 2.4 三维地形模型主要建模方法
• 2.4.1 基于点的表面建模
• 2.4.2 基于三角形的表面建模
• 2.4.3 基于格网的建模
• 2.4.4 混合表面的建模
• 第三章 汇水盆地概述
• 3.1 汇水盆地的定义
• 3.1.1 汇水盆地的自然定义
• 3.1.2 汇水盆地的分级定义
• 3.1.3 汇水盆地的数学定义
• 3.2 实现汇水盆地计算机自动检测的意义
• 3.2.1 水资源概况
• 3.2.2 研究汇水盆地的意义
• 3.3 用爬山法检测汇水盆地
• 3.3.1 爬山法的原理
• 3.3.2 爬山法的不足
• 第四章 遗传算法
• 4.1 遗传算法
• 4.1.1 遗传算法的产生和发展
• 4.1.2 遗传算法的简单描述
• 4.1.3 遗传算法的基本步骤
• 4.2 单亲遗传算法
• 4.2.1 单亲遗传算法的运行过程
• 4.2.2 单亲遗传算法的编码方式
• 4.2.3 单亲遗传算法的遗传算子
• 4.2.4 单亲遗传算法的特点
• 第五章 基于点的汇水盆地及改进的单亲遗传算法
• 5.1 基于点的汇水盆地的定义
• 5.2 改进单亲遗传算法的基本思想及实现
• 5.2.1 算法中母体和子体的确定方法
• 5.2.2 建立遗传编码
• 5.2.3 产生初始种群
• 5.2.4 确定适应度
• 5.2.5 遗传算子
• 5.2.6 算法描述
• 5.2.7 算法流程图
• 第六章 对比仿真实验
• 6.1 三维地形原始数据资料分析
• 6.1.1 数据集特点
• 6.1.2 数据的格式
• 6.2 地表建模
• 6.2.1 OpenGL 简介
• 6.2.2 地表建模
• 6.3 实验效果及分析
• 结论
• 参考文献
• 后记
• 在学期间公开发表论文及参加的科研项目情况