四蟻群算法的基本原理

1、四.蟻群算法基本原理引言:各個(gè)螞蟻在沒有事先告訴他們食物在什么地方的前提下開始尋找食物。當(dāng) 一只找到食物以后，它會(huì)向環(huán)境釋放一種揮發(fā)性分泌物pheromone (稱為信息素, 該物質(zhì)隨著時(shí)間的推移會(huì)逐漸揮發(fā)消失，信息素濃度的大小表征路徑的遠(yuǎn)近)來 實(shí)現(xiàn)的，吸引其他的螞蟻過來，這樣越來越多的螞蟻會(huì)找到食物。有些螞蟻并 沒有象其它螞蟻一樣總重復(fù)同樣的路，他們會(huì)另辟蹊徑，如果另開辟的道路比 原來的其他道路更短，那么，漸漸地，更多的螞蟻被吸引到這條較短的路上來。 最后，經(jīng)過一段時(shí)間運(yùn)行，可能會(huì)出現(xiàn)一條最短的路徑被大多數(shù)螞蟻重復(fù)著。 這就是要講的蟻群算法。蟻群算法蟻群算法(ant colony opti

2、mization, ACO)，又稱螞蟻算法，是一種用來 在圖中尋找優(yōu)化路徑的機(jī)率型算法。它由Marco Dorigo于1992年在他的博士 論文中提出，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。蟻群算法 是一種模擬進(jìn)化算法，初步的研究表明該算法具有許多優(yōu)良的性質(zhì)。針對PID 控制器參數(shù)優(yōu)化設(shè)計(jì)問題，將蟻群算法設(shè)計(jì)的結(jié)果與遺傳算法設(shè)計(jì)的結(jié)果進(jìn)行 了比較，數(shù)值仿真結(jié)果表明，蟻群算法具有一種新的模擬進(jìn)化優(yōu)化方法的有效 性和應(yīng)用價(jià)值。蟻群算法原理蟻群優(yōu)化算法是模擬螞蟻覓食的原理，設(shè)計(jì)出的一種群集智能算法。螞蟻 在覓食過程中能夠在其經(jīng)過的路徑上留下一種稱之為信息素的物質(zhì)，并在覓食 過程中能夠感知這

3、種物質(zhì)的強(qiáng)度，并指導(dǎo)自己行動(dòng)方向，它們總是朝著該物質(zhì) 強(qiáng)度高的方向移動(dòng)，因此大量螞蟻組成的集體覓食就表現(xiàn)為一種對信息素的正 反饋現(xiàn)象。某一條路徑越短，路徑上經(jīng)過的螞蟻越多，其信息素遺留的也就越 多，信息素的濃度也就越高，螞蟻選擇這條路徑的幾率也就越高，由此構(gòu)成的 正反饋過程，從而逐漸的逼近最優(yōu)路徑，找到最優(yōu)路徑。螞蟻在覓食過程時(shí)，是以信息素作為媒介而間接進(jìn)行信息交流，當(dāng)螞蟻從 食物源走到蟻穴，或者從蟻穴走到食物源時(shí)，都會(huì)在經(jīng)過的路徑上釋放信息素， 從而形成了一條含有信息素的路徑，螞蟻可以感覺出路徑上信息素濃度的大小，并且以較高的概率選擇信息素濃度較高的路經(jīng)。蟻群算法原理優(yōu)化過程的本質(zhì)選擇機(jī)制：

4、信息素越多的路徑，被選擇的概率越大。更新機(jī)制：路徑上面的信息素會(huì)隨螞蟻的經(jīng)過而增長，而且同時(shí)也隨時(shí) 間的推移逐漸揮發(fā)消失。協(xié)調(diào)機(jī)制：螞蟻間實(shí)際上是通過分泌物來互相通信、協(xié)同工作的。蟻群算法正是充分利用了選擇、更新和協(xié)調(diào)的優(yōu)化機(jī)制，即通過個(gè)體之間的信 息交流與相互協(xié)作最終找到最優(yōu)解，使它具有很強(qiáng)的發(fā)現(xiàn)較優(yōu)解的能力?；谝陨蠙C(jī)制編寫的程序的核心代碼可能不過上百行，卻完成了類似于學(xué)習(xí)的 過程。原因就是所謂的自組織理論，簡單規(guī)則的涌現(xiàn)。事實(shí)上，每只螞蟻并不 是像我們想象的需要知道整個(gè)世界的信息，他們其實(shí)只關(guān)心很小范圍內(nèi)的眼前 信息，而且根據(jù)這些局部信息利用幾條簡單的規(guī)則進(jìn)行決策，但是，當(dāng)集群里 有無數(shù)

5、螞蟻的時(shí)候，復(fù)雜性的行為就會(huì)凸現(xiàn)出來。這就是人工生命、復(fù)雜性科 學(xué)解釋的規(guī)律！蟻群算法原則的規(guī)則1、范圍：螞蟻觀察到的范圍是一個(gè)方格世界，螞蟻有一個(gè)參數(shù)為速度半徑（一般是3）， 那么它能觀察到的范圍就是3*3個(gè)方格世界，并且能移動(dòng)的距離也在這個(gè)范圍 之內(nèi)。2、環(huán)境：螞蟻所在的環(huán)境是一個(gè)虛擬的世界，其中有障礙物，有別的螞蟻，還有信 息素，信息素有兩種，一種是找到食物的螞蟻灑下的食物信息素，一種是找到 窩的螞蟻灑下的窩的信息素。每個(gè)螞蟻都僅僅能感知它范圍內(nèi)的環(huán)境信息。環(huán) 境以一定的速率讓信息素消失。3、覓食規(guī)則：在每只螞蟻能感知的范圍內(nèi)尋找是否有食物，如果有就直接過去。否則看 是否有信息素，并且比

6、較在能感知的范圍內(nèi)哪一點(diǎn)的信息素最多，這樣，它就 朝信息素多的地方走，并且每只螞蟻多會(huì)以小概率犯錯(cuò)誤，從而并不是往信息 素最多的點(diǎn)移動(dòng)。螞蟻找窩的規(guī)則和上面一樣，只不過它對窩的信息素做出反應(yīng)，而對食物信息素沒反應(yīng)。4、移動(dòng)規(guī)則：每只螞蟻都朝向信息素最多的方向移，并且，當(dāng)周圍沒有信息素指引的時(shí) 候，螞蟻會(huì)按照自己原來運(yùn)動(dòng)的方向慣性的運(yùn)動(dòng)下去，并且，在運(yùn)動(dòng)的方向有 一個(gè)隨機(jī)的小的擾動(dòng)。為了防止螞蟻原地轉(zhuǎn)圈，它會(huì)記住最近剛走過了哪些點(diǎn)， 如果發(fā)現(xiàn)要走的下一點(diǎn)已經(jīng)在最近走過了，它就會(huì)盡量避開。5、避障規(guī)則：如果螞蟻要移動(dòng)的方向有障礙物擋住，它會(huì)隨機(jī)的選擇另一個(gè)方向，并且 有信息素指引的話，它會(huì)按照覓食

7、的規(guī)則行為。6、播撒信息素規(guī)則：每只螞蟻在剛找到食物或者窩的時(shí)候撒發(fā)的信息素最多，并隨著它走遠(yuǎn)的 距離，播撒的信息素越來越少。根據(jù)這幾條規(guī)則，螞蟻之間并沒有直接的關(guān)系，但是每只螞蟻都和環(huán)境發(fā) 生交互，而通過信息素這個(gè)紐帶，實(shí)際上把各個(gè)螞蟻之間關(guān)聯(lián)起來了。比如， 當(dāng)一只螞蟻找到了食物，它并沒有直接告訴其它螞蟻這兒有食物，而是向環(huán)境 播撒信息素，當(dāng)其它的螞蟻經(jīng)過它附近的時(shí)候，就會(huì)感覺到信息素的存在，進(jìn) 而根據(jù)信息素的指引找到了食物。蟻群算法的特點(diǎn)：是一種自組織的算法：在系統(tǒng)論中，自組織和它組織是組織的兩個(gè)基本 分類，其區(qū)別在于組織力或組織指令是來自于系統(tǒng)的內(nèi)部還是來自于系統(tǒng)的外 部，來自于系統(tǒng)內(nèi)部

8、的是自組織，來自于系統(tǒng)外部的是他組織。是一種本質(zhì)上并行的算法：不僅增加了算法的可靠性，也使得算法具有 較強(qiáng)的全局搜索能力。是一種本質(zhì)上并行的算法：正反饋是螞蟻算法的重要特征，它使得算法 演化過程得以進(jìn)行。具有較強(qiáng)的魯棒性：蟻群算法的參數(shù)數(shù)目少，設(shè)置簡單，易于蟻群算法 應(yīng)用到其它組合優(yōu)化問題的求解。蟻群算法原理的應(yīng)用蟻群優(yōu)化算法最初用于解決TSP問題，經(jīng)過多年的發(fā)展，已經(jīng)陸續(xù)滲透到 其他領(lǐng)域中，比如圖著色問題、大規(guī)模集成電路設(shè)計(jì)、通訊網(wǎng)絡(luò)中的路由問題 以及負(fù)載平衡問題、車輛調(diào)度問題等。蟻群算法在若干領(lǐng)域己獲得成功的應(yīng)用， 其中最成功的是在組合優(yōu)化問題中的應(yīng)用。蟻群算法的應(yīng)用進(jìn)展以蟻群算法為代表的

9、蟻群智能已成為當(dāng)今分布式人工 智能研究的一個(gè)熱點(diǎn)，許多源于蜂群和蟻群模型設(shè)計(jì)的算法己越來越多地被應(yīng) 用于企業(yè)的運(yùn)轉(zhuǎn)模式的研究。美國五角大樓正在資助關(guān)于群智能系統(tǒng)的研究工作-群體戰(zhàn)略(Swarm Strategy)，它的一個(gè)實(shí)戰(zhàn)用途是通過運(yùn)用成群的空中無人駕駛飛行器和地面車 輛來轉(zhuǎn)移敵人的注意力，讓自己的軍隊(duì)在敵人后方不被察覺地安全進(jìn)行。英國電信公司和美國世界通信公司以電子螞蟻為基礎(chǔ)，對新的電信網(wǎng)絡(luò)管 理方法進(jìn)行了試驗(yàn)。群智能還被應(yīng)用于工廠生產(chǎn)計(jì)劃的制定和運(yùn)輸部門的后勤管理。美國太平 洋西南航空公司采用了一種直接源于螞蟻行為研究成果的運(yùn)輸管理軟件，結(jié)果 每年至少節(jié)約了 1000萬美元的費(fèi)用開支。

10、英國聯(lián)合利華公司己率先利用群智能 技術(shù)改善其一家牙膏廠的運(yùn)轉(zhuǎn)情況。美國通用汽車公司、法國液氣公司、荷蘭 公路交通部和美國一些移民事務(wù)機(jī)構(gòu)也都采用這種技術(shù)來改善其運(yùn)轉(zhuǎn)的機(jī)能。鑒于群智能廣闊的應(yīng)用前景，美國和歐盟均于近幾年開始出資資助基于群 智能模擬的相關(guān)研究項(xiàng)目，并在一些院校開設(shè)群體智能的相關(guān)課程。國內(nèi)，國 家自然科學(xué)基金”十五”期間學(xué)科交叉類優(yōu)先資助領(lǐng)域中的認(rèn)知科學(xué)及其信息 處理的研究內(nèi)容中也明確列出了群智能領(lǐng)域的進(jìn)化、自適應(yīng)與現(xiàn)場認(rèn)知主題。 總結(jié)：蟻群算法是近年來產(chǎn)生的一種源于大自然生物世界的新的啟發(fā)式優(yōu)化方 法。通過以上對蟻群算法的基本原理及其實(shí)際應(yīng)用的介紹可以發(fā)現(xiàn)該算法有如 下主要特點(diǎn):a.正反饋機(jī)制:經(jīng)過螞蟻越多的路徑，后續(xù)螞蟻選擇該路徑的可能 性就越大,通過信息素的不斷更新最終收斂于最優(yōu)路徑上。b.較強(qiáng)的通用性:算 法模型只需做很少修改就可運(yùn)用于別的組合優(yōu)化問題。c.分布式并行計(jì)算能力: 算法在全局的多點(diǎn)同時(shí)進(jìn)行解的搜索，具有本質(zhì)上的并行性，易于并