蟻群算法最全集課件

蟻群算法及其應(yīng)用馬文強(qiáng)歡迎下載1蟻群算法及其應(yīng)用馬文強(qiáng)1在非洲的大草原上，如果你發(fā)現(xiàn)羚羊在奔逃，那一定是獅子來了；如果見到獅子在躲避，那一定是象群在發(fā)怒了；如果見到成百上千的獅子和大象集體逃命的壯觀景象，那是什么來了呢？

——螞蟻軍團(tuán)來了2在非洲的大草原上，如果你發(fā)現(xiàn)羚羊在奔逃，那一定是獅子來了；如33

算法的背景與意義

一國內(nèi)外研究現(xiàn)狀二

研究內(nèi)容與方法三蟻群算法的應(yīng)用四4算法的背景與意義一國內(nèi)外研究現(xiàn)狀二研究內(nèi)容與方法三蟻群算法背景與意義5算法背景與意義5背景2001年至今1996年-2001年意大利學(xué)者Dorigo1991年啟發(fā)各種改進(jìn)算法的提出，應(yīng)用領(lǐng)域更廣引起學(xué)者關(guān)注，在應(yīng)用領(lǐng)域得到拓寬ACO首次被系統(tǒng)的提出自然界中真實(shí)蟻群集體行為MacroDorigo6背景2001年至今1996年-2001年意大利學(xué)者啟發(fā)各種改從自然界中蟻群的的覓食行為中受啟發(fā)，于1991年，由意大利學(xué)者M(jìn).Dorigo在其博士論文中提出，并成功的解決了旅行商(TSP)問題。針對(duì)該算法的不足，一些學(xué)者提出了許多改進(jìn)的蟻群優(yōu)化算法，如蟻群系統(tǒng)，最大-最小螞蟻系統(tǒng)，最優(yōu)保留蟻群系統(tǒng)等。近年來，一些學(xué)者提出了蟻群優(yōu)化元啟發(fā)式這一求解復(fù)雜問題的統(tǒng)一框架，這一框架為蟻群優(yōu)化算法的理論研究和設(shè)計(jì)提供了技術(shù)上的保障。我國最早研究蟻群算法的是東北大學(xué)的張紀(jì)會(huì)博士和徐心和教授。背景7從自然界中蟻群的的覓食行為中受啟發(fā)，于1991年，由意大利有學(xué)者通過對(duì)比實(shí)驗(yàn)發(fā)現(xiàn)，在組合優(yōu)化問題中，蟻群算法的優(yōu)化性能要好于遺傳算法等算法。蟻群算法是一種基于種群的啟發(fā)式搜索算法。蟻群算法廣泛應(yīng)用于求解TSP問題，Job-Shop調(diào)度問題，二次指派問題，背包問題等。蟻群算法是一種很有發(fā)展前景的優(yōu)化算法意義8有學(xué)者通過對(duì)比實(shí)驗(yàn)發(fā)現(xiàn)，在組合優(yōu)化問題中，蟻群算法的優(yōu)化性能目前，蟻群算法己經(jīng)成為一個(gè)備受關(guān)注的研究熱點(diǎn)和前沿性課題。人們對(duì)蟻群算法的研究已經(jīng)由當(dāng)初的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í)在蟻群算法的模型改進(jìn)以及其他仿生優(yōu)化算法的融合方面也取得了相當(dāng)豐富的研究成果，從而使這種新興的仿生優(yōu)化算法展現(xiàn)出前所未有的生機(jī)。從當(dāng)前可以檢索到的文獻(xiàn)情況看，研究和應(yīng)用蟻群優(yōu)化算法的學(xué)者主要集中在比利時(shí)，意大利，英國，法國和德國等歐洲國家。日本和美國在這兩年也開始啟動(dòng)對(duì)蟻群算法的研究。目前，蟻群優(yōu)化算法在啟發(fā)式方法范疇內(nèi)已逐漸成為一個(gè)獨(dú)立的分支。盡管蟻群優(yōu)化的嚴(yán)格理論基礎(chǔ)尚未奠定，國內(nèi)外的有關(guān)研究仍停留在實(shí)驗(yàn)探索階段，但從當(dāng)前的應(yīng)用效果來看，這種新型的尋優(yōu)思想無疑是具有十分光明的前景，更多深入細(xì)致的工作還有待于進(jìn)一步展開。國內(nèi)外研究現(xiàn)狀9目前，蟻群算法己經(jīng)成為一個(gè)備受關(guān)注的研究熱點(diǎn)和前沿性課蟻群算法(antcolonyoptimization,ACO)，又稱螞蟻算法，是一種用來在圖中尋找優(yōu)化路徑的機(jī)率型算法。它由MarcoDorigo于1992年在他的博士論文中提出，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。什么是蟻群算法10什么是蟻群算法10信息素：信息素多的地方顯然經(jīng)過這里的螞蟻多，因而會(huì)有更多的螞蟻聚集過來。正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。螞蟻如何找到最短路徑11螞蟻如何找到最短路徑11當(dāng)螞蟻沿著一條路到達(dá)終點(diǎn)以后會(huì)馬上返回來，這樣，短的路螞蟻來回一次的時(shí)間就短，這也意味著重復(fù)的頻率就快，因而在單位時(shí)間里走過的螞蟻數(shù)目就多，灑下的信息素自然也會(huì)多，自然會(huì)有更多的螞蟻被吸引過來，從而灑下更多的信息素……；而長的路正相反，因此，越來越多地螞蟻聚集到較短的路徑上來，最短的路徑就近似找到了。蟻群算法的基本思想12當(dāng)螞蟻沿著一條路到達(dá)終點(diǎn)以后會(huì)馬上返回來，這樣，短的路螞蟻來螞蟻系統(tǒng)是最早的蟻群優(yōu)化算法。螞蟻算法在解決一些小規(guī)模的TSP問題時(shí)的表現(xiàn)尚可令人滿意。但隨著問題規(guī)模的擴(kuò)大，螞蟻系統(tǒng)很難在可接受的循環(huán)次數(shù)內(nèi)找出最優(yōu)解。蟻群系統(tǒng)做了三個(gè)方面的改進(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)3.最大-最小螞蟻系統(tǒng)基本蟻群算法以及改進(jìn)算法13螞蟻系統(tǒng)是最早的蟻群優(yōu)化算法。螞蟻算法在解決一些小規(guī)模的TS基本蟻群算法螞蟻k(k=1,2，…,m)根據(jù)各個(gè)城市間連接路徑上的信息素濃度決定其下一個(gè)訪問城市，設(shè)Pijk(t)表示t時(shí)刻螞蟻k從城市i轉(zhuǎn)移到城市j的概率，其計(jì)算公式為：14基本蟻群算法螞蟻k(k=1,2，…,m)根據(jù)各個(gè)城市間連接路其中，表示從城市i可以直接到達(dá)的且又不在螞蟻訪問過的城市序列中的城市集合，是一個(gè)啟發(fā)式信息，通常由直接計(jì)算，表示邊(i,j)上的信息素量。由公式（1）可知，長度越短、信息素濃度越大的路徑被螞蟻選擇的概率越大。和是兩個(gè)預(yù)先設(shè)置的參數(shù)，用來控制啟發(fā)式信息（路徑的能見度）與信息濃度（路徑的軌跡）作用的權(quán)重關(guān)系。當(dāng)時(shí)，算法演變成傳統(tǒng)的隨機(jī)貪婪算法，最鄰近城市被選種的概率最大，當(dāng)時(shí)，螞蟻完全只根據(jù)信息度濃度確定路徑，算法將快速收斂，這樣構(gòu)建出的最優(yōu)路徑往往與實(shí)際目標(biāo)有著較大的差異，算法的性能比較糟糕，實(shí)驗(yàn)表明，在AS中設(shè)置比較合適。15其中，表示從城市i可以直接到達(dá)的且又不在螞基本蟻群算法信息更新公式為：在算法初始化時(shí)，問題空間中所有邊上的信息素都被初始化為，如果太小，算法容易早熟，即螞蟻很快就完部集中在一個(gè)局部最優(yōu)的路徑上，反之，如果太大，信息素對(duì)搜索方向的指導(dǎo)作用太低，也會(huì)影響算法的性能。對(duì)AS來說，我們使用，n是螞蟻的個(gè)數(shù)，是由貪婪算法構(gòu)造的路徑長度。16基本蟻群算法信息更新公式為：在算法初始化時(shí)，問題空間中所有邊基本蟻群算法信息素更新的每一輪中，問題空間中的所有路徑上的信息素都會(huì)發(fā)生蒸發(fā)，信息素蒸發(fā)是自然界本身固有的特征，在算法中能避免信息素的無限積累，使得算法可以快速丟棄之前構(gòu)建過的較差路徑。隨后所有的螞蟻根據(jù)自己構(gòu)建路徑長度在它們本輪經(jīng)過的邊釋放信息素。螞蟻構(gòu)建的路徑越短、釋放的信息素就越多；一條被螞蟻爬過的邊的次數(shù)越多、它所獲得的信息素也越多。n表示螞蟻的個(gè)數(shù),是信息素的蒸發(fā)率，規(guī)定，一般設(shè)置為0.5.是第k只螞蟻在它經(jīng)過的邊上釋放的信息素量。17基本蟻群算法信息素更新的每一輪中，問題空間中的所有路徑上的信基本蟻群算法針對(duì)螞蟻釋放信息是問題，M.Dorigo等人曾給出3中不同的模型，分別為蟻周系統(tǒng)、蟻量系統(tǒng)和蟻密系統(tǒng)，其計(jì)算公式如下：1.蟻周系統(tǒng)模型(初始時(shí)置為0)2.蟻量系統(tǒng)模型(初始時(shí)置為0)3.蟻密系統(tǒng)模(初始時(shí)置為0)18基本蟻群算法針對(duì)螞蟻釋放信息是問題，M.Dorigo等人曾給P、NP、NP-C、NP-hard問題P類問題所有可用DTM(Deterministicone-tapeTuringMachine)在多項(xiàng)式時(shí)間內(nèi)求解的判定問題Π的集合。簡記為O(p(n))即P={L:存在一個(gè)多項(xiàng)式時(shí)間DTM程序M，使得L=LM},其中LM表示程序M所識(shí)別的語言。若存在一個(gè)多項(xiàng)式時(shí)間DTM程序，它在編碼策略e之下求解判定問題Π，即L[Π,e]∈P,則稱該判定問題屬于P類問題。19P、NP、NP-C、NP-hard問題P類問題19P、NP、NP-C、NP-hard問題NP類問題(Non-deterministicPolynomial)若存在一個(gè)多項(xiàng)式函數(shù)g(x)和一個(gè)驗(yàn)證算法H,對(duì)一類判定問題A的任何一個(gè)“是”回答，滿足其輸入長度d(s)不超過g(d(I)),其中d(I)為I的輸入長度，且驗(yàn)證算法中S為I的“是”回答的計(jì)算時(shí)間不超過g(d(I)),則稱判定問題A為非多項(xiàng)式確定問題。NP類問題是所有可用NDTM(Non-Deterministicone-tapeTuringMachine)在多項(xiàng)式時(shí)間內(nèi)求解的判定問題Π的集合20P、NP、NP-C、NP-hard問題NP類問題(Non-P、NP、NP-C、NP-hard問題NP-C類問題(NP-Complete)是NP類中最困難的一類問題。有重要實(shí)際意義和工程背景TSP(TravelingSalesmanProblem)Symmetric;AsymmetricNP-hard類問題NP-CNP-hardNPPNP-hardNP-C21P、NP、NP-C、NP-hard問題NP-C類問題(NP基本蟻群算法模型基本假設(shè)螞蟻之間通過信息素和環(huán)境進(jìn)行通信。每只螞蟻僅根據(jù)其周圍的局部環(huán)境作出反應(yīng)，也只對(duì)周圍的局部環(huán)境產(chǎn)生影響；螞蟻對(duì)環(huán)境的反應(yīng)由其內(nèi)部模式?jīng)Q定。即螞蟻是反應(yīng)型適應(yīng)性主體在個(gè)體水平上，每只螞蟻僅根據(jù)環(huán)境做出獨(dú)立選擇；在群體水平上，單只螞蟻的行為是隨機(jī)的，但蟻群可通過自組織過程形成高度有序的群體行為。22基本蟻群算法模型基本假設(shè)22蟻群算法的應(yīng)用23蟻群算法的應(yīng)用23TSP問題旅行商問題（TSP,travelingsalesmanproblem）1960年首先提出。問題描述：

一商人去n個(gè)城市銷貨，所有城市走一遍再回到

起點(diǎn)，使所走路程最短。TSP在許多工程領(lǐng)域具有廣泛的應(yīng)用價(jià)值 例如電路板布線、VLSI芯片設(shè)計(jì)、機(jī)器人控制、交通路由等。TSP的求解是NP-hard問題。隨著城市數(shù)目的增多,問題空間將呈指數(shù)級(jí)增長。24TSP問題旅行商問題（TSP,travelingsales蟻群系統(tǒng)在TSP問題中的應(yīng)用10城市TSP問題20城市TSP問題25蟻群系統(tǒng)在TSP問題中的應(yīng)用10城市TSP問題20城市TSP蟻群系統(tǒng)在TSP問題中的應(yīng)用30城市TSP問題48城市TSP問題26蟻群系統(tǒng)在TSP問題中的應(yīng)用30城市TSP問題48城市TSPTSP問題的數(shù)學(xué)描述TSP問題表示為一個(gè)N個(gè)城市的有向圖G=（N，A），其中 城市之間距離目標(biāo)函數(shù)為其中，，為城市1,2，…n的一個(gè)排列，。27TSP問題的數(shù)學(xué)描述TSP問題表示為一個(gè)N個(gè)城市的有向圖G=下面以TSP為例說明基本蟻群算法模型。首先將m只螞蟻隨機(jī)放置在n個(gè)城市，位于城市i的第k只螞蟻選擇下一個(gè)城市j的概率為:蟻群算法求解TSP問題其中：

表示邊（i，j）上的信息素濃度；

是啟發(fā)信息，d是城市i和j之間的距離；

α和β反映了信息素與啟發(fā)信息的相對(duì)重要性；

表示螞蟻k已經(jīng)訪問過的城市列表。28下面以TSP為例說明基本蟻群算法模型。蟻群算法求解TSP問題當(dāng)所有螞蟻完成周游后，按以下公式進(jìn)行信息素更新。蟻群算法求解TSP問題其中，ρ為小于1的常數(shù)，表示信息的持久性。其中，

Q為常數(shù)；表示第k只螞蟻在本次迭代中走過的路徑，為路徑長度。29當(dāng)所有螞蟻完成周游后，按以下公式進(jìn)行信息素更新。蟻群算法求解3030實(shí)現(xiàn)過程31實(shí)現(xiàn)過程31323233333434蟻群算法的應(yīng)用舉例2網(wǎng)絡(luò)路由問題將蟻群算法應(yīng)用于解決受限路由問題，目前可以解決包括帶寬、延時(shí)、丟包率和最小花費(fèi)等約束條件在內(nèi)的QoS組播路由問題，比現(xiàn)有的鏈路狀態(tài)路由算法有明顯的優(yōu)越性35蟻群算法的應(yīng)用舉例2網(wǎng)絡(luò)路由問題35蟻群算法的應(yīng)用舉例3電力系統(tǒng)領(lǐng)域電力系統(tǒng)的許多優(yōu)化問題本質(zhì)上是屬于組合優(yōu)化問題。36蟻群算法的應(yīng)用舉例3電力系統(tǒng)領(lǐng)域36蟻群算法的應(yīng)用舉例4航跡規(guī)劃問題

航跡規(guī)劃是指在特定的約束條件下，尋找運(yùn)動(dòng)體從初始點(diǎn)到目標(biāo)點(diǎn)滿足某種性能指標(biāo)最優(yōu)的運(yùn)動(dòng)軌跡。37蟻群算法的應(yīng)用舉例4航跡規(guī)劃問題375混流裝配線調(diào)度混流裝配線(sequencingmixedmodelsonanassemblyline,SMMAL)是指一定時(shí)間內(nèi)，在一條生產(chǎn)線上生產(chǎn)出多種不同型號(hào)的產(chǎn)品，產(chǎn)品的品種可以隨顧客需求的變化而變化。SMMAL是車間作業(yè)調(diào)度問題(job-shopschedulingproblem,JSP)的具體應(yīng)用之一。蟻群算法的應(yīng)用385混流裝配線調(diào)度混流裝配線(sequencingmixe問題描述以汽車組裝為例，即在組裝所有車輛的過程中，所確定的組裝順序應(yīng)使各零部件的使用速率均勻化。如果不同型號(hào)的汽車消耗零部件的種類大致相同，那么原問題可簡化為單級(jí)SMMAL調(diào)度問題。39問題描述以汽車組裝為例，即在組裝所有車輛的過程中，所確定的組問題描述i表示車型數(shù)的標(biāo)號(hào)n表示需要裝配的車型數(shù)m表示裝配線上需要的零部件種類總數(shù)p表示生產(chǎn)調(diào)度中子裝配的標(biāo)號(hào)表示零部件p的理想使用速率j表示車型調(diào)度結(jié)果(即排序位置)的標(biāo)號(hào)D表示在一個(gè)生產(chǎn)循環(huán)中需要組裝的各種車型的總和40問題描述i表示車型數(shù)的標(biāo)號(hào)40問題描述di表示在一個(gè)生產(chǎn)循環(huán)中車型i的數(shù)量bip表示生產(chǎn)每輛i車型需要零部件p的數(shù)量表示在組裝線調(diào)度中前j-1臺(tái)車消耗零部件p的數(shù)量和41問題描述di表示在一個(gè)生產(chǎn)循環(huán)中車型i的數(shù)量416蟻群算法在SMMAL中的應(yīng)用假設(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)426蟻群算法在SMMAL中的應(yīng)用假設(shè)有3種車型A、B、C排序簡單SMMAL排序的搜索空間舉例經(jīng)過若干次迭代之后，搜索空間變化，此時(shí)最可能的可行解為B-A-C-A-B-A若干次迭代后的狀態(tài)43簡單SMMAL排序的搜索空間舉例經(jīng)過若干次迭代之后，搜索空局部搜索()的計(jì)算局部搜索采用的是貪心策略基本思路：每一步均從當(dāng)前可選擇策略中選取，使目標(biāo)函數(shù)值增加最少的策略，即在確定第j個(gè)位置組裝的車型時(shí)，如果有多種車型可供選擇，則從中選擇一種車型i，使第j個(gè)位置組裝車型i時(shí)各零部件的使用速率最為均勻。44局部搜索()的計(jì)算局部搜索采用的是貪心策略基本思狀態(tài)轉(zhuǎn)移概率狀態(tài)轉(zhuǎn)移概率公式如下45狀態(tài)轉(zhuǎn)移概率狀態(tài)轉(zhuǎn)移概率公式如下45信息素更新規(guī)則LB表示目標(biāo)函數(shù)的下限值表示當(dāng)前目標(biāo)函數(shù)的平均值Zcutr表示當(dāng)前的目標(biāo)函數(shù)值這種動(dòng)態(tài)標(biāo)記的方法可在搜索過程中加大可行解間信息素的差別，避免算法早熟46信息素更新規(guī)則LB表示目標(biāo)函數(shù)的下限值46實(shí)驗(yàn)數(shù)據(jù)47實(shí)驗(yàn)數(shù)據(jù)47實(shí)驗(yàn)參數(shù)設(shè)置螞蟻系統(tǒng)螞蟻數(shù)量N_ant=5最大循環(huán)周期Ncmax=400=0.2Q=20000=0.9LB=0.0蟻群系統(tǒng)q0=0.5全局更新規(guī)則中的

和局部更新規(guī)則中的均取0.148實(shí)驗(yàn)參數(shù)設(shè)置螞蟻系統(tǒng)蟻群系統(tǒng)48實(shí)驗(yàn)參數(shù)設(shè)置最大-最小螞蟻系統(tǒng)選取全局最優(yōu)解帶有精英策略的螞蟻系統(tǒng)精英螞蟻數(shù)量:1只49實(shí)驗(yàn)參數(shù)設(shè)置最大-最小螞蟻系統(tǒng)帶有精英策略的螞蟻系統(tǒng)49實(shí)驗(yàn)結(jié)果50實(shí)驗(yàn)結(jié)果50實(shí)驗(yàn)結(jié)果分析直接用貪心策略求解結(jié)果：3293.4375螞蟻系統(tǒng)求解SMMAL問題的性能較差對(duì)于這個(gè)具體的問題，帶精英策略的螞蟻系統(tǒng)的求解性能并不好于螞蟻系統(tǒng)蟻群系統(tǒng)的性能相對(duì)于前兩者而言，有了很大幅度的提高最大-最小螞蟻系統(tǒng)的性能最好，大多數(shù)情況下的求解結(jié)果已達(dá)到實(shí)際的最優(yōu)解51實(shí)驗(yàn)結(jié)果分析直接用貪心策略求解結(jié)果：51蟻群的規(guī)模和停止規(guī)則蟻群大小

一般情況下蟻群中螞蟻的個(gè)數(shù)不超過TSP圖中節(jié)點(diǎn)的個(gè)數(shù)。終止條件 1給定一個(gè)外循環(huán)的最大數(shù)目； 2當(dāng)前最優(yōu)解連續(xù)K次相同而停止，其中K是一個(gè)給定的整數(shù)，表示算法已經(jīng)收斂，不再需要繼續(xù)。52蟻群的規(guī)模和停止規(guī)則蟻群大小52蟻群算法的缺點(diǎn)蟻群算法的缺點(diǎn) 1）收斂速度慢 2）易于陷入局部最優(yōu)53蟻群算法的缺點(diǎn)蟻群算法的缺點(diǎn)53Questions?54Questions?54個(gè)人觀點(diǎn)供參考，歡迎討論個(gè)人觀點(diǎn)供參考，歡迎討論蟻群算法及其應(yīng)用馬文強(qiáng)歡迎下載56蟻群算法及其應(yīng)用馬文強(qiáng)1在非洲的大草原上，如果你發(fā)現(xiàn)羚羊在奔逃，那一定是獅子來了；如果見到獅子在躲避，那一定是象群在發(fā)怒了；如果見到成百上千的獅子和大象集體逃命的壯觀景象，那是什么來了呢？

——螞蟻軍團(tuán)來了57在非洲的大草原上，如果你發(fā)現(xiàn)羚羊在奔逃，那一定是獅子來了；如583

算法的背景與意義

一國內(nèi)外研究現(xiàn)狀二

研究內(nèi)容與方法三蟻群算法的應(yīng)用四59算法的背景與意義一國內(nèi)外研究現(xiàn)狀二研究內(nèi)容與方法三蟻群算法背景與意義60算法背景與意義5背景2001年至今1996年-2001年意大利學(xué)者Dorigo1991年啟發(fā)各種改進(jìn)算法的提出，應(yīng)用領(lǐng)域更廣引起學(xué)者關(guān)注，在應(yīng)用領(lǐng)域得到拓寬ACO首次被系統(tǒng)的提出自然界中真實(shí)蟻群集體行為MacroDorigo61背景2001年至今1996年-2001年意大利學(xué)者啟發(fā)各種改從自然界中蟻群的的覓食行為中受啟發(fā)，于1991年，由意大利學(xué)者M(jìn).Dorigo在其博士論文中提出，并成功的解決了旅行商(TSP)問題。針對(duì)該算法的不足，一些學(xué)者提出了許多改進(jìn)的蟻群優(yōu)化算法，如蟻群系統(tǒng)，最大-最小螞蟻系統(tǒng)，最優(yōu)保留蟻群系統(tǒng)等。近年來，一些學(xué)者提出了蟻群優(yōu)化元啟發(fā)式這一求解復(fù)雜問題的統(tǒng)一框架，這一框架為蟻群優(yōu)化算法的理論研究和設(shè)計(jì)提供了技術(shù)上的保障。我國最早研究蟻群算法的是東北大學(xué)的張紀(jì)會(huì)博士和徐心和教授。背景62從自然界中蟻群的的覓食行為中受啟發(fā)，于1991年，由意大利有學(xué)者通過對(duì)比實(shí)驗(yàn)發(fā)現(xiàn)，在組合優(yōu)化問題中，蟻群算法的優(yōu)化性能要好于遺傳算法等算法。蟻群算法是一種基于種群的啟發(fā)式搜索算法。蟻群算法廣泛應(yīng)用于求解TSP問題，Job-Shop調(diào)度問題，二次指派問題，背包問題等。蟻群算法是一種很有發(fā)展前景的優(yōu)化算法意義63有學(xué)者通過對(duì)比實(shí)驗(yàn)發(fā)現(xiàn)，在組合優(yōu)化問題中，蟻群算法的優(yōu)化性能目前，蟻群算法己經(jīng)成為一個(gè)備受關(guān)注的研究熱點(diǎn)和前沿性課題。人們對(duì)蟻群算法的研究已經(jīng)由當(dāng)初的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í)在蟻群算法的模型改進(jìn)以及其他仿生優(yōu)化算法的融合方面也取得了相當(dāng)豐富的研究成果，從而使這種新興的仿生優(yōu)化算法展現(xiàn)出前所未有的生機(jī)。從當(dāng)前可以檢索到的文獻(xiàn)情況看，研究和應(yīng)用蟻群優(yōu)化算法的學(xué)者主要集中在比利時(shí)，意大利，英國，法國和德國等歐洲國家。日本和美國在這兩年也開始啟動(dòng)對(duì)蟻群算法的研究。目前，蟻群優(yōu)化算法在啟發(fā)式方法范疇內(nèi)已逐漸成為一個(gè)獨(dú)立的分支。盡管蟻群優(yōu)化的嚴(yán)格理論基礎(chǔ)尚未奠定，國內(nèi)外的有關(guān)研究仍停留在實(shí)驗(yàn)探索階段，但從當(dāng)前的應(yīng)用效果來看，這種新型的尋優(yōu)思想無疑是具有十分光明的前景，更多深入細(xì)致的工作還有待于進(jìn)一步展開。國內(nèi)外研究現(xiàn)狀64目前，蟻群算法己經(jīng)成為一個(gè)備受關(guān)注的研究熱點(diǎn)和前沿性課蟻群算法(antcolonyoptimization,ACO)，又稱螞蟻算法，是一種用來在圖中尋找優(yōu)化路徑的機(jī)率型算法。它由MarcoDorigo于1992年在他的博士論文中提出，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。什么是蟻群算法65什么是蟻群算法10信息素：信息素多的地方顯然經(jīng)過這里的螞蟻多，因而會(huì)有更多的螞蟻聚集過來。正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。螞蟻如何找到最短路徑66螞蟻如何找到最短路徑11當(dāng)螞蟻沿著一條路到達(dá)終點(diǎn)以后會(huì)馬上返回來，這樣，短的路螞蟻來回一次的時(shí)間就短，這也意味著重復(fù)的頻率就快，因而在單位時(shí)間里走過的螞蟻數(shù)目就多，灑下的信息素自然也會(huì)多，自然會(huì)有更多的螞蟻被吸引過來，從而灑下更多的信息素……；而長的路正相反，因此，越來越多地螞蟻聚集到較短的路徑上來，最短的路徑就近似找到了。蟻群算法的基本思想67當(dāng)螞蟻沿著一條路到達(dá)終點(diǎn)以后會(huì)馬上返回來，這樣，短的路螞蟻來螞蟻系統(tǒng)是最早的蟻群優(yōu)化算法。螞蟻算法在解決一些小規(guī)模的TSP問題時(shí)的表現(xiàn)尚可令人滿意。但隨著問題規(guī)模的擴(kuò)大，螞蟻系統(tǒng)很難在可接受的循環(huán)次數(shù)內(nèi)找出最優(yōu)解。蟻群系統(tǒng)做了三個(gè)方面的改進(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)3.最大-最小螞蟻系統(tǒng)基本蟻群算法以及改進(jìn)算法68螞蟻系統(tǒng)是最早的蟻群優(yōu)化算法。螞蟻算法在解決一些小規(guī)模的TS基本蟻群算法螞蟻k(k=1,2，…,m)根據(jù)各個(gè)城市間連接路徑上的信息素濃度決定其下一個(gè)訪問城市，設(shè)Pijk(t)表示t時(shí)刻螞蟻k從城市i轉(zhuǎn)移到城市j的概率，其計(jì)算公式為：69基本蟻群算法螞蟻k(k=1,2，…,m)根據(jù)各個(gè)城市間連接路其中，表示從城市i可以直接到達(dá)的且又不在螞蟻訪問過的城市序列中的城市集合，是一個(gè)啟發(fā)式信息，通常由直接計(jì)算，表示邊(i,j)上的信息素量。由公式（1）可知，長度越短、信息素濃度越大的路徑被螞蟻選擇的概率越大。和是兩個(gè)預(yù)先設(shè)置的參數(shù)，用來控制啟發(fā)式信息（路徑的能見度）與信息濃度（路徑的軌跡）作用的權(quán)重關(guān)系。當(dāng)時(shí)，算法演變成傳統(tǒng)的隨機(jī)貪婪算法，最鄰近城市被選種的概率最大，當(dāng)時(shí)，螞蟻完全只根據(jù)信息度濃度確定路徑，算法將快速收斂，這樣構(gòu)建出的最優(yōu)路徑往往與實(shí)際目標(biāo)有著較大的差異，算法的性能比較糟糕，實(shí)驗(yàn)表明，在AS中設(shè)置比較合適。70其中，表示從城市i可以直接到達(dá)的且又不在螞基本蟻群算法信息更新公式為：在算法初始化時(shí)，問題空間中所有邊上的信息素都被初始化為，如果太小，算法容易早熟，即螞蟻很快就完部集中在一個(gè)局部最優(yōu)的路徑上，反之，如果太大，信息素對(duì)搜索方向的指導(dǎo)作用太低，也會(huì)影響算法的性能。對(duì)AS來說，我們使用，n是螞蟻的個(gè)數(shù)，是由貪婪算法構(gòu)造的路徑長度。71基本蟻群算法信息更新公式為：在算法初始化時(shí)，問題空間中所有邊基本蟻群算法信息素更新的每一輪中，問題空間中的所有路徑上的信息素都會(huì)發(fā)生蒸發(fā)，信息素蒸發(fā)是自然界本身固有的特征，在算法中能避免信息素的無限積累，使得算法可以快速丟棄之前構(gòu)建過的較差路徑。隨后所有的螞蟻根據(jù)自己構(gòu)建路徑長度在它們本輪經(jīng)過的邊釋放信息素。螞蟻構(gòu)建的路徑越短、釋放的信息素就越多；一條被螞蟻爬過的邊的次數(shù)越多、它所獲得的信息素也越多。n表示螞蟻的個(gè)數(shù),是信息素的蒸發(fā)率，規(guī)定，一般設(shè)置為0.5.是第k只螞蟻在它經(jīng)過的邊上釋放的信息素量。72基本蟻群算法信息素更新的每一輪中，問題空間中的所有路徑上的信基本蟻群算法針對(duì)螞蟻釋放信息是問題，M.Dorigo等人曾給出3中不同的模型，分別為蟻周系統(tǒng)、蟻量系統(tǒng)和蟻密系統(tǒng)，其計(jì)算公式如下：1.蟻周系統(tǒng)模型(初始時(shí)置為0)2.蟻量系統(tǒng)模型(初始時(shí)置為0)3.蟻密系統(tǒng)模(初始時(shí)置為0)73基本蟻群算法針對(duì)螞蟻釋放信息是問題，M.Dorigo等人曾給P、NP、NP-C、NP-hard問題P類問題所有可用DTM(Deterministicone-tapeTuringMachine)在多項(xiàng)式時(shí)間內(nèi)求解的判定問題Π的集合。簡記為O(p(n))即P={L:存在一個(gè)多項(xiàng)式時(shí)間DTM程序M，使得L=LM},其中LM表示程序M所識(shí)別的語言。若存在一個(gè)多項(xiàng)式時(shí)間DTM程序，它在編碼策略e之下求解判定問題Π，即L[Π,e]∈P,則稱該判定問題屬于P類問題。74P、NP、NP-C、NP-hard問題P類問題19P、NP、NP-C、NP-hard問題NP類問題(Non-deterministicPolynomial)若存在一個(gè)多項(xiàng)式函數(shù)g(x)和一個(gè)驗(yàn)證算法H,對(duì)一類判定問題A的任何一個(gè)“是”回答，滿足其輸入長度d(s)不超過g(d(I)),其中d(I)為I的輸入長度，且驗(yàn)證算法中S為I的“是”回答的計(jì)算時(shí)間不超過g(d(I)),則稱判定問題A為非多項(xiàng)式確定問題。NP類問題是所有可用NDTM(Non-Deterministicone-tapeTuringMachine)在多項(xiàng)式時(shí)間內(nèi)求解的判定問題Π的集合75P、NP、NP-C、NP-hard問題NP類問題(Non-P、NP、NP-C、NP-hard問題NP-C類問題(NP-Complete)是NP類中最困難的一類問題。有重要實(shí)際意義和工程背景TSP(TravelingSalesmanProblem)Symmetric;AsymmetricNP-hard類問題NP-CNP-hardNPPNP-hardNP-C76P、NP、NP-C、NP-hard問題NP-C類問題(NP基本蟻群算法模型基本假設(shè)螞蟻之間通過信息素和環(huán)境進(jìn)行通信。每只螞蟻僅根據(jù)其周圍的局部環(huán)境作出反應(yīng)，也只對(duì)周圍的局部環(huán)境產(chǎn)生影響；螞蟻對(duì)環(huán)境的反應(yīng)由其內(nèi)部模式?jīng)Q定。即螞蟻是反應(yīng)型適應(yīng)性主體在個(gè)體水平上，每只螞蟻僅根據(jù)環(huán)境做出獨(dú)立選擇；在群體水平上，單只螞蟻的行為是隨機(jī)的，但蟻群可通過自組織過程形成高度有序的群體行為。77基本蟻群算法模型基本假設(shè)22蟻群算法的應(yīng)用78蟻群算法的應(yīng)用23TSP問題旅行商問題（TSP,travelingsalesmanproblem）1960年首先提出。問題描述：

一商人去n個(gè)城市銷貨，所有城市走一遍再回到

起點(diǎn)，使所走路程最短。TSP在許多工程領(lǐng)域具有廣泛的應(yīng)用價(jià)值 例如電路板布線、VLSI芯片設(shè)計(jì)、機(jī)器人控制、交通路由等。TSP的求解是NP-hard問題。隨著城市數(shù)目的增多,問題空間將呈指數(shù)級(jí)增長。79TSP問題旅行商問題（TSP,travelingsales蟻群系統(tǒng)在TSP問題中的應(yīng)用10城市TSP問題20城市TSP問題80蟻群系統(tǒng)在TSP問題中的應(yīng)用10城市TSP問題20城市TSP蟻群系統(tǒng)在TSP問題中的應(yīng)用30城市TSP問題48城市TSP問題81蟻群系統(tǒng)在TSP問題中的應(yīng)用30城市TSP問題48城市TSPTSP問題的數(shù)學(xué)描述TSP問題表示為一個(gè)N個(gè)城市的有向圖G=（N，A），其中 城市之間距離目標(biāo)函數(shù)為其中，，為城市1,2，…n的一個(gè)排列，。82TSP問題的數(shù)學(xué)描述TSP問題表示為一個(gè)N個(gè)城市的有向圖G=下面以TSP為例說明基本蟻群算法模型。首先將m只螞蟻隨機(jī)放置在n個(gè)城市，位于城市i的第k只螞蟻選擇下一個(gè)城市j的概率為:蟻群算法求解TSP問題其中：

表示邊（i，j）上的信息素濃度；

是啟發(fā)信息，d是城市i和j之間的距離；

α和β反映了信息素與啟發(fā)信息的相對(duì)重要性；

表示螞蟻k已經(jīng)訪問過的城市列表。83下面以TSP為例說明基本蟻群算法模型。蟻群算法求解TSP問題當(dāng)所有螞蟻完成周游后，按以下公式進(jìn)行信息素更新。蟻群算法求解TSP問題其中，ρ為小于1的常數(shù)，表示信息的持久性。其中，

Q為常數(shù)；表示第k只螞蟻在本次迭代中走過的路徑，為路徑長度。84當(dāng)所有螞蟻完成周游后，按以下公式進(jìn)行信息素更新。蟻群算法求解8530實(shí)現(xiàn)過程86實(shí)現(xiàn)過程31873288338934蟻群算法的應(yīng)用舉例2網(wǎng)絡(luò)路由問題將蟻群算法應(yīng)用于解決受限路由問題，目前可以解決包括帶寬、延時(shí)、丟包率和最小花費(fèi)等約束條件在內(nèi)的QoS組播路由問題，比現(xiàn)有的鏈路狀態(tài)路由算法有明顯的優(yōu)越性90蟻群算法的應(yīng)用舉例2網(wǎng)絡(luò)路由問題35蟻群算法的應(yīng)用舉例3電力系統(tǒng)領(lǐng)域電力系統(tǒng)的許多優(yōu)化問題本質(zhì)上是屬于組合優(yōu)化問題。91蟻群算法的應(yīng)用舉例3電力系統(tǒng)領(lǐng)域36蟻群算法的應(yīng)用舉例4航跡規(guī)劃問題

航跡規(guī)劃是指在特定的約束條件下，尋找運(yùn)動(dòng)體從初始點(diǎn)到目標(biāo)點(diǎn)滿足某種性能指標(biāo)最優(yōu)的運(yùn)動(dòng)軌跡。92蟻群算法的應(yīng)用舉例4航跡規(guī)劃問題375混流裝配線調(diào)度混流裝配線(sequencingmixedmodelsonanassemblyline,SMMAL)是指一定時(shí)間內(nèi)，在一條生產(chǎn)線上生產(chǎn)出多種不同型號(hào)的產(chǎn)品，產(chǎn)品的品種可以隨顧客需求的變化而變化。SMMAL是車間作業(yè)調(diào)度問題(job-shopschedulingproblem,JSP)的具體應(yīng)用之一。蟻群算法的應(yīng)用935混流裝配線調(diào)度混流裝配線(sequencingmixe問題描述以汽車組裝為例，即在組裝所有車輛的過程中，所確定的組裝順序應(yīng)使各零部件的使用速率均勻化。如果不同型號(hào)的汽車消耗零部件的種類大致相同，那么原問題可簡化為單級(jí)SMMAL調(diào)度問題。94問題描述以汽車組裝為例，即在組裝所有車輛的過程中，所確定的組問題描述i表示車型數(shù)的標(biāo)號(hào)n表示需要裝配的車型數(shù)m表示裝配線上需要的零部件種類總數(shù)p表示生產(chǎn)調(diào)度中子裝配的標(biāo)號(hào)表示零部件p的理想使用速率j表示車型調(diào)度結(jié)果(即排序位置)的標(biāo)