智能算法之蚁群算法

1、蚁群算法陈华2010-9Macro Dorigo 1992年，意大利学者MDorigo在他的博士论文中引入蚁群算法，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。通过对这种行为的模拟，提出来一种新型的模拟进化算法 蚁群算法。目前，蚁群算法已经是群智能理论研究领域的一种主要算法。算法背景3AC4AC5AC6蚁群算法原理 蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正

2、反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。 7蚁群算法原理 为了说明蚁群算法的原理，先简要介绍一下蚂蚁搜寻食物的具体过程。在蚁群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时，就随机地挑选一条路径前行，与此同时释放出与路径长度有关的信息素。路径越长，释放的激索浓度越低，当后来的蚂蚁再次碰到这个路口的时候，选择激素浓度较高路径概率就会相对较大，这样形成一个正反馈。最优路径上的激索浓度越来越大，而其它的路径上激素浓度却会随着时间的流逝而消减，最终整个蚁群会找出最优路径。8简

3、化的蚂蚁寻食过程 蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。9简化的蚂蚁寻食过程 本图为从开始算起，经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。10简化的蚂蚁寻食过程 假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物，此时ABD的路线往返了2趟，每一处的信息素为4个单位，而 ACD的路

4、线往返了一趟，每一处的信息素为2个单位，其比值为2：1。 寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD路线上增派一只蚂蚁（共2只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为12和4，比值为3：1。 若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共3只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为24和6，比值为4：1。 若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线，而都选择ABD路线。这也就是前面所提到的正反馈效应。11自然蚁群与人工蚁群算法 基于以上蚁群寻找食物时的最优路径选择问

5、题，可以构造人工蚁群，来解决最优化问题，如TSP问题。 人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的相似之处在于都是优先选择信息素浓度大的路径。较短路径的信息素浓度高，所以能够最终被所有蚂蚁选择，也就是最终的优化结果。 两者的区别在于人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。同时，人工蚁群再选择下一条路径的时候是按一定算法规律有意识地寻找最短路径，而不是盲目的。例如在TSP问题中，可以预先知道当前城市到下一个目的地的距离。12蚁群算法与TSP问题TSP问题表示为一个N个城市的有向图G=（N，A），其中城市之间距离目标函数为 ，其中 为城市1,2，n的一个排列， 。, |j),

6、(iA n1,2,.,NNjinnijd)(nliilldwf11)(),(21niiiw11iin13蚁群算法与TSP问题 TSP问题的人工蚁群算法中，假设m只蚂蚁在图的相邻节点间移动，从而协作异步地得到问题的解。每只蚂蚁的一步转移概率由图中的每条边上的两类参数决定：1.信息素值，也称信息素痕迹。2.可见度，即先验值。 信息素的更新方式有2种，一是挥发，也就是所有路径上的信息素以一定的比率进行减少，模拟自然蚁群的信息素随时间挥发的过程；二是增强，给评价值“好”(有蚂蚁走过)的边增加信息素。14蚁群算法与TSP问题 蚂蚁向下一个目标的运动是通过一个随机原则来实现的，也就是运用当前所在节点存储的

7、信息，计算出下一步可达节点的概率，并按此概率实现一步移动，逐此往复，越来越接近最优解。 蚂蚁在寻找过程中，或者找到一个解后，会评估该解或解的一部分的优化程度，并把评价信息保存在相关连接的信息素中。15otherwise 0allowed if )(allowed)()(jtpjijijijijttkij),()()(ijntttntijij轨迹更新:Visibility: ij = 1/dij蚁群算法的计算流程表示轨迹的相对重要性表示能见度的相对重要性轨迹的持久性ij表示第K只蚂蚁在本次循环中留在路径ij上的信息量计算结果10城市TSP问题20城市TSP问题计算结果30城市TSP问题48城市T

8、SP问题连续蚁群算法 从上面可以看出，蚁群算法比较显著的特点是：整个算法过程更适用于离散对象问题。在算法求解组合优化问题过程中，路径是离散和有限的路径，蚂蚁的每一步选择都是在离散值中进行的。这一特点使得将蚁群算法直接应用于一般常规的连续对象优化问题存在一定的困难。 应用蚁群算法求解连续对象优化问题，目前的处理方法大致为: 1.将解空间的每一个分量分成许多小区间，这样整个解空间被分成许多小多面体，将每个多面体看为一个节点，然后用人工蚂蚁在这些节点之间行走最后找到最优解。 2.在解空间中随机生成一些蚂蚁，每个蚂蚁表示一个解，并构成一个区域，根据蚂蚁的评价值，可将这些区域分成优势区和劣势区，劣势区的蚂蚁会按一定概率原则向优势区移动，直到所有蚂蚁都移动到优势区。这类处理方法我们认为己经不是原本意义上的蚁群算法，其实质是模拟了生态环境的一种宏观演化过程。20 蚁群优化算法参考书1蚁群算法及其应用.李士勇.哈工大出版社 国内首部蚁群算法的专著，系统地阐述蚁群算法的基本原理、基本蚁群算法及改进算法，蚁群算法与遗传、免疫算法的融合，自适应蚁群算法，并行蚁群算法，蚁群算法的收敛性与理论模型及其在优化问题中的应用。本书可供人工智能、计算机科学、信息科学、控制工程、管理工程、交通工程、网络工程、智能优化算法及智能自动化等领域的广大师生和科技