蟻群算法概述

蟻群算法概述程亮1.蟻群算法的產(chǎn)生AntColonyAlgorithms隨著近代仿生學(xué)發(fā)展,這種似乎微不足道的小東西越來越多地受到學(xué)者們的關(guān)注。蟻群算法正是由蟻群的行為啟發(fā)而產(chǎn)生的“自然”算法。1991年M·Dorigo等人首先提出了蟻群算法(AntColonyAlgorithms),人們開始了對蟻群的研究:相對弱小,功能并不強(qiáng)大的個體是如何完成復(fù)雜的工作的。在此基礎(chǔ)上一種很好的優(yōu)化算法逐漸發(fā)展起來。螞蟻是自然界中常見的一種生物,人們對螞蟻的關(guān)注大都是因為“螞蟻搬家,天要下雨”之類的民諺。MacroDorigo2.1蟻群算法原理由于在一定的時間內(nèi),越短的路徑會被越多的螞蟻訪問,因而積累的外激素也就越多,在下一個時間內(nèi)被其他的螞蟻選中的可能性也就越大。這個過程會一直持續(xù)到所有的螞蟻都走最短的那一條路徑為止。正如在關(guān)于蟻群算法的第1篇文章中指出的:蟻群中的螞蟻以“外激素”(為媒介的間接的異步聯(lián)系方式是蟻群算法的最大的特點。螞蟻在行動(尋找食物或者尋找回巢的路徑)中,會在它們經(jīng)過的地方留下一些化學(xué)物質(zhì)(外激素)。后到者留下的外激素會對原有的外激素進(jìn)行加強(qiáng),并如此循環(huán)下去。這樣,經(jīng)過螞蟻越多的路徑,在后到螞蟻的選擇中被選中的可能性就越大(因為殘留的外激素濃度較大的緣故)。這些物質(zhì)能被同一蟻群中后來的螞蟻感受到,并作為一種信號影響后到者的行動(具體表現(xiàn)在后到的螞蟻選擇這些物質(zhì)的路徑的可能性,比選擇沒有這些物質(zhì)的路徑的可能性大得多)2.1蟻群算法原理

在某一個時刻忽然有一個障礙物出現(xiàn)在螞蟻經(jīng)過的路徑中,原有的路徑被切斷,從a點到e點的螞蟻就必須在b點決定應(yīng)該往左還是往右走。而從e點到a點的螞蟻也必須在d點決定選擇哪條路徑。這種決定會受到各條路徑上以往螞蟻留下的外激素濃度(即殘留信息濃度)的影響。如果向右的路徑上的外激素濃度比較大,那么向右的路徑被螞蟻選中的可能性也就比較大一些。但是對障礙出現(xiàn)后第一個到達(dá)b點或d點的螞蟻而言,因為沒有外激素的影響,所以它們選擇向左或者向右的可能性是一樣的。圖中有一條螞蟻經(jīng)過的路徑,我們假設(shè)a點是食物,e點是螞蟻的巢穴。2.1蟻群算法原理若以從a點到e點的螞蟻為例進(jìn)行說明,對于從e點到a點的螞蟻而言過程基本是一樣的。由于路徑bhd比路徑bcd要短,因此選擇bhd路徑的第一只螞蟻要比選擇bcd的第一只螞蟻早到達(dá)d點。此時,從d點向b點看,指向路徑dhb的外激素濃度要比指向路徑dcb的外激素濃度大。因此從下一時刻開始,從e點經(jīng)d點達(dá)到a點的螞蟻選擇dhb路徑比選擇dcb路徑的可能性要大得多。從而使路徑bhd(或dhb)上外激素濃度與路徑bcd(或dcb)上外激素濃度的差變大。而外激素濃度差變大的結(jié)果是選擇路徑bhd(或dhb)路徑的螞蟻進(jìn)一步增加,這又導(dǎo)致外激素濃度差進(jìn)一步加大。人工蟻群具有一定的記憶能力。它能夠記憶已經(jīng)訪問過的節(jié)點;另外,人工蟻群在選擇下一條路徑的時候并不是完全盲目的,而是按一定的算法規(guī)律有意識地尋找最短路徑(如在TSP問題中,可以預(yù)先知道下一個目標(biāo)的距離)。自然界蟻群不具有記憶的能力，它們的選路但憑借外激素，或者道路的殘留信息來選擇，更多地體現(xiàn)正反饋的過程自然界中,蟻群的這種尋找路徑的過程表現(xiàn)為一種正反饋的過程,與人工蟻群的尋優(yōu)算法極為一致。如我們把只具備了簡單功能的工作單元視為”螞蟻”,那么上述尋找路徑的過程可以用于解釋人工蟻群的尋優(yōu)過程人工蟻群和自然界蟻群的相似之處在于,兩者優(yōu)先選擇的都是含“外激素”濃度較大的路徑;這在兩種情況下,較短的路徑上都能聚集比較多的外激素;兩者的工作單元(螞蟻)都是通過在其所經(jīng)過的路徑上留下一定信息的方法進(jìn)行間接的信息傳遞。2.1蟻群算法原理自然界蟻群人工蟻群2.2蟻群算法的實現(xiàn)首先，了解一個問題：TSP。

旅行商問題（TravelingSalesmanProblem）又譯為旅行推銷員問題、貨郎擔(dān)問題，是數(shù)學(xué)領(lǐng)域中著名問題之一。假設(shè)有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。2.2蟻群算法的實現(xiàn)現(xiàn)在用TSP問題的分析,來說明基本蟻群算法是如何實現(xiàn)的。假設(shè)將m只螞蟻放入到n個隨機(jī)選擇的城市中,那么每一只螞蟻每一步的行動是,根據(jù)一定的依據(jù)選擇下一個它還沒有訪問的城市;同時在完成一步(從一個城市到達(dá)另外一個城市)或者一個循環(huán)(完成對所有n個城市的訪問)后,更新所有路徑上的殘留信息濃度。選擇下一個城市的依據(jù)主要是兩點:τij(t)—t時刻連接城市i和j的路徑上殘留信息的濃度,即由算法本身提供的信息;ηij—由城市i轉(zhuǎn)移到城市j的啟發(fā)信息,該啟發(fā)信息是由要解決的問題給出的,由一定的算法實現(xiàn)。在TSP問題中一般取ηij=1/dij(dij表示城市i,j間的距離,ηij在這里可以稱為先驗知識)。2.2蟻群算法的實現(xiàn)那么,t時刻位于城市i的螞蟻k選擇城市j為目標(biāo)城市的概率是:式中：

—能見度，在TSP問題中為城市

轉(zhuǎn)移到

城市

的啟發(fā)信息；

—路徑上殘留信息的重要程

度；

—啟發(fā)信息的重要程度；

—記錄螞蟻

當(dāng)前所走過的城市，稱為禁忌表，

隨著進(jìn)化過程作動態(tài)調(diào)整。2.2蟻群算法的實現(xiàn)為了避免殘留信息過多引起的殘留信息淹沒啟發(fā)信息的問題,在每一只螞蟻完成對所有n個城市的訪問后(也即一個循環(huán)結(jié)