蚁群算法课件

蚁群算法(AntColonyOptimization,ACO）

蚁群算法是20世纪90年代意大利学者

Dorigo，．Maniezzo，．Colorni等从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法。DorigoM.,V.Maniezzo&A.Colorni(1996).AntSystem:Optimizationbyacolonyofcooperatingagents.IEEETransactionsonSystems,Man,andCybernetics-PartB,26(1):29-41蚁群算法

90年代Dorigo最早提出了蚁群优化算法---蚂蚁系统（AntSystem,AS）并将其应用于解决计算机算法学中经典的旅行商问题（TSP）。

蚁群算法蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。

蚁群算法蚁群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时．就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激索浓度越低.当后来的蚂蚁再次碰到这个路口的时候．选择激素浓度较高路径概率就会相对较大。蚁群算法

这样形成一个正反馈。最优路径上的激索浓度越来越大．而其它的路径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。

蚁群算法蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。蚁群算法本图为从开始算起，经过18个时间单位时的情形：走BD的蚂蚁到达终点后得到食物又返回了起点A，而ACD的蚂蚁刚好走到D点。蚁群算法假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物，此时ABD的路线往返了2趟，每一处的信息素为4个单位，而ACD的路线往返了一趟，每一处的信息素为2个单位，其比值为2：1。寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD路线上增派一只蚂蚁（共2只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为12和4，比值为3：1。

蚁群算法MarcoDorigo

若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共3只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为24和6，比值为4：1。若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线，而都选择ABD路线。这也就是前面所提到的正反馈效应。

蚁群算法基于以上蚁群寻找食物时的最优路径选择问题，可以构造人工蚁群，来解决最优化问题，如TSP问题。人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的相似之处在于都是优先选择信息素浓度大的路径。较短路径的信息素浓度高，所以能够最终被所有蚂蚁选择，也就是最终的优化结果。两者的区别在于人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。同时，人工蚁群再选择下一条路径的时候是按一定算法规律有意识地寻找最短路径，而不是盲目的。例如在TSP问题中，可以预先知道当前城市到下一个目的地的距离

蚁群算法

Dorigo

與Gambardella在1997年提出人工蚂蚁模拟自然界蚂蚁行为的三大关键特性：1.蚂蚁倾向于选择具有较高費洛蒙浓度的路路径。2.对于较短的路径，其费洛蒙累积的速度较为快速。3.蚂蚁通过费洛蒙达到间接沟通的效果。

蚁群算法旅行商问题（TSP,travelingsalesmanproblem）1960年首先提出。问题描述： 一商人去n个城市销货，所有城市走一遍再回到起点，使所走路程最短。TSP在许多工程领域具有广泛的应用价值 例如电路板布线、VLSI芯片设计、机器人控制、交通路由等。TSP的求解是NP-hard问题。随着城市数目的增多,问题空间将呈指数级增长。蚁群算法

ＴＳＰＬＩＢ中的ＴＳＰ１４原始数据图optimum=30.87504蚁群算法ＡＣＯ算法：１如何选择下一路径转移概率轮盘赌法２信息素的改变挥发因子

蚁群算法k=1whilek<=ItCountdo(执行迭代)fori=1：m(对m只蚂蚁循环)

随机放置m只蚂蚁的起点，为每只蚂蚁建立禁忌表tabuk将各蚂蚁的初始节点置入禁忌表中;forj=２：n(对n个城市循环)

根据轮盘赌法，选择下一个城市j;

将j置入禁忌表tabui,蚂蚁转移到j;

end

end计算每只蚂蚁的路径长度lk;根据公式更新所有蚂蚁路径上的信息素浓度;

k=k+1;endwhile输出找到的最短路径,结束算法

蚁群算法

蚁群算法

蚁群算法蚁群算法蚁群算法适合解决组合优化问题即离散问题的最优化

蚁群算法蚁群算法的缺点：1）收敛速度慢2)局部搜索能力不强2）参数比较敏感

蚁群算法