蟻群算法綜述

1、智能計(jì)算蟻群算法基本綜述班級(jí)： 研1102班 專業(yè)： 計(jì) 算 數(shù) 學(xué) 姓名： 劉 鑫 學(xué)號(hào)： 2012年蟻群算法基本綜述劉 鑫（西安理工大學(xué)理學(xué)院，研1102班，西安市，）摘 要:蟻群算法( ACA)是一種廣泛應(yīng)用于優(yōu)化領(lǐng)域的仿生進(jìn)化算法。ACA發(fā)展背景著手，分析比較國內(nèi)外ACA研究團(tuán)隊(duì)與發(fā)展情況立足于基本原理,分析其數(shù)學(xué)模型,介紹了六種經(jīng)典的改進(jìn)模型，對(duì)其優(yōu)缺點(diǎn)進(jìn)行分析，簡要總結(jié)其應(yīng)用領(lǐng)域并對(duì)其今后的發(fā)展、應(yīng)用做 出展望。 關(guān)鍵詞: 蟻群；算法；優(yōu)化；改進(jìn)；應(yīng)用0 引言專家發(fā)現(xiàn)單個(gè)螞蟻只具有一些簡單的行為能力。但整個(gè)蟻群卻能完成一系列復(fù)雜的任務(wù)。這種現(xiàn)象是通過高度組織協(xié)調(diào)完成的1991年。意

2、大利學(xué)者M(jìn).Dorigo首次提出一種新型仿生算法ACA。研究了螞蟻的行為。提出其基本原理及數(shù)學(xué)模型。并將之應(yīng)用于尋求旅行商問題(TSP)的解。 通過實(shí)驗(yàn)及相關(guān)理論證明,ACA有著有著優(yōu)化的選擇機(jī)制的本質(zhì)。而這種適應(yīng)和協(xié)作機(jī)制使之具有良好的發(fā)現(xiàn)能力及其它算法所沒有的優(yōu)點(diǎn)。如較強(qiáng)的魯棒性、分布式計(jì)算、易與其他方法結(jié)合等；但同時(shí)也不應(yīng)忽略其不足。如搜索時(shí)間較長，若每步進(jìn)行信息素更新，計(jì)算仿真時(shí)所占用CPU時(shí)間過長：若當(dāng)前最優(yōu)路徑不是全局最優(yōu)路徑，但其信息素濃度過高時(shí)?？抗綄?duì)信息素濃度的調(diào)整不能緩解這種現(xiàn)象。會(huì)陷人局部收斂無法尋找到全局最優(yōu)解：轉(zhuǎn)移概率過大時(shí)，雖有較快的收斂速度，但會(huì)導(dǎo)致早熟收斂。所

3、以正反饋原理所引起的自催化現(xiàn)象意在強(qiáng)化性能好的解，卻容易出現(xiàn)停滯現(xiàn)象。筆者綜述性地介紹了ACA對(duì)一些已有的提出自己的想法，并對(duì)其應(yīng)用及發(fā)展前景提出了展望。1 蟻群算法概述 ACA源自于蟻群的覓食行為。S.Goss的“雙橋”實(shí)驗(yàn)說明螞蟻總會(huì)選擇距食物源較短的分支螞蟻之間通過信息素進(jìn)行信息的傳遞,捷徑上的信息素越多,吸引的螞蟻越多。形成正反饋 機(jī)制,達(dá)到一種協(xié)調(diào)化的高組織狀態(tài)該行為稱集體自催化目前研究的多為大規(guī)模征兵，即僅靠化學(xué)追蹤的征兵。1 .1 蟻群算法的基本原理為便于研究提出以下基本假設(shè)：螞蟻間通過信息素和環(huán)境進(jìn)行間接通信：螞蟻對(duì)環(huán)境的反應(yīng)由其內(nèi)部模決定：螞蟻個(gè)體是獨(dú)立的，但群體卻呈現(xiàn)出一種

4、隨機(jī)性。螞蟻通過適應(yīng) 和協(xié)作兩個(gè)階段的 調(diào)整從無序到有序，得到最優(yōu)解，完成對(duì)路徑的搜索。對(duì)路徑的選擇，重點(diǎn)在轉(zhuǎn)移概率，即某時(shí)刻螞在城市選擇城市的概率的大小。 （1）其中，和分別為上的參數(shù)和均勻分布的隨機(jī)數(shù)，其大小決定了利用先驗(yàn)知識(shí)與探 索新路徑之間的相對(duì)重要性。若，則轉(zhuǎn)移概率選取上面一個(gè)式子，即按照先驗(yàn)知識(shí)選擇最好的邊，否則，按照轉(zhuǎn)移概率選擇一條邊，式又被稱為偽隨機(jī)比例規(guī)則；為螞蟻下一 步允許選擇的城市；為能見度因子；為禁忌表；，分別反映螞蟻在運(yùn)動(dòng)過程中所積累的信息和啟發(fā)信息在螞蟻選擇路徑中的相對(duì)重要性；為信息素濃度的函數(shù)根據(jù)不同的模型，信息素做不同的調(diào)整，如全局更新規(guī)則和局部更新規(guī)則。2 蟻

5、群算法的發(fā)展蟻群優(yōu)化（ACO）研究受到真實(shí)蟻群行為啟發(fā)的智能系統(tǒng)，常用于解決離散優(yōu)化問題啟發(fā)式ACO是1991年由Dorigo和Gambardella提出定義的。2.1 國外蟻群算法的發(fā)展概況2.1.1 有關(guān)蟻群算法的研究團(tuán)隊(duì) 從ACO提出至今,越來越多的專家投身于蟻群算法的研究之中,其中較為突出的有以下四個(gè)：（1）瑞士盧加諾IDSIA。1998年建立是IDSIA是非營利性研究人工智能研究所，2000年成為公共研究機(jī)構(gòu)，隸屬于盧加諾大學(xué)的信息學(xué)院和瑞士意大利語區(qū)高等專業(yè)學(xué)院的科技創(chuàng)新系，主要負(fù)責(zé)人為Luca,Lepori,Carlo和Schmidhuber。其中一研究主題是人工螞蟻，該多代理方

6、法是受基于信息素交流的生物螞蟻啟發(fā)而來，由前高級(jí)研究員Dorigo和聯(lián)合負(fù)責(zé)人Luca領(lǐng)導(dǎo)研究的。其人工蟻和局部搜索算法的結(jié)合已經(jīng)成為解決某些圖形優(yōu)化任務(wù)的方法選擇，如車輛路徑和網(wǎng)絡(luò)路徑，其迅速發(fā)展促成許多商業(yè)應(yīng)用和關(guān)于人工螞蟻的專門會(huì)議。（2）比利時(shí)布魯塞爾IRIDIA。IRIDIA是布魯塞爾自由大學(xué)人工智能研究實(shí)驗(yàn)室，主要在理論上進(jìn)行深入研究以及計(jì)算智能應(yīng)用于優(yōu)化。在Dorigo和Bersini領(lǐng)導(dǎo)下，其主要研究領(lǐng)域?yàn)槿褐悄?、組合問題的求解和連續(xù)空間優(yōu)化問題的啟發(fā)式、生物網(wǎng)絡(luò)原理性研究以及 商業(yè)智能應(yīng)用四個(gè)方面，而有關(guān)于ACA的方向?yàn)槿褐悄芎驮獑l(fā)式。IRIDIA在群智能的ACO和群機(jī)器人

7、這兩方面處于世界領(lǐng)先地位，對(duì)于具體元啟發(fā)式的研究聚焦于ACO，主要研究點(diǎn)是研發(fā)一套合理的實(shí)驗(yàn)方法論，一套經(jīng)驗(yàn)學(xué)習(xí)和元啟發(fā)式構(gòu)建的發(fā)展工具的應(yīng)用，特別著重研究的是發(fā)展能夠設(shè)計(jì)和完善隨機(jī)局部搜索算法和元啟發(fā)式算法的方法論。近期研究AC A項(xiàng)目有：對(duì)AC A的基礎(chǔ)理論研究、復(fù)雜系統(tǒng)的智能計(jì)算方法、使用生物啟發(fā)和軟件計(jì)算的醫(yī)學(xué)成像、自組織的蟻群、走向型機(jī)器人群和群智能系統(tǒng)的通信策略。（3）) 奧地利維也納大學(xué)經(jīng)濟(jì)與統(tǒng)計(jì)商學(xué)院由Richard和Artner等組成的團(tuán)隊(duì)，主要研究遺傳算法、項(xiàng)目管理、最優(yōu)控制、ACO和電子裝配等研究課題其中，關(guān)于ACO方面的工作由Richard和Karl負(fù)責(zé)，從1999年開

8、始至今。(4)德國萊比錫大學(xué)并行計(jì)算與復(fù)雜系統(tǒng)Martin領(lǐng)導(dǎo)的數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)科學(xué)研究所的并行計(jì)算與復(fù)雜系統(tǒng)團(tuán)隊(duì)，關(guān)于ACA的主要研究是由人類前沿科學(xué)組織自主計(jì)劃的自然系統(tǒng)優(yōu)化，以及東風(fēng)集團(tuán)項(xiàng)目中的一些關(guān)于系統(tǒng)、模型和硬件算法等。2 .1 .2 有關(guān)蟻群算法的國際會(huì)議隨著人們對(duì)ACA越來越重視，相關(guān)會(huì)議也組織起來，來自世界各地的專家對(duì)ACA及其應(yīng)用展開研究討論，其中以Dorigo為大會(huì)總主席的ANTS最為權(quán)威。1998年在比利時(shí)布魯塞爾召開第一屆ACA研討會(huì)：從蟻群到人工蟻，每隔兩年召開一次蟻群優(yōu)化和群智能國際會(huì)議期間，2000年召開第二屆ACA 國際專會(huì)：從蟻群到人工蟻。另外，自

9、2005年在美國加利福尼亞州帕薩迪納威斯汀召開了IEEE群智能討論會(huì)，2006年、2007年分別在美國印第安州印第安納波利斯和美國夏威夷檀香山希爾頓村延續(xù)召開此會(huì)。除以上較為權(quán)威的會(huì)議，還有很多相關(guān)的國際會(huì)議，說明ACA在國際范圍內(nèi)得的重視，研究亦廣泛展開。2.2 國內(nèi)蟻群算法的發(fā)展概況國內(nèi)對(duì)該算法研究最早的是張紀(jì)會(huì)博士和徐心和教授1999年3月，他們首次簡單引進(jìn) ACA，從其基本原理、模型、偽碼流程進(jìn)行說明，對(duì)Oliver30 TSP問題分析說明，但未對(duì)基本模型中的參數(shù)進(jìn)行詳細(xì)地理論說明，且停止條件的界定較含糊，主要靠經(jīng)驗(yàn)決定其后引入的變異機(jī)制加快了收斂速度，使得到較優(yōu)解的周期縮短，并從計(jì)算

10、機(jī)仿真層面上證明其有效性。2001年，陳燁引入遺傳算法中用到的雜交算子來改善蟻群搜索速度慢、容易陷入局部最優(yōu)。但隨路程，的增長每次的代數(shù)顯著增加，計(jì)算量較大。同年8月， 郝晉等通過將轉(zhuǎn)移概率設(shè)置為轉(zhuǎn)移系數(shù)，結(jié)合擾動(dòng)策略以防止漏選最優(yōu)路徑，能夠節(jié)約計(jì)算時(shí)間，且能夠很好的克服算法容易陷入局部最優(yōu)的缺陷，計(jì)算精度也有提高但在關(guān)于倒指數(shù)的擾動(dòng)因子和均勻分布的隨機(jī)數(shù)的選擇并未解決，仍以實(shí)驗(yàn)為主要獲取手段而后李艷君等對(duì)自適應(yīng)ACA進(jìn)行了進(jìn)一步研究，對(duì)信息素采取自適應(yīng)更新，應(yīng)用于連續(xù)空間優(yōu)化問題的求解，并進(jìn)行了證 明 。2002年，王穎等對(duì)自適應(yīng)ACA作出了改進(jìn)，獲得了很好的結(jié)果。該ACA在進(jìn)化代數(shù)減少的情

11、況下，解的質(zhì)量也得到了一定提高，在一定程度上實(shí)現(xiàn)了收斂速度與解的質(zhì)量的平衡。但分析其復(fù)雜度可知，螞蟻的數(shù)目與問題規(guī)模不相上下，螞蟻數(shù)目增多會(huì)使收斂。速度過快，為防止該現(xiàn)象而將信息素?fù)]發(fā)悉數(shù)設(shè)置得比一般情況低一個(gè)數(shù)量級(jí)，而相關(guān)系數(shù) 儀、B、P等則由實(shí)驗(yàn)設(shè)定。當(dāng)螞蟻數(shù)量與問題規(guī)模相當(dāng)時(shí)，實(shí)驗(yàn)次數(shù)與時(shí)間是不容忽視的一個(gè)問題ACA除在原理層面進(jìn)行模型改進(jìn)。在應(yīng)用方面也有一定發(fā)展。如張宗永等將ACA作出改進(jìn)，配合隨機(jī)分布技術(shù)。應(yīng)用到分析上海市整個(gè)內(nèi)河航道和集裝箱運(yùn)輸?shù)倪^程中對(duì)內(nèi)河航道進(jìn)行規(guī)劃，最終得出合理的分配方案并提出了滿足最優(yōu)分配的河道改造的建議。2003年，陳岐等令人工蟻模仿真實(shí)螞蟻的感覺和知覺行

12、為，設(shè)置合理絕對(duì)感覺閾值以克服螞蟻在初始選擇時(shí)容易失去解的多樣性，改進(jìn)選擇策略以自適應(yīng)的修改路徑上的信息量 ，通過對(duì)不同規(guī)模和不對(duì)稱TSP的仿真說明算法具有較好的收斂性和穩(wěn)定性新I葉J的 啟發(fā)式搜索方法智能ACA，通過取消外激素、自動(dòng)凋整選擇最優(yōu)路徑的比例，改變選擇目標(biāo)城市的依據(jù)和引入擾動(dòng)，仿真結(jié)果說明在減少計(jì)算量的同時(shí)，可取得更好的搜索結(jié)果，但也指出通過實(shí)驗(yàn)確定相關(guān)的物理系數(shù)不利于算法的推廣但該文僅針對(duì)TSP，對(duì)其他問題能否應(yīng)用仍不明確。2004年，黃國銳等提出采用不同于傳統(tǒng)基本ACA所采用的蟻周模型，它采用了更貼近于真實(shí)螞蟻行為的蟻量模型。建立信息素?cái)U(kuò)散模型，使相距較近的螞蟻之間能夠更好地

13、進(jìn)行協(xié)作，文中仿真結(jié)果表明該算法的有效性然而文中雖在達(dá)到收斂所需進(jìn)化代數(shù)上較基本ACA有了很大的改進(jìn)。減少約4倍。但最短路徑長度的減少并不明顯，且參數(shù)的設(shè)定仍是以試驗(yàn)為手段，缺乏理論支撐。針對(duì)基本ACA容易陷入局部最優(yōu)、收斂慢等缺陷，許多新模型陸續(xù)提出，如基于云模型的ACA、對(duì)信息素的限制、回歸型的等，甚至還有不少研究者試圖從新的角度重新審視并嘗試性研究ACA，較為新穎的有從蟻群社會(huì)的“多態(tài)性”出發(fā)， 試圖以更貼近真實(shí)世界中螞蟻行為來研究ACA，發(fā)現(xiàn)更適應(yīng)較大規(guī)模的問題，以及將著眼于蟻群整體的研究，角度轉(zhuǎn)換到關(guān)注螞蟻個(gè)體的速度對(duì)算法的影響。為從根本上解決ACA不足，其收斂性的分析也在不斷展開，

14、如用動(dòng)態(tài)分階段的方式，而具體影響ACA的參數(shù)也越來越得到關(guān)注，如有相關(guān)討論，但參數(shù)如何設(shè)定并未有理論依據(jù)，如何建立通用標(biāo)準(zhǔn)來對(duì)參數(shù)進(jìn)行最優(yōu)設(shè)置仍是難點(diǎn)在研究的應(yīng)用范圍方面也從一開始的離散域擴(kuò)展到連續(xù)域，連續(xù)域中有關(guān)于收斂性的研究，以及新模型的設(shè)計(jì)也在進(jìn)行著。全國各高校及研究機(jī)構(gòu)也對(duì)該算 法展開了研究，如徐鋒、杜軍平的改進(jìn)蟻群算法在旅游路線規(guī)劃中的應(yīng)用研究等1999年從首次引入ACA至今，相關(guān)研究蓬勃發(fā)展，下圖為相關(guān)的論文題名和關(guān)鍵字的論文數(shù)量增長表。國內(nèi)對(duì)于ACA的研究也越來越深人，基于各類模型的ACA層出不窮，研究域也從散域擴(kuò)展到連續(xù)域，同時(shí)ACA在不斷與其他算法結(jié)合以克服本身的缺陷但國內(nèi)的

15、研究起步較晚，對(duì)于影響收斂性的、B等相關(guān)參數(shù)至今無法確定一套相關(guān)的理論來進(jìn)行設(shè)置，只能通過反復(fù)試驗(yàn)來大致確定一個(gè)參數(shù)范圍，且研究較多地停留在理論仿真，應(yīng)用到實(shí)踐中仍較少。而國外對(duì)于這些范圍的研究已經(jīng)較為成熟。2 .3 蟻群算法的改進(jìn)型ACA的收斂速度和最優(yōu)解的全局性是一對(duì)矛盾體，收斂速度過快，會(huì)導(dǎo)致早熟，陷入局部最優(yōu)解，而當(dāng)信息素更新不及時(shí)或算法計(jì)算量過大時(shí)，則導(dǎo)致收斂速度過慢而應(yīng)用不現(xiàn)實(shí)，為克服這些問題。相應(yīng)的改進(jìn)的ACA不斷提出。（1）帶精英策略的蟻群系統(tǒng)(AS)。在帶精英策略的AS中，為了使到目前為止所找出的最優(yōu)解在下一個(gè)循環(huán)中對(duì)螞蟻更有吸引力，在每次循環(huán)之后給予最優(yōu)解額外的信息素量它信

16、息素的更新為 ： （2）其中，表示經(jīng)螞蟻引起路徑上的信息素量的增加；是精英螞蟻的個(gè)數(shù)； 為所找出的最優(yōu)解的路徑長度。這種算法收斂速度快，且計(jì)算耗時(shí)短，但如果過大，搜索會(huì)局限于極值周圍，導(dǎo)致搜索的早熟收斂。(2)基于優(yōu)化排序的螞蟻系統(tǒng)?；趦?yōu)化排序的AS針對(duì)帶精英策略的AS的缺點(diǎn)，通過排序很好地抑制了早熟，尤其當(dāng)初始狀態(tài)各解的差異性不大時(shí)，效果顯著，但其中，第只最優(yōu)螞蟻引起的路徑上信息素量的增加 （3）為只最優(yōu)螞蟻引起的路徑)上信息素量的增加；由精英螞蟻引起的路徑 上的信息素量的增加。(3)最大一最小螞蟻系統(tǒng)（MMAS)。MMAS是由德國學(xué)者TStuetzle和H.Hoos提出的，其目的主要在于

17、防止過早的算法停滯現(xiàn)象，性能改進(jìn)在以下幾方面： 只允許其中的一個(gè)路徑更新信息素該路徑通常是最優(yōu)路徑，可以是所有或當(dāng)前周游中的最優(yōu)路徑即只有一只螞蟻進(jìn)行信息素更新，而用于信息素更新的螞蟻可能是迭代最優(yōu)螞蟻，也可能是全局最優(yōu)螞蟻；為了避免搜索的停滯，在每個(gè)解的元素上的信息素軌跡量的值被限制在一個(gè) 固定范圍內(nèi)；為了盡可能的擴(kuò)大搜索范圍，信息素軌跡初始值設(shè)為。該法的軌跡更新規(guī)則為 （4）其中，表示迭代最優(yōu)解或全局最優(yōu)解的值這也保證了在初始的搜索中，能夠保證最優(yōu)解的多樣性。盡管在算法中對(duì)信息素濃度進(jìn)行了最大和最小值的限制，但此限制還不足以在較長的運(yùn)行時(shí)間里持久消除停滯現(xiàn)象，故采用信息素的平滑機(jī)制：按照比

18、例更新的方法來調(diào)整信息素 的濃度，使信息素濃度的增加值正比于與邊上的信息素濃度的差值?；咀龇ㄊ牵?限定信息素濃度允許值的上下限，且采用了平滑機(jī)制，也就是不同點(diǎn)中的。在當(dāng)前路徑上的信息素濃度遠(yuǎn)遠(yuǎn)高于其它路徑時(shí)，會(huì)導(dǎo)致過度收斂，為了降低運(yùn)行時(shí)間 ，可增加候選解集的選擇概率，不僅能降低算法的運(yùn)行時(shí)間，還可提高該算法的性能這些改進(jìn)模式可以通過對(duì)一些較大規(guī)模的巡游問題求解加以證明。 在全局修正規(guī)則中，只讓實(shí)現(xiàn)最好周游的螞蟻釋放信息素它和改進(jìn)的狀態(tài)轉(zhuǎn)移規(guī)則相結(jié)合的搜索模式，保證了螞蟻在優(yōu)秀父輩完成的周游領(lǐng)域內(nèi)進(jìn)行更多搜索，這就使得相應(yīng)的求解速度大大提高。( 4 ) 最優(yōu)一最差螞蟻系統(tǒng)。鑒于AS搜索效率低

19、和質(zhì)量差的缺點(diǎn)，最優(yōu)一最差螞蟻系統(tǒng)增強(qiáng)了搜索過程的指導(dǎo)性，使螞蟻的搜索更集中于到當(dāng)前循環(huán)位置所找出的最好路徑的領(lǐng)域 內(nèi)，既避免的早熟收斂，又縮短的搜索時(shí)間，其模型為 （5）其中，為該算法引入的一個(gè)參數(shù)；，分別表示當(dāng)前循環(huán)中最差和最優(yōu)螞蟻的路徑長度；表示城市和城市之間的信息素軌跡量。(5)隨機(jī)擾動(dòng)蟻群算法。ACA的參數(shù)往往是通過反復(fù)試驗(yàn)，由經(jīng)驗(yàn)湊得的，但對(duì)算法的計(jì)算效率和收斂性會(huì)產(chǎn)生不利影響ACA的主要依據(jù)是信息正反饋原理和某種啟發(fā)式算法的結(jié)合，式1充分說明了這點(diǎn)。如果放到某條路徑上信息素越多且路徑越短，則該路徑被選中的概率越大，此時(shí)轉(zhuǎn)移概率基本不變，成為了“轉(zhuǎn)移系數(shù)”，由于螞蟻總是選擇轉(zhuǎn)移系數(shù)

20、最大的路徑，這個(gè)值就具有一定的確定性，而此時(shí)，隨機(jī)擾動(dòng)蟻群算法與基本蟻群算法相同，也就不可避免會(huì)出現(xiàn)停滯現(xiàn)象，由此提出了可變的擾動(dòng)因子。隨機(jī)擾動(dòng)蟻群算法的過程具 體分為“粗調(diào)”和“細(xì)調(diào)”兩部分“粗調(diào)”是事先設(shè)定信息素濃度和轉(zhuǎn)移概率，再調(diào)整系數(shù)和 ，而和的大小分別決定了某一路徑的信量對(duì)螞蟻選擇路徑的影響程度和路徑上信息量的更新程度，而“細(xì)調(diào)”則相反確定性選擇導(dǎo)致 螞蟻總是選擇轉(zhuǎn)移系數(shù)最大的路徑，而隨機(jī)選擇導(dǎo)致計(jì)算轉(zhuǎn)移系數(shù)時(shí)具有較強(qiáng)的隨性，正是兩者的共同作用才使算法具有更強(qiáng)的全局搜索能力。(6)動(dòng)態(tài)蟻群算法。動(dòng)態(tài)蟻群算法相對(duì)于傳統(tǒng)蟻群算法和最大一最小蟻群算法，其主要 的改進(jìn)在于；前者在迭代過程中，

21、在選擇目標(biāo)城市的標(biāo)準(zhǔn)時(shí)，沒有使用一個(gè)固定的標(biāo)準(zhǔn)，這樣就有利于減少進(jìn)化停滯現(xiàn)象后者兩者依據(jù)信息素和啟發(fā)函數(shù)來選擇目標(biāo)城市，如何依據(jù)這兩個(gè)因子選擇城市對(duì)算法的性能是非常關(guān)鍵的蟻群算法對(duì)信息素的強(qiáng)度沒有限制，因而容易 陷入局部最優(yōu)解，MMAS對(duì)信息素的強(qiáng)度給予了一定的范圍限制，大大改善了算法的性能而動(dòng)態(tài)蟻群算法的揮發(fā)因子是動(dòng)態(tài)變化。其信息素濃度越高。則揮發(fā)因子越大，濃度越低， 則揮發(fā)因子越小。這樣實(shí)際上就對(duì)信息素的濃度也進(jìn)行了限制，使信息素濃度不可能無 限增大，也不可能為零。(7)帶獎(jiǎng)懲策略的蟻群算法。帶獎(jiǎng)懲策略的蟻群算法采取獎(jiǎng)勵(lì)每次循環(huán)中的較優(yōu)解而懲罰一般性的解，限制信息素量的范圍，將揮發(fā)系數(shù)設(shè)為

22、相對(duì)較大值以抵消信息素兩極分化影響路徑選擇的隨機(jī)性，同時(shí)兼顧了提高收斂速度與避免早熟收斂。通過模擬實(shí)驗(yàn)，該方法讀對(duì)解決復(fù)雜組合優(yōu)化問題有很好的效果。但是對(duì)于獎(jiǎng)勵(lì)的螞蟻數(shù)目和信息素?fù)]發(fā)系數(shù)的取值只能通過實(shí)驗(yàn)來確定，當(dāng)遇到較大規(guī)模的問題時(shí)，計(jì)算量將會(huì)非常大，不易于實(shí)踐。 此外，自適應(yīng)ACA也是應(yīng)用較為廣泛的一種蟻群算法，一文中的實(shí)驗(yàn)表明由于采用自適應(yīng)選擇和 動(dòng)態(tài)調(diào)整策略，算法的性能明顯得到改善，該方法不僅能夠加快收斂速度，節(jié)省搜索時(shí)間，而且能夠克服停滯行，為的過早出現(xiàn)，有利于發(fā)現(xiàn)更好的解，這對(duì)于求解大規(guī)模優(yōu)化問題是十分有利的筆者對(duì)自適應(yīng)蟻群算法進(jìn)行了進(jìn)一步研究，對(duì)信息素采取自適應(yīng)更新，應(yīng)用于求解連

23、續(xù)空間優(yōu)化問題的，并進(jìn)行了證明。除了上述改進(jìn)型，還有其他如具有感覺和知覺特征的ACA、基于去交叉局部優(yōu)化策略的ACA、基于信息素?cái)U(kuò)散的ACA基于模式學(xué)習(xí)的小窗口ACA、帶聚類處理的ACA、基于云模型理論的A CA、基于信息熵的改進(jìn)ACA等據(jù)需要可以針對(duì)ACA模型中的不同參數(shù)進(jìn)行調(diào)整，甚至創(chuàng)新。3 蟻群算法的應(yīng)用與展望 3.1 蟻群算法的應(yīng)用概況 隨著蟻群算法研究的深入，其應(yīng)用也愈來愈廣泛，從宏觀上看，主要分為靜態(tài)組合優(yōu)化中的應(yīng)用和動(dòng)態(tài)組合優(yōu)化中的應(yīng)用，下面羅列了一些較為具體的應(yīng)用。此外，國家經(jīng)濟(jì)分配 問題的協(xié)作智能搜索方法、解決反應(yīng)堆再生器的多目標(biāo)優(yōu)化問題等以下是國內(nèi)一些論文中出現(xiàn)的關(guān)于ACA

24、的應(yīng)用范圍中的特例。 3.2 蟻群算法展望 近年研究ACA的研究人員和研究成果成幾何級(jí)數(shù)增長，蟻群算法表現(xiàn)出了其強(qiáng)大的生命力和廣闊的前景。在模型改進(jìn)方面，注意思維變換，比如嘗試逆向思維，試圖建立一個(gè)具有普遍適應(yīng)性的 ACA模型，而不僅僅是針對(duì)某一類特定的問題。對(duì)于從自然界真實(shí)蟻群的行為研究，進(jìn)一步剖析深層原因，提出更加智能化的蟻群混合行為模型。此外，很重要的一點(diǎn)就是擺脫已有框架，提出更具有創(chuàng)新性的ACA模型，尤其是與智能融合方面。在理論分析方面，由于 ACA是一種概率搜索算法，從數(shù)學(xué)理論上對(duì)其正確性與可靠性進(jìn)行嚴(yán)密的證明相對(duì)于確定性算法而言，是比較困難的。而GutijahrWJ首次利用有向圖論

25、對(duì)A C A進(jìn)行其收斂性方面的證明?，F(xiàn)階段AC A的眾多模型并沒有歸統(tǒng)于共同的框架之下，并且對(duì)于ACA在連續(xù)域的研究相對(duì)離散域而言還相對(duì)較少，所以對(duì)于收斂性的證明和理論分析值得進(jìn)一步深入研究。而對(duì)于蟻群方法的并行實(shí)現(xiàn)，而言，ACA本身隱含著一定的并行性，單只螞蟻在一次循環(huán)中獨(dú)立于其他螞蟻因此，從本質(zhì)上說，AC A應(yīng)以分布式的協(xié)同優(yōu)化計(jì)算方式為特征，而在串行計(jì)算機(jī)上對(duì)ACA的并行模擬并不能真正體現(xiàn)蟻群算法的本質(zhì)特征，因此，進(jìn)一步的研究工作還應(yīng)該開展ACA的并行機(jī)實(shí)現(xiàn)從目前的發(fā)展趨勢(shì)來看，最優(yōu)并行化將會(huì)成為發(fā)展重點(diǎn)。關(guān)于硬件實(shí)現(xiàn)，ACA能夠處理的電路規(guī)模不及常規(guī)電路綜合方法，算法的運(yùn)行時(shí)間時(shí)間、硬

26、件功能以及電路規(guī)模之間的協(xié)調(diào)平衡。同時(shí)，對(duì)蟻群算法的仿真硬件產(chǎn)品的可靠性、可測(cè)試性、普適性和魯棒性，問題也需要進(jìn)行進(jìn)一步的研究，尤其是實(shí)際應(yīng)用時(shí)的穩(wěn)定性。 然而最關(guān)鍵的突破點(diǎn)是如何從實(shí)際的現(xiàn)實(shí)問題中抽象出其理論模型，從而更加清晰明確地 與ACA結(jié)合應(yīng)用，在應(yīng)用中，如何進(jìn)行相關(guān)產(chǎn)品的批量生產(chǎn)以及市場應(yīng)用的推廣。特別是在技術(shù)規(guī)范以及國家標(biāo)準(zhǔn)方面未雨綢繆也是十分必要的。4 結(jié)語 ACA被廣泛用于理論與實(shí)際應(yīng)用的各個(gè)領(lǐng)域，從最基本的ACA初用于解決旅行商問題 ，到分析解決當(dāng)下的交通布線、貨物運(yùn)送、蛋白質(zhì)折疊等問題。ACA應(yīng)用領(lǐng)域之廣 ，效率之高空前，這和其本身所具有的一些特征是密不可分的。ACA提出之

27、際，其創(chuàng)始人對(duì)它的發(fā)展指出了四個(gè)的主要的研究方向；所提出模型和一般自催化過程的數(shù)學(xué)理論公式；通過研究這種算法能夠很好的用于解決問題的類型，該方法的一般性的評(píng)價(jià)；所提出的模型在人工智能領(lǐng)域的研究意義，尤其是在模式識(shí)別和機(jī)器學(xué)習(xí)領(lǐng)域；開發(fā)所提出模型的內(nèi)在并行 性，以此繪制并行體系結(jié)構(gòu)的遠(yuǎn)景。在以上方向的指導(dǎo)下，針對(duì)傳統(tǒng)ACA收斂速度慢、易陷入局部最優(yōu)及早熟收斂。的缺陷和早期的一些算法模型、收斂性等問題所存在的不確定性，研究者們不斷提出新的改進(jìn)模型，新近提出的量子ACA大大加速了各自算法的收斂速度，使得并行計(jì)算和魯棒性得到了強(qiáng)化，但 是由于研究時(shí)間不長，缺乏堅(jiān)實(shí)的理論基礎(chǔ)，而且其可行性是建立在實(shí)驗(yàn)仿

28、真的基礎(chǔ)上。至今，蟻群算法仍然沒有一個(gè)普適性的數(shù)學(xué)模型，尤其是在信息素更新方面，它的主要參數(shù)的手段也是建立在實(shí)驗(yàn)。仿真基礎(chǔ)上，從而導(dǎo)致理論基礎(chǔ)相對(duì)薄弱。某種蟻群優(yōu)化算法的延拓性在實(shí)踐應(yīng)用上對(duì)一般ACA 并不適用，也就是缺乏普適性，而且AS、MMAS等的收斂性的結(jié)果并不能預(yù)測(cè)最優(yōu)解能何時(shí)找到。參考文獻(xiàn)1 Alberto Colomi，Macro Dofigo etc.Distributed Optimization by Ant Colonies.Elsevier Publis- -hingM,19912 陳峻.基于分布均勻度的自適應(yīng)蟻群算法J.軟件學(xué)報(bào),2003(14) 3 王劍.蟻群算法的理

29、論與應(yīng)用J.機(jī)電工程,2003(20) 4 張紀(jì)會(huì).自適應(yīng)蟻群算法J.控制理論與應(yīng),2000(2) 5 李士勇.蟻群算法及其應(yīng)用M.哈爾濱哈:爾濱工業(yè)大學(xué)出版社.2006 張紀(jì)會(huì).一種新的進(jìn)化算法蟻群算法J.系統(tǒng)工程理論與實(shí)踐,1999(3) 7 張紀(jì)會(huì).具有變異特征的蟻群算法J.計(jì)算機(jī)研究與發(fā)展.1999(10) 8 陳燁.帶雜交算子的蟻群算法J.計(jì)算機(jī)工程,2001(12) 9 郝晉.具有隨機(jī)擾動(dòng)特性的蟻群算法J.儀器儀表學(xué)報(bào),2001(8) 10 李艷君.連續(xù)空間優(yōu)化問題的自適應(yīng)蟻群系統(tǒng)算法J.模式識(shí)別與人工智能2001 (12)11 王穎.一種自適應(yīng)蟻群算法及其仿真研究J.系統(tǒng)仿真學(xué)報(bào),2002 (1) l2 張宗永.蟻群算法的改進(jìn)及其應(yīng)用J.上海交通大學(xué)學(xué)報(bào).2002(11)