蚁群算法(Ant Colony Optimization Algorithm),又称蚂蚁算法,是一种用来在图中寻找优化路径的机率型算法,利用生物信息激素(Pheromone)作为蚂蚁选择后续行为的依据。每只蚂蚁会对一定范围内其它蚂蚁散布的生物信息激素做出反应,依据生物信息激素的强度在每一个道口对多条路径选择做出概率上的判断并执行选择,由此观察并影响它们以后的行为。它由意大利学者DorigoM等人于20世纪90年代提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群优化算法以其分布式并发性、较强的鲁棒性、易于与其他方法相结合等优点引起越来越多的国内外学者的关注,成为目前国内外研究的热点和前沿问题。本文在理论上对蚁群算法本身的理论部分进行研究,提出了三点有效的改进策略,即采用新的初始化信息素矩阵、通过聚类进行局部搜索和混合算法,对蚁群算法加以改进。在应用方面选取TSP问题和交通路径优化问题作为典型的组合优化问题,用改进的蚁群算法求解之。仿真结果表明了改进算法的有效性和可行性。论文的主要工作概括如下:(1)在阅读国内外大量文献资料的基础上,总结了当前蚁群算法的研究成果和亟待解决的问题。本文以研究典型的NP难问题——旅行商问题入手,对蚁群优化算法的发展背景、原理、实现方法和性能作了详细介绍,对该算法本身进行了深入研究,提出了自己的改进方案并作进行了仿真。(2)针对蚁群算法存在着搜索时间长、易限于局部最优解等缺陷,提出了一种改进的蚁群算法。通过在初始化信息素矩阵中采用候选城市列表减少劣质解,在局部搜索中采用聚类进行二次搜索,缩小了算法的搜索范围、改善了解空间的质量,提高了搜索速度。仿真结果表明,改进后的蚁群算法,在TSP问题的求解中,收敛速度和全局寻优能力均得到较大的提高。(3)针对实际交通中带约束的多目标问题,提出一种基于分层GA-AS混合算法的多目标路径优化方法。该算法通过约束条件对路网进行分层,遗传算法求解上层问题,蚁群算法求解下层问题。前者能够从全局角度探索到最优解,但它无法对探索空间的细节做局部探索;而后者可从局部角度出发趋近最优解,从而提高算法局部寻优能力。算例仿真结果表明:采用这种算法既具有很强的实际应用效果,又在很大程度上减少寻优计算次数,提高了算法的性能。