(3.236.118.225) 您好！臺灣時間：2021/05/16 15:06

### 詳目顯示:::

:

• 被引用: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 Introduction1.1 Overview of the Ant Colonies...............................11.2 Ants’ Foraging Behavior...................................21.3 A Brief of Ant Algorithms..................................81.4 A Brief of AntNet..........................................91.5 Thesis Overview...........................................10Chapter 2 Methodologies of Ant System Algorithm and Ant Colony System Algorithm 2.1 Methodology of Ant System Algorithm.......................112.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..............................................................22Chapter 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....................................32Chapter 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.....................................404.3 Comparison of AS and ACS.....................................414.4 Simulation of Antnet Algorithm...............................424.4.1 Parameter settings.........................................424.4.2 Simulation result..........................................43Chapter 5 Conclusions and Future Studies5.1 Conclusions..................................................455.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.
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 應用蟻群最佳化演算法於含時窗限制之旅行推銷員問題 2 全黑啟動最佳加壓路徑之規劃 3 建築動線最短路徑模擬之研究 4 整合即時路況之導航系統研究 5 整體最佳化演算法應用於最長不相交路徑之研究 6 啟發式演算法於最佳化與分群問題之研究

 1 15. 張心馨、陳忠仁、王仁君（2002），「以NTT DoCoMo競合關係和價值網的經驗為例－芻議發展行動商務的經營契機和策略模式」，經濟情勢暨評論，135-168頁，2002年9月。

 1 類神經網路應用於產品可靠度預測 2 適應性智慧型解耦合模糊滑動控制系統設計 3 路口延滯下路徑演算法之研究 4 以小腦模型為基底之智慧型控制系統設計與實現 5 智慧型自組織小腦模型控制器應用於汽車控制設計 6 小腦模型控制器於機械臂之控制 7 PC-Based控制器於智慧型溫度控制之研究 8 以小腦模型為基底之強健控制器用於不確定非線性系統 9 遞迴式小波類神經網路之適應性控制器設計用於船舶及無人飛機運動控制系統 10 對於螞蟻族群最佳化演算法的一些論點 11 具非線性不確定系統之適應性強健型小腦模型控制器設計 12 以小腦模型為基底之適應性控制器設計及其應用 13 智慧型強健小波類神經網路控制器設計用於多輸入多輸出非線性系統 14 適應性小波類神經網路控制運用於直流轉直流電源轉換器 15 數位學習中學習路徑之研究-螞蟻演算法之應用

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室