1、1蚁群算法蚁群算法国防科技大学理学院数学系国防科技大学理学院数学系 成礼智成礼智20112011年夏季学期数学建模竞赛讲座年夏季学期数学建模竞赛讲座2 n 蚁群优化算法概述n 蚁群优化算法概念n 算法模型和收敛性分析n 算法实现的技术问题n 应用n 参考资料3 1 1 蚁群优化算法概述蚁群优化算法概述1.1 1.1 起源起源1.2 1.2 应用领域应用领域1.3 1.3 研究背景研究背景1.4 1.4 研究现状研究现状1.5 1.5 应用现状应用现状4 1.1 1.1 蚁群优化算法起源蚁群优化算法起源 20世纪世纪90年代意大利学者年代意大利学者MDorigo，VManiezzo，AColor
2、ni等从生物进化的机制中等从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法提出来一种新型的模拟进化算法 蚁群算法，是蚁群算法，是群智能理论研究领域的一种主要算法。用该方法求群智能理论研究领域的一种主要算法。用该方法求解解TSP问题、分配问题、问题、分配问题、job-shop调度问题，取得了调度问题，取得了较好的试验结果虽然研究时间不长，但是现在的较好的试验结果虽然研究时间不长，但是现在的研究显示出，蚁群算法在求解复杂优化问题（特别研究显示出，蚁群算法在求解复杂优化问题（特别是离散优化问题）方面有一定优势，表明
3、它是一种是离散优化问题）方面有一定优势，表明它是一种有发展前景的算法有发展前景的算法5 1.2 1.2 蚁群优化算法应用领域蚁群优化算法应用领域 蚁群算法是一种群智能方法，能够被用于解蚁群算法是一种群智能方法，能够被用于解决大多数优化问题或者能够转化为优化求解的决大多数优化问题或者能够转化为优化求解的问题。现在其应用领域已扩展到多目标优化、问题。现在其应用领域已扩展到多目标优化、数据分类、数据聚类、模式识别、电信管理、数据分类、数据聚类、模式识别、电信管理、生物系统建模、流程规划、信号处理、机器人生物系统建模、流程规划、信号处理、机器人控制、决策支持以及仿真和系统辩识等方面，控制、决策支持以及
4、仿真和系统辩识等方面，群智能理论和方法为解决这类应用问题提供了群智能理论和方法为解决这类应用问题提供了新的途径新的途径。6 1.3 1.3 蚁群优化算法研究背景蚁群优化算法研究背景 群智能理论研究领域有两种主要的算法：蚁群群智能理论研究领域有两种主要的算法：蚁群算法算法(Ant Colony Optimization,ACO)和微粒群（或和微粒群（或称为粒子群）算法（称为粒子群）算法（Particle Swarm Optimization,PSO）。）。前者是对蚂蚁群落食物采集过程的模拟，已成前者是对蚂蚁群落食物采集过程的模拟，已成功应用于许多离散优化问题。微粒群算法也是起源功应用于许多离散优
5、化问题。微粒群算法也是起源于对简单社会系统的模拟，最初是模拟鸟群觅食的于对简单社会系统的模拟，最初是模拟鸟群觅食的过程，但后来发现它是一种很好的优化工具。过程，但后来发现它是一种很好的优化工具。7 1.3 1.3 蚁群优化算法研究背景蚁群优化算法研究背景 与大多数基于梯度的应用优化算法不同，群智能依与大多数基于梯度的应用优化算法不同，群智能依靠的是概率搜索算法。虽然概率搜索算法通常要采用靠的是概率搜索算法。虽然概率搜索算法通常要采用较多的评价函数，但是与梯度方法及传统的演化算法较多的评价函数，但是与梯度方法及传统的演化算法相比，其优点还是显著的相比，其优点还是显著的 ，主要表现在以下几个方，主
6、要表现在以下几个方面：面：1 1 无集中控制约束，不会因个别个体的故障影响整无集中控制约束，不会因个别个体的故障影响整个问题的求解，确保了系统具备更强的鲁棒性个问题的求解，确保了系统具备更强的鲁棒性 2 2 以非直接的信息交流方式确保了系统的扩展性以非直接的信息交流方式确保了系统的扩展性 3 3 并行分布式算法模型，可充分利用多处理器并行分布式算法模型，可充分利用多处理器 4 4 对问题定义的连续性无特殊要求对问题定义的连续性无特殊要求 5 5 算法实现简单算法实现简单 8 1.3 1.3 蚁群优化算法研究背景蚁群优化算法研究背景 群智能方法易于实现，算法中仅涉及各种基本群智能方法易于实现，算
7、法中仅涉及各种基本的数学操作，其数据处理过程对的数学操作，其数据处理过程对CPU和内存的要求和内存的要求也不高。而且，这种方法只需目标函数的输出值，也不高。而且，这种方法只需目标函数的输出值，而无需其梯度信息。已完成的群智能理论和应用方而无需其梯度信息。已完成的群智能理论和应用方法研究证明群智能方法是一种能够有效解决大多数法研究证明群智能方法是一种能够有效解决大多数全局优化问题的新方法。更为重要是，群智能潜在全局优化问题的新方法。更为重要是，群智能潜在的并行性和分布式特点为处理大量的以数据库形式的并行性和分布式特点为处理大量的以数据库形式存在的数据提供了技术保证。无论是从理论研究还存在的数据提
8、供了技术保证。无论是从理论研究还是应用研究的角度分析，群智能理论及其应用研究是应用研究的角度分析，群智能理论及其应用研究都是具有重要学术意义和现实价值的。都是具有重要学术意义和现实价值的。9 1.4 1.4 蚁群优化算法研究现状蚁群优化算法研究现状 90年代年代Dorigo最早提出了蚁群优化算法最早提出了蚁群优化算法-蚂蚁系统蚂蚁系统（Ant System,AS）并将其应用于解决计算机算法学中经）并将其应用于解决计算机算法学中经典的旅行商问题（典的旅行商问题（TSP）。）。从蚂蚁系统开始，基本的蚁群算法得到了不断的发展和从蚂蚁系统开始，基本的蚁群算法得到了不断的发展和完善，并在完善，并在TSP
9、以及许多实际优化问题求解中进一步得到了以及许多实际优化问题求解中进一步得到了验证。这些验证。这些AS改进版本的一个共同点就是增强了蚂蚁搜索改进版本的一个共同点就是增强了蚂蚁搜索过程中对最优解的探索能力，它们之间的差异仅在于搜索控过程中对最优解的探索能力，它们之间的差异仅在于搜索控制策略方面。而且，取得了最佳结果的制策略方面。而且，取得了最佳结果的ACO是通过引入局部是通过引入局部搜索算法实现的，这实际上是一些结合了标准局域搜索算法搜索算法实现的，这实际上是一些结合了标准局域搜索算法的混合型概率搜索算法，有利于提高蚁群各级系统在优化问的混合型概率搜索算法，有利于提高蚁群各级系统在优化问题中的求解
10、质量。题中的求解质量。10 1.41.4蚁群优化算法研究现状蚁群优化算法研究现状 M.Dorigo 最初提出的最初提出的AS（Ant-System）有三种版本：）有三种版本：Ant-density(蚁密蚁密)、Ant-quantity（蚁量）和（蚁量）和Ant-cycle（蚁（蚁周）。周）。在在Ant-density和和Ant-quantity中蚂蚁在两个位置节点间每中蚂蚁在两个位置节点间每移动一次后即更新信息素，而在移动一次后即更新信息素，而在Ant-cycle中当所有的蚂蚁中当所有的蚂蚁都完成了自己的行程后才对信息素进行更新，而且每个蚂蚁都完成了自己的行程后才对信息素进行更新，而且每个蚂蚁
11、所释放的信息素被表达为反映相应行程质量的函数。通过与所释放的信息素被表达为反映相应行程质量的函数。通过与其它各种通用的启发式算法相比，在不大于其它各种通用的启发式算法相比，在不大于75城市的城市的TSP中，中，这三种基本算法的求解能力还是比较理想的，但是当问题规这三种基本算法的求解能力还是比较理想的，但是当问题规模扩展时，模扩展时，AS的解题能力大幅度下降。的解题能力大幅度下降。对此，后面的研究者提出了多种不同的改进蚁群算法。对此，后面的研究者提出了多种不同的改进蚁群算法。11 1.5 1.5 蚁群优化算法应用现状蚁群优化算法应用现状 随着群智能理论和应用算法研究的不断发展，研究者随着群智能理
12、论和应用算法研究的不断发展，研究者已尝试着将其用于各种工程优化问题，并取得了意想不到已尝试着将其用于各种工程优化问题，并取得了意想不到的收获。多种研究表明，群智能在离散求解空间和连续求的收获。多种研究表明，群智能在离散求解空间和连续求解空间中均表现出良好的搜索效果，并在组合优化问题中解空间中均表现出良好的搜索效果，并在组合优化问题中表现突出。表现突出。蚁群优化算法并不是旅行商问题的最佳解决方法，但蚁群优化算法并不是旅行商问题的最佳解决方法，但是它却为解决组合优化问题提供了新思路，并很快被应用是它却为解决组合优化问题提供了新思路，并很快被应用到其它组合优化问题中。比较典型的应用研究包括：网络到其
13、它组合优化问题中。比较典型的应用研究包括：网络路由优化、数据挖掘以及一些经典的组合优化问题。路由优化、数据挖掘以及一些经典的组合优化问题。12 1.5 1.5 蚁群优化算法应用现状蚁群优化算法应用现状 蚁群算法在电信路由优化中已取得了一定的应用成果。蚁群算法在电信路由优化中已取得了一定的应用成果。HP公司和英国电信公司在公司和英国电信公司在90年代中后期都开展了这方面的研年代中后期都开展了这方面的研究，设计了蚁群路由算法（究，设计了蚁群路由算法（Ant Colony Routing,ACR）。）。每只蚂蚁就像蚁群优化算法中一样，根据它在网络上的经每只蚂蚁就像蚁群优化算法中一样，根据它在网络上的
14、经验与性能，动态更新路由表项。如果一只蚂蚁因为经过了网验与性能，动态更新路由表项。如果一只蚂蚁因为经过了网络中堵塞的路由而导致了比较大的延迟，那么就对该表项做络中堵塞的路由而导致了比较大的延迟，那么就对该表项做较大的增强。同时根据信息素挥发机制实现系统的信息更较大的增强。同时根据信息素挥发机制实现系统的信息更新，从而抛弃过期的路由信息。这样，在当前最优路由出现新，从而抛弃过期的路由信息。这样，在当前最优路由出现拥堵现象时，拥堵现象时，ACR算法就能迅速的搜寻另一条可替代的最优算法就能迅速的搜寻另一条可替代的最优路径，从而提高网络的均衡性、负荷量和利用率。目前这方路径，从而提高网络的均衡性、负荷
15、量和利用率。目前这方面的应用研究仍在升温，因为通信网络的分布式信息结构、面的应用研究仍在升温，因为通信网络的分布式信息结构、非稳定随机动态特性以及网络状态的异步演化与非稳定随机动态特性以及网络状态的异步演化与ACO的算法的算法本质和特性非常相似。本质和特性非常相似。13 1.5 1.5 蚁群优化算法应用现状蚁群优化算法应用现状 ACO还在许多经典组合优化问题中获得了成功的应用，还在许多经典组合优化问题中获得了成功的应用，如二次规划问题（如二次规划问题（QAP）、机器人路径规划、作业流程规）、机器人路径规划、作业流程规划、图着色（划、图着色（Graph Coloring）等问题。）等问题。经过多
16、年的发展，经过多年的发展，ACO已成为能够有效解决实际二次已成为能够有效解决实际二次规划问题的几种重要算法之一。规划问题的几种重要算法之一。AS在作业流程计划（在作业流程计划（Job-shop Scheduling）问题中的应用实例已经出现，这说明了）问题中的应用实例已经出现，这说明了AS在此领域的应用潜力。利用在此领域的应用潜力。利用MAX-MIN AS解决解决PAQ也取也取得了比较理想的效果，并通过实验中的计算数据证明采用该得了比较理想的效果，并通过实验中的计算数据证明采用该方法处理方法处理PAQ比较早的比较早的SA算法更好，且与禁忌搜索算法性算法更好，且与禁忌搜索算法性能相当。利用能相当
17、。利用ACO实现对生产流程和特料管理的综合优化，实现对生产流程和特料管理的综合优化，并通过与遗传、模拟退火和禁忌搜索算法的比较证明了并通过与遗传、模拟退火和禁忌搜索算法的比较证明了ACO的工程应用价值。的工程应用价值。14 1.5 1.5 蚁群优化算法应用现状蚁群优化算法应用现状 许多研究者将许多研究者将ACO用于了武器攻击目标分配和优化用于了武器攻击目标分配和优化问题、车辆运行路径规划、区域性无线电频率自动分配、问题、车辆运行路径规划、区域性无线电频率自动分配、Bayesian networks的训练和集合覆盖等应用优化问题。的训练和集合覆盖等应用优化问题。Costa和和Herz还提出了一种
18、还提出了一种AS在规划问题方面的扩展应在规划问题方面的扩展应用用图着色问题，并取得了可与其他启发式算法相比的图着色问题，并取得了可与其他启发式算法相比的效果。效果。15 2 2 蚁群优化算法概念蚁群优化算法概念 2.1 蚁群算法原理蚁群算法原理 2.2 简化的蚂蚁寻食过程简化的蚂蚁寻食过程 2.3 自然蚁群与人工蚁群算法自然蚁群与人工蚁群算法 2.4 蚁群算法与蚁群算法与TSP问题问题 2.5 初始的蚁群优化算法初始的蚁群优化算法基于图的蚁群系统基于图的蚁群系统（GBAS）2.6 一般蚁群算法的框架一般蚁群算法的框架16 2.1 2.1 蚁群算法原理蚁群算法原理 蚁群算法是对自然界蚂蚁的寻径方
19、式进行模似而得出的一蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素下一种称之为外激素(pheromone)的物质进行信息传递，而且的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路正反馈现象：某一路径上走过的蚂蚁越多，则后来者
20、选择该路径的概率就越大。径的概率就越大。为了说明蚁群算法的原理，先简要介绍一下蚂蚁搜寻食物为了说明蚁群算法的原理，先简要介绍一下蚂蚁搜寻食物的具体过程。在蚁群寻找食物时，它们总能找到一条从食物到的具体过程。在蚁群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时就随机地挑选一条路径前行。与此同时释放出与路径长度时就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激
21、索浓度越低有关的信息素。路径越长，释放的激索浓度越低.当后来的蚂当后来的蚂蚁再次碰到这个路口的时候选择激素浓度较高路径概率就会蚁再次碰到这个路口的时候选择激素浓度较高路径概率就会相对较大。这样形成一个正反馈。最优路径上的激索浓度越来相对较大。这样形成一个正反馈。最优路径上的激索浓度越来越大而其它的路径上激素浓度却会随着时间的流逝而消减。越大而其它的路径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。最终整个蚁群会找出最优路径。17 蚂蚁觅食机理蚂蚁觅食机理18 其基本原理如下图：其基本原理如下图：上图表示蚂蚁觅食的线路，上图表示蚂蚁觅食的线路，A为蚁穴为蚁穴,B为食源，从到有两
22、条线路可为食源，从到有两条线路可走，走，是长路径，是长路径，是短路径是短路径.蚂蚁走过一条路线蚂蚁走过一条路线以后，在地面上会留下信息素气味，后来蚂蚁就是根据留在地面上这以后，在地面上会留下信息素气味，后来蚂蚁就是根据留在地面上这种气味的强度选择移动的方向种气味的强度选择移动的方向.A CBADB19 2.2 蚁群觅食中的简单规则蚁群觅食中的简单规则 每只蚂蚁只关心很小范围内的局部信息，而且根据这些局每只蚂蚁只关心很小范围内的局部信息，而且根据这些局部信息利用几条简单的规则进行决策部信息利用几条简单的规则进行决策。（1）范围：蚂蚁观察到的范围是一个方格世界速度半径）范围：蚂蚁观察到的范围是一个
23、方格世界速度半径（一般是（一般是3），移动的距离在这个方格范围之内），移动的距离在这个方格范围之内.（2）环境：蚂蚁所在的环境是一个虚拟世界，有障碍物、环境：蚂蚁所在的环境是一个虚拟世界，有障碍物、别的蚂蚁、信息素。信息素有两种，一种是找到食物的蚂蚁别的蚂蚁、信息素。信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素.每个蚂蚁都仅仅能感知它范围内的环境信息每个蚂蚁都仅仅能感知它范围内的环境信息.环境以一定的环境以一定的速率让信息素消失速率让信息素消失.（3）觅食规则：直接奔食物或看是否有信息素，并且朝）觅食
24、规则：直接奔食物或看是否有信息素，并且朝信息素多的地方走，还会以小概率犯错误，从而并不总是信息素多的地方走，还会以小概率犯错误，从而并不总是往信息素最多的点移动信息素最多的点移动.20 （4）移动规则：每只蚂蚁都朝向信息素最多的方向）移动规则：每只蚂蚁都朝向信息素最多的方向移，当周围没有信息素指引的时候，蚂蚁会按照原来运动移，当周围没有信息素指引的时候，蚂蚁会按照原来运动的方向惯性的运动下去，在运动的方向有一个随机的小的的方向惯性的运动下去，在运动的方向有一个随机的小的扰动扰动.为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点
25、已经在最近走过了，它就会尽点，如果发现要走的下一点已经在最近走过了，它就会尽量避开量避开.（5）避障规则：如果蚂蚁要移动的方向有障碍物挡住，）避障规则：如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为会按照觅食的规则行为.（6）播撒信息素规则：每只蚂蚁在刚找到食物或者窝的）播撒信息素规则：每只蚂蚁在刚找到食物或者窝的时候散发的信息素最多，并随着它走的距离越远，播撒的时候散发的信息素最多，并随着它走的距离越远，播撒的信息素越来越少信息素越来越少.21 2.3 自然蚁群与人工蚁群自然蚁群与人工
26、蚁群人工蚁是自然蚁群的抽象：人工蚁是自然蚁群的抽象：(1)人工蚁与真实蚁一样，通人工蚁与真实蚁一样，通过相互协调与合作从而有可能找到全局最优方案，而每只过相互协调与合作从而有可能找到全局最优方案，而每只人工蚁的单独行动只可能找到局部最优解人工蚁的单独行动只可能找到局部最优解.(2)人工蚁和真实蚁一样，都要寻找一个从源节点（巢人工蚁和真实蚁一样，都要寻找一个从源节点（巢穴）到目的节点（食物源）之间的最短路径（或最小代穴）到目的节点（食物源）之间的最短路径（或最小代价），人工蚂蚁与真实蚂蚁一样都不能跳跃，必须在相邻价），人工蚂蚁与真实蚂蚁一样都不能跳跃，必须在相邻节点之间移动，直至遍历所有可能路径
27、，为了减少计算复节点之间移动，直至遍历所有可能路径，为了减少计算复杂度并寻找出最短路径，需要记录当前路径杂度并寻找出最短路径，需要记录当前路径.(3)人工蚁与真实蚁一样都通过使用信息素进行间接通信人工蚁与真实蚁一样都通过使用信息素进行间接通信真实蚂蚁在经过的路径上留下信息素，人工蚁则不断修改真实蚂蚁在经过的路径上留下信息素，人工蚁则不断修改更新在其所经过的路径上存储的信息，是一种模拟自然界更新在其所经过的路径上存储的信息，是一种模拟自然界中的信息素轨迹更新的过程中的信息素轨迹更新的过程.22 (4)人工蚁利用真实蚁觅食行为中的自催化机制人工蚁利用真实蚁觅食行为中的自催化机制正反馈正反馈 当一些
28、路径上通过的蚂蚁越来越多时，路径上留下的信息素轨迹也当一些路径上通过的蚂蚁越来越多时，路径上留下的信息素轨迹也越来越多，使得信息素强度变大，根据蚂蚁群倾向于选择信息强度越来越多，使得信息素强度变大，根据蚂蚁群倾向于选择信息强度大的特点，后来的蚂蚁选择该路径的概率也越高，从而增加了该路大的特点，后来的蚂蚁选择该路径的概率也越高，从而增加了该路径的信息素强度（自催化过程），自催化机制利用信息素作为反馈，径的信息素强度（自催化过程），自催化机制利用信息素作为反馈，通过对系统演化过程中较优解的增强作用，使得问题的解向着全局通过对系统演化过程中较优解的增强作用，使得问题的解向着全局最优的方向逐步接近最优
29、的方向逐步接近.(5)信息素的挥发机制信息素的挥发机制 在蚁群算法中设置一种挥发机制，类似于真实信息素的挥发，这在蚁群算法中设置一种挥发机制，类似于真实信息素的挥发，这种机制需要蚂蚁忘记过去，不受过去经验的过分约束，有利于指引种机制需要蚂蚁忘记过去，不受过去经验的过分约束，有利于指引蚂蚁朝着新的方向搜索，避免早熟收敛蚂蚁朝着新的方向搜索，避免早熟收敛.(6)利用当前信息进行路径选择的随机选择策略利用当前信息进行路径选择的随机选择策略 人工蚁与真实蚁都是利用概率选择策略实现一个节点到相邻节人工蚁与真实蚁都是利用概率选择策略实现一个节点到相邻节点的移动，选择策略只利用当前的信息去预测未来的情况，而
30、不能点的移动，选择策略只利用当前的信息去预测未来的情况，而不能利用未来的信息，因此，人工蚁与真实蚁所使用的选择策略在时间利用未来的信息，因此，人工蚁与真实蚁所使用的选择策略在时间和空间上都具有局部特性和空间上都具有局部特性.23 人工蚁具备一些真实蚁所不具备的特征，主要体现在下人工蚁具备一些真实蚁所不具备的特征，主要体现在下列五个方面：列五个方面：(1)人工蚁存在于离散空间中，它们的移动实质上是有一人工蚁存在于离散空间中，它们的移动实质上是有一个离散状态到另一个离散状态的转移；个离散状态到另一个离散状态的转移；(2)人工蚁具有一个记录其过去自身行为的内在状态（记人工蚁具有一个记录其过去自身行为
31、的内在状态（记忆特性）；忆特性）；(3)人工蚁存在于与时间无关联的环境之中；人工蚁存在于与时间无关联的环境之中；(4)人工蚁并非完全盲从，它受到问题特征的启发，例人工蚁并非完全盲从，它受到问题特征的启发，例如，有的问题中人工蚂蚁产生一个解后改变信息量，而在有如，有的问题中人工蚂蚁产生一个解后改变信息量，而在有的问题中人工蚂蚁每做一次选择便改变信息量；的问题中人工蚂蚁每做一次选择便改变信息量；(5)为了提升人工蚁系统的性能，改进算法效率，人工蚁为了提升人工蚁系统的性能，改进算法效率，人工蚁可增加一些性能，如预测未来、局部优化、回溯等可增加一些性能，如预测未来、局部优化、回溯等.24 2.3 2.
32、3 蚁群算法与蚁群算法与TSPTSP问题问题 2.3.1 2.3.1 蚁群算法模型的建立蚁群算法模型的建立 （1 1）蚂蚁个体的抽象蚂蚁个体的抽象:抽象出能够为建立模型起作用的真抽象出能够为建立模型起作用的真 实蚁群的机理，摒弃与建立模型算法无关的因素实蚁群的机理，摒弃与建立模型算法无关的因素.（2 2）问题空间的描述问题空间的描述:蚂蚁轨迹可以看成二维平面上的活蚂蚁轨迹可以看成二维平面上的活动，其活动过程为一个状态到另一个状态的迁移，利用蚁动，其活动过程为一个状态到另一个状态的迁移，利用蚁群算法求解的采用图论语言来描述就显得非常自然，另一群算法求解的采用图论语言来描述就显得非常自然，另一方面
33、，在实际问题中的许多应用问题可以通过图的语言来方面，在实际问题中的许多应用问题可以通过图的语言来描述，这就使得蚁群算法的广泛应用成为可能描述，这就使得蚁群算法的广泛应用成为可能.（3 3）寻找路径的抽象寻找路径的抽象:把真实蚂蚁的觅食过程抽象成算把真实蚂蚁的觅食过程抽象成算法中解的构造过程，将信息素抽象成存在于图边上的轨迹，法中解的构造过程，将信息素抽象成存在于图边上的轨迹，信息素的大小可以通过设置权重来体现，并根据权重的值信息素的大小可以通过设置权重来体现，并根据权重的值决定走向下一个节点的概率决定走向下一个节点的概率.用任何两个节点分别表示蚂蚁用任何两个节点分别表示蚂蚁的巢穴（初始节点）和
34、食物源（终止节点），人工蚂蚁按的巢穴（初始节点）和食物源（终止节点），人工蚂蚁按照一定的状态转移概率从初始节点移动到邻近的节点，以照一定的状态转移概率从初始节点移动到邻近的节点，以此类推，最终选择行走到目标节点，从而得到问题的一个此类推，最终选择行走到目标节点，从而得到问题的一个可行解可行解.25 （4 4）信息素挥发的抽象）信息素挥发的抽象:自然界中真实蚂蚁在所自然界中真实蚂蚁在所经过的路径上会连续不断的留下信息素，而信息素也会经过的路径上会连续不断的留下信息素，而信息素也会随着时间的推移连续不断的挥发，在人工蚁群算法中，随着时间的推移连续不断的挥发，在人工蚁群算法中，蚂蚁完成从某一节点到相
35、邻节点的一次移动后（相应于蚂蚁完成从某一节点到相邻节点的一次移动后（相应于经过一个时间单位），进行一次信息素挥发，这有利于经过一个时间单位），进行一次信息素挥发，这有利于避免陷入局部最优的陷阱避免陷入局部最优的陷阱.（5 5）启发因子的引入）启发因子的引入:为了设计有效的蚁群算法，为了设计有效的蚁群算法，在决定蚂蚁行走方向的状态转移概率时，引入一个随机在决定蚂蚁行走方向的状态转移概率时，引入一个随机搜索的过程，即引入一个启发因子，根据所求问题空间搜索的过程，即引入一个启发因子，根据所求问题空间的具体特征，给蚁群算法一个初始的引导，从而极大的的具体特征，给蚁群算法一个初始的引导，从而极大的增加算
36、法的有效性，从而使蚁群算法的有效应用成为可增加算法的有效性，从而使蚁群算法的有效应用成为可能能.26 2.3.2 旅行商问题（）与蚁群算法旅行商问题（）与蚁群算法 TSP问题描述如下：设有问题描述如下：设有n个城市，用数码个城市，用数码1,n代表代表.城市和城市之间的距离为城市和城市之间的距离为TSP问题是问题是要找遍访每个域市恰好一次的一条回路，且其要找遍访每个域市恰好一次的一条回路，且其路径总长度为最短路径总长度为最短.图论模型：图论模型：给定图，其中给定图，其中V为顶点集，为顶点集，A为各定点相为各定点相互连接组成的边集，已知各顶点间的连接距离，要求确互连接组成的边集，已知各顶点间的连接
37、距离，要求确定一条最短的定一条最短的Hamilton回路，即遍历所有顶点当且仅当回路，即遍历所有顶点当且仅当一次的最短回路一次的最短回路.Hamilton回路：回路：经过图（有向图或无向图）中所有顶经过图（有向图或无向图）中所有顶点一次且仅一次的通路点一次且仅一次的通路 。27 TSP问题表示为一个问题表示为一个N个城市的有向图个城市的有向图G=（N，A），），其中其中城市之间距离城市之间距离目标函数为目标函数为 其中其中 为城市为城市1,2，n的一个排的一个排列，列，。N 1,2,n A(i,j)|,i j Nnnijd)(nliilldwf11)(),(21niiiw11iin28 以以T
38、SP为例，基本蚁群算法的具体实现步骤描述如下：为例，基本蚁群算法的具体实现步骤描述如下：（1 1）参数初始化）参数初始化 （2 2）循环循环 （3 3）蚂蚁个体根据状态转移概率公式计算的概率选择）蚂蚁个体根据状态转移概率公式计算的概率选择沿元素（城市）沿元素（城市）j j前进，前进，（4 4）修改禁忌指针表，即将选择好之后的蚂蚁移动到）修改禁忌指针表，即将选择好之后的蚂蚁移动到新的元素（城市），并将该元素（城市）移到该蚂蚁个体的新的元素（城市），并将该元素（城市）移到该蚂蚁个体的禁忌表中；禁忌表中；（5 5）信息素更新的计算）信息素更新的计算 （6 6）纪录到目前为止的最短路径，如果）纪录到目
39、前为止的最短路径，如果 ，则计，则计算终止，循环结束并输出计算结果，否则，清空禁忌表并返算终止，循环结束并输出计算结果，否则，清空禁忌表并返回步骤（回步骤（2 2）.整个计算过程所耗的空间复杂度为整个计算过程所耗的空间复杂度为 .maxcNN2()O nnm29 例例2 2：0-10-1背包问题的解顺序表达形式与算法实现。设有一背包问题的解顺序表达形式与算法实现。设有一个容积为个容积为b b的背包，的背包，n n个尺寸分别为个尺寸分别为 ，价，价值分别为值分别为 的物品，的物品，0-10-1背包问题的数学模背包问题的数学模型为：型为：假设其解的顺序表达形式为，其中假设其解的顺序表达形式为，其中
40、 为的一个排列。为的一个排列。(1,2,.,)ia in(1,2,.,)ic in11m a x.0,1,1,.,niiiniiiic xs ta xbxjn120,.,niii12,.,ni ii1,2,3,.,n30 建立有向图建立有向图 ，其中，其中 A中共有中共有 条弧。初始信息素痕迹定义为条弧。初始信息素痕迹定义为 。设第设第s只蚂蚁第只蚂蚁第k步所走的路线为步所走的路线为 ，表示蚂蚁从表示蚂蚁从0点出发，顺序到达点出发，顺序到达 。第。第 步按步按TSP算法的转移概率公式行走选择算法的转移概率公式行走选择 。若。若 则则 ，否则，此蚂蚁不再继续行，否则，此蚂蚁不再继续行走，退回起点
41、。走，退回起点。(,)GVA0,1,2,.,(,)|,VnAijijV(1)n n 1(1)ijnn12()(0,.,)kLsiii12,.,kiii1k 1ki11jkijab121()(0,.,)kkLsiiii31 对蚁群重复以上过程，比较对蚁群重复以上过程，比较m只蚂蚁的装包值只蚂蚁的装包值 并记忆具有最大装包值的蚂蚁为并记忆具有最大装包值的蚂蚁为t。把。把AS算法中步骤算法中步骤3中的中的改为改为 ，若满足此条件则替换当前最好解为，若满足此条件则替换当前最好解为 ，对对W上的弧进行信息素的加强，其他弧进行信息素的挥发。上的弧进行信息素的加强，其他弧进行信息素的挥发。算法中记录了三个信
42、息：信息素痕迹算法中记录了三个信息：信息素痕迹 ；行走路线；行走路线 ；和问题的约束条件；和问题的约束条件，以确定是否将以确定是否将 加入。加入。()0,1,2,.,ii L sic sm()()f L tf w()()f Ltf w:()WL tij121()(0,.,)kkL si iii11jkijab1ki32 算法中需要记忆的信息有三部分。算法中需要记忆的信息有三部分。第一部分信息是存在每个节点路由表数据结构第一部分信息是存在每个节点路由表数据结构 ，由此决定的的转移概率为由此决定的的转移概率为其中其中T T可以看成节点可以看成节点i i的邻域。的邻域。|(,)iijAai jA(1
43、)(1)|(,)iijA kaki jA(1)(1),0ijili jlTakjTakPjT(1)(1)(1)(1)(1),0ijijililijl Tkkkka kjTjT33 第二部分需要记忆的信息是每个蚂蚁的记忆表中存储着的自第二部分需要记忆的信息是每个蚂蚁的记忆表中存储着的自身的历史信息，这一部分主要由算法的中的身的历史信息，这一部分主要由算法的中的 记忆，表示记忆，表示蚂蚁已经行走过的节点。蚂蚁已经行走过的节点。第三部分为问题的约束条件。在第三部分为问题的约束条件。在GBAS中，中，T集合表示满足集合表示满足约束条件的候选集，在背包问题的蚁群算法中由判别条件约束条件的候选集，在背包问
44、题的蚁群算法中由判别条件 ，实现记忆功能。实现记忆功能。()L s11jkijab121()(0,.,)kkL si iii34 基于最大基于最大-最小蚁群算法的指派问题求解最小蚁群算法的指派问题求解一、指派问题模型一、指派问题模型有有 个人和个人和 个任务，已知第个任务，已知第 个人做第个人做第 个任务的费用为个任务的费用为 ，要求确，要求确定人和任务之间的一一对应的指派方案，使完成这些任务的总费用定人和任务之间的一一对应的指派方案，使完成这些任务的总费用最少。最少。数学模型：数学模型：njijijixij,2,1,人做第指派若0人做第若指派第1个任务第不个任务nnnnnnnCCCCCCCC
45、CCCCC32122322211131211(1)zmin 11ninjijijxc)4(),2,1,(10)3(),2,1(1(2),2,1(1.1jn1njixnixnjxt sijnijiij或nnijcij35 在改进的蚁群算法之最大在改进的蚁群算法之最大最小蚁群系统（最小蚁群系统（Max-Min Ant System）MMAS系统系统 中每次只对迭代最优蚂蚁或到目前为止全局中每次只对迭代最优蚂蚁或到目前为止全局最优的蚂蚁进行信息素更新（不是像蚂蚁系统对所有走过路最优的蚂蚁进行信息素更新（不是像蚂蚁系统对所有走过路径进行信息素更新）；每个解的元素上的信息素轨迹量值域径进行信息素更新）；
46、每个解的元素上的信息素轨迹量值域限制在限制在 区间内（不同于蚂蚁系统中信息素轨迹量区间内（不同于蚂蚁系统中信息素轨迹量不被限制，使得一些路径上轨迹量远高于其它边导致搜素停不被限制，使得一些路径上轨迹量远高于其它边导致搜素停滞）；精心设计信息素初始化值，以保证更容易探索新的滞）；精心设计信息素初始化值，以保证更容易探索新的解（蚂蚁系统中没有考虑该因素导致算法收敛性较差）；引解（蚂蚁系统中没有考虑该因素导致算法收敛性较差）；引入信息素轨迹的平滑机制，以增加探索新解的能力，加快算入信息素轨迹的平滑机制，以增加探索新解的能力，加快算法的收敛速度以及提高算法的数值稳定性。法的收敛速度以及提高算法的数值稳
47、定性。（MMAS系统系统1996年由年由M Luca与与Cambradella等人提出）等人提出）minmax,36 改进算法描述改进算法描述设需要指派3个人去完成3个任务，并知道每个人完成每个任务所需的费用，则可得到一个三行三列的系数矩阵。指派问题的系数矩阵形成移动矩阵相同行的不同列之间移动，并且此列未到达过信息素集中在节点转到下一个节点的代价为下一个节点的系数矩阵值转移概率并非选择最大节点，有干扰因子到达一个节点，立即进行节点信息素的更新所有蚂蚁完成一次觅食，比较次优解，全局信息素的更新改进算法模型37 改进算法模型改进算法模型 转移概率。产生随机数转移概率。产生随机数 ，如果，如果 ，则
48、根据下式，蚂，则根据下式，蚂蚁移向概率最大的节点。否则在可选节点中随机选择一个。蚁移向概率最大的节点。否则在可选节点中随机选择一个。局部信息素更新。当蚂蚁选择此节点后，立即更新此节点的信息素。局部信息素更新。当蚂蚁选择此节点后，立即更新此节点的信息素。全局信息素更新。当所有蚂蚁完成一次觅食后，得到次优解。优于全全局信息素更新。当所有蚂蚁完成一次觅食后，得到次优解。优于全局最优解，更新全局信息素。局最优解，更新全局信息素。,1,1)(1)()1(,Crqnimpcncnnpmnamnpqapqpqij)10(0totalpqpqcQ)1()(,)1(Nnodepqpqpqpq38 实验描述实验描
49、述实验目的：得到信息素启发因子，期望值启发因子，干扰因实验目的：得到信息素启发因子，期望值启发因子，干扰因子，蚂蚁数量，局部信息素挥发系数，全局信息素的挥发系子，蚂蚁数量，局部信息素挥发系数，全局信息素的挥发系数范围数范围规模为规模为1010的干扰因子实验设置及结果，的干扰因子实验设置及结果，1010次，迭代次数不同次，迭代次数不同 所有实验所有实验39 实验目的：验证算法的有效性实验目的：验证算法的有效性61012961061476781296101417971215784C参数设置及结果-40 o与标准蚁群算法性能对比与标准蚁群算法性能对比2381201791751091112291471
50、97201117111157126142170206101172228210198219170225110117103179126217229149177110160167106158222154238197178238221117236234108237128241167172172194114208223168184249114207221156102228163149122110228214141190102163114144115183124155243102199120140149161218106216119102106230204C参数设置及结果-41 另外还有两种改进蚁群算法以
