以SOPC為基礎之蟻群最佳化演算法設計

SOPC Based Ant Colony Optimization Algorithm Design

楊閔皓(Min-Hao Yang)

指導教授 ： 李世安

淡江大學/工學院/電機工程學系碩士班/碩士(2012年)

https://doi.org/10.6846/TKU.2012.00901

摘要

本論文提出一個以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.

並列關鍵字

Ant Colony Algorithm ； FPGA ； Hardware/Software Codesign ； SOPC

參考文獻

[12] 李捷隆，分散式基因演算法應用於旅行家銷售員問題，中原大學資訊工程研究所碩士論文(指導教授：阮議聰)，2004。

[4] Dorigo M., and L.M. Gambardella, “Ant colonies for the traveling salesman problem,” BioSystems, 43,1997, pp.73-81.

[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.

[1] Altera多媒體發展平台DE2-70網址，

URL: http://university.altera.com/materials/boards/