蟻群算法介紹

1、數(shù)學(xué)建模數(shù)學(xué)建模主講人：王成章2前言 通過前面的學(xué)習(xí)，我們可以發(fā)現(xiàn)，智能優(yōu)化算法實(shí)際上是根據(jù)問題的部分已知信息來啟發(fā)式地探索該問題的解決方案，在探索解決方案的過程中將發(fā)現(xiàn)的有關(guān)信息記錄下來，不斷積累和分析，并根據(jù)越來越豐富的已知信息來指導(dǎo)下一步的動(dòng)作并修正以前的步驟，從而獲得在整體上較好的解決方案。 啟發(fā)式計(jì)算方法啟發(fā)式計(jì)算方法3前言(C.)什么是啟發(fā)式算法呢？【定義1】 啟發(fā)式算法是一種基于直觀或經(jīng)驗(yàn)構(gòu)造的算法，在可接受的耗費(fèi)（指計(jì)算時(shí)間、占用空間等）下給出待解決優(yōu)化問題每一實(shí)例的一個(gè)可行解，該可行解與最優(yōu)解的偏離程度未必可事先估計(jì)。【定義2】 啟發(fā)式算法是一種技術(shù)，該技術(shù)使得能在可接受的計(jì)

2、算費(fèi)用內(nèi)去尋找盡可能好的解，但不一定能保證所得解的可行性和最優(yōu)性，甚至在多數(shù)情況下，無法描述所得解與最優(yōu)解的近似程度。4前言(C.)物理啟發(fā)式： 模擬退火算法：模擬固體熔化狀態(tài)下由逐漸冷卻至最終達(dá)到結(jié)晶狀態(tài)的物理過程社會(huì)與文化啟發(fā)： 文化算法 （模擬人類社會(huì)的演化過程） 人口遷移算法 （模擬人口流動(dòng)與人口遷移）5前言(C.)生物啟發(fā)式： 生物啟發(fā)式計(jì)算是指以生物界的各種自然現(xiàn)象或過程為靈感，而提出的一系列啟發(fā)式智能計(jì)算方法。比如： 遺傳算法 人工神經(jīng)網(wǎng)絡(luò)6前言(C.)遺傳算法： 生物進(jìn)化過程是一個(gè)自然，并行，穩(wěn)健的優(yōu)化過程，這一優(yōu)化過程的目的在于使生命體達(dá)到適應(yīng)環(huán)境的最佳結(jié)構(gòu)與效果，而生物種群

3、通過” “優(yōu)勝劣汰”及遺傳變異來達(dá)到進(jìn)化（優(yōu)化）目的的。 7前言(C.e) 還有一類重要的現(xiàn)代智能優(yōu)化算法：群體智能（Swarm Intelligence：SI）算法。 生物學(xué)家研究表明：在這些群居生物中雖然每個(gè)個(gè)體的智能不高，行為簡(jiǎn)單，也不存在集中的指揮，但由這些單個(gè)個(gè)體組成的群體，似乎在某種內(nèi)在規(guī)律的作用下，卻表現(xiàn)出異常復(fù)雜而有序的群體行為。8蟻群算法蟻群：蟻群是自然界中常見的一種生物，人們對(duì)螞蟻的關(guān)注大都是因?yàn)椤跋伻喊峒?，天要下雨”之類的民諺。然而隨著近代仿生學(xué)的發(fā)展，這種似乎微不足道的小東西越來越多地受到學(xué)者們地關(guān)注。螞蟻是一種群居昆蟲，在覓食、清理巢穴等活動(dòng)中，彼此依賴、相互協(xié)作共同

4、完成特定的任務(wù)。就個(gè)體來講，單個(gè)螞蟻的智力和體力是極其有限的，服務(wù)于整個(gè)群落的生存與發(fā)展；就群體來講，蟻群在行為上的分工協(xié)作、在完成任務(wù)過程中所體現(xiàn)的自組織特征等反應(yīng)出蟻群具有較高的智能和自我管理能力，具有很高層次組織性，這使得蟻群能夠完成一些復(fù)雜的任務(wù)。9蟻群算法(C.)自然現(xiàn)象：為了說明蟻群算法的原理，先簡(jiǎn)要介紹一下螞蟻搜尋食物的具體過程。在蟻群尋找食物時(shí)，它們總能找到一條從食物到巢穴之間的最優(yōu)路徑。這是因?yàn)槲浵佋趯ふ衣窂綍r(shí)會(huì)在路徑上釋放出一種特殊的信息素。當(dāng)它們碰到一個(gè)還沒有走過的路口時(shí)就隨機(jī)地挑選一條路徑前行。與此同時(shí)釋放出與路徑長(zhǎng)度有關(guān)的信息素。路徑越長(zhǎng)，釋放的激索濃度越低.當(dāng)后來的

5、螞蟻再次碰到這個(gè)路口的時(shí)候選擇激素濃度較高路徑概率就會(huì)相對(duì)較大。這樣形成一個(gè)正反饋。最優(yōu)路徑上的激索濃度越來越大而其它的路徑上激素濃度卻會(huì)隨著時(shí)間的流逝而消減。最終整個(gè)蟻群會(huì)找出最優(yōu)路徑。 10蟻群算法(C.)自然現(xiàn)象： Goss. S. “雙橋”實(shí)驗(yàn)(1989)AC11蟻群算法(C.)自然現(xiàn)象：AC12蟻群算法(C.)自然現(xiàn)象：AC13蟻群算法(C.) 簡(jiǎn)化的尋食過程： 螞蟻從A點(diǎn)出發(fā)，速度相同，食物在D點(diǎn)，可能隨機(jī)選擇路線ABD或ACD。假設(shè)初始時(shí)每條路線分配一只螞蟻，每個(gè)時(shí)間單位行走一步，本圖為經(jīng)過9個(gè)時(shí)間單位時(shí)的情形：走ABD的螞蟻到達(dá)終點(diǎn)，而走ACD的螞蟻剛好走到C點(diǎn)，為一半路程。1

6、4蟻群算法(C.) 簡(jiǎn)化的尋食過程： 本圖為從開始算起，經(jīng)過18個(gè)時(shí)間單位時(shí)的情形：走ABD的螞蟻到達(dá)終點(diǎn)后得到食物又返回了起點(diǎn)A，而走ACD的螞蟻剛好走到D點(diǎn)。15蟻群算法(C.) 假設(shè)螞蟻每經(jīng)過一處所留下的信息素為一個(gè)單位，則經(jīng)過36個(gè)時(shí)間單位后，所有開始一起出發(fā)的螞蟻都經(jīng)過不同路徑從D點(diǎn)取得了食物，此時(shí)ABD的路線往返了2趟，每一處的信息素為4個(gè)單位，而 ACD的路線往返了一趟，每一處的信息素為2個(gè)單位，其比值為2：1。 尋找食物的過程繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，蟻群在ABD路線上增派一只螞蟻（共2只），而ACD路線上仍然為一只螞蟻。再經(jīng)過36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為1

7、2和4，比值為3：1。 若按以上規(guī)則繼續(xù)，蟻群在ABD路線上再增派一只螞蟻（共3只），而ACD路線上仍然為一只螞蟻。再經(jīng)過36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為24和6，比值為4：1。 若繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，最終所有的螞蟻會(huì)放棄ACD路線，而都選擇ABD路線。這也就是前面所提到的正反饋效應(yīng)。16蟻群算法(C.)蟻群算法： 蟻群算法是對(duì)自然界螞蟻的尋食方式進(jìn)行模似而得出的一種仿生算法。螞蟻在運(yùn)動(dòng)過程中，能夠在它所經(jīng)過的路徑上留下一種稱之為外激素(pheromone)/信息素的物質(zhì)進(jìn)行信息傳遞，而且螞蟻在運(yùn)動(dòng)過程中能夠感知這種物質(zhì)，并以此指導(dǎo)自己的運(yùn)動(dòng)方向，因此由大量螞蟻組成的蟻群

8、集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。17蟻群算法的起源：20世紀(jì)90年代意大利學(xué)者M(jìn)Dorigo，VManiezzo，AColorni等從生物進(jìn)化的機(jī)制中受到啟發(fā)，通過模擬自然界螞蟻搜索路徑的行為，提出來一種新型的模擬進(jìn)化算法 蟻群算法(Ant Colony Optimization: ACO)。蟻群算法是群智能理論研究領(lǐng)域的一種主要算法。用該方法求解TSP問題、分配問題、job-shop調(diào)度問題，取得了較好的試驗(yàn)結(jié)果。雖然研究時(shí)間不長(zhǎng)，但是現(xiàn)在的研究顯示出，蟻群算法在求解復(fù)雜優(yōu)化問題（特別是離散優(yōu)化問題）方面有一定優(yōu)勢(shì)。蟻群算法(C.

9、)18蟻群算法的應(yīng)用領(lǐng)域：這種方法能夠被用于解決大多數(shù)優(yōu)化問題或者能夠轉(zhuǎn)化為優(yōu)化求解的問題?，F(xiàn)在其應(yīng)用領(lǐng)域已擴(kuò)展到多目標(biāo)優(yōu)化、數(shù)據(jù)分類、數(shù)據(jù)聚類、模式識(shí)別、電信管理、生物系統(tǒng)建模、流程規(guī)劃、信號(hào)處理、機(jī)器人控制、決策支持以及仿真和系統(tǒng)辯識(shí)等方面，群智能理論和方法為解決這類應(yīng)用問題提供了新的途徑。蟻群算法(C.)19蟻群算法的研究背景：與大多數(shù)基于梯度的應(yīng)用優(yōu)化算法不同，群智能依靠的是概率搜索算法。雖然概率搜索算法通常要采用較多的評(píng)價(jià)函數(shù)，但是與梯度方法及傳統(tǒng)的演化算法相比，其優(yōu)點(diǎn)還是顯著的 ，主要表現(xiàn)在以下幾個(gè)方面：無集中控制約束，不會(huì)因個(gè)別個(gè)體的故障影響整個(gè)問題 的求解，確保了系統(tǒng)具備更強(qiáng)的

10、魯棒性 以非直接的信息交流方式確保了系統(tǒng)的擴(kuò)展性 并行分布式算法模型，可充分利用多處理器 對(duì)問題定義的連續(xù)性無特殊要求 算法實(shí)現(xiàn)簡(jiǎn)單 蟻群算法(C.)20蟻群算法的研究背景：群智能方法易于實(shí)現(xiàn)，算法中僅涉及各種基本的數(shù)學(xué)操作，其數(shù)據(jù)處理過程對(duì)CPU和內(nèi)存的要求也不高。而且，這種方法只需目標(biāo)函數(shù)的輸出值，而無需其梯度信息。已完成的群智能理論和應(yīng)用方法研究證明群智能方法是一種能夠有效解決大多數(shù)全局優(yōu)化問題的新方法。更為重要是，群智能潛在的并行性和分布式特點(diǎn)為處理大量的以數(shù)據(jù)庫(kù)形式存在的數(shù)據(jù)提供了技術(shù)保證。蟻群算法(C.)21蟻群算法的研究背景：最初提出的AS有三種版本：Ant-density、An

11、t-quantity和Ant-cycle。在Ant-density和Ant-quantity中螞蟻在兩個(gè)位置節(jié)點(diǎn)間每移動(dòng)一次后即更新信息素，而在Ant-cycle中當(dāng)所有的螞蟻都完成了自己的行程后才對(duì)信息素進(jìn)行更新，而且每個(gè)螞蟻所釋放的信息素被表達(dá)為反映相應(yīng)行程質(zhì)量的函數(shù)。蟻群算法(C.)22蟻群算法的原理：蟻群的行為是整體協(xié)作，相互分工，以一個(gè)整體去解決一些對(duì)單個(gè)螞蟻看上去是不可能完成的任務(wù)。蟻群算法是對(duì)自然界螞蟻的尋食方式進(jìn)行模似而得出的一種仿生算法。為了根據(jù)自然界螞蟻的行為設(shè)計(jì)蟻群算法，首先要定義一種人工螞蟻。一方面，人工蟻群是真實(shí)蟻群行為特征的一種抽象，將真實(shí)蟻群尋食行為中核心的部分抽

12、象了出來賦給了人工蟻群。另一方面，由于人工蟻群需要解決實(shí)際的復(fù)雜優(yōu)化問題，為了能使蟻群算法更有效，人工蟻群還具備了真實(shí)蟻群所不具備的本領(lǐng)。蟻群算法(C.)23人工蟻群與真實(shí)蟻群之間的共同點(diǎn)：人工蟻群和真實(shí)蟻群一樣，都是相互合作的群體。蟻群中的每只螞蟻都能建立一個(gè)解，螞蟻個(gè)體通過相互的協(xié)作在全局范圍內(nèi)找出問題較優(yōu)的解。人工蟻群和真實(shí)蟻群有著共同的任務(wù)：尋找起點(diǎn)(蟻穴)到終點(diǎn)(食物源)的最短路經(jīng)(最優(yōu)目標(biāo))。人工蟻群和真實(shí)蟻群都是通過信息素進(jìn)行間接通訊的。在人工蟻群算法中信息素軌跡是通過狀態(tài)變量來表示的。人工蟻群算法通過修改狀態(tài)變量矩陣中元素的值來模擬真實(shí)蟻群中信息素的更新過程。蟻群算法(C.)2

13、4人工蟻群與真實(shí)蟻群之間的共同點(diǎn)：人工蟻群還應(yīng)用了真實(shí)蟻群尋食過程中的正反饋機(jī)制。蟻群的正反饋機(jī)制使得問題的解向著最優(yōu)的方向不斷進(jìn)化。人工蟻群和真實(shí)蟻群都存在著一種信息素?fù)]發(fā)機(jī)制。這種機(jī)制可以使得螞蟻逐漸忘記過去，不會(huì)受過去經(jīng)驗(yàn)的過分束縛，有利于向著新的方向搜索，避免過早的收斂。人工蟻群和真實(shí)蟻群都是基于概率轉(zhuǎn)移的局部搜索策略。螞蟻在轉(zhuǎn)移時(shí)，所應(yīng)用的策略在時(shí)間和空間上是完全局部的。蟻群算法(C.)25人工蟻群的特有功能：人工蟻群算法存在于一個(gè)離散的空間中，它們的移動(dòng)是一個(gè)狀態(tài)到另一個(gè)狀態(tài)的轉(zhuǎn)換。人工蟻群算法具有一個(gè)記憶它本身過去行為的內(nèi)在狀態(tài)。人工螞蟻釋放信息素的量，是由螞蟻所建立的問題解決方

14、案優(yōu)劣程度函數(shù)決定的。蟻群算法更新信息量的時(shí)機(jī)是隨著不同問題而變化，不反映真實(shí)蟻群的行為。為了改善系統(tǒng)的性能，人工蟻群算法可以增加一些性能，如：前瞻性、局部?jī)?yōu)化、原路返回等。蟻群算法(C.)26下面以TSP問題為例，詳細(xì)說明蟻群算法的流程：TSP問題描述：TSP問題可以表示為一個(gè)N個(gè)城市的有向圖 G=(N, A)其中，N=1,2,3,n，A=(i, j)| i, j N城市之間的距離矩陣為：(dij)nnm 為蟻群中螞蟻的數(shù)量ij(t)為t 時(shí)刻邊弧(i, j) 的軌跡強(qiáng)度(即ij 連線上殘留的信息量)，且設(shè) ij(0) = c ( c 為常數(shù)，可以設(shè)為邊矩陣A行列式的倒數(shù))； ij (t)

15、為t 時(shí)刻邊弧(i, j)的能見度，反映由城市i 轉(zhuǎn)移到城市j 的期望程度。蟻群算法(C.)27下面以TSP問題為例，詳細(xì)說明蟻群算法的流程：螞蟻k (k = 1,2,m) 在運(yùn)動(dòng)過程中根據(jù)各條路徑上的信息量決定轉(zhuǎn)移方向。與真實(shí)蟻群系統(tǒng)不同，人工蟻群系統(tǒng)具有一定的記憶功能。隨著時(shí)間的推移，以前留下的信息逐漸消逝，經(jīng)n 個(gè)時(shí)刻，螞蟻完成一次循環(huán)，各路徑上信息量要作調(diào)整。人工蟻群系統(tǒng)模型：1）設(shè)人工蟻群在并行地搜索TSP 的解，并通過一種信息素做媒介相互通信，在每個(gè)結(jié)點(diǎn)上且和該結(jié)點(diǎn)相連的邊上以信息素量做搜索下一結(jié)點(diǎn)的試探依據(jù)，直到找到一個(gè)TSP 問題的可行解。蟻群算法(C.)28下面以TSP問題為

16、例，詳細(xì)說明蟻群算法的流程：人工蟻群系統(tǒng)模型：2）在時(shí)刻t 人工螞蟻k 由位置i 轉(zhuǎn)移至位置j 的轉(zhuǎn)移概率為：蟻群算法(C.)29下面以TSP問題為例，詳細(xì)說明蟻群算法的流程：人工蟻群系統(tǒng)模型：3）當(dāng)m 個(gè)人工螞蟻式找到了可行解，則將各邊的信息量用下式修改。即調(diào)整信息量的軌跡強(qiáng)度更新方程為：蟻群算法(C.)30下面以TSP問題為例，詳細(xì)說明蟻群算法的流程：對(duì)上述系統(tǒng)模型，采用人工蟻群方法求解的算法步驟可歸結(jié)為：蟻群算法(C.)31下面以TSP問題為例，詳細(xì)說明蟻群算法的流程：對(duì)上述系統(tǒng)模型，采用人工蟻群方法求解的算法步驟可歸結(jié)為：說明：若為了簡(jiǎn)化計(jì)算，增加處理較大規(guī)模的TSP 問題的能力，則可

17、將軌跡更新方程修改為蟻群算法(C.)32蟻群算法的分析補(bǔ)充：算法中包括信息素更新的過程：信息素?fù)]發(fā)： 信息素痕跡的揮發(fā)過程是每個(gè)連接上的信息素痕跡的濃度自動(dòng)逐漸減弱的過程，這個(gè)揮發(fā)過程主要用于避免算法過快地向局部最優(yōu)區(qū)域集中，有助于搜索區(qū)域的擴(kuò)展。 信息素增強(qiáng)：增強(qiáng)過程是蟻群優(yōu)化算法中可選的部分。這種方式可以實(shí)現(xiàn)由單個(gè)螞蟻無法實(shí)現(xiàn)的集中行動(dòng)，增強(qiáng)過程體現(xiàn)在觀察蟻群（m只螞蟻）中每只螞蟻所找到的路徑，并選擇其中最優(yōu)路徑上的弧進(jìn)行信息素的增強(qiáng)，揮發(fā)過程是所有弧都進(jìn)行的，不與螞蟻數(shù)量相關(guān)。這種增強(qiáng)過程中進(jìn)行的信息素更新稱為離線的信息素更新。蟻群算法(C.)33蟻群算法的分析補(bǔ)充：人工螞蟻要實(shí)現(xiàn)的四個(gè)

18、功能：1)基于概率的局部搜索策略：實(shí)際問題中，螞蟻經(jīng)常要從一個(gè)狀態(tài)點(diǎn)移動(dòng)到另一個(gè)狀態(tài)點(diǎn)。經(jīng)過這樣有限步的移動(dòng)，每只螞蟻都建立了一個(gè)問題的解。在每一步的移動(dòng)過程中，螞蟻應(yīng)用基于概率的局部搜索策略選擇移動(dòng)方向。這個(gè)策略主要基于螞蟻的記憶以及信息素的濃度，有時(shí)還有具體問題的局部信息等。2)螞蟻的記憶：螞蟻的記憶存儲(chǔ)了關(guān)于螞蟻過去的信息。這些記憶的信息可以用于計(jì)算所解決方案的價(jià)值或每一步移動(dòng)的貢獻(xiàn)。在一些組和優(yōu)化問題中，利用螞蟻的記憶可以正確引導(dǎo)螞蟻構(gòu)建方案的解。蟻群算法(C.)34蟻群算法的分析補(bǔ)充：人工螞蟻要實(shí)現(xiàn)的四個(gè)功能：2)螞蟻的記憶(續(xù))：比如在TSP問題中，利用螞蟻的記憶可以記錄螞蟻已經(jīng)走

19、過的城市，并將其置于一個(gè)禁忌表中。這樣就可以避免螞蟻重復(fù)訪問這些城市，使得螞蟻構(gòu)造出來的解可以滿足TSP問題的約束條件。所以，螞蟻可以只使用關(guān)于局部的信息，就可以構(gòu)造出問題的解。3)釋放信息素：螞蟻之間的協(xié)作是通過信息素來完成，信息素給蟻群算法產(chǎn)生了正反饋的重要作用。螞蟻釋放信息素的量與螞蟻建立解決方案的優(yōu)劣程度成正比。蟻群算法(C.)35蟻群算法的分析補(bǔ)充：人工螞蟻要實(shí)現(xiàn)的四個(gè)功能：4)螞蟻決策表：螞蟻決策表是由信息素函數(shù)與啟發(fā)函數(shù)共同決定的，它是一種概率表。螞蟻使用這個(gè)表來指導(dǎo)其搜索最有吸引力的移動(dòng)方向。在螞蟻移動(dòng)時(shí)，不僅基于概率的局部搜索策略，還增加了信息素?fù)]發(fā)機(jī)制，這樣就可以避免過早收

20、斂，出現(xiàn)早熟現(xiàn)象?？傊?，蟻群算法就是通過螞蟻個(gè)體功能來構(gòu)造解，并釋放信息素來協(xié)調(diào)，最終找到一個(gè)較優(yōu)的解決方案。蟻群算法(C.)36蟻群算法的技術(shù)問題：解的表達(dá)形式與算法的實(shí)現(xiàn)每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定蟻群的規(guī)模和停止規(guī)則信息素的更改蟻群算法(C.)37蟻群算法的技術(shù)問題：解的表達(dá)形式與算法的實(shí)現(xiàn)基于TSP問題的蟻群優(yōu)化算法，其解的形式是所有城市的一個(gè)排列（閉圈，這種情況下誰(shuí)在第一并不重要），信息素痕跡按每個(gè)弧記錄。而對(duì)于一般以順序作為解的優(yōu)化問題，誰(shuí)在第一是很重要的。蟻群算法在解決這類問題時(shí)，只需要建立一個(gè)虛擬的始終點(diǎn)，就可以把TSP問題的解法推廣，用于諸多的優(yōu)化問題。每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定蟻群的規(guī)模和停止規(guī)則信息素的更改蟻群算法(C.)38蟻群算法的技術(shù)問題：解的表達(dá)形式與算法的實(shí)現(xiàn)每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定算法中需要記憶的信息有三部分：第一部分信息是存在每個(gè)節(jié)點(diǎn)的路由表數(shù)據(jù)結(jié)構(gòu)；第二部分需要記憶的信息是每個(gè)螞蟻的記憶表中存儲(chǔ)著的自身的歷史信息；第三部分為問題的約束條件。殘留信息的相對(duì)重要程度和預(yù)見值的相對(duì)重要程度體現(xiàn)了相關(guān)信息痕跡和預(yù)見度對(duì)螞蟻決策的相對(duì)影響。求解TSP問題時(shí)，推薦參數(shù)的最佳設(shè)置為：=1， =5，=0.5。蟻群的規(guī)模和停止規(guī)則信息素的更改蟻群算法(C.)39蟻群算法的技術(shù)問題：解的表達(dá)形式與算法的實(shí)現(xiàn)每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定蟻群的規(guī)模和