数学建模之蚁群算法课件

蚁群算法国防科技大学理学院数学系成礼智2011年夏季学期数学建模竞赛讲座1蚁群算法国防科技大学理学院数学系1

蚁群优化算法概述蚁群优化算法概念算法模型和收敛性分析算法实现的技术问题应用参考资料2蚁群优化算法概述2

1蚁群优化算法概述1.1起源1.2应用领域1.3研究背景1.4研究现状1.5应用现状31蚁群优化算法概述1.1起源3

1.1蚁群优化算法起源20世纪90年代意大利学者M．Dorigo，V．Maniezzo，A．Colorni等从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法——蚁群算法，是群智能理论研究领域的一种主要算法。用该方法求解TSP问题、分配问题、job-shop调度问题，取得了较好的试验结果．虽然研究时间不长，但是现在的研究显示出，蚁群算法在求解复杂优化问题（特别是离散优化问题）方面有一定优势，表明它是一种有发展前景的算法．41.1蚁群优化算法起源

1.2蚁群优化算法应用领域

蚁群算法是一种群智能方法，能够被用于解决大多数优化问题或者能够转化为优化求解的问题。现在其应用领域已扩展到多目标优化、数据分类、数据聚类、模式识别、电信管理、生物系统建模、流程规划、信号处理、机器人控制、决策支持以及仿真和系统辩识等方面，群智能理论和方法为解决这类应用问题提供了新的途径。51.2蚁群优化算法应用领域蚁群算法是一

1.3蚁群优化算法研究背景

群智能理论研究领域有两种主要的算法：蚁群算法(AntColonyOptimization,ACO)和微粒群（或称为粒子群）算法（ParticleSwarmOptimization,PSO）。前者是对蚂蚁群落食物采集过程的模拟，已成功应用于许多离散优化问题。微粒群算法也是起源于对简单社会系统的模拟，最初是模拟鸟群觅食的过程，但后来发现它是一种很好的优化工具。

61.3蚁群优化算法研究背景

1.3蚁群优化算法研究背景

与大多数基于梯度的应用优化算法不同，群智能依靠的是概率搜索算法。虽然概率搜索算法通常要采用较多的评价函数，但是与梯度方法及传统的演化算法相比，其优点还是显著的，主要表现在以下几个方面：1无集中控制约束，不会因个别个体的故障影响整个问题的求解，确保了系统具备更强的鲁棒性2以非直接的信息交流方式确保了系统的扩展性3并行分布式算法模型，可充分利用多处理器4对问题定义的连续性无特殊要求5算法实现简单71.3蚁群优化算法研究背景与大多数基于梯

1.3蚁群优化算法研究背景

群智能方法易于实现，算法中仅涉及各种基本的数学操作，其数据处理过程对CPU和内存的要求也不高。而且，这种方法只需目标函数的输出值，而无需其梯度信息。已完成的群智能理论和应用方法研究证明群智能方法是一种能够有效解决大多数全局优化问题的新方法。更为重要是，群智能潜在的并行性和分布式特点为处理大量的以数据库形式存在的数据提供了技术保证。无论是从理论研究还是应用研究的角度分析，群智能理论及其应用研究都是具有重要学术意义和现实价值的。81.3蚁群优化算法研究背景群智能

1.4蚁群优化算法研究现状90年代Dorigo最早提出了蚁群优化算法---蚂蚁系统（AntSystem,AS）并将其应用于解决计算机算法学中经典的旅行商问题（TSP）。从蚂蚁系统开始，基本的蚁群算法得到了不断的发展和完善，并在TSP以及许多实际优化问题求解中进一步得到了验证。这些AS改进版本的一个共同点就是增强了蚂蚁搜索过程中对最优解的探索能力，它们之间的差异仅在于搜索控制策略方面。而且，取得了最佳结果的ACO是通过引入局部搜索算法实现的，这实际上是一些结合了标准局域搜索算法的混合型概率搜索算法，有利于提高蚁群各级系统在优化问题中的求解质量。91.4蚁群优化算法研究现状90

1.4蚁群优化算法研究现状

M.Dorigo

最初提出的AS（Ant-System）有三种版本：Ant-density(蚁密)、Ant-quantity（蚁量）和Ant-cycle（蚁周）。在Ant-density和Ant-quantity中蚂蚁在两个位置节点间每移动一次后即更新信息素，而在Ant-cycle中当所有的蚂蚁都完成了自己的行程后才对信息素进行更新，而且每个蚂蚁所释放的信息素被表达为反映相应行程质量的函数。通过与其它各种通用的启发式算法相比，在不大于75城市的TSP中，这三种基本算法的求解能力还是比较理想的，但是当问题规模扩展时，AS的解题能力大幅度下降。对此，后面的研究者提出了多种不同的改进蚁群算法。

101.4蚁群优化算法研究现状

1.5蚁群优化算法应用现状

随着群智能理论和应用算法研究的不断发展，研究者已尝试着将其用于各种工程优化问题，并取得了意想不到的收获。多种研究表明，群智能在离散求解空间和连续求解空间中均表现出良好的搜索效果，并在组合优化问题中表现突出。蚁群优化算法并不是旅行商问题的最佳解决方法，但是它却为解决组合优化问题提供了新思路，并很快被应用到其它组合优化问题中。比较典型的应用研究包括：网络路由优化、数据挖掘以及一些经典的组合优化问题。111.5蚁群优化算法应用现状

1.5蚁群优化算法应用现状

蚁群算法在电信路由优化中已取得了一定的应用成果。HP公司和英国电信公司在90年代中后期都开展了这方面的研究，设计了蚁群路由算法（AntColonyRouting,ACR）。每只蚂蚁就像蚁群优化算法中一样，根据它在网络上的经验与性能，动态更新路由表项。如果一只蚂蚁因为经过了网络中堵塞的路由而导致了比较大的延迟，那么就对该表项做较大的增强。同时根据信息素挥发机制实现系统的信息更新，从而抛弃过期的路由信息。这样，在当前最优路由出现拥堵现象时，ACR算法就能迅速的搜寻另一条可替代的最优路径，从而提高网络的均衡性、负荷量和利用率。目前这方面的应用研究仍在升温，因为通信网络的分布式信息结构、非稳定随机动态特性以及网络状态的异步演化与ACO的算法本质和特性非常相似。121.5蚁群优化算法应用现状蚁群算法在

1.5蚁群优化算法应用现状

ACO还在许多经典组合优化问题中获得了成功的应用，如二次规划问题（QAP）、机器人路径规划、作业流程规划、图着色（GraphColoring）等问题。经过多年的发展，ACO已成为能够有效解决实际二次规划问题的几种重要算法之一。AS在作业流程计划（Job-shopScheduling）问题中的应用实例已经出现，这说明了AS在此领域的应用潜力。利用MAX-MINAS解决PAQ也取得了比较理想的效果，并通过实验中的计算数据证明采用该方法处理PAQ比较早的SA算法更好，且与禁忌搜索算法性能相当。利用ACO实现对生产流程和特料管理的综合优化，并通过与遗传、模拟退火和禁忌搜索算法的比较证明了ACO的工程应用价值。131.5蚁群优化算法应用现状

1.5蚁群优化算法应用现状

许多研究者将ACO用于了武器攻击目标分配和优化问题、车辆运行路径规划、区域性无线电频率自动分配、Bayesiannetworks的训练和集合覆盖等应用优化问题。Costa和Herz还提出了一种AS在规划问题方面的扩展应用——图着色问题，并取得了可与其他启发式算法相比的效果。141.5蚁群优化算法应用现状许

2蚁群优化算法概念

2.1蚁群算法原理2.2简化的蚂蚁寻食过程2.3自然蚁群与人工蚁群算法2.4蚁群算法与TSP问题2.5初始的蚁群优化算法—基于图的蚁群系统（GBAS）2.6一般蚁群算法的框架152蚁群优化算法概念 2.1蚁群算法原理15

2.1蚁群算法原理

蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。为了说明蚁群算法的原理，先简要介绍一下蚂蚁搜寻食物的具体过程。在蚁群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时．就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激索浓度越低.当后来的蚂蚁再次碰到这个路口的时候．选择激素浓度较高路径概率就会相对较大。这样形成一个正反馈。最优路径上的激索浓度越来越大．而其它的路径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。162.1蚁群算法原理蚁群算法

蚂蚁觅食机理17蚂蚁觅食机理17

其基本原理如下图：上图表示蚂蚁觅食的线路，A为蚁穴,B为食源，从到有两条线路可走，是长路径，是短路径.蚂蚁走过一条路线以后，在地面上会留下信息素气味，后来蚂蚁就是根据留在地面上这种气味的强度选择移动的方向.18其基本原理如下图：18

2.2蚁群觅食中的简单规则

每只蚂蚁只关心很小范围内的局部信息，而且根据这些局部信息利用几条简单的规则进行决策。（1）范围：蚂蚁观察到的范围是一个方格世界速度半径（一般是3），移动的距离在这个方格范围之内.（2）环境：蚂蚁所在的环境是一个虚拟世界，有障碍物、别的蚂蚁、信息素。信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素.每个蚂蚁都仅仅能感知它范围内的环境信息.环境以一定的速率让信息素消失.（3）觅食规则：直接奔食物或看是否有信息素，并且朝信息素多的地方走，还会以小概率犯错误，从而并不总是往信息素最多的点移动.192.2蚁群觅食中的简单规则19

（4）移动规则：每只蚂蚁都朝向信息素最多的方向移，当周围没有信息素指引的时候，蚂蚁会按照原来运动的方向惯性的运动下去，在运动的方向有一个随机的小的扰动.为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开.（5）避障规则：如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为.（6）播撒信息素规则：每只蚂蚁在刚找到食物或者窝的时候散发的信息素最多，并随着它走的距离越远，播撒的信息素越来越少.20（4）移动规则：每只蚂蚁都朝向信息素最多的方向

2.3自然蚁群与人工蚁群人工蚁是自然蚁群的抽象：(1)人工蚁与真实蚁一样，通过相互协调与合作从而有可能找到全局最优方案，而每只人工蚁的单独行动只可能找到局部最优解.(2)人工蚁和真实蚁一样，都要寻找一个从源节点（巢穴）到目的节点（食物源）之间的最短路径（或最小代价），人工蚂蚁与真实蚂蚁一样都不能跳跃，必须在相邻节点之间移动，直至遍历所有可能路径，为了减少计算复杂度并寻找出最短路径，需要记录当前路径.(3)人工蚁与真实蚁一样都通过使用信息素进行间接通信真实蚂蚁在经过的路径上留下信息素，人工蚁则不断修改更新在其所经过的路径上存储的信息，是一种模拟自然界中的信息素轨迹更新的过程.212.3自然蚁群与人工蚁群21

(4)人工蚁利用真实蚁觅食行为中的自催化机制—正反馈当一些路径上通过的蚂蚁越来越多时，路径上留下的信息素轨迹也越来越多，使得信息素强度变大，根据蚂蚁群倾向于选择信息强度大的特点，后来的蚂蚁选择该路径的概率也越高，从而增加了该路径的信息素强度（自催化过程），自催化机制利用信息素作为反馈，通过对系统演化过程中较优解的增强作用，使得问题的解向着全局最优的方向逐步接近.(5)信息素的挥发机制在蚁群算法中设置一种挥发机制，类似于真实信息素的挥发，这种机制需要蚂蚁忘记过去，不受过去经验的过分约束，有利于指引蚂蚁朝着新的方向搜索，避免早熟收敛.(6)利用当前信息进行路径选择的随机选择策略人工蚁与真实蚁都是利用概率选择策略实现一个节点到相邻节点的移动，选择策略只利用当前的信息去预测未来的情况，而不能利用未来的信息，因此，人工蚁与真实蚁所使用的选择策略在时间和空间上都具有局部特性.22(4)人工蚁利用真实蚁觅食行为中的自催化

人工蚁具备一些真实蚁所不具备的特征，主要体现在下列五个方面：(1)人工蚁存在于离散空间中，它们的移动实质上是有一个离散状态到另一个离散状态的转移；(2)人工蚁具有一个记录其过去自身行为的内在状态（记忆特性）；(3)人工蚁存在于与时间无关联的环境之中；(4)人工蚁并非完全盲从，它受到问题特征的启发，例如，有的问题中人工蚂蚁产生一个解后改变信息量，而在有的问题中人工蚂蚁每做一次选择便改变信息量；(5)为了提升人工蚁系统的性能，改进算法效率，人工蚁可增加一些性能，如预测未来、局部优化、回溯等.23人工蚁具备一些真实蚁所不具备的特征，主要体现2.3蚁群算法与TSP问题

2.3.1蚁群算法模型的建立

（1）蚂蚁个体的抽象:抽象出能够为建立模型起作用的真实蚁群的机理，摒弃与建立模型算法无关的因素.（2）问题空间的描述:蚂蚁轨迹可以看成二维平面上的活动，其活动过程为一个状态到另一个状态的迁移，利用蚁群算法求解的采用图论语言来描述就显得非常自然，另一方面，在实际问题中的许多应用问题可以通过图的语言来描述，这就使得蚁群算法的广泛应用成为可能.（3）寻找路径的抽象:把真实蚂蚁的觅食过程抽象成算法中解的构造过程，将信息素抽象成存在于图边上的轨迹，信息素的大小可以通过设置权重来体现，并根据权重的值决定走向下一个节点的概率.用任何两个节点分别表示蚂蚁的巢穴（初始节点）和食物源（终止节点），人工蚂蚁按照一定的状态转移概率从初始节点移动到邻近的节点，以此类推，最终选择行走到目标节点，从而得到问题的一个可行解.242.3蚁群算法与TSP问题2.3.1蚁群算法模型的

（4）信息素挥发的抽象:自然界中真实蚂蚁在所经过的路径上会连续不断的留下信息素，而信息素也会随着时间的推移连续不断的挥发，在人工蚁群算法中，蚂蚁完成从某一节点到相邻节点的一次移动后（相应于经过一个时间单位），进行一次信息素挥发，这有利于避免陷入局部最优的陷阱.（5）启发因子的引入:为了设计有效的蚁群算法，在决定蚂蚁行走方向的状态转移概率时，引入一个随机搜索的过程，即引入一个启发因子，根据所求问题空间的具体特征，给蚁群算法一个初始的引导，从而极大的增加算法的有效性，从而使蚁群算法的有效应用成为可能.25（4）信息素挥发的抽象:自然界中真实蚂蚁在

2.3.2旅行商问题（ＴＳＰ）与蚁群算法

TSP问题描述如下：设有n个城市，用数码1,,n代表.城市和城市之间的距离为．TSP问题是要找遍访每个域市恰好一次的一条回路，且其路径总长度为最短.图论模型：给定图，其中V为顶点集，A为各定点相互连接组成的边集，已知各顶点间的连接距离，要求确定一条最短的Hamilton回路，即遍历所有顶点当且仅当一次的最短回路.

Hamilton回路：经过图（有向图或无向图）中所有顶点一次且仅一次的通路。262.3.2旅行商问题（ＴＳＰ）与蚁群算法26

TSP问题表示为一个N个城市的有向图G=（N，A），其中 城市之间距离目标函数为其中为城市1,2，…n的一个排列，。27TSP问题表示为一个N个城市的有向图G=（N，A），

以TSP为例，基本蚁群算法的具体实现步骤描述如下：

（1）参数初始化（2）循环（3）蚂蚁个体根据状态转移概率公式计算的概率选择沿元素（城市）j前进，（4）修改禁忌指针表，即将选择好之后的蚂蚁移动到新的元素（城市），并将该元素（城市）移到该蚂蚁个体的禁忌表中；（5）信息素更新的计算（6）纪录到目前为止的最短路径，如果，则计算终止，循环结束并输出计算结果，否则，清空禁忌表并返回步骤（2）.整个计算过程所耗的空间复杂度为.28以TSP为例，基本蚁群算法的具体实现步骤描述如下：28

例2：0-1背包问题的解顺序表达形式与算法实现。设有一个容积为b的背包，n个尺寸分别为，价值分别为的物品，0-1背包问题的数学模型为：假设其解的顺序表达形式为，其中为的一个排列。29例2：0-1背包问题的解顺序表达形式与算法实现。设

建立有向图，其中A中共有条弧。初始信息素痕迹定义为。设第s只蚂蚁第k步所走的路线为，表示蚂蚁从0点出发，顺序到达。第步按TSP算法的转移概率公式行走选择。若则，否则，此蚂蚁不再继续行走，退回起点。30建立有向图，其中

对蚁群重复以上过程，比较m只蚂蚁的装包值 并记忆具有最大装包值的蚂蚁为t。把AS算法中步骤3中的改为，若满足此条件则替换当前最好解为，对W上的弧进行信息素的加强，其他弧进行信息素的挥发。算法中记录了三个信息：信息素痕迹；行走路线；和问题的约束条件 ，以确定是否将加入。31对蚁群重复以上过程，比较m只蚂蚁的装

算法中需要记忆的信息有三部分。第一部分信息是存在每个节点路由表数据结构，由此决定的的转移概率为其中T可以看成节点i的邻域。32算法中需要记忆的信息有三部分。32

第二部分需要记忆的信息是每个蚂蚁的记忆表中存储着的自身的历史信息，这一部分主要由算法的中的记忆，表示蚂蚁已经行走过的节点。第三部分为问题的约束条件。在GBAS中，T集合表示满足约束条件的候选集，在背包问题的蚁群算法中由判别条件， 实现记忆功能。33第二部分需要记忆的信息是每个蚂蚁的记忆表中

基于最大-最小蚁群算法的指派问题求解

一、指派问题模型有个人和个任务，已知第个人做第个任务的费用为，要求确定人和任务之间的一一对应的指派方案，使完成这些任务的总费用最少。数学模型：34基于最大-最小蚁群算法的指派问题求解

一、指派问

在改进的蚁群算法之最大–最小蚁群系统（Max-MinAntSystem）

MMAS系统

中每次只对迭代最优蚂蚁或到目前为止全局最优的蚂蚁进行信息素更新（不是像蚂蚁系统对所有走过路径进行信息素更新）；每个解的元素上的信息素轨迹量值域限制在区间内（不同于蚂蚁系统中信息素轨迹量不被限制，使得一些路径上轨迹量远高于其它边导致搜素停滞）；精心设计信息素初始化值，以保证更容易探索新的解（蚂蚁系统中没有考虑该因素导致算法收敛性较差）；引入信息素轨迹的平滑机制，以增加探索新解的能力，加快算法的收敛速度以及提高算法的数值稳定性。（MMAS系统1996年由MLuca与Cambradella等人提出）35在改进的蚁群算法之最大–最小蚁群系统（Max

改进算法描述设需要指派3个人去完成3个任务，并知道每个人完成每个任务所需的费用，则可得到一个三行三列的系数矩阵。指派问题的系数矩阵形成移动矩阵相同行的不同列之间移动，并且此列未到达过信息素集中在节点转到下一个节点的代价为下一个节点的系数矩阵值转移概率并非选择最大节点，有干扰因子到达一个节点，立即进行节点信息素的更新所有蚂蚁完成一次觅食，比较次优解，全局信息素的更新改进算法模型36改进算法描述设需要指派3个人去完成3个任务，并

改进算法模型转移概率。产生随机数，如果，则根据下式，蚂蚁移向概率最大的节点。否则在可选节点中随机选择一个。局部信息素更新。当蚂蚁选择此节点后，立即更新此节点的信息素。全局信息素更新。当所有蚂蚁完成一次觅食后，得到次优解。优于全局最优解，更新全局信息素。37改进算法模型转移概率。产生随机数

实验描述实验目的：得到信息素启发因子，期望值启发因子，干扰因子，蚂蚁数量，局部信息素挥发系数，全局信息素的挥发系数范围规模为10的干扰因子实验设置及结果，10次，迭代次数不同所有实验38实验描述实验目的：得到信息素启发因子，期望值启发因

实验目的：验证算法的有效性参数设置及结果--》39实验目的：验证算法的有效性参数设置及结果--》39

与标准蚁群算法性能对比参数设置及结果--》40与标准蚁群算法性能对比参数设置及结果--》40

另外还有两种改进蚁群算法以及蚁群算法的应用（运输问题的蚁群算法）见word文档41另外还有两种改进蚁群算法以及蚁群算法的应用（运输问题的蚁TheEnd！BaiBai！42TheEnd！42蚁群算法国防科技大学理学院数学系成礼智2011年夏季学期数学建模竞赛讲座43蚁群算法国防科技大学理学院数学系1

蚁群优化算法概述蚁群优化算法概念算法模型和收敛性分析算法实现的技术问题应用参考资料44蚁群优化算法概述2

1蚁群优化算法概述1.1起源1.2应用领域1.3研究背景1.4研究现状1.5应用现状451蚁群优化算法概述1.1起源3

1.1蚁群优化算法起源20世纪90年代意大利学者M．Dorigo，V．Maniezzo，A．Colorni等从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法——蚁群算法，是群智能理论研究领域的一种主要算法。用该方法求解TSP问题、分配问题、job-shop调度问题，取得了较好的试验结果．虽然研究时间不长，但是现在的研究显示出，蚁群算法在求解复杂优化问题（特别是离散优化问题）方面有一定优势，表明它是一种有发展前景的算法．461.1蚁群优化算法起源

1.2蚁群优化算法应用领域

蚁群算法是一种群智能方法，能够被用于解决大多数优化问题或者能够转化为优化求解的问题。现在其应用领域已扩展到多目标优化、数据分类、数据聚类、模式识别、电信管理、生物系统建模、流程规划、信号处理、机器人控制、决策支持以及仿真和系统辩识等方面，群智能理论和方法为解决这类应用问题提供了新的途径。471.2蚁群优化算法应用领域蚁群算法是一

1.3蚁群优化算法研究背景

群智能理论研究领域有两种主要的算法：蚁群算法(AntColonyOptimization,ACO)和微粒群（或称为粒子群）算法（ParticleSwarmOptimization,PSO）。前者是对蚂蚁群落食物采集过程的模拟，已成功应用于许多离散优化问题。微粒群算法也是起源于对简单社会系统的模拟，最初是模拟鸟群觅食的过程，但后来发现它是一种很好的优化工具。

481.3蚁群优化算法研究背景

1.3蚁群优化算法研究背景

与大多数基于梯度的应用优化算法不同，群智能依靠的是概率搜索算法。虽然概率搜索算法通常要采用较多的评价函数，但是与梯度方法及传统的演化算法相比，其优点还是显著的，主要表现在以下几个方面：1无集中控制约束，不会因个别个体的故障影响整个问题的求解，确保了系统具备更强的鲁棒性2以非直接的信息交流方式确保了系统的扩展性3并行分布式算法模型，可充分利用多处理器4对问题定义的连续性无特殊要求5算法实现简单491.3蚁群优化算法研究背景与大多数基于梯

1.3蚁群优化算法研究背景

群智能方法易于实现，算法中仅涉及各种基本的数学操作，其数据处理过程对CPU和内存的要求也不高。而且，这种方法只需目标函数的输出值，而无需其梯度信息。已完成的群智能理论和应用方法研究证明群智能方法是一种能够有效解决大多数全局优化问题的新方法。更为重要是，群智能潜在的并行性和分布式特点为处理大量的以数据库形式存在的数据提供了技术保证。无论是从理论研究还是应用研究的角度分析，群智能理论及其应用研究都是具有重要学术意义和现实价值的。501.3蚁群优化算法研究背景群智能

1.4蚁群优化算法研究现状90年代Dorigo最早提出了蚁群优化算法---蚂蚁系统（AntSystem,AS）并将其应用于解决计算机算法学中经典的旅行商问题（TSP）。从蚂蚁系统开始，基本的蚁群算法得到了不断的发展和完善，并在TSP以及许多实际优化问题求解中进一步得到了验证。这些AS改进版本的一个共同点就是增强了蚂蚁搜索过程中对最优解的探索能力，它们之间的差异仅在于搜索控制策略方面。而且，取得了最佳结果的ACO是通过引入局部搜索算法实现的，这实际上是一些结合了标准局域搜索算法的混合型概率搜索算法，有利于提高蚁群各级系统在优化问题中的求解质量。511.4蚁群优化算法研究现状90

1.4蚁群优化算法研究现状

M.Dorigo

最初提出的AS（Ant-System）有三种版本：Ant-density(蚁密)、Ant-quantity（蚁量）和Ant-cycle（蚁周）。在Ant-density和Ant-quantity中蚂蚁在两个位置节点间每移动一次后即更新信息素，而在Ant-cycle中当所有的蚂蚁都完成了自己的行程后才对信息素进行更新，而且每个蚂蚁所释放的信息素被表达为反映相应行程质量的函数。通过与其它各种通用的启发式算法相比，在不大于75城市的TSP中，这三种基本算法的求解能力还是比较理想的，但是当问题规模扩展时，AS的解题能力大幅度下降。对此，后面的研究者提出了多种不同的改进蚁群算法。

521.4蚁群优化算法研究现状

1.5蚁群优化算法应用现状

随着群智能理论和应用算法研究的不断发展，研究者已尝试着将其用于各种工程优化问题，并取得了意想不到的收获。多种研究表明，群智能在离散求解空间和连续求解空间中均表现出良好的搜索效果，并在组合优化问题中表现突出。蚁群优化算法并不是旅行商问题的最佳解决方法，但是它却为解决组合优化问题提供了新思路，并很快被应用到其它组合优化问题中。比较典型的应用研究包括：网络路由优化、数据挖掘以及一些经典的组合优化问题。531.5蚁群优化算法应用现状

1.5蚁群优化算法应用现状

蚁群算法在电信路由优化中已取得了一定的应用成果。HP公司和英国电信公司在90年代中后期都开展了这方面的研究，设计了蚁群路由算法（AntColonyRouting,ACR）。每只蚂蚁就像蚁群优化算法中一样，根据它在网络上的经验与性能，动态更新路由表项。如果一只蚂蚁因为经过了网络中堵塞的路由而导致了比较大的延迟，那么就对该表项做较大的增强。同时根据信息素挥发机制实现系统的信息更新，从而抛弃过期的路由信息。这样，在当前最优路由出现拥堵现象时，ACR算法就能迅速的搜寻另一条可替代的最优路径，从而提高网络的均衡性、负荷量和利用率。目前这方面的应用研究仍在升温，因为通信网络的分布式信息结构、非稳定随机动态特性以及网络状态的异步演化与ACO的算法本质和特性非常相似。541.5蚁群优化算法应用现状蚁群算法在

1.5蚁群优化算法应用现状

ACO还在许多经典组合优化问题中获得了成功的应用，如二次规划问题（QAP）、机器人路径规划、作业流程规划、图着色（GraphColoring）等问题。经过多年的发展，ACO已成为能够有效解决实际二次规划问题的几种重要算法之一。AS在作业流程计划（Job-shopScheduling）问题中的应用实例已经出现，这说明了AS在此领域的应用潜力。利用MAX-MINAS解决PAQ也取得了比较理想的效果，并通过实验中的计算数据证明采用该方法处理PAQ比较早的SA算法更好，且与禁忌搜索算法性能相当。利用ACO实现对生产流程和特料管理的综合优化，并通过与遗传、模拟退火和禁忌搜索算法的比较证明了ACO的工程应用价值。551.5蚁群优化算法应用现状

1.5蚁群优化算法应用现状

许多研究者将ACO用于了武器攻击目标分配和优化问题、车辆运行路径规划、区域性无线电频率自动分配、Bayesiannetworks的训练和集合覆盖等应用优化问题。Costa和Herz还提出了一种AS在规划问题方面的扩展应用——图着色问题，并取得了可与其他启发式算法相比的效果。561.5蚁群优化算法应用现状许

2蚁群优化算法概念

2.1蚁群算法原理2.2简化的蚂蚁寻食过程2.3自然蚁群与人工蚁群算法2.4蚁群算法与TSP问题2.5初始的蚁群优化算法—基于图的蚁群系统（GBAS）2.6一般蚁群算法的框架572蚁群优化算法概念 2.1蚁群算法原理15

2.1蚁群算法原理

蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。为了说明蚁群算法的原理，先简要介绍一下蚂蚁搜寻食物的具体过程。在蚁群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时．就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激索浓度越低.当后来的蚂蚁再次碰到这个路口的时候．选择激素浓度较高路径概率就会相对较大。这样形成一个正反馈。最优路径上的激索浓度越来越大．而其它的路径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。582.1蚁群算法原理蚁群算法

蚂蚁觅食机理59蚂蚁觅食机理17

其基本原理如下图：上图表示蚂蚁觅食的线路，A为蚁穴,B为食源，从到有两条线路可走，是长路径，是短路径.蚂蚁走过一条路线以后，在地面上会留下信息素气味，后来蚂蚁就是根据留在地面上这种气味的强度选择移动的方向.60其基本原理如下图：18

2.2蚁群觅食中的简单规则

每只蚂蚁只关心很小范围内的局部信息，而且根据这些局部信息利用几条简单的规则进行决策。（1）范围：蚂蚁观察到的范围是一个方格世界速度半径（一般是3），移动的距离在这个方格范围之内.（2）环境：蚂蚁所在的环境是一个虚拟世界，有障碍物、别的蚂蚁、信息素。信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素.每个蚂蚁都仅仅能感知它范围内的环境信息.环境以一定的速率让信息素消失.（3）觅食规则：直接奔食物或看是否有信息素，并且朝信息素多的地方走，还会以小概率犯错误，从而并不总是往信息素最多的点移动.612.2蚁群觅食中的简单规则19

（4）移动规则：每只蚂蚁都朝向信息素最多的方向移，当周围没有信息素指引的时候，蚂蚁会按照原来运动的方向惯性的运动下去，在运动的方向有一个随机的小的扰动.为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开.（5）避障规则：如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为.（6）播撒信息素规则：每只蚂蚁在刚找到食物或者窝的时候散发的信息素最多，并随着它走的距离越远，播撒的信息素越来越少.62（4）移动规则：每只蚂蚁都朝向信息素最多的方向

2.3自然蚁群与人工蚁群人工蚁是自然蚁群的抽象：(1)人工蚁与真实蚁一样，通过相互协调与合作从而有可能找到全局最优方案，而每只人工蚁的单独行动只可能找到局部最优解.(2)人工蚁和真实蚁一样，都要寻找一个从源节点（巢穴）到目的节点（食物源）之间的最短路径（或最小代价），人工蚂蚁与真实蚂蚁一样都不能跳跃，必须在相邻节点之间移动，直至遍历所有可能路径，为了减少计算复杂度并寻找出最短路径，需要记录当前路径.(3)人工蚁与真实蚁一样都通过使用信息素进行间接通信真实蚂蚁在经过的路径上留下信息素，人工蚁则不断修改更新在其所经过的路径上存储的信息，是一种模拟自然界中的信息素轨迹更新的过程.632.3自然蚁群与人工蚁群21

(4)人工蚁利用真实蚁觅食行为中的自催化机制—正反馈当一些路径上通过的蚂蚁越来越多时，路径上留下的信息素轨迹也越来越多，使得信息素强度变大，根据蚂蚁群倾向于选择信息强度大的特点，后来的蚂蚁选择该路径的概率也越高，从而增加了该路径的信息素强度（自催化过程），自催化机制利用信息素作为反馈，通过对系统演化过程中较优解的增强作用，使得问题的解向着全局最优的方向逐步接近.(5)信息素的挥发机制在蚁群算法中设置一种挥发机制，类似于真实信息素的挥发，这种机制需要蚂蚁忘记过去，不受过去经验的过分约束，有利于指引蚂蚁朝着新的方向搜索，避免早熟收敛.(6)利用当前信息进行路径选择的随机选择策略人工蚁与真实蚁都是利用概率选择策略实现一个节点到相邻节点的移动，选择策略只利用当前的信息去预测未来的情况，而不能利用未来的信息，因此，人工蚁与真实蚁所使用的选择策略在时间和空间上都具有局部特性.64(4)人工蚁利用真实蚁觅食行为中的自催化

人工蚁具备一些真实蚁所不具备的特征，主要体现在下列五个方面：(1)人工蚁存在于离散空间中，它们的移动实质上是有一个离散状态到另一个离散状态的转移；(2)人工蚁具有一个记录其过去自身行为的内在状态（记忆特性）；(3)人工蚁存在于与时间无关联的环境之中；(4)人工蚁并非完全盲从，它受到问题特征的启发，例如，有的问题中人工蚂蚁产生一个解后改变信息量，而在有的问题中人工蚂蚁每做一次选择便改变信息量；(5)为了提升人工蚁系统的性能，改进算法效率，人工蚁可增加一些性能，如预测未来、局部优化、回溯等.65人工蚁具备一些真实蚁所不具备的特征，主要体现2.3蚁群算法与TSP问题

2.3.1蚁群算法模型的建立

（1）蚂蚁个体的抽象:抽象出能够为建立模型起作用的真实蚁群的机理，摒弃与建立模型算法无关的因素.（2）问题空间的描述:蚂蚁轨迹可以看成二维平面上的活动，其活动过程为一个状态到另一个状态的迁移，利用蚁群算法求解的采用图论语言来描述就显得非常自然，另一方面，在实际问题中的许多应用问题可以通过图的语言来描述，这就使得蚁群算法的广泛应用成为可能.（3）寻找路径的抽象:把真实蚂蚁的觅食过程抽象成算法中解的构造过程，将信息素抽象成存在于图边上的轨迹，信息素的大小可以通过设置权重来体现，并根据权重的值决定走向下一个节点的概率.用任何两个节点分别表示蚂蚁的巢穴（初始节点）和食物源（终止节点），人工蚂蚁按照一定的状态转移概率从初始节点移动到邻近的节点，以此类推，最终选择行走到目标节点，从而得到问题的一个可行解.662.3蚁群算法与TSP问题2.3.1蚁群算法模型的

（4）信息素挥发的抽象:自然界中真实蚂蚁在所经过的路径上会连续不断的留下信息素，而信息素也会随着时间的推移连续不断的挥发，在人工蚁群算法中，蚂蚁完成从某一节点到相邻节点的一次移动后（相应于经过一个时间单位），进行一次信息素挥发，这有利于避免陷入局部最优的陷阱.（5）启发因子的引入:为了设计有效的蚁群算法，在决定蚂蚁行走方向的状态转移概率时，引入一个随机搜索的过程，即引入一个启发因子，根据所求问题空间的具体特征，给蚁群算法一个初始的引导，从而极大的增加算法的有效性，从而使蚁群算法的有效应用成为可能.67（4）信息素挥发的抽象:自然界中真实蚂蚁在

2.3.2旅行商问题（ＴＳＰ）与蚁群算法

TSP问题描述如下：设有n个城市，用数码1,,n代表.城市和城市之间的距离为．TSP问题是要找遍访每个域市恰好一次的一条回路，且其路径总长度为最短.图论模型：给定图，其中V为顶点集，A为各定点相互连接组成的边集，已知各顶点间的连接距离，要求确定一条最短的Hamilton回路，即遍历所有顶点当且仅当一次的最短回路.

Hamilton回路：经过图（有向图或无向图）中所有顶点一次且仅一次的通路。682.3.2旅行商问题（ＴＳＰ）与蚁群算法26

TSP问题表示为一个N个城市的有向图G=（N，A），其中 城市之间距离目标函数为其中为城市1,2，…n的一个排列，。69TSP问题表示为一个N个城市的有向图G=（N，A），

以TSP为例，基本蚁群算法的具体实现步骤描述如下：

（1）参数初始化（2）循环（3）蚂蚁个体根据状态转移概率公式计算的概率选择沿元素（城市）j前进，（4）修改禁忌指针表，即将选择好之后的蚂蚁移动到新的元素（城市），并将该元素（城市）移到该蚂蚁个体的禁忌表中；（5）信息素更新的计算（6）纪录到目前为止的最短路径，如果，则计算终止，循环结束并输出计算结果，否则，清空禁忌表并返回步骤（2）.整个计算过程所耗的空间复杂度为.70以TSP为例，基本蚁群算法的具体实现步骤描述如下：28

例2：0-1背包问题的解顺序表达形式与算法实现。设有一个容积为b的背包，n个尺寸分别为，价值分别为的物品，0-1背包问题的数学模型为：假设其解的顺序表达形式为，其中为的一个排列。71例2：0-1背包问题的解顺序表达形式与算法实现。设

建立有向图，其中A中共有条弧。初始信息素痕迹定义为。设第s只蚂蚁第k步所走的路线为，表示蚂蚁从0点出发，顺序到达。第步按TSP算法的转移概率公式行走选择。若则