智能計算之蟻群算法

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

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

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

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

5、數(shù)學(xué)模型TSP問題3,4旅行商問題，可以描述為：給定n個城市，任何兩個城市之間皆有路連通，且城市間距離已知，某旅行商從其中某城市出發(fā)，要經(jīng)過每個城市一次，且只能一次，最后又必須返回出發(fā)城市，要求找出最短的巡回路徑。旅行商問題是運籌學(xué)中有代表的組合優(yōu)化問題，也是典型NP-complete類問題.雖然陳述起來很簡單，但求解卻很困難。對于具有n個城市規(guī)模的TSP問題，其可能的閉合路徑數(shù)目為(n-1)!/2。在理論上枚舉法可以解決這一問題，但是當(dāng)n較大時，解題所需的計算時間和存儲空間的消耗會使枚舉法顯得沒有任何實際價值。數(shù)學(xué)模型模型建立蟻群算法是對現(xiàn)實螞蟻覓食行為的模擬，因此需要對現(xiàn)實螞蟻進(jìn)行抽象。現(xiàn)

6、實螞蟻存在于三維空間中，而問題空間抽象為一個二維平面一一圖。螞蟻在連續(xù)平面運動，其運動經(jīng)過的總是離散點，連續(xù)的平面可以離散化為由一組點組成的離散平面，可供計算機(jī)處理?，F(xiàn)實螞蟻在覓食過程中主要按照所處環(huán)境的信息素量來決定前進(jìn)方向，在算法構(gòu)造過程中，信息素被抽象為圖的邊上的軌跡，螞蟻到達(dá)每一節(jié)點處根據(jù)邊上的信息素濃度選擇下一節(jié)點。螞蟻從初始節(jié)點(巢穴)按照一定轉(zhuǎn)移概率選擇下一節(jié)點，最終選擇行走到目標(biāo)節(jié)點(食物源)，這樣便得到了TSP問題的一個可行解。給出一個n個城市組成的集合，TSP問題可以被描述為訪問每個城市一次找到最短路程的封閉式旅行問題。bi(t)(i=1,.,n)表示t時刻在城市in中的螞

7、蟻數(shù)量，m=£b<)是螞蟻的總數(shù)。*(t)為t時刻從城市i到城市ji1路徑上的信息量，期(0)可以設(shè)置為任意數(shù)值(在實驗中是每條路徑上的一個很小的數(shù)值)。城市i和城市j之間的距離定義為dij(dij=(xi-xj)2+(yi-yD21/2)。為了約束螞蟻訪問所有的城市而不重復(fù)訪問(即確定一個n城市的循環(huán))，我們?yōu)槊總€螞蟻定義一個數(shù)據(jù)結(jié)構(gòu)用于記錄螞蟻k訪問過的城市，稱為禁忌表tabuk。在螞蟻行動過程中tabuk動態(tài)調(diào)整，當(dāng)一次循環(huán)結(jié)束后清空禁忌表，螞蟻重新選擇路徑，重新填充禁忌表。在行進(jìn)過程中，螞蟻根據(jù)每條路徑上的信息素量及路徑的啟發(fā)信息來計算轉(zhuǎn)移概率pijo啟發(fā)函數(shù)飛等于1/

8、dij,表示螞蟻從城市i轉(zhuǎn)移到城市j的期望程度。城市i到城市j的轉(zhuǎn)移概率定義為jallowedkij(t):*ij：Xis(t)-*is：shallowedk其中，allowedk=C-tabuk表示螞蟻k下一步允許選擇的城市。a和P分別是表示允許用戶控制軌跡和能見度的相對重要性的參數(shù)，«反映了螞蟻在運動過程中所積累的信息在運動時所起的作用，P反映了螞蟻在運動過程中啟發(fā)信息在選擇路徑時的受重視程度。4.2.2信息素更新3,5現(xiàn)實螞蟻在經(jīng)過的路徑上不斷地留下信息素，而信息素隨著時間的推移不斷地?fù)]發(fā)改變。在計算機(jī)中，當(dāng)螞蟻完成一次對n個城市遍歷的循環(huán)后需要對信息素含量進(jìn)行一次更新。ij(

9、t+n)=(1-P*ij(t)+：ij(t)m.ij(t)=xATijk(t)k=1其中，P表示信息素?fù)]發(fā)系數(shù)，1-P則表示信息素殘留因子。夕ijk(t)表示第k只螞蟻在本次循環(huán)中留在路徑(i,j)上的信息素量。為了避免某條路段因為信息素濃度過低而不能被螞蟻選擇，每條道路上的信息素濃度設(shè)立取值的下限Tmino當(dāng)某路段上的信息素濃度小于下限如in時，則將其強(qiáng)制更正，同樣也設(shè)置其上限Tmaxo關(guān)于如何計算Aiijk(t)和何時更新Tij(t)的不同選擇出現(xiàn)了三種不同的蟻群算法模型：ANT-density模型，ANT-quantity模型和ANT-cycle模型。在ANT-quantity模型中kQ

10、/dij,若第k只螞蟻在本次循環(huán)中經(jīng)過路徑(i,j).ij(t)='L0,否則在ANT-density模型中我們有kQ,若第k只螞蟻在本次循環(huán)中經(jīng)過路徑(i,j)7ij(t)=00,否則在ANT-cycle模型中kQ/Lk,若第k只螞蟻在本次循環(huán)中經(jīng)過路徑(i,j)ij(t)=L0,否則式中，Q表示信息素強(qiáng)度，在一定程度上影響算法的收斂速度。Lk表示螞蟻k在本次循環(huán)中所走路徑的總長度。式(4.4)(4.5)中利用的是局部信息，螞蟻完成每一步后需更新路徑上的信息素量；式(4.6)中利用的是整體信息信息，信息素量在一個循環(huán)后而不是每一步單獨的移動后更新，求解TSP問題性能較好，本文中就采用

11、這種模型作為蟻群算法的基本模型。4.2.3參數(shù)設(shè)置5采用ANT-cycle模型執(zhí)行時優(yōu)于其他兩種模型，對參數(shù)的變化也更為明智。信息啟發(fā)式因子a：a<l時的值小導(dǎo)致了收斂速度慢，a2時會較早收斂到次優(yōu)，最佳取值范圍為14X015期望啟發(fā)式因子隹P>5時收斂過快，系統(tǒng)迅速在次優(yōu)循環(huán)處卡住，P司時收斂緩慢，1<PW5時值增大收斂速度加快。信息素?fù)]發(fā)系數(shù)P:值低于0.2或大于0.5時收斂速度較慢，約0.3時最佳信息素強(qiáng)度Q:效果不顯著，本次實驗取100。第五章基本蟻群算法的算法流程算法運行步驟以TSP問題為例，基本蟻群算法的具體實現(xiàn)步驟如下：.參數(shù)初始化：令t=0設(shè)置最大循環(huán)次數(shù)Nc

12、Max,循環(huán)次數(shù)Nc=0將m只螞蟻置于n個節(jié)點上，在每個節(jié)點i放置bi(t)只螞蟻初始化每條邊(i,j)上的信息素量Tij(0)=C為一個常量，初始時刻.ijk(0)=0初始化禁忌表tabuk及路線表routek.設(shè)置索引號s=1,對k=1m將螞蟻k的起始城市放入禁忌表中，并重復(fù)以下步驟直至禁忌表填充完整：對k=1m,利用式(4.1)計算轉(zhuǎn)移概率p/根據(jù)偽隨機(jī)比例規(guī)則選擇下一城市，將螞蟻k移動到下一城市j并將其填入禁忌表，同時記錄螞蟻k的路線s+.對k=1m,根據(jù)routek的記錄計算螞蟻k所走循環(huán)路徑的總長度，找到最佳路線.按式(4.6)計算每只螞蟻的信息素增量ijk(t).更新每條路徑上的

13、信息素量引(t+n).清空禁忌表及路線表.Nc+,若Nc<NcMax,返回步驟2,否則，循環(huán)結(jié)束，輸出結(jié)果算法運行流程以TSP問題為例，基本蟻群算法的程序結(jié)構(gòu)流程如圖5.1所示:圖5.1基本蟻群算法的程序流程圖1.計算啟發(fā)函數(shù)，=1/dij：for(i=0;i<m_N;i+)for(intj=0；j<m_N；j+)(if(j!=i)yitaij=1/distanceij;).路線及禁忌表更新路線表route初始值為-1,禁忌表tabu叩初始值為0。將螞蟻分別放置在初始節(jié)點(城市)上，記錄路線及修改禁忌表第一項：for(k=0;k<m_M;k+)(.routek0=(k+

14、m_N)%m_N;tabukroutek0=1;)所有螞蟻開始尋找下一節(jié)點，利用公式4.1計算轉(zhuǎn)移概率p,當(dāng)p大于隨機(jī)生成的(0,1)中的數(shù)時，則可選擇此節(jié)點，記錄路線，修改禁忌表：for(intk=0;k<m_M;k+)(.intjrand=rand()%3000;drand=double(jrand)/3001;partsum=0;p=0;for(intj=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(ta

15、bukj=0)p+=pow(Trouteks-1j,m_alfa)*pow(yitarouteks-1j,m_beta)/partsum;if(p>drand)break;)tabukj=1;routeks=j;).m只螞蟻進(jìn)行一次遍歷后，計算所有螞蟻循環(huán)路線的總長度，比較得出最短路徑長度，記錄最佳路線：for(k=0;k<m_M;k+)(.doubled=0;for(i=0;i<m_N;i+)d+=distanceroutek(i+m_N)%m_Nroutek(i+m_N+1)%m_N;_solutionk=d;for(k=1;k<m_M;k+)if(solution

16、k<bestsolution)(bestsolution=solutionk;/最短路徑長度for(s=0;s<m_N;s+)bestroutes=routeks;/最佳路線.信息素量的更新：使用ANT-cycle模型，Sij(t)的計算依照公式4.6,荀依照公式4.2計算。止匕外，為了避免某條路段因為信息素濃度過低或過高影響螞蟻選擇結(jié)果，每條道路上的信息素濃度設(shè)立取值的上下限。當(dāng)某路段上的信息素濃度超過此區(qū)間時，則將其強(qiáng)制更正。doubleT5050;/信息量doubledetaT5050;/信息量增量doubledistance5050;/兩城市間距離doubleyita505

17、0;/啟發(fā)函數(shù)inttabu3050;/禁忌表introute3050;/路線doublesolution30;/路徑長度intbestroute50;/最佳路徑記錄doublebestsolution=10000000000;/記錄最佳路徑長度/城市坐標(biāo)intx50=(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;inty50=(52,49,64,26

18、,30,47,63,62,33,21,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(inti=0;i<m_N;i+)for(intj=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(intj=0;j<m_N;j+)

19、Tij=m_inittao;/初始信息素量if(j!=i)yitaij=1/distanceij;)for(intk=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);intNc=0;doints=1;doubledrand;doublepartsum;doublep;while(s<m_N)for(intk=0;k<m_M;k+)(.intjrand=rand()%3000;drand=double(jrand)/3001;partsum=0;p=0;for(intj=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_beta)/partsum;if(p&g