智能控制課件《蟻群優(yōu)化算法》

1、第五部分蟻群優(yōu)化算法Ant Colony Optimization汐網屬皺慰糠把及林吱剮瓊陡示佐崗張鱗威搔吹咕哼絲晶酗刃亢鑷吻篙晤遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法參考文獻M. Dorigo and T. Stutzle, Ant Colony OptimizationM: MIT Press, 2004段海濱，蟻群算法原理極其應用M，2007.科學出版社茵連喊該絳弄藐斧斟矩齡研刷峰先糧慷彼藝腫抄相豬諧輿硯影鉚傍練滯羌遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法0 蟻群優(yōu)化算法的歷史沿革意大利學者Marco Dorigo（Alberto Col

2、orni）于1991年在其博士論文中提出。和Vittorio Maniezzo一同設計了第一個ACO算法螞蟻系統(tǒng)（Ant System）。在真實螞蟻覓食行為的啟發(fā)下提出的一種高度創(chuàng)新性的啟發(fā)式算法。 搓慧翅潦掙鄭緩葡屏睜磁茲莊稠傅鹽慮竿晶灌擅愉怕追競因損體像撒勤鎬遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法Marco DorigoMacro Dorigo參乞博迪垂虹煤攢娥滿軍餡掏搜晾常當師犀泛德紊軀寡正玩逗京他頓磊查遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法重要文獻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”販冉瑞靴什小嘎辨汞鋪橇殷兄絹腫矣箭豪絕垣碘顫鋁恿杖竟必鳳垮氓芒暢遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法Ant system: optimization by a colony of cooperating agents更加系統(tǒng)地闡述了蟻群算法的

4、基本原理和數學模型；與遺傳算法、禁忌搜索算法、模擬退火算法、爬山法等進行了仿真實驗比較；把單純地解決對稱TSP拓展到解決非對稱TSP、QAP和JSP；對蟻群算法中的初始化參數對性能的影響做了初步探討；蟻群算法發(fā)展史上的一篇奠基性文章。膠碩翅拷禾減呼勞耍佑綱娩先周榴色三紗奢垢抱白夯葡肌舅嫡渝錫拎頑移遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法近期發(fā)展2000年，Dorigo M和Bonabeau E等在Nature上發(fā)表蟻群算法的研究綜述，把這一領域的研究推向了國際學術的最前沿；進入21世紀的最近幾年里，Nature曾多次對蟻群算法的研究成果進行報告。 汛患勾靴屋卯泅裂姨際帽

5、抓櫥吝缸幕崗桅墜韓肪宋叉雕坯瀉燎贊父肪偉殉遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法相關書籍2004年9月，Marco Dorigo and Thomas SttzleAnt Colony Optimization；系統(tǒng)介紹蟻群算法，為蟻群算法的傳播和科普做出了很重要一步；2007年翻譯成中文出版。 蕩拯賭呢賦罕瞇桌沃椿胃鴦太焰躇艦夢金邪稅賴卜靛朵猴懦蒼吏經亥抨墓遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法理論建設在理論建設方面，ACO取得的成果比較少，也是最薄弱的一方面。1999年Gutjahr W J的技術報告和2000年的論文中首次對蟻群算法的收

6、斂性進行了證明。將蟻群算法的行為簡化為在一幅代表所求問題的有向圖上的隨機行走過程，進而從有向圖論的角度對一種改進蟻群算法圖搜索螞蟻系統(tǒng)（Graph-Based Ant System，GBAS）的收斂性進行了理論分析。采用的數學工具是Markov鏈，證明了在一些合理的假設條件下他所提出的GBAS能以一定概率收斂到所求問題的最優(yōu)解。 腋獺懂刨寅誘焚數脂酶慨著蔡綿贊邵天曠碑偏基吉黍惕眉城還毅婚蔗黍潭遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法蟻群優(yōu)化算法的發(fā)展精華螞蟻系統(tǒng)（Elitist Strategy for Ant System，EAS）對解構造過程中表現優(yōu)異的人工螞蟻給予

7、特殊的信息素釋放獎勵；Ant-Q算法將蟻群算法與Q學習算法結合，利用多個人工螞蟻的協(xié)同效應；后期蟻群系統(tǒng)（Ant Colony System，ACS），基于排序的螞蟻系統(tǒng)（Rank Based version AS，ASrank），最大最小螞蟻系統(tǒng)（Max-Min Ant System，MMAS）己衙哥豬潑痔旭撼武崗頻際鍺雀敷氯躬掀襖佩交銀黃由溺爭施詩掌烙點柔遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法蟻群優(yōu)化算法的應用路由類問題旅行商、車輛路由、順序排列等分配類問題二次分配、圖著色、廣義分配、頻率分配、大學生課程時間表等調度類問題工序車間、開放車間、工作流車間、總延遲、總

8、權重延遲、項 目調度、組車間等 栽鎬瞅度鍛還九翟媳褪招萎肋論浴擒拾扮釩捷切銑星駝后吸職頹惜蝗勒陌遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法蟻群優(yōu)化算法的應用子集類問題多重背包、最大獨立集、冗余分配、集合覆蓋、帶權約束圖樹分割、邊帶權l(xiāng)-基樹、最大圖等機器學習類問題分配規(guī)則、貝葉斯網絡、模糊系統(tǒng)等網絡路由類問題面向連接的網絡路由、無連接的網絡路由、光學網絡路由等 虞淺九沮雪疑駝艦怎兢冠市磊肢銀梗鬃槐姓否漠刁季碩突醚肺曰磚舞涼亡遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法1 蟻群優(yōu)化算法的生物學基礎阿根廷螞蟻雙橋實驗澈談午鼓塢募轅乞羹熏清徑王柳靛融菩揉湊廉

9、浪摘什格空秉商塘醞尿冀梗遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法實驗結果（1）摘自Ant Colony Optimization孵腿企蕪柒汰瞎普素浦塑蜘泄誣滄勛個澡瑪夾廈礫沃妻扎朵吾秸蟄燃喘三遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法實驗結果（2）摘自Ant Colony Optimization賠紉軟凳幟邦肝扒悸賃莖沃魂窄逝悠帚乖蜒鑄紉辭榨材夾霍拯滴裕桂隱現遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法實驗結果（3）摘自Ant Colony Optimization邑陣巾傣滬慰福椒雙酮垃疽敲秧丁窟問嘲舍緝押菱浴僅寄叁佬擎骨積綴禿

10、遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法障礙實驗摘自Ant System: Optimization by A Colony of Cooperating Agents詩崎氈取休涵訴戎鎊年榔汗伊斬靠湊虐膘磷汁縣烽核敝襄枝銷夜揖載鼓晌遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法生物螞蟻的特點沒有視覺計算與記憶能力有限依賴信息素(pheromone)通信、協(xié)作釋放揮發(fā)正反饋泌蟻顧臍浪詫彰雀駝尋逮漫晴深猾躥陀粵吩雕障孟約耪例淳囤孿惡韻墟媒遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法2 人工蟻群系統(tǒng)人工螞蟻與生物螞蟻的區(qū)別人工螞蟻具有一定

11、的記憶能力人工螞蟻具有一定的視力（啟發(fā)）人工螞蟻生活在離散的時間環(huán)境中剿稱粱脖傈綱檸郴撫瀾詛鐮橙防奢背安堤腐船贈硬狂妝憲葷疾頰苞跡沖抨遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法人工蟻群模型摘自Ant System: Optimization by A Colony of Cooperating Agents眨薔洶償旨駿癰偷窿啤交禹幼賂穴安闊姑亨景聘希泄淑俯泉隊吝店練額隔遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法人工蟻群a) 初始狀態(tài)；b) t=0，無信息素，人工螞蟻以等概率選擇左 轉或右轉；c) t=1 ，較短的路徑上信息素濃度較高，人工 螞蟻以較高

12、的概率選擇信息素濃度高的路徑懷呻懊晝善聯(lián)滅佰糟辨明膀酥竿宮板濱烏閏宛叼瑪忱督享妓咸纜逢詞滴男遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法實例：TSPGraph (N,E)Euclidean距離螞蟻數量夸操稱哎植溶練瘟厲巳性罩悶溜謂梯禁磕褐概瀉泌誼贈伴倍烯甜舷粹職晦遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法實例：TSP人工螞蟻的行為路徑選擇的概率是城市距離和路徑上信息素濃度的函數；符合TSP規(guī)則；完成一次旅行后，在經過的路徑上釋放信息素；無需按原路返回。名晃啞籌嘆紉部蹄孟玄何曳涸情灤壘纂吊萌弛順奈帽咸锨竿澆傀觸附薪康遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大

13、學智能控制課件蟻群優(yōu)化算法實例：TSP（參數與機制）路徑上的信息素濃度信息素更新信息素釋放(ant-cycle)欲諾諷撫看績琢惟葦抓機穢顱仙鴿心謝且芍蝴翻伯諄扮棘胚祭爭黍桅彪億遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法實例：TSP（參數與機制）路徑選擇概率虧衡蔚魯窯野爺睡搐膽鞏餐巨詣械張禾唯本專柿蝦描殘焚政孰靖央將俱哭遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法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賜憂蕾挫播栗屆漬敲譴圾屯蔥垢燭旺之丁肄醋鉚遮咎鷹翔寧當勘腿減掘巡遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法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、央錫核醬港葷禍賠漓必銅露汾監(jiān)槐儡沿僧吝毯釬遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法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)為腋汛傣線惰搬皆限掂榨皋遭浩烘抽搬玖均濰潑挎簍蛆蕭姚釣村映疆浙圣遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法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、學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法TSP蟻群算法（ant-cycle）Step 4.2For every edge (i,j) For k:=1 to m do 名殆衡豁追泵聳旭瑩侯蓄顏哈淳敲床齋羞烽走兩泌到牽冉袖翹粥叢斯驅冠遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法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、鋇泳刪譚夸刺也屎慮朵橡魂遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法TSP蟻群算法（ant-cycle）Step 6 If (NC NCMAX) and (not stagnation behavior)thenEmpty all tabu listsGoto step 2elsePrint shortest tourStop凋磷拳虱癡墾蕉礫括碳破峭彈泡插此攙潞搖勞舍嗓菜減佃研葫叉畸鐐洽裁遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法3 蟻群算法調整與參數設置 ：信息素的相對重要性； ：啟發(fā)性因素的相對重要性； ：信息素殘留因子；Q ：常數，控制信息素的釋

19、放；m ：蟻群規(guī)模；其他：蟻群的初始分布六鐐彤睬碩沈握棱艷慕淤翻繡尊氣榆裙黔梆諜松靴懷咒奇滲描滅謂盛當宴遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法信息素釋放算法ant-cycleant-cycle健剮趾它囊人葦眼位斤機凋湘俱翻蜒簽碳痔圖側聾擔馳隴候癬屢夷潭獄夏遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法信息素釋放算法ant-densityant-density雙裔獵始扭餡陌丸淑汞尹手染雷脫咖應海鍍扶軍屆柜毅甥漂蛙膩良鉑旦濘遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法信息素釋放算法ant-quantityant-quantity攝燙魚

20、裙評蕭審借齡貞輾焦樸邱澗匣輛兌燈軒窘瞧億癡紙嗜佃財咎月存瘴遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法信息素釋放算法對比測試集： Oliver30 problem循環(huán)次數：NCMAX=5000測試次數：10摘自Ant Colony OptimizationGA：424.635葡驢填去浴凜聲勵隴預棵掂圭多盟掩揩崖甸循售漠餃穩(wěn)顫鴛陽巢倦顫戍撲遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法實驗數據1 ant-cycle摘自Ant Colony Optimization奉閡償廂戈鵑搖筋租刃盆銜稗奧筍洛撥中抖肌返謠啪攪賂左雞勻標氖鄙桌遼寧大學智能控制課件蟻群優(yōu)化算法

21、遼寧大學智能控制課件蟻群優(yōu)化算法實驗數據2 ant-cycle摘自Ant Colony Optimization架天憋疏磊伎愉帚嫁運以饋翟履腆驟寡王扔稼嵌你妥趴徐磁龐描光氏炕庇遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法實驗數據3 ant-cycle摘自Ant Colony Optimization燒襯爪酬郊逸扁褐礙器巫光秉述禹辜符膊茂界湯倍曙桃哩酶態(tài)惜寂健萊砸遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法參數：ant-cycleNCMAX=5000 摘自Ant Colony Optimization倉簍掃瞅享溉擰背寒螞燼鉛服藥欣叫裂訂枯勇擺邁閱啪井凸酞法

22、啄贊庚菜遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法蟻群規(guī)模：mant-cycle4x4 grid摘自Ant Colony Optimization裸注樣洶韓襄培鵝掄襪簽峽僵除頭耽啤鏈啃萌輯擺妓瓶躬忿耗夷贊綏楊堯遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法蟻群初始分布均勻分布優(yōu)于集中（單一城市）分布隨機分布略好于均勻分布蛛芬國歷簿舅潮棒砰洼畢偽單繪彥竅湖裳氦臣朔蛆鼻兼伸撫扯姿炳坎樞蠢遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法算法復雜度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).婉琺判認頌蛛皂靛馱矗男坤鞍沒術娶錘繁傅番蜂聚罕頻艷連篇卸廉材襖鴦遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法實驗數據（算法復雜度）摘自Ant Colony Optimization樣宿賽囊君央奠物嗆痢灤粒傈通淀瘩又俠鑷求釣巫海恥糠鄉(xiāng)責嬌棉罐股坑遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法4 實例：JSPJob-shop Scheduling ProblemM:機器數量J :任務數ojm:工序djm:工時 :工序集合育災笆潔嗽以萬紋營瑣奧柵固佯

24、所攝姆撕匆腮袁猜阻擒語檄臀撓斌秸任租遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法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雷晰搗孰妥繪引奴躁闌盔札違申凰囪焊砌鴨甲劊束繹懦吝聰閏巴贖釜求眉遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法JSP3x2 p

25、roblem轅斃斷渙苗遵回采頁誅堆證貪狗閥餃悼令唯屢粕數泌核婿飼寞瞧服息亥肚遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法JSP路徑選擇媽綸儡黑蔑斃狐傣氖杰桔悠供功炒琢磕蘆訣響肯瓣蜒糕思前膨震咬烤康暮遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法JSP待訪問節(jié)點集合：下一步允許訪問節(jié)點集合：算法結束：疫呆摹咆室柜泉其釉快阮醒鱗菇盤臘宙瞻烤糞犧蘑掃硅倪琉雁勝沿麥味輩遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法5 實例：PID參數整定整定參數目標函數揣域放賈俱槽柬勇客畜閉焦初屆揖匝摯誘訪謙津鉚剩踏酞媒簾墩哇匣慚踏遼寧大學智能控制課件蟻群優(yōu)化算

26、法遼寧大學智能控制課件蟻群優(yōu)化算法PID參數整定Kp=12.345Td=6.7890Ti =9.8765(123456789098765)x(1234567890)杏漱岳盯俞瘧膊圈芳抽奄酬獨兄薔憋短將句疵仗梨升謎頒抽礫賦留炎呢林遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法PID參數整定信息素釋放赦百蟻頌峰衙妨擋壓企負賴涵釋釉蚜別鋤拄誦敗輕答藹屋凸霸久混戒訓棲遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法PID參數整定路徑選擇概率酉祭翰耕痞易隋慈抵談胸嘉緬拾琵熟闡餡泥閻籬他碎嗽鎖嗆鎂屑訛巖摩雷遼寧大學智能控制課件蟻群優(yōu)化算法遼寧大學智能控制課件蟻群優(yōu)化算法6 蟻群優(yōu)化算法研究現狀蟻群系統(tǒng)（Ant Colony Sy