Outline ● What is ACO ● The Algorithm ● Applications ● Future Directions ● References.pdf

下载文档

4
0
约4千字
约 15页
2017-04-06 发布于江苏
举报
版权申诉
保障服务

Outline ● What is ACO ● The Algorithm ● Applications ● Future Directions ● References.pdf

1、本文档共15页，可阅读全部内容。
2、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击这里二次下载。
4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。

Outline ● What is ACO ● The Algorithm ● Applications ● Future Directions ● References

Ant Colony Optimization Ak?n Günay 10.04.2007 2Out l i ne ● What is ACO? ● The Algorithm ● Applications ● Future Directions ● References 3I n t roduc t ion ● Ant Colony Optimization (ACO) is a meta- heuristic for combinatorial optimization ● Part of the Swarm Intelligence approach ● Inspired from the foraging behaviour of the real ants ● First proposed by Marco Dorigo in 1992 4B io log i ca l I nsp i ra t ion ● ACO is inspired from the foraging behaviour of real ants ● Stigmergy for communication – indirect, non-symbolic communication via modifying the environment – stigmergic information is local ● Real ants use a chemical substance called pheromone 5The Doub le Br idge Exper iment ( D e n e u b o u r g e t a l . ) Branches have equal length Branches have different length p1= m1k  h m1k  hm2k  h  Model of the observed behaviour by Goss et al. 6The ACO Meta -heur i s t i c ● initialize parameters and pheromone trails ● while termination condition not met do – construct ant solutions – local search (optional) – update pheromone trails ● end-while 7Trave l l i ng Sa lesman P rob lem (TSP) ● Given a number of cities and the costs of travelling from any city to any other city, finding the cheapest round-trip route that visits each city exactly once and then returns to the starting city 8Ant Sys tem (AS) T o u r C o n s t r u c t i o n Using?the?random proportional rule ?ant? k ?currently? in?city?i ?choses?to?go?to?city? j ?with?probaility? p . pij k= [ij ]  [ij]  ∑l∈N ik [il ]  [il ]  ,?if? j∈N i k where?ij=1/d ij ?-?Large? ?may?cause?stagnation ?-?Large? ?leads?to?greedy?search 9Ant Sys tem (AS) P h e r o m o n e U p d a t e Evaporation; ij1?p ij ,? i , j∈L Pheromone?deposit; ijij∑ k=1 m ij k ,? i , j∈L ij k={1 /C k ,0, if?arc? i , j ?belongs?to?T k otherwise ?-?Evaporation?is?used?to?forget?previous?bad?decisions ?-?Pheromone?deposit?aims?to?deposit?more?pheromone? ????to?the?arcs?that?belong?to?