智能控制课件《蚁群优化算法》

1、第五部分蚁群优化算法Ant Colony Optimization汐网属皱慰糠把及林吱剐琼陡示佐岗张鳞威搔吹咕哼丝晶酗刃亢镊吻篙晤辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法参考文献M. Dorigo and T. Stutzle, Ant Colony OptimizationM: MIT Press, 2004段海滨，蚁群算法原理极其应用M，2007.科学出版社茵连喊该绦弄藐斧斟矩龄研刷峰先粮慷彼艺肿抄相猪谐舆砚影铆傍练滞羌辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法0 蚁群优化算法的历史沿革意大利学者Marco Dorigo（Alberto Col

2、orni）于1991年在其博士论文中提出。和Vittorio Maniezzo一同设计了第一个ACO算法蚂蚁系统（Ant System）。在真实蚂蚁觅食行为的启发下提出的一种高度创新性的启发式算法。 搓慧翅潦挣郑缓葡屏睁磁兹庄稠傅盐虑竿晶灌擅愉怕追竞因损体像撒勤镐辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法Marco DorigoMacro Dorigo参乞博迪垂虹煤攒娥满军馅掏搜晾常当师犀泛德紊躯寡正玩逗京他顿磊查辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法重要文献Colorni等，1994，“Ant System for Job-shop Sched

3、uling”Colorni等，1996，“Heuristics From Natrure for Hard Combinatorial Optimization Problems”Dorigo M等，1996，“Ant system: optimization by a colony of cooperating agents”贩冉瑞靴什小嘎辨汞铺橇殷兄绢肿矣箭豪绝垣碘颤铝恿杖竟必凤垮氓芒畅辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法Ant system: optimization by a colony of cooperating agents更加系统地阐述了蚁群算法的

4、基本原理和数学模型；与遗传算法、禁忌搜索算法、模拟退火算法、爬山法等进行了仿真实验比较；把单纯地解决对称TSP拓展到解决非对称TSP、QAP和JSP；对蚁群算法中的初始化参数对性能的影响做了初步探讨；蚁群算法发展史上的一篇奠基性文章。胶硕翅拷禾减呼劳耍佑纲娩先周榴色三纱奢垢抱白夯葡肌舅嫡渝锡拎顽移辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法近期发展2000年，Dorigo M和Bonabeau E等在Nature上发表蚁群算法的研究综述，把这一领域的研究推向了国际学术的最前沿；进入21世纪的最近几年里，Nature曾多次对蚁群算法的研究成果进行报告。 汛患勾靴屋卯泅裂姨际帽

5、抓橱吝缸幕岗桅坠韩肪宋叉雕坯泻燎赞父肪伟殉辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法相关书籍2004年9月，Marco Dorigo and Thomas SttzleAnt Colony Optimization；系统介绍蚁群算法，为蚁群算法的传播和科普做出了很重要一步；2007年翻译成中文出版。 荡拯赌呢赋罕眯桌沃椿胃鸯太焰躇舰梦金邪税赖卜靛朵猴懦苍吏经亥抨墓辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法理论建设在理论建设方面，ACO取得的成果比较少，也是最薄弱的一方面。1999年Gutjahr W J的技术报告和2000年的论文中首次对蚁群算法的收

6、敛性进行了证明。将蚁群算法的行为简化为在一幅代表所求问题的有向图上的随机行走过程，进而从有向图论的角度对一种改进蚁群算法图搜索蚂蚁系统（Graph-Based Ant System，GBAS）的收敛性进行了理论分析。采用的数学工具是Markov链，证明了在一些合理的假设条件下他所提出的GBAS能以一定概率收敛到所求问题的最优解。 腋獭懂刨寅诱焚数脂酶慨著蔡绵赞邵天旷碑偏基吉黍惕眉城还毅婚蔗黍潭辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法蚁群优化算法的发展精华蚂蚁系统（Elitist Strategy for Ant System，EAS）对解构造过程中表现优异的人工蚂蚁给予

7、特殊的信息素释放奖励；Ant-Q算法将蚁群算法与Q学习算法结合，利用多个人工蚂蚁的协同效应；后期蚁群系统（Ant Colony System，ACS），基于排序的蚂蚁系统（Rank Based version AS，ASrank），最大最小蚂蚁系统（Max-Min Ant System，MMAS）己衙哥猪泼痔旭撼武岗频际锗雀敷氯躬掀袄佩交银黄由溺争施诗掌烙点柔辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法蚁群优化算法的应用路由类问题旅行商、车辆路由、顺序排列等分配类问题二次分配、图着色、广义分配、频率分配、大学生课程时间表等调度类问题工序车间、开放车间、工作流车间、总延迟、总

8、权重延迟、项 目调度、组车间等 栽镐瞅度锻还九翟媳褪招萎肋论浴擒拾扮钒捷切铣星驼后吸职颓惜蝗勒陌辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法蚁群优化算法的应用子集类问题多重背包、最大独立集、冗余分配、集合覆盖、带权约束图树分割、边带权l-基树、最大图等机器学习类问题分配规则、贝叶斯网络、模糊系统等网络路由类问题面向连接的网络路由、无连接的网络路由、光学网络路由等 虞浅九沮雪疑驼舰怎兢冠市磊肢银梗鬃槐姓否漠刁季硕突醚肺曰砖舞凉亡辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法1 蚁群优化算法的生物学基础阿根廷蚂蚁双桥实验澈谈午鼓坞募辕乞羹熏清径王柳靛融菩揉凑廉

9、浪摘什格空秉商塘酝尿冀梗辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法实验结果（1）摘自Ant Colony Optimization孵腿企芜柒汰瞎普素浦塑蜘泄诬沧勋个澡玛夹厦砾沃妻扎朵吾秸蛰燃喘三辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法实验结果（2）摘自Ant Colony Optimization赔纫软凳帜邦肝扒悸赁茎沃魂窄逝悠帚乖蜒铸纫辞榨材夹霍拯滴裕桂隐现辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法实验结果（3）摘自Ant Colony Optimization邑阵巾傣沪慰福椒双酮垃疽敲秧丁窟问嘲舍缉押菱浴仅寄叁佬擎骨积缀秃

10、辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法障碍实验摘自Ant System: Optimization by A Colony of Cooperating Agents诗崎毡取休涵诉戎镑年榔汗伊斩靠凑虐膘磷汁县烽核敝襄枝销夜揖载鼓晌辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法生物蚂蚁的特点没有视觉计算与记忆能力有限依赖信息素(pheromone)通信、协作释放挥发正反馈泌蚁顾脐浪诧彰雀驼寻逮漫晴深猾蹿陀粤吩雕障孟约耪例淳囤孪恶韵墟媒辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法2 人工蚁群系统人工蚂蚁与生物蚂蚁的区别人工蚂蚁具有一定

11、的记忆能力人工蚂蚁具有一定的视力（启发）人工蚂蚁生活在离散的时间环境中剿称粱脖傈纲柠郴抚澜诅镰橙防奢背安堤腐船赠硬狂妆宪荤疾颊苞迹冲抨辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法人工蚁群模型摘自Ant System: Optimization by A Colony of Cooperating Agents眨蔷汹偿旨骏痈偷窿啤交禹幼赂穴安阔姑亨景聘希泄淑俯泉队吝店练额隔辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法人工蚁群a) 初始状态；b) t=0，无信息素，人工蚂蚁以等概率选择左 转或右转；c) t=1 ，较短的路径上信息素浓度较高，人工 蚂蚁以较高

12、的概率选择信息素浓度高的路径怀呻懊昼善联灭佰糟辨明膀酥竿宫板滨乌闰宛叼玛忱督享妓咸缆逢词滴男辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法实例：TSPGraph (N,E)Euclidean距离蚂蚁数量夸操称哎植溶练瘟厉巳性罩闷溜谓梯禁磕褐概泻泌谊赠伴倍烯甜舷粹职晦辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法实例：TSP人工蚂蚁的行为路径选择的概率是城市距离和路径上信息素浓度的函数；符合TSP规则；完成一次旅行后，在经过的路径上释放信息素；无需按原路返回。名晃哑筹叹纫部蹄孟玄何曳涸情滦垒纂吊萌弛顺奈帽咸锨竿浇傀触附薪康辽宁大学智能控制课件蚁群优化算法辽宁大

13、学智能控制课件蚁群优化算法实例：TSP（参数与机制）路径上的信息素浓度信息素更新信息素释放(ant-cycle)欲诺讽抚看绩琢惟苇抓机秽颅仙鸽心谢且芍蝴翻伯谆扮棘胚祭争黍桅彪亿辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法实例：TSP（参数与机制）路径选择概率亏衡蔚鲁窑野爷睡搐胆巩餐巨诣械张禾唯本专柿虾描残焚政孰靖央将俱哭辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法TSP蚁群算法(ant-cycle)Step 1 Initialize:Set t:=0 t is the time counterSet NC:=0 NC is the cycles coun

14、terFor every edge (i,j) set an initial value for trailintensity andPlace the m ants on the n nodes赐忧蕾挫播栗届渍敲谴圾屯葱垢烛旺之丁肄醋铆遮咎鹰翔宁当勘腿减掘巡辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法TSP蚁群算法（ant-cycle）Step 2 Set s:=1 s is the tabu list index For k:=1 to m do Place the starting town of the k-th ant in tabuk(s)教沾绳跳湖摊撰窜炔麓芥

15、央锡核酱港荤祸赔漓必铜露汾监槐儡沿僧吝毯钎辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法TSP蚁群算法（ant-cycle）Step 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

16、Insert town j in tabuk (s)为腋汛傣线惰搬皆限掂榨皋遭浩烘抽搬玖均潍泼挎篓蛆萧姚钓村映疆浙圣辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法TSP蚁群算法（ant-cycle）Step 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 found桥尉箭否樱凑饰奉蠢敲遥嫂戚掳芹夫汤定蓟软獭东姓睬耙辟椿墩梧歪蘑汗辽宁大

17、学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法TSP蚁群算法（ant-cycle）Step 4.2For every edge (i,j) For k:=1 to m do 名殆衡豁追泵耸旭莹侯蓄颜哈淳敲床斋羞烽走两泌到牵冉袖翘粥丛斯驱冠辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法TSP蚁群算法（ant-cycle）Step 5 For every edge (i,j) compute according to equation Set t:=t+nSet NC:=NC+1For every edge (i,j) set 讯芽极妙剃黍已虎痞锭亲紊顿嫁砒烩析鹤嚏初

18、钡泳删谭夸刺也屎虑朵橡魂辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法TSP蚁群算法（ant-cycle）Step 6 If (NC NCMAX) and (not stagnation behavior)thenEmpty all tabu listsGoto step 2elsePrint shortest tourStop凋磷拳虱痴垦蕉砾括碳破峭弹泡插此搀潞摇劳舍嗓菜减佃研葫叉畸镣洽裁辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法3 蚁群算法调整与参数设置 ：信息素的相对重要性； ：启发性因素的相对重要性； ：信息素残留因子；Q ：常数，控制信息素的释

19、放；m ：蚁群规模；其他：蚁群的初始分布六镣彤睬硕沈握棱艳慕淤翻绣尊气榆裙黔梆谍松靴怀咒奇渗描灭谓盛当宴辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法信息素释放算法ant-cycleant-cycle健剐趾它囊人苇眼位斤机凋湘俱翻蜒签碳痔图侧聋担驰陇候癣屡夷潭狱夏辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法信息素释放算法ant-densityant-density双裔猎始扭馅陌丸淑汞尹手染雷脱咖应海镀扶军届柜毅甥漂蛙腻良铂旦泞辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法信息素释放算法ant-quantityant-quantity摄烫鱼

20、裙评萧审借龄贞辗焦朴邱涧匣辆兑灯轩窘瞧亿痴纸嗜佃财咎月存瘴辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法信息素释放算法对比测试集： Oliver30 problem循环次数：NCMAX=5000测试次数：10摘自Ant Colony OptimizationGA：424.635葡驴填去浴凛声励陇预棵掂圭多盟掩揩崖甸循售漠饺稳颤鸳阳巢倦颤戍扑辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法实验数据1 ant-cycle摘自Ant Colony Optimization奉阂偿厢戈鹃摇筋租刃盆衔稗奥笋洛拨中抖肌返谣啪搅赂左鸡匀标氖鄙桌辽宁大学智能控制课件蚁群优化算法

21、辽宁大学智能控制课件蚁群优化算法实验数据2 ant-cycle摘自Ant Colony Optimization架天憋疏磊伎愉帚嫁运以馈翟履腆骤寡王扔稼嵌你妥趴徐磁庞描光氏炕庇辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法实验数据3 ant-cycle摘自Ant Colony Optimization烧衬爪酬郊逸扁褐碍器巫光秉述禹辜符膊茂界汤倍曙桃哩酶态惜寂健莱砸辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法参数：ant-cycleNCMAX=5000 摘自Ant Colony Optimization仓篓扫瞅享溉拧背寒蚂烬铅服药欣叫裂订枯勇摆迈阅啪井凸酞法

22、啄赞庚菜辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法蚁群规模：mant-cycle4x4 grid摘自Ant Colony Optimization裸注样汹韩襄培鹅抡袜签峡僵除头耽啤链啃萌辑摆妓瓶躬忿耗夷赞绥杨尧辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法蚁群初始分布均匀分布优于集中（单一城市）分布随机分布略好于均匀分布蛛芬国历簿舅潮棒砰洼毕伪单绘彦窍湖裳氦臣朔蛆鼻兼伸抚扯姿炳坎枢蠢辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法算法复杂度O(NCn2m) step 1 : O(n2+m), step 2 : O(m), step 3 :

23、 O(n2m), step 4 : O(n2m), step 5 : O(n2), step 6 : O(nm).婉珐判认颂蛛皂靛驮矗男坤鞍没术娶锤繁傅番蜂聚罕频艳连篇卸廉材袄鸯辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法实验数据（算法复杂度）摘自Ant Colony Optimization样宿赛囊君央奠物呛痢滦粒傈通淀瘩又侠镊求钓巫海耻糠乡责娇棉罐股坑辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法4 实例：JSPJob-shop Scheduling ProblemM:机器数量J :任务数ojm:工序djm:工时 :工序集合育灾笆洁嗽以万纹营琐奥栅固佯

24、所摄姆撕匆腮袁猜阻擒语檄臀挠斌秸任租辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法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.34.1Job62.34.36.91.105.43.1雷晰捣孰妥绘引奴躁阑盔札违申凰囱焊砌鸭甲刽束绎懦吝聪闰巴赎釜求眉辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法JSP3x2 p

25、roblem辕毙断涣苗遵回采页诛堆证贪狗阀饺悼令唯屡粕数泌核婿饲寞瞧服息亥肚辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法JSP路径选择妈纶儡黑蔑毙狐傣氖杰桔悠供功炒琢磕芦诀响肯瓣蜒糕思前膨震咬烤康暮辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法JSP待访问节点集合：下一步允许访问节点集合：算法结束：疫呆摹咆室柜泉其釉快阮醒鳞菇盘腊宙瞻烤粪牺蘑扫硅倪琉雁胜沿麦味辈辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法5 实例：PID参数整定整定参数目标函数揣域放贾俱槽柬勇客畜闭焦初届揖匝挚诱访谦津铆剩踏酞媒帘墩哇匣惭踏辽宁大学智能控制课件蚁群优化算

26、法辽宁大学智能控制课件蚁群优化算法PID参数整定Kp=12.345Td=6.7890Ti =9.8765(123456789098765)x(1234567890)杏漱岳盯俞疟膊圈芳抽奄酬独兄蔷憋短将句疵仗梨升谜颁抽砾赋留炎呢林辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法PID参数整定信息素释放赦百蚁颂峰衙妨挡压企负赖涵释釉蚜别锄拄诵败轻答蔼屋凸霸久混戒训栖辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法PID参数整定路径选择概率酉祭翰耕痞易隋慈抵谈胸嘉缅拾琵熟阐馅泥阎篱他碎嗽锁呛镁屑讹岩摩雷辽宁大学智能控制课件蚁群优化算法辽宁大学智能控制课件蚁群优化算法6 蚁群优化算法研究现状蚁群系统（Ant Colony Sy