島嶼式基因演算法之硬體架構及其在向量量化器之應用

SOPC-based Island Genetic Algorithm for Vector Quantizer Design

游宗毅(Tsung-Yi Yu)

指導教授 ： 黃文吉 ； 蔣宗哲

國立臺灣師範大學/理學院/資訊工程研究所/碩士(2010年)

摘要

本研究為島嶼式基因演算法提出一個硬體架構，並應用於向量化器的設計。本文中每個島嶼為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.

並列關鍵字

Island GA ； VLSI ； Vector Quantizers

參考文獻

[1] A. E., Eiben and J. D. Smith, Introduction to Evolutionary Computing, Springer, 2003.

[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

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

[9] N. Nedjah and L. Mourelle, “Hardware Architecture for Genetic Algorithms,”Lecture Notes in Computer Science, vol. 3533, pp. 554-556, 2005.