螞蟻演算法應用於最佳化路徑演算

Optimal Path Computation Using Ant Algorithm

羅文光(Wen-Kuang Lo)

指導教授 ： 林志民

元智大學/工程學院/電機工程學系/碩士(2004年)

摘要

昆蟲群體聚集的智慧行為，可以延伸出來並實際運用到各種不同例子，其中螞蟻也是基於群體行為，藉著螞蟻藉找尋食物時，會在行經巢穴與食物間的路徑上，留下一種化學物質費洛蒙（Pheromone），而螞蟻乃是藉由費洛蒙當作是間接溝通的管道，與其他螞蟻間相互傳遞訊息，然後建構一個螞蟻群體合作找尋食物的一個機制，然後可以利用螞蟻群體合作的原理來解決尋優問題，進而尋找出最短路徑。Dr.Macro Dorigo基於螞蟻的行為的概念，前後發展出幾種啟發式演算法，包括適合應用於解決組合最佳化問題的基本螞蟻系統演算法(Ant System,簡稱為AS)與蟻群系統演算法(Ant Colony System,簡稱為ACS)及適合應用於解決網路路由問題的Antnet Algorithm。本篇論文除了介紹螞蟻演算法及Antnet外，應用的例子分成兩個部分，第一是應用螞蟻演算法最佳化路徑演算來解決旅行業務員問題，並運算AS及ACS的研究模式，設定相同參數進行模擬，發現ACS較AS找到更佳的解，且更快收斂;第二是以AntNet應用於網路路由問題，運用一個簡單的網路節點然後送入資料封包進行模擬，經過模擬的結果顯示Antnet能夠依據當時網路資訊流量負載來選擇分配路徑，使此網路傳送具有很好的輸出吞吐量(Throughput)，說明Antnet具有很好的自適應性調整網路負載分配路由的能力。

關鍵字

螞蟻演算法 ； 最佳業務員問題 ； 適應性網路路由

並列摘要

The recently developed ant algorithms have been successfully applied to several combinatorial optimization problems. The heuristic algorithms based on the ants behavior concepts have been developed by Dr. Macro Dorigo, referred to as ant system (AS), ant colony system (ACS) and antnet algorithm (AntNet). The AS and ACS could find good solutions to combinatorial optimization problems. AntNet is a new algorithm for packet routing in networks. In AntNet, a group of mobile agents build paths between pair of nodes, exploring the network concurrently and exchanging data to update routing tables. This thesis introduces uses the AS and ACS to solve the traveling salesman problem (TSP) and uses the AntNet to the routing in networks. The first application is simulated for TSP problem using AS and ACS, and the second application is simulated using a simple network topology of the AntNet algorithm. In the first application, the comparison of results show that the ACS can achieve better solution than AS. The simulation results of the second application indicate that the Antnet can achieve favorable throughput. The AntNet Algorithm is an adaptive routing algorithm by distributing load over all possible paths for improving network throughput and keeping the good network traffic performance.

並列關鍵字

ant algorithm ； TSP ； adaptive network routing

參考文獻

[1] B. Bonabeau, M. Dorigo, and G. Thraulaz, Swarm Intelligence : from Natural to Artificial Systems, Oxford University Press,1999.

[2] M. Dorigo and S. Thomas, Ant Colony Optimization, ISBN 0-262-04219-3, 2004.

[3] E. Bonabeau, M. Dorigo and G. Theraulaz, “Inspiration for Optimization from Social Insect Behaviour”, Nature, vol.406, pp.39-43, 2000.

[4] S. Liang, A. N. Zincir-Heywood and M. I. Heywood, “The Effect of Routing under Local Information using a Social Insect Metaphor”, IEEE International Congress on Evolutionary Computation, pp.1438-1443, 2002.

[8] M. Dorigo, V. Maniezzo, and A. Colorni, “The Ant System Applied to the Quadratic Assignment Problem”, Technical Report, IRIDIA-Free Brussels University, Belgium, 1994.