國立臺灣師範大學博碩士論文全文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	游宗毅 Tsung-Yi Yu
論文名稱：	島嶼式基因演算法之硬體架構及其在向量量化器之應用 SOPC-based Island Genetic Algorithm for Vector Quantizer Design
指導教授：	黃文吉 Hwang, Wen-Jyi 蔣宗哲 Chiang, Tsung-Che
學位類別：	碩士 Master
系所名稱：	資訊工程學系 Department of Computer Science and Information Engineering
論文出版年：	2010
畢業學年度：	98
語文別：	中文
論文頁數：	56
中文關鍵詞：	島嶼式基因法則、系統晶片設計、向量量化器
英文關鍵詞：	Island GA, VLSI, Vector Quantizers
論文種類：	學術論文
相關次數：	點閱：162 下載：6
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

本研究為島嶼式基因演算法提出一個硬體架構，並應用於向量化器的設計。本文中每個島嶼為steady-state基因演算法的演化加速器，透過這樣的方式可以有效改善其硬體資源之消耗。除此之外，本論文提出一個適用於島嶼間快速的移民(migration)硬體架構，讓每個島嶼可以透過該硬體架構平行的執行移民機制，該硬體中使用了一個Migration table，透過查表可以快速的決定移民方式，並有效降低演化運算的時間消耗，達到系統效能提升之目的。
本研究所提出的系統架構，與擁有相同族群總數的steady-state基因演算法系統架構做比較，研究顯示該系統架構擁有較佳的效能與較少的執行時間。此外，本系統架構與於多核心系統下透過多執行緒模擬島嶼式基因演算法的軟體實驗環境做比較，研究顯示該系統架構擁有極佳的執行加速。

A novel VLSI architecture for an island genetic algorithm (GA) is presented in this thesis. The island GA is based on steady-state GA for reducing the hardware resource consumption. A look-up table based fast string migration architecture is proposed for lowering the computational overhead while enhancing the performance for the island GA. As compared with its single-island GA hardware counterpart, the proposed architecture attains superior performance with less computation time subject to the same total population size. In addition, the proposed architecture has significantly lower computational time as compared with its software counter parts running on multicore processors with multithreading.

中文摘要        I
Abstract    II
致謝        III
目錄        IV
附圖目錄        VI
附表目錄        VIII
第一章    緒論    1
1.1    研究背景    1
1.2    研究目的    3
1.3    研究方法    3
1.4    全文架構    6
第二章    基礎理論及技術背景介紹    7
2.1    向量量化器簡介    7
2.2    基因演算法簡介    8
2.2.1    前言    8
2.2.2    基因演算法基本名詞定義    9
2.2.3    基因演算法運算程序    10
2.2.4    基因演算法收斂條件    14
2.2.5    Steady-State基因演算法    14
2.3    島嶼式基因演算法    17
2.4    FPGA系統設計    18
第三章    系統架構    23
3.1    島嶼式基因演算法之系統架構    23
3.2    GA模組之硬體電路架構    24
3.2.1    族群記憶體單元(Population Memory Unit)    26
3.2.2    交配突變單元(Crossover & Mutation Unit)    27
3.2.3    適應值計算單元(Fitness Evaluation Unit)    31
3.2.4    生存測試更新單元(Survival Test & Update Unit)    33
3.3    移民模組之硬體電路架構    34
第四章    實驗數據與效能比較    38
4.1    開發平台與實驗環境介紹    38
4.2    實驗數據的呈現與討論    43
4.2.1    島嶼式基因演算法系統架構之硬體資源消耗    43
4.2.2    島嶼式基因演算法實驗參數探討    44
4.2.3    島嶼式基因演算法系統架構之效能比較    49
第五章    結論    54
參考著作        55
                                

[1] A. E., Eiben and J. D. Smith, Introduction to Evolutionary Computing, Springer, 2003.
[2] A. Chipperfield and P. Fleming, “Parallel Genetic Algorithms,” Parallel and Distributed Computing Handbook (Edit by A. Y. H. Zomaya), pp.1118-1143, McGraw-Hill, New York, 1996.
[3] E. Cantu-Paz, “Efficient and Accurate Parallel Genetic Algorithms,”Norwell: Kluwer, 2000.
[4] A. Gersho and R.M. Gray, Vector Quantization and Signal Compression, Norwood:Kluwer, 1992
[5] S. Hauck and A. Dehon, Reconfigurable Computing, Morgan Kaufmann, 2008.
[6] P.D. Hortensius, R.D. McLeod, and H.C. Card, “Parallel Random Number Generation for VLSI Systems Using Cellular Automata,” IEEE Trans. Computer, pp. 1466-1473, 1989.
[7] W.J. Hwang, H.Y. Li, Y.J. Yeh, and K.F. Chan, “FPGA Implementation of Competitive Learning with Partial Distance Search in the Wavelet Domain,”Progress in Neurocom-puting Research (Edited by G. B. Kang), pp.203-221, NOVA Science Publisher, 2008.
[8] M. Hutton, J. Schleicher, D. Lewis, B. Pedersen, R. Yuan, S. Kaptanoglu, G. Baeckler,B. Ratchev, K. Padalia, M. Bourgeault, A. Lee, H. Kim and R. Saini, “Improving FPGA Performance and Area Using an Adaptive Logic Module”, Lecture Notes in Computer Science, vol. 3203, FPL 2004, pp. 135-144, 2004.
[9] N. Nedjah and L. Mourelle, “Hardware Architecture for Genetic Algorithms,”Lecture Notes in Computer Science, vol. 3533, pp. 554-556, 2005.
[10] K. Rasheed and B.D. Davisson, “Effect of global parallelism on the behave of a steadystate genetic algorithm for design optimization,” In Proceedings of the Congress on Evolutionary Computation, Washington, DC, 1999.
[11] G. Syswerda,“A Study of Reproduction in Generational and Steady State genetic Algorithms,” Foundations of Genetic Algorithms, (Edited by G. Rawlins), pp. 94-101, Morgan Kaufmann, 1991.
[12] M. Tommiska and J. Vuori, “Implementation of genetic algorithms with programmable logic devices,”Proc. 2nd NordicWorkshop on Genetic Algorithms and Their Applications, pp. 111-126, 1996.
[13] D. Whitley and T. Starkweather, “GENITOR II: A distributed genetic algorithm,” J.Expt. Theor. Artif. Intell., vol. 2, pp. 189-214, 1990.
[14] Stratix II Device Handbook, 2008, Altera Corporation. http:// www.altera.com/ literature/ lit-nio2.jsp.
[15] NIOS II Processor Reference Handbook, 2008, Altera Corporation. http: //www.altera.com/ literature/ lit-nio2.jsp.
[16] Scheunders, S., “A genetic c-means clustering algorithm applied to color image quantization,” Pattern Recognition, vol. 30, 6, pp. 859-866, 1997.
[17] Hwang, W. j., and Hong, S. L., “Genetic entropy-constrained vector quantization,”Optical Engineering, vol. 38, pp.233-239, 1999.

簡易檢索 / 詳目顯示

相關論文