資源描述：
《淺談蟻群算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。
1、—、引言蟻群算法(AntColonyOptimization,ACO),是一種用來在圖中尋找優(yōu)化路徑的算法。它由MarcoDorigo于1992年在他的博士論文中提；1
2、,其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。蟻群算法是一種模擬進(jìn)化算法，初步的研究表明該算法具有許多優(yōu)良的性質(zhì)。蟻群算法成功解決了旅行商問題(TravelingSalesmanProblem,TSP)：―個商人要到若干城市推銷物品，從一個城市出發(fā)要到達(dá)其他各城市一次而且最多一次最后又冋到第一個城市。尋找一條最短路徑，使他從起點的城市到達(dá)所有城市一遍，最
3、后回到起點的總路程最短。若把每個城市看成是圖上的節(jié)點，那么旅行商問題就是在N個節(jié)點的完全圖上尋找一條花費最少的冋路。最基本的蟻群算法見第二節(jié)。目前典型的蟻群算法冇隨機(jī)蟻群算法、排序蟻群算法和最大最小蟻群算法，其中后兩種蟻群算法是對前一種的優(yōu)化。本文將終點介紹隨機(jī)蟻群算法。二、基本蟻群算法(-)算法思想各個螞蟻在沒冇事先告訴他們食物在什么地方的前提下開始尋找食物。當(dāng)一只找到食物以后，它會向環(huán)境釋放一種信息索，信息索多的地方顯然經(jīng)過這里的螞蟻會多，因而會有更多的螞蟻聚集過來。假設(shè)有兩條路從窩通向食物，開始的時候，走這兩條路的螞蟻
4、數(shù)量同樣多(或者較長的路上螞蟻多，這也無關(guān)緊要)。當(dāng)螞蟻沿著一條路到達(dá)終點以后會馬上返回來，這樣，短的路螞蟻來回一次的時間就短，這也意味著重復(fù)的頻率就快，因而在單位時間里走過的螞蟻數(shù)目就多，灑下的信息素自然也會多，自然會有更多的螞蟻被吸引過來，從而灑下更多的信息素。因此，越來越多地螞蟻聚集到較短的路徑上來，最短的路徑就找到了。蟻群算法的基本思想如下圖表示:(c)(a)(b)圖3最優(yōu)比重圖1等概率選擇圖2最優(yōu)路徑(二)算法描述基本蟻群算法的算法簡單描述如下：1.所有螞蟻遇到障礙物時按照等概率選擇路徑，并留下信息素；2.隨著時間
5、的推移，較短路徑的信息索濃度升高；3.螞蟻再次遇到障礙物時，會選擇信息素濃度高的路徑；4.較短路徑的信息素濃度繼續(xù)升高，最終最優(yōu)路徑被選擇出來。三、隨機(jī)蟻群算法(-)算法思想在基本蟻群算法中，螞蟻會在多條可選擇的路徑中，自動選擇岀最短的一條路徑。但是，一旦蟻群選擇了一條比之前短的路徑，就會認(rèn)為這條路徑是最好的，在這條路徑上一直走下去。這樣的算法存在問題：螞蟻可能只是找到了局部的最短路徑，而忽略了全局最優(yōu)解。因此，在基木蟻群算法的基礎(chǔ)上，需要對螞蟻選路的方案加以改善：有些螞蟻并沒有象其它螞蟻一樣總重復(fù)同樣的路，他們會另辟蹊徑，
6、也就是它會按照一定的概率不往信息索高的地方。如果令開辟的道路比原來的其他道路更短，那么，漸漸地，更多的螞蟻被吸引到這條較短的路上來。最后，經(jīng)過一段時間運行，可能會出現(xiàn)一條最短的路徑被人多數(shù)螞蟻重復(fù)著，這就是優(yōu)化的隨機(jī)蟻群算法。為了實現(xiàn)螞蟻的“隨機(jī)”選路，我們需要做以下假設(shè)：1.范圍：螞蟻觀察到的范圍是一個方格世界，螞蟻有一個參數(shù)為速度半徑，如果半徑等于2,那么它能觀察到的范圍就是2*2個方格世界，并且能移動的距離也在這個范圍Z內(nèi)。1.環(huán)境：環(huán)境以一定的速率讓信息索消失。2.覓食規(guī)則：在每只螞蟻能感知的范圍內(nèi)尋找是否有食物，如
7、果有就直接過去。否則看是否冇信息素，并冃比較在能感知的范圍內(nèi)哪一點的信息素最多，那么它朝哪個方向走的概率就大。這就意味著每只螞蟻多會以小概率犯錯誤，從而并不是往信息索最多的點移動。3.避障規(guī)則：如果螞蟻要移動的方向有障礙物扌半住，它會隨機(jī)的選擇另一個方向，并且冇信息素指引的話，它會按照覓食的規(guī)則行為。4.播撒信息索規(guī)則：每只螞蟻在找到食物后撒發(fā)的信息索。自然想到一個問題：開始時環(huán)境沒有信息素，螞蟻為什么會相對有效的找到食物呢？這個問題用螞蟻的移動規(guī)則同樣可以解釋。首先，它要能盡量保持某種慣性，這樣使得螞蟻盡量向前方移動（開始
8、，這個前方是隨機(jī)固定的一個方向），而不是原地?zé)o謂的打轉(zhuǎn)或者震動；其次，螞蟻要有一定的隨機(jī)性，雖然有了固定的方向，但它也不能像粒子一樣直線運動下去，而是有一個隨機(jī)的干擾。這樣就使得螞蟻運動起來貝有了一定的目的性，盡量保持原來的方向，但又有新的試探，這就解釋了為什么單個螞蟻在復(fù)雜的諸如迷宮的地圖屮仍然能找到隱蔽得很好的食物。（-）算法描述隨機(jī)蟻群算法的算法描述如2算法輸入：城市數(shù)量N,兩兩城市間的距離，所冇路徑的信息素濃度算法輸出：螞蟻走過的路徑長度1.設(shè)置全部城市都沒有去過，走過的路徑長度為0；2.隨機(jī)選擇一個出發(fā)的城市；3.
9、i=14.while（i
