gis路径寻优中的蚁群算法研究

《gis路径寻优中的蚁群算法研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、南京理工大学硕士学位论文GIS路径寻优中的蚁群算法研究姓名：孙中华申请学位级别：硕士专业：控制理论与控制工程指导教师：王海梅20090608硕士论文GIS路径寻优中的蚁群算法研究摘要最短路径问题是交通网络分析中的一个重要问题，也是资源分配、路线设计等优化问题的基础。多年来，最短路径算法一直是运筹学、地理信息科学等学科的研究热点，由此出现了大量研究成果。纵观这些成果，主要还是集中在以经典Dijkstra算法为基础的各类改进算法的研究和应用方面。蚁群算法是近年来迅速发展起来的一种全局性优化算法，但这种基于生物进化原理的算法还没有形成系统的、成熟的算法理论体系，提高

2、搜索速度，克服过早收敛仍然是算法研究的方向。论文以提高算法效率为出发点，对基于道路网络的蚁群算法搜索策略进行了研究。论文还对时变道路网络的最短路径问题进行了探讨。论文的研究成果主要包括：1)基于泰州市电子地图道路信息，通过道路的提取，拓扑网络的构建，生成了适于最短路径问题分析的道路网络平台。2)基于上述平台，设计并实现了道路网络寻优中的蚁群算法，具体包括：分析蚂蚁搜寻过程，设计算法流程，编写代码并实现。3)对上述蚁群算法进行改进，研究了矩形限制搜索区域的蚁群算法，实验结果表明：矩形限制搜索区域的蚁群算法较传统的蚁群算法在节点搜索数目及运算时间方面有较大改善。4

3、)利用蚁群算法多解性，通过调整蚂蚁信息素释放标准，保证蚂蚁得到的次优解质量，结果表明，在最短路径不可行的情况下，蚂蚁能够迅速地收敛到最理想的替代路径上来。5)在对时变网络分析的基础上，建立了一个时变道路网模型。对道路交通网络的道路通行时间进行区域简化，并基于该简化网络实现了时变的最短时间路径算法。关键词：最短路径，蚁群算法，限制搜索区域，时变网络硕士论文AbstractTheshortestpathoptimizationisoneofthecriticalproblemsintransportationnetworks．It’Salsothebasisofm

4、anyareas，suchasresourceallocationandroutedesigning．Overtheyears，development,application,andefficiencyanalysisoftheshortestpathalgorithmhavebeenahotspotinoperationalresearch，geographicinformationscienceandsoon．Asaresult,largenumbersofalgorithmscameout．Andthesealgorithmsaremainlyfocus

5、edontheresearchesandapplicationsofimprovementbasedonclassicalalgorithm—Dijkstraalgorithm．Antcolonyalgorithmdevelopedrapidlyinrecentyears，itisaglobaloptimizationalgorithmandbasedontheprinciplesofbiologicalevolution．However,thisalgorithmhasnotyetformedasystemicandmaturetheoreticalsyst

6、em．Toimprovesearchingspeedandovercometheprematureconvergenceisstillthedirectionofthealgorithm．ThepurposeofpaperisimprovingefficiencyofthealgorithmandstudyingsearchingstrategyofACObasedonroadnetworks．Andpaperalsodiscussedtheshortestpathproblemintime-dependentnetworks．Themaintasksaref

7、ollowingaspects：1．ThroughtheextractionofroadsfromelectronicmapofTaizhouCity,andconstructionoftopologynetwork，toconstructtheroadnetworkplatformfortheshortestpathanalysis．2．Basedontheplatformabove，designandimplementACOinoptimizationofgeographicalroads，including：analysingprocessofantse

8、arching，designingst