资源描述：
《蚁群算法的研究与进展》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、蚁群算法的研究与进展摘要：蚁群算法(antcolonyalgorithm(ACA))是一种应用于优化问题的启发式算法，它是受口然界蚂蚁的觅食行为启发而产生的。本文首先介绍了蚁群算法的基本原理和工作机制,然后分别就蚁样算法的理论和应用的研究现状进行了综述，最后是关于蚁群算法的研究展望和而临的挑战，捉出了蚁群算法研究中值得探讨的一些课题。关键字：蚁群算法优化问题1引言90年代初期，Dorigo和他的同事在论文屮提出了解决组合优化问题的一种基于自然的启发式算法——蚁群算法⑴乙3’则。该算法的灵感是真实的蚁群系统。更确切的说，蚁群算法是基于蚂蚁的觅食行为得
2、來的。这种行为的核心是，蚂蚁通过一种叫做费洛蒙的信息索进行间接的交流，这种信息索能使蚂蚁找到蚁巢和食物源之间的最短路径。现实世界的蚁群的这种行为被开发成蚁群算法，其口的是为了解决优化问题。最早的蚁群算法是蚂蚁系^(AntSystem),研究者们根据不同的改进策略对蚂蚁系统进行改进并开发了不同版本的蚁群算法，并成功地应用于优化领域。蚁群算法以其分布式并发性、正反馈、鲁棒性强、收敛速度快、易获得全局最优解等特点引起了越来越多国内外学者的关注，成为目前国内外启发式算法研究的热点和前沿问题。蚁群算法特别适合于在离散优化问题的解空间进行多点非确定性搜索，已经
3、先后被应用到TSP问题、二次分配问题、工件调度问题、图着色问题等多个经典组合优化问题，取得了很好的效果，成为求解组合优化(combinatorialoptimization)等NP-hard问题的一种有潜力的演化算法。2蚁群算法的基本原理2.1蚁群的觅食机理蚁群算法的灵感源泉是真实世界里蚂蚁的觅食行为。蚂蚁是一种社会昆虫，它们群居在一起，它们的行为受群体目标指引，而不是仅仅考虑个体的生存。在寻找食物的过程中，蚂蚁最初以一种随机的方式來寻找位于蚁巢周围的食物。一旦某只蚂蚁找到了一个食物源，它将估计岀食物的数量和质量，并且携带-•些回到蚁巢。在这个返冋
4、的途中，蚂蚁将沿路释放一些信息素。信息素的数量，取决于食物的数量和质量，信息索将会指引其它的蚂蚁去寻找食物源。文献
5、5］已经说明了这种通过信息素的间接交流方式，这种方式是作为一种间接通信來使蚂蚁找到蚁巢和食物源之间的最短路径。2.2蚁群算法的基木原理以求解n个城市的TSP旅行商问题为例说明ACA模型。TSP⑹模型描述的是一个旅行商要通过多个城市的这么一个问题。这个问题的目标是在每个城市通过一次的情况下，旅行商行走的路径要最短。设蚁群中蚂蚁的数量为m,djj(i,j=l,2,…，n)表示城市i和城市jZ间的距离，bi(t)表示t时刻位于城市i的蚂蚁的
6、个数，则有皿=£仲。r,(r)i=l表示t时刻在城市i,j连线上残留的信息量。初始时刻，各条路径上信息量相等,设r..(O)=C(C为常数)。蚂蚁k(k=1,2,•,m)在运动过程中，根据各条[/)]"[订，农tab“*啟)=工［皿)丁［订k^tahu^0,路径上的信息量决定转移方向。掳⑴表示在t时刻蚂蚁I由城市i传移到城市的概率：jetabuk式中:%——先验知识或称为能见度，在TSP问题屮为城市i转移到城Mj的启发信息；a——在路径ij上残留信息的重要程度；B——启发信息的重要程度；tabuk记录蚂蚁I当前所走过的城市，称为记忆列表，k=1,2
7、,…，m,集合tab协随着进化过程作动态调整。经过n个时刻，所有蚂蚁都完成了一次遍历。此时，计算每一只蚂蚁所走过的路径S并保存最短路径厶罰二min仏1,2,…m｝。在蚂蚁完成一次循环以后，各路径上的信息量进行如下调整：r..(r+l)=(l-/7)r..(r)+Ar..式中°w(0,l),表示信息素©随时间的推移而衰减的程度。信息素增量可表示为：△%=工△砖k=l式屮△砖为蚂蚁I在本次循环中在城市i和j之间留下的信息量，它的计算公式根据具体问题而定。Dorigo曾给出M：j3种不同的模型，分别称为Ant-cycleSystem,Ant-Quanti
8、tySystem和Ant-DensitySystem［1］。Ant-cycle同Ant-Quantity,Ant-Density的区别就在于信息素的更新机制，在后两个模型中每只蚂蚁每前进一步都会释放信息素并更新经过路径上的信息素浓度，而前者则只在结束整个循环后才更新。Dorigo对上述3种模型进行多次比较，以Ant-cycleSystem的求解效果最好。3蚁群算法的发展3.1蚁群算法参数设置的研处蚁群算法的参数设置对蚁群算法的性能有着重要的影响。Solnon171分析了信息素相关参数对“勘探”和“开采”的影响，提出了在蚁群算法运行之前加入一个预处理
9、阶段，这个阶段先不使用信息素找到一定数量的路径(即回路)，再从中选择部分路径在算法开始前初始化信息素，获得了较好的效杲。不
