辽宁大学智能控制课件《蚁群优化算法》

第五部分蚁群优化算法

AntColonyOptimization1可编辑ppt参考文献M.DorigoandT.Stutzle,AntColonyOptimization[M]:MITPress,2004段海滨，蚁群算法原理极其应用[M]，2007.科学出版社2可编辑ppt0蚁群优化算法的历史沿革意大利学者MarcoDorigo（AlbertoColorni）于1991年在其博士论文中提出。和VittorioManiezzo一同设计了第一个ACO算法—蚂蚁系统（AntSystem）。在真实蚂蚁觅食行为的启发下提出的一种高度创新性的启发式算法。3可编辑pptMarcoDorigoMacroDorigo4可编辑ppt重要文献Colorni等，1994，“AntSystemforJob-shopScheduling”Colorni等，1996，“HeuristicsFromNatrureforHardCombinatorialOptimizationProblems”DorigoM等，1996，“Antsystem:optimizationbyacolonyofcooperatingagents”5可编辑pptAntsystem:optimization

byacolonyofcooperatingagents更加系统地阐述了蚁群算法的基本原理和数学模型；与遗传算法、禁忌搜索算法、模拟退火算法、爬山法等进行了仿真实验比较；把单纯地解决对称TSP拓展到解决非对称TSP、QAP和JSP；对蚁群算法中的初始化参数对性能的影响做了初步探讨；蚁群算法发展史上的一篇奠基性文章。6可编辑ppt近期发展2000年，DorigoM和BonabeauE等在《Nature》上发表蚁群算法的研究综述，把这一领域的研究推向了国际学术的最前沿；进入21世纪的最近几年里，《Nature》曾多次对蚁群算法的研究成果进行报告。7可编辑ppt相关书籍2004年9月，MarcoDorigoandThomasStützle《AntColonyOptimization》；系统介绍蚁群算法，为蚁群算法的传播和科普做出了很重要一步；2007年翻译成中文出版。8可编辑ppt理论建设在理论建设方面，ACO取得的成果比较少，也是最薄弱的一方面。1999年GutjahrWJ的技术报告和2000年的论文中首次对蚁群算法的收敛性进行了证明。将蚁群算法的行为简化为在一幅代表所求问题的有向图上的随机行走过程，进而从有向图论的角度对一种改进蚁群算法——图搜索蚂蚁系统（Graph-BasedAntSystem，GBAS）的收敛性进行了理论分析。采用的数学工具是Markov链，证明了在一些合理的假设条件下他所提出的GBAS能以一定概率收敛到所求问题的最优解。9可编辑ppt蚁群优化算法的发展精华蚂蚁系统（ElitistStrategyforAntSystem，EAS）对解构造过程中表现优异的人工蚂蚁给予特殊的信息素释放奖励；Ant-Q算法将蚁群算法与Q学习算法结合，利用多个人工蚂蚁的协同效应；后期蚁群系统（AntColonySystem，ACS），基于排序的蚂蚁系统（RankBasedversionAS，ASrank），最大最小蚂蚁系统（Max-MinAntSystem，MMAS）10可编辑ppt蚁群优化算法的应用路由类问题旅行商、车辆路由、顺序排列等分配类问题二次分配、图着色、广义分配、频率分配、大学生课程时间表等调度类问题工序车间、开放车间、工作流车间、总延迟、总权重延迟、项目调度、组车间等

11可编辑ppt蚁群优化算法的应用子集类问题多重背包、最大独立集、冗余分配、集合覆盖、带权约束图树分割、边带权l-基树、最大图等机器学习类问题分配规则、贝叶斯网络、模糊系统等网络路由类问题面向连接的网络路由、无连接的网络路由、光学网络路由等12可编辑ppt1蚁群优化算法的生物学基础阿根廷蚂蚁双桥实验13可编辑ppt实验结果（1）摘自AntColonyOptimization14可编辑ppt实验结果（2）摘自AntColonyOptimization15可编辑ppt实验结果（3）摘自AntColonyOptimization16可编辑ppt障碍实验摘自AntSystem:OptimizationbyAColonyofCooperatingAgents17可编辑ppt生物蚂蚁的特点没有视觉计算与记忆能力有限依赖信息素(pheromone)通信、协作释放挥发正反馈18可编辑ppt2人工蚁群系统人工蚂蚁与生物蚂蚁的区别人工蚂蚁具有一定的记忆能力人工蚂蚁具有一定的视力（启发）人工蚂蚁生活在离散的时间环境中19可编辑ppt人工蚁群模型摘自AntSystem:OptimizationbyAColonyofCooperatingAgents20可编辑ppt人工蚁群a)初始状态；b)t=0，无信息素，人工蚂蚁以等概率选择左转或右转；c)t=1，较短的路径上信息素浓度较高，人工蚂蚁以较高的概率选择信息素浓度高的路径21可编辑ppt实例：TSPGraph(N,E)Euclidean距离蚂蚁数量22可编辑ppt实例：TSP人工蚂蚁的行为路径选择的概率是城市距离和路径上信息素浓度的函数；符合TSP规则；完成一次旅行后，在经过的路径上释放信息素；无需按原路返回。23可编辑ppt实例：TSP（参数与机制）路径上的信息素浓度信息素更新信息素释放(ant-cycle)24可编辑ppt实例：TSP（参数与机制）路径选择概率25可编辑pptTSP蚁群算法(ant-cycle)Step1Initialize:Sett:=0 {tisthetimecounter}SetNC:=0 {NCisthecyclescounter}Foreveryedge(i,j)setaninitialvaluefortrailintensityandPlacethem

antsonthennodes26可编辑pptTSP蚁群算法（ant-cycle）Step2

Sets:=1 {sisthetabulistindex}

Fork:=1tomdo Placethestartingtownofthek-thantintabuk(s)27可编辑pptTSP蚁群算法（ant-cycle）Step3 Repeatuntiltabulistisfull{thisstepwillberepeated(n-1) times}Sets:=s+1Fork:=1tomdoChoosethetown

j

tomoveto,withprobability{attimet

thek-th

antisontowni=tabuk(s-1)}Movethek-thanttothetownjInserttownj

intabuk

(s)28可编辑pptTSP蚁群算法（ant-cycle）Step4.1Fork:=1tomdoMovethek-thantfromtabuk(n)totabuk(1)ComputethelengthLk

ofthetourdescribedbythek-thantUpdatetheshortesttourfound29可编辑pptTSP蚁群算法（ant-cycle）Step4.2Foreveryedge(i,j) Fork:=1tomdo

30可编辑pptTSP蚁群算法（ant-cycle）Step5Foreveryedge(i,j)computeaccordingtoequation

Sett:=t+nSetNC:=NC+1Foreveryedge(i,j)set31可编辑pptTSP蚁群算法（ant-cycle）Step6If(NC<NCMAX)and(notstagnationbehavior) thenEmptyalltabulistsGotostep2 elsePrintshortesttourStop32可编辑ppt3蚁群算法调整与参数设置：信息素的相对重要性；：启发性因素的相对重要性；：信息素残留因子；Q：常数，控制信息素的释放；m：蚁群规模；其他：蚁群的初始分布33可编辑ppt信息素释放算法ant-cycleant-cycle34可编辑ppt信息素释放算法ant-densityant-density35可编辑ppt信息素释放算法ant-quantityant-quantity36可编辑ppt信息素释放算法对比测试集：Oliver30problem循环次数：NCMAX=5000测试次数：10摘自AntColonyOptimizationGA：424.63537可编辑ppt实验数据1ant-cycle摘自AntColonyOptimization38可编辑ppt实验数据2ant-cycle摘自AntColonyOptimization39可编辑ppt实验数据3ant-cycle摘自AntColonyOptimization40可编辑ppt参数：ant-cycleNCMAX=5000

摘自AntColonyOptimization41可编辑ppt蚁群规模：mant-cycle4x4grid摘自AntColonyOptimization42可编辑ppt蚁群初始分布均匀分布优于集中（单一城市）分布随机分布略好于均匀分布43可编辑ppt算法复杂度O(NC▪n2▪m)step1:O(n2+m),step2:O(m),step3:O(n2▪m),step4:O(n2▪m),step5:O(n2),step6:O(n▪m).44可编辑ppt实验数据（算法复杂度）摘自AntColonyOptimization45可编辑ppt4实例：JSPJob-shopSchedulingProblemM:机器数量J:任务数ojm:工序djm:工时:工序集合46可编辑pptJSP(Muth&Thompson6x6)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.34.1Job62.34.36.91.105.43.147可编辑pptJSP3x2problem48可编辑pptJSP路径选择49可编辑pptJSP待访问节点集合：下一步允许访问节点集合：算法结束：50可编辑ppt5实例：PID参数整定整定参数目标函数51可编辑pptPID参数整定Kp=12.345Td=6.7890Ti=9.8765(123456789098765)x(1234567890)52可编辑pptPID参数整定信息素释放53可编辑pptPID参数整定路径选择概率54可编辑ppt6蚁群优化算法研究现