摘要：蟻群算法是模擬螞蟻活動(dòng)規(guī)律而提出的一種元啟發(fā)式優(yōu)化算法，研究表明其具有很多優(yōu)點(diǎn)，在解決優(yōu)化問(wèn)題時(shí)表現(xiàn)出很好特性，但也存在一些缺陷。因此，許多學(xué)者提出了許多改進(jìn)算法。該文對(duì)算法的改進(jìn)策略進(jìn)行研究，形成結(jié)論，為算法進(jìn)一步發(fā)展提供參考。

關(guān)鍵詞：蟻群算法；缺陷；改進(jìn)算法；改進(jìn)策略

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）28-6674-03

蟻群算法（Ant Colony Optimization，ACO）是由意大利學(xué)者M(jìn) Dorigo在1991年根據(jù)螞蟻活動(dòng)規(guī)律從而提出的一種仿生學(xué)的優(yōu)化算法，并把其應(yīng)用在求解TSP問(wèn)題，表現(xiàn)出了很好的特性。[1] 算法得到了有很快的發(fā)展，應(yīng)用領(lǐng)域也不斷的拓廣，因此對(duì)于該算法的研究就顯得尤其重要，但是任何一種算法并不能完美，其存在著一些缺陷，如收斂速度慢，容易陷入局部最優(yōu)等缺陷，所以很多學(xué)者提出了改進(jìn)方法，對(duì)算法的改進(jìn)方法總結(jié)，就成為必要的課題。

1 蟻群算法基本原理

在對(duì)螞蟻覓食過(guò)程進(jìn)行研究之后，發(fā)現(xiàn)螞蟻可以在路徑上留下一種叫做信息素的物質(zhì)，并且螞蟻能感知這種信息，并會(huì)向著信息素濃度高的方向移動(dòng)。螞蟻個(gè)體之間通過(guò)這種方式進(jìn)行聯(lián)系，于是群體的覓食行為就表現(xiàn)出一種正反饋性。在覓食過(guò)程中某一條路徑越短，其信息素濃度會(huì)越高，經(jīng)過(guò)的螞蟻會(huì)越多，反之路徑越長(zhǎng)，經(jīng)過(guò)的螞蟻越少，信息素濃度會(huì)越低，這就是算法的基本原理。

為了敘述方便我們以[n]個(gè)城市[TSP]問(wèn)題為例，其中[m]螞蟻數(shù)量，[dij]為兩城市之間距離，[bi（t）][i=（1]、2……[n）]是[t]時(shí)刻城市[i]螞蟻的數(shù)量，那么[m=i=1nbi（t）]。

螞蟻系統(tǒng)：我們將[m]只螞蟻隨機(jī)放到平面上[n]個(gè)城市，同時(shí)記錄每一只螞蟻所在的城市，設(shè)城市之間路徑上信息素一樣，即[τij（0）=c（c]是常數(shù)[）]。接下來(lái)螞蟻按照覓食規(guī)則選擇下一城市。在[t]時(shí)刻螞蟻[k]從[i]城市轉(zhuǎn)移到[j]城市的概率為[pkij（t）]，其中

2 蟻群算法的改進(jìn)

蟻群算法得到很快發(fā)展，但是其本身是存在一些缺陷，于是很多學(xué)者提出很多改進(jìn)方法，總結(jié)起來(lái)，我們從以下幾個(gè)方面進(jìn)行論述。

2.1 信息素的更新策略

蟻群算法中信息素起著重要作用，對(duì)算法的改進(jìn)最先也是從信息素的更新開(kāi)始的。

M Dorigo等在1997年針對(duì)蟻群算法的不足提出一種蟻群系統(tǒng)（Ant Colony System，ACS），這個(gè)系統(tǒng)的提出是以Ant Q算法[2]為基礎(chǔ)的。其中ACS為了避免螞蟻陷入局部最優(yōu)在信息素的更新上實(shí)施新方法，其只對(duì)最優(yōu)路徑上的信息素進(jìn)行更新，同時(shí)還引入了揮發(fā)機(jī)制，即螞蟻?zhàn)哌^(guò)的路徑上除信息素要增加外還要揮發(fā)一部分，從而實(shí)現(xiàn)一種信息素局部調(diào)整以減小已選擇過(guò)的路徑再次被選擇的概率。ACS對(duì)于AS算法的該進(jìn)提高了其性能。在同年 T.Stützle， H.Hoos對(duì)AS算法進(jìn)行了直接改進(jìn)，該改進(jìn)方法是在AS的基礎(chǔ)上直接進(jìn)行，對(duì)信息素進(jìn)行限定，即MAX-MIN Ant System[3]。算法中信息素更新方式規(guī)定，每次迭代后只有一只螞蟻進(jìn)行信息素更新。為了避免陷入局部最優(yōu)，信息素濃度被限制在[[τmin，τmax]]范圍內(nèi)，除此之外，信息素初始值為取值上限，這樣初始階段的搜索能力較強(qiáng)。MMAS算法得到了廣泛應(yīng)用，但還是存在一些缺點(diǎn)，如消耗時(shí)間較長(zhǎng)。2007年薛莉等提出了一種雙信息素更新的蟻群算法，該算法通過(guò)對(duì)全局信息素和接近最優(yōu)路經(jīng)上的信息素進(jìn)行更新，改善蟻群算法的尋優(yōu)能力。[4]2008年，李亞韞等提出信息素?cái)U(kuò)散蟻群算法用于求解TSP問(wèn)題，該文引入了擴(kuò)散模型，使得算法更逼真，更加接近螞蟻真實(shí)行為，加大了螞蟻之間的協(xié)作，加快了算法的收斂速度。[5]2013年趙偉等人提出了一種基于懲罰函數(shù)和新信息素更新方式的蟻群算法，該文引入了局部和全局信息素更新的新方式并且引入了懲罰函數(shù)，降低了算法的復(fù)雜度，并且減小了搜索范圍，有利于發(fā)現(xiàn)較好的解。[6]孟祥萍等人提出了基于方向信息素協(xié)調(diào)的蟻群算法，該算法定義了一種新的信息素，該種信息素刻畫全局信息，其使算法求得的解是最優(yōu)解，并能加快算法的收斂速度。[7]

綜上所述，以上的改進(jìn)算法，都有效提高了算法性能，使得螞蟻尋優(yōu)能力更強(qiáng)，并有效避免算法的停滯，是行之有效的改進(jìn)策略。

2.2 螞蟻本身特性的改進(jìn)

蟻群算法改進(jìn)的另外一方面便是螞蟻本身的特性。2008年汪采萍等提出具有變異特性的蟻群算法，并應(yīng)用于求解TSP問(wèn)題，該變異采用遺傳算法中的變異對(duì)蟻群進(jìn)行變異，該方法保存了蟻群的多樣性，有效避免算法陷入停滯，使蟻群具有發(fā)現(xiàn)較好解的能力。[8]2008年鄭松等提出了動(dòng)態(tài)調(diào)整選擇策略的蟻群算法，算法使得螞蟻具有新特性，該種螞蟻能夠?qū)π畔⑺貪舛容^低的路徑探索，有效加大搜索范圍，避免陷入局部最優(yōu)。[9]2009年薛晗等提出生存模糊自適應(yīng)蟻群算法，其使得螞蟻個(gè)體具有適應(yīng)度，保證了螞蟻種群多樣性以及生存時(shí)間，改進(jìn)算法更有效，更穩(wěn)定。[10]2013年吳華鋒等提出基于自然選擇特性的蟻群算法，使螞蟻具有自然選擇特性即優(yōu)勝劣汰的進(jìn)化策略，其在解決TSP上表現(xiàn)出很好的特性。[11]

螞蟻特性的改進(jìn)是算法改進(jìn)新方向，改進(jìn)時(shí)加入新特性，使螞蟻在尋求最優(yōu)解上表現(xiàn)出很好的特性，在跳出局部最優(yōu)方面也表現(xiàn)出了有效性。

2.3 算法的融合方面

算法的改進(jìn)層出不窮，科技發(fā)展到今天各種智能算法不斷出現(xiàn)，每種算法都有自己的優(yōu)缺點(diǎn)，所以我們把具有不同優(yōu)點(diǎn)的算法進(jìn)行綜合、融合就成為算法改進(jìn)另外一個(gè)重要方向。

2008年黃立君、許永花，提出了遺傳算法與蟻群算法融合新算法，分別利用了兩種算法的優(yōu)點(diǎn)進(jìn)行結(jié)合，并將其應(yīng)用于求解TSP問(wèn)題，表現(xiàn)出很好的特性。[12]2010年，劉好斌等人將蟻群算法和免疫算法的優(yōu)點(diǎn)進(jìn)行有機(jī)結(jié)合形成了帶免疫變異的蟻群算法，其表現(xiàn)出很好的穩(wěn)定性和尋優(yōu)能力。[13]2013年李擎等將粒子群算法與蟻群算法進(jìn)行結(jié)合，利用粒子群算法的優(yōu)點(diǎn)對(duì)蟻群算法參數(shù)進(jìn)行優(yōu)化，從而改進(jìn)了蟻群算法耗時(shí)大的缺陷，是對(duì)蟻群算法的很好補(bǔ)充，該算法應(yīng)用于求解優(yōu)化問(wèn)題，表現(xiàn)出很好的特性。[14]

隨著計(jì)算機(jī)技術(shù)的發(fā)展，新算法不斷的出現(xiàn)，算法融合的改進(jìn)方法將成為算法改進(jìn)的重要方面，有著很廣的前景。

2.4 應(yīng)用領(lǐng)域

算法始終都是為了解決實(shí)際問(wèn)題，對(duì)于算法改進(jìn)的另一個(gè)方面即使對(duì)算法應(yīng)用領(lǐng)域的不斷拓展。

蟻群算法從一開(kāi)始出現(xiàn)便應(yīng)用于求解TSP問(wèn)題，隨著算法的發(fā)展應(yīng)用領(lǐng)域不斷擴(kuò)大，已經(jīng)滲透到組合優(yōu)化、指派問(wèn)題、圖像處理、城市路徑規(guī)劃、網(wǎng)絡(luò)路由、單機(jī)調(diào)度、電路分布線等各個(gè)方面，表現(xiàn)出很強(qiáng)生命力。2008年張景虎等將蟻群算法進(jìn)行改進(jìn)應(yīng)用于圖像處理，對(duì)CT圖像的邊緣進(jìn)行檢測(cè)，表現(xiàn)出很好的性質(zhì)。[15]2011年張瀟等將蟻群算法進(jìn)行適當(dāng)改進(jìn)并應(yīng)用于求解車輛路徑問(wèn)題，表現(xiàn)出很好的穩(wěn)定性以及尋求最優(yōu)解的能力。[16]

算法終究要應(yīng)用于實(shí)際，雖然現(xiàn)在對(duì)于蟻群算法應(yīng)用的文章不在少數(shù)，但是都是簡(jiǎn)化之后的簡(jiǎn)單應(yīng)用，對(duì)于應(yīng)用的研究還有很長(zhǎng)的路要走，這也是對(duì)算法進(jìn)行改進(jìn)的一個(gè)重要方面。

3 結(jié)論、展望

蟻群算法的發(fā)展告訴我們，蟻群算法是一種具有研究?jī)r(jià)值的算法，隨著科技發(fā)展，仿生算法會(huì)成為智能計(jì)算的重要部分，蟻群算法的研究也將是一個(gè)長(zhǎng)期研究的課題，現(xiàn)在對(duì)于蟻群算法的改進(jìn)策略雖然很多，但還有很多方面做的還不夠，有待于進(jìn)一步深入。

1） 對(duì)于蟻群算法的理論研究還不夠深入，其收斂性的證明還沒(méi)有完整的理論依據(jù)；對(duì)于算法的參數(shù)設(shè)置還處于實(shí)驗(yàn)階段，沒(méi)有選擇的理論依據(jù)。

2） 算法應(yīng)用領(lǐng)域還不夠?qū)拸V，雖然現(xiàn)在算法應(yīng)用文章比較多，但是大多數(shù)只是在理論方面的應(yīng)用還沒(méi)有真正應(yīng)用到實(shí)際中去，這方面還需要不斷推廣。

3） 現(xiàn)在新仿生算法不斷出現(xiàn)，與這些算法的結(jié)合，還需要進(jìn)一步加強(qiáng)，不斷完善算法的特性，解決更多實(shí)際問(wèn)題。

參考文獻(xiàn)：

[1] Dorigo M， Maniezzo V， Colorni A. Positive feedback as a search strategy[R]. TechnicalReport 91-016， Dipartimento di Elettronica， Politecnico di Milano， IT 1991.

[2] Dorigo M， Gambardella L M. A study of some properties of Ant-Q[C]//Proceedings of PPSN-IV，F(xiàn)ourth International Conference on Parallel Problem Solving From Nature.Berlin：SpringerVerlag，1996，656-665.

[3] Stutzle T， Hoos H. The MAX-MIN ant system and local search for the traveling salesman problem[C]//Baeck T， Michalewiez Z， Yao X. Proceedings of IEEE-ICEC-EPS1997，IEEE International Conference on Evolutionary Computation and Evolutionary Programming Conference.IEEE Press，1997，309-314.

[4] 薛莉，戴居豐，魏志成.雙信息素蟻群算法法及其在TSP中的應(yīng)用研究[J].計(jì)算機(jī)仿真，2007，24（8）：167-170.

[5] 李亞韞，杜永貴.用于求解TSP 的信息素?cái)U(kuò)散蟻群算法[J].機(jī)械工程與自動(dòng)化，2008，3：39-41

[6] 趙偉，蔡興盛，曲慧雁.一種基于懲罰函數(shù)和新信息素更新方式的蟻群算法[J].計(jì)算機(jī)工程與科學(xué)，2013，35（3）：103-107.

[7] 孟祥萍，片兆宇，沈中玉，等.基于方向信息素協(xié)調(diào)的蟻群算法[J]. 控制與決策，2013，28（5）：782-786.

[8] 汪采萍，胡學(xué)鋼.具有分段和變異特性的蟻群算法求解TSP 問(wèn)題[J].計(jì)算機(jī)技術(shù)與發(fā)展，2008，18（6）：90-93.

[9] 鄭松，侯迪波，周澤魁.動(dòng)態(tài)調(diào)整選擇策略的改進(jìn)蟻群算法[J].控制與決策，2008，23（2）：225-228.

[10] 薛晗，李迅，馬宏緒.生存模糊自適應(yīng)的蟻群算法及收斂性[J].控制與決策，2009，24（9）：1288-1293.

[11] 吳華鋒，陳信強(qiáng)，毛奇凰，等.基于自然選擇策略的蟻群算法求解TSP 問(wèn)題[J].通信學(xué)報(bào)，2013，34（4）：165-170.

[12] 黃立君，許永花.遺傳算法和蟻群算法融合求解TSP[J].東北農(nóng)業(yè)大學(xué)學(xué)報(bào)，2008，39（4）：109-113.

[13] 劉好斌，胡小兵，趙吉東.帶免疫變異的蟻群優(yōu)化算法[J].計(jì)算機(jī)仿真.2010，27（12）：221-224.

[14] 李擎，張超，陳鵬，等.一種基于粒子群參數(shù)優(yōu)化的改進(jìn)蟻群算法[J].控制與決策，2013，28（6）：873-878.

[15] 張景虎，郭敏，王亞文.基于改進(jìn)蟻群算法的CT圖像邊緣檢測(cè)方法研究[J].計(jì)算機(jī)應(yīng)用，2008，28（5）：1236-1239.

[16] 張瀟，王江晴.混合蟻群算法在車輛路徑問(wèn)題中的應(yīng)用[J].計(jì)算機(jī)工程，2011，37（24）：190-192.