蟻群算法基本原理及其應用實例

蟻群算法概況

蟻群算法又稱螞蟻算法，是一種用來在圖中尋找優(yōu)化路徑的機率型算法。它由Marco Dorigo于1992年在他的博士論文中提出，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。蟻群算法是一種模擬進化算法，初步的研究表明該算法具有許多優(yōu)良的性質。針對PID控制器參數(shù)優(yōu)化設計問題，將蟻群算法設計的結果與遺傳算法設計的結果進行了比較，數(shù)值仿真結果表明，蟻群算法具有一種新的模擬進化優(yōu)化方法的有效性和應用價值。

各個螞蟻在沒有事先告訴他們食物在什么地方的前提下開始尋找食物。當一只找到食物以后，它會向環(huán)境釋放一種揮發(fā)性分泌物pheromone （稱為信息素，該物質隨著時間的推移會逐漸揮發(fā)消失，信息素濃度的大小表征路徑的遠近）來實現(xiàn)的，吸引其他的螞蟻過來，這樣越來越多的螞蟻會找到食物。有些螞蟻并沒有像其它螞蟻一樣總重復同樣的路，他們會另辟蹊徑，如果另開辟的道路比原來的其他道路更短，那么，漸漸地，更多的螞蟻被吸引到這條較短的路上來。最后，經過一段時間運行，可能會出現(xiàn)一條最短的路徑被大多數(shù)螞蟻重復著。

蟻群算法是一種仿生學算法，是由自然界中螞蟻覓食的行為而啟發(fā)的。在自然界中，螞蟻覓食過程中，蟻群總能夠按照尋找到一條從蟻巢和食物源的最優(yōu)路徑。圖（1）顯示了這樣一個覓食的過程。

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

?

蟻群算法原理

假如蟻群中所有螞蟻的數(shù)量為m，所有城市之間的信息素用矩陣pheromone表示，最短路徑為bestLength，最佳路徑為bestTour。每只螞蟻都有自己的內存，內存中用一個禁忌表（Tabu）來存儲該螞蟻已經訪問過的城市，表示其在以后的搜索中將不能訪問這些城市；還有用另外一個允許訪問的城市表（Allowed）來存儲它還可以訪問的城市；另外還用一個矩陣（Delta）來存儲它在一個循環(huán)（或者迭代）中給所經過的路徑釋放的信息素；還有另外一些數(shù)據(jù)，例如一些控制參數(shù)（α，β，ρ，Q）（α，β，ρ，Q），該螞蟻行走玩全程的總成本或距離（tourLength），等等。假定算法總共運行MAX_GEN次，運行時間為t。
?