本論文提出以改良式蟻群演算法為基礎的蟻群硬體加速器，應用於取放作業任務物件取放順序的路徑規劃，並使用ALTERA DE2i-150 FPGA開發平台實現軟硬體共同設計的系統架構。
本論文使用INTEL ATOM處理器與ALTERA FPGA處理器並行的DE2i-150開發平台，透過軟硬體共同設計的方法，將蟻群演算法運算功能作軟體運算以及硬體運算的區分，軟體主要用於處理浮點數的運算，硬體主要用於處理重覆程序的運算，並藉由調整蟻群最佳化演算法的路徑起訖表與費洛蒙更新等方法而提出的改良式蟻群演算法，於FPGA處理器中設計以此為基礎的蟻群硬體加速器，試圖以系統分工的觀念提升蟻群演算法的系統效能以及穩定度。
由實驗結果可知，蟻群硬體加速器確實提升系統的效能以及穩定度，減少蟻群演算法用於路徑規劃的運算時間以及提供穩定的路徑搜尋結果。

In this thesis, an improved ant colony algorithm-based ant colony hardware accelerator is proposed. It is applied to pick and place task for planning the path of picking objects' sequences based on ALTERA DE2i-150 development kit platform to implement the architecture of hardware/software co-design system.
In this thesis, ALTERA DE2i-150 development kit platform has two main processor, INTEL ATOM processor and ALTERA FPGA processor, executing simultaneously. According to the method of hardware/software co-design, the computing functions are divided into software and hardware. Software is used to process float-point computation, and hardware is used to process repeat procedure computation. Due to the method of changing terminal table and pheromone updating, this thesis proposes an improved ant colony algorithm and designs an improved ant colony algorithm-based hardware accelerator into the FPGA processor. This thesis attempts to use the concept of system division to enhance the performance and stability of the system.
According to the results, the ant colony hardware accelerator can enhance the performance and stability of the system indeed. It not only decreases the processing time of the path planning system but also keeps the search results stability.

<目錄>
中文摘要 (I)
英文摘要 (II)
目錄 (III)
圖目錄 (V)
表目錄 (VIII)
第一章　緒論 (1)
1.1　研究背景 (1)
1.2　研究動機 (2)
1.3　文獻探討 (5)
1.3.1　演算法 (5)
1.3.2　萬用啟發式演算法 (7)
1.4　論文架構(9)
第二章　蟻群最佳化演算法 (10)
2.1　蟻群最佳化演算法之原理 (12)
2.2　蟻群最佳化演算法之數學模型 (16)
2.2.1　轉移機率規則公式 (17)
2.2.2　費洛蒙更新公式 (20)
2.3　改良式蟻群演算法之數學模型 (22)
2.4　改良式蟻群演算法之應用 (25)
2.4.1　旅行銷售員問題 (25)
2.4.2　取放作業問題 (28)
第三章　軟硬體共同設計之系統架構介紹 (37)
3.1　軟硬體共同設計介紹 (37)
3.2　DE2i-150開發平台介紹 (39)
3.3　蟻群硬體加速器系統介紹 (43)
3.3.1　系統架構 (44)
3.3.2　蟻群硬體加速器之系統架構 (49)
3.3.3　蟻群硬體加速器之設計流程 (55)
第四章　實驗結果 (57)
4.1　MATLAB模擬 (57)
4.1.1　旅行銷售員問題之路徑規劃模擬 (58)
4.1.2　取放作業之路徑規劃模擬 (62)
4.2　ATOM處理器之實驗結果 (69)
4.3　蟻群硬體加速器之實驗結果 (70)
4.4　效能比較 (73)
第五章　結論與未來展望 (77)
參考文獻 (78)

<圖目錄>
圖1.1　取放作業工作環境示意圖 (4)
圖1.2　最大公因數演算法範例示意圖 (6)
圖1.3　萬用啟發式演算法主要分類示意圖 (8)
圖2.1　螞蟻群體覓食的社會行為示意圖 (環境不受限制) (13)
圖2.2　螞蟻群體覓食的社會行為示意圖 (環境受限制) (13)
圖2.3　人工螞蟻利用轉移機率規則公式挑選下一個節點示意圖 (18)
圖2.4　旅行銷售員問題範例示意圖 (25)
圖2.5　蟻群最佳化演算法應用於旅行銷售員問題流程示意圖 (26)
圖2.6　取放作業開放式路徑示意圖 (28)
圖2.7　取放作業中四種物件的移動路徑示意圖 (31)
圖2.8　取放作業任務的必經路段示意圖 (31)
圖2.9　物件至物件指定分類箱之間的區間路段示意圖 (32)
圖2.10　改良式蟻群演算法應用於取放作業路徑規劃流程示意圖 (36)
圖3.1　微處理器與FPGA的系統平台架構示意圖 (38)
圖3.2　DE2i-150開發平台上視圖 (42)
圖3.3　DE2i-150開發平台系統方塊圖 (42)
圖3.4　DE2i-150開發平台架構示意圖 (43)
圖3.5　軟硬共同設計體整合系統架構示意圖 (45)
圖3.6　蟻群演算法之系統流程圖 (48)
圖3.7　蟻群演算法硬體加速器之系統架構示意圖 (49)
圖3.8　轉移機率暫存模組示意圖 (50)
圖3.9　轉移機率計算模組示意圖 (51)
圖3.10　費洛蒙暫存模組示意圖 (51)
圖3.11　費洛蒙更新模組示意圖 (52)
圖3.12　資料緩衝器模組示意圖 (53)
圖3.13　迭代計算模組示意圖 (53)
圖3.14　隨機數字產生模組示意圖 (54)
圖3.15　路徑選擇模組示意圖 (54)
圖3.16　蟻群演算法硬體加速器之系統架構流程示意圖 (56)
圖4.1　10個城市節點路徑模擬示意圖 (59)
圖4.2　10個城市節點100次測試的路徑長度示意圖 (59)
圖4.3　20個城市節點路徑模擬示意圖 (60)
圖4.4　20個城市節點100次測試的路徑長度示意圖 (60)
圖4.5　31個城市節點路徑模擬示意圖 (61)
圖4.6　31個城市節點20次測試的路徑長度示意圖 (61)
圖4.7　11個物件節點路徑模擬示意圖 (64)
圖4.8　11個物件節點100次測試的路徑長度示意圖 (64)
圖4.9　24個物件節點路徑模擬示意圖 (65)
圖4.10　24個物件節點20次測試的路徑長度示意圖 (65)
圖4.11　24個隨機放置物件節點路徑模擬示意圖一 (66)
圖4.12　24個隨機放置物件節點20次測試的路徑長度示意圖一 (66)
圖4.13　24個隨機放置物件節點路徑模擬示意圖二 (67)
圖4.14　24個隨機放置物件節點20次測試的路徑長度示意圖二 (67)
圖4.15　24個隨機放置物件節點路徑模擬示意圖三 (68)
圖4.16　24個隨機放置物件節點20次測試的路徑長度示意圖三 (68)
圖4.17　ATOM處理器之實驗結果 (69)
圖4.18　蟻群硬體加速器之實驗結果 (71)
圖4.19　蟻群硬體加速器之實驗結果示意圖 (71)
圖4.20　蟻群硬體加速器之實驗結果標示示意圖 (72)

<表目錄>
表2.1　節點間距離表示意圖 (27)
表2.2　旅行銷售員問題的節點間距離表示意圖 (29)
表2.3　取放作業問題的節點間距離表示意圖 (29)
表4.1　蟻群最佳化演算法應用於旅行銷售員問題的建議參數對照表 (58)
表4.2　改良式蟻群演算法應用於取放作業的參數對照表 (63)
表4.3　效能比較之蟻群演算法參數對照表 (73)
表4.4　MATLAB模擬應用於取放作業路徑規劃之效能比較對照表 (74)
表4.5　效能比較之平均執行時間與平均搜尋路徑長度對照表 (75)

[1] R.G. Mishra, "Robotics: Survey of its various possible applications," International Journal of Scientific & Engineering Research, vol. 4, no. 11, pp. 44-52, 2013.
[2] Yiannis N. Moschovakis, "What is an algorithm?" in Mathematics Unlimited, B. Engquist and W. Schmid, pp. 919-936, 2001.
[3] L. Bianchi, M. Dorigo, L. M. Gambardella, W.J. Gutjahr, "A survey on metaheuristics for stochastic combinatorial optimization," Natural Computing, vol. 8, pp. 239-287, 2008.
[4] Meta-heuristics wikipedia, URL:http://en.wikipedia.org/wiki/Metaheuristic
[5] M. Dorigo and C. Blum, “Ant colony optimization: A survey,” Theoretical Computer Science, vol. 344, no. 2-3, pp. 243-278, 2005.
[6] M. Dorigo, V. Maniezzo and A. Colorni, "Positive feedback as a search strategy," Technical Report no.91-016 Revised, Dipartimento di Elettronica, Politecnico di Milano, 1991.
[7] M. Dorigo, “Optimization, learning and natural algorithms,” Ph.D. Thesis, Dip. Elettronica, Politecnico di Milano, Italy, 1992.
[8] M. Dorigo, V. Maniezzo and A. Colorni, “Ant system: Optimization by a colony of cooperating agents,” IEEE Transactions on System, Man, and Cybernetics Part B: Cybernetics, vol. 26, no. 1, pp. 29-41, 1996.
[9] M. Dorigo, M. Birattari and T. Stutzle, “Ant colony optimization: Artificial ants as a computational intelligence technique,” IEEE Computation Intelligence Magazine, vol. 1, no. 4, pp. 28-39, 2006.
[10] T. Stutzle and H.H. Hoos, “MAX-MIN ant system,” Future Generation Computer Systems, vol. 16, no. 8, pp.889-914, 2000.
[11] T. Stutzle, "Parallelization strategies for ant colony optimization," Proceeding of the Fifth International Conference on Parallel Problem Solving from Nature, London UK, pp. 722-731, 1998.
[12] L.M. Gambardella and M. Dorigo, “Solving symmetric and asymmetric TSPs by ant colonies,” Proceeding of the IEEE International Conference on Evolutionary Computation, IEEE Press, New York, pp. 622-627, 1996.
[13] M. Dorigo and L.M. Gambardella, “Ant colony for the travelling salesman problem,” Bio-Systems, vol. 43, no. 1, pp. 73-81, 1997.
[14] M. Dorigo and L.M. Gambardella, “Ant colony system: A cooperative learning approach to the travelling salesman problem,” IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, pp. 53-66, 1997.
[15] Colorni, M. Dorigo and V. Maniezzo, “Distributed optimization by ant colonies,” Proceeding of the First European Conference on Artificial Life, pp. 134-142, 1991.
[16] H. Duan, Y. Yu, J. Zou and X. Feng, “Ant colony optimization-based bio-inspired hardware: Survey and prospect,” Transactions of the Institute of Measurement and Control, vol. 34, no. 2-3, pp. 318-333, 2012.
[17] J. L. Deneubourg, J. M. Pasteels and J. C. Verhaeghe, "Probability behavior in ants: A strategy of error?" Journal of Theoretical Biology, vol. 105, pp. 259-271, 1983.
[18] S.A. Li, M.H. Yang, C.W. Weng, Y.H. Chen, C.H. Lo, C.E. Wu and C.C. Wong, "Ant colony optimization algorithm design and its FPGA implementation," IEEE International Symposium on Intelligent Signal Processing and Communication Systems, pp. 262-265, 2012.
[19] TERASIC Technology co., URL: http://www.terasic.com.tw/tw/
[20] DE2i-150 FPGA Development Kit, URL:http://www.terasic.com.tw/cgi-bin/page/archive.pl?Language=English&CategoryNo=139&No=529
[21] M. Randall and A. Lewis, "A parallel implementation of ant colony optimization," Journal of Parallel and Distributed Computing, vol. 62, no. 9, pp. 1421-1432, 2002.
[22] H. Duan, Y. Yu, J. Zou and X. Feng, "Ant colony optimization-based bio-inspired hardware: Survey and prospect," Transactions of the Institute of Measurement and Control, vol. 34, no. 2-3, pp. 318-333, 2012.
[23] H. Duan, D. Wang and X. Yu, "Survey for hardware realization for ant colony algorithm," Control and Decision, vol. 22, no. 2, pp. 241-246, 2007.
[24] M.H. Tsai, “ACO-based path planning for pick-and-place objects of robot manipulator,” Master’s program in Robotics Engineering, Department of Electrical Engineering, Tamkang University, 2013.