蚁群算法概述.doc

作业4蚁群算法概述1.蚁群算法的基本思想 现实生活中单个蚂蚁的能力和智力非常简单，但它们能通过相互协调、分工、合作来完成筑巢、觅食、迁徙、清扫蚁穴等复杂行为，尤其是蚂蚁有能力在没有任何可见提示的条件下找到从蚁穴到食物源的最短路径，并且能随环境的变化而变化地搜索新的路径，产生新的选择。这是因为蚂蚁在其走过的路上会分泌一种信息素，其他的蚂蚁能够感知这种物质的存在和强度，并以此指导自己的运动方向，使其倾向于朝着信息素强度高的方向移动。蚁群算法就是从自然界中真实蚂蚁觅食的群体行为中得到启发而提出的。在蚁群算法中，为了实现对真实蚂蚁的抽象，提出了人工蚁的概念。人工蚁和真实蚂蚁有如下相同点：（1）人工蚁和蚂蚁一样，是一群相互合作的个体，每个蚂蚁都能建立一种解决方案，整个蚁群相互合作在全局范围内找出问题的较优的解决方案。（2）人工蚁和真实蚂蚁有着公共的任务，寻找最优路径。（3）人工蚁和真实蚂蚁一样也通过使用信息素进行间接通讯。（4）人工蚁和真实蚂蚁的觅食行为都是一种正反馈过程。（5）在蚁群算法中存在一种信息素的挥发机制，类似于真实世界中的情况，（6）不预测未来状态概率的状态转移策略。人工蚁的策略是充分利用了局部信息，而没有前瞻性的预测未来的状态。图1：二元桥实验初始状态图2：二元桥实验结束状态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 便完成了一次周游，此时蚂蚁 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)，则kij的值为0。kij表示为： (2. 4)其中，Q 为正常数，Lk 表示第 k 只蚂蚁在本次周游中所走过路径的长度。M. Dorigo 提出了 3 种 AS 算法的模型4， 式 (2.4) 称为蚁周系统，另两个模型分别称为蚁量系统和蚁密系统，其差别主要在 (2. 4) 式，即：在蚁量系统模型中为： (2. 5) 在蚁密系统模型中为： (2. 6)AS算法实际上是正反馈原理和启发式算法相结合的一种算法。在选择路径时，蚂蚁不仅利用了路径上的信息素，而且用到了城市间距离的倒数作为启发式因子。实验结果表明，蚁周系统模型比蚁量系统和蚁密系统模型有更好的性能。这是因为蚁周系统型利用全局信息更新路径上的信息素量，而蚁量系统和蚁密系统模型使用局部信息。AS 算法的时间复杂度为(NC*n2*m) ，算法的空间复杂度为S(n)=O(n2)+O(n*m) ，其中 NC 表示迭代的次数，n 为城市数，m为蚂蚁的数目。2.2 蚁群算法的优点与不足众多研究已经证明 AS 算法具有很强的发现较好解的能力，这是因为该算法不仅利用了正反馈原理，在一定程度上可以加快进化过程，而且是一种本质上并行的算法。它有如下优点5：(1) 较强的鲁棒性：对蚁群算法模型稍加修改，便可以应用于其它问题。(2) 分布式计算：蚁群算法是一种基于种群的进化算法，具有本质的并行性，易于实现。(3) 易于与其他方法结合：蚁群算法很容易与多种启发式算法结合，以改善算法的性能。同时它也存在一些缺陷：(1)限于局部最优解，从算法解的性质而言，蚁群算法也是在寻找一个比较好的局部最优解，而不是强求是全局最优解。(2)工作过程的中间停滞问题，和算法开始时收敛速度快一样，在算法工作过程当中，迭代到一定次数后，蚂蚁也可能在某个或某些局部最优解的邻域附近产生停滞。(3)较长的搜索时间，尽管和其他算法相比，蚁群算法在迭代次数和解的质量上都有一定的优势，但对于目前计算机网络的实际情况，还是需要较长的搜索时间。虽然计算机计算速度的提高和蚁群算法的并行性在一定程