蚂蚁算法2010

1、 丁建立丁建立中国民航大学计算机学院中国民航大学计算机学院l蚂蚁算法的原理、特点l蚂蚁算法的模型l蚂蚁算法的研究进展l蚂蚁算法求解TSP问题l用于优化领域的人工蚂蚁算法，其基本原理吸收了生物界中蚂蚁群体行为的某些显著特征:l（1） 察觉小范围区域内状况并判断出是否有食物 l 或其他同类的信息素轨迹；l（2） 释放自己的信息素；l（3） 所遗留的信息素数量会随时间而逐步减少。 图图2-1 蚂蚁从蚁穴（蚂蚁从蚁穴（Nest）移至食物源）移至食物源(Food)图图2-2 在巢穴与食物源之间出现障碍物时蚂蚁收敛到最短路径的过程在巢穴与食物源之间出现障碍物时蚂蚁收敛到最短路径的过程l蚂蚁在寻找食物源时，

2、能在其走过的路上释放一种特殊的分泌物蚂蚁在寻找食物源时，能在其走过的路上释放一种特殊的分泌物信信息素息素 (随着时间的推移该物质会逐渐挥发随着时间的推移该物质会逐渐挥发), 后来的蚂蚁选择该路径的概后来的蚂蚁选择该路径的概率与当时这条路径上该物质的强度成正比率与当时这条路径上该物质的强度成正比.l当一定路径上通过的蚂蚁越来越多时，其留下的信息素轨迹也越来越多，当一定路径上通过的蚂蚁越来越多时，其留下的信息素轨迹也越来越多，后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强度。后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强度。l而强度大的信息素会吸引更多的蚂蚁，从而形成一

3、种正反馈机制而强度大的信息素会吸引更多的蚂蚁，从而形成一种正反馈机制, 通过通过这种正反馈机制，蚂蚁最终可以发现最短路径。这种正反馈机制，蚂蚁最终可以发现最短路径。l 特别地，当蚂蚁巢穴与食物源之间出现障碍物时，蚂蚁不仅可以绕过障特别地，当蚂蚁巢穴与食物源之间出现障碍物时，蚂蚁不仅可以绕过障碍物，而且通过蚁群信息素轨迹在不同路径上的变化，经过一段时间的碍物，而且通过蚁群信息素轨迹在不同路径上的变化，经过一段时间的正反馈，最终收敛到最短路径上。正反馈，最终收敛到最短路径上。（1）其原理是一种正反馈机制或称增强型学习系统；）其原理是一种正反馈机制或称增强型学习系统；它通过信息素的不断更新达到最终收

4、敛于最优路径上；（2）它是一种通用型随机优化方法；）它是一种通用型随机优化方法；但人工蚂蚁决不是对实际蚂蚁的一种简单模拟，它融进了人类的智能；（3）它是一种分布式的优化方法；）它是一种分布式的优化方法；不仅适合目前的串行计算机，而且适合未来的并行计算机；（4）它是一种全局优化的方法；）它是一种全局优化的方法；不仅可用于求解单目标优化问题，而且可用于求解多目标优化问题；（5）它是一种启发式算法；）它是一种启发式算法；计算复杂性为 ，其中NC 是迭代次数，m 是蚂蚁数目，n 是目的节点数目。)(2nmNCO蚂蚁算法（蚂蚁算法（Ant Algorithm, AA）或统称蚁群优化（）或统称蚁群优化（A

5、nt Colony Optimization, ACO）一些符号的含义：）一些符号的含义： m 蚂蚁个数蚂蚁个数; n 结点（顶点）个数结点（顶点）个数; 边弧边弧 的能见度（的能见度（visibility）, 或称局部启发因子，或称局部启发因子，一般取一般取 ， 表示路径表示路径 之间的长度之间的长度; 边弧边弧 的信息素轨迹强度（的信息素轨迹强度（intensity）; 蚂蚁蚂蚁k 于弧上于弧上 留下的单位长度轨迹信息素数量留下的单位长度轨迹信息素数量; 蚂蚁蚂蚁k 在结点的转移概率，在结点的转移概率，j 是尚未访问结点是尚未访问结点; 信息素轨迹的相对重要性（信息素轨迹的相对重要性（ ）

6、; 边弧能见度的相对重要性（边弧能见度的相对重要性（ ）;ij),(jiijd1ijd),(jiij),(jikij),(jikijp00 信息素轨迹的持久性（信息素轨迹的持久性（ ），）， 可理解为可理解为轨迹衰减度（轨迹衰减度（evaporation）；）； 体现蚂蚁所留轨迹数量的一个常数；体现蚂蚁所留轨迹数量的一个常数； 可行结点集合；可行结点集合； 为第为第k 只蚂蚁在第结点只蚂蚁在第结点i 出发下一步的可行结点集；出发下一步的可行结点集； 一个列表，用于记录第一个列表，用于记录第k只蚂蚁到目前为止已经只蚂蚁到目前为止已经访问的城市。访问的城市。 101QUkiN)(ktabul第第1

7、步：步：初始化，NC=0, 将m只蚂蚁置于n个顶点上；l第第2步：步：将各蚂蚁的初始出发点置于当前解集中；对每一个蚂蚁k，按概率P选择移至下一顶点j上；将顶点j置于当前解集；l第第3步：步：计算各蚂蚁的目标函数值；记录当前的最好解；l第第4步：步：按更新方程修改信息素轨迹强度；l第第5步：步：对各边弧 , ，NC=NC+1；l第第6步：步：若搜索次数NC预定迭代次数且无退化行为（即找到的都是相同解），则转第二步；l第第7步：步：输出目前的最好解。),(ji0ijl蚂蚁系统（AS）是第一个蚁群优化算法（ACO），它是意大利科学家Dorigo 在1991年最先提出，并成功地用于求解著名的组合爆炸问

8、题TSP问题，后经他本人（1992,1996,2000）及学者Colorni，Maniezzo(1997,1999)等进一步研究，将其系统化。其主要参数变量表达如下：l选择概率： l信息素更新方程为：otherUjtttpUlililijijkij0)()()(mkkijijijttt1)()() 1(l按 的不同取法,可形成三种类型的蚂蚁算法模型:l(1) 蚂蚁密度模型（Ant Density）： l(2) 蚂蚁数量模型（Ant Quantity）： l(3) 蚂蚁圈模型（Ant Cycle）：l其中: 可行结点集合，具体应用中经常用 表示， 为第k只蚂蚁在第i 结点出发下一步的可行结点集（

9、TSP问题应去掉第k只蚂蚁已经过的结点）， 为第k只蚂蚁在本次循环中所走的路径的长度。l上述三种模型中，蚂蚁密度模型和蚂蚁数量模型利用的是局部信息，而蚂蚁圈模型利用的是全局信息，对全局优化较好。 kijkkijLQijkijdQQkijUkiNkiNkLlDorigo与与Gambardella等学者在1997年在Ant-Q算法的基础上进行修改，为了平衡寻找更好结果和寻找更大的搜索空间，Pseudo-Random-Proportional rule下状态转移如下：lV按照下面概率选择 l这里是将Ant-Q模型中， 更重要地是给出了局部在线和全局离线的两种信息素轨迹更新方式：00)()(argma

10、xqqVqqvililNlkikiNlililijijkijp)()()()(1lLocal Updating(online updating): lGlobal Updating(offline updating):l 这里的 可以是 ， ，0 。 仅对最短路径的信息素增加量。l局部更新用于每一时刻每一蚂蚁的每一步移动之中，而全局更新是所有的蚂蚁都完成一个周期的搜索之后最好的搜索结果进行信息素轨迹更新。 ijijijtt)1 ()() 1(eijijijtt)1 ()() 1(jmaxeij0ijl为避免停滞和陷入局部，Stutzle和Hoos 提出了MAX-MIN Ant System（简

11、称MMAS）模型，它对AS进行了三点改进:l(1)为了更加充分地寻优，各路径信息素初值设为最大值 ；l(2)一圈中只有最短路径的蚂蚁才进行信息素修改增加，这与AS蚂蚁圈模型调整方法相似；l(3)为了避免算法过早收敛非全局最优解，将各路经的信息素浓度限制在于 之间，即 。超出这个范围的值被强制设为 或者 。l从实验结果看，MMAS算法在防止算法过早停滞及有效性方面对AS算法有较大的改进。maxeijijijtt)() 1(,maxminmaxminijmaxminl随着蚂蚁算法发展，蚂蚁算法的模型越来越丰富，人们针对不同的问题设计不同的参数，如求解TSP问题时, , 表示两个城市之间的距离；在求

12、解QAP问题时， 表示流程与距离的关系；在求解SMTT时， 是可以得到的启发数据。如 等参数的选择也要根据不同问题做出不同选择。同时，基于问题进行轨迹更新方程的修改及概率选择的定义也是必要的。l在蚂蚁算法的几种模型中，在蚂蚁算法的几种模型中，AS, ACS, MMAS三种具有重要三种具有重要的作用的作用。ijijd1ijdijijs1jiijdfsijijMDD1ijMDD,QlAS (Ant System) 是最早的伴随蚁群这个概念提出来的算法，它首先被成功地运用于TSP问题。虽然与目前已经发展完备的一些算法(如GA等)比较起来，基本蚁群算法计算量比较大，而且效果也并不一定更好，但是它的成功

13、运用激起了人们对蚁群算法的极大兴趣，并吸引了一批研究人员从事蚁群算法的研究。AS的优点在于:l（1）正反馈，从而能迅速找到好的解决方法；l（2）分布式计算可以避免过早地收敛；l（3）强启发能在早期的寻优中迅速找到合适的解决方案。l（4）AS算法被成功地运用于许多能被表达为在图表上寻找最佳路径的问题。 l（1）ACS算法中，蚂蚁在寻找最佳路径的过程中使用局部信息，即采用局部信息对信息素浓度进行调整；l（2）在所有进行寻优的蚂蚁结束路径寻找后，信息素的浓度会再一次调整，这次采用的是全局信息，而且只对过程中发现的最好路径上的信息素浓度进行加强；l（3）有一个状态传递机制，用于指导蚂蚁最初的寻优过程，

14、并通过信息素的积累反映问题的目前状态。lMMAS(MAX-MIN Ant System)是到目前为止解决是到目前为止解决TSP，QAP等问题最好的等问题最好的ACO类算法。和其他寻优算法比较起来，类算法。和其他寻优算法比较起来，它仍然属于最好的解决方案之一。它仍然属于最好的解决方案之一。其特点在于:l（1）只对最佳路径增加信息素的浓度，从而更好地利用了历史信息(这与ACS算法的调整方案有点类似)；l（2）为了避免算法过早收敛于并非全局最优的解，将各条路径可能的信息素浓度限制于 ，超出这个范围的值被强制设为 或者是 ，可以有效地避免某条路径上的信息量远大于其余路径，使得所有的蚂蚁都集中到同一条路

15、径上，从而使算法不再扩散；l（3）将各条路径上信息素的起始浓度设为 ，这样便可以更加充分地进行寻优。,maxminmaxmaxmin 表表2 蚂蚁算法及其应用蚂蚁算法及其应用 研究问题研究者算法命名时间旅行商问题（TSP）Dorigo,Maniezzo,ColorniGambardella and DorigoStizle and HoosBullnheimer and Hartl马良吴斌、史忠植Randall丁建立、陈增强、袁著祉ASAnt-Q,ACS and ACS-3-optMMASASrank扩展TSP蚂蚁算法分段蚂蚁算法PACS遗传算法与蚂蚁算法融合GAAA19911995,1996

16、199619971999200120022003分配问题（QAP）Maniezzo, Colorni, DorigoGambardella ,Taillard,DorigoStizle and HoosManiezzo,CarbonaroRamalhinho,Lourenco,SerraTalbi,Roux,Fonlupt,RobillardAS-QAP,ANTS-QAP,AS-QAPcHAS-QAPbMMAS-QAPANTS-FAPMMAS-GAPPAC1994,1998,199919971997199819982001调度问题(SP)Colorni, Dorigo,ManiezzoStiz

17、le Bauer et alDenBesten, Dorigo, Maniezzo陈义宝、周济等AS-JSPAS-FSPACS-SMTTPACS-SMTWTP工件排序蚁群算法19941997199919992002 表表2 蚂蚁算法及其应用（续）蚂蚁算法及其应用（续） 路由问题（RP）Bullnheimer,Hartl,StraussGambardella ,Taillard,AgazziSchoonderwoerd,Bonabeau ,van der put et alWhite,Pagurek,OppacherDi Caro,DorigoSubramanian,Druschel,ChenH

18、eusse et al Navarro Varela,Sinclair李生红，刘泽民，周正张素兵，刘泽民丁建立、陈增强、袁著祉AS-VRPHAS-VRPABC,ABC-smart,ABC-backwardASGAAntNet-FA, AntNet-FSRegular antsCAFACO-VWPVC路由选择分布式多播路由动态路由选择199719991996199819981997,1998199719981999200020012003其他问题Gambardella ,DorigoCosta and HertzMichel,MiddendorfLeguizamon,MichalewiczLia

19、ng,Smith马良，蒋馥马良，王龙德丁建立、陈增强、袁著祉HAS-SOPANTCOLAS-SCSAS-MKPACO-RAP度限制最小树（DCMST）背包问题蚂蚁算法蚂蚁算法收敛性分析19971997199819991999199920012004蚂蚁算法的研究与发展历史毕竟较短，还存在诸多问题：（1）它的发展远没有形成完整的理论体系；（2）模型对问题具有依赖性，研究者必须根据问题的特点选择和修正模型；（3）算法的参数选择更多的是依靠实验和经验，没有定理或公认的确定方法；（4）由于初始信息素匮乏，计算时间偏长，对实时应用不利。这些都表明其理论和实践方面有许多问题尚需更深入的研究。l遗传算法具有

20、快速随机的全局搜索能力，但不能很好地利用系统的反馈信息,当求解到一定范围时往往作大量无为的冗余迭代，求精确解效率低。l蚂蚁系统是一种并行的分布式正反馈系统，它是通过信息素的累积和更新收敛于最优路径上，但初期信息素匮乏，初始求解速度慢。l遗传算法与蚂蚁算法的融合模型，采用遗传算法生成初始信息素分布，利用蚂蚁算法反复迭代求精确解，以期达到优势互补。 图3-1 简单遗传算法进化过程示例种群# 位串 适应值 排序1011011011 38.3 31100011100 43.7 20111010101 54.5 110110010010 34.6 4交叉位11000111000111010101变异位1

21、1000101010111011100新后代11000101010111001100选择交叉变异新后代遗传算法具有进化计算的所有特征，其优点是：l（1）具有大范围全局搜索的能力，与问题领域无关；l（2）搜索从群体出发，具有潜在的并行性；l（3）可进行多值比较，鲁棒性强；l（4）搜索使用评价函数启发，过程简单；l（5）使用概率机制进行迭代，具有随机性；l（6）具有可扩展性，容易与其它算法结合。 但遗传算法在编码表示、适应度函数、选择策略、控制参数等方面还存在诸多问题。特别是，对于系统中的反馈信息利用不够，当求解到一定范围时往往作大量无为的冗余迭代，求精确解效率低。 遗传算法与蚂蚁算法的融合（Ge

22、netic AlgorithmAnt Algorithm 简称GAAA）,其基本思想是汲取两种算法的优点，克服各自的缺陷，优势互补。在时间效率上优于蚂蚁算法，在求精解效率上优于遗传算法，是时间效率和求解效率都比较好的一种新的启发式方法。其基本思路是算法前过程采用遗传算法，充分利用遗传算法的快速性、随机性、全局收敛性，其结果是产生有关问题的初始信息素分布。算法后过程采用蚂蚁算法，在有一定初始信息素分布的情况下，充分利用蚂蚁算法并行性、正反馈性、求精解效率高等特点。 图3-2 GAAA算法总体框架 定义目标函数定义目标函数 生成若干组优化解生成若干组优化解 定义适应值函数定义适应值函数 转化为初始

23、信息素分布转化为初始信息素分布问题问题 遗传遗传 算法算法 蚂蚁蚂蚁 算法算法最好最好解解图3-3 GAAA算法详细流图lGAAA中的遗传算法中的遗传算法是基于优胜选择遗传算法的原理与定义。l编码与适应值函数：编码与适应值函数：如TSP问题，以城市的遍历次序作为遗传算法的编码，适应度函数取为哈密顿圈的长度的倒数。l种群生成与染色体选择：种群生成与染色体选择：利用随机函数生成一定数量的十进制实数编码种群，根据适应值函数选择准备进行交配的一对染色体父串。l交叉算子：交叉算子：采用Davis提出的顺序交叉方法。l变异算子变异算子：采用逆转变异方法。 l交叉算子：交叉算子：采用Davis提出的顺序交叉

24、方法，先进行常规的双点交叉，在进行维持原有相对访问顺序的巡回路线修改。具体交叉如下：l（1）随机在父串上选择一个交配区域，如两父串选定为：lold1= 1 2 | 3 4 5 6 | 7 8 9, old2= 9 8 | 7 6 5 4 | 3 2 1l（2）将old2的交配区域加到old1前面，将old1的交配区域加到old2的前面：l old1= 7 6 5 4 | 1 2 3 4 5 6 7 8 9, old2= 3 4 5 6 | 9 8 7 6 5 4 3 2 1l（3）依次删除old1，old2中与交配区相同的数码，得到最终的两子串：l new1= 7 6 5 4 1 2 3 8

25、9, new2= 3 4 5 6 9 8 7 2 1l l变异算子变异算子：采用逆转变异方法，所谓“逆转”，如染色体 (123456) 在区间23和区间56处发生断裂，断裂片段又以反向顺序插入，于是逆转后的染色体变为(125436)。这里的“进化”，是指逆转算子的单方向性，只有经逆转后，适应值有提高的才接受下来，否则逆转无效。lGAAA中蚂蚁算法选择基于蚂蚁圈模型（Ant-Cycle）和MMAS(MAX-MIN Ant System)算法，在吸取其各自优点的基础上并进行改进，具体来说：l信息素更新方程：l选择概率： l每一蚂蚁圈信息素增加：l各路径设置信息素初值。 )()() 1(tttkij

26、ijijotherNjtttpkiNlililijijkijki0)()()(kkijLQl两种算法对接的关键是如何把遗传算法的结果转化为蚂蚁算法的信息素。l信息素的初值设置：信息素的初值设置：MMAS是把各路径信息素初值设为最大值max，这里我们通过遗传算法得到了一定的路径信息素，所以把信息素的初值设置为: S = C+G 这里，C是一个根据具体求解问题规模给定的一个信息素常数，相当于MMAS算法中的min，G是遗传算法求解结果转换的信息素值。l信息素更新模型：信息素更新模型：采用蚂蚁圈模型进行信息素更新，即一圈中只有最短路径的蚂蚁才进行信息素修改增加。l我们采用GAAA算法分别对典型的NP

27、-hard问题30城市TSP问题和中国CHN144城市问题进行了实验, GAAA中遗传算法迭代次数分别选定为30代和144代，蚂蚁算法中各路径信息素初值C分别设为60和600, 遗传算法求解结果转换的信息素值是经过路径加2和20,轨迹更新分别取=0.8，Q=1000和=0.9，Q=100000。表3-1、表3-2、表3-3、表3-4、图3-4、图3-5、图3-6、图3-7、图3-8、图3-9、图3-10、图3-11、图3-12、图3-13是仿真实验结果。 表表3-1 GAAA算法优化解数据逼近过程算法优化解数据逼近过程 GAAA过程TSP30优化解值CHN144优化解值 最大值 最小值 平均值

28、最大值 最小值 平均值初始随机生成优化解值 1500 1209 1318.888763 65739 76316选择算子作用优化解值1198 1101 1139.165564 61278 63211杂交算子作用优化解值 1095 1005 1050.356405 54329 55323变异算子作用优化解值987 817 912.351994 51344 51508蚂蚁算法作用优化解值452 424 433.731153 30351 30612 表表3-2 GAAA算法随机求解的算法随机求解的30个个 优化解值分布优化解值分布)1000, 8 . 0, 2, 1(Q)100000, 9 . 0,

29、2, 2(QTSP30优化解值分布CHN144优化解值分布436 430 431 439 426 437 433 429 434 439 426 438 424 426 425 446 449 426 424 443 434 427 452 436 426 425 448 431 440 43030351 30585 30643 30730 30807 30928 31153 30810 30748 30617 30507 30358 30379 30357 30595 30551 30676 30760 30736 30788 30563 30354 30360 30431 30566 30739 30792 30743 30380 30356图3-4 GAAA算法一次随机遗传变异后产生的信息素分布(TSP30)图3