蚁群算法的基本原理及其应用

蚁群算法的基本原理及其应用专业：控制理论与控制工程年级：姓名：学号：指导老师：蚁群算法蚁群算法的原理、特点蚁群算法的模型蚁群算法的研究及应用蚁群算法的提出蚁群算法(antcolonyoptimization,ACO)，又称蚂蚁算法，是一种用来寻找优化路径的机率型算法。它由MarcoDorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。MacroDorigo蚁群现象：在蚁群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径，并且能随着环境的变化而变化的搜索新的最优路径。NestFoodObstacle图1蚂蚁正常行进，突然环境改变，增加了障碍物NestFoodObstacle图2蚂蚁以等同概率选择各条路径紧接着，随着时间的增加较短路径信息素浓度高，选择该路径的蚂蚁逐渐增多图3蚂蚁选路过程示例EABDHCEABDHCd=0.5d=0.5d=1d=130ants30ants15ants15ants15ants15antst=0EABDHC30ants30ants20ants20ants10ants10antst=1NestFoodObstacle图4蚂蚁最终绕过障碍物找到最优路径蚁群算法原理蚂蚁在寻找食物源时，能在其走过的路上释放一种特殊的分泌物——信息素(随着时间的推移该物质会逐渐挥发)，

后来的蚂蚁选择该路径的概率与当时这条路径上该物质的强度成正比.当某路径上通过的蚂蚁越来越多时，其留下的信息素轨迹也越来越多，后来蚂蚁选择该路径的概率也越高，更增加了该路径的信息素强度。而强度大的信息素会吸引更多的蚂蚁，从而形成一种正反馈机制,通过这种正反馈机制，蚂蚁最终可以发现最短路径。

特别地，当蚂蚁巢穴与食物源之间出现障碍物时，蚂蚁不仅可以绕过障碍物，而且通过蚁群信息素轨迹在不同路径上的变化，经过一段时间的正反馈，最终收敛到最短路径上。蚁群算法的特点（1）其原理是一种正反馈机制或称增强型学习系统；它通过信息素的不断更新达到最终收敛于最优路径上；（2）它是一种通用型随机优化方法；但人工蚂蚁决不是对实际蚂蚁的一种简单模拟，它融进了人类的智能；（3）它是一种分布式的优化方法；不仅适合目前的串行计算机，而且适合未来的并行计算机；（4）它是一种全局优化的方法；不仅可用于求解单目标优化问题，而且可用于求解多目标优化问题；（5）它是一种启发式算法；计算复杂性为

其中NC是迭代次数，m是蚂蚁数目，n是目的节点数目。(1)参数初始化。令时间

和循环次数

，设置最大循环次数

，将m只蚂蚁置于

n(m<n)个城市上

，令有向图上每条边

(i,j)的初始化信息量

，其中

表示常数，且初始时刻

。(2)循环次数

。(3)蚂蚁数目

。(4)蚂蚁个体根据状态转移概率公式(后面介绍)计算的概率选择城市

j并前进，(5)修改禁忌表指针，即选择好之后将蚂蚁移动到新的城市，并把该城市移动到该蚂蚁个体的禁忌表中。(6)若集合C中城市未遍历完，即

k<m，则跳转到第(3)步，否则执行第(7)步。(7)更新每条路径上的信息量，计算公式将在后面介绍。(8)若满足结束条件，即如果循环次数

，则循环结束并输出程序计算结果，否则清空禁忌表并跳转到第(2)步。蚁群算法求解的一般步骤

蚁群算法流程图禁忌表：与真实蚁不同，人工蚁群系统具有记忆功能。为了满足蚂蚁必须经过所有n个不同的城市这个约束条件，为每只蚂蚁都设计了一个数据结构，成为禁忌表。用来记录了t时刻蚂蚁已经经过的城市，不允许该蚂蚁在本次循环中再经过这些城市。当本次循环结束后禁忌表被用来计算该蚂蚁所建立的解决方案。之后禁忌表清空蚂蚁又可以自由地选择。蚁群算法相关符号的定义

m

——蚂蚁个数;

n——结点（顶点）个数;——边弧

的能见度（visibility）,或称局部启发因子，一般取，表示路径之间的长度;（由城市i转移到城市j的可见度亦称启发信息）——边弧的信息素轨迹强度（intensity）;——蚂蚁k于弧上留下的单位长度轨迹信息素数量;——蚂蚁k在结点的转移概率，j是尚未访问结点;——信息素轨迹的相对重要性（）;

——边弧能见度的相对重要性（）;蚁群算法符号的定义——

信息素轨迹的持久性（），可理解为轨迹衰减度（evaporation）；

——体现蚂蚁所留轨迹数量的一个常数；

——可行结点集合；——为第k只蚂蚁在第结点i出发下一步的可行结点集；——一个列表，用于记录第k只蚂蚁到目前为止已经访问的城市。AS模型（AntSystem简称AS）

蚂蚁系统（AS）是第一个蚁群优化算法（ACO），它是意大利科学家Dorigo

在1991年最先提出，并成功地用于求解著名的组合爆炸问题TSP问题，后经他本人（1992,1996,2000）及学者Colorni，Maniezzo(1997,1999)等进一步研究，将其系统化。其主要参数变量表达如下：

选择概率：

信息素更新方程为：按的不同取法,可形成三种类型的蚂蚁算法模型:(1)

蚂蚁密度模型（AntDensity）：(2)

蚂蚁数量模型（AntQuantity）：(3)

蚂蚁圈模型（AntCycle）：

其中:

可行结点集合，具体应用中经常用表示，为第k只蚂蚁在第i结点出发下一步的可行结点集，为第k只蚂蚁在本次循环中所走的路径的长度。

上述三种模型中，蚂蚁密度模型和蚂蚁数量模型利用的是局部信息，而蚂蚁圈模型利用的是全局信息，对全局优化较好。ACS（AntColonySystem）模型

Dorigo与Gambardella等学者在1997年在Ant-Q算法的基础上进行修改，为了平衡寻找更好结果和寻找更大的搜索空间，Pseudo-Random-Proportionalrule（伪随机概率选择）下状态转移如下：

V按照下面概率选择

这里是将Ant-Q模型中，更重要地是给出了局部在线和全局离线的两种信息素轨迹更新方式：q为一个区间[0，1]之间的随机数，q0是一[0，1]之间的参数

LocalUpdating(onlineupdating):

GlobalUpdating(offlineupdating):

这里的可以是，，0。仅对最短路径的信息素增加量。

局部更新用于每一时刻每一蚂蚁的每一步移动之中，而全局更新是所有的蚂蚁都完成一个周期的搜索之后最好的搜索结果进行信息素轨迹更新。

MMAS(Max-MinAntSystem)模型

为避免停滞和陷入局部，Stutzle和Hoos提出了MAX-MINAntSystem（简称MMAS）模型，它对AS进行了三点改进:

(1)为了更加充分地寻优，各路径信息素初值设为最大值；

(2)一圈中只有最短路径的蚂蚁才进行信息素修改增加，这与AS蚂蚁圈模型调整方法相似；

(3)为了避免算法过早收敛非全局最优解，将各路经的信息素浓度限制在于之间，即。超出这个范围的值被强制设为或者。

从实验结果看，MMAS算法在防止算法过早停滞及有效性方面对AS算法有较大的改进。几种模型的评价

随着蚂蚁算法发展，蚂蚁算法的模型越来越丰富，人们针对不同的问题设计不同的参数，如求解TSP问题时,

表示两个城市之间的距离；在求解QAP问题时，

表示流程与距离的关系；在求解SMTT时，

是可以得到的启发数据。如等参数的选择也要根据不同问题做出不同选择。同时，基于问题进行轨迹更新方程的修改及概率选择的定义也是必要的。

在蚂蚁算法的几种模型中，AS、ACS、MMAS三种具有重要的作用。AS(AntSystem)模型的优点

AS(AntSystem)是最早的伴随蚁群这个概念提出来的算法，它首先被成功地运用于TSP问题。虽然与目前已经发展完备的一些算法(如GA等)比较起来，基本蚁群算法计算量比较大，而且效果也并不一定更好，但是它的成功运用激起了人们对蚁群算法的极大兴趣，并吸引了一批研究人员从事蚁群算法的研究。AS的优点在于:

（1）正反馈，从而能迅速找到好的解决方法；

（2）分布式计算可以避免过早地收敛；

（3）强启发能在早期的寻优中迅速找到合适的解决方案。

（4）AS算法被成功地运用于许多能被表达为在图表上寻找最佳路径

的问题。ACS与AS的主要区别

（1）ACS算法中，蚂蚁在寻找最佳路径的过程中使用局部信息，即采用局部信息对信息素浓度进行调整；（2）在所有进行寻优的蚂蚁结束路径寻找后，信息素的浓度会再一次调整，这次采用的是全局信息，而且只对过程中发现的最好路径上的信息素浓度进行加强；（3）有一个状态传递机制，用于指导蚂蚁最初的寻优过程，并通过信息素的积累反映问题的目前状态。MMAS模型特点

MMAS(MAX-MINAntSystem)是到目前为止解决TSP，QAP等问题最好的ACO类算法。和其他寻优算法比较起来，它仍然属于最好的解决方案之一。其特点在于:（1）只对最佳路径增加信息素的浓度，从而更好地利用了历史信息(这与

ACS算法的调整方案有点类似)；（2）为了避免算法过早收敛于并非全局最优的解，将各条路径可能的信息素浓度限制于，超出这个范围的值被强制设为或者是

，可以有效地避免某条路径上的信息量远大于其余路径，使得所有的蚂蚁都集中到同一条路径上，从而使算法不再扩散；（3）将各条路径上信息素的起始浓度设为，这样便可以更加充分地进行寻优。研究问题研究者算法命名时间旅行商问题（TSP）Dorigo,Maniezzo,ColorniGambardellaandDorigoStizleandHoosBullnheimerandHartl马良吴斌、史忠植Randall丁建立、陈增强、袁著祉ASAnt-Q,ACSandACS-3-optMMASASrank扩展TSP蚂蚁算法分段蚂蚁算法PACS遗传算法与蚂蚁算法融合GAAA19911995,1996199619971999200120022003分配问题（QAP）Maniezzo,Colorni,DorigoGambardella,Taillard,DorigoStizleandHoosManiezzo,CarbonaroRamalhinho,Lourenco,SerraTalbi,Roux,Fonlupt,RobillardAS-QAP,ANTS-QAP,AS-QAPcHAS-QAPbMMAS-QAPANTS-FAPMMAS-GAPPAC1994,1998,199919971997199819982001调度问题

(SP)Colorni,Dorigo,ManiezzoStizleBaueretalDenBesten,Dorigo,Maniezzo陈义宝、周济等AS-JSPAS-FSPACS-SMTTPACS-SMTWTP工件排序蚁群算法19941997199919992002

表2蚁群算法及其应用

表2蚁群算法及其应用（续）

路由问题（RP）Bullnheimer,Hartl,StraussGambardella,Taillard,AgazziSchoonderwoerd,Bonabeau,vanderputetalWhite,Pagurek,OppacherDiCaro,DorigoSubramanian,Druschel,ChenHeusseetalNavarroVarela,Sinclair李生红，刘泽民，周正张素兵，刘泽民丁建立、陈增强、袁著祉AS-VRPHAS-VRPABC,ABC-smart,ABC-backwardASGAAntNet-FA,AntNet-FSRegularantsCAFACO-VWPVC路由选择分布式多播路由动态路由选择199719991996