蚁群算法综述，涵盖问题描述和解法
需积分: 0 176 浏览量
2009-09-07
14:56:47
上传
评论
收藏 121KB DOC 举报
蚁群算法综述
摘要：蚁群算法是一种具有许多优良特性的模拟进化算法,已经成功地解决了许多复杂的组
合优化问题。但是蚁群算法并不完善。本文介绍蚁群算法的模型及其存在的问题,并综述蚁
群算法的多种改进形式以及其应用，最后对蚁群算法将来的研究方向作出预测。
关键词：蚁群算法，进化蚁群算法，蚁群算法的应用
Ant Colony Algorithm and Summary
Abstract: Ant colony algorithm is a simulated evolutionary algorithm which shows many excellent characters and
has succeeded in solving many difficult combined optimization problems. However , It is not perfect now. This
paper introduces the models and problems about it, summarizes its improved versions and apply , and forecasts its
future research issues.
Key words: ant colony algorithm; evolutionary ant algorithm; apply of ant algorithm
0 引言
20 世纪90 年代初意大利学者M.Dorigo等
[1,2]
通过模拟蚂蚁搜索路径的行为，提出了
一种新型的仿生优化算法——蚁群算法，并将其应用于经典的旅行商问题( TSP) ,取得了
较好的实验效果, 接着又在二次分配问题(QAP) ,车间任务调度问题(J SP) 等问题中得到了
成功的应用。蚁群算法采用了正反馈并行自催化机制，具有较强的鲁棒性、优良的分布式
计算机制、易于与其他方法结合的优点，在短期内得到了很大发展，其应用领域也不断得
到扩展，显示了其在求解复杂的组合优化问题方面已展现出其优异的性能和巨大的发展潜
力。同时由于蚁群算法收敛速度慢，容易发生停滞，易于陷入局部最优解等不足，国内外
专家学者对其进行了不断的改进，提高了算法的性能。
1 蚁群算法的模型
研究表明:蚂蚁在觅食途中,能够在所经过的路径上留下一种挥发性分泌物- 信息素,并
能够感知这种物质的存在及其强度,朝着这种物质强度高的方向移动,强度越高的路径,选择
它的蚂蚁越多,越发增加该路径的信息素强度,这样又将吸引更多的蚂蚁,从而形成一种正反
馈,蚂蚁最终可以发现蚁巢与食物之间的最短路径。通常用求解n 个城市的TSP 问题(寻找
一条经过各城市一次且回到原出发城市的最短路径) 说明蚁群算法的模型。
引入如下标记: n 表示城市个数, m 表示蚂蚁数量, d
ij
表示城市i 和城市j 之间距离,
评论0