(3.236.118.225) 您好!臺灣時間:2021/05/16 15:06
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:羅文光
研究生(外文):Wen-Kuang Lo
論文名稱:螞蟻演算法應用於最佳化路徑演算
論文名稱(外文):Optimal Path Computation Using Ant Algorithm
指導教授:林志民林志民引用關係
指導教授(外文):Chih-Min Lin
學位類別:碩士
校院名稱:元智大學
系所名稱:電機工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2005
畢業學年度:93
語文別:英文
論文頁數:52
中文關鍵詞:螞蟻演算法最佳業務員問題適應性網路路由
外文關鍵詞:ant algorithmTSPadaptive network routing
相關次數:
  • 被引用被引用:5
  • 點閱點閱:415
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
昆蟲群體聚集的智慧行為,可以延伸出來並實際運用到各種不同例子,其中螞蟻也是基於群體行為,藉著螞蟻藉找尋食物時,會在行經巢穴與食物間的路徑上,留下一種化學物質費洛蒙(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.
Chapter 1 Introduction
1.1 Overview of the Ant Colonies...............................1
1.2 Ants’ Foraging Behavior...................................2
1.3 A Brief of Ant Algorithms..................................8
1.4 A Brief of AntNet..........................................9
1.5 Thesis Overview...........................................10
Chapter 2 Methodologies of Ant System Algorithm and Ant Colony System Algorithm
2.1 Methodology of Ant System Algorithm.......................11
2.1.1 Ant system process chart...................................13
2.1.2 Ant system process steps..............................14
2.2 Methodology of Ant Colony System Algorithm................16
2.2.1 Ant colony system process chart........................18
2.2.2 Ant colony system process steps........................18
2.3 Difference between Local Updating Rule and Global Updating Rule..............................................................22
Chapter 3 Methodology of Antnet Algorithm
3.1 Overviewof the Routing Algorithm..........................23
3.2 Overview of the AntNet Algorithm..........................24
3.2.1 Antnet algorithm description..........................25
3.2.2 Example of explanation....................................32
Chapter 4 Simulation Results
4.1 Implement the AS Algorithm................................38
4.1.1 Parameter settings....................................38
4.1.2 Simulation result.....................................39
4.2 Implement the ACS Algorithm...............................39
4.2.1 Parameter settings....................................39
4.2.2 Simulation result.....................................40
4.3 Comparison of AS and ACS.....................................41
4.4 Simulation of Antnet Algorithm...............................42
4.4.1 Parameter settings.........................................42
4.4.2 Simulation result..........................................43
Chapter 5 Conclusions and Future Studies
5.1 Conclusions..................................................45
5.2 Future Studies...............................................46
5.2.1 Tuning the parameters to improve performance..............46
5.2.2 Ant algorithm to solve vehicle routing problem............46
[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.
[5] M. Dorigo, G. D. Caro and L. M. Gambardella, “Ant Algorithms for Discrete Optimization”, Artificial Life, vol. 5, pp. 137–172, 1999.
[6] A. Colorni, M. Dorigo, F. Maffioli, V. Maniezzo, G. Righini and M. Trubian, “Heuristics from Nature for Hard Combinatorial Problems”, International Transactions in Operational Research, vol. 3, pp. 1–21, 1996.
[7] M. Dorigo, V. Maniezzo and A. Colorni, “Ant System: Optimization by a Colony of Cooperating Agents”, IEEE Transactions on Systems, Man, and Cybernetics-part B: Cybernetics, vol.26, no.1, pp.29-41, 1996.
[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.
[9] A.Bauer ,B. Bullnheimer ,R. Hartl and C. Strauss, “An Ant Colony Optimization Approach for the Single Machine Tool Tardiness Problem”, Congress on Evolutionary Computation, pp.1445-1450, 1999.
[10] M. Dorigo and L.M. Gambardella, ”Ant Colonies for the Traveling Salesman Problem”, BioSystems, vol.43, pp.73-81, 1997.
[11] B. Yang, J. Yu and T. Yan and J. Li, ”An Obstacle Detoured Routing algorithm Based On the Enhanced ACS”, International Conference on Communications Circuits and Systems, vol. 2, pp.1286-1289, 2004.
[12] W. Q. Xiong and P. Wei, “A Kind of Ant Colony Algrithm for Function Optimization”, International Conference on Machine Learning and Cybernetics, pp.552-555, 2002.
[13] M. Dorigo and G. D. Caro, “AntNet: A Mobile Agents Approach to Adaptive Routing”, Technical Report, IRIDIA-Free Brussels University, Belgium, 1997.
[14] M. Dorigo and G. D. Caro, “Ant Colonies for Adaptive Routing in Packet-Switched Communication Networks”, Technical Report, IRIDIA-Free Brussels University, Belgium, 1998.
[15] G. D.Gianni and M. Dorigo, “Mobile Agents for Adaptive Routing”, System Sciences, vol.7, pp.74-83, 1998.
[16] B. Holldobler and E. O. Wilson, The Ants, Berlin: Springer-Verlag,1990.
[17] A. Colorni, M. Dorigo, and V. Maniezzo, “Distributed Optimization by Ant Colonies”, ECAL91-Eur. Conf. Artificial Life, pp.134-142, 1991.
[18] M. Dorigo and L. M. Gambardella., “Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem”, IEEE Transactions on Evolutionary Computation, vol.1, no.1, pp.53-66, 1997.
[19] D. Merkle, M. Middendorf, and H. Schmeck,” Pheromone Evaluation in Ant Colony Optimization”, 26th Annual Conference of the IEEE, Vol.4, pp.22-28, 2000.
[20] P. K. Leslie, L. L. Michael and W. M. Andrew, ”Reinforcement Learning: A Survey,” Journal of Artifical Intelligent Reserch, vol.4 ,pp.237-285, 1996.
[21] L. M. Gambardella and M. Dorigo, “Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem”, the 12th International Conference on Machine Learning, pp.252-260, 1995.
[22] L. M. Gambardella and M. Dorigo, “Solving Symmetric and Asymmetric TSPs by Ant Colonies”, Technical Report, IRIDIA-Free Brussels University, Belgium, 1996.
[23] S. Thomas and H. H. Holger, ”MAX-MIN Ant System”, Future Generation Computer Systems, vol.16, pp.889–914, 2000.
[24] S. T. Andrew, Computer Networks fourth edition, ISBN 957-483-227-9, 2003.
[25] H. Yun and A. N. Zincir-Heywood, ”Intelligent Ants for Adaptive Network Routing”, Second Annual Conference on Communication Networks and Services Research, pp.255-261, 2004.
[26] B. Baran, “Improved AntNet Routing”, Workshop on Data communication in Latin America and the Caribbean, pp.42 -48, 2001.
[27] B. Baran and R. Sosa, “A New Approach for AntNet Routing”, International Conference on Computer Communication and Networks, pp.303-308, 2000.
[28] G. D. Caro and M. Dorigo, “AnNet: Distributed Stigmertic Control for Communications Networks”, Journal of Artificial Intelligence Research, vol.9, pp. 317-365, 1998.
[29] R. Schwnderwoerd, O. Holland and J.Bruten, “Ant-Like Agents for Load Balancing in Telecommunications Networks”, Technical Report, Hewlett-Packard Laboratories, Bristol-England, 1997.
[30] M. Dorigo, E. Bonabeau, and G. Theraulaz, “Ant Algorithms and Stigmergy”, Future Generation Computer Systems, vol.16, pp.851–871, 2000.
[31] G. D. Caro and M. Dorigo, “An Adaptive Multi-Agent Routing Algorithm Inspired by Ants Behavior,” Technical Report, IRIDIA-Free Brussels University, Belgium, 1998.
[32] P. Stone and M. Veloso, “Multi-Agent Systems: A Survey from a Machine Learning Perspective”, Technical Report, Carnegie Mellon University, 1996.
[33] T. Michalareas, L. Sacks, ”Link-State & Ant-Like Algorithm Behaviour for Single-Constrained Routing”, Telecommunication System Research Group, University College London, 2001.
[34] W. Zhong and D. Evans, “When Ants Attack: Security Issues for Stigmergic Systems”, University of Virginia, 2002.
[35] J. R. Hertz, “Routing with Swarm Artificial Intelligence: Improving the AntNet Algorithm”, Rose-Hulman Institute of Technology, 2004.
[36] TSPLIB WebPage, http://www.iwr.uni-heidelberg.de/groups/comopt/sofeware/
TSPLIB95/tsp.
[37] J. E. Bell and P. R. McMullen,” Ant Colony Optimization Techniques for the Vehicle Routing Problem”, Advanced Engineering Informatics, vol.18, pp.41-48, 2004.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top