1、蟻群算法蟻群算法的起源蟻群算法的原理自然蟻群與人工蟻群蟻群算法在TSP問題中的應用三種模型蟻群的規(guī)模及停止規(guī)則蟻群算法的特點蟻群算法的研究現(xiàn)狀蟻群算法的其他應用參考書推薦總結 研究群居性昆蟲行為的科學家發(fā)現(xiàn)，昆蟲在群落一級上的合作基本上是自組織的，在許多場合中盡管這些合作可能很簡單，但它們卻可以解決許多復雜的問題。 蟻群算法就是利用群集智能解決組合優(yōu)化 題的典型例子。 20世紀90年代意大利學者MDorigo，VManiezzo，AColorni等從生物進化的機制中受到啟發(fā)，通過模擬自然界螞蟻搜索路徑的行為，提出來一種新型的模擬進化算法 蟻群算法(Ant Colony Algorithm，AC

2、A)，一種仿生算法。蟻群算法的起源 它是繼模擬退火算法、遺傳算法、禁忌搜索(Tabu Search)算法、人工神經(jīng)網(wǎng)絡算法等啟發(fā)式搜索算法以后的又一種應用于組合優(yōu)化問題的啟發(fā)式搜索算法。用該方法求解TSP問題、分配問題、job-shop調(diào)度問題，取得了較好的試驗結果雖然研究時間不長，但是現(xiàn)在的研究顯示出，蟻群算法在求解復雜優(yōu)化問題（特別是離散優(yōu)化問題）方面有一定優(yōu)勢，表明它是一種有發(fā)展前景的算法。蟻群算法的起源 螞蟻在運動過程中，能夠在它所經(jīng)過的路徑上留下一種稱之為外激素(pheromone)的物質(zhì)進行信息傳遞，而且螞蟻在運動過程中能夠感知這種物質(zhì)，并以此指導自己的運動方向，因此由大量螞蟻組成

3、的蟻群集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。 蟻群算法的原理 螞蟻從A點出發(fā)，速度相同，食物在D點，可能隨機選擇路線ABD或ACD。假設初始時每條分配路線一只螞蟻，每個時間單位行走一步，本圖為經(jīng)過9個時間單位時的情形：走ABD的螞蟻到達終點，而走ACD的螞蟻剛好走到C點，為一半路程。簡化的螞蟻尋食過程 本圖為從開始算起，經(jīng)過18個時間單位時的情形：走ABD的螞蟻到達終點后得到食物又返回了起點A，而走ACD的螞蟻剛好走到D點。簡化的螞蟻尋食過程 基于以上蟻群尋找食物時的最優(yōu)路徑選擇問題，可以構造人工蟻群，來解決最優(yōu)化問題，如TSP問題。 人

4、工蟻群中把具有簡單功能的工作單元看作螞蟻。兩者相似之處在于：都是優(yōu)先選擇信息素濃度大的路徑。兩者的區(qū)別： （1）在于人工蟻群有一定的記憶能力，能夠記憶已經(jīng)訪問過的節(jié)點。 （2）人工蟻群選擇路徑時不是盲目的。而是按一定規(guī)律有意識地尋找最短路徑。例如，在TSP問題中，可以預先知道當前城市到下一個目的地的距離。自然蟻群與人工蟻群蟻群算法在TSP問題中的應用旅行商問題（TSP,traveling salesman problem）1960年首先提出。問題描述： 一商人去n個城市銷貨，所有城市走一遍再回到起點，使所走路程最短。TSP在許多工程領域具有廣泛的應用價值 例如電路板布線、VLSI芯片設計、機器

5、人控制、交通路由等。TSP的求解是NP-hard問題。隨著城市數(shù)目的增多,問題空間將呈指數(shù)級增長。 TSP問題的數(shù)學描述TSP問題表示為一個N個城市的有向圖G=(N,A)，其中城市之間距離目標函數(shù)為其中， ，為城市1,2，n的一 個排列， 。螞蟻算法求解TSP其中：表示邊（i，j）上的信息素濃度； 是啟發(fā)信息，d是城市i和j之間的距離；和反映了信息素與啟發(fā)信息的相對重要性；表示螞蟻k已經(jīng)訪問過的城市列表。 當所有螞蟻完成周游后，按以下公式進行信息素更新。 螞蟻算法求解TSP其中：為小于1的常數(shù)，表示信息的持久性。其中：Q為常數(shù)；lk表示第k只螞蟻在本次迭代中走過的路徑，Lk為路徑長度。 蟻量算

6、法（ant-quantity algorithm）的信息素更新為 ,Q為常量， 表示i到j的距離，這樣信息濃度會隨城市距離的減小而加大。蟻密算法（ ant-density algorithm ）信息素更新為 ，在此算法中，從城市i到j的螞蟻在路徑上殘留的信息濃度為一個與路徑無關的常量Q。 后兩種算法與前一種算法的區(qū)別在于：后兩種算法中每走一步(即從時間t到t+1)，都要更新殘留信息素的濃度，而非等到所有螞蟻完成對所有城市的訪問 之后。 三種模型 通過實驗表明，在這三種算法中：ant-cycle算法的效果最好，這是因為它用的是全局信息；而其余兩種算法用的是局部信息。這種更新方法很好地保證了殘留信

7、息不至于無限累積，非最優(yōu)路徑會逐漸隨時間推移被忘記。三種模型一、蟻群大小 一般情況下蟻群中螞蟻的個數(shù)不超過TSP圖中節(jié)點的個數(shù)。二、終止條件 1 給定一個外循環(huán)的最大數(shù)目； 2 當前最優(yōu)解連續(xù)K次相同而停止，其中K是一個給定的整數(shù)，表示算法已經(jīng)收斂，不再需要繼續(xù)。蟻群的規(guī)模及停止規(guī)則 其原理是一種正反饋機制或稱增強型學習系統(tǒng); 它通過【最優(yōu)路徑上螞蟻數(shù)量的增加信息素強度增加后來螞蟻選擇概率增大最優(yōu)路徑上螞蟻數(shù)量更大增加】達到最終收斂于最優(yōu)路徑上。 它是一種通用型隨機優(yōu)化方法, 它吸收了螞蟻的行為特點(內(nèi)在搜索機制) , 它是使用人工螞蟻仿真(也稱螞蟻系統(tǒng)) 來求解問題。但人工螞蟻決不是對實際螞

8、蟻的一種簡單模擬, 它融進了人類的智能。人工螞蟻有一定的記憶; 人工螞蟻不完全是瞎的; 人工螞蟻生活的時空是離散的。蟻群算法的特點 它是一種分布式的優(yōu)化方法, 不僅適合目前的串行計算機, 而且適合未來的并行計算機。 它是一種全局優(yōu)化的方法, 不僅可用于求解單目標優(yōu)化問題, 而且可用于求解多目標優(yōu)化問題。 它是一種啟發(fā)式算法, 計算復雜性為 , 其中Nc是迭代次數(shù), m是螞蟻數(shù)目, n是目的節(jié)點數(shù)目。蟻群算法的特點蟻群算法的研究現(xiàn)狀 90年代Dorigo最早提出了蟻群優(yōu)化算法-螞蟻系統(tǒng)（Ant System, AS）并將其應用于解決計算機算法學中經(jīng)典的旅行商問題（TSP）。從螞蟻系統(tǒng)開始，基本的

9、蟻群算法得到了不斷的發(fā)展和完善，并在TSP以及許多實際優(yōu)化問題求解中進一步得到了驗證。這些AS改進版本的一個共同點就是增強了螞蟻搜索過程中對最優(yōu)解的探索能力，它們之間的差異僅在于搜索控制策略方面。而且，取得了最佳結果的ACO是通過引入局部搜索算法實現(xiàn)的，這實際上是一些結合了標準局域搜索算法的混合型概率搜索算法，有利于提高蟻群各級系統(tǒng)在優(yōu)化問題中的求解質(zhì)量。蟻群算法的研究現(xiàn)狀 因此，其后的ACO研究工作主要都集中于AS性能的改進方面。較早的一種改進方法是精英策略(Elitist Strategy)，其思想是在算法開始后即對所有已發(fā)現(xiàn)的最好路徑給予額外的增強，并將隨后與之對應的行程記為Tgb(全局

10、最優(yōu)行程)，當進行信息素更新時，對這些行程予以加權，同時將經(jīng)過這些行程的螞蟻記為“精英”，從而增大較好行程的選擇機會。這種改進型算法能夠以更快的速度獲得更好的解。但是若選擇的精英過多則算法會由于較早的收斂于局部次優(yōu)解而導致搜索的過早停滯。 蟻群算法的研究現(xiàn)狀 為了進一步克服AS中暴露出的問題，提出了蟻群系統(tǒng)(Ant Colony System, ACS)。該系統(tǒng)的提出是以Ant-Q算法為基礎的。Ant-Q將螞蟻算法和一種增強型學習算法Q-learning有機的結合了起來。ACS與AS之間存在三方面的主要差異：首先，ACS采用了更為大膽的行為選擇規(guī)則；其次，只增強屬于全局最優(yōu)解的路徑上的信息素。

11、其中，01是信息素揮發(fā)參數(shù)， 是從尋路開始到當前為止全局最優(yōu)的路徑長度。蟻群算法的研究現(xiàn)狀 在對AS進行直接完善的方法中，MAX-MIN Ant System是一個典型代表。該算法修改了AS的信息素更新方式，每次迭代之后只有一只螞蟻能夠進行信息素的更新以獲取更好的解。為了避免搜索停滯，路徑上的信息素濃度被限制在MAX，MIN 范圍內(nèi)，另外，信息素的初始值被設為其取值上限，這樣有助于增加算法初始階段的搜索能力。蟻群算法的研究現(xiàn)狀 另一種對AS改進的算法是Rank-based Version AS。與“精英策略”相似，在此算法中總是更新更好進程上的信息素，選擇的標準是其行程長度 決定的排序，且每個

12、螞蟻放置信息素的強度通過下式中的排序加權處理確定，其中，為每次迭代后放置信息素的螞蟻總數(shù)。 蟻群算法的研究現(xiàn)狀 這種算法求解TSP的能力與AS、精英策略AS、遺傳算法和模擬退火算法進行了比較。在大型TSP問題中（最多包含132座城市），基于AS的算法都顯示出了優(yōu)于GA和SA的特性。而且在Rank-based AS和精英策略AS均優(yōu)于基本AS的同時，前者還獲得了比精英策略AS更好的解。 蟻群算法的其他應用 蟻群算法在解決很多組合問題上都取得比較理想的效果。其中有兩個比較著名的組合問題，QAP問題和JSP問題(JobShop Scheduling Problem)作相應調(diào)整的蟻群算法可以比較好地解

13、決這兩個組合問題。另外，將蟻群算法對實際問題的解決也取得一定的進展，如大規(guī)模集成電路中的綜合布線以及電信網(wǎng)絡中的路由等方面的應用。智能蟻群算法及應用 吳啟迪 上?？萍汲霭嫔鐝幕窘Y構、算法特點、改進方法、突破途徑、實現(xiàn)模式及應用模式等方面進行了論述。主要內(nèi)容有蟻群算法的由來、研究成果、應用綜述、算法的具體描述及改進、算法的典型優(yōu)化問題求解模式、算法的典型應用及拓展應用。參考書推薦目前，除了業(yè)界已得到公認的遺傳算法、模擬退火法、禁忌搜索法、人工神經(jīng)網(wǎng)絡等熱門進化類方法，新加入這個行列的蟻群算法開始嶄露頭角，為復雜困難的系統(tǒng)優(yōu)化問題提供了新的具有競爭力的求解算法。蟻群算法思想在啟發(fā)式方法范疇內(nèi)已逐漸成為一個獨立的分支，在有關國際會議上多次作為專題加以討論。這種由歐洲學者提出并加以改進的新穎系統(tǒng)思想，正在受到越來越多的人的注意和研究，應用范圍也開始遍及許多領域：例如交通網(wǎng)絡中的最佳路徑