混合蚁群算法及其应用地研究.pdf

硕士学位论文
M . D . Thesis
混合蚁群算法及其应用研究
M ixed A nt C olony A lgorithm and T heir
A pplications
侯文静
H ou w en jing
二○一一年五月
西北师范大学硕士学位论文
摘要
蚁群算法(A nt Colony O ptim ization A lgorithm ),又称蚂蚁算法,是一种用来在
图中寻找优化路径的机率型算法,利用生物信息激素(Pherom one)作为蚂蚁选择
后续行为的依据。每只蚂蚁会对一定范围内其它蚂蚁散布的生物信息激素做出反
应,依据生物信息激素的强度在每一个道口对多条路径选择做出概率上的判断并
执行选择,由此观察并影响它们以后的行为。它由意大利学者 D origo M 等人于 20
世纪 90 年代提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群优
化算法以其分布式并发性、较强的鲁棒性、易于与其他方法相结合等优点引起越
来越多的国内外学者的关注,成为目前国内外研究的热点和前沿问题。
本文在理论上对蚁群算法本身的理论部分进行研究,提出了三点有效的改进
策略,即采用新的初始化信息素矩阵、通过聚类进行局部搜索和混合算法,对蚁
群算法加以改进。在应用方面选取 TSP 问题和交通路径优化问题作为典型的组合
优化问题, 用改进的蚁群算法求解之。仿真结果表明了改进算法的有效性和可行
性。
论文的主要工作概括如下:
(1)在阅读国内外大量文献资料的基础上,总结了当前蚁群算法的研究成果
和亟待解决的问题。本文以研究典型的 N P 难问题——旅行商问题入手,对蚁群优
化算法的发展背景、原理、实现方法和性能作了详细介绍,对该算法本身进行了
深入研究,提出了自己的改进方案并作进行了仿真。
(2)针对蚁群算法存在着搜索时间长、易限于局部最优解等缺陷,提出了一
种改进的蚁群算法。通过在初始化信息素矩阵中采用候选城市列表减少劣质解,
在局部搜索中采用聚类进行二次搜索, 缩小了算法的搜索范围、改善了解空间的
质量,提高了搜索速度。仿真结果表明,改进后的蚁群算法,在 T SP 问题的求解
中,收敛速度和全局寻优能力均得到较大的提高。
(3)针对实际交通中带约束的多目标问题,提出一种基于分层 G A -A S 混合
算法的多目标路径优化方法。该算法通过约束条件对路网进行分层, 遗传算法求
解上层问题,蚁群算法求解下层问题。前者能够从全局角度探索到最优解,但它
无法对探索空间的细节做局部探索;而后者可从局部角度出发趋近最优解,从而
提高算法局部寻优能力。算例仿真结果表明:采用这种算法既具有很强的实际应
用效果,又在很大程度上减少寻优计算次数,提高了算法的性能。
关键词:蚁群算法;旅行商问题;改进算法;多目标交通约束;混合蚁群算法
I
混合蚁群算法及其应用研究
A bstract
A nt colony optim ization algorithm , called ant colony algorithm , is a probabilistic
algorithm for finding the optim al path, w hich used of biological inform ation as the basis for
the ants chose the follow -up actions. Each ant w ill according to the intensity of pherom one at
the intersection and m akes the selection on the probability, w hich to observe and influence
their future behavior. The algorithm is inspired by the foraging behavior of real ants in the
w ild, introduced by D origo M and in the early 1990s. W ith the extraordinary m erits of
distributional concurrency, stronger robustness and bining w ith other algorithm s,
this algorithm attracts m ore and m ore dom estic and foreign scholar's