蚁群优化算法在求解最短路径问题中的研究与应用

最短路径问题一直是交通工程学、计算机科学、城市规划等学科的研究热点,研究最短路径问题具有重要的意义和实用价值。在求解此问题时,传统的最短路径算法有Dijkstra算法,动态规划算法,启发性的搜索算法有模拟退火算法、遗传算法、蚁群算法等。 蚁群算法作为仿生优化算法,它的全局搜索、正反馈、鲁棒性、易与其他仿生优化算法结合、分布式计算等特点,体现出了求解复杂优化问题的优越性,吸引了越来越多人的研究。从一开始被运用在解决旅行商问题到图着色问题、车辆调度问题,再后来应用在动态组合优化问题如通讯网络路由问题等等,蚁群算法已经广泛应用到各个其他领域中,许多学者通过研究基本蚁群算法,针对它的收敛速度慢和早熟缺点,提出了很多改进的蚁群优化算法,如蚁群系统、带精英策略的蚁群算法、多态蚁群算法、基于免疫的蚁群算法、自适应蚁群算法等。 本文首先系统地论述了基本的蚁群算法,介绍了几种常见的蚁群优化算法,并对蚁群系统进行了深入的分析,然后针对蚁群算法在求解交通网络两点之间最短路径问题时存在收敛速度慢和容易出现搜索停滞现象等缺点,为提高搜索效率和质量,提出了一种改进的蚁群算法,改进如下： 1.通过在初始化信息素时加入方向引导因素,减少了劣质解,提高了解空间的质量; 2.设计了一个动态因子,使其自适应平滑地更新迭代最优解路径信息素,很好地利用了较优的解,提高了搜索比较好的解空间能力,有效地避免算法求解出现早熟。 仿真实验结果表明,不但算法在收敛速度有大幅度地提高,而且在避免易于陷入局部最优解方面取得了很好的效果,该改进算法是有效的、可行的。最后把改进的蚁群优化算法应用到GIS交通网络最短路径问题中,提高了搜索到全局最优解的速度。