蟻群算法簡述和實(shí)現(xiàn)

1、WORD格式可編輯蟻群算法簡述及實(shí)現(xiàn)1蟻群算法的原理分析蟻群算法是受自然界中真實(shí)蟻群算法的集體覓食行為的啟發(fā)而發(fā)展起來的一種基于群 體的模擬進(jìn)化算法，屬于隨機(jī)搜索算法，所以它更恰當(dāng)?shù)拿謶?yīng)該叫“人工蟻群算法”，我們 一般簡稱為蟻群算法。M.Dorigo等人充分的利用了蟻群搜索食物的過程與著名的TSP問題的相似性，通過人工模擬蟻群搜索食物的行為來求解TSP問題。螞蟻這種社會(huì)性動(dòng)物，雖然個(gè)體行為及其簡單，但是由這些簡單個(gè)體所組成的群體卻表 現(xiàn)出及其復(fù)雜的行為特征。這是因?yàn)槲浵佋趯ふ沂澄飼r(shí)，能在其經(jīng)過的路徑上釋放一種叫做信息素白物質(zhì)，使得一定范圍內(nèi)的其他螞蟻能夠感覺到這種物質(zhì)，且傾向于朝著該物質(zhì)強(qiáng)度

2、高的方向移動(dòng)。蟻群的集體行為表現(xiàn)為一種正反饋現(xiàn)象，蟻群這種選擇路徑的行為過程稱之為自催化行為。由于其原理是一種正反饋機(jī)制，因此也可以把蟻群的行為理解成所謂的增強(qiáng)型學(xué)習(xí)系統(tǒng) (Reinforcement Learning System) 。引用M.Dorigo所舉的例子來說明蟻群發(fā)現(xiàn)最短路徑的原理和機(jī)制，見圖1所示。假設(shè)D和H之間、B和H之間以及B和D之間(通過C)的距離為1,C位于D和B的中央(見圖1 (a)。 現(xiàn)在我們考慮在等間隔等離散世界時(shí)間點(diǎn)(t=0,1,2)的蟻群系統(tǒng)情況。假設(shè)每單位時(shí)間有30只螞蟻從A到B,另三十只螞蟻從 E到D,其行走速度都為1( 一個(gè)單位時(shí)間所走距離為 1),在行

3、走時(shí)，一只螞蟻可在時(shí)刻t留下濃度為1的信息素。為簡單起見，設(shè)信息素在時(shí)間區(qū) 間(t+1 , t+2)的中點(diǎn)(t+1.5)時(shí)刻瞬時(shí)完全揮發(fā)。在t=0時(shí)刻無任何信息素，但分別有30只螞蟻在B、30只螞蟻在D等待出發(fā)。它們選擇走哪一條路徑是完全隨機(jī)的，因此在兩個(gè)節(jié)點(diǎn)上蟻群可各自一分為二，走兩個(gè)方向。但在t=1時(shí)刻，從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到達(dá)B留下的氣息之和(圖1 (c)。這時(shí)，選

4、擇路徑的 概率就有了偏差，向C走的螞蟻數(shù)將是向 H走的螞蟻數(shù)的2倍。對于從E到D來的螞蟻也是 如此。II收60?；鸸、H孰15Hif(b)圖1蟻群路徑搜索實(shí)例奴砂15KirEk1效和30Tift 10J： b這個(gè)過程一直會(huì)持續(xù)到所有的螞蟻?zhàn)罱K都選擇了最短的路徑為止。這樣，我們就可以理解蟻群算法的基本思想：如果在給定點(diǎn)，一只螞蟻要在不同的路徑中專業(yè)知識分享WORD格式可編輯選才i ,那么，那些被先行螞蟻大量選擇的路徑（也就是信息素留存較濃的路徑）被選中的概率就更大，較多的信息素意味著較短的路徑，也就意味著較好的問題回答。2人工蟻群算法描述蟻群算法可以看作為一種基于解空間參數(shù)化概率分布模型（Pa

5、rameterized Probabilistic Model）的搜索算法框架 （Model-based search algorithms）。在蟻群算法中, 解空間參數(shù)化概率，模型的參數(shù)就是信息素，因而這種參數(shù)化概率分布模型就是信息素模型。 在基于模型的搜索算法框架中，可行解通過在一個(gè)解空間參數(shù)化概率分布模型上的搜索產(chǎn)生此模型的參數(shù)用以前產(chǎn)生的解來更新，使得在新模型上的搜索能夠集中在高質(zhì)量的解搜索空 間內(nèi)。這種方法的有效性建立在高質(zhì)量的解總是包含好的解構(gòu)成元素的假設(shè)前提下。通過學(xué)習(xí)這種解構(gòu)成元素對解的質(zhì)量的影響有助于找到一種機(jī)制，并通過解構(gòu)成元素的最佳組合來構(gòu)造出高質(zhì)量的解。一般來說，一個(gè)記

6、憶模型的搜索算法通常使用以下兩步迭代來解決優(yōu)化 問題：1）可行解通過在解空間參數(shù)化概率分布模型上的搜索產(chǎn)生。2）用搜索產(chǎn)生的解來更新參數(shù)化概率模型，即更新解空間參數(shù)化概率分布的參數(shù)，使得在新模型上的參數(shù)搜索能夠集中在高質(zhì)量的解搜索空間內(nèi)。在蟻群算法中，基于信息素的解空間參數(shù)化概率模型（信息素模型）以解構(gòu)造圖的形式給出。在解構(gòu)造圖上，定義了一種作為隨機(jī)搜索機(jī)制的人工蟻群，螞蟻通過一種分布在解構(gòu)造圖上被稱為信息素的局部信息的指引，在解構(gòu)造圖上移動(dòng)，從而逐步的構(gòu)造出問題的可行。信息 素與解構(gòu)造圖上的節(jié)點(diǎn)或弧相關(guān)聯(lián)，作為解空間參數(shù)化概率分布模型的參數(shù)。由于TSP問題可以直接的映射為解構(gòu)造圖（城市為節(jié)點(diǎn)

7、，城市間的路徑為弧，信息素分布在弧上）,加之TSP問題也是個(gè)NP難題，所以，蟻群算法的大部分應(yīng)用都集中在TSP問題上。一般而言，用于求解TSP問題、生產(chǎn)調(diào)度問題等優(yōu)化問題的蟻群算法都遵循下面的統(tǒng)一算法 框架。算法1:求解組合優(yōu)化問題的蟻群算法設(shè)置參數(shù)，初始化信息素蹤跡While（不滿足條件時(shí)）dofor蟻群中的每只螞蟻for每個(gè)解構(gòu)造步（直到構(gòu)造出完整的可行解）1）螞蟻按照信息素及啟發(fā)式信息的指引構(gòu)造一步問題的解；2）進(jìn)行信息素局部更新。（可選） endforendfor1）以某些已獲得的解為起點(diǎn)進(jìn)行鄰域（局部）搜索;（可選）2）根據(jù)某些已獲得的解的質(zhì)量進(jìn)行全局信息素更新。 endwhilee

8、nd在算法1中，螞蟻逐步的構(gòu)造問題的可行解，在一步解的構(gòu)造過程中，螞蟻以概率方式選擇信息素強(qiáng)且啟發(fā)式因子高的弧到達(dá)下一個(gè)節(jié)點(diǎn)，直到不能繼續(xù)移動(dòng)為止。此時(shí)螞蟻所走過的路徑對應(yīng)求解問題的一個(gè)可行解。局部信息素更新針對螞蟻當(dāng)前走過的一步路徑上的信息 素進(jìn)行，全局信息素更新是在所有螞蟻找到可行解之后，根據(jù)發(fā)現(xiàn)解的質(zhì)量或當(dāng)前算法找到 的最好解對路徑上的信息素進(jìn)行更新。3蟻群算法與其他搜索算法比較專業(yè)知識分享WORD格式可編輯蟻群算法與進(jìn)化算法比較近年來,遺傳算法(GA)、進(jìn)化規(guī)劃(Evolutionary Planning) 、進(jìn)化策略(Evolutionary Strategies)在理論和應(yīng)用上發(fā)展

9、迅速、效果顯著并逐漸走向了融合，形成了一種新穎的模擬 進(jìn)化的計(jì)算理論，統(tǒng)稱為進(jìn)化計(jì)算(Evolutionary Computation) 。因此我們可以用進(jìn)化計(jì)算 作為代表與蟻群算法進(jìn)行比較 ，從另一個(gè)角度來認(rèn)識蟻群算法 ，加深對蟻群算法的理解。蟻群算法與進(jìn)化計(jì)算的相似之處有兩點(diǎn)：首先，兩種算法均采用群體表示問題的解；其次,新群體通過包含在群體中與問題相關(guān)的知識來生成。兩者的主要區(qū)別在于進(jìn)化計(jì)算中所有問題的的知識都包含在當(dāng)前群體中，而蟻群算法中代表過去所學(xué)的知識保存在信息素的蹤跡中。蟻群算法與模擬退火算法比較從模擬退火算法的搜索策略可以看出蟻群算法和模擬退火算法(SA)從本質(zhì)上來講是一致的。S

10、A對某個(gè)“固體的” 一個(gè)微觀狀態(tài)i計(jì)算其能量E的過程與螞蟻的一次“周游” 一樣 ，都是對解空間的一次采樣；“退火”與“分泌信息素”都是利用積累信息來增強(qiáng)對子空間的 搜索；而a Metropolis 準(zhǔn)則”和“隨機(jī)狀態(tài)轉(zhuǎn)移規(guī)則”類似 ，都是使算法能夠跳出局部最優(yōu)，在一定范圍內(nèi)接受惡化解，搜索新的子空間。因此,SA已經(jīng)非常成熟的收斂性研究對分析設(shè)置螞蟻規(guī)模參數(shù)和信息素分布策略對最終解質(zhì)量的影響有很大的借鑒意義。對于SA的收斂性分析一般分兩種情況，齊次Markov鏈和非齊次Markov鏈。齊次Markov鏈的分析結(jié)果告訴我們，在任意溫度t,SA都達(dá)到平衡分布 的情況下，當(dāng)t-0時(shí),SA將收斂于全局最

11、優(yōu)。也就是說，在任意溫度t,SA都要遍歷整個(gè)解空間。那么，如果我們保留sA采樣后的當(dāng)前全局最優(yōu)解，則即使在任何溫度t,SA都會(huì)收斂于全 局最優(yōu)。換句話說，對于蟻群算法，如果螞蟻數(shù)量(規(guī)模)足夠多，能夠保證對解空間的遍歷，那么即使不用信息素，也能保證全局收斂。不過這種方法顯然就是一種盲目隨機(jī)搜索，沒有任何實(shí)際的應(yīng)用價(jià)值。對于非其次 Markov鏈的SA,即在某個(gè)固定溫度t,采樣次數(shù)有限，而t將無限趨近于0 的情況下，結(jié)論告訴我們當(dāng)控制參數(shù)序列滿足一定條件時(shí),SA才收斂于整體最優(yōu)解集。其更直接的表述方式是：控制參數(shù)t的衰減量與在溫度t下的采樣數(shù)之間存在一種均衡：t的衰減量越大，則在溫度藝下的采樣數(shù)

12、就必須越多；反之，若t的衰減量緩慢，則在每個(gè)溫度下 SA只需進(jìn)行少量采樣。那么。從蟻群算法的角度可以看到 ：因?yàn)槲浵伒囊?guī)模實(shí)際上影響的只是信息素更新的頻 率，所以當(dāng)規(guī)模設(shè)置較大時(shí)，每次更新信息素時(shí)，可以以較快的速度拉大不同狀態(tài)上的信息素 差距；當(dāng)規(guī)模較小時(shí)，每次只對信息素進(jìn)行少量更新 ，以免算法早熟。由此可見，對蟻群算法的參數(shù)設(shè)置可以直接利用SA中對“冷卻進(jìn)度表”的研究成果。此外，既然兩者在本質(zhì)上一致，那么SA的一些改進(jìn)和變異可以直接用在蟻群算法上以改 進(jìn)其性能。蟻群算法與神經(jīng)網(wǎng)絡(luò)比較由許多并發(fā)、局部交互的單元(人工螞蟻)組成的蟻群，可以看成是一種“連接”系統(tǒng)。連接系統(tǒng)最具代表性的例子是神經(jīng)網(wǎng)

13、絡(luò)(Neural Network, 簡稱NN)。從結(jié)本上看，蟻群算法與通常的神經(jīng)網(wǎng)絡(luò)具有類似的并行機(jī)制。螞蟻訪問過的每一個(gè)狀態(tài)i對應(yīng)于神經(jīng)網(wǎng)絡(luò)中的神經(jīng)元i,與問題相關(guān)的狀態(tài)i的鄰域結(jié)構(gòu)與神經(jīng)元i中的突觸連接相對應(yīng)。螞蟻本身可 以看成是通過神經(jīng)網(wǎng)絡(luò)的并發(fā)輸入信號，以修改突觸與神經(jīng)元之間的連接強(qiáng)度。信號經(jīng)過隨機(jī)轉(zhuǎn)換函數(shù)的局部反傳，使用的突觸越多，兩個(gè)神經(jīng)元之間的連接越強(qiáng)。蟻群算法中的學(xué)習(xí)規(guī)專業(yè)知識分享WORD格式可編輯則可以解釋為一種后天性的規(guī)則，即質(zhì)量較好的解包含連接信號的強(qiáng)度高于質(zhì)量較差的解。4基本蟻群算法及其實(shí)現(xiàn)引言蟻群在覓食過程中總能找到蟻巢和食物源之間的最短路徑。受螞蟻的這種行為啟發(fā)，意

14、大利學(xué)者M(jìn).Dorigo、V.Maniezzo以及A.Colorni首先提出了一種新型的隨機(jī)搜索模擬進(jìn)化 算法一螞蟻系統(tǒng)(Ant System,簡稱As)。AS算法是第一個(gè)蟻群算法的模型，被稱為基本蟻群算法。AS算法首先被用來求解 TSP問題，并取得了巨大成功。實(shí)驗(yàn)結(jié)果顯示AS算法具有很強(qiáng)的發(fā)現(xiàn)較好解的能力，但同時(shí)也存在一些缺點(diǎn)，如收斂速度較慢、易出現(xiàn)停滯現(xiàn)象等等。 針 對AS算法的不足之處，許多學(xué)者對其進(jìn)行了深入的研究，提出了一些改進(jìn)的蟻群算法，如帶精英策略的螞蟻系統(tǒng)(Ant System With elitist strategy,簡稱 ASlgt、蟻群系統(tǒng)(AntColorni Syst

15、em,簡稱 ACS)、基于優(yōu)化排序的螞蟻系統(tǒng)(Rank-Based Version of Ant System,簡稱ASank)、最大-最小螞蟻系統(tǒng)(Max-Min Ant System, 簡稱MMA硯及最優(yōu)-最差螞蟻系統(tǒng) (Best-Worst Ant System, 簡稱 BWAS等等。螞蟻系統(tǒng)的模型描述為了說明螞蟻系統(tǒng)的模型，首先引入TSP問題。一般地來說，旅行商問題(Traveling Salesman Problem, 簡稱TSP問題)可以描述如下： 設(shè)C=。,c2,c n為n個(gè)城市的集合，L= L巧5、cCC 是c中元素兩兩連接的集合，G=(C,L)是一個(gè)圖，已知各城市之間的距離，

16、TSP問題的求解目的是從 G中找出長度最短的 Hamiltonian 圈，即找出對 C=c ,c2,c n中n個(gè)城市訪問且只訪問一次的最短的一條封閉 曲線。TSP問題分為對稱型和非對稱型。在對稱型TSP問題中，有du =d ,。，c C C1,2 ,n, dj是l ij的長度；在非對稱型TSP問題中，至少存在一對0 , cj C C,使dij w打。為了模擬實(shí)際螞蟻的行為，我們首先引入如下記號： n蟻群中螞蟻的數(shù)量；b (t) t時(shí)刻位于城市i的螞蟻數(shù)，m= 1 ()；dij 一兩城市i和j之間的距離；t ij 一邊(i,j)的能見度，反映由城市i轉(zhuǎn)移到城市j的啟發(fā)程度，這個(gè)量在螞蟻的運(yùn)行中

17、不改變；ij (t) t時(shí)刻邊(i,j)上的信息素量;”一本次迭代中邊ij上的信息素增量；(t)一在t時(shí)刻螞蟻k從城市i轉(zhuǎn)移到城市j的概率； 每只螞蟻都具有以下特性：(1)完成一次循環(huán)后，螞蟻在其訪問過的每條邊上留下相應(yīng)的信息素；(2)螞蟻依據(jù)概率選擇下一個(gè)將要訪問的城市，這個(gè)概率是兩城市間距離及連接兩個(gè)城市的邊上信息量的函數(shù)；(3)為了滿足問題的約束條件，在完成一次循環(huán)之前，不允許螞蟻選擇己經(jīng)訪問過的城市 該過程由螞蟻的禁忌表來控制。設(shè)tabuk為螞蟻k的禁忌表，則螞蟻在經(jīng)過城市i以后，就將城市i加入到自己的禁忌表 tabuk、中，表示下次不能再選擇城市 i。用tabuk(s)表示禁忌表 中

18、第s個(gè)元素，也即螞蟻?zhàn)哌^的第 s個(gè)城市。于是AS算法可以表述如下：在算法的初始時(shí)刻，將m只螞蟻隨機(jī)的放到 n座城市，同時(shí)， 將每只螞蟻的禁忌表的第一個(gè)元素設(shè)置為當(dāng)前它所在的城市。初始時(shí)刻，各條路徑上的信息專業(yè)知識分享WORD格式可編輯素量相等，設(shè)ij (0) =C(C為一較小的常數(shù))。然后每只螞蟻按照各條路徑上的信息素量和啟,螞蟻系統(tǒng)所用的狀態(tài)轉(zhuǎn)移規(guī)則稱為隨機(jī) 的轉(zhuǎn)移概率 (t)為：(4.1)發(fā)式信息(兩城市間的距離)獨(dú)立的選擇下一座城市 比例規(guī)則。在t時(shí)刻，螞蟻k在城市i選擇城市j()()()，0,其中，allowed k =1,2，,ntabuk表示螞蟻下一步允許選擇的城市。列表tabuk記錄了螞蟻k當(dāng)前走過的城市。當(dāng)所有n座城市都加入到tabuk中時(shí)，螞蟻k便完成了一次周游，此時(shí) 螞蟻k所走過的路徑便是 TSP問題的一個(gè)可行解。式(4.1)中的 中j通常取城市i和城市j 之間距離的倒數(shù)?！焙?分別表示信息素和啟發(fā)式因子的相對重要程度。當(dāng)所有螞蟻完成 一次周游以后，各路徑上的信息素根據(jù)下式更新。(4.2)1(4.3)其中(0 (t) do以概率