蚁群算法详细讲解

《蚁群算法详细讲解》由会员分享，可在线阅读，更多相关《蚁群算法详细讲解（81页珍藏版）》请在金锄头文库上搜索。

1、1蚁群算法及其应用1.蚂蚁觅食行 为与觅食策略2.蚂蚁系统 蚁群系统的原 型3.改进的蚁群优 化算法4.蚁群优化算法的 仿真研究5.蚁群算法的应用 对QoS组播路由 问题求解2341.1 蚁群优化算法概述n1.1.1 起源n1.1.2 应用领域n1.1.3 研究背景n1.1.4 研究现状n1.1.5 应用现状51.1.1 蚁群优化算法起源20世纪50年代中期创立了仿生学，人们从生物进化的机理中 受到启发。提出了许多用以解决复杂优化问题的新方法，如进 化规划、进化策略、遗传算法等，这些算法成功地解决了一些 实际问题。20世纪90年代意大利学者MDorigo，VManiezzo，A Colorni

2、等从生物进化的机制中受到启发，通过模拟自然界蚂蚁 搜索路径的行为，提出来一种新型的模拟进化算法 蚁群算 法，是群智能理论研究领域的一种主要算法。用该方法求解TSP 问题、分配问题、job-shop调度问题，取得了较好的试验结果 虽然研究时间不长，但是现在的研究显示出，蚁群算法在求 解复杂优化问题（特别是离散优化问题）方面有一定优势，表 明它是一种有发展前景的算法61.1.2 蚁群优化算法应用领域这种方法能够被用于解决大多数优化问题或 者能够转化为优化求解的问题。现在其应用领 域已扩展到多目标优化、数据分类、数据聚类 、模式识别、电信QoS管理、生物系统建模、流 程规划、信号处理、机器人控制、决

3、策支持以 及仿真和系统辩识等方面，群智能理论和方法 为解决这类应用问题提供了新的途径。72.1.3 蚁群优化算法研究背景 1/3群智能理论研究领域有两种主要的算法：蚁 群算法(Ant Colony Optimization, ACO)和微粒 群算法（Particle Swarm Optimization, PSO） 。前者是对蚂蚁群落食物采集过程的模拟，已 成功应用于许多离散优化问题。微粒群算法也 是起源于对简单社会系统的模拟，最初是模拟 鸟群觅食的过程，但后来发现它是一种很好的 优化工具。81.1.3 蚁群优化算法研究背景 2/3与大多数基于梯度的应用优化算法不同，群智能依靠的是 概率搜索算

4、法。虽然概率搜索算法通常要采用较多的评价 函数，但是与梯度方法及传统的演化算法相比，其优点还 是显著的 ，主要表现在以下几个方面： 1 无集中控制约束，不会因个别个体的故障影响整个问 题的求解，确保了系统具备更强的鲁棒性 2 以非直接的信息交流方式确保了系统的扩展性 3 并行分布式算法模型，可充分利用多处理器 4 对问题 定义的连续性无特殊要求 5 算法实现简单 91.1.3 蚁群优化算法研究背景 3/3群智能方法易于实现，算法中仅涉及各种基本的数学 操作，其数据处理过程对CPU和内存的要求也不高。而 且，这种方法只需目标函数的输出值，而无需其梯度 信息。已完成的群智能理论和应用方法研究证明群

5、智 能方法是一种能够有效解决大多数全局优化问题的新 方法。更为重要是，群智能潜在的并行性和分布式特 点为处理大量的以数据库形式存在的数据提供了技术 保证。无论是从理论研究还是应用研究的角度分析， 群智能理论及其应用研究都是具有重要学术意义和现 实价值的。 101.1.4 蚁群优化算法研究现状 1/790年代Dorigo最早提出了蚁群优化算法-蚂蚁系统（ Ant System, AS）并将其应用于解决计算机算法学中 经典的旅行商问题（TSP）。从蚂蚁系统开始，基本的 蚁群算法得到了不断的发展和完善，并在TSP以及许多 实际优化问题求解中进一步得到了验证。这些AS改进 版本的一个共同点就是增强了蚂

6、蚁搜索过程中对最优 解的探索能力，它们之间的差异仅在于搜索控制策略 方面。而且，取得了最佳结果的ACO是通过引入局部 搜索算法实现的，这实际上是一些结合了标准局域搜 索算法的混合型概率搜索算法，有利于提高蚁群各级 系统在优化问题中的求解质量。111.1.4蚁群优化算法研究现状 2/7最初提出的AS有三种版本：Ant-density、Ant-quantity和Ant-cycle 。在Ant-density和Ant-quantity中蚂蚁在两个位置节点间每移动一次后 即更新信息素，而在Ant-cycle中当所有的蚂蚁都完成了自己的行程后才 对信息素进行更新，而且每个蚂蚁所释放的信息素被表达为反映相

7、应行 程质量的函数。通过与其它各种通用的启发式算法相比，在不大于75城 市的TSP中，这三种基本算法的求解能力还是比较理想的，但是当问题 规模扩展时，AS的解题能力大幅度下降。因此，其后的ACO研究工作主要都集中于AS性能的改进方面。较早 的一种改进方法是精英策略(Elitist Strategy)，其思想是在算法开始后即 对所有已发现的最好路径给予额外的增强，并将随后与之对应的行程记 为Tgb(全局最优行程)，当进行信息素更新时，对这些行程予以加权， 同时将经过这些行程的蚂蚁记为“精英”，从而增大较好行程的选择机会 。这种改进型算法能够以更快的速度获得更好的解。但是若选择的精英过多则算法会由

8、于较早的收敛于局部次优解而导致搜索的过早停滞。 121.1.4蚁群优化算法研究现状 3/7为了进一步克服AS中暴露出的问题，提出了蚁群系统(Ant Colony System, ACS)。该系统的提出是以Ant-Q算法为基础的 。Ant-Q将蚂蚁算法和一种增强型学习算法Q-learning有机的结 合了起来。ACS与AS之间存在三方面的主要差异：首先，ACS 采用了更为大胆的行为选择规则；其次，只增强属于全局最优 解的路径上的信息素。其中，01是信息素挥发参数， 是从寻路开始到当前为止全局最优的路径长度。131.1.4蚁群优化算法研究现状 4/7再次，还引入了负反馈机制，每当一只蚂蚁由一 个节

9、点移动到另一个节点时，该路径上的信息素 都按照如下公式被相应的消除一部分，从而实现 一种信息素的局部调整，以减小已选择过的路径 再次被选择的概率。 141.1.4蚁群优化算法研究现状 5/7在对AS进行直接完善的方法中，MAX-MIN Ant System 是一个典型代表。该算法修改了AS的信息素更新方式 ，每次迭代之后只有一只蚂蚁能够进行信息素的更新 以获取更好的解。为了避免搜索停滞，路径上的信息 素浓度被限制在MAX，MIN 范围内，另外，信息素 的初始值被设为其取值上限，这样有助于增加算法初 始阶段的搜索能力。151.1.4蚁群优化算法研究现状 6/7另一种对AS改进的算法是Rank-b

10、ased Version AS。与“ 精英策略”相似，在此算法中总是更新更好进程上的信 息素，选择的标准是其行程长度 决定的排序，且每个蚂蚁放置信息素的强度通过下式中 的排序加权处理确定，其中，为每次迭代后放置信息 素的蚂蚁总数。 161.1.4蚁群优化算法研究现状 7/7这种算法求解TSP的能力与AS、精英策略AS、 遗传算法和模拟退火算法进行了比较。在大型 TSP问题中（最多包含132座城市），基于AS 的算法都显示出了优于GA和SA的特性。而且 在Rank-based AS和精英策略AS均优于基本AS 的同时，前者还获得了比精英策略AS更好的解 。 171.1.5 蚁群优化算法应用现状

11、1/5随着群智能理论和应用算法研究的不断发展，研究者 已尝试着将其用于各种工程优化问题，并取得了意想不到 的收获。多种研究表明，群智能在离散求解空间和连续求 解空间中均表现出良好的搜索效果，并在组合优化问题中 表现突出。蚁群优化算法并不是旅行商问题的最佳解决方法，但 是它却为解决组合优化问题提供了新思路，并很快被应用 到其它组合优化问题中。比较典型的应用研究包括：网络 路由优化、数据挖掘以及一些经典的组合优化问题。 181.1.5 蚁群优化算法应用现状 2/5蚁群算法在电信路由优化中已取得了一定的应用成果。HP公 司和英国电信公司在90年代中后期都开展了这方面的研究， 设计了蚁群路由算法（An

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

13、群智能的聚类算法起源于对蚁群蚁卵的分类研究 。Lumer和Faieta将Deneubourg提出将蚁巢分类模型 应用于数据聚类分析。其基本思想是将待聚类数据随 机地散布到一个二维平面内，然后将虚拟蚂蚁分布到 这个空间内，并以随机方式移动，当一只蚂蚁遇到一 个待聚类数据时即将之拾起并继续随机运动，若运动 路径附近的数据与背负的数据相似性高于设置的标准 则将其放置在该位置，然后继续移动，重复上述数据 搬运过程。按照这样的方法可实现对相似数据的聚类 。201.1.5 蚁群优化算法应用现状 4/5ACO还在许多经典组合优化问题中获得了成功的应用 ，如二次规划问题（QAP）、机器人路径规划、作业 流程规

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

15、器攻击目标分配和 优化问题、车辆运行路径规划、区域性无线电 频率自动分配、Bayesian networks的训练和集 合覆盖等应用优化问题。Costa和Herz还提出 了一种AS在规划问题方面的扩展应用图着 色问题，并取得了可与其他启发式算法相比的 效果。221.2 蚁群优化算法概念1.2.1 蚁群算法原理 1.2.2 简化的蚂蚁寻食过程 1.2.3 自然蚁群与人工蚁群算法 1.2.4 蚁群算法与TSP问题 1.2.5 初始的蚁群优化算法基于图的 蚁群系统（GBAS） 1.2.6 一般蚁群算法的框架231.2.1 蚁群算法原理蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿 生算法。蚂

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