臺灣博碩士論文加值系統

本篇論文主要目標為實現基因演算法之硬體架構，並將其與類神經網路前饋計算之硬體架構做結合，用於找尋類神經網路中權重值的最佳解。有別於傳統的單點搜尋演算法，基因演算法採用多點(族群)的方式來找尋最佳解，由於不需要繁複的計算，而且可用二進位來做運算，更有利於在FPGA上之實現。本論文之基因演算法硬體架構使用交配突變單元(CMU)與搜尋單元(SU)兩個模組來加快搜尋速度。在交配突變單元中，同時產生交配遮罩(crossover mask)與突變遮罩(mutation mask)來加快硬體執行速度，此硬體共提供單點(one-point)、雙點(two-point)以及均勻(uniform)等三種交配方式，使用者可自行選擇，並依照需求來改變交配率(crossover rate)與突變率(mutation rate)。而搜尋單元則用來找尋上一世代中最好的個體，並將其存入新的族群當中，以避免在複製、交配與突變後產生較差的後代。此外類神經網路之前饋計算採單層多工(layer multiplexing)方式，藉由重複使用單一神經層來達到多層的運算，可有效減少硬體資源的使用。最後將整個硬體架構以Altera DE2-70 FPGA來實現，應用於二維最佳值搜尋、M-G曲線預測以及影像邊緣偵測，並獲得成功的實驗結果。

This thesis is aimed to implement the hardware structure of the genetic algorithm (GA), which is applied to search the optimal weights for the FPGA-based artificial neural network (ANN). In contrast with the traditional gradient algorithm, GA uses multi-point population to search the optimum, which is suitable to implement on FPGA in binary code without complex computation. There are two modules proposed for GA hardware to speed up searching, CMU and SU. The CMU generates one crossover mask and two mutation masks at the same time, not in order, to reduce a lot of execution clock cycles. The SU finds the best individual in each generation and saves it as the next generation parent to always keep the elite in the population. The hardware includes three crossover operations, one-point crossover, two-point crossover and uniform crossover. The users can choose one of them and define the crossover rate and mutation rate to deal with different problems. As for the forward calculation of ANN, the multilayer architecture is realized by the layer multiplexing method to reduce the resource since it only requires a single layer to be used repeatedly. The success of the GA hardware architecture is demonstrated by three experiments on Altera DE2-70 FPGA board with 50 MHz operation frequency, including two-dimensional optimal searching, M-G curve prediction fitting and edge detection.

Chapter 1 Introduction 1
Chapter 2 Intelligent Learning Algorithm 3
2.1 Introduction to Genetic Algorithm 3
2.1.1 Operations of the Genetic Algorithm 7
2.1.2 Parameters of GA 10
2.2 Introduction to ANN 12
Chapter 3 Hardware Implementation 16
3.1 Hardware Implementation of GA 16
3.2 Speed-up of GA Implementation 28
3.3 GA Controller Unit (GACU) 31
3.4 Hardware Implementation of ANN 33
3.4.1 Neuron Implementation 36
3.4.2 ANNU Implementation 38
3.4.3 MC Implementation 42
Chapter 4 Experiments 46
4.1 Experiment-I: Two-dimensional Optimal Searching 46
4.2 Experiment-II: Prediction Problem 49
4.3 Experiment-III: Image Edge Detection Problem 53
Chapter 5 Conclusions 59
References 61

[1] L. A. Zadeh, “Knowledge representation in fuzzy logic, “IEEE Trans. on Knowledge Data Engineering,” vol. 1, pp. 89-100, 1989.
[2] S. Haykin, Neural Networks. A Comprehensive Foundation, NY: Macmillan College Publishing, 1994.
[3] C. G. Looney, Pattern Recognition using Neural Networks: Theory and Algorithms for Engineers and Scientists, NY, USA: Oxford University Press, Inc, 1997.
[4] D. E. Goldberg, Genetic Algorithms in Search Optimization and Machine Learning, Addison-Wesley, 1989.
[5] K. F. Man, K. S. Tang and S. Kwong, “Genetic algorithms: concepts and applications [in engineering design],” IEEE Trans. on Industrial Electronics, vol. 43, pp. 519-534, 1996.
[6] M. Mitchell, An Introduction to Genetic Algorithms, Cambridge, MA, USA: MIT Press, 1996.
[7] “www.terasic.com.”
[8] S. D. Scott, A. Samal and S. Seth, “HGA: A hardware-Based Genetic Algorithm,” ACM/SIMDA 3rd Int. Symposium on FPGA, pp. 53-59, 1995.
[9] N. Yoshida and T. Yasuoka, “Multi-GAP: Parallel and distributed genetic algorithms in VLSI,” IEEE Int. Conf. Syst., Man, and Cyber., vol. 5, pp. 571-576, 1999.
[10] C. T. Lin and C. S. G. Lee, Neural fuzzy systems, Prentice Hill Inc, 1996.
[11] 王進德，「類神經網路與模糊控制理論-入門與應用」，全華圖書股份有限公司，2008。
[12] 林俊良，「智慧型控制-分析與設計」，全華科技圖書股份有限公司，2005。
[13] "http://www.iitk.ac.in/karmaa/DownloadTools/MCIT_DataCompressionProject/User_Manual_Image_Compression.html"
[14] P. Y. Chen, R. D. Chen, Y. P. Chang, L. S. Shieh and H. A. Malki, “Hardware implementation for a Genetic algorithm,” IEEE Trans on Instrumentation and Measurement, vol. 57, pp. 699-705, 2008.
[15] M. Serra, T. Slater, J. C. Muzio and D. M. Miller, “The Analysis of One-Dimensional Linear Cellular Automata and Their Aliasing Properties,” IEEE Trans. on Computer-Aided Design, vol. 9, pp. 767-778, 1990.
[16] P. D. Hortensius, R. D. McLeod and H.C. Card, “Parallel Random Number Generation for VLSI Systems Using Cellular Automata,” IEEE Trans. on Computers, vol. 9, pp. 1466-1473, 1989.
[17] 劉澤翰，「以FPGA為核心之倒傳遞類神經網路硬體實現」，國立交通大學電機學院電控工程研究所碩士論文，民國100年。
[18] Y. Maeda, and M. Wakamura, “Simultaneous perturbation learning rule for recurrent neural networks and its FPGA implementation,” IEEE Trans. on Neural Networks, vol. 16, pp. 1664-1672, 2005.
[19] T. Szabo, L. Antoni, G. Horvath, and B. Fether, “A full-parallel digitial implementation for pre-trained NNs,” Proc. Of the IEEE-INNS-ENNS Int. Joint Conf. on Neural Networks, vol. 2, pp. 49-54, 2000.
[20] S. Himavathi, D. Anitha, and A. Muthuramalingam, “Feedforward neural network implementation in FPGA using layer multiplexing for effective resource utilization,” IEEE Trans. on Neural Networks, vol. 18, no. 3, pp. 880-888, 2007.
[21] M. Mackey and L. Glass, “Oscillation and chaos in physiological control systems,” Science, vol. 197, pp. 287-289, 1977.
[22] J. Wu, X. Zhang, F. Zhang etc, “The experiment research of edge detection in digital image”. Microcomputer Information (CONTROL & AUTOMATION), vol. 20, pp. 106-107, 2004.
[23] L. G. Roberts, “Machine Perception of Three-Dimension Solids”, Optical and Electro-Optimal Information Processing, England : Cambridge, pp. 99-19, 1965.
[24] L. Sobel, Camera Models and Machine Perception, CA: Stanford University, pp. 121, 1970.
[25] J. Canny, “A Computational Approach to Edge Detection”, IEEE Trans. Pattern Analysis and Machine Intelligence, vol. PAMI-8, pp.679-699, 1986.
[26] J. Prewitt. “Enhancement and Extraction”, Picture Process, NY: Academic Press, pp.75-1970, 1970.
[27] R. C. Gonzalez, and R. E. Woods, Digital Image Processing, Prentice-Hall Inc, 2003.