论文部分内容阅读
网络分析是地理信息系统中强大的分析功能之一,而路径求解是网络分析的基础。遗传算法是当代人工智能技术求解最优化问题的有力工具,用遗传算法求解路径开辟了另外一种思路。遗传算法求解路径问题能够较少地了解待求问题的细节,而采用能够最终收敛到最优解的随机搜索方法,因此实现思路较简单,易于编程实现,省掉了研究过程实现的细节和步骤。
本论文首先对传统经典的最短路径算法进行了研究,在此基础上,用计算机高级语言编程实现,对实验数据进行求解最短路径。接着主要从遗传算法入手进行研究,得出用遗传算法求解的步骤,并用计算机辅助工具MATLAB实现对较复杂的网络图求解最短路径。在分别用Dijkstra算法和遗传算法求解之后,对比两种方法的优劣,得出使用遗传算法求解的优点。本论文还对一个地理信息系统中的实例全国铁路网的最短路径进行了求解和显示输出。
此外,本文还对NP难题TSP旅行商问题做了研究,并在MATLAB环境下实现了对全国81个城市的TSP求解。
本论文的特点在于:采用优先权编码和适合此类问题求解的交叉和变异算子的遗传算法对GIS路径进行求解,并用MATLAB去实现。通过大量的实验,得出随着网络规模大小的不同,应当采用不同的编码和算子。本论文还简单总结了用遗传算法求解路径问题的优势所在。