臺灣博碩士論文加值系統

本論文提出一個以SOPC(System On a Programmable Chip)技術為核心之軟硬體共同設計將蟻群演算法實現於FPGA晶片上。本論文使用SOPC技術進行蟻群演算法之軟硬體電路設計，其設計方法主要分成兩個部分：(1) 選擇路徑，(2) 路徑分析。其中(1)選擇路徑屬於蟻群演算法的前置處理，需要耗費較久的運算處理時間，因此將在FPGA晶片內以設計成硬體電路，以加快處理速度。而(2)路經分析則會在NIOS II 處理器內以C語言的軟體方式實現。在本論文的實驗結果中得到可以用較少的處理時間獲得最佳的路徑資訊。

In this thesis, proposed ant colony algorithm based on a SOPC (System on a Programmable Chip) technique on the FPGA chip. In the design and implementation of ant colony algorithm based on a SOPC (System on a Programmable Chip) technique is applied to design two processing method: (1) Selecting path, (2) Path analysis. Selecting path belongs to the pre-processing of the ant colony algorithm takes a longer computing processing time, so design into a hardware circuit, in order to speed up processing. (2) path analysis will be to the C language software in the NIOS II processor. Experimental results found in this paper to the processing time can be less accurate path information.

目錄
圖目錄 IV
表目錄 VI
第一章 序論 1
1.1研究背景與動機 1
1.2 論文架構 3
第二章 軟硬體設計平台 4
2.1 DE2-70 多媒體開發板 4
2.2 DE2-70 軟硬體共同設計 7
第三章 蟻群演算法 10
3.1蟻群演算法由來 10
3.2蟻群演算法原理 13
第四章 旅行者問題 17
4.1旅行者問題由來 17
4.2基因演算法應用於旅行者問題 18
4.3蟻群演算法應用於旅行者問題 24
第五章 系統流程與硬體電路設計 27
5.1 軟硬體共同設計之蟻群演算法流程 27
5.2 路徑選擇處理 28
5.2.1 費洛蒙矩陣 28
5.2.2 轉移機率規則 31
5.2.3 路徑選擇 34
5.2.4 路徑比對 38
5.3 蟻群演算法硬體電路設計 40
5.3.1 費洛蒙矩陣之硬體電路 40
5.3.2 轉移機率規則之硬體電路 41
5.3.3 路徑選擇之硬體電路 42
5.3.4 路徑比對之硬體電路 43
第六章 實驗結果與分析 45
6.1 蟻群演算法之實驗結果 45
6.1.1 轉移機率規則 45
6.1.2 路徑選擇 46
6.2 處理效能比較 47
第七章 結論與未來展望 49
參考文獻 50

圖目錄
圖2.1 DE2-70開發板實體圖[2] 6
圖2.2 DE2-70開發板搭配DVD多媒體平台[2] 6
圖2.3 DE2-70開發板搭配數位相機與LTM顯示模組平台[2] 7
圖2.4 傳統的軟硬體共同設計流程[3] 8
圖2.5 SOPC系統的軟硬體共同設計架構[3] 9
圖3.1 自然界螞蟻覓食行為 10
圖3.2 螞蟻覓食行為 12
圖4.1 漢米爾頓迴圈 18
圖4.2 基因演算法基本流程 19
圖4.3 解集合A、B 21
圖4 4部分匹配法(a) 21
圖4.5部分匹配法(b) 22
圖4.6匹配交換法 23
圖4 7鄰近城市交換圖 23
圖4.8隨機城市交換圖 24
圖4.9 蟻群演算法基本流程圖 25
圖5.1 蟻群演算法軟硬體共同設計流程圖 28
圖5.2 蟻群演算法費洛蒙矩陣電路 29
圖5.3 蟻群演算法費洛蒙矩陣電路流程圖 31
圖5.4 蟻群演算法轉移機率規則電路 32
圖5.5 轉移機率規則電路流程圖 33
圖5.6 蟻群演算法路徑選擇電路 34
圖5.7 蟻群演算法路徑選擇流程圖 35
圖5.8 蟻群演算法路徑選取示意圖 37
圖5.9 蟻群演算法路徑選取流程圖 37
圖5.10 蟻群演算法路徑比對電路 38
圖5.11 蟻群演算法路徑比對流程圖 39
圖5.12 費洛蒙更新之硬體電路圖 41
圖5.13 轉移機率規則之硬體電路圖 42
圖5.14 路徑選擇之硬體電路圖 43
圖5.15 路徑比對之硬體電路圖 44
圖6.1 轉移機率規則之波形圖 45
圖6.2 路徑選擇之波形圖 46

表目錄
表4.1 解集合A、B 21
表5.1費洛蒙矩陣電路訊號功能 29
表5.2轉移機率規則電路訊號功能 32
表5.3路徑選擇電路訊號功能 34
表5.4路徑比對電路訊號功能 38
表6.1 蟻群演算法時間比較表 47

[1]Altera多媒體發展平台DE2-70網址，
URL: http://university.altera.com/materials/boards/
[2]友晶科技網址，URL: http://www.terasic.com.tw/
[3]URL:http://ee.sjtu.edu.cn:8080/wangzhan/PLDlecture%20note/ch6/ch6_2_Altera_SoPC_NiosII.ppt
[4]Dorigo M., and L.M. Gambardella, “Ant colonies for the traveling salesman problem,” BioSystems, 43,1997, pp.73-81.
[5]Dorigo M., V. Maniezzo, and A. Colorni, “The ant system: An autocatalytic optimizing process,” Technical Report no.91-016 Revised, Politecnico di Milano, Italy,1991.
[6]Dorigo M., V. Maniezzo, and A. Colorni, “Ant system: Optimization by a colony of cooperating agents,” IEEE Transactions on Systems, Man, and Cybernetics-Part B, vol.26, no. 1, pp.29-41, 1996.
[7]Dorigo M., V. Maniezzo, and A. Colorni, “Positive feedback as a searchstrategy,” Technical Report no.1-016 Revised, Dip. Elettronica, Politecnico di Milano,1991.
[8]Dorigo M., and L.M. Gambardella, “Ant colony system: A cooperative learning approach to the traveling salesman problem,” IEEE Transitions on Evolutionary Computation, vol. 1, no. 1, 1997, pp.53-66.
[9]L.M. Gambardella, E. Taillard, and Dorigo M., “Ant colonies for quadratic assignment problem, ” Journal of the Operational Research Society, vol.50, no.2, pp.167-176, 1999.
[10]劉開國，利用位能場規劃以機械手臂傳遞之路徑，國立交通大學資訊科學與工程研究所(指導教授：莊仁輝)，2006。
[11]侯惠傑，機器人之避障路徑規劃與FPGA實現，淡江大學電機工程學系碩士論文(指導教授：翁慶昌)，2001。
[12]李捷隆，分散式基因演算法應用於旅行家銷售員問題，中原大學資訊工程研究所碩士論文(指導教授：阮議聰)，2004。
[13]Altera Corporation, SOPC Builder User Guide, 2003.
[14]Altera Corporation, Designing With Nios & SOPC Builder, 2003。
[15]Shih-An Li, Chen-Chien Hsu, Ching-Chang Wong, and Chia-Jun Yu, “Hardware/Software Co-design for Particle Swarm Optimization Algorithm,” submitted to Information Sciences, Aug. 15, 2009. (SCI)
[16]李世安,翁仲緯,賴鈺婷,翁慶昌,”影像硬體加速器之設計,” Proceedings of 2009 National Symposium on System Science and Engineering, 2009.