蚁群算法介绍

1、数学建模数学建模主讲人：王成章2前言 通过前面的学习，我们可以发现，智能优化算法实际上是根据问题的部分已知信息来启发式地探索该问题的解决方案，在探索解决方案的过程中将发现的有关信息记录下来，不断积累和分析，并根据越来越丰富的已知信息来指导下一步的动作并修正以前的步骤，从而获得在整体上较好的解决方案。 启发式计算方法启发式计算方法3前言(C.)什么是启发式算法呢？【定义1】 启发式算法是一种基于直观或经验构造的算法，在可接受的耗费（指计算时间、占用空间等）下给出待解决优化问题每一实例的一个可行解，该可行解与最优解的偏离程度未必可事先估计。【定义2】 启发式算法是一种技术，该技术使得能在可接受的计

2、算费用内去寻找尽可能好的解，但不一定能保证所得解的可行性和最优性，甚至在多数情况下，无法描述所得解与最优解的近似程度。4前言(C.)物理启发式： 模拟退火算法：模拟固体熔化状态下由逐渐冷却至最终达到结晶状态的物理过程社会与文化启发： 文化算法 （模拟人类社会的演化过程） 人口迁移算法 （模拟人口流动与人口迁移）5前言(C.)生物启发式： 生物启发式计算是指以生物界的各种自然现象或过程为灵感，而提出的一系列启发式智能计算方法。比如： 遗传算法 人工神经网络6前言(C.)遗传算法： 生物进化过程是一个自然，并行，稳健的优化过程，这一优化过程的目的在于使生命体达到适应环境的最佳结构与效果，而生物种群

3、通过” “优胜劣汰”及遗传变异来达到进化（优化）目的的。 7前言(C.e) 还有一类重要的现代智能优化算法：群体智能（Swarm Intelligence：SI）算法。 生物学家研究表明：在这些群居生物中虽然每个个体的智能不高，行为简单，也不存在集中的指挥，但由这些单个个体组成的群体，似乎在某种内在规律的作用下，却表现出异常复杂而有序的群体行为。8蚁群算法蚁群：蚁群是自然界中常见的一种生物，人们对蚂蚁的关注大都是因为“蚁群搬家，天要下雨”之类的民谚。然而随着近代仿生学的发展，这种似乎微不足道的小东西越来越多地受到学者们地关注。蚂蚁是一种群居昆虫，在觅食、清理巢穴等活动中，彼此依赖、相互协作共同

4、完成特定的任务。就个体来讲，单个蚂蚁的智力和体力是极其有限的，服务于整个群落的生存与发展；就群体来讲，蚁群在行为上的分工协作、在完成任务过程中所体现的自组织特征等反应出蚁群具有较高的智能和自我管理能力，具有很高层次组织性，这使得蚁群能够完成一些复杂的任务。9蚁群算法(C.)自然现象：为了说明蚁群算法的原理，先简要介绍一下蚂蚁搜寻食物的具体过程。在蚁群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激索浓度越低.当后来的

5、蚂蚁再次碰到这个路口的时候选择激素浓度较高路径概率就会相对较大。这样形成一个正反馈。最优路径上的激索浓度越来越大而其它的路径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。 10蚁群算法(C.)自然现象： Goss. S. “双桥”实验(1989)AC11蚁群算法(C.)自然现象：AC12蚁群算法(C.)自然现象：AC13蚁群算法(C.) 简化的寻食过程： 蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。假设初始时每条路线分配一只蚂蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。1

6、4蚁群算法(C.) 简化的寻食过程： 本图为从开始算起，经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。15蚁群算法(C.) 假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物，此时ABD的路线往返了2趟，每一处的信息素为4个单位，而 ACD的路线往返了一趟，每一处的信息素为2个单位，其比值为2：1。 寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD路线上增派一只蚂蚁（共2只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为1

7、2和4，比值为3：1。 若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共3只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为24和6，比值为4：1。 若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线，而都选择ABD路线。这也就是前面所提到的正反馈效应。16蚁群算法(C.)蚁群算法： 蚁群算法是对自然界蚂蚁的寻食方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone)/信息素的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群

8、集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。17蚁群算法的起源：20世纪90年代意大利学者MDorigo，VManiezzo，AColorni等从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法 蚁群算法(Ant Colony Optimization: ACO)。蚁群算法是群智能理论研究领域的一种主要算法。用该方法求解TSP问题、分配问题、job-shop调度问题，取得了较好的试验结果。虽然研究时间不长，但是现在的研究显示出，蚁群算法在求解复杂优化问题（特别是离散优化问题）方面有一定优势。蚁群算法(C.

9、)18蚁群算法的应用领域：这种方法能够被用于解决大多数优化问题或者能够转化为优化求解的问题。现在其应用领域已扩展到多目标优化、数据分类、数据聚类、模式识别、电信管理、生物系统建模、流程规划、信号处理、机器人控制、决策支持以及仿真和系统辩识等方面，群智能理论和方法为解决这类应用问题提供了新的途径。蚁群算法(C.)19蚁群算法的研究背景：与大多数基于梯度的应用优化算法不同，群智能依靠的是概率搜索算法。虽然概率搜索算法通常要采用较多的评价函数，但是与梯度方法及传统的演化算法相比，其优点还是显著的 ，主要表现在以下几个方面：无集中控制约束，不会因个别个体的故障影响整个问题 的求解，确保了系统具备更强的

10、鲁棒性 以非直接的信息交流方式确保了系统的扩展性 并行分布式算法模型，可充分利用多处理器 对问题定义的连续性无特殊要求 算法实现简单 蚁群算法(C.)20蚁群算法的研究背景：群智能方法易于实现，算法中仅涉及各种基本的数学操作，其数据处理过程对CPU和内存的要求也不高。而且，这种方法只需目标函数的输出值，而无需其梯度信息。已完成的群智能理论和应用方法研究证明群智能方法是一种能够有效解决大多数全局优化问题的新方法。更为重要是，群智能潜在的并行性和分布式特点为处理大量的以数据库形式存在的数据提供了技术保证。蚁群算法(C.)21蚁群算法的研究背景：最初提出的AS有三种版本：Ant-density、An

11、t-quantity和Ant-cycle。在Ant-density和Ant-quantity中蚂蚁在两个位置节点间每移动一次后即更新信息素，而在Ant-cycle中当所有的蚂蚁都完成了自己的行程后才对信息素进行更新，而且每个蚂蚁所释放的信息素被表达为反映相应行程质量的函数。蚁群算法(C.)22蚁群算法的原理：蚁群的行为是整体协作，相互分工，以一个整体去解决一些对单个蚂蚁看上去是不可能完成的任务。蚁群算法是对自然界蚂蚁的寻食方式进行模似而得出的一种仿生算法。为了根据自然界蚂蚁的行为设计蚁群算法，首先要定义一种人工蚂蚁。一方面，人工蚁群是真实蚁群行为特征的一种抽象，将真实蚁群寻食行为中核心的部分抽

12、象了出来赋给了人工蚁群。另一方面，由于人工蚁群需要解决实际的复杂优化问题，为了能使蚁群算法更有效，人工蚁群还具备了真实蚁群所不具备的本领。蚁群算法(C.)23人工蚁群与真实蚁群之间的共同点：人工蚁群和真实蚁群一样，都是相互合作的群体。蚁群中的每只蚂蚁都能建立一个解，蚂蚁个体通过相互的协作在全局范围内找出问题较优的解。人工蚁群和真实蚁群有着共同的任务：寻找起点(蚁穴)到终点(食物源)的最短路经(最优目标)。人工蚁群和真实蚁群都是通过信息素进行间接通讯的。在人工蚁群算法中信息素轨迹是通过状态变量来表示的。人工蚁群算法通过修改状态变量矩阵中元素的值来模拟真实蚁群中信息素的更新过程。蚁群算法(C.)2

13、4人工蚁群与真实蚁群之间的共同点：人工蚁群还应用了真实蚁群寻食过程中的正反馈机制。蚁群的正反馈机制使得问题的解向着最优的方向不断进化。人工蚁群和真实蚁群都存在着一种信息素挥发机制。这种机制可以使得蚂蚁逐渐忘记过去，不会受过去经验的过分束缚，有利于向着新的方向搜索，避免过早的收敛。人工蚁群和真实蚁群都是基于概率转移的局部搜索策略。蚂蚁在转移时，所应用的策略在时间和空间上是完全局部的。蚁群算法(C.)25人工蚁群的特有功能：人工蚁群算法存在于一个离散的空间中，它们的移动是一个状态到另一个状态的转换。人工蚁群算法具有一个记忆它本身过去行为的内在状态。人工蚂蚁释放信息素的量，是由蚂蚁所建立的问题解决方

14、案优劣程度函数决定的。蚁群算法更新信息量的时机是随着不同问题而变化，不反映真实蚁群的行为。为了改善系统的性能，人工蚁群算法可以增加一些性能，如：前瞻性、局部优化、原路返回等。蚁群算法(C.)26下面以TSP问题为例，详细说明蚁群算法的流程：TSP问题描述：TSP问题可以表示为一个N个城市的有向图 G=(N, A)其中，N=1,2,3,n，A=(i, j)| i, j N城市之间的距离矩阵为：(dij)nnm 为蚁群中蚂蚁的数量ij(t)为t 时刻边弧(i, j) 的轨迹强度(即ij 连线上残留的信息量)，且设 ij(0) = c ( c 为常数，可以设为边矩阵A行列式的倒数)； ij (t)

15、为t 时刻边弧(i, j)的能见度，反映由城市i 转移到城市j 的期望程度。蚁群算法(C.)27下面以TSP问题为例，详细说明蚁群算法的流程：蚂蚁k (k = 1,2,m) 在运动过程中根据各条路径上的信息量决定转移方向。与真实蚁群系统不同，人工蚁群系统具有一定的记忆功能。随着时间的推移，以前留下的信息逐渐消逝，经n 个时刻，蚂蚁完成一次循环，各路径上信息量要作调整。人工蚁群系统模型：1）设人工蚁群在并行地搜索TSP 的解，并通过一种信息素做媒介相互通信，在每个结点上且和该结点相连的边上以信息素量做搜索下一结点的试探依据，直到找到一个TSP 问题的可行解。蚁群算法(C.)28下面以TSP问题为

16、例，详细说明蚁群算法的流程：人工蚁群系统模型：2）在时刻t 人工蚂蚁k 由位置i 转移至位置j 的转移概率为：蚁群算法(C.)29下面以TSP问题为例，详细说明蚁群算法的流程：人工蚁群系统模型：3）当m 个人工蚂蚁式找到了可行解，则将各边的信息量用下式修改。即调整信息量的轨迹强度更新方程为：蚁群算法(C.)30下面以TSP问题为例，详细说明蚁群算法的流程：对上述系统模型，采用人工蚁群方法求解的算法步骤可归结为：蚁群算法(C.)31下面以TSP问题为例，详细说明蚁群算法的流程：对上述系统模型，采用人工蚁群方法求解的算法步骤可归结为：说明：若为了简化计算，增加处理较大规模的TSP 问题的能力，则可

17、将轨迹更新方程修改为蚁群算法(C.)32蚁群算法的分析补充：算法中包括信息素更新的过程：信息素挥发： 信息素痕迹的挥发过程是每个连接上的信息素痕迹的浓度自动逐渐减弱的过程，这个挥发过程主要用于避免算法过快地向局部最优区域集中，有助于搜索区域的扩展。 信息素增强：增强过程是蚁群优化算法中可选的部分。这种方式可以实现由单个蚂蚁无法实现的集中行动，增强过程体现在观察蚁群（m只蚂蚁）中每只蚂蚁所找到的路径，并选择其中最优路径上的弧进行信息素的增强，挥发过程是所有弧都进行的，不与蚂蚁数量相关。这种增强过程中进行的信息素更新称为离线的信息素更新。蚁群算法(C.)33蚁群算法的分析补充：人工蚂蚁要实现的四个

18、功能：1)基于概率的局部搜索策略：实际问题中，蚂蚁经常要从一个状态点移动到另一个状态点。经过这样有限步的移动，每只蚂蚁都建立了一个问题的解。在每一步的移动过程中，蚂蚁应用基于概率的局部搜索策略选择移动方向。这个策略主要基于蚂蚁的记忆以及信息素的浓度，有时还有具体问题的局部信息等。2)蚂蚁的记忆：蚂蚁的记忆存储了关于蚂蚁过去的信息。这些记忆的信息可以用于计算所解决方案的价值或每一步移动的贡献。在一些组和优化问题中，利用蚂蚁的记忆可以正确引导蚂蚁构建方案的解。蚁群算法(C.)34蚁群算法的分析补充：人工蚂蚁要实现的四个功能：2)蚂蚁的记忆(续)：比如在TSP问题中，利用蚂蚁的记忆可以记录蚂蚁已经走

19、过的城市，并将其置于一个禁忌表中。这样就可以避免蚂蚁重复访问这些城市，使得蚂蚁构造出来的解可以满足TSP问题的约束条件。所以，蚂蚁可以只使用关于局部的信息，就可以构造出问题的解。3)释放信息素：蚂蚁之间的协作是通过信息素来完成，信息素给蚁群算法产生了正反馈的重要作用。蚂蚁释放信息素的量与蚂蚁建立解决方案的优劣程度成正比。蚁群算法(C.)35蚁群算法的分析补充：人工蚂蚁要实现的四个功能：4)蚂蚁决策表：蚂蚁决策表是由信息素函数与启发函数共同决定的，它是一种概率表。蚂蚁使用这个表来指导其搜索最有吸引力的移动方向。在蚂蚁移动时，不仅基于概率的局部搜索策略，还增加了信息素挥发机制，这样就可以避免过早收

20、敛，出现早熟现象。总之，蚁群算法就是通过蚂蚁个体功能来构造解，并释放信息素来协调，最终找到一个较优的解决方案。蚁群算法(C.)36蚁群算法的技术问题：解的表达形式与算法的实现每一节点的记忆信息和系数的确定蚁群的规模和停止规则信息素的更改蚁群算法(C.)37蚁群算法的技术问题：解的表达形式与算法的实现基于TSP问题的蚁群优化算法，其解的形式是所有城市的一个排列（闭圈，这种情况下谁在第一并不重要），信息素痕迹按每个弧记录。而对于一般以顺序作为解的优化问题，谁在第一是很重要的。蚁群算法在解决这类问题时，只需要建立一个虚拟的始终点，就可以把TSP问题的解法推广，用于诸多的优化问题。每一节点的记忆信息和系数的确定蚁群的规模和停止规则信息素的更改蚁群算法(C.)38蚁群算法的技术问题：解的表达形式与算法的实现每一节点的记忆信息和系数的确定算法中需要记忆的信息有三部分：第一部分信息是存在每个节点的路由表数据结构；第二部分需要记忆的信息是每个蚂蚁的记忆表中存储着的自身的历史信息；第三部分为问题的约束条件。残留信息的相对重要程度和预见值的相对重要程度体现了相关信息痕迹和预见度对蚂蚁决策的相对影响。求解TSP问题时，推荐参数的最佳设置为：=1， =5，=0.5。蚁群的规模和停止规则信息素的更改蚁群算法(C.)39蚁群算法的技术问题：解的表达形式与算法的实现每一节点的记忆信息和系数的确定蚁群的规模和