蟻群算法及算例課件

1、蟻 群 優(yōu) 化 算 法（ACO算法）一、概述二、螞蟻系統(tǒng)（AS）三、算例四、改進(jìn)的ACO算法一、概述（一）算法背景蟻群的自組織行為特征 1、高度結(jié)構(gòu)化的組織雖然螞蟻的個體行為極其簡單，但由個體組成的蟻群卻構(gòu)成高度結(jié)構(gòu)化的社會組織，螞蟻社會的成員有分工，有相互的通信和信息傳遞。 2、自然優(yōu)化蟻群在覓食過程中，在沒有任何提示下總能找到從蟻巢到食物源之間的最短路徑；當(dāng)經(jīng)過的路線上出現(xiàn)障礙物時，還能迅速找到新的最優(yōu)路徑。 3、信息正反饋螞蟻在尋找食物時，在其經(jīng)過的路徑上釋放信息素（外激素）。螞蟻基本沒有視覺，但能在小范圍內(nèi)察覺同類散發(fā)的信息素的軌跡，由此來決定何去何從，并傾向于朝著信息素強(qiáng)度高的方向移

2、動。 4、自催化行為某條路徑上走過的螞蟻越多，留下的信息素也越多（隨時間蒸發(fā)一部分），后來螞蟻選擇該路徑的概率也越高。 （二）算法的產(chǎn)生與發(fā)展 1、產(chǎn)生受蟻群覓食行為啟發(fā)，意大利學(xué)者M(jìn).Dorigo于1991年在其博士論文中首次系統(tǒng)地提出一種基于螞蟻種群的新型智能優(yōu)化算法“螞蟻系統(tǒng)（Ant system,簡稱AS）”，并用該法求解旅行商問題，獲得了較好的效果。 2、發(fā)展后來，提出者及許多研究者對該算法作了各種改進(jìn)，將其應(yīng)用于更為廣泛的領(lǐng)域，如圖著色問題、二次分配問題、工件排序問題、車輛路徑問題、車間作業(yè)調(diào)度問題、網(wǎng)絡(luò)路由問題、大規(guī)模集成電路設(shè)計等。近些年來，M.Dorigo等人把螞蟻算法進(jìn)一步

3、發(fā)展成一種通用的優(yōu)化技術(shù)“蟻群優(yōu)化（Ant Colony Optimization,簡稱ACO）”，并將所有符合ACO框架的算法稱為“蟻群優(yōu)化算法（ACO algorithm）”。 3、展望初步的研究結(jié)果已顯示出ACO算法在求解復(fù)雜優(yōu)化問題，特別是離散優(yōu)化問題方面的優(yōu)越性。雖然嚴(yán)格的理論基礎(chǔ)尚未奠定，但從當(dāng)前的應(yīng)用效果來看，此算法具有光明的發(fā)展前景。（三）特點(diǎn)是一種基于多主體的智能算法，不是單個螞蟻行動，而是多個螞蟻同時搜索，具有分布式的協(xié)同優(yōu)化機(jī)制。本質(zhì)上屬于隨機(jī)搜索算法（概率算法），具有概率搜索的特征。是一種全局搜索算法，能夠有效地避免局部最優(yōu)。（四）優(yōu)點(diǎn)求解問題的快速性由正反饋機(jī)制決定；

4、全局優(yōu)化性由分布式計算決定，避免蟻群在尋優(yōu)空間中過早收斂；有限時間內(nèi)答案的合理性由貪婪式搜索模式?jīng)Q定，使能在搜索過程的早期就找到可以接受的較好解。 4、每只螞蟻只能走合法路線（經(jīng)過每個城市1次且僅1次），為此設(shè)置禁忌表來控制。 5、所有螞蟻都搜索完一次就是迭代一次，每迭代一次就對所有的邊做一次信息素更新，原來的螞蟻死掉，新的螞蟻進(jìn)行新一輪搜索。 6、更新信息素包括原有信息素的蒸發(fā)和經(jīng)過的路徑上信息素的增加。 7、達(dá)到預(yù)定的迭代步數(shù)，或出現(xiàn)停滯現(xiàn)象（所有螞蟻都選擇同樣的路徑，解不再變化），則算法結(jié)束，以當(dāng)前最優(yōu)解作為問題的最優(yōu)解。（二）參數(shù)含義及符號螞蟻數(shù)量；螞蟻編號；時刻；城市數(shù)；城市 之間的

5、距離；啟發(fā)式因子（能見度），反映螞蟻由 城市 轉(zhuǎn)移到城市 的啟發(fā)程度；邊 上的信息素量；（三）計算公式1、轉(zhuǎn)移概率 計算公式：螞蟻 下一步允許選擇的城市集合。信息素的相對重要程度；啟發(fā)式因子的相對重要程度；2、啟發(fā)式因子計算公式：3、信息素計算公式正常數(shù)，螞蟻 在本次周游中所走路徑的長度。 當(dāng)所有螞蟻完成1次周游后，各路徑上的信息素為：開始時，令（四）算法步驟1、初始化參數(shù)：開始時每條邊的信息素量都相等。2、將各只螞蟻放置各頂點(diǎn)，禁忌表為對應(yīng)的頂點(diǎn)。3、取1只螞蟻，計算轉(zhuǎn)移概率 ，按輪盤賭的方式 選擇下一個頂點(diǎn)，更新禁忌表，再計算概率，再選 擇頂點(diǎn)，再更新禁忌表，直至遍歷所有頂點(diǎn)1次。4、計算

6、該只螞蟻留在各邊的信息素量 ，該螞蟻 死去。5、重復(fù)34，直至 只螞蟻都周游完畢。6、計算各邊的信息素增量 和信息素量 。7、記錄本次迭代的路徑，更新當(dāng)前的最優(yōu)路徑，清空 禁忌表。8、判斷是否達(dá)到預(yù)定的迭代步數(shù)，或者是否出現(xiàn)停滯 現(xiàn)象。若是，算法結(jié)束，輸出當(dāng)前最優(yōu)路徑；否， 轉(zhuǎn)2，進(jìn)行下一次迭代。三、算例5個點(diǎn)的貨郎擔(dān)問題 參數(shù)設(shè)置：最優(yōu)解保留策略螞蟻系統(tǒng)（帶精英策略的螞蟻系統(tǒng)ASelite） 蟻群系統(tǒng)（ACS） 最大-最小螞蟻系統(tǒng)（MMAS） 基于優(yōu)化排序的螞蟻系統(tǒng)（ASrank）最優(yōu)最差螞蟻系統(tǒng)（BWAS） 一種新的自適應(yīng)蟻群算法（AACA） 基于混合行為的蟻群算法（HBACA） 改 進(jìn)

7、的螞蟻算法四、改進(jìn)的蟻群優(yōu)化算法特點(diǎn)、狀態(tài)轉(zhuǎn)移規(guī)則偽隨機(jī)比率規(guī)則 設(shè) 為常數(shù)， 為隨機(jī)數(shù)，如果 ，則螞蟻轉(zhuǎn)移的下一座城市是使 取最大值的城市；若 ，仍按轉(zhuǎn)移概率確定。、全局更新規(guī)則只有精英螞蟻才允許釋放 信息素，即只有全局最優(yōu)解所屬的邊才增加 信息素。 、局部更新規(guī)則螞蟻每次從城市 轉(zhuǎn)移到 城市 后，邊 上的信息素適當(dāng)減少。 一般， 取值較大。（二）蟻群系統(tǒng) 規(guī)則和都是為了使搜索過程更具有指導(dǎo)性，即使螞蟻的搜索主要集中在當(dāng)前找出的最好解鄰域內(nèi)。規(guī)則則是為了使已選的邊對后來的螞蟻具有較小的影響力，以避免螞蟻收斂到同一路徑。（三）最大最小螞蟻系統(tǒng) 關(guān)于 的取值，沒有確定的方法，有的書例子中取為0.

8、01，10；有的書提出一個在最大值給定的情況下計算最小值的公式。1、每次迭代后，只對最優(yōu)解所屬路徑上的信 息素更新。特點(diǎn)2、對每條邊的信息素量限制在范圍 內(nèi)，目的是防止某一條路徑上的信息素量遠(yuǎn) 大于其余路徑，避免過早收斂于局部最優(yōu)解。 （四）基于優(yōu)化排序的螞蟻系統(tǒng)特點(diǎn)：每次迭代完成后，螞蟻所經(jīng)路徑由小到大排序，并根據(jù)路徑長度賦予不同的權(quán)重，路徑越短權(quán)重越大。信息素更新時對 考慮權(quán)重的影響。 特點(diǎn)：主要是修改了ACS中的全局更新公式，增加 對最差螞蟻路徑信息素的更新，對最差解進(jìn) 行削弱，使信息素差異進(jìn)一步增大。 （五）最優(yōu)最差螞蟻系統(tǒng)（六）一種新的自適應(yīng)蟻群算法特點(diǎn)：將ACS中的狀態(tài)轉(zhuǎn)移規(guī)則改為

9、自適應(yīng)偽隨機(jī) 比率規(guī)則，動態(tài)調(diào)整轉(zhuǎn)移概率，以避免出現(xiàn) 停滯現(xiàn)象。說明：在ACS的狀態(tài)轉(zhuǎn)移公式中， 是給定的常數(shù)；在AACA中， 是隨平均節(jié)點(diǎn)分支數(shù)ANB而變化的變量。ANB較大，意味著下一步可選的城市較多， 也變大，表示選擇信息素和距離最好的邊的可能性增大；反之減小。（七）基于混合行為的蟻群算法特點(diǎn)：按螞蟻的行為特征將螞蟻分成4類，稱為4個子蟻群，各子蟻群按各自的轉(zhuǎn)移規(guī)則行動，搜索路徑，每迭代一次，更新當(dāng)前最優(yōu)解，按最優(yōu)路徑長度更新各條邊上的信息素，如此直至算法結(jié)束。 螞蟻行為螞蟻在前進(jìn)過程中，用以決定其下一步移動到哪個狀態(tài)的規(guī)則集合。 1、螞蟻以隨機(jī)方式選擇下一步要到達(dá)的狀態(tài)。2、螞蟻以貪婪

10、方式選擇下一步要到達(dá)的狀態(tài)。3、螞蟻按信息素強(qiáng)度選擇下一步要到達(dá)的狀態(tài)。4、螞蟻按信息素強(qiáng)度和城市間距離選擇下一步要到達(dá)的狀態(tài) 。螞蟻行為五、蟻群算法與遺傳、模擬退火算法的比較實(shí)驗(yàn)結(jié)果表明：1、蟻群算法所找出的解的質(zhì)量最高，遺傳算法次之，模擬退火算法最低。2、蟻群算法的收斂速度最快，遺傳算法次之，模擬退火算法最慢。蟻群算法之所以能夠快速收斂到全局最優(yōu)解，是因?yàn)樵撍惴ǖ膫€體之間不斷進(jìn)行信息交流和傳遞。單個個體容易收斂于局部最優(yōu)，多個個體通過合作可以很快地收斂于解空間的最優(yōu)解的附近。討 論1、對已學(xué)過的算法作出某種改進(jìn)。2、介紹自學(xué)的一種新的算法。3、查閱文獻(xiàn)，介紹某算法在某領(lǐng)域的一個應(yīng)用。4、應(yīng)

11、用某算法解決一個實(shí)際問題。正常數(shù)，螞蟻 在本次周游中所走路徑的長度。 當(dāng)所有螞蟻完成1次周游后，各路徑上的信息素為：開始時，令ktitabuk10AABCDE22220.470.0950.1180.315119.12.117BA,BCDE2220.5930.2370.1691.686CA,B,CDE220.670.331.0DA,B,C,DE21.01.0EA,B,C,D,E空集-ktitabuk30CCABDE22220.0690.620.2070.103911.13.222BC,BADE2220.7450.1490.1062.686AC,B,ADE220.2730.7270.917EC,B

12、,A,ED21.02.0DC,B,A,E,D空集-ktitabuk40DDABCE22220.0840.2110.2870.422119.12.367ED,EABC2220.5930.1690.2371.686AD,E,ABC220.830.171.2BD,E,A,BC21.01.0CD,E,A,B,C空集-ktitabuk50EEABCD22220.2710.0780.1090.543911.13.686DE,DABC2220.1460.3660.4881.367CE,D,CAB220.10.92.222BE,D,C,BA21.02.0AE,D,C,B,A空集-ABCDEA09.1+9.1+

13、1=19.21111.1+11.1+11.1+1=34.3B11.1+11.1+11.1+1=34.309.1+9.1+1=19.211C111.1+11.1+11.1+1=34.309.1+9.1+1=19.21D1111.1+11.1+11.1+1=34.309.1+9.1+1=19.2E9.1+9.1+1=19.21111.1+11.1+11.1+1=34.30信息素矩陣ktitabuk15AABCDE19.21134.30.450.0050.0060.5380.76911.121.258EA,EBCD1134.30.0040.0060.990.4934.643DA,E,DBC134.3

14、0.0210.9790.5811.683CA,E,D,CB34.31.00.8834.3BA,E,D,C,B空集-ktitabuk25BBACDE34.319.2110.7750.2170.0050.003911.144.24AB,ACDE1134.30.0090.0110.9811.66EB,A,ECD134.30.0060.99434.5DB,A,E,DC34.31.011.43CB,A,E,D,C空集-ktitabuk35CCABDE134.319.210.0030.8370.1560.004911.140.98BC,BADE34.3110.990.0060.00434.64AC,B,A

15、DE134.30.0110.98911.56EC,B,A,ED34.31.034.3DC,B,A,E,D空集-ktitabuk45DDABCE1134.319.20.0050.0120.5350.449911.121.38CD,CABE134.310.0030.9920.00534.58BD,C,BAE34.310.9960.00434.44AD,C,B,AE34.31.011.43ED,C,B,A,E空集-ktitabuk55EEABCD19.21134.30.2170.0030.0050.775911.144.24DE,DABC1134.30.0080.0210.97111.78CE,D,

16、CAB134.30.0030.99734.41BE,D,C,BA34.31.034.3AE,D,C,B,A空集- 至此出現(xiàn)了停滯現(xiàn)象，算法結(jié)束。 已找到最優(yōu)解：AEDCBA,目標(biāo)函數(shù)值為9。 試用蟻群算法求解6個點(diǎn)的對稱TSP。已知資料如下。ABCDEFA05756217870B5702365161C5620355160D21363506868E78515168013F70616068130練 習(xí)參數(shù)設(shè)置：令開始時，令已 知 資 料 表ABCDEA021083B10257C91036D104302E27510EABCD參數(shù)設(shè)置：算 例 正常數(shù)，螞蟻 在本次周游中所走路徑的長度。 當(dāng)所有螞蟻完成

17、1次周游后，各路徑上的信息素為：開始時，令ktitabuk10AABCDE22220.470.0950.1180.315119.12.117BA,BCDE2220.5930.2370.1691.686CA,B,CDE220.670.331.0DA,B,C,DE21.01.0EA,B,C,D,E空集-ktitabuk20BBACDE22220.540.270.110.08911.13.686AB,ACDE2220.180.220.601.117EB,A,ECD220.170.832.4DB,A,E,DC21.00.667CB,A,E,D,C空集-ktitabuk30CCABDE22220.069

18、0.620.2070.103911.13.222BC,BADE2220.7450.1490.1062.686AC,B,ADE220.2730.7270.917EC,B,A,ED21.02.0DC,B,A,E,D空集-ktitabuk40DDABCE22220.0840.2110.2870.422119.12.367ED,EABC2220.5930.1690.2371.686AD,E,ABC220.830.171.2BD,E,A,BC21.01.0CD,E,A,B,C空集-ktitabuk50EEABCD22220.2710.0780.1090.543911.13.686DE,DABC2220.

19、1460.3660.4881.367CE,D,CAB220.10.92.222BE,D,C,BA21.02.0AE,D,C,B,A空集-ABCDEA09.1+9.1+1=19.21111.1+11.1+11.1+1=34.3B11.1+11.1+11.1+1=34.309.1+9.1+1=19.211C111.1+11.1+11.1+1=34.309.1+9.1+1=19.21D1111.1+11.1+11.1+1=34.309.1+9.1+1=19.2E9.1+9.1+1=19.21111.1+11.1+11.1+1=34.30信息素矩陣ktitabuk15AABCDE19.21134.30.450.0050.0060.5380.76911.121.258EA,EBCD1134.30.0040.0060.990.4934.643DA,E,DBC134.30.0210.9790.5811.683CA,E,D,CB34.31.00.8834.3BA,E,D,C,B空集-ktitabuk25BBACDE34.319.2110.7750.2170.0050.003911.144.24AB,ACDE1134.30.0090.0110.9811.66EB,A,EC