蟻群算法最全集講解學(xué)習(xí)

1、蟻群算法最全集 算法的背景與意義算法的背景與意義 一國(guó)內(nèi)外研究現(xiàn)狀國(guó)內(nèi)外研究現(xiàn)狀二 研究?jī)?nèi)容與方法研究?jī)?nèi)容與方法三蟻群算法的應(yīng)用蟻群算法的應(yīng)用四算法背景與意義背景2001年至今1996年-2001年意大利學(xué)者Dorigo1991年啟發(fā)各種改進(jìn)算法的提出，應(yīng)用領(lǐng)域更廣各種改進(jìn)算法的提出，應(yīng)用領(lǐng)域更廣 引起學(xué)者關(guān)注，在應(yīng)用領(lǐng)域得到拓寬ACO首次被系統(tǒng)的提出首次被系統(tǒng)的提出自然界中真實(shí)蟻群集體行為Macro Dorigou 從自然界中蟻群的的覓食行為中受啟發(fā)， 于1991年，由意大利學(xué)者M(jìn).Dorigo在其博士論文中提出，并成功的解決了旅行商(TSP)問題 。針對(duì)該算法的不足，一些學(xué)者提出了許多改進(jìn)

2、的蟻群優(yōu)化算法，如蟻群系統(tǒng)，最大-最小螞蟻系統(tǒng)，最優(yōu)保留蟻群系統(tǒng)等。近年來，一些學(xué)者提出了蟻群優(yōu)化元啟發(fā)式這一求解復(fù)雜問題的統(tǒng)一框架，這一框架為蟻群優(yōu)化算法的理論研究和設(shè)計(jì)提供了技術(shù)上的保障。u 我國(guó)最早研究蟻群算法的是東北大學(xué)的張紀(jì)會(huì)博士和徐心和教授。背景有學(xué)者通過對(duì)比實(shí)驗(yàn)發(fā)現(xiàn)，在組合優(yōu)化問題中，蟻群算法的優(yōu)化性能要好于遺傳算法等算法。蟻群算法是一種基于種群的啟發(fā)式搜索算法 。蟻群算法廣泛應(yīng)用于求解TSP問題，Job-Shop調(diào)度問題，二次指派問題，背包問題等。蟻群算法蟻群算法 是一種很有發(fā)展前景的優(yōu)化算法 意義u 目前，蟻群算法己經(jīng)成為一個(gè)備受關(guān)注的研究熱點(diǎn)和前沿性課題。人們對(duì)蟻群算法的研

3、究已經(jīng)由當(dāng)初的TSP領(lǐng)域滲透到多個(gè)應(yīng)用領(lǐng)域，由解決一維靜態(tài)優(yōu)化問題一維靜態(tài)優(yōu)化問題發(fā)展到解決多維動(dòng)態(tài)組合優(yōu)化多維動(dòng)態(tài)組合優(yōu)化問題，由離散域范圍內(nèi)研究逐漸拓展到了連續(xù)域范圍內(nèi)研究。同時(shí)在蟻群算法的模型改進(jìn)以及其他仿生優(yōu)化算法的融合方面也取得了相當(dāng)豐富的研究成果，從而使這種新興的仿生優(yōu)化算法展現(xiàn)出前所未有的生機(jī)。u 從當(dāng)前可以檢索到的文獻(xiàn)情況看，研究和應(yīng)用蟻群優(yōu)化算法的學(xué)者主要集中在比利時(shí)，意大利，英國(guó)，法國(guó)和德國(guó)等歐洲國(guó)家。日本和美國(guó)在這兩年也開始啟動(dòng)對(duì)蟻群算法的研究。目前，蟻群優(yōu)化算法在啟發(fā)式方法范疇內(nèi)已逐漸成為一個(gè)獨(dú)立的分支。u 盡管蟻群優(yōu)化的嚴(yán)格理論基礎(chǔ)尚未奠定，國(guó)內(nèi)外的有關(guān)研究仍停留在實(shí)

4、驗(yàn)探索階段，但從當(dāng)前的應(yīng)用效果來看，這種新型的尋優(yōu)思想無(wú)疑是具有十分光明的前景，更多深入細(xì)致的工作還有待于進(jìn)一步展開。國(guó)內(nèi)外研究現(xiàn)狀o 蟻群算法(ant colony optimization, ACO)，又稱螞蟻算法，是一種用來在圖中尋找優(yōu)化路徑的機(jī)率型算法。它由Marco Dorigo于1992年在他的博士論文中提出，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。 什么是蟻群算法o 信息素：信息素多的地方顯然經(jīng)過這里的螞蟻多，因而會(huì)有更多的螞蟻聚集過來。o 正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。螞蟻如何找到最短路徑o當(dāng)螞蟻沿著一條路到達(dá)終點(diǎn)以后會(huì)馬上返回來

5、，這樣，短的路螞蟻來回一次的時(shí)間就短，這也意味著重復(fù)的頻率就快，因而在單位時(shí)間里走過的螞蟻數(shù)目就多，灑下的信息素自然也會(huì)多，自然會(huì)有更多的螞蟻被吸引過來，從而灑下更多的信息素；而長(zhǎng)的路正相反，因此，越來越多地螞蟻聚集到較短的路徑上來，最短的路徑就近似找到了。蟻群算法的基本思想螞蟻系統(tǒng)是最早的蟻群優(yōu)化算法。螞蟻算法在解決一些小規(guī)模的螞蟻系統(tǒng)是最早的蟻群優(yōu)化算法。螞蟻算法在解決一些小規(guī)模的TSPTSP問題時(shí)的表現(xiàn)尚可令人滿意。但隨著問題規(guī)模的擴(kuò)大，螞蟻系問題時(shí)的表現(xiàn)尚可令人滿意。但隨著問題規(guī)模的擴(kuò)大，螞蟻系統(tǒng)很難在可接受的循環(huán)次數(shù)內(nèi)找出最優(yōu)解。統(tǒng)很難在可接受的循環(huán)次數(shù)內(nèi)找出最優(yōu)解。蟻群系統(tǒng)做了三個(gè)

6、方面的改進(jìn)：狀態(tài)轉(zhuǎn)移規(guī)則為更好更合理地利用新路徑和利用關(guān)于問題的先驗(yàn)知識(shí)提供了方法；全局更新規(guī)則只應(yīng)用于最優(yōu)的螞蟻路徑上；在建立問題解決方案的過程中，應(yīng)用局部信息素更新規(guī)則。蟻群算法將螞蟻的搜索行為集中到最優(yōu)解的附近可以提高解的質(zhì)量和收斂速度，從而改進(jìn)算法的性能。但這種搜索方式會(huì)使早熟收斂行為更容易發(fā)生。 MMAS能將這種搜索方式和一種能夠有效避免早熟收斂的機(jī)制結(jié)合在一起，從而使算法獲得最優(yōu)的性能1.基本蟻群算法基本蟻群算法2.蟻群系統(tǒng)蟻群系統(tǒng)3.最大最大-最小螞蟻系統(tǒng)最小螞蟻系統(tǒng)基本蟻群算法以及改進(jìn)算法基本蟻群算法o 螞蟻k(k=1,2，,m)根據(jù)各個(gè)城市間連接路徑上的信息素濃度決定其下一個(gè)

7、訪問城市，設(shè)Pijk(t)表示t時(shí)刻螞蟻k從城市i轉(zhuǎn)移到城市j的概率，其計(jì)算公式為： ( ) ( , ) ( , ),( ) ( , ) ( , )( , )(1)0,kkks Jii ji jif jJii si sPi jotherwiseo 其中， 表示從城市i可以直接到達(dá)的且又不在螞蟻訪問過的城市序列 中的城市集合， 是一個(gè)啟發(fā)式信息，通常由 直接計(jì)算， 表示邊(i,j)上的信息素量。 由公式（1）可知，長(zhǎng)度越短、信息素濃度越大的路徑被螞蟻選擇的概率越大。 和 是兩個(gè)預(yù)先設(shè)置的參數(shù)，用來控制啟發(fā)式信息（路徑的能見度）與信息濃度（路徑的軌跡）作用的權(quán)重關(guān)系。當(dāng) 時(shí)，算法演變成傳統(tǒng)的隨機(jī)貪

8、婪算法，最鄰近城市被選種的概率最大，當(dāng) 時(shí)，螞蟻完全只根據(jù)信息度濃度確定路徑，算法將快速收斂，這樣構(gòu)建出的最優(yōu)路徑往往與實(shí)際目標(biāo)有著較大的差異，算法的性能比較糟糕，實(shí)驗(yàn)表明，在AS中設(shè)置 比較合適。( )kJikR( , )i j( ,)1 /iji jd( , )i j001 2,a 2 5基本蟻群算法o信息更新公式為：1(1)(1)( ),01ijijijnkijijktt o 在算法初始化時(shí)，問題空間中所有邊上的信息素都被初始化為 ，如果 太小，算法容易早熟，即螞蟻很快就完部集中在一個(gè)局部最優(yōu)的路徑上，反之，如果 太大，信息素對(duì)搜索方向的指導(dǎo)作用太低，也會(huì)影響算法的性能。對(duì)AS來說，我們

9、使用 ，n是螞蟻的個(gè)數(shù)， 是由貪婪算法構(gòu)造的路徑長(zhǎng)度。00/nn CnC00基本蟻群算法o 信息素更新的每一輪中，問題空間中的所有路徑上的信息素都會(huì)發(fā)生蒸發(fā)，信息素蒸發(fā)是自然界本身固有的特征，在算法中能避免信息素的無(wú)限積累，使得算法可以快速丟棄之前構(gòu)建過的較差路徑。隨后所有的螞蟻根據(jù)自己構(gòu)建路徑長(zhǎng)度在它們本輪經(jīng)過的邊釋放信息素。螞蟻構(gòu)建的路徑越短、釋放的信息素就越多；一條被螞蟻爬過的邊的次數(shù)越多、它所獲得的信息素也越多。o n表示螞蟻的個(gè)數(shù), 是信息素的蒸發(fā)率，規(guī)定 ，一般設(shè)置為0.5. 是第k只螞蟻在它經(jīng)過的邊上釋放的信息素量。01ij基本蟻群算法o針對(duì)螞蟻釋放信息是問題，M.Dorigo等

10、人曾給出3中不同的模型，分別為蟻周系統(tǒng)、蟻量系統(tǒng)和蟻密系統(tǒng)，其計(jì)算公式如下：1.蟻周系統(tǒng)模型(初始時(shí)置為0)2.蟻量系統(tǒng)模型(初始時(shí)置為0)3.蟻密系統(tǒng)模(初始時(shí)置為0)ij/kij0,kijQ d，第 只螞蟻從城市 訪問城市其他kij0,kijQ，第 只螞蟻從城市 訪問城市其他/kij0,kkijQ L，第 只螞蟻從城市 訪問城市其他P、NP、NP-C、NP-hard問題o P類問題n 所有可用DTM (Deterministic one-tape Turing Machine) 在多項(xiàng)式時(shí)間內(nèi)求解的判定問題的集合。簡(jiǎn)記為O(p(n)n 即 P=L: 存在一個(gè)多項(xiàng)式時(shí)間DTM程序M，使得L=

11、LM , 其中LM表示程序M所識(shí)別的語(yǔ)言。n 若存在一個(gè)多項(xiàng)式時(shí)間DTM程序，它在編碼策略e之下求解判定問題，即L, eP,則稱該判定問題屬于P類問題。P、NP、NP-C、NP-hard問題o NP類問題 (Non-deterministic Polynomial)n 若存在一個(gè)多項(xiàng)式函數(shù) g(x) 和一個(gè)驗(yàn)證算法H, 對(duì)一類判定問題A的任何一個(gè)“是”回答，滿足其輸入長(zhǎng)度d(s)不超過g(d(I), 其中d(I)為I的輸入長(zhǎng)度，且驗(yàn)證算法中S為I的“是”回答的計(jì)算時(shí)間不超過g(d(I), 則稱判定問題A為非多項(xiàng)式確定問題。n NP類問題是所有可用NDTM (Non-Deterministic

12、one-tape Turing Machine)在多項(xiàng)式時(shí)間內(nèi)求解的判定問題的集合P、NP、NP-C、NP-hard問題o NP-C類問題 (NP-Complete)n是NP類中最困難的一類問題。n有重要實(shí)際意義和工程背景nTSP (Traveling Salesman Problem)o Symmetric; Asymmetrico NP-hard類問題nNP-C NP-hardNPPNP-hardNP-C基本蟻群算法模型o 基本假設(shè)n 螞蟻之間通過信息素和環(huán)境進(jìn)行通信。每只螞蟻僅根據(jù)其周圍的局部環(huán)境作出反應(yīng)，也只對(duì)周圍的局部環(huán)境產(chǎn)生影響；n 螞蟻對(duì)環(huán)境的反應(yīng)由其內(nèi)部模式?jīng)Q定。即螞蟻是反應(yīng)型

13、適應(yīng)性主體n 在個(gè)體水平上，每只螞蟻僅根據(jù)環(huán)境做出獨(dú)立選擇；在群體水平上，單只螞蟻的行為是隨機(jī)的，但蟻群可通過自組織過程形成高度有序的群體行為。蟻群算法的應(yīng)用TSP問題o 旅行商問題旅行商問題（TSP,traveling salesman problem）1960年首先提出。o 問題描述問題描述：一商人去n個(gè)城市銷貨，所有城市走一遍再回到起點(diǎn)，使所走路程最短。o TSP在許多工程領(lǐng)域具有廣泛的應(yīng)用價(jià)值例如電路板布線、VLSI芯片設(shè)計(jì)、機(jī)器人控制、交通路由等。o TSP的求解是NP-hardNP-hard問題問題。隨著城市數(shù)目的增多,問題空間將呈指數(shù)級(jí)增長(zhǎng)。 蟻群系統(tǒng)在TSP問題中的應(yīng)用10城市

14、TSP問題20城市TSP問題蟻群系統(tǒng)在TSP問題中的應(yīng)用30城市TSP問題48城市TSP問題TSP問題的數(shù)學(xué)描述TSP問題表示為一個(gè)N個(gè)城市的有向圖G=（N，A），其中城市之間距離目標(biāo)函數(shù)為其中， ，為城市1,2，n的一個(gè)排列， 。nnijd)(nliilldwf11)(),(21niiiw11iinN1,2,.,n A(i ,j)| ,i jN12( , , )nwi iio下面以TSP為例說明基本蟻群算法模型。o首先將m只螞蟻隨機(jī)放置在n個(gè)城市，位于城市i的第k只螞蟻選擇下一個(gè)城市j的概率為: 蟻群算法求解TSP問題) 1 (,0,),(),(),(),(),(otherwisetabuj

15、ifsisijijijiPktabuskko其中：表示邊（i，j）上的信息素濃度； 是啟發(fā)信息，d是城市i和j之間的距離； 和反映了信息素與啟發(fā)信息的相對(duì)重要性；表示螞蟻k已經(jīng)訪問過的城市列表。),(ji),(/1),(jidjiktabuo 當(dāng)所有螞蟻完成周游后，按以下公式進(jìn)行信息素更新。蟻群算法求解TSP問題)2()()(1mkkijijijijijtnto 其中，為小于1的常數(shù)，表示信息的持久性。) 3(0otherwiselijLQkkkijo 其中， Q為常數(shù)； 表示第k只螞蟻在本次迭代中走過的路徑， 為路徑長(zhǎng)度。 kLkLkLkL實(shí)現(xiàn)過程蟻群算法的應(yīng)用舉例o 2網(wǎng)絡(luò)路由問題o 將蟻

16、群算法應(yīng)用于解決受限路由問題，目前可以解決包括帶寬、延時(shí)、丟包率和最小花費(fèi)等約束條件在內(nèi)的QoS組播路由問題，比現(xiàn)有的鏈路狀態(tài)路由算法有明顯的優(yōu)越性蟻群算法的應(yīng)用舉例o 3電力系統(tǒng)領(lǐng)域o 電力系統(tǒng)的許多優(yōu)化問題本質(zhì)上是屬于組合優(yōu)化問題。蟻群算法的應(yīng)用舉例o 4航跡規(guī)劃問題 o 航跡規(guī)劃是指在特定的約束條件下，尋找運(yùn)動(dòng)體從初始點(diǎn)到目標(biāo)點(diǎn)滿足某種性能指標(biāo)最優(yōu)的運(yùn)動(dòng)軌跡。5 混流裝配線調(diào)度混流裝配線(sequencing mixed models on an assembly line, SMMAL)是指一定時(shí)間內(nèi)，在一條生產(chǎn)線上生產(chǎn)出多種不同型號(hào)的產(chǎn)品，產(chǎn)品的品種可以隨顧客需求的變化而變化。SMM

17、AL是車間作業(yè)調(diào)度問題(job-shop scheduling problem, JSP)的具體應(yīng)用之一。蟻群算法的應(yīng)用問題描述o 以汽車組裝為例，即在組裝所有車輛的過程中，所確定的組裝順序應(yīng)使各零部件的使用速率均勻化。如果不同型號(hào)的汽車消耗零部件的種類大致相同，那么原問題可簡(jiǎn)化為單級(jí)SMMAL調(diào)度問題。21,111min()Dnmpipjpjijipjbx1,0,jiijx如果車型 在調(diào)度中的 位置否則iipipd bD問題描述o i表示車型數(shù)的標(biāo)號(hào)o n表示需要裝配的車型數(shù)o m表示裝配線上需要的零部件種類總數(shù)o p表示生產(chǎn)調(diào)度中子裝配的標(biāo)號(hào)o 表示零部件p的理想使用速率o j表示車型調(diào)度

18、結(jié)果(即排序位置)的標(biāo)號(hào)o D表示在一個(gè)生產(chǎn)循環(huán)中需要組裝的各種車型的總和p問題描述o di表示在一個(gè)生產(chǎn)循環(huán)中車型i的數(shù)量o bip表示生產(chǎn)每輛i車型需要零部件p的數(shù)量o 表示在組裝線調(diào)度中前j-1臺(tái)車消耗零部件p的數(shù)量和1,0,0jpjpjiippx b且1,jp6 蟻群算法在SMMAL中的應(yīng)用o 假設(shè)有3種車型A、B、C排序，每個(gè)生產(chǎn)循環(huán)需A型車3輛，B型車2輛，C型車1輛，則每個(gè)循環(huán)共需生產(chǎn)6輛車。采用下圖的搜索空間定義，列表示6個(gè)排序階段，行表示有3種車型可以選擇。蟻群算法就是不斷改變圓圈的大小，最終尋找到滿意的可行解。搜索的初始狀態(tài) 簡(jiǎn)單SMMAL排序的搜索空間舉例o 經(jīng)過若干次迭

19、代之后，搜索空間變化，此時(shí)最可能的可行解為B-A-C-A-B-A若干次迭代后的狀態(tài)局部搜索( )的計(jì)算ij21,1()ijmpipkppQjbo 局部搜索 采用的是貪心策略ijo 基本思路：每一步均從當(dāng)前可選擇策略中選取，使目標(biāo)函數(shù)值增加最少的策略，即在確定第j個(gè)位置組裝的車型時(shí)，如果有多種車型可供選擇，則從中選擇一種車型i，使第j個(gè)位置組裝車型i時(shí)各零部件的使用速率最為均勻。狀態(tài)轉(zhuǎn)移概率o 狀態(tài)轉(zhuǎn)移概率公式如下(1),(1)( )0,kijijkkijijijj tabuitabupt 若否則信息素更新規(guī)則o LB表示目標(biāo)函數(shù)的下限值o 表示當(dāng)前目標(biāo)函數(shù)的平均值o Zcutr表示當(dāng)前的目標(biāo)函數(shù)值o 這種動(dòng)態(tài)標(biāo)記的方法可在搜索過程中加大可行解間信息素的差別，避免算法早熟Z0(1),0,cutrkijZLBijZLB如果車型 在調(diào)度中的 位置否則_1nantkiji