第5章 蚁群算法

1、5 蚁群算法蚁群算法 Ant Colony Optimization 2 3 目录目录 1、蚁群算法起源、蚁群算法起源 2、蚁群算法模型、蚁群算法模型 3、实例仿真、实例仿真 4、蚁群算法特点、蚁群算法特点 5、总结、总结 双桥实验双桥实验 l蚁群优化（ant colony optimization,ACO）是20世纪90年代 初由意大利学者M.Dorigo等通过模拟 蚂蚁的行为而提出的一种随机优化技 术（寻找优化路径的机率型算法）。 l研究主要是以蚂蚁寻找食物之后能选 择一条最短路径来连接蚁穴和食物源。 l1991年，M.Dorigo在法国巴黎第一 届欧洲人工生命会议上最早提出了蚁 群算法的

2、基本模型，1992年又在其博 士论文中进一步阐述了蚁群算法的核 心思想。 Macro Dorigo 1.蚁群算法起源蚁群算法起源 蚂蚁觅食过程蚂蚁觅食过程 在蚁群寻找食物时，能够在它所经过的路径上留下在蚁群寻找食物时，能够在它所经过的路径上留下 一种称之为一种称之为(pheromone)的物质进行信息的物质进行信息 传递，而且蚂蚁在运动过程中能够感知这种物质，传递，而且蚂蚁在运动过程中能够感知这种物质， 并以此指导自己的运动方向，因此由大量蚂蚁组并以此指导自己的运动方向，因此由大量蚂蚁组 成的蚁群集体行为便表现出一种信息成的蚁群集体行为便表现出一种信息： 某一路径上走过的蚂蚁越多，则后来者选择

3、该路径某一路径上走过的蚂蚁越多，则后来者选择该路径 的概率就越大。的概率就越大。最优路径上的信息素浓度越来越最优路径上的信息素浓度越来越 大，而其它的路径上激素浓度却会随着时间的流大，而其它的路径上激素浓度却会随着时间的流 逝而消减。最终整个蚁群会找出最优路径。逝而消减。最终整个蚁群会找出最优路径。 A点为蚁穴，食物在点为蚁穴，食物在D点，可能随机选择路线点，可能随机选择路线ABD或或 ACD。假设初始时每条路线有一只蚂蚁，每个时。假设初始时每条路线有一只蚂蚁，每个时 间单位行走一步，本图为经过间单位行走一步，本图为经过9个时间单位时的情个时间单位时的情 形：走形：走ABD的蚂蚁到达食物，而走

4、的蚂蚁到达食物，而走ACD的蚂蚁刚的蚂蚁刚 好走到好走到C点，为一半路程。点，为一半路程。 简化的蚂蚁寻食过程简化的蚂蚁寻食过程 本图为从开始算起，经过本图为从开始算起，经过18个时间单位时的个时间单位时的 情形：走情形：走ABD的蚂蚁到达的蚂蚁到达D点后得到食物又返回点后得到食物又返回 了起点了起点A，而走，而走ACD的蚂蚁刚好走到的蚂蚁刚好走到D点。点。 假设蚂蚁每经过一处所留下的信息素为一个单位，假设蚂蚁每经过一处所留下的信息素为一个单位， 则经过则经过36个时间单位后，个时间单位后，ABD的路线往返了的路线往返了2趟，每一趟，每一 处的信息素为处的信息素为4个单位，而个单位，而 ACD

5、的路线往返了一趟，每的路线往返了一趟，每 一处的信息素为一处的信息素为2个单位，其比值为个单位，其比值为2：1。 按信息素的指导，按信息素的指导，ABD路线增加一只蚂蚁（共路线增加一只蚂蚁（共2 只），只），ACD路线仍为一只蚂蚁。再经过路线仍为一只蚂蚁。再经过36个时间单位后，个时间单位后， 两条线路上的信息素为两条线路上的信息素为12和和4，比值为，比值为3：1。 于是，于是， ABD路线增加一只蚂蚁（共路线增加一只蚂蚁（共3只），只），ACD路路 线仍为一只蚂蚁。再经过线仍为一只蚂蚁。再经过36个时间单位后，两条线路上个时间单位后，两条线路上 的信息素为的信息素为24和和6，比值为，比值

6、为4：1。 若继续进行，则按信息素的指导，最终所有的蚂蚁若继续进行，则按信息素的指导，最终所有的蚂蚁 会放弃会放弃ACD路线，而都选择路线，而都选择ABD路线。路线。 l蚁群算法通常用于求解复杂的蚁群算法通常用于求解复杂的组合优化问题组合优化问题。所谓组合优。所谓组合优 化化,是指在离散的、有限的数学结构上是指在离散的、有限的数学结构上,寻找一个满足给定寻找一个满足给定 条件条件,并使其目标函数值达到最大或最小的解并使其目标函数值达到最大或最小的解. 理论假设理论假设 1、蚁群之间通过信息素和环境进行通信。、蚁群之间通过信息素和环境进行通信。 2、蚂蚁对环境的反应由其内部模式决定。、蚂蚁对环境

7、的反应由其内部模式决定。 3、个体水平上，每个蚂蚁相对独立；群体水平、个体水平上，每个蚂蚁相对独立；群体水平 上，每只蚂上，每只蚂 蚁的行为是随机的。蚁的行为是随机的。 2.蚁群算法模型蚁群算法模型 算法规则算法规则 12 1.范围范围 l蚂蚁观察到的范围是一个方格世界，蚂蚁有 一个参数为速度半径（一般是3），那么它能 观察到的范围就是3*3个方格世界，并且能移 动的距离也在这个范围之内。 13 2.环境环境 l蚂蚁所在的环境是一个虚拟的世界，其中有障 碍物，有别的蚂蚁，还有信息素，信息素有两 种，一种是找到食物的蚂蚁洒下的食物信息素 ，一种是找到窝的蚂蚁洒下的窝的信息素。每 个蚂蚁都仅仅能感

8、知它范围内环境信息。环境 以一定的速率让信息素消失 。 14 3.觅食规则觅食规则 在每只蚂蚁能感知的范围内寻找是否有食 物，如果有就直接过去。否则看是否有信息素 ，并且比较在能感知的范围内哪一点的信息素 最多，这样，它就朝信息素多的地方走，并且 每只蚂蚁都会以小概率犯错误，从而并不是往 信息素最多的点移动。蚂蚁找窝的规则和上面 一样，只不过它对窝的信息素做出反应，而对 食物信息素没反应。 15 4.移动规则移动规则 l每只蚂蚁都朝向信息素最多的方向移，并且 ，当周围没有信息素指引的时候，蚂蚁会按照 自己原来运动的方向惯性的运动下去，并且， 在运动的方向有一个随机的小的扰动。为了防 止蚂蚁原地

9、转圈，它会记住最近刚走过了哪些 点，如果发现要走的下一点已经在最近走过了 ，它就会尽量避开。 16 5.避障规则避障规则 l如果蚂蚁要移动的方向有障碍物挡住，它会 随机的选择另一个方向，并且有信息素指引的 话，它会按照觅食的规则行为。 17 6.播撒信息素规则播撒信息素规则 l每只蚂蚁在刚找到食物或者窝的时候撒发的 信息素最多，并随着它走远的距离，播撒的信 息素越来越少。 l现以平面上现以平面上n个城市的旅行商问题（个城市的旅行商问题（ Traveling Salesman Problem ，TSP）为例说明基本蚁群算法模型。）为例说明基本蚁群算法模型。 l旅行商问题：一商人去旅行商问题：一商

10、人去n个城市销货，所有城市走一遍再个城市销货，所有城市走一遍再 回到起点，使所走路程最短。回到起点，使所走路程最短。 lTSP在许多工程领域具有广泛的应用价值，例如电路板布在许多工程领域具有广泛的应用价值，例如电路板布 线、线、VLSI芯片设计、机器人控制、网络路由等。随着城芯片设计、机器人控制、网络路由等。随着城 市数目的增多市数目的增多,问题空间将呈指数级增长。问题空间将呈指数级增长。 TSP问题的数学描述问题的数学描述 TSP问题表示为一个问题表示为一个N个城市的有向图个城市的有向图G=（N，A），其中），其中 城市之间距离城市之间距离 目标函数为目标函数为 其中，其中， ，为城市，为城

11、市1,2，nn的的 一个排列，一个排列， 。 , |j), (iA n1,2,.,NNji () ijn n Dd n l ii ll dwf 1 1 )( ),( 21n iiiw 11 iin 蚁群算法求解蚁群算法求解TSP l下面以下面以TSPTSP为例说明基本蚁群算法模型。为例说明基本蚁群算法模型。 l首先将首先将m m只蚂蚁随机放置在只蚂蚁随机放置在n n个城市，通常个城市，通常 ： ，m m只蚂蚁同时由一个城市运动到只蚂蚁同时由一个城市运动到 下一个城市，逐步完成它们的搜索过程。下一个城市，逐步完成它们的搜索过程。 整个算法的迭代过程以整个算法的迭代过程以N N为刻度，为刻度， ，

12、 为预设的最大迭代次数。每次迭代过为预设的最大迭代次数。每次迭代过 程中以程中以t t为刻度，为刻度， ，蚂蚁，蚂蚁k k根据概率根据概率 转换规则选择下一个城市，由此生成一个转换规则选择下一个城市，由此生成一个 由由n n个城市组成的行动路线，并伴随信息素个城市组成的行动路线，并伴随信息素 的更新。的更新。 max 1NN max N 0tn mn （2）能见度）能见度 定义为距离的倒数，即定义为距离的倒数，即 代表由城市代表由城市i到城市到城市j的的启发性愿望启发性愿望，距离越短，能见度越，距离越短，能见度越 大，被选择的愿望越大，由此引导蚂蚁搜索。其信息是固大，被选择的愿望越大，由此引导

13、蚂蚁搜索。其信息是固 定的。定的。 （3）虚拟信息素）虚拟信息素 当由城市当由城市i选择城市选择城市j后，将在后，将在ij路径上留下虚拟信息素路径上留下虚拟信息素 ，代表由城市，代表由城市i到到j的的获知性愿望获知性愿望，是动态的全局信息，在线，是动态的全局信息，在线 实时更新。实时更新。 1 ij ij d ij 蚂蚁蚂蚁k由城市由城市i转到城市转到城市j的决定因素：的决定因素： （1）禁忌列表）禁忌列表 该表用于存储第该表用于存储第k只蚂蚁在当前时刻已访问过的所有城市，只蚂蚁在当前时刻已访问过的所有城市， 每只蚂蚁在选择下一个城市前，先检索该表来确定下一步每只蚂蚁在选择下一个城市前，先检索

14、该表来确定下一步 可能选择的城市是否已经走过，如果走过就不在选择范围可能选择的城市是否已经走过，如果走过就不在选择范围 内，这样可以避免重复访问同一个城市。内，这样可以避免重复访问同一个城市。 信息素更新方式体现在信息素的增加和信息素的挥发两个 方面。挥发系数 信息素更新公式如下： 1 (1)(1)( )( ) ( )( ) ijijij m k ijij k ttt tt /( ),tkij ( ) 0 k k ij Q L t t 如果 时刻蚂蚁 由城市 选择了城市 ，否则 表示当m个蚂蚁都选择了下一个城市后，所有选择由i到j的 蚂蚁在该路径上遗留的信息素之和 表示第k只蚂蚁在路径ij上留

15、下的信息素 为预设参数，表示信息素的强度 表示第k只蚂蚁在t时刻选择城市j后经过的所有城市构成的 路径长度 ( ) ij t ( ) k ij t Q ( ) k L t 其中：其中： 表示表示ijij路径上的路径上的信息素浓度信息素浓度； 是是启发信息启发信息，能见度能见度； 和和反映了信息素与启发信息的相对重要性；反映了信息素与启发信息的相对重要性； 表示蚂蚁表示蚂蚁k k已经访问过的城市列表，已经访问过的城市列表，禁忌列表禁忌列表。 ( ) , ( ) ( ) 0, k ijij k k ilil ij l tabu t if jtabu t pt otherwise 1/ ijij d

16、 ( ) ij t k tabu （4 4）概率转换规则）概率转换规则 位于城市位于城市i i的第的第k k只蚂蚁选择下一个城市只蚂蚁选择下一个城市j j的概率为的概率为: : 注意：处在同一城市注意：处在同一城市i的两只蚂蚁，即使都按照上述概率选的两只蚂蚁，即使都按照上述概率选 择下一个城市，结果也可能是不同的。择下一个城市，结果也可能是不同的。 系统在上述四个因素（系统在上述四个因素（禁忌列表、能见度、虚拟禁忌列表、能见度、虚拟 信息素、概率转换规则信息素、概率转换规则）的控制下，实现路径）的控制下，实现路径 选择策略和信息素更新策略。选择策略和信息素更新策略。 上述信息素更新方式与真实蚂

17、蚁觅食过程最为接上述信息素更新方式与真实蚂蚁觅食过程最为接 近，但是在解决近，但是在解决TSPTSP问题上，效果并不是特别问题上，效果并不是特别 理想。理想。 DorigoDorigo针对信息素更新策略又给出了三种模型。针对信息素更新策略又给出了三种模型。 蚁量系统（蚁量系统（Ant-Quantity） 蚁密系统（蚁密系统（Ant-Density） 蚁周系统（蚁周系统（Ant-Cycle） 三种模型三种模型 它们的差别在于表达式它们的差别在于表达式 的不同的不同( (即更新信息素的即更新信息素的 方式和更新量不同方式和更新量不同) )。 ij Ant-Quantity和和Ant-Density

18、模型都是利用模型都是利用局部信息局部信息， 即即m个蚂蚁都各自选完下一城市后，就对所走路径并个蚂蚁都各自选完下一城市后，就对所走路径并 行进行信息素更新，两者的区别仅仅在于更新的信息行进行信息素更新，两者的区别仅仅在于更新的信息 素量有所不同。素量有所不同。 Ant-Cycle模型是模型是所有蚂蚁选择完所有城市所有蚂蚁选择完所有城市完成一次迭完成一次迭 代后，更新所有路径上的信息素，并且每只蚂蚁经过代后，更新所有路径上的信息素，并且每只蚂蚁经过 的路径所更新的信息素是相同的。的路径所更新的信息素是相同的。 蚁量算法蚁量算法（ Ant-Quantity ）：）： tkij ( ) 0 k i j

19、 ij Q d t ，若 时刻，蚂蚁 由城市 选择了城市 ，否则 蚁密算法蚁密算法（ Ant-Density ）：）： 蚁周算法蚁周算法（ Ant-Cycle ）：）： 1 (1)(1)()() ()() ijijij m k ijij k NNN NN /,kNij () 0 k k ij Q L N 如果第 只蚂蚁在第 次循环中经过路径 ，否则 Qtkij ( ) 0 k ij t ，若 时刻，蚂蚁 由城市 选择了城市 ，否则 27 通过实验表明，在这三种算法中：通过实验表明，在这三种算法中： Ant-CycleAnt-Cycle算法的效果最好，这是因为它算法的效果最好，这是因为它 用的是

20、全局信息；而其余两种算法用的用的是全局信息；而其余两种算法用的 是局部信息。这种更新方法很好地保证是局部信息。这种更新方法很好地保证 了残留信息不至于无限累积，非最优路了残留信息不至于无限累积，非最优路 径会逐渐随时间推移被忘记径会逐渐随时间推移被忘记。 TSP算法流程图算法流程图（ Ant-Cycle Ant-Cycle ） k是否等于m t是否等于n N是否等于Nmax 根据公式更新信息素 记录当前最优路径T+和最优路径 长度L+禁忌表清零 输出最优路径T+和最优路径长度L+ 结束 设置参数各个参数，并计算各个城市之间 的距离，生成距离矩阵D，生成禁忌列表及 存储最优路径和最优路径长度的矩

21、阵T+和L+ 开始 将m个蚂蚁随机分布到n个城市，并将蚂蚁 所在的位置存储到禁忌表中，并令N=0 令t=0,N=N+1 令k=0,t=t+1 令k=k+1 第k个蚂蚁根据公式选择下一个 城市，并更新禁忌表 N N N Y Y Y 蚁群算法的误区与对策蚁群算法的误区与对策 29 误区一：利用最大概率确定被选城市。误区一：利用最大概率确定被选城市。 s4 0.31 s2 0.49 s1 0.14 S3 0.06 轮盘赌法（赌轮选择法）轮盘赌法（赌轮选择法） 在在0, 10, 1区间内产生一个均区间内产生一个均 匀分布的随机数匀分布的随机数r r。 若若r rq q1 1, ,则城市则城市x x1

22、1被选中。被选中。 若若q qk k-1 -1 r r q qk k(2(2k kN N), ), 则城则城 市市x xk k被选中。被选中。 其中的其中的q qi i称为称为 城市城市x xi i ( (i i=1, 2, =1, 2, , , n n) ) 的积累概率的积累概率, , 其计算公式为其计算公式为 i j ji xPq 1 )( 对策一对策一 31 误区二：误区二： Q Q值的影响不大值的影响不大 32 对策二对策二 33 误区三：参数组合选择误区三：参数组合选择 34 对策三对策三 3.实例仿真实例仿真 l采用靳潘教授所提出的采用靳潘教授所提出的31个城市的个城市的CTSP（

23、求一条从北京（求一条从北京 出发经过中国出发经过中国31个省会城市及直辖市最后又回到北京的最个省会城市及直辖市最后又回到北京的最 短回路。短回路。 36 l下图对应31个城市的巡回路线为：北京-福州-南昌-合肥- 杭州-南京-西安-台北-太原-呼和浩特-沈阳-上海-石家庄-长 春-哈尔滨-济南-天津-武汉-郑州-长沙-银川-兰州-广州-海 口-南宁-西宁-成都-乌鲁木齐-昆明-拉萨-贵阳-北京。 l从仿真结果看最优解为:15708km。 l目前，公认的TSP问题最优结果为15398km，虽然，不完 全相等，但是结果比较相近，这说明蚂蚁算法虽然不是 TSP问题的最好算法，但是依据蚂蚁觅食过程提出

24、的蚁群 算法具有一定的可行性。 一、蚁群大小一、蚁群大小 一般情况下蚁群中蚂蚁的个数不超过一般情况下蚁群中蚂蚁的个数不超过TSPTSP 图中节点的个数。图中节点的个数。 二、终止条件二、终止条件 1 1 给定一个外循环的最大数目；给定一个外循环的最大数目； 2 2 当前最优解连续当前最优解连续K K次相同而停止，其次相同而停止，其 中中K K是一个给定的整数，表示算法已经收是一个给定的整数，表示算法已经收 敛，不再需要继续。敛，不再需要继续。 蚁群的规模及停止规则蚁群的规模及停止规则 优化问题优化问题蚂蚁觅食问题蚂蚁觅食问题 各个状态各个状态要遍历的各个路径要遍历的各个路径 解解蚂蚁经过的一条

25、完整路径蚂蚁经过的一条完整路径 最优解最优解最短路径最短路径 各状态的吸引度各状态的吸引度信息素的浓度信息素的浓度 状态更新状态更新信息素更新信息素更新 目标函数目标函数路径长度路径长度 蚂蚁觅食行为与优化问题的对照关系蚂蚁觅食行为与优化问题的对照关系 其原理是一种其原理是一种正反馈机制正反馈机制或称或称增强型学习系统增强型学习系统; ; 它通过它通过 【最优路径上蚂蚁数量的增加【最优路径上蚂蚁数量的增加信息素强度增加信息素强度增加后来蚂后来蚂 蚁选择概率增大蚁选择概率增大最优路径上蚂蚁数量更最优路径上蚂蚁数量更大大增加】达到最增加】达到最 终收敛于最优路径上终收敛于最优路径上。 它是一种它是

26、一种通用型随机优化方法通用型随机优化方法, , 它吸收了蚂蚁的行为特它吸收了蚂蚁的行为特 点点, , 它是使用人工蚂蚁仿真来求解问题它是使用人工蚂蚁仿真来求解问题。但人工蚂蚁决不但人工蚂蚁决不 是对实际蚂蚁的一种简单模拟是对实际蚂蚁的一种简单模拟, , 它融进了人类的智能它融进了人类的智能。具。具 有一定的记忆能力，能够记忆已经访问过的节点。选择路有一定的记忆能力，能够记忆已经访问过的节点。选择路 径时不是盲目的。而是按一定规律有意识地寻找最短路径径时不是盲目的。而是按一定规律有意识地寻找最短路径 。例如，在。例如，在TSP问题中，可以预先知道当前城市到下一个目问题中，可以预先知道当前城市到下一个目 的地的距离。的地的距离。 4.蚁群算法的特点蚁群算法