一種改進的蟻群算法

趙吉東

摘要：蟻群算法是一種元啟發(fā)算法，其具有比較好的發(fā)現(xiàn)優(yōu)化問題較好解的能力，但還有一些不足。該文為了克服算法存在一些不足，對算法提出了改進，通過改變蟻群算法信息素的更新策略，提高算法的性能，并將改進后的算法應(yīng)用于求解TSP問題，數(shù)據(jù)結(jié)果顯示該算法發(fā)現(xiàn)較好解的能力較強。

關(guān)鍵詞：蟻群算法；信息素更新；TSP

中圖分類號：TP18 文獻標(biāo)識碼：A 文章編號：1009-3044（2015）08-0192-02

【Abstract】：窗體頂端

Abstract： Ant colony algorithm is a meta-heuristic algorithm， which has a relatively good ability to find better solutions for optimization problems， but there are some drawbacks.In this paper， the algorithm in order to overcome the drawbacks of the proposed algorithm， which by changing the ant colony algorithm pheromone update strategy to improve the performance of the algorithm，and improved algorithm is applied to solve TSP problem， the data showed that the algorithm found a strong ability to better solution.

Key word： Ant colony algorithm；pheromone update；TSP

蟻群算法（Ant Colony Optimization 簡稱ACO）是一種模擬螞蟻群體性覓食活動而形成的進化算法，是由M Dorigo等學(xué)者首先提出的。[1-2]隨后，國內(nèi)的不少學(xué)者開始研究改算法，并且發(fā)現(xiàn)了該算法具有很好的解決優(yōu)化問題的能力，尤其是離散型的優(yōu)化問題，同時由于蟻群算法的正反饋性、魯棒性以及容易與其他的算法融合的特點，其正在生活中的各個領(lǐng)域得到廣泛的應(yīng)用。

最初，蟻群算法用來解決了資源的二次分配問題以及TSP問題。但是蟻群算法在解決問題的同時也被發(fā)現(xiàn)還有不少的缺陷，比如在計算中容易陷入停滯狀態(tài)、局部最優(yōu)，還存在著運算時間較長的缺陷。針對蟻群算法缺陷很多的學(xué)者提出了改進的算法。[3-5]本文就其缺點中的陷入局部最優(yōu)的缺陷進行了改進，并且用來解決旅行商問題，標(biāo)明改算法具有一些好的性質(zhì)。

1 改進算法

3 結(jié)束語

蟻群算法是一種來自大自然的隨機搜索尋優(yōu)方法，現(xiàn)已經(jīng)陸續(xù)應(yīng)用于圖像處理、智能交通等很多領(lǐng)域[6-7]，并具有極強發(fā)展?jié)摿Γ疚尼槍υ撍惴ㄌ岢隽烁倪M方法，并且應(yīng)用于的求解，表現(xiàn)出較好的特性，但是我們不難發(fā)現(xiàn)對于蟻群算法的改進之優(yōu)劣還是只能通過計算機模擬所得到的實驗數(shù)據(jù)進行驗證，參數(shù)的選擇也只能通過編程實驗來確定，缺乏嚴(yán)格的數(shù)學(xué)證明，蟻群算法還有很多理論性的工作需要進一步開展。

參考文獻：

[1] Colorni A，Dorigo M，Maniezzo V，etal.Distributed optimization by ant colonies.Proceedings of the 1st European Conference on Artificial Life，1991：134-142.

[2] Dorigo M. Optimiztion， Learning and Natural Algorithma（in Italian）[D]. Ph.D. thesis， Dipartimento di Elettronica， Politecnico di Milano， IT， 1992.

[3] 宋錦娟，白艷萍.一種改進的蟻群算法及其在TSP中的應(yīng)用[J].數(shù)學(xué)的實踐與認(rèn)識，2012，42（18）：154-162.

[4] 孫晶，白艷萍.一種改進的混合型蟻群算法在TSP問題中的應(yīng)用[J].數(shù)學(xué)的實踐與認(rèn)識，2013，43（12）：174-181.

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

[6] 胡慧，何聚厚，何秀青.基于模糊理論和蟻群算法的圖像邊緣連接方法[J].計算機工程與應(yīng)用，2014，50（3））：168-172.

[7] 冀俊忠，黃振，劉椿年.改進蟻群算法在智能交通中的應(yīng)用[J].數(shù)學(xué)的實踐與認(rèn)識，2013，43（3）：66-72.