淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-2108201212165300
中文論文名稱 以SOPC為基礎之蟻群最佳化演算法設計
英文論文名稱 SOPC Based Ant Colony Optimization Algorithm Design
校院名稱 淡江大學
系所名稱(中) 電機工程學系碩士班
系所名稱(英) Department of Electrical Engineering
學年度 100
學期 2
出版年 101
研究生中文姓名 楊閔皓
研究生英文姓名 Min-Hao Yang
學號 699470208
學位類別 碩士
語文別 中文
口試日期 2012-07-09
論文頁數 51頁
口試委員 指導教授-李世安
委員-許陳鑑
委員-陳慶逸
委員-李世安
委員-鄭吉泰
委員-翁慶昌
中文關鍵字 蟻群演算法  路徑規劃  軟硬體共同設計 
英文關鍵字 Ant Colony Algorithm  FPGA  Hardware/Software Codesign  SOPC 
學科別分類 學科別應用科學電機及電子
中文摘要 本論文提出一個以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.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2012-08-27公開。
  • 同意授權瀏覽/列印電子全文服務,於2012-08-27起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信