第5章 蟻群算法

5蟻群算法

AntColonyOptimization23

目錄1、蟻群算法起源2、蟻群算法模型3、實(shí)例仿真4、蟻群算法特點(diǎn)5、總結(jié)雙橋?qū)嶒?yàn)蟻群優(yōu)化（antcolonyoptimization,ACO）是20世紀(jì)90年代初由意大利學(xué)者M(jìn).Dorigo等通過(guò)模擬螞蟻的行為而提出的一種隨機(jī)優(yōu)化技術(shù)（尋找優(yōu)化路徑的機(jī)率型算法）。研究主要是以螞蟻尋找食物之后能選擇一條最短路徑來(lái)連接蟻穴和食物源。1991年，M.Dorigo在法國(guó)巴黎第一屆歐洲人工生命會(huì)議上最早提出了蟻群算法的基本模型，1992年又在其博士論文中進(jìn)一步闡述了蟻群算法的核心思想。MacroDorigo1.蟻群算法起源螞蟻覓食過(guò)程在蟻群尋找食物時(shí)，能夠在它所經(jīng)過(guò)的路徑上留下一種稱之為信息素(pheromone)的物質(zhì)進(jìn)行信息傳遞，而且螞蟻在運(yùn)動(dòng)過(guò)程中能夠感知這種物質(zhì)，并以此指導(dǎo)自己的運(yùn)動(dòng)方向，因此由大量螞蟻組成的蟻群集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過(guò)的螞蟻越多，則后來(lái)者選擇該路徑的概率就越大。最優(yōu)路徑上的信息素濃度越來(lái)越大，而其它的路徑上激素濃度卻會(huì)隨著時(shí)間的流逝而消減。最終整個(gè)蟻群會(huì)找出最優(yōu)路徑。A點(diǎn)為蟻穴，食物在D點(diǎn)，可能隨機(jī)選擇路線ABD或ACD。假設(shè)初始時(shí)每條路線有一只螞蟻，每個(gè)時(shí)間單位行走一步，本圖為經(jīng)過(guò)9個(gè)時(shí)間單位時(shí)的情形：走ABD的螞蟻到達(dá)食物，而走ACD的螞蟻剛好走到C點(diǎn)，為一半路程。簡(jiǎn)化的螞蟻尋食過(guò)程本圖為從開(kāi)始算起，經(jīng)過(guò)18個(gè)時(shí)間單位時(shí)的情形：走ABD的螞蟻到達(dá)D點(diǎn)后得到食物又返回了起點(diǎn)A，而走ACD的螞蟻剛好走到D點(diǎn)。假設(shè)螞蟻每經(jīng)過(guò)一處所留下的信息素為一個(gè)單位，則經(jīng)過(guò)36個(gè)時(shí)間單位后，ABD的路線往返了2趟，每一處的信息素為4個(gè)單位，而ACD的路線往返了一趟，每一處的信息素為2個(gè)單位，其比值為2：1。按信息素的指導(dǎo)，ABD路線增加一只螞蟻（共2只），ACD路線仍為一只螞蟻。再經(jīng)過(guò)36個(gè)時(shí)間單位后，兩條線路上的信息素為12和4，比值為3：1。于是，ABD路線增加一只螞蟻（共3只），ACD路線仍為一只螞蟻。再經(jīng)過(guò)36個(gè)時(shí)間單位后，兩條線路上的信息素為24和6，比值為4：1。若繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，最終所有的螞蟻會(huì)放棄ACD路線，而都選擇ABD路線。蟻群算法通常用于求解復(fù)雜的組合優(yōu)化問(wèn)題。所謂組合優(yōu)化,是指在離散的、有限的數(shù)學(xué)結(jié)構(gòu)上,尋找一個(gè)滿足給定條件,并使其目標(biāo)函數(shù)值達(dá)到最大或最小的解.理論假設(shè)1、蟻群之間通過(guò)信息素和環(huán)境進(jìn)行通信。2、螞蟻對(duì)環(huán)境的反應(yīng)由其內(nèi)部模式?jīng)Q定。3、個(gè)體水平上，每個(gè)螞蟻相對(duì)獨(dú)立；群體水平上，每只螞蟻的行為是隨機(jī)的。2.蟻群算法模型算法規(guī)則121.范圍螞蟻觀察到的范圍是一個(gè)方格世界，螞蟻有一個(gè)參數(shù)為速度半徑（一般是3），那么它能觀察到的范圍就是3*3個(gè)方格世界，并且能移動(dòng)的距離也在這個(gè)范圍之內(nèi)。132.環(huán)境螞蟻所在的環(huán)境是一個(gè)虛擬的世界，其中有障礙物，有別的螞蟻，還有信息素，信息素有兩種，一種是找到食物的螞蟻灑下的食物信息素，一種是找到窩的螞蟻灑下的窩的信息素。每個(gè)螞蟻都僅僅能感知它范圍內(nèi)環(huán)境信息。環(huán)境以一定的速率讓信息素消失。143.覓食規(guī)則在每只螞蟻能感知的范圍內(nèi)尋找是否有食物，如果有就直接過(guò)去。否則看是否有信息素，并且比較在能感知的范圍內(nèi)哪一點(diǎn)的信息素最多，這樣，它就朝信息素多的地方走，并且每只螞蟻都會(huì)以小概率犯錯(cuò)誤，從而并不是往信息素最多的點(diǎn)移動(dòng)。螞蟻找窩的規(guī)則和上面一樣，只不過(guò)它對(duì)窩的信息素做出反應(yīng)，而對(duì)食物信息素沒(méi)反應(yīng)。154.移動(dòng)規(guī)則每只螞蟻都朝向信息素最多的方向移，并且，當(dāng)周圍沒(méi)有信息素指引的時(shí)候，螞蟻會(huì)按照自己原來(lái)運(yùn)動(dòng)的方向慣性的運(yùn)動(dòng)下去，并且，在運(yùn)動(dòng)的方向有一個(gè)隨機(jī)的小的擾動(dòng)。為了防止螞蟻原地轉(zhuǎn)圈，它會(huì)記住最近剛走過(guò)了哪些點(diǎn)，如果發(fā)現(xiàn)要走的下一點(diǎn)已經(jīng)在最近走過(guò)了，它就會(huì)盡量避開(kāi)。165.避障規(guī)則如果螞蟻要移動(dòng)的方向有障礙物擋住，它會(huì)隨機(jī)的選擇另一個(gè)方向，并且有信息素指引的話，它會(huì)按照覓食的規(guī)則行為。176.播撒信息素規(guī)則每只螞蟻在剛找到食物或者窩的時(shí)候撒發(fā)的信息素最多，并隨著它走遠(yuǎn)的距離，播撒的信息素越來(lái)越少?，F(xiàn)以平面上n個(gè)城市的旅行商問(wèn)題（TravelingSalesmanProblem，TSP）為例說(shuō)明基本蟻群算法模型。旅行商問(wèn)題：一商人去n個(gè)城市銷貨，所有城市走一遍再回到起點(diǎn)，使所走路程最短。TSP在許多工程領(lǐng)域具有廣泛的應(yīng)用價(jià)值，例如電路板布線、VLSI芯片設(shè)計(jì)、機(jī)器人控制、網(wǎng)絡(luò)路由等。隨著城市數(shù)目的增多,問(wèn)題空間將呈指數(shù)級(jí)增長(zhǎng)。TSP問(wèn)題的數(shù)學(xué)描述TSP問(wèn)題表示為一個(gè)N個(gè)城市的有向圖G=（N，A），其中 城市之間距離目標(biāo)函數(shù)為其中，，為城市1,2，…n的一個(gè)排列，。蟻群算法求解TSP下面以TSP為例說(shuō)明基本蟻群算法模型。首先將m只螞蟻隨機(jī)放置在n個(gè)城市，通常

：，m只螞蟻同時(shí)由一個(gè)城市運(yùn)動(dòng)到下一個(gè)城市，逐步完成它們的搜索過(guò)程。整個(gè)算法的迭代過(guò)程以N為刻度，，為預(yù)設(shè)的最大迭代次數(shù)。每次迭代過(guò)程中以t為刻度，，螞蟻k根據(jù)概率轉(zhuǎn)換規(guī)則選擇下一個(gè)城市，由此生成一個(gè)由n個(gè)城市組成的行動(dòng)路線，并伴隨信息素的更新。（2）能見(jiàn)度

定義為距離的倒數(shù)，即

代表由城市i到城市j的啟發(fā)性愿望，距離越短，能見(jiàn)度越大，被選擇的愿望越大，由此引導(dǎo)螞蟻搜索。其信息是固定的。

（3）虛擬信息素

當(dāng)由城市i選擇城市j后，將在ij路徑上留下虛擬信息素，代表由城市i到j(luò)的獲知性愿望，是動(dòng)態(tài)的全局信息，在線實(shí)時(shí)更新。

螞蟻k由城市i轉(zhuǎn)到城市j的決定因素：（1）禁忌列表

該表用于存儲(chǔ)第k只螞蟻在當(dāng)前時(shí)刻已訪問(wèn)過(guò)的所有城市，每只螞蟻在選擇下一個(gè)城市前，先檢索該表來(lái)確定下一步可能選擇的城市是否已經(jīng)走過(guò)，如果走過(guò)就不在選擇范圍內(nèi)，這樣可以避免重復(fù)訪問(wèn)同一個(gè)城市。信息素更新方式體現(xiàn)在信息素的增加和信息素的揮發(fā)兩個(gè)方面。揮發(fā)系數(shù)信息素更新公式如下：表示當(dāng)m個(gè)螞蟻都選擇了下一個(gè)城市后，所有選擇由i到j(luò)的螞蟻在該路徑上遺留的信息素之和表示第k只螞蟻在路徑ij上留下的信息素為預(yù)設(shè)參數(shù)，表示信息素的強(qiáng)度表示第k只螞蟻在t時(shí)刻選擇城市j后經(jīng)過(guò)的所有城市構(gòu)成的路徑長(zhǎng)度其中： 表示ij路徑上的信息素濃度； 是啟發(fā)信息，能見(jiàn)度；

α和β反映了信息素與啟發(fā)信息的相對(duì)重要性； 表示螞蟻k已經(jīng)訪問(wèn)過(guò)的城市列表，禁忌列表。（4）概率轉(zhuǎn)換規(guī)則位于城市i的第k只螞蟻選擇下一個(gè)城市j的概率為:注意：處在同一城市i的兩只螞蟻，即使都按照上述概率選擇下一個(gè)城市，結(jié)果也可能是不同的。系統(tǒng)在上述四個(gè)因素（禁忌列表、能見(jiàn)度、虛擬信息素、概率轉(zhuǎn)換規(guī)則）的控制下，實(shí)現(xiàn)路徑選擇策略和信息素更新策略。上述信息素更新方式與真實(shí)螞蟻覓食過(guò)程最為接近，但是在解決TSP問(wèn)題上，效果并不是特別理想。Dorigo針對(duì)信息素更新策略又給出了三種模型。蟻量系統(tǒng)（Ant-Quantity）蟻密系統(tǒng)（Ant-Density）蟻周系統(tǒng)（Ant-Cycle）三種模型它們的差別在于表達(dá)式

的不同(即更新信息素的方式和更新量不同)。Ant-Quantity和Ant-Density模型都是利用局部信息，即m個(gè)螞蟻都各自選完下一城市后，就對(duì)所走路徑并行進(jìn)行信息素更新，兩者的區(qū)別僅僅在于更新的信息素量有所不同。Ant-Cycle模型是所有螞蟻選擇完所有城市完成一次迭代后，更新所有路徑上的信息素，并且每只螞蟻經(jīng)過(guò)的路徑所更新的信息素是相同的。

蟻量算法（Ant-Quantity）：蟻密算法（Ant-Density）：蟻周算法（Ant-Cycle）：27通過(guò)實(shí)驗(yàn)表明，在這三種算法中：Ant-Cycle算法的效果最好，這是因?yàn)樗玫氖侨中畔?；而其余兩種算法用的是局部信息。這種更新方法很好地保證了殘留信息不至于無(wú)限累積，非最優(yōu)路徑會(huì)逐漸隨時(shí)間推移被忘記。TSP算法流程圖（Ant-Cycle）k是否等于mt是否等于nN是否等于Nmax根據(jù)公式更新信息素記錄當(dāng)前最優(yōu)路徑T+和最優(yōu)路徑長(zhǎng)度L+禁忌表清零輸出最優(yōu)路徑T+和最優(yōu)路徑長(zhǎng)度L+結(jié)束設(shè)置參數(shù)各個(gè)參數(shù)，并計(jì)算各個(gè)城市之間的距離，生成距離矩陣D，生成禁忌列表及存儲(chǔ)最優(yōu)路徑和最優(yōu)路徑長(zhǎng)度的矩陣T+和L+開(kāi)始將m個(gè)螞蟻隨機(jī)分布到n個(gè)城市，并將螞蟻所在的位置存儲(chǔ)到禁忌表中，并令N=0令t=0,N=N+1令k=0,t=t+1令k=k+1第k個(gè)螞蟻根據(jù)公式選擇下一個(gè)城市，并更新禁忌表NNNYYY蟻群算法的誤區(qū)與對(duì)策29誤區(qū)一：利用最大概率確定被選城市。

s40.31s20.49s10.14S30.06輪盤賭法（賭輪選擇法）①在［0,1］區(qū)間內(nèi)產(chǎn)生一個(gè)均勻分布的隨機(jī)數(shù)r。②若r≤q1,則城市x1被選中。③若qk-1<r≤qk(2≤k≤N),則城市xk被選中。其中的qi稱為城市xi(i=1,2,…,n)的積累概率,其計(jì)算公式為對(duì)策一31誤區(qū)二：

Q值的影響不大32對(duì)策二33誤區(qū)三：參數(shù)組合選擇34對(duì)策三3.實(shí)例仿真采用靳潘教授所提出的31個(gè)城市的CTSP（求一條從北京出發(fā)經(jīng)過(guò)中國(guó)31個(gè)省會(huì)城市及直轄市最后又回到北京的最短回路。36下圖對(duì)應(yīng)31個(gè)城市的巡回路線為：北京-福州-南昌-合肥-杭州-南京-西安-臺(tái)北-太原-呼和浩特-沈陽(yáng)-上海-石家莊-長(zhǎng)春-哈爾濱-濟(jì)南-天津-武漢-鄭州-長(zhǎng)沙-銀川-蘭州-廣州-海口-南寧-西寧-成都-烏魯木齊-昆明-拉薩-貴陽(yáng)-北京。從仿真結(jié)果看最優(yōu)解為:15708km。目前，公認(rèn)的TSP問(wèn)題最優(yōu)結(jié)果為15398km，雖然，不完全相等，但是結(jié)果比較相近，這說(shuō)明螞蟻算法雖然不是TSP問(wèn)題的最好算法，但是依據(jù)螞蟻覓食過(guò)程提出的蟻群算法具有一定的可行性。一、蟻群大小一般情況下蟻群中螞蟻的個(gè)數(shù)不超過(guò)TSP圖中節(jié)點(diǎn)的個(gè)數(shù)。二、終止條件

1給定一個(gè)外循環(huán)的最大數(shù)目；

2當(dāng)前最優(yōu)解連續(xù)K次相同而停止，其中K是一個(gè)給定的整數(shù)，表示算法已經(jīng)收斂，不再需要繼續(xù)。蟻群的規(guī)模及停止規(guī)則優(yōu)化問(wèn)題螞蟻覓食問(wèn)題各個(gè)狀態(tài)要遍歷的各個(gè)路徑解螞蟻經(jīng)過(guò)的一條完整路徑最優(yōu)解最短路徑各狀態(tài)的吸引度信息素的濃度狀態(tài)更新信息素更新目標(biāo)函數(shù)路徑長(zhǎng)度螞蟻覓食行為與優(yōu)化問(wèn)題的對(duì)照關(guān)系

①其原理是一種正反饋機(jī)制或稱增強(qiáng)型學(xué)習(xí)系統(tǒng);它通過(guò)【最優(yōu)路徑上螞蟻數(shù)量的增加→信息素強(qiáng)度增加→后來(lái)螞蟻選擇概率增大→最優(yōu)路徑上螞蟻數(shù)量更大增加】達(dá)到最終收斂于最優(yōu)路徑上。

②它是一種通用型隨機(jī)優(yōu)化方法,它吸收了螞蟻的行為特點(diǎn),它是使用人工螞蟻仿真來(lái)求解問(wèn)題。但人工螞蟻決不是對(duì)實(shí)際螞蟻的一種簡(jiǎn)單模擬,它融進(jìn)了人類的智能。具有一定的記憶能力，能夠記憶已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn)。選擇路徑時(shí)不是盲目的。而是按一定規(guī)律有意識(shí)地尋找最短路徑。例如，在TSP問(wèn)題中，可以預(yù)先知道當(dāng)前城市到下一個(gè)目的地的距離。

4.蟻群算法的特點(diǎn)⑤它是一種啟發(fā)式算法,計(jì)算復(fù)雜性為,其中Nc是迭代次數(shù),m是螞蟻數(shù)目,n是目的節(jié)點(diǎn)數(shù)目。③它是一種本質(zhì)上的并行算法。

④它是一種全局優(yōu)化的方法,不僅可用于求解單目標(biāo)優(yōu)化問(wèn)題,而且可用于求解多目標(biāo)優(yōu)化問(wèn)題。

蟻群算法還不像其它的啟發(fā)式算法那樣已形成系統(tǒng)的分析方法和具有堅(jiān)實(shí)的數(shù)