蟻群算法研究報(bào)告(已修改)
2025-05-08 07:40 本頁面
【正文】 蟻群算法研究報(bào)告 題 目 信息工程學(xué)院 專 業(yè) 計(jì)算機(jī)科學(xué)與技術(shù)姓 名 程亮學(xué) 號 201115068 指導(dǎo)教師 譚同德 201464 目 錄第一章 蟻群算法概述 2 2 2 3 人工蟻群的特點(diǎn) 3 蟻群的特點(diǎn) 3 4 4第二章 蟻群算法解決TSP問題 5 TSP問題描述 5 基于 TSP 問題的蟻群算法模型 5 6 6 7參考文獻(xiàn) 9 第一章 蟻群算法概述蟻群算法（Ant Clony Optimization， ACO）是一種群智能算法，它是由一群無智能或有輕微智能的個(gè)體（Agent）通過相互協(xié)作而表現(xiàn)出智能行為，從而為求解復(fù)雜問題提供了一個(gè)新的可能性。從1991年意大利學(xué)者DorigoM等首次提出蟻群算法以來，蟻群算法作為一種自然計(jì)算方法，由解決tsP(旅行商)問題開始，從一維靜態(tài)優(yōu)化問題到多維動態(tài)優(yōu)化問題，從解決離散域范圍問題到連續(xù)域范圍，發(fā)展到今天已經(jīng)相對成熟了，應(yīng)用到了眾多的領(lǐng)域，比如說數(shù)據(jù)挖掘、物流、通信網(wǎng)絡(luò)、大規(guī)模集成電路、網(wǎng)絡(luò)路由等。而且這種仿生算法同遺傳算法、粒子群算法、免疫算法、神經(jīng)網(wǎng)絡(luò)等智能算法相結(jié)合的新算法，更好的提高了效率并加強(qiáng)了其在實(shí)際問題中的應(yīng)用。蟻群算法之所以能引起相關(guān)領(lǐng)域研究者的注意，是因?yàn)檫@種求解模式能將問題求解的快速性、全局優(yōu)化特征以及有限時(shí)間內(nèi)答案的合理性結(jié)合起來。其中，尋優(yōu)的快速性是通過正反饋式的信息傳遞和積累來保證的。而算法的早熟性收斂又可以通過其分布式計(jì)算特征加以避免，同時(shí)，具有貪婪啟發(fā)式搜索特征的蟻群系統(tǒng)又能在搜索過程的早期找到可以接受的問題解答。這種優(yōu)越的問題分布式求解模式經(jīng)過相關(guān)領(lǐng)域研究者的關(guān)注和努力，已經(jīng)在最初的算法模型基礎(chǔ)上得到了很大的改進(jìn)和拓展。研究蟻群算法的改進(jìn)方法以及其發(fā)展和應(yīng)用的趨勢，為蟻群算法在更多領(lǐng)域有更多的應(yīng)用價(jià)值來說是十分必要的。蟻群算法是一種仿生學(xué)算法，是由自然界中螞蟻覓食的行為而啟發(fā)的。在自然界中，螞蟻覓食過程中，蟻群總能夠按照尋找到一條從蟻巢和食物源的最優(yōu)路徑。圖（1）顯示了這樣一個(gè)覓食的過程。在圖1（a）中，有一群螞蟻，假如A是蟻巢，E是食物源（反之亦然）。這群螞蟻將沿著蟻巢和食物源之間的直線路徑行駛。假如在A和E之間突然出現(xiàn)了一個(gè)障礙物（圖1（b）），那么，在B點(diǎn)（或D點(diǎn)）的螞蟻將要做出決策，到底是向左行駛還是向右行駛？由于一開始路上沒有前面螞蟻留下的信息素（pheromone），螞蟻朝著兩個(gè)方向行進(jìn)的概率是相等的。但是當(dāng)有螞蟻?zhàn)哌^時(shí)，它將會在它行進(jìn)的路上釋放出信息素，并且這種信息素會議一定的速率散發(fā)掉。信息素是螞蟻之間交流的工具之一。它后面的螞蟻通過路上信息素的濃度，做出決策，往左還是往右。很明顯，沿著短邊的的路徑上信息素將會越來越濃（圖1（c）），從而吸引了越來越多的螞蟻沿著這條路徑行駛。 人工蟻群的特點(diǎn). 蟻群算法中所使用的螞蟻是現(xiàn)實(shí)螞蟻行為特征的一種抽象，稱為人工螞蟻。人工螞蟻的通訊方式、相互協(xié)作機(jī)制與現(xiàn)實(shí)螞蟻一樣，但是如果完全依照現(xiàn)實(shí)螞蟻行為機(jī)制來設(shè)計(jì)蟻群算法，實(shí)驗(yàn)表明算法需要很多的時(shí)間才會收斂，而且可能會收斂于一些局部優(yōu)解。故人工螞蟻又有不同于現(xiàn)實(shí)螞蟻的地方，以tsP問題為例：(1)人工螞蟻有一定的記憶能力，它可以記住已經(jīng)走過的路徑，以保證不會重復(fù)走相同的城市?，F(xiàn)實(shí)的螞蟻沒有記憶。(2)人工螞蟻不僅僅依據(jù)信息素來確定要走的路徑，還引入了與問題相關(guān)的啟發(fā)信息，比如相鄰邊的長度。這個(gè)
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1