1、第五部分第五部分蚁群优化算法蚁群优化算法Ant Colony Optimization参考文献参考文献nM.Dorigo and T.Stutzle,Ant Colony OptimizationM:MIT Press,2004n段海滨，蚁群算法原理极其应用蚁群算法原理极其应用M，2007.科学出版社0 蚁群优化算法的历史沿革蚁群优化算法的历史沿革n意大利学者Marco Dorigo（Alberto Colorni）于1991年在其博士论文中提出。n和Vittorio Maniezzo一同设计了第一个ACO算法蚂蚁系统（Ant System）。n在真实蚂蚁觅食行为的启发下提出的一种高度创新性的
2、启发式算法。Marco DorigoMacro Dorigo重要文献重要文献nColorni等，1994，“Ant System for Job-shop Scheduling”nColorni等，1996，“Heuristics From Natrure for Hard Combinatorial Optimization Problems”nDorigo M等，1996，“Ant system:optimization by a colony of cooperating agents”Ant system:optimization by a colony of cooperating
3、agentsn更加系统地阐述了蚁群算法的基本原理和数学模型；n与遗传算法、禁忌搜索算法、模拟退火算法、爬山法等进行了仿真实验比较；n把单纯地解决对称TSP拓展到解决非对称TSP、QAP和JSP；n对蚁群算法中的初始化参数对性能的影响做了初步探讨；n蚁群算法发展史上的一篇奠基性文章奠基性文章。近期发展近期发展n2000年，Dorigo M和Bonabeau E等在Nature上发表蚁群算法的研究综述，把这一领域的研究推向了国际学术的最前沿；n进入21世纪的最近几年里，Nature曾多次对蚁群算法的研究成果进行报告。相关书籍相关书籍n2004年9月，Marco Dorigo and Thomas
4、SttzleAnt Colony Optimization；n系统介绍蚁群算法，为蚁群算法的传播和科普做出了很重要一步；n2007年翻译成中文出版。理论建设理论建设n在理论建设方面，ACO取得的成果比较少，也是最薄弱的一方面。n1999年Gutjahr W J的技术报告和2000年的论文中首次对蚁群算法的收敛性进行了证明。n将蚁群算法的行为简化为在一幅代表所求问题的有向图上的随机行走过程，进而从有向图论的角度对一种改进蚁群算法图搜索蚂蚁系统（Graph-Based Ant System，GBAS）的收敛性进行了理论分析。n采用的数学工具是Markov链，证明了在一些合理的假设条件下他所提出的G
5、BAS能以一定概率收敛到所求问题的最优解。蚁群优化算法的发展蚁群优化算法的发展n精华蚂蚁系统（Elitist Strategy for Ant System，EAS）n对解构造过程中表现优异的人工蚂蚁给予特殊的信息素释放奖励；nAnt-Q算法n将蚁群算法与Q学习算法结合，利用多个人工蚂蚁的协同效应；n后期n蚁群系统（Ant Colony System，ACS），n基于排序的蚂蚁系统（Rank Based version AS，ASrank），n最大最小蚂蚁系统（Max-Min Ant System，MMAS）蚁群优化算法的应用蚁群优化算法的应用n路由类问题路由类问题n旅行商、车辆路由、顺序排列
6、等n分配类问题分配类问题n二次分配、图着色、广义分配、频率分配、大学生课程时间表等n调度类问题调度类问题n工序车间、开放车间、工作流车间、总延迟、总权重延迟、项 目调度、组车间等 蚁群优化算法的应用蚁群优化算法的应用n子集类问题子集类问题n多重背包、最大独立集、冗余分配、集合覆盖、带权约束图树分割、边带权l-基树、最大图等n机器学习类问题机器学习类问题n分配规则、贝叶斯网络、模糊系统等n网络路由类问题网络路由类问题n面向连接的网络路由、无连接的网络路由、光学网络路由等 1 蚁群优化算法的生物学基础蚁群优化算法的生物学基础n阿根廷蚂蚁n双桥实验实验结果（实验结果（1）摘自Ant Colony O
7、ptimization实验结果（实验结果（2）摘自Ant Colony Optimization实验结果（实验结果（3）摘自Ant Colony Optimization障碍实验障碍实验摘自Ant System:Optimization by A Colony of Cooperating Agents生物蚂蚁的特点生物蚂蚁的特点n没有视觉n计算与记忆能力有限n依赖信息素(pheromone)通信、协作n释放n挥发n正反馈2 人工蚁群系统人工蚁群系统n人工蚂蚁与生物蚂蚁的区别人工蚂蚁与生物蚂蚁的区别n人工蚂蚁具有一定的记忆能力n人工蚂蚁具有一定的视力（启发）n人工蚂蚁生活在离散的时间环境中人工
8、蚁群模型人工蚁群模型摘自Ant System:Optimization by A Colony of Cooperating Agents人工蚁群人工蚁群na)初始状态；nb)t=0，无信息素，人工蚂蚁以等概率等概率选择左 转或右转；nc)t=1，较短的路径上信息素浓度较高，人工 蚂蚁以较高的概率较高的概率选择信息素浓度高的路径实例：实例：TSPnGraph(N,E)nEuclidean距离n蚂蚁数量)(tbmNii122)()(jijiijyyxxd实例：实例：TSPn人工蚂蚁的行为人工蚂蚁的行为n路径选择的概率是城市距离城市距离和路径上信息素信息素浓度浓度的函数；n符合TSP规则；n完成一
9、次旅行后，在经过的路径上释放信息素；n无需按原路返回。实例：实例：TSP（参数与机制）（参数与机制）n路径上的信息素浓度n信息素更新n信息素释放(ant-cycle)ijijijtnt)()()(tijotherwisen)t and t ime(between t tour itsin j)(i,edge usesant th-k if0kkijLQmkkijij1实例：实例：TSP（参数与机制）（参数与机制）n路径选择概率ijijd1 otherwisej if)()()(k0allowedtttpkallowedlililijijkijTSP蚁群算法蚁群算法(ant-cycle)nSte
10、p 1 Initialize:Set t:=0 t is the time counterSet NC:=0 NC is the cycles counterFor every edge(i,j)set an initial value for trailintensity andPlace the m ants on the n nodesctij)(0ijTSP蚁群算法（蚁群算法（ant-cycle）nStep 2 Set s:=1 s is the tabu list index For k:=1 to m do Place the starting town of the k-th a
11、nt in tabuk(s)TSP蚁群算法（蚁群算法（ant-cycle）nStep 3 Repeat until tabu list is full this step will be repeated(n-1)timesSet s:=s+1For k:=1 to m do Choose the town j to move to,with probability at time t the k-th ant is on town i=tabuk(s-1)Move the k-th ant to the town j Insert town j in tabuk(s)(tpkijTSP蚁群算
12、法（蚁群算法（ant-cycle）nStep 4.1 For k:=1 to m doMove the k-th ant from tabuk(n)to tabuk(1)Compute the length Lk of the tour described by the k-th antUpdate the shortest tour foundTSP蚁群算法（蚁群算法（ant-cycle）nStep 4.2For every edge(i,j)For k:=1 to m do mkkijij1otherwiseby tabu describedtour j)(i,ifk0kkijLQTSP蚁
13、群算法（蚁群算法（ant-cycle）nStep 5 For every edge(i,j)compute according to equation Set t:=t+nSet NC:=NC+1For every edge(i,j)set)(ntijijijijtnt)()(0:ijTSP蚁群算法（蚁群算法（ant-cycle）nStep 6 If(NC NCMAX)and(not stagnation behavior)thenEmpty all tabu listsGoto step 2elsePrint shortest tourStop3 蚁群算法调整与参数设置蚁群算法调整与参数设置
14、n ：信息素的相对重要性；n ：启发性因素的相对重要性；n ：信息素残留因子；nQ：常数，控制信息素的释放常数，控制信息素的释放；nm：蚁群规模；n其他：n蚁群的初始分布信息素释放算法信息素释放算法ant-cyclenant-cycleotherwisen)t and t ime(between t tour itsin j)(i,edge usesant th-k if0kkijLQ信息素释放算法信息素释放算法ant-densitynant-densityotherwise1 t and t mebetween ti j toi from goesant th-k theifQ0kij信息素
15、释放算法信息素释放算法ant-quantitynant-quantityotherwise1 t and t mebetween ti j toi from goesant th-k theif0ijkijdQ信息素释放算法对比信息素释放算法对比n测试集：Oliver30 problemn循环次数：NCMAX=5000n测试次数：10摘自Ant Colony OptimizationGA：424.635实验数据实验数据1 ant-cycle摘自Ant Colony Optimization实验数据实验数据2 ant-cycle摘自Ant Colony Optimization实验数据实验数据3
16、 ant-cycle摘自Ant Colony Optimization参数：参数：nant-cyclenNCMAX=5000n,50.摘自Ant Colony Optimization蚁群规模：蚁群规模：mnant-cyclen4x4 grid摘自Ant Colony Optimization蚁群初始分布蚁群初始分布n均匀均匀分布优于分布优于集中集中（单一城市）分布（单一城市）分布n随机随机分布略好于均匀分布分布略好于均匀分布算法复杂度算法复杂度nO(NC n2m)nstep 1:O(n2+m),nstep 2:O(m),nstep 3:O(n2 m),nstep 4:O(n2 m),nste
17、p 5:O(n2),nstep 6:O(n m).实验数据（算法复杂度）实验数据（算法复杂度）摘自Ant Colony Optimization4 实例：实例：JSPnJob-shop Scheduling ProblemnM:机器数量nJ:任务数nojm:工序ndjm:工时n :工序集合,jmoO JSP(Muth&Thompson 6x6)m.tm.tm.tm.tm.tm.tJob13.11.32.64.76.35.6Job22.83.55.106.101.104.4Job33.54.46.81.92.15.7Job42.51.53.54.35.86.9Job53.92.35.56.41.
18、34.1Job62.34.36.91.105.43.1JSPn3x2 problemJSPn路径选择 otherwisej if)()()(k0allowedtttpkallowedlililijijkijijijT1JSPn待访问节点集合：n下一步允许访问节点集合：n算法结束：654321,kG321,kSkG5 实例：实例：PID参数整定参数整定n整定参数n目标函数idpTTK,dttetJ0)(PID参数整定参数整定nKp=12.345nTd=6.7890nTi=9.8765n(123456789098765)x(1234567890)PID参数整定参数整定n信息素释放信息素释放othe
19、rwise),(node passesant th-k theif),(0iikiikyxJQyxPID参数整定参数整定n路径选择概率路径选择概率1010jjjiyytyx,otherwisej if),(),(),(),(),(k090allowedtyxtyxtyxtyxtyxplillijijijik6 蚁群优化算法研究现状蚁群优化算法研究现状n蚁群系统（Ant Colony System，ACS）n基于排序的蚂蚁系统（Rank Based version AS，ASrank）n最大最小蚂蚁系统（Max-Min Ant System，MMAS）蚁群系统蚁群系统ACSn结合结合Q-lear
20、ning；nACS采用了更为大胆的行为选择规则；采用了更为大胆的行为选择规则；n只增强属于只增强属于全局最优解的路径全局最优解的路径上的信息素；上的信息素；gbgbijgbijijijLtttnt11)()()()()(到当前为止全局最优的路径长度蚁群系统蚁群系统ACSn引入负反馈机制引入负反馈机制。每当蚂蚁由一个节点移动到。每当蚂蚁由一个节点移动到另一个节点时，该路径上的信息素按照如下公另一个节点时，该路径上的信息素按照如下公式被相应的消除一部分，从而实现一种信息素式被相应的消除一部分，从而实现一种信息素的局部调整，以减小已选择过的路径再次被选的局部调整，以减小已选择过的路径再次被选择的概率
21、。择的概率。01ijij)(最大最小蚂蚁系统最大最小蚂蚁系统MMASn修改了修改了AS的信息素更新方式；的信息素更新方式；n每次迭代之后只有一只蚂蚁每次迭代之后只有一只蚂蚁能够进行信息素的能够进行信息素的更新，以获取更好的解；更新，以获取更好的解；n为了避免搜索停滞，路径上的信息素浓度被限为了避免搜索停滞，路径上的信息素浓度被限制在制在MAX，MIN 范围内；范围内；n信息素的初始值被设为其取值上限，有助于增信息素的初始值被设为其取值上限，有助于增加算法初始阶段的搜索能力。加算法初始阶段的搜索能力。基于排序的蚂蚁系统基于排序的蚂蚁系统ASrankn与与“精英策略精英策略”相似；相似；n算法中总是更新更好进程上的信息素；算法中总是更新更好进程上的信息素；n选择的标准是其行程长度决定的排序；选择的标准是其行程长度决定的排序；)()()()(tLtLtLtLm321基于排序的蚂蚁系统基于排序的蚂蚁系统ASrankn每个蚂蚁释放信息素的强度每个蚂蚁释放信息素的强度通过排序加权处理通过排序加权处理确定。其中，为每次迭代后释放信息素的蚂确定。其中，为每次迭代后释放信息素的蚂蚁总数。蚁总数。gbgbijrrijgbijwrrijijijLtLttwtrwtt11111)()()()()()()()(
