基于蟻群算法的路徑最優(yōu)研究 畢業(yè)答辯課件

1、導(dǎo) 師: 王康平答辯人: 劉媛媛專 業(yè): 計(jì)算機(jī)科學(xué)與技術(shù)基于蟻群算法的路徑最優(yōu)問(wèn)題研究論文的結(jié)構(gòu)和主要內(nèi)容第一部分 選題的背景與意義第二部分 國(guó)內(nèi)外研究現(xiàn)狀第三部分 研究?jī)?nèi)容與方法第四部分 研究中可能存在的問(wèn)題第五部分 預(yù)期結(jié)果一 選題背景與意義 2001年至今1996年-2001年意大利學(xué)者Dorigo1991年啟發(fā)各種改進(jìn)算法的提出，應(yīng)用領(lǐng)域更廣 引起學(xué)者關(guān)注，在應(yīng)用領(lǐng)域得到拓寬ACO首次被系統(tǒng)的提出自然界中真實(shí)蟻群集體行為一 選題背景與意義蟻群算法的由來(lái)：螞蟻是地球上最常見、數(shù)量最多的昆蟲種類之一，常常成群結(jié)隊(duì)地出現(xiàn)在人類的日常生活環(huán)境中。這些昆蟲的群體生物智能特征，引起了一些學(xué)者的注

2、意。意大利學(xué)者M(jìn).Dorigo，V.Maniezzo等人在觀察螞蟻的覓食習(xí)性時(shí)發(fā)現(xiàn)，螞蟻總能找到巢穴與食物源之間的最短路徑。 經(jīng)研究發(fā)現(xiàn)，螞蟻的這種群體協(xié)作功能是通過(guò)一種遺留在其來(lái)往路徑上的叫做信息素(Pheromone)的揮發(fā)性化學(xué)物質(zhì)來(lái)進(jìn)行通信和協(xié)調(diào)的?；瘜W(xué)通信是螞蟻采取的基本信息交流方式之一，在螞蟻的生活習(xí)性中起著重要的作用。通過(guò)對(duì)螞蟻覓食行為的研究，他們發(fā)現(xiàn)，整個(gè)蟻群就是通過(guò)這種信息素進(jìn)行相互協(xié)作，形成正反饋，從而使多個(gè)路徑上的螞蟻都逐漸聚集到最短的那條路徑上。二 國(guó)內(nèi)外研究現(xiàn)狀目前，蟻群算法己經(jīng)成為一個(gè)備受關(guān)注的研究熱點(diǎn)和前沿性課題。人們對(duì)蟻群算法的研究已經(jīng)由當(dāng)初的TSP領(lǐng)域滲透到多

3、個(gè)應(yīng)用領(lǐng)域，由解決一維靜態(tài)優(yōu)化問(wèn)題發(fā)展到解決多維動(dòng)態(tài)組合優(yōu)化問(wèn)題，由離散域范圍內(nèi)研究逐漸拓展到了連續(xù)域范圍內(nèi)研究。同時(shí)在蟻群算法的模型改進(jìn)以及其他仿生優(yōu)化算法的融合方面也取得了相當(dāng)豐富的研究成果，從而使這種新興的仿生優(yōu)化算法展現(xiàn)出前所未有的生機(jī)。 3.1.1蟻群算法的基本思想 在自然界中，螞蟻的食物源往往隨機(jī)散布于蟻巢周圍，通過(guò)觀察可以發(fā)現(xiàn)，經(jīng)過(guò)一段時(shí)間后，螞蟻總能找到一條從蟻巢到食物源的最短路徑。自然界中的螞蟻雖然視覺(jué)能力十分有限，但它們?cè)谝捠尺^(guò)程中，卻能夠通過(guò)播撒、感知信息素與其它同伴建立起通訊關(guān)系，并以此相互協(xié)調(diào)、分工、合作來(lái)找到食物源和巢穴之間的最短路徑。并且在相同的時(shí)間內(nèi)，路徑越短則

4、遺留的信息素濃度就越大，而螞蟻在選擇路徑時(shí)，傾向于那些信息素濃度較高的路徑，這樣選擇較短路徑的螞蟻也隨之增多。因此，由大量螞蟻組成的蟻群集體覓食行為表現(xiàn)出了一種正反饋現(xiàn)象：一條路徑上走過(guò)的螞蟻越多，則后來(lái)者選擇這條路徑的概率就越高。螞蟻個(gè)體之間就是通過(guò)這種信息素的交流機(jī)制，來(lái)搜索食物，并最終找到最短路徑。3.1.2螞蟻覓食原理：自然界中，螞蟻這種視盲生物，在沒(méi)有任何先知經(jīng)驗(yàn)的情況下總能找到從其巢穴到食物源的最佳路徑，甚至在該路徑上放置障礙物之后，它們?nèi)匀荒芎芸熘匦抡业叫碌淖罴崖肪€。3.1.3蟻群算法的優(yōu)缺點(diǎn)蟻群算法的優(yōu)點(diǎn)不依賴于所求問(wèn)題的具體數(shù)學(xué)表達(dá)式描述，具有很強(qiáng)的找到全局最優(yōu)解的優(yōu)化能力。

5、該算法具有正反饋、較強(qiáng)的魯棒性、全局性、普遍性、優(yōu)良的分布式并行計(jì)算機(jī)制、易于與其他方法相結(jié)合等諸多優(yōu)點(diǎn)。蟻群算法的缺點(diǎn)：蟻群算法的成功主要在實(shí)驗(yàn)層次上，很少有理論來(lái)解釋利用蟻群算法為什么能夠成功地解決這些問(wèn)題，它沒(méi)有堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)；蟻群算法的模型普適性不強(qiáng)，其模型不能直接應(yīng)用于實(shí)際優(yōu)化問(wèn)題；蟻群算法的局部搜索能力較弱，易于出現(xiàn)停滯和局部收斂、收斂速度慢等問(wèn)題，因而往往需要嵌入一些專門的輔助技巧；長(zhǎng)時(shí)間花費(fèi)在解的構(gòu)造上，從而導(dǎo)致搜索時(shí)間過(guò)長(zhǎng)，算法最先基于離散問(wèn)題，不能直接解決連續(xù)優(yōu)化問(wèn)題。3.2 自然蟻群與人工蟻群 蟻群算法都是從自然界中真實(shí)螞蟻尋找食物行為得到啟發(fā)提出來(lái)的。人們只有通過(guò)對(duì)蟻群

6、行為的一種模擬來(lái)滿足實(shí)際問(wèn)題的求解需要。所以人工蟻群與真實(shí)蟻群之間存在一定的異同。 相似之處在于：都是優(yōu)先選擇信息素濃度大的路徑。 兩者的區(qū)別： （1）在于人工蟻群有一定的記憶能力，能夠記憶已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn)。 （2）人工蟻群選擇路徑時(shí)不是盲目的。而是按一定規(guī)律有意識(shí)地尋找最短路徑。例如，在TSP問(wèn)題中，可以預(yù)先知道當(dāng)前城市到下一個(gè)目的地的距離。針對(duì)螞蟻釋放信息是問(wèn)題，M.Dorigo等人曾給出3中不同的模型，分別為蟻周系統(tǒng)、蟻量系統(tǒng)和蟻密系統(tǒng)，其計(jì)算公式如下：1.蟻周系統(tǒng)模型2.蟻量系統(tǒng)模型3.蟻密系統(tǒng)模型其中，Q為常數(shù)，表示螞蟻循環(huán)一次所釋放的信息素總量；L為第k只螞蟻經(jīng)過(guò)路徑的長(zhǎng)度。d為城

7、市間的距離。3.3.2 蟻群系統(tǒng)蟻群系統(tǒng)的狀態(tài)轉(zhuǎn)移規(guī)則 一只位于節(jié)點(diǎn)r的螞蟻通過(guò)應(yīng)用下式給出的規(guī)則選擇下一個(gè)將要移動(dòng)到的城市s： 其中，S根據(jù)下列公式得到 q是在0,1區(qū)間均勻分布的隨機(jī)數(shù) q0的大小決定了利用先驗(yàn)知識(shí)與探索新路徑之間的相對(duì)重要性。 蟻群系統(tǒng)局部更新原則 螞蟻應(yīng)用下列局部更新原則對(duì)它們所經(jīng)過(guò)的邊進(jìn)行激素更新： 實(shí)驗(yàn)發(fā)現(xiàn)， 可以產(chǎn)生好的結(jié)果，其中n是城市的數(shù)量， 是由最近的鄰域啟發(fā)產(chǎn)生的一個(gè)路徑長(zhǎng)度。局部更新原則可以有效的避免收斂到同一路徑。3.3.3 最大-最小螞蟻系統(tǒng)信息素軌跡更新在 MMAS中，只有一只螞蟻用于在每次循環(huán)后更新信息軌跡。經(jīng)修改的軌跡更新原則如下： 表示迭代最

8、優(yōu)解或全局最優(yōu)解的值。在蟻群算法中主要使用全局最優(yōu)解，而在MMAS中則主要使用迭代最優(yōu)解。 MMAS對(duì)信息素軌跡的最小值和最大值分別施加了 和 的限制，從而使得對(duì)所有信息素軌跡 ，有信息素軌跡的限制的選取： 的選取要基于兩點(diǎn)假設(shè)： 最優(yōu)解在搜索停滯發(fā)生之前不久被找出。對(duì)解構(gòu)造的主要影響是由信息素軌跡的上限與下限之間的相對(duì)差異決定。3.4 蟻群算法的實(shí)現(xiàn) (1)參數(shù)初始化。令時(shí)間t=0和循環(huán)次數(shù)Nc=0，設(shè)置最大循環(huán)次數(shù)Ncmax, 將 m個(gè)螞蟻置于n個(gè)元素(城市)上，令有向圖上每條邊(i, j)的初始化信息量ij(t)=const, 其中const表示常數(shù)，且初始時(shí)刻ij(0)=0 (2)循環(huán)

9、次數(shù)Nc Nc+1。 (3)螞蟻的禁忌表索引號(hào)k=1。 (4)螞蟻數(shù)目 kk+1 。 (5)螞蟻個(gè)體根據(jù)狀態(tài)轉(zhuǎn)移概率公式(1)計(jì)算的概率選擇元素(城市) j 并前進(jìn)，jC - tabuk。 (6)修改禁忌表指針，即選擇好之后將螞蟻移動(dòng)到新的元素(城市)，并把該元素(城市)移動(dòng)到該螞蟻個(gè)體的禁忌表中。 (7)若集合C中元素(城市)未遍歷完，即km，則跳轉(zhuǎn)到第(4)步，否則執(zhí)行第(8)步。 (8)根據(jù)公式(2)和式(3)更新每條路徑上的信息量。 (9)若滿足結(jié)束條件，即如果循環(huán)次數(shù)Nc Ncmax 則循環(huán)結(jié)束并輸出程序計(jì)算結(jié)果，否則清空禁忌表并跳轉(zhuǎn)到第(2)步。四 預(yù)期結(jié)果 對(duì)于信息素?fù)]發(fā)因子、啟

10、發(fā)式因子、自啟發(fā)因子、螞蟻的數(shù)目m對(duì)于蟻群算法性能的影響進(jìn)行了實(shí)驗(yàn)研究，發(fā)現(xiàn)蟻群算法中各個(gè)參數(shù)的取值對(duì)最后的求解性能有很大的影響，目前還是靠經(jīng)驗(yàn)對(duì)各個(gè)參數(shù)取值。在分析各個(gè)參數(shù)的作用及對(duì)算法性能的影響的基礎(chǔ)上，并通過(guò)大量實(shí)驗(yàn)驗(yàn)證，給出了蟻群算法中各參數(shù)的一個(gè)較理想取值范圍。五 研究中可能遇到的問(wèn)題問(wèn)題一 蟻群算法參數(shù)選擇很重要，選擇不當(dāng)?shù)脑挄?huì)出現(xiàn)搜索的過(guò)早停滯現(xiàn)象或陷入局部最優(yōu)問(wèn)題。問(wèn)題二 蟻群算法對(duì)非線性系統(tǒng)辨識(shí)中對(duì) 輸入信號(hào)的選擇是一個(gè)難點(diǎn)。 由于作者的知識(shí)水平的限制，本文的工作還存在著較多的不足之處。比如用改進(jìn)的蟻群算法求解大型的TSP問(wèn)題結(jié)果就差一些，并且運(yùn)行時(shí)間很長(zhǎng)，效果不是很理想。本文所提出的改進(jìn)的算法還只是應(yīng)用于旅行商問(wèn)題，對(duì)于一定的旅行