蟻群算法最全集課件

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

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

算法的背景與意義

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

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

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

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

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

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

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

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

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

航跡規(guī)劃是指在特定的約束條件下，尋找運動體從初始點到目標點滿足某種性能指標最優(yōu)的運動軌跡。37蟻群算法的應用舉例4航跡規(guī)劃問題375混流裝配線調度混流裝配線(sequencingmixedmodelsonanassemblyline,SMMAL)是指一定時間內，在一條生產線上生產出多種不同型號的產品，產品的品種可以隨顧客需求的變化而變化。SMMAL是車間作業(yè)調度問題(job-shopschedulingproblem,JSP)的具體應用之一。蟻群算法的應用385混流裝配線調度混流裝配線(sequencingmixe問題描述以汽車組裝為例，即在組裝所有車輛的過程中，所確定的組裝順序應使各零部件的使用速率均勻化。如果不同型號的汽車消耗零部件的種類大致相同，那么原問題可簡化為單級SMMAL調度問題。39問題描述以汽車組裝為例，即在組裝所有車輛的過程中，所確定的組問題描述i表示車型數(shù)的標號n表示需要裝配的車型數(shù)m表示裝配線上需要的零部件種類總數(shù)p表示生產調度中子裝配的標號表示零部件p的理想使用速率j表示車型調度結果(即排序位置)的標號D表示在一個生產循環(huán)中需要組裝的各種車型的總和40問題描述i表示車型數(shù)的標號40問題描述di表示在一個生產循環(huán)中車型i的數(shù)量bip表示生產每輛i車型需要零部件p的數(shù)量表示在組裝線調度中前j-1臺車消耗零部件p的數(shù)量和41問題描述di表示在一個生產循環(huán)中車型i的數(shù)量416蟻群算法在SMMAL中的應用假設有3種車型A、B、C排序，每個生產循環(huán)需A型車3輛，B型車2輛，C型車1輛，則每個循環(huán)共需生產6輛車。采用下圖的搜索空間定義，列表示6個排序階段，行表示有3種車型可以選擇。蟻群算法就是不斷改變圓圈的大小，最終尋找到滿意的可行解。搜索的初始狀態(tài)426蟻群算法在SMMAL中的應用假設有3種車型A、B、C排序簡單SMMAL排序的搜索空間舉例經過若干次迭代之后，搜索空間變化，此時最可能的可行解為B-A-C-A-B-A若干次迭代后的狀態(tài)43簡單SMMAL排序的搜索空間舉例經過若干次迭代之后，搜索空局部搜索()的計算局部搜索采用的是貪心策略基本思路：每一步均從當前可選擇策略中選取，使目標函數(shù)值增加最少的策略，即在確定第j個位置組裝的車型時，如果有多種車型可供選擇，則從中選擇一種車型i，使第j個位置組裝車型i時各零部件的使用速率最為均勻。44局部搜索()的計算局部搜索采用的是貪心策略基本思狀態(tài)轉移概率狀態(tài)轉移概率公式如下45狀態(tài)轉移概率狀態(tài)轉移概率公式如下45信息素更新規(guī)則LB表示目標函數(shù)的下限值表示當前目標函數(shù)的平均值Zcutr表示當前的目標函數(shù)值這種動態(tài)標記的方法可在搜索過程中加大可行解間信息素的差別，避免算法早熟46信息素更新規(guī)則LB表示目標函數(shù)的下限值46實驗數(shù)據(jù)47實驗數(shù)據(jù)47實驗參數(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ù)設置螞蟻系統(tǒng)蟻群系統(tǒng)48實驗參數(shù)設置最大-最小螞蟻系統(tǒng)選取全局最優(yōu)解帶有精英策略的螞蟻系統(tǒng)精英螞蟻數(shù)量:1只49實驗參數(shù)設置最大-最小螞蟻系統(tǒng)帶有精英策略的螞蟻系統(tǒng)49實驗結果50實驗結果50實驗結果分析直接用貪心策略求解結果：3293.4375螞蟻系統(tǒng)求解SMMAL問題的性能較差對于這個具體的問題，帶精英策略的螞蟻系統(tǒng)的求解性能并不好于螞蟻系統(tǒng)蟻群系統(tǒng)的性能相對于前兩者而言，有了很大幅度的提高最大-最小螞蟻系統(tǒng)的性能最好，大多數(shù)情況下的求解結果已達到實際的最優(yōu)解51實驗結果分析直接用貪心策略求解結果：51蟻群的規(guī)模和停止規(guī)則蟻群大小

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

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

算法的背景與意義

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

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

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

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

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

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

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

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

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

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