蟻群算法簡介

《蟻群算法簡介》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、1.蟻群算法簡介????蟻群算法（AntClonyOptimization，ACO）是一種群智能算法，它是由一群無智能或有輕微智能的個體（Agent）通過相互協(xié)作而表現(xiàn)出智能行為，從而為求解復(fù)雜問題提供了一個新的可能性。蟻群算法最早是由意大利學(xué)者ColorniA.,DorigoM.等于1991年提出。經(jīng)過20多年的發(fā)展，蟻群算法在理論以及應(yīng)用研究上已經(jīng)得到巨大的進步。?????蟻群算法是一種仿生學(xué)算法，是由自然界中螞蟻覓食的行為而啟發(fā)的。在自然界中，螞蟻覓食過程中，蟻群總能夠按照尋找到一條從蟻巢和食物源的最優(yōu)路徑。圖（1）顯示了這樣一個覓食的過程。圖

2、（1）螞蟻覓食?????在圖1（a）中，有一群螞蟻，假如A是蟻巢，E是食物源（反之亦然）。這群螞蟻將沿著蟻巢和食物源之間的直線路徑行駛。假如在A和E之間突然出現(xiàn)了一個障礙物（圖1（b）），那么，在B點（或D點）的螞蟻將要做出決策，到底是向左行駛還是向右行駛？由于一開始路上沒有前面螞蟻留下的信息素（pheromone），螞蟻朝著兩個方向行進的概率是相等的。但是當(dāng)有螞蟻走過時，它將會在它行進的路上釋放出信息素，并且這種信息素會議一定的速率散發(fā)掉。信息素是螞蟻之間交流的工具之一。它后面的螞蟻通過路上信息素的濃度，做出決策，往左還是往右。很明顯，沿著短邊的的

3、路徑上信息素將會越來越濃（圖1（c）），從而吸引了越來越多的螞蟻沿著這條路徑行駛。2.TSP問題描述?????蟻群算法最早用來求解TSP問題，并且表現(xiàn)出了很大的優(yōu)越性，因為它分布式特性，魯棒性強并且容易與其它算法結(jié)合，但是同時也存在這收斂速度慢，容易陷入局部最優(yōu)（localoptimal）等缺點。?????TSP問題（TravelSalespersonProblem，即旅行商問題或者稱為中國郵遞員問題），是一種，是一種NP-hard問題，此類問題用一般的算法是很大得到最優(yōu)解的，所以一般需要借助一些啟發(fā)式算法求解，例如遺傳算法（GA），蟻群算法（ACO

4、），微粒群算法（PSO）等等。?????TSP問題可以分為兩類，一類是對稱TSP問題（SymmetricTSP），另一類是非對稱問題（AsymmetricTSP）。所有的TSP問題都可以用一個圖（Graph）來描述：令V={c1,c2,…,ci,…,cn}，i=1,2,…,n，是所有城市的集合.?ci表示第i個城市，?n為城市的數(shù)目；E={(r,s):r,s∈V}是所有城市之間連接的集合；C={crs:r,s∈V}是所有城市之間連接的成本度量（一般為城市之間的距離）；如果crs?=csr,那么該TSP問題為對稱的，否則為非對稱的。一個TSP問題可以表

5、達為：求解遍歷圖G=(V,E,C)，所有的節(jié)點一次并且回到起始節(jié)點，使得連接這些節(jié)點的路徑成本最低。3.蟻群算法原理?????假如蟻群中所有螞蟻的數(shù)量為m，所有城市之間的信息素用矩陣pheromone表示，最短路徑為bestLength，最佳路徑為bestTour。每只螞蟻都有自己的內(nèi)存，內(nèi)存中用一個禁忌表（Tabu）來存儲該螞蟻已經(jīng)訪問過的城市，表示其在以后的搜索中將不能訪問這些城市；還有用另外一個允許訪問的城市表（Allowed）來存儲它還可以訪問的城市；另外還用一個矩陣（Delta）來存儲它在一個循環(huán)（或者迭代）中給所經(jīng)過的路徑釋放的信息素；還

6、有另外一些數(shù)據(jù)，例如一些控制參數(shù)（，，，Q），該螞蟻行走玩全程的總成本或距離（tourLength），等等。假定算法總共運行MAX_GEN次，運行時間為t。蟻群算法計算過程如下：（1）初始化設(shè)t=0，初始化bestLength為一個非常大的數(shù)（正無窮），bestTour為空。初始化所有的螞蟻的Delt矩陣所有元素初始化為0，Tabu表清空，Allowed表中加入所有的城市節(jié)點。隨機選擇它們的起始位置（也可以人工指定）。在Tabu中加入起始節(jié)點，Allowed中去掉該起始節(jié)點。（2）為每只螞蟻選擇下一個節(jié)點。為每只螞蟻選擇下一個節(jié)點，該節(jié)點只能從All

7、owed中以某種概率（公式1）搜索到，每搜到一個，就將該節(jié)點加入到Tabu中，并且從Allowed中刪除該節(jié)點。該過程重復(fù)n-1次，直到所有的城市都遍歷過一次。遍歷完所有節(jié)點后，將起始節(jié)點加入到Tabu中。此時Tabu表元素數(shù)量為n+1（n為城市數(shù)量），Allowed元素數(shù)量為0。接下來按照（公式2）計算每個螞蟻的Delta矩陣值。最后計算最佳路徑，比較每個螞蟻的路徑成本，然后和bestLength比較，若它的路徑成本比bestLength小，則將該值賦予bestLength，并且將其Tabu賦予BestTour。（公式1）（公式2）其中表示選擇城市

8、j的概率，k表示第k個螞蟻，表示城市i，j在第t時刻的信息素濃度，表示從城市i到城市j的可見度，，表示城市i