蟻群算法簡述及實現(xiàn)1蟻群算法的原理分析蟻群算法是受自然界中真實蟻群算法的集體覓食行為的啟發(fā)而發(fā)展起來的一種基于群體的模擬進化算法,屬于隨機搜索算法,所以它更恰當(dāng)?shù)拿謶?yīng)該叫“人工蟻群算法”,我們一般簡稱為蟻群算法。M.Dorigo等人充分的利用了蟻群搜索食物的過程與著名的TSP問題的相似性,通過人工模擬蟻群搜索食物的行為來求解TSP問題。螞蟻這種社會性動物,雖然個體行為及其簡單,但是由這些簡單個體所組成的群體卻表現(xiàn)出及其復(fù)雜的行為特征。這是因為螞蟻在尋找食物時,能在其經(jīng)過的路徑上釋放一種叫做信息素的物質(zhì),使得一定范圍內(nèi)的其他螞蟻能夠感覺到這種物質(zhì),且傾向于朝著該物質(zhì)強度高的方向移動。蟻群的集體行為表現(xiàn)為一種正反饋現(xiàn)象,蟻群這種選擇路徑的行為過程稱之為自催化行為。由于其原理是一種正反饋機制,因此也可以把蟻群的行為理解成所謂的增強型學(xué)習(xí)系統(tǒng)(ReinforcementLearningSystem)。引用M.Dorigo所舉的例子來說明蟻群發(fā)現(xiàn)最短路徑的原理和機制,見圖1所示。假設(shè)D和H之間、B和H之間以及B和D之間(通過C)的距離為1,C位于D和B的中央(見圖1(a))。現(xiàn)在我們考慮在等間隔等離散世界時間點(t=0,1,2……)的蟻群系統(tǒng)情況。假設(shè)每單位時間有30只螞蟻從A到B,另三十只螞蟻從E到D,其行走速度都為1(一個單位時間所走距離為1),在行走時,一只螞蟻可在時刻t留下濃度為1的信息素。為簡單起見,設(shè)信息素在時間區(qū)間(t+1，t+2)的中點(t+1.5)時刻瞬時完全揮發(fā)。在t=0時刻無任何信息素,但分別有30只螞蟻在B、30只螞蟻在D等待出發(fā)。它們選擇走哪一條路徑是完全隨機的,因此在兩個節(jié)點上蟻群可各自一分為二,走兩個方向。但在t=1時刻,從A到B的30只螞蟻在通向H的路徑上(見圖1(b))發(fā)現(xiàn)一條濃度為15的信息素,這是由15只從B走向H的先行螞蟻留下來的;而在通向C的路徑上它們可以發(fā)現(xiàn)一條濃度為30的信息素路徑,這是由15只走向BC的路徑的螞蟻所留下的氣息與15只從D經(jīng)C到達B留下的氣息之和(圖1(c))。這時,選擇路徑的概率就有了偏差,向C走的螞蟻數(shù)將是向H走的螞蟻數(shù)的2倍。對于從E到D來的螞蟻也是如此。（a）（b）（c）圖1蟻群路徑搜索實例這個過程一直會持續(xù)到所有的螞蟻最終都選擇了最短的路徑為止。這樣,我們就可以理解蟻群算法的基本思想:如果在給定點,一只螞蟻要在不同的路徑中選擇,那么,那些被先行螞蟻大量選擇的路徑(也就是信息素留存較濃的路徑)被選中的概率就更大,較多的信息素意味著較短的路徑,也就意味著較好的問題回答。2人工蟻群算法描述蟻群算法可以看作為一種基于解空間參數(shù)化概率分布模型(ParameterizedProbabilisticModel)的搜索算法框架(Model-basedsearchalgorithms)。在蟻群算法中,解空間參數(shù)化概率,模型的參數(shù)就是信息素,因而這種參數(shù)化概率分布模型就是信息素模型。在基于模型的搜索算法框架中,可行解通過在一個解空間參數(shù)化概率分布模型上的搜索產(chǎn)生,此模型的參數(shù)用以前產(chǎn)生的解來更新,使得在新模型上的搜索能夠集中在高質(zhì)量的解搜索空間內(nèi)。這種方法的有效性建立在高質(zhì)量的解總是包含好的解構(gòu)成元素的假設(shè)前提下。通過學(xué)習(xí)這種解構(gòu)成元素對解的質(zhì)量的影響有助于找到一種機制,并通過解構(gòu)成元素的最佳組合來構(gòu)造出高質(zhì)量的解。一般來說,一個記憶模型的搜索算法通常使用以下兩步迭代來解決優(yōu)化問題:1)可行解通過在解空間參數(shù)化概率分布模型上的搜索產(chǎn)生。2)用搜索產(chǎn)生的解來更新參數(shù)化概率模型,即更新解空間參數(shù)化概率分布的參數(shù),使得在新模型上的參數(shù)搜索能夠集中在高質(zhì)量的解搜索空間內(nèi)。在蟻群算法中,基于信息素的解空間參數(shù)化概率模型(信息素模型)以解構(gòu)造圖的形式給出。在解構(gòu)造圖上,定義了一種作為隨機搜索機制的人工蟻群,螞蟻通過一種分布在解構(gòu)造圖上被稱為信息素的局部信息的指引,在解構(gòu)造圖上移動,從而逐步的構(gòu)造出問題的可行。信息素與解構(gòu)造圖上的節(jié)點或弧相關(guān)聯(lián),作為解空間參數(shù)化概率分布模型的參數(shù)。由于TSP問題可以直接的映射為解構(gòu)造圖(城市為節(jié)點,城市間的路徑為弧,信息素分布在弧上),加之TSP問題也是個NP難題,所以,蟻群算法的大部分應(yīng)用都集中在TSP問題上。一般而言,用于求解TSP問題、生產(chǎn)調(diào)度問題等優(yōu)化問題的蟻群算法都遵循下面的統(tǒng)一算法框架。算法1：求解組合優(yōu)化問題的蟻群算法設(shè)置參數(shù),初始化信息素蹤跡While(不滿足條件時)dofor蟻群中的每只螞蟻for每個解構(gòu)造步(直到構(gòu)造出完整的可行解)1)螞蟻按照信息素及啟發(fā)式信息的指引構(gòu)造一步問題的解;2)進行信息素局部更新。(可選)endforendfor1)以某些已獲得的解為起點進行鄰域(局部)搜索;(可選)2)根據(jù)某些已獲得的解的質(zhì)量進行全局信息素更新。endwhileend在算法1中,螞蟻逐步的構(gòu)造問題的可行解,在一步解的構(gòu)造過程中,螞蟻以概率方式選擇信息素強且啟發(fā)式因子高的弧到達下一個節(jié)點,直到不能繼續(xù)移動為止。此時螞蟻所走過的路徑對應(yīng)求解問題的一個可行解。局部信息素更新針對螞蟻當(dāng)前走過的一步路徑上的信息素進行,全局信息素更新是在所有螞蟻找到可行解之后,根據(jù)發(fā)現(xiàn)解的質(zhì)量或當(dāng)前算法找到的最好解對路徑上的信息素進行更新。3蟻群算法與其他搜索算法比較3.1蟻群算法與進化算法比較近年來,遺傳算法(GA)、進化規(guī)劃(EvolutionaryPlanning)、進化策略(EvolutionaryStrategies)在理論和應(yīng)用上發(fā)展迅速、效果顯著并逐漸走向了融合,形成了一種新穎的模擬進所走過的路徑便是TSP問題的一個可行解。式(4.1)中的ηij通常取城市i和城市j之間距離的倒數(shù)。α和β分別表示信息素和啟發(fā)式因子的相對重要程度。當(dāng)所有螞蟻完成一次周游以后,各路徑上的信息素根據(jù)下式更新。τijt+n=ρ?τij=其中ρ(0<ρ<l)表示信息殘留系數(shù),用1-ρ表示信息素的揮發(fā)系數(shù)。關(guān)于?τijk的計算方法,M.Dorigo曾給出三種不同的實現(xiàn)方法,分別對應(yīng)三種不同的螞蟻系統(tǒng)模型ant-cyclesystem、ant-densitysystem以及ant-quantitysystem在ant-cyclesystem模型中：?τijk=在ant-densitysystem模型中：?τijk=在ant-quantitysystem模型中：?τijk=上面公式中,Q為一正常數(shù),表示螞蟻循環(huán)一周或者一個過程在經(jīng)過的路徑上所釋放的信息素總量。Lk表示第k只螞蟻在本次循環(huán)中所經(jīng)過的路徑的長度。以上三種模型的區(qū)別在于:第一種模型利用的是蟻群的整體信息,即走完一個循環(huán)以后才進行殘留信息量的全局調(diào)整;而后兩種模型中螞蟻每走一步(即從時間t到t+1)都要更新殘留的信息量,而不是等到所有的螞蟻完成對所有的城市訪問以后。4.3螞蟻系統(tǒng)模型的實現(xiàn)從上面的螞蟻系統(tǒng)模型來看,其尋找最優(yōu)解的過程實際上是一個有限的遞推過程,因而也適合在計算機上實現(xiàn)。AS算法的實現(xiàn)可用以下的偽代碼來描述:算法2：AS算法1.初始化設(shè)t=0；{t為計時器}Nc=0；{Nc為迭代次數(shù)計算器}τij（t）=C；{τij（t）為每條路徑（i，j）設(shè)的信息素量的初值Δτij=0；{信息素增量的初值設(shè)為0}ηij由某種啟發(fā)式算法確定；{在TSP中，ηij=1/dij}tabuk=Φ;{在初始階段，禁忌表為空}將m只螞蟻隨機地置于n個節(jié)點上；設(shè)置s=1；{s為禁忌表索引，將各螞蟻的初始城市置于當(dāng)前禁忌表中}fork=1tondofork=1tobi（t）dotabuk（s）=i；2.重復(fù)直至禁忌表滿為止{這一步要重復(fù)（n-1）次}設(shè)置s=s+1；fori=1tondofork=1tobi（t）do以概率Pijkt將螞蟻k移動到城市j；將剛剛選擇到的城市j加入到禁忌表中在ant-cyclesystem模型中：按照（4.4）式計算?在ant-densitysystem模型中：按照（4.5）式計算?在ant-quantitysystem模型中：按照（4.6）式計算?3.記錄到目前為止的最短路徑ifNc<Ncmax則清