遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》

第五部分蟻群優(yōu)化算法

AntColonyOptimization遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第1頁(yè)!參考文獻(xiàn)M.DorigoandT.Stutzle,AntColonyOptimization[M]:MITPress,2004段海濱，蟻群算法原理極其應(yīng)用[M]，2007.科學(xué)出版社遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第2頁(yè)!0蟻群優(yōu)化算法的歷史沿革意大利學(xué)者M(jìn)arcoDorigo（AlbertoColorni）于1991年在其博士論文中提出。和VittorioManiezzo一同設(shè)計(jì)了個(gè)ACO算法—螞蟻系統(tǒng)（AntSystem）。在真實(shí)螞蟻覓食行為的啟發(fā)下提出的一種高度創(chuàng)新性的啟發(fā)式算法。遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第3頁(yè)!重要文獻(xiàn)Colorni等，1994，“AntSystemforJob-shopScheduling”Colorni等，1996，“HeuristicsFromNatrureforHardCombinatorialOptimizationProblems”DorigoM等，1996，“Antsystem:optimizationbyacolonyofcooperatingagents”遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第4頁(yè)!近期發(fā)展2000年，DorigoM和BonabeauE等在《Nature》上發(fā)表蟻群算法的研究綜述，把這一領(lǐng)域的研究推向了國(guó)際學(xué)術(shù)的最前沿；進(jìn)入21世紀(jì)的最近幾年里，《Nature》曾多次對(duì)蟻群算法的研究成果進(jìn)行報(bào)告。遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第5頁(yè)!理論建設(shè)在理論建設(shè)方面，ACO取得的成果比較少，也是最薄弱的一方面。1999年GutjahrWJ的技術(shù)報(bào)告和2000年的論文中首次對(duì)蟻群算法的收斂性進(jìn)行了證明。將蟻群算法的行為簡(jiǎn)化為在一幅代表所求問(wèn)題的有向圖上的隨機(jī)行走過(guò)程，進(jìn)而從有向圖論的角度對(duì)一種改進(jìn)蟻群算法——圖搜索螞蟻系統(tǒng)（Graph-BasedAntSystem，GBAS）的收斂性進(jìn)行了理論分析。采用的數(shù)學(xué)工具是Markov鏈，證明了在一些合理的假設(shè)條件下他所提出的GBAS能以一定概率收斂到所求問(wèn)題的最優(yōu)解。遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第6頁(yè)!蟻群優(yōu)化算法的應(yīng)用路由類問(wèn)題旅行商、車輛路由、順序排列等分配類問(wèn)題二次分配、圖著色、廣義分配、頻率分配、大學(xué)生課程時(shí)間表等調(diào)度類問(wèn)題工序車間、開(kāi)放車間、工作流車間、總延遲、總權(quán)重延遲、項(xiàng)目調(diào)度、組車間等

遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第7頁(yè)!1蟻群優(yōu)化算法的生物學(xué)基礎(chǔ)阿根廷螞蟻雙橋?qū)嶒?yàn)遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第8頁(yè)!實(shí)驗(yàn)結(jié)果（2）摘自AntColonyOptimization遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第9頁(yè)!障礙實(shí)驗(yàn)摘自AntSystem:OptimizationbyAColonyofCooperatingAgents遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第10頁(yè)!2人工蟻群系統(tǒng)人工螞蟻與生物螞蟻的區(qū)別人工螞蟻具有一定的記憶能力人工螞蟻具有一定的視力（啟發(fā)）人工螞蟻生活在離散的時(shí)間環(huán)境中遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第11頁(yè)!人工蟻群a)初始狀態(tài)；b)t=0，無(wú)信息素，人工螞蟻以等概率選擇左轉(zhuǎn)或右轉(zhuǎn)；c)t=1，較短的路徑上信息素濃度較高，人工螞蟻以較高的概率選擇信息素濃度高的路徑遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第12頁(yè)!實(shí)例：TSP人工螞蟻的行為路徑選擇的概率是城市距離和路徑上信息素濃度的函數(shù)；符合TSP規(guī)則；完成一次旅行后，在經(jīng)過(guò)的路徑上釋放信息素；無(wú)需按原路返回。遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第13頁(yè)!實(shí)例：TSP（參數(shù)與機(jī)制）路徑選擇概率遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第14頁(yè)!TSP蟻群算法（ant-cycle）Step2

Sets:=1 {sisthetabulistindex}

Fork:=1tomdo Placethestartingtownofthek-thantintabuk(s)遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第15頁(yè)!TSP蟻群算法（ant-cycle）Step4.1Fork:=1tomdoMovethek-thantfromtabuk(n)totabuk(1)ComputethelengthLk

ofthetourdescribedbythek-thantUpdatetheshortesttourfound遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第16頁(yè)!TSP蟻群算法（ant-cycle）Step5Foreveryedge(i,j)puteaccordingtoequation

Sett:=t+nSetNC:=NC+1Foreveryedge(i,j)set遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第17頁(yè)!3蟻群算法調(diào)整與參數(shù)設(shè)置：信息素的相對(duì)重要性；：?jiǎn)l(fā)性因素的相對(duì)重要性；：信息素殘留因子；Q：常數(shù)，控制信息素的釋放；m：蟻群規(guī)模；其他：蟻群的初始分布遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第18頁(yè)!信息素釋放算法ant-densityant-density遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第19頁(yè)!信息素釋放算法對(duì)比測(cè)試集：Oliver30problem循環(huán)次數(shù)：NCMAX=5000測(cè)試次數(shù)：10摘自AntColonyOptimizationGA：424.635遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第20頁(yè)!實(shí)驗(yàn)數(shù)據(jù)2ant-cycle摘自AntColonyOptimization遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第21頁(yè)!參數(shù)：ant-cycleNCMAX=5000

摘自AntColonyOptimization遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第22頁(yè)!蟻群初始分布均勻分布優(yōu)于集中（單一城市）分布隨機(jī)分布略好于均勻分布遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第23頁(yè)!實(shí)驗(yàn)數(shù)據(jù)（算法復(fù)雜度）摘自AntColonyOptimization遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第24頁(yè)!JSP(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.1遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第25頁(yè)!JSP路徑選擇遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第26頁(yè)!5實(shí)例：PID參數(shù)整定整定參數(shù)目標(biāo)函數(shù)遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第27頁(yè)!PID參數(shù)整定信息素釋放遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第28頁(yè)!6蟻群優(yōu)化算法研究現(xiàn)狀蟻群系統(tǒng)（AntColonySystem，ACS）基于排序的螞蟻系統(tǒng)（RankBasedversionAS，ASrank）最大最小螞蟻系統(tǒng)（Max-MinAntSystem，MMAS）遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第29頁(yè)!蟻群系統(tǒng)ACS引入負(fù)反饋機(jī)制。每當(dāng)螞蟻由一個(gè)節(jié)點(diǎn)移動(dòng)到另一個(gè)節(jié)點(diǎn)時(shí)，該路徑上的信息素按照如下公式被相應(yīng)的消除一部分，從而實(shí)現(xiàn)一種信息素的局部調(diào)整，以減小已選擇過(guò)的路徑再次被選擇的概率。遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第30頁(yè)!基于排序的螞蟻系統(tǒng)ASrank與“精英策略”相似；算法中總是更新更好進(jìn)程上的信息素；選擇的標(biāo)準(zhǔn)是其行程長(zhǎng)度決定的排序；遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第31頁(yè)!MarcoDorigoMacroDorigo遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第32頁(yè)!Antsystem:optimization

byacolonyofcooperatingagents更加系統(tǒng)地闡述了蟻群算法的基本原理和數(shù)學(xué)模型；與遺傳算法、禁忌搜索算法、模擬退火算法、爬山法等進(jìn)行了仿真實(shí)驗(yàn)比較；把單純地解決對(duì)稱TSP拓展到解決非對(duì)稱TSP、QAP和JSP；對(duì)蟻群算法中的初始化參數(shù)對(duì)性能的影響做了初步探討；蟻群算法發(fā)展史上的一篇奠基性文章。遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第33頁(yè)!相關(guān)書(shū)籍2004年9月，MarcoDorigoandThomasStützle《AntColonyOptimization》；系統(tǒng)介紹蟻群算法，為蟻群算法的傳播和科普做出了很重要一步；2007年翻譯成中文出版。遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第34頁(yè)!蟻群優(yōu)化算法的發(fā)展精華螞蟻系統(tǒng)（ElitistStrategyforAntSystem，EAS）對(duì)解構(gòu)造過(guò)程中表現(xiàn)優(yōu)異的人工螞蟻給予特殊的信息素釋放獎(jiǎng)勵(lì)；Ant-Q算法將蟻群算法與Q學(xué)習(xí)算法結(jié)合，利用多個(gè)人工螞蟻的協(xié)同效應(yīng)；后期蟻群系統(tǒng)（AntColonySystem，ACS），基于排序的螞蟻系統(tǒng)（RankBasedversionAS，ASrank），最大最小螞蟻系統(tǒng)（Max-MinAntSystem，MMAS）遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第35頁(yè)!蟻群優(yōu)化算法的應(yīng)用子集類問(wèn)題多重背包、最大獨(dú)立集、冗余分配、集合覆蓋、帶權(quán)約束圖樹(shù)分割、邊帶權(quán)l(xiāng)-基樹(shù)、最大圖等機(jī)器學(xué)習(xí)類問(wèn)題分配規(guī)則、貝葉斯網(wǎng)絡(luò)、模糊系統(tǒng)等網(wǎng)絡(luò)路由類問(wèn)題面向連接的網(wǎng)絡(luò)路由、無(wú)連接的網(wǎng)絡(luò)路由、光學(xué)網(wǎng)絡(luò)路由等遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第36頁(yè)!實(shí)驗(yàn)結(jié)果（1）摘自AntColonyOptimization遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第37頁(yè)!實(shí)驗(yàn)結(jié)果（3）摘自AntColonyOptimization遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第38頁(yè)!生物螞蟻的特點(diǎn)沒(méi)有視覺(jué)計(jì)算與記憶能力有限依賴信息素(pheromone)通信、協(xié)作釋放揮發(fā)正反饋遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第39頁(yè)!人工蟻群模型摘自AntSystem:OptimizationbyAColonyofCooperatingAgents遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第40頁(yè)!實(shí)例：TSPGraph(N,E)Euclidean距離螞蟻數(shù)量遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第41頁(yè)!實(shí)例：TSP（參數(shù)與機(jī)制）路徑上的信息素濃度信息素更新信息素釋放(ant-cycle)遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第42頁(yè)!TSP蟻群算法(ant-cycle)Step1Initialize:Sett:=0 {tisthetimecounter}SetNC:=0 {NCisthecyclescounter}Foreveryedge(i,j)setaninitialvaluefortrailintensityandPlacethem

antsonthennodes遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第43頁(yè)!TSP蟻群算法（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)遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第44頁(yè)!TSP蟻群算法（ant-cycle）Step4.2Foreveryedge(i,j) Fork:=1tomdo

遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第45頁(yè)!TSP蟻群算法（ant-cycle）Step6If(NC<NCMAX)and(notstagnationbehavior) thenEmptyalltabulistsGotostep2 elsePrintshortesttourStop遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第46頁(yè)!信息素釋放算法ant-cycleant-cycle遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第47頁(yè)!信息素釋放算法ant-quantityant-quantity遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第48頁(yè)!實(shí)驗(yàn)數(shù)據(jù)1ant-cycle摘自AntColonyOptimization遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第49頁(yè)!實(shí)驗(yàn)數(shù)據(jù)3ant-cycle摘自AntColonyOptimization遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第50頁(yè)!蟻群規(guī)模：mant-cycle4x4grid摘自AntColonyOptimization遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第51頁(yè)!算法復(fù)雜度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).遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》共60頁(yè)，您現(xiàn)在瀏覽的是第52頁(yè)!4實(shí)例：JSPJob-shopSchedulingP