智能計(jì)算之蟻群算法

1、第三章基本蟻群算法原理3.1自然界中的螞蟻在螞蟻尋找食物的過程中，總能找到一條從蟻穴到隨機(jī)分布的距離很 遠(yuǎn)的食物源之間的最短路徑。仿生學(xué)家經(jīng)過研究發(fā)現(xiàn)，螞蟻沒有視覺，但 是在尋找食物的行進(jìn)過程中，會(huì)不斷分泌一種化學(xué)刺激物一一信息素，螞 蟻之間通過它來相互通信。信息素量與路徑長(zhǎng)度有關(guān)，路徑越長(zhǎng)，釋放的信息素濃度就越低。信 息素可以吸引后來的螞蟻沿信息素濃度高的路徑行進(jìn)。某一路徑上走過的 螞蟻越多，留下的信息素就越多，后來者選擇該路徑的概率就越大，螞蟻 個(gè)體之間就是通過這種信息的交流搜索食物，這樣，由大量螞蟻組成的蟻 群的集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象，整個(gè)蟻群最終會(huì)選擇出最短 路徑行進(jìn)。-弊

2、b>圖3.1現(xiàn)實(shí)螞蟻尋找食物如圖3.1(a)所示，螞蟻在點(diǎn)A和E之間的路徑上行走，路徑突然被出現(xiàn)的障礙物截?cái)?，?.1(b)所示。因此，螞蟻從A至E步行至位置 B(或以相反的方向在位置D處)必須決定是否要向左或向右轉(zhuǎn)。一開始螞蟻按同等概率選擇路徑，不論路徑長(zhǎng)短。第一只螞蟻到達(dá)B點(diǎn)（或D）具有相同的概率向左或向右轉(zhuǎn)。由于路徑 BCD 比 BHD 短，以路徑 BCD 第 一個(gè)到達(dá)的螞蟻比以路徑 BHD 到達(dá)的早。由于一半螞蟻是以偶然的方式 通過 DCBA 障礙的或者已經(jīng)通過路徑 BCD 到達(dá)的，于是，一個(gè)螞蟻從 E 到 D 返回會(huì)在路徑 DCB 上找到一個(gè)更強(qiáng)有力的線索。因此他們極大概率上選

3、擇通過路徑 DCB 而不是 DHB 。因此， 單位時(shí)間內(nèi)通過路徑 BCD 的螞 蟻要比通過路徑 BHD 的螞蟻多的多，如圖 3.1（c） 。這將導(dǎo)致較短路徑上的 信息素量增長(zhǎng)地比較長(zhǎng)路徑上的快得多，因此單一螞蟻路徑的選擇很快偏 向于較短路徑。最后的結(jié)果是很快所有的螞蟻會(huì)選擇較短的路徑1 。不僅如此，作為一種化學(xué)物質(zhì)，信息素還具有揮發(fā)性，這使得尋徑 初期距離較長(zhǎng)的路徑和長(zhǎng)期沒有經(jīng)過的路徑對(duì)螞蟻的影響逐漸減小?？?見，在整個(gè)尋找食物的過程中，雖然單個(gè)螞蟻的選擇能力有限，但是通過 信息素的作用是整個(gè)蟻群行為具有非常高的自組織性，螞蟻之間交換著路 徑信息，最終通過蟻群的集體自催化行為找出最優(yōu)路徑 3,

4、4 。3.2 算法中的螞蟻蟻群算法是對(duì)自然界螞蟻的尋徑方式進(jìn)行模擬而得出的一種仿生算 法。此算法的本質(zhì)在于：選擇機(jī)制：信息素越多的路徑，被選擇的概率越大； 更新機(jī)制：路徑上的信息素會(huì)隨螞蟻的經(jīng)過次數(shù)增加而增長(zhǎng)，而且同 時(shí)也會(huì)隨時(shí)間的推移逐漸揮發(fā)消失；協(xié)調(diào)機(jī)制：螞蟻之間實(shí)際上是通過信息素來相互通信、協(xié)同工作的。 作為一種應(yīng)用于組合優(yōu)化問題的算法，基本蟻群算法的邏輯結(jié)構(gòu)（如 圖 3.2 所示）可以表述為：先將具體的優(yōu)化組合問題表述成規(guī)范的格式，然 后利用蟻群算法在“探索”和“利用”之間根據(jù)信息素這一反饋載體確定 決策點(diǎn)，同時(shí)按照相應(yīng)的信息素更新規(guī)則對(duì)每只螞蟻個(gè)體的信息素進(jìn)行增 量構(gòu)建，隨后從整體角

5、度規(guī)劃出蟻群活動(dòng)的行為方向，周而復(fù)始，即可求 出組合優(yōu)化問題的最優(yōu)解 3 。螞蟻活動(dòng)規(guī)劃丿螞蟻個(gè)體 A信息素 的增量構(gòu) 建信息素更新螞蟻個(gè)體 B信息素 的增量構(gòu) 建信息素決策點(diǎn)J冋題表達(dá)組合優(yōu)化問題圖3.2基本蟻群算法的邏輯結(jié)構(gòu)第四章 基本蟻群算法的數(shù)學(xué)模型4.1 TSP 問題3,4旅行商問題，可以描述為：給定n個(gè)城市，任何兩個(gè)城市之間皆有路連通，且城市間距離已知，某旅行商從其中某城市出發(fā)，要經(jīng)過每個(gè)城市 一次，且只能一次，最后又必須返回出發(fā)城市，要求找出最短的巡回路徑。旅行商問題是運(yùn)籌學(xué)中有代表的組合優(yōu)化問題，也是典型NP-complete類問題雖然陳述起來很簡(jiǎn)單，但求解卻很困難。對(duì)于具有n

6、個(gè)城市規(guī)模的TSP問題，其可能的閉合路徑數(shù)目為(n-1)!/2。在理論上枚舉法可以解決這一問題，但是當(dāng)n較大時(shí)，解題所需的計(jì)算時(shí)間和存儲(chǔ)空間的消耗會(huì)使枚舉法顯得沒有任何實(shí)際價(jià)值。4.2數(shù)學(xué)模型4.2.1 模型建立蟻群算法是對(duì)現(xiàn)實(shí)螞蟻覓食行為的模擬，因此需要對(duì)現(xiàn)實(shí)螞蟻進(jìn)行抽 象?，F(xiàn)實(shí)螞蟻存在于三維空間中，而問題空間抽象為一個(gè)二維平面一一圖。螞蟻在連續(xù)平面運(yùn)動(dòng)，其運(yùn)動(dòng)經(jīng)過的總是離散點(diǎn)，連續(xù)的平面可以離散化 為由一組點(diǎn)組成的離散平面，可供計(jì)算機(jī)處理?，F(xiàn)實(shí)螞蟻在覓食過程中主 要按照所處環(huán)境的信息素量來決定前進(jìn)方向，在算法構(gòu)造過程中，信息素 被抽象為圖的邊上的軌跡，螞蟻到達(dá)每一節(jié)點(diǎn)處根據(jù)邊上的信息素濃度

7、選 擇下一節(jié)點(diǎn)。螞蟻從初始節(jié)點(diǎn)(巢穴)按照一定轉(zhuǎn)移概率選擇下一節(jié)點(diǎn)， 最終選擇行走到目標(biāo)節(jié)點(diǎn)(食物源)，這樣便得到了TSP問題的一個(gè)可行解。給出一個(gè)n個(gè)城市組成的集合，TSP問題可以被描述為訪問每個(gè)城市一次找到最短路程的封閉式旅行問題。bi(t) (i=1, ., n)表示t時(shí)刻在城市in中的螞蟻數(shù)量，m 八bi(t)是螞蟻的總數(shù)。 j (t)為t時(shí)刻從城市i到城市ji =1路徑上的信息量，j (0)可以設(shè)置為任意數(shù)值(在實(shí)驗(yàn)中是每條路徑上的一個(gè)很小的數(shù)值)。城市i和城市j之間的距離定義為dij ( dij =(x i-xj)2 +(yi-yj)T/2)。為了約束螞蟻訪問所有的城市而不重復(fù)訪問

8、(即確定一個(gè)n城市的循環(huán))，我們?yōu)槊總€(gè)螞蟻定義一個(gè)數(shù)據(jù)結(jié)構(gòu)用于記錄螞蟻k訪問過的城市，稱為禁忌表tabuk。在螞蟻行動(dòng)過程中tabuk動(dòng)態(tài)調(diào)整，當(dāng)一次循環(huán)結(jié)束后清空禁忌表，螞蟻重新選擇路徑，重新填充禁忌表。在行進(jìn)過程中，螞蟻根據(jù)每條路徑上的信息素量及路徑的啟發(fā)信息來 計(jì)算轉(zhuǎn)移概率 pj。啟發(fā)函數(shù)ij等于1/dj，表示螞蟻從城市i轉(zhuǎn)移到城市j的期望程度。城市i到城市j的轉(zhuǎn)移概率定義為j allowed kj(t)：* Jx is(t)r * is:shallowed k(4.1)其中，allowed k=C-tabu k表示螞蟻 k下一步允許選擇的城市。:-和分別是表示允許用戶控制軌跡和能見度的

9、相對(duì)重要性的參數(shù)，:反映了螞蟻在運(yùn)動(dòng)過程中所積累的信息在運(yùn)動(dòng)時(shí)所起的作用，1反映了螞蟻在運(yùn)動(dòng)過程中啟發(fā)信息在選擇路徑時(shí)的受重視程度。4.2.2信息素更新3,5現(xiàn)實(shí)螞蟻在經(jīng)過的路徑上不斷地留下信息素，而信息素隨著時(shí)間的推 移不斷地?fù)]發(fā)改變。在計(jì)算機(jī)中，當(dāng)螞蟻完成一次對(duì)n個(gè)城市遍歷的循環(huán)后需要對(duì)信息素含量進(jìn)行一次更新。ij(t+n)=(1- : * j (t)+j (t)(4.2)mkij(t)二At ijk(t)k=1(4.3)其中，表示信息素?fù)]發(fā)系數(shù)，1-則表示信息素殘留因子。=ijk(t)表示第k只螞蟻在本次循環(huán)中留在路徑(i,j)上的信息素量。為了避免某條路段因?yàn)樾畔⑺貪舛冗^低而不能被螞蟻

10、選擇，每條道路 上的信息素濃度設(shè)立取值的下限.min。當(dāng)某路段上的信息素濃度小于下限.min時(shí)，則將其強(qiáng)制更正，同樣也設(shè)置其上限.max。關(guān)于如何計(jì)算 =ijk(t)和何時(shí)更新ij(t)的不同選擇出現(xiàn)了三種不同的蟻 群算法模型：ANT-density 模型，ANT-quantity 模型和 ANT-cycle 模型。在ANT-quantity 模型中k- Q/dj，若第k只螞蟻在本次循環(huán)中經(jīng)過路徑(i,j)：j (t)=-I 0，否 則(4.4)在ANT-density模型中我們有kQ，若第k只螞蟻在本次循環(huán)中經(jīng)過路徑(i,j)：j (t)=-L 0，否則(4.5)在ANT-cycle模型中k

11、 Q/Lk，若第k只螞蟻在本次循環(huán)中經(jīng)過路徑(i,j)：j (t)=L 0，否 則(4.6)式中，Q表示信息素強(qiáng)度，在一定程度上影響算法的收斂速度。Lk表示螞蟻k在本次循環(huán)中所走路徑的總長(zhǎng)度。式(4.4)(4.5)中利用的是局部信息，螞蟻完成每一步后需更新路徑上的信息素量；式(4.6)中利用的是整體信息信息，信息素量在一個(gè)循環(huán)后而不是每一步單獨(dú)的移動(dòng)后更新，求 解TSP問題性能較好，本文中就采用這種模型作為蟻群算法的基本模型。4.2.3 參數(shù)設(shè)置采用ANT-cycle模型執(zhí)行時(shí)優(yōu)于其他兩種模型，對(duì)參數(shù)的變化也更為 明智。信息啟發(fā)式因子："：】時(shí)的值小導(dǎo)致了收斂速度慢，:->2時(shí)

12、會(huì)較早收斂到次優(yōu)，最佳取值范圍為1W-W 1.5期望啟發(fā)式因子：5時(shí)收斂過快，系統(tǒng)迅速在次優(yōu)循環(huán)處卡住，：W時(shí)收斂緩慢， '<5時(shí)值增大收斂速度加快。信息素?fù)]發(fā)系數(shù) 二值低于二或大于時(shí)收斂速度較慢,信息素強(qiáng)度 Q:效果不顯著，本次實(shí)驗(yàn)取100。第五章基本蟻群算法的算法流程5.1算法運(yùn)行步驟以TSP問題為例，基本蟻群算法的具體實(shí)現(xiàn)步驟如下：1. 參數(shù)初始化：令t=0設(shè)置最大循環(huán)次數(shù)NcMax，循環(huán)次數(shù)Nc=O將m只螞蟻置于n個(gè)節(jié)點(diǎn)上，在每個(gè)節(jié)點(diǎn)i放置bi(t)只螞蟻初始化每條邊(i,j)上的信息素量ij (0)=c為一個(gè)常量，初始時(shí)刻k ijk(O)=O初始化禁忌表 tabuk及路

13、線表routek2. 設(shè)置索引號(hào)s=1,對(duì)k=1m將螞蟻k的起始城市放入禁忌表中，并重復(fù)以下步驟直至禁忌表填充完整：對(duì)k=1m，利用式(4.1)計(jì)算轉(zhuǎn)移概率 pij,根據(jù)偽隨機(jī)比例規(guī)則選 擇下一城市，將螞蟻 k移動(dòng)到下一城市j并將其填入禁忌表，同時(shí)記 錄螞蟻k的路線S+3. 對(duì)k=1m，根據(jù)routek的記錄計(jì)算螞蟻 k所走循環(huán)路徑的總長(zhǎng)度， 找到最佳路線4. 按式(4.6)計(jì)算每只螞蟻的信息素增量 ij k(t)5. 更新每條路徑上的信息素量ij(t+n)6. 清空禁忌表及路線表7. Nc+，若NcvNcMax，返回步驟2，否則，循環(huán)結(jié)束，輸出結(jié)果5.2算法運(yùn)行流程以TSP問題為例，基本蟻群

14、算法的程序結(jié)構(gòu)流程如圖5.1所示:圖5.1基本蟻群算法的程序流程圖1.計(jì)算啟發(fā)函數(shù) j=1/dj :for(i=0;i<m_N;i+)for (int j=0;j<m_N;j+)if (j!=i) yitaij=1/distanceij;2. 路線及禁忌表更新路線表 route 初始值為 -1 ，禁忌表 tabu 初始值為 0。 將螞蟻分別放置在初始節(jié)點(diǎn)(城市)上，記錄路線及修改禁忌表第一 項(xiàng)：for (k=0;k<m_M;k+) routek0=(k+m_N)%m_N; tabukroutek0=1;所有螞蟻開始尋找下一節(jié)點(diǎn)，利用公式4.1計(jì)算轉(zhuǎn)移概率 p，當(dāng)p大于隨機(jī)生成

15、的 (0,1) 中的數(shù)時(shí)，則可選擇此節(jié)點(diǎn)，記錄路線，修改禁忌表：for(int k=0;k<m_M;k+)int jrand=rand()%3000; drand=double(jrand)/3001;partsum=0;p=0;for (int j=0;j<m_N;j+) if(tabukj=0) partsum+=pow(Trouteks-1j,m_alfa)*pow(yitarouteks-1j,m_beta);for (j=0;j<m_N;j+) if(tabukj=0) p+=pow(Trouteks-1j,m_alfa)*pow(yitarouteks-1j ,m

16、_beta)/partsum;if(p>drand) break;tabukj=1; routeks=j;3. m 只螞蟻進(jìn)行一次遍歷后，計(jì)算所有螞蟻循環(huán)路線的總長(zhǎng)度，比較 得出最短路徑長(zhǎng)度，記錄最佳路線：for(k=0;k<m_M;k+) _double d=0;for(i=0;i<m_N;i+)d+=dista nceroutek(i+m_N)%m_Nroutek(i+m_N+1)%m_N;_soluti on k=d;for(k=1;k<m_M;k+)if (solutio n k<bestsoluti on)bestsolutio n=solutio n

17、k; /最短路徑長(zhǎng)度f(wàn)or(s=0;s<m_N;s+)bestroutes=routeks; / 最佳路線4.6，4. 信息素量的更新：使用ANT-cycle模型，.j (t)的計(jì)算依照公式 .ij依照公式4.2計(jì)算。此外，為了避免某條路段因?yàn)樾畔⑺貪舛冗^低或過 高影響螞蟻選擇結(jié)果，每條道路上的信息素濃度設(shè)立取值的上下限。當(dāng)某 路段上的信息素濃度超過此區(qū)間時(shí)，則將其強(qiáng)制更正。double T5050; 信息量double detaT5050; 信息量增量double dista nce5050; 兩城市間距離double yita5050; 啟發(fā)函數(shù)int tabu3050; 禁忌表in

18、 t route3050;/ 路線double solution30; 路徑長(zhǎng)度int bestroute50;最佳路徑記錄double bestsolutio n=10000000000; 記錄最佳路徑長(zhǎng)度/城市坐標(biāo)int x50=37,49,52,20,40,21,17,31,52,51,42,31,5,12,36,52,27,17,13,57,62,42,16,8,7,27,30,43,58,58,37,38,46,61,62,63,32,45,59,5,10,21,5,30,39,32,25,25,48,56;int y50= 52,49,64,26,30,47,63,62,33,21

19、,41,32,25,42,16,41,23,33,13,58,42,57,57,52,38,68,48,67,48,27,69,46,10,33,63,69,22,35,15,6,17,10,64,15,10,39,32,55,28,37;for (int i=0;i<m_N;i+)for (int j=i+1;j<m_N;j+)distanceji=sqrt(xi-xj)*(xi-xj)+(yi-yj)*(yi-yj); distanceij=distanceji;for(i=0;i<m_N;i+)for (int j=0;j<m_N;j+)Tij=m_inittao

20、;/ 初始信息素量if (j!=i)yitaij=1/distanceij;for (int k=0;k<m_M;k+)for(i=0;i<m_N;i+)routeki=-1;tabuki=0;for (k=0;k<m_M;k+)routek0=(k+m_N)%m_N;tabukroutek0=1;srand(time(NULL);int Nc=0;doint s=1;double drand;double partsum;double p;while (s<m_N)for(int k=0;k<m_M;k+)int jrand=rand()%3000;drand=double(jrand)/3001;partsum=0;p=0;for (int j=0;j<m_N;j+)if(tabukj=0)partsum+=pow(Trouteks-1j,m_alfa)*pow(yitarouteks-1j,m_b eta);for (j=0;j<m_N;j+)if(tabukj=0)p+=pow(Trouteks-1j,m_alfa)*pow(yitarouteks-1j,m