蚁群算法概述

《蚁群算法概述》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、作业4蚁群算法概述1.蚁群算法的基本思想现实生活中单个蚂蚁的能力和智力非常简单，但它们能通过相互协调、分工、合作来完成筑巢、觅食、迁徙、清扫蚁穴等复杂行为，尤其是蚂蚁有能力在没有任何可见提示的条件下找到从蚁穴到食物源的最短路径，并且能随环境的变化而变化地搜索新的路径，产生新的选择。这是因为蚂蚁在其走过的路上会分泌一种信息素，其他的蚂蚁能够感知这种物质的存在和强度，并以此指导自己的运动方向，使其倾向于朝着信息素强度高的方向移动。蚁群算法就是从自然界中真实蚂蚁觅食的群体行为中得到启发而提出的。在蚁群算法中，为了实现对真实蚂蚁的抽象，提出了人工

2、蚁的概念。人工蚁和真实蚂蚁有如下相同点：（1）人工蚁和蚂蚁一样，是一群相互合作的个体，每个蚂蚁都能建立一种解决方案，整个蚁群相互合作在全局范围内找出问题的较优的解决方案。（2）人工蚁和真实蚂蚁有着公共的任务，寻找最优路径。（3）人工蚁和真实蚂蚁一样也通过使用信息素进行间接通讯。（4）人工蚁和真实蚂蚁的觅食行为都是一种正反馈过程。（5）在蚁群算法中存在一种信息素的挥发机制，类似于真实世界中的情况，（6）不预测未来状态概率的状态转移策略。人工蚁的策略是充分利用了局部信息，而没有前瞻性的预测未来的状态。图1：二元桥实验初始状态图2：二元桥实验结

3、束状态2.蚁群算法基本原理蚁群算法[3]可以表述如下：初始时刻，各条路径上的信息素量相等，设τij(0)=C（C为常数），蚂蚁k（k=1,2,3,…,m）在运动过程中根据各条路径上的信息量决定转移方向。蚂蚁系统所使用的转移规则被称为随机比例规则，在时刻t，蚂蚁k从城市i选择城市j的转移概率(t)为：(2.1)其中，Jk(i)={1，2，……，n}-tabuk表示蚂蚁k下一步允许选择的城市。列表tabuk记录了蚂蚁k在本次迭代中已经走过的城市，不允许该蚂蚁在本次循环中再经过这些城市。当所有n座城市都加入到tabuk中时，蚂蚁k便完成了一次周

4、游，此时蚂蚁k所走过的路径便是TSP问题的一个可行解。(2.1)式中的ηij是一个启发式因子，被称为能见度因子。在AS算法中，ηij通常取城市i与城市j之间距离的倒数。α和β分别反映了在蚂蚁的运动过程中已积累的信息和启发信息的相对重要程度。当所有蚂蚁完成一次周游后，各路径上的信息素根据（2.2）式更新。(2.2)(2.3)其中ρ(0<ρ<1)表示路径上信息素的挥发系数，1-ρ表示信息素的持久系数；△τij表示本次迭代边(ij)上信息素的增量。△τkij表示第k只蚂蚁在本次迭代中留在边(ij)上的信息素量。如果蚂蚁k没有经过边(ij)，则△

5、τkij的值为0。△τkij表示为：(2.4)其中，Q为正常数，Lk表示第k只蚂蚁在本次周游中所走过路径的长度。M.Dorigo提出了3种AS算法的模型[4]，式(2.4)称为蚁周系统，另两个模型分别称为蚁量系统和蚁密系统，其差别主要在(2.4)式，即：在蚁量系统模型中为：(2.5)在蚁密系统模型中为：(2.6)AS算法实际上是正反馈原理和启发式算法相结合的一种算法。在选择路径时，蚂蚁不仅利用了路径上的信息素，而且用到了城市间距离的倒数作为启发式因子。实验结果表明，蚁周系统模型比蚁量系统和蚁密系统模型有更好的性能。这是因为蚁周系统型利用全

6、局信息更新路径上的信息素量，而蚁量系统和蚁密系统模型使用局部信息。AS算法的时间复杂度为Ο(NC*n2*m)，算法的空间复杂度为S(n)=O(n2)+O(n*m)，其中NC表示迭代的次数，n为城市数，m为蚂蚁的数目。2.2蚁群算法的优点与不足众多研究已经证明AS算法具有很强的发现较好解的能力，这是因为该算法不仅利用了正反馈原理，在一定程度上可以加快进化过程，而且是一种本质上并行的算法。它有如下优点[5]：(1)较强的鲁棒性：对蚁群算法模型稍加修改，便可以应用于其它问题。(2)分布式计算：蚁群算法是一种基于种群的进化算法，具有本质的并行性，

7、易于实现。(3)易于与其他方法结合：蚁群算法很容易与多种启发式算法结合，以改善算法的性能。同时它也存在一些缺陷：(1)限于局部最优解，从算法解的性质而言，蚁群算法也是在寻找一个比较好的局部最优解，而不是强求是全局最优解。(2)工作过程的中间停滞问题，和算法开始时收敛速度快一样，在算法工作过程当中，迭代到一定次数后，蚂蚁也可能在某个或某些局部最优解的邻域附近产生停滞。(3)较长的搜索时间，尽管和其他算法相比，蚁群算法在迭代次数和解的质量上都有一定的优势，但对于目前计算机网络的实际情况，还是需要较长的搜索时间。虽然计算机计算速度的提高和蚁群算

8、法的并行性在一定程度上可以缓解这一问题，但是对于大规模复杂的计算机网络，这还是一个很大的障碍。基本蚁群算法在解决一些小规模的TSP问题时的表现尚可令人满意。但是随着问题规模的增大，蚂蚁系统难以