蚁群算法原理介绍

1、大 纲 蚁群算法的起源 蚁群行为描述 蚁群算法的基本思想 基本蚁群算法的系统学特征 TSP问题描述 基本蚁群算法的数学模型 基本蚁群算法的应用举例 总结蚁群算法起源蚁群算法起源蚁群算法蚁群算法(ant colony optimization, ACO)：Dorigo M于于1991年提出，其灵感来源于蚂蚁年提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。在寻找食物过程中发现路径的行为。 通过模拟通过模拟自然界蚂蚁搜索路径的行为，提出来一种新型自然界蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法。的模拟进化算法。TSP问题、分配问题、问题、分配问题、job-shop调度问题调度问题蚁群行

2、为描述蚁群行为描述CBEF3030AD蚁穴蚁穴食物源食物源d=1d=1d=0.5d=0.5ADCBEF303015151515释放信息素与路径长度成反比释放信息素与路径长度成反比蚁群行为描述蚁群行为描述ADCBEF303010102020ADCBEF30303030信息量大，路径被选概率大信息量大，路径被选概率大基本蚁群算法的机制原理基本蚁群算法的机制原理ADCBEF303015151515ADCBEF30303030路径路径BFC：蚂蚁增加，信息量增加，路径被选择的机率增加；：蚂蚁增加，信息量增加，路径被选择的机率增加；路径路径BEC：时间增加，：时间增加，信息量减少，路径被选择的机率减小。

3、信息量减少，路径被选择的机率减小。基本蚁群算法的系统学特征基本蚁群算法的系统学特征蚁群算法是一个系统蚁群算法是一个系统分布式计算分布式计算自组织自组织正反馈正反馈蚁群算法是一个系统蚁群算法是一个系统Bertalanffy L V： 系统可以确定为处于一定的相互关系中系统可以确定为处于一定的相互关系中并与环境发生关系的各组成部分（要素）的并与环境发生关系的各组成部分（要素）的综合体。综合体。多元性多元性 整体性整体性 相关性相关性 系统特征系统特征蚂蚁的个体行为是系统的元素蚂蚁的个体行为是系统的元素蚁群行为的相互影响蚁群行为的相互影响蚁群能完成个体完蚁群能完成个体完成不了的任务成不了的任务整体大

4、于部分之和整体大于部分之和蚁群算法满足分布式计算蚁群算法满足分布式计算分布式系统：依赖于个体行为，但并不单独依赖于分布式系统：依赖于个体行为，但并不单独依赖于每一个体的行为。每一个体的行为。在蚁群中，许多蚂蚁都为共同目的进行着同样的工在蚁群中，许多蚂蚁都为共同目的进行着同样的工作，而最终任务的完成不会由于某些个体（蚂蚁）作，而最终任务的完成不会由于某些个体（蚂蚁）的缺陷而受到影响。的缺陷而受到影响。蚁群算法具有自组织的特征蚁群算法具有自组织的特征系统外部系统外部系统内部系统内部组织行为组织行为他组织他组织自组织自组织自组织：在没有外界作用自组织：在没有外界作用下使得系统熵增加的组织下使得系统熵

5、增加的组织无序无序有序有序蚁群算法具有正反馈的特征蚁群算法具有正反馈的特征削弱未来行为削弱未来行为加强未来行为加强未来行为反馈反馈负反馈负反馈正反馈正反馈在蚁群中，在蚁群中，信息素的堆积信息素的堆积就是一个正反馈就是一个正反馈自组织是正反馈和负反馈的结合自组织是正反馈和负反馈的结合自组织自组织负反馈负反馈正反馈正反馈缩小搜索范围缩小搜索范围保持搜索范围保持搜索范围TSP描述描述TSP问题（问题（Traveling Salesman Problem）：）：即旅行商问题，是数学领域中著名问题之一。假设即旅行商问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访有一个旅行商人要拜访N个城市，他必

6、须选择所要个城市，他必须选择所要走的路径，路径的限制是走的路径，路径的限制是每个城市只能拜访一次，每个城市只能拜访一次，而且最后要回到原来出发的城市而且最后要回到原来出发的城市。路径的选择目标。路径的选择目标是要求得的路径路程为所有路径之中的是要求得的路径路程为所有路径之中的最小值最小值。ATSP的目的的目的Hamilton圈圈TSP数学语言描述数学语言描述有向图：有向图：给定一个有向图给定一个有向图 的三元组为的三元组为 ，其，其中中 是一个非空集合，其元素称为有向图的是一个非空集合，其元素称为有向图的结点结点 ； 是一个集合，其元素称为有向图的是一个集合，其元素称为有向图的弧段，弧段， 是

7、从是从 到到 上的一个映射（函数）上的一个映射（函数）一个一个 有向图有向图 ，可简记为，可简记为 D),(fEVVfVV ED),(EVETSP描述描述TSP：设设 是是 个城市的集合，个城市的集合， 是集合是集合 中元素两两连中元素两两连接的集合，接的集合， 是是 的的Euclidean距离，即距离，即)()(22yyxxdjijiijcccnC,21nCCLccljiij,), 2 , 1,(njidijlijC1C2C3CnLij基本蚁群算法的数学模型基本蚁群算法的数学模型 ：TSP的规模的规模 ：蚁群中蚂蚁总数目，：蚁群中蚂蚁总数目， ： 次循环次循环 上的残留信息量的集合上的残留信

8、息量的集合 ：禁忌表：禁忌表 ：状态转移概率：状态转移概率 ：在初始时刻各条路径上的信息：在初始时刻各条路径上的信息量相等量相等niitmb1)(nmCtccjiij,)(stijcon)0(t)(tPkij), 2 , 1(tabumkklij基本蚁群算法的数学模型基本蚁群算法的数学模型allowedkj，若，否则 0allowedisisijijkstt)() 1()() 1()(tPkij信息启发式因子:期望启发式因子:dijij1基本蚁群算法的数学模型基本蚁群算法的数学模型)()()1 () 1(tttijijij ：挥发系数：挥发系数 ：信息素残留因子：信息素残留因子1)()(1tt

9、mkkijij) 1(tkijLkQ0信息素更新策略YesNo输输出出程程序序计计算算结结果果结结束束按按照照公公式式进进行行信信息息素素更更新新满满足足结结束束条条件件？蚂蚂蚁蚁k=k+1开开始始初初始始化化迭迭代代次次数数N=N+1 蚂蚂蚁蚁k=1按按照照状状态态转转移移概概率率公公式式选选择择下下一一个个城城市市修修改改禁禁忌忌表表蚂蚂蚁蚁总总数数？NoYes蚂蚁图的蚁群系统（GBAS）可以验证，下式满足：即 是一个随机矩阵。( )k( , )( )1,0iji jAkk 四个城市的非对称TSP问题，距离矩阵和城市图示如下：010.511011()1.55011110ijDd2.2.5

10、初始的蚁群优化算法基于图的蚁群系统（GBAS）假设共4只蚂蚁，所有蚂蚁都从城市A出发，挥发因子 。此时，观察GBAS的计算过程。 矩阵共有12条弧，初始信息素记忆矩阵为：1,1,2,32kk01 121 121 121 1201 121 12(0)(0)1 121 1201 121 121 121 120ij2.2.5 初始的蚁群优化算法基于图的蚁群系统（GBAS）执行GBAS算法的步骤2，假设蚂蚁的行走路线分别为：当前最优解为，这个解是截止到当前的最优解，碰巧是实际最优解1:,(1)4;2:,(2)3.5;3:,(3)8;4:,(4)4.5;WABCDA f WWACDBA f WWADCB

11、A f WWABDCA f W第一只第二只第三只第四只2.2.5 初始的蚁群优化算法基于图的蚁群系统（GBAS）按算法步骤3的信息素更新规则，得到更新矩阵这是第一次外循环结束的状态。01 241 61 241 601 241 24(1)(1)1 241 1201 61 241 61 240ij2.2.5 初始的蚁群优化算法基于图的蚁群系统（GBAS）重复外循环，由于上一次得到的W2已经是全局最优解，因此按算法步骤3的信息素更新规则，无论蚂蚁如何行走，都只是对W2路线上的城市信息素进行增强，其他的城市信息素进行挥发。得到更新矩阵这是第一次外循环结束的状态。01 485 241 485 2401 481 48(2)(2)1 481 4805 241 485 241 480ij2.2.5 初始的蚁群优化算法基于图的蚁群系统（GBAS）重复外循环，由于W2全局最优解，GBAS只记录第一个最优解，因此一但得到了全局最优解，信息素的更新将不再依赖于以群的行走路线，而只是不断增强最优路线的信息素，同时进行挥发。第三次外循环后得到的信息素矩阵为：01 9611 481 9611 4801 961 96(3)(3)1 961 96011 481 9611 481 960ij2.2.5 初始的蚁群优化算法基于图的蚁群系统（GBAS） 蚂蚁以一定的概率从城市i到城市j进行转移，信息