應(yīng)用篇-第11章-蟻群算法的仿真與實(shí)現(xiàn)

第11章

蟻群算法的仿真與實(shí)現(xiàn)蟻群算法是近年來興起的一種新型仿生優(yōu)化算法，具有其他進(jìn)化算法不可比擬的優(yōu)勢(shì)。該算法是繼神經(jīng)網(wǎng)絡(luò)、遺傳算法、模擬退火算法、粒子群算法、免疫算法等仿生搜索算法以后的又一種應(yīng)用于組合優(yōu)化問題的啟發(fā)式搜索算法。由于蟻群算法采用分布式并行計(jì)算機(jī)制，具有較強(qiáng)的魯棒性，容易與其它算法結(jié)合等優(yōu)點(diǎn)，一經(jīng)提出，立即受到各個(gè)領(lǐng)域?qū)W者的重視，展開了對(duì)其的研究。目前蟻群算法已經(jīng)被廣泛的應(yīng)用于求解旅行商問題，自動(dòng)組卷系統(tǒng)問題等等、本章則對(duì)于這兩個(gè)問題做出了詳細(xì)的闡述。11.1 蟻群算法介紹生物學(xué)家通過對(duì)螞蟻的長(zhǎng)期觀察研究發(fā)現(xiàn)，每只螞蟻的智能并不高，看起來沒有集中的指揮，但它們卻能協(xié)同工作，集中食物，建起堅(jiān)固漂亮的蟻穴并撫養(yǎng)后代，依靠群體能力發(fā)揮出超出個(gè)體的智能。蟻群算法(antcolonyoptimization,ACO)是最新發(fā)展的一種模擬昆蟲王國(guó)中螞蟻群體智能行為的仿生優(yōu)化算法。它具有較強(qiáng)的魯棒性、優(yōu)良的分布式計(jì)算機(jī)制、易于與其他方法相結(jié)合等優(yōu)點(diǎn)盡管蟻群算法的嚴(yán)格理論基礎(chǔ)尚未奠定，國(guó)內(nèi)外的相關(guān)研究還處于實(shí)驗(yàn)探索和初步應(yīng)用階段，但是目前人們對(duì)蟻群算法的研究已經(jīng)由當(dāng)初單一的旅行商問題(travelingsalesmanproblem，TSP)領(lǐng)域滲透到了多個(gè)應(yīng)用領(lǐng)域，由解決一維靜態(tài)優(yōu)化問題發(fā)展到解決多維動(dòng)態(tài)組合優(yōu)化問題，由離散域范圍內(nèi)的研究逐漸拓展到了連續(xù)域范圍內(nèi)的研究，而且在蟻群算法的硬件實(shí)現(xiàn)上也取得了很多突破性的研究進(jìn)展，從而使這種新興的仿生優(yōu)化算法展現(xiàn)出勃勃生機(jī)和廣闊的發(fā)展前景。蟻群算法是從自然界中真實(shí)螞蟻覓食的群體行為得到啟發(fā)而提出的，其很多觀點(diǎn)都來源于真實(shí)蟻群，因此算法中所定義的人丁螞蟻與真實(shí)螞蟻存在如下共同點(diǎn)。

（1）都存在一個(gè)群體中個(gè)體相互交流通信的機(jī)制

（2）都要完成一個(gè)相同的任務(wù)

（3）利用當(dāng)前信息進(jìn)行路徑選擇的隨機(jī)選擇策略在從真實(shí)蟻群行為獲得啟發(fā)而構(gòu)造蟻群算法的過程中，人工螞蟻還具備了真實(shí)螞蟻所不具有的一些特性：

(1)人工螞蟻存在于一個(gè)離散的空間中，它們的移動(dòng)是從一個(gè)狀態(tài)到另一個(gè)狀態(tài)

的轉(zhuǎn)換； (2)人工螞蟻具有一個(gè)記憶其本身過去行為的內(nèi)在狀態(tài)； (3)人工螞蟻存在于一個(gè)與時(shí)間無關(guān)聯(lián)的環(huán)境之中； (4)人工螞蟻不是完全盲從的，它還受到問題空間特征的啟發(fā)。例如有的問題中

人工螞蟻在產(chǎn)生一個(gè)解后改變信息量，而有的問題中人工螞蟻每作出一步選擇

就更改信息量，但無論哪種方法，信息量的更新井不是隨時(shí)都可進(jìn)行的； (5)為了改善算法的優(yōu)化效率，人工螞蟻可增加一些性能，如預(yù)測(cè)未來、局部?jī)?yōu)

化、回退等，這些行為在真實(shí)螞蟻中是不存在的。在很多具體應(yīng)用中，人工螞

蟻可在局部?jī)?yōu)化過程中相互交換信息，還有一些改進(jìn)蟻群算法中的人工螞蟻可

實(shí)現(xiàn)簡(jiǎn)單預(yù)測(cè)。11.2 蟻群算法原理根據(jù)仿生學(xué)家的長(zhǎng)期研究發(fā)現(xiàn)：螞蟻雖沒有視覺，但運(yùn)動(dòng)時(shí)會(huì)通過在路徑上釋放出一種特殊的分泌物——信息素來尋找路徑。當(dāng)它們碰到～個(gè)還沒有走過的路口時(shí)，就隨機(jī)地挑選一條路徑前行，同時(shí)釋放出與路徑長(zhǎng)度有關(guān)的信息素。螞蟻?zhàn)叩穆窂皆介L(zhǎng)，則釋放的信息量越小。當(dāng)后來的螞蟻再次碰到這個(gè)路口的時(shí)候，選擇信息量較大路徑的概率相對(duì)較大，這樣便形成了一個(gè)正反饋機(jī)制。最優(yōu)路徑上的信息量越來越大，而其他路徑上的信息量卻會(huì)隨著時(shí)間的流逝而逐漸消減，最終整個(gè)蟻群會(huì)找出最優(yōu)路徑。同時(shí)蟻群還能夠適應(yīng)環(huán)境的變化，當(dāng)蟻群的運(yùn)動(dòng)路徑上突然出現(xiàn)障礙物時(shí)，螞蟻也能很快地重新找到最優(yōu)路徑。可見，在整個(gè)尋徑過程中，雖然單只螞蟻的選擇能力有限，但是通過信息素的作用使整個(gè)蟻群行為具有非常高的自組織性，螞蟻之間交換著路徑信息，最終通過蟻群的集體自催化行為找出最優(yōu)路徑。11.2.1 蟻群行為描述模擬螞蟻群體覓食行為的蟻群算法是作為一種新的計(jì)算智能模式引入的，該算法基于如下基本假設(shè)：（1）螞蟻之間通過信息素和環(huán)境進(jìn)行通信。每只螞蟻僅根據(jù)其周圍的局部環(huán)境做出反應(yīng)，也只對(duì)其周圍的局部環(huán)境產(chǎn)生影響。（2）螞蟻對(duì)環(huán)境的反應(yīng)由其內(nèi)部模式?jīng)Q定。因?yàn)槲浵伿腔蛏?，螞蟻的行為?shí)際上是其基因的適應(yīng)性表現(xiàn)，即螞蟻是反應(yīng)型適應(yīng)性主體。（3）在個(gè)體水平上，每只螞蟻僅根據(jù)環(huán)境做出獨(dú)立選擇；在群體水平上，單只螞蟻的行為是隨機(jī)的，但蟻群可通過自組織過程形成高度有序的群體行為。11.2.2 基本蟻群算法的機(jī)制原理由于蟻群算法是對(duì)自然界中真實(shí)螞蟻覓食行為的一種模擬，是一種機(jī)理上的應(yīng)用，因此首先必須對(duì)真實(shí)螞蟻進(jìn)行抽象，而不可能也沒必要對(duì)螞蟻個(gè)體進(jìn)行完全再現(xiàn)。抽象的目的就是為了能夠更加有效地刻畫出真實(shí)蟻群中能夠?yàn)樗惴ㄋ梃b的機(jī)理，同時(shí)摒棄與建立算法模型無關(guān)的因素。這樣抽象出來的人工螞蟻可以看做是一個(gè)簡(jiǎn)單的智能體，能夠完成所求問題簡(jiǎn)單解的構(gòu)造過程，也能通過一種通信手段相互影響。11.2.3 對(duì)螞蟻個(gè)體的抽象自然界中的真實(shí)螞蟻存在于一個(gè)三維的環(huán)境中，而問題空間的求解一般是在平面內(nèi)進(jìn)行的，因此需要將螞蟻覓食的三維空間抽象為一個(gè)平面。這一點(diǎn)比較容易理解，因?yàn)槲浵佉捠乘叩穆窂奖緛砭痛嬖谟谝粋€(gè)二維空間（平面或者曲面）上。另外一個(gè)問題是真實(shí)螞蟻是在一個(gè)連續(xù)的二維平面中行走的，而我們無法用計(jì)算機(jī)直接來完整的描述一個(gè)連續(xù)的平面，因?yàn)橛?jì)算機(jī)處理的是離散事件，因此必須將連續(xù)的平面離散化由一組點(diǎn)組成的離散平面，人工螞蟻可在抽象出來的點(diǎn)上自由運(yùn)動(dòng)。這個(gè)抽象過程的可行性在于，盡管螞蟻是在連續(xù)平面行動(dòng)，但其行動(dòng)經(jīng)過的總是離散點(diǎn)，因此抽象過程只是提高了平面點(diǎn)離散分布的粒度，與其覓食行為的本身機(jī)理沒有任何沖突。基于上述分析，很容易得到蟻群算法所求解的問題空間可用一個(gè)重要的數(shù)學(xué)工具——圖(graph)來描述。在工程實(shí)際中的很多問題都可以用圖來描述，這便使蟻群算法的廣泛應(yīng)用成為可能。11.2.4 問題空間的描述真實(shí)螞蟻在覓食過程中主要按照所處環(huán)境中的信息量來決定其前進(jìn)的方向，而人工螞蟻是在平面的節(jié)點(diǎn)上運(yùn)動(dòng)的，因此可把覓食過程抽象成算法中解的構(gòu)造過程，將信息素抽象為存在于圖的邊上的軌跡。在每一節(jié)點(diǎn)，人工螞蟻感知連接該節(jié)點(diǎn)與相鄰節(jié)點(diǎn)邊上的信息素軌跡濃度，并根據(jù)該濃度大小決定走向下一節(jié)點(diǎn)的概率。用任意兩個(gè)節(jié)點(diǎn)分別表示螞蟻的巢穴（初始節(jié)點(diǎn)）和食物源（目標(biāo)節(jié)點(diǎn)），人工螞蟻從初始節(jié)點(diǎn)按照一定狀態(tài)轉(zhuǎn)移概率選擇下一節(jié)點(diǎn)，依此類推，最終選擇行走到目標(biāo)節(jié)點(diǎn)，這樣便得到了所求問題的一個(gè)可行解。11.2.5 尋找路徑的抽象自然界中的真實(shí)螞蟻總是在所經(jīng)路徑上連續(xù)不斷地留下信息素，而信息素也會(huì)隨著時(shí)間的推移而連續(xù)不斷地?fù)]發(fā)。由于計(jì)算機(jī)處理的事件只能是離散事件，所以必須使信息素的揮發(fā)離散發(fā)生。通常的做法是，當(dāng)螞蟻完成從某一節(jié)點(diǎn)到下一節(jié)點(diǎn)的移動(dòng)后，即經(jīng)過一個(gè)時(shí)間單位之后，進(jìn)行一次信息素的揮發(fā)，而這種在離散時(shí)間點(diǎn)進(jìn)行信息素?fù)]發(fā)的方式與螞蟻覓食過程的機(jī)理是完全相符的。11.2.6 信息素?fù)]發(fā)的抽象以上幾點(diǎn)是對(duì)真實(shí)螞蟻覓食行為的抽象，整個(gè)過程體現(xiàn)了蟻群算法的自組織性，但是這種自組織系統(tǒng)存在一個(gè)缺陷，即系統(tǒng)的演化需要耗費(fèi)較長(zhǎng)的時(shí)間。而實(shí)際應(yīng)用時(shí)對(duì)算法運(yùn)行時(shí)間的要求也是必不可少的，因此在決定螞蟻行走方向的狀態(tài)轉(zhuǎn)移概率時(shí)，引入了一個(gè)隨機(jī)搜索的過程，即引入了啟發(fā)因子，根據(jù)所求問題空間的具體特征，給蟻群算法一個(gè)初始的引導(dǎo)，這個(gè)過程極大地增加了算法的時(shí)間有效性，從而使蟻群算法的有效應(yīng)用成為可能。以上幾點(diǎn)是對(duì)真實(shí)螞蟻覓食行為的抽象，整個(gè)過程體現(xiàn)了蟻群算法的自組織性，但是這種自組織系統(tǒng)存在一個(gè)缺陷，即系統(tǒng)的演化需要耗費(fèi)較長(zhǎng)的時(shí)間。而實(shí)際應(yīng)用時(shí)對(duì)算法運(yùn)行時(shí)間的要求也是必不可少的，因此在決定螞蟻行走方向的狀態(tài)轉(zhuǎn)移概率時(shí)，引入了一個(gè)隨機(jī)搜索的過程，即引入了啟發(fā)因子，根據(jù)所求問題空間的具體特征，給蟻群算法一個(gè)初始的引導(dǎo)，這個(gè)過程極大地增加了算法的時(shí)間有效性，從而使蟻群算法的有效應(yīng)用成為可能。11.2.7 啟發(fā)因子的引入蟻群算法具有很強(qiáng)的自學(xué)習(xí)能力，可根據(jù)環(huán)境的改變和過去的行為結(jié)果對(duì)自身的知識(shí)庫(kù)或自身的組織結(jié)構(gòu)進(jìn)行再組織，從而實(shí)現(xiàn)算法求解能力的進(jìn)化，而這種進(jìn)化是環(huán)境變化與算法自學(xué)習(xí)能力交互作用的產(chǎn)物，同時(shí)算法機(jī)理的復(fù)雜性和環(huán)境變化的不確定性進(jìn)一步增加了蟻群算法的不可預(yù)測(cè)性。11.3 基本蟻群算法的數(shù)學(xué)模型

設(shè)hi(t)表示t時(shí)刻位于元素i的螞蟻數(shù)目，Гij(t)為，時(shí)刻路徑(i,j)上的信息量，n表示TSP規(guī)模，m為蟻群中螞蟻的總數(shù)目，則是t時(shí)刻集合C中元素（城市）兩兩連接lij上殘留信息量的集合。在初始時(shí)刻各條路徑上信息量相等，并設(shè)rij(0)=const，基本蟻群算法的尋是通過有向圖g=(C,L,Г)實(shí)現(xiàn)的。

螞蟻k(k=l,2,…,m)在運(yùn)動(dòng)過程中，根據(jù)各條路徑上的信息量決定其轉(zhuǎn)移方向。這里用禁忌表tabuk(k=l,2,…,m)來記錄螞蟻k當(dāng)前所走過的城市，集合隨著tabuk進(jìn)化過程作動(dòng)態(tài)調(diào)整。在搜索過程中，螞蟻根據(jù)各條路徑上的信息量及路徑的啟發(fā)信息來計(jì)算狀態(tài)轉(zhuǎn)移概率。pkij(t)表示在t時(shí)刻螞蟻k由元素（城市）i轉(zhuǎn)移到元素（城市）j的狀態(tài)轉(zhuǎn)移概率式中，allowedk=(C-tabuk）表示螞蟻k下一步允許選擇的城市；α為信息啟發(fā)式因子，表示軌跡的相對(duì)重要性，反映了螞蟻在運(yùn)動(dòng)過程中所積累的信息在螞蟻運(yùn)動(dòng)時(shí)所起的作用，其值越大，則該螞蟻越傾向于選擇其他螞蟻經(jīng)過的路徑，螞蟻之間協(xié)作性越強(qiáng)；β為期望啟發(fā)式因子，表示能見度的相對(duì)重要性，反映了螞蟻在運(yùn)動(dòng)過程中啟發(fā)信息在螞蟻選擇路徑中的受重視程度，其值越大，則該狀態(tài)轉(zhuǎn)移概率越接近于貪心規(guī)則；ηij(t)為啟發(fā)函數(shù)，其表達(dá)式如下式中，dij表示相鄰兩個(gè)城市之間的距離。對(duì)螞蟻k而言，dij越小，則ηij(t)越大，pkij(t)也就越大。顯然，該啟發(fā)函數(shù)表示螞蟻從元素（城市）j轉(zhuǎn)移到元素（城市）j的期望程度。為了避免殘留信息素過多引起殘留信息淹沒啟發(fā)信息，在每只螞蟻?zhàn)咄暌徊交蛘咄瓿蓪?duì)所有n個(gè)城市的遍歷（也即一個(gè)循環(huán)結(jié)束）后，要對(duì)殘留信息進(jìn)行更新處理。這種更新策略模仿了人類大腦記憶的特點(diǎn)，在新信息不斷存人大腦的同時(shí)，存儲(chǔ)在大腦中的舊信患隨著時(shí)間的推移逐漸淡化，甚至忘記。由此，t+n時(shí)刻在路徑(i,j)上的信息量可按如下規(guī)則進(jìn)行調(diào)整式中，ρ表示信息素?fù)]發(fā)系數(shù)，則1-ρ表示信息素殘留因子，為了防止信息的