基因演算法是現代進化計算中的關鍵技術之一，也是近幾年來具有全域最佳化能力的隨機強健搜尋機制。在本論文中，我們將基因演算法應用在迷袋問題(Knapsack Problem)上的解決，透過基因演算法中模擬生物基因演化的人工模型，即染色體經由選擇(Selection)、交配(Crossover)、突變(Mutation)等運算子，最終搜索出本問題之最佳化解答。
本論文同時以軟體及硬體兩方面來設計，軟體部份為Borland C++ Builder和MATLAB程式語言，而硬體部份則是以FPGA(現場可程式規劃閘陣列)來實現，選擇目標元件為Xilinx公司之Virtex晶片，最後並驗證軟硬體兩者之模擬結果。

The Genetic Algorithm (GA) is a key technology based on modern evolutionary computation.In recent years, GA has been successfully applied to many hard optimization problems.GA is a randomly robust engine of Global optimum.
In this thesis, we solve Knapsack Problem using Genetic Algorithm. With this artificial evolution, the solutions are gradually improved generation by generation. In GA, the chromosomes are produced by standard genetic operators：selection, crossover, and mutation. The GA process starts with a random population and iterates until the termination condition is met (the optimal solution is found).
We proposed a software and hardware implementation of the Genetic Algorithm. The software contains Borland C++ Builder and MATLAB language. Hardware design was realized using FPGA. The design was synthesized on Virtex part V800FG680 using Xilinx. Finally, we verify that both results of software and hardware are the same.

[1] 周鵬程編著，遺傳演算法原理與應用－活用Matlab，全華科
技圖書股份有限公司，民國九十年十一月。

[2] E. Karnin.A parallel algorithm for the knapsack problem.
IEEE Transactions on Computers,5(33):404–408,1984.

[3] J. Lee, E. Shragowitz, and S. Sahni. A hypercube
algorithm for the 0/1 knapsack problem. Journal of
Parallel and Distributed Computing,(5):438–456,1988.

[4] Chatchawit and Prabhas,“A Hardware Implementation of the Compact Genetic
Algorithm”,in Proceedings of the 2001 IEEE Congress on Evolutionary
Computation,pp.624-629,Seoul,Korea,May 2001.

[5] 王文俊編著，認識Fuzzy，全華科技圖書股份有限公司，民國八十九年。

[6] 蘇木春、張孝德編著。機器學習：類神經網路，模糊系統以及基因演算法則，
全華科技圖書股份有限公司，民國九十年。

[7] 吳建生，「以基因法則設計通道匹配向量量化之研究」，
國立交通大學電信工程研究所碩士論文，民國八十七年六月。

[8] 黃俊銘編譯，G.Lindfield & J.Penny原著，數值方法－使用
MATLAB程式語言，全華科技圖書股份有限公司，民國九十年。

[9] Michael Negnevitsky,“Artifical Intelligence”：a guide
to intelligent systems,2001.

[10] Lance D.Chambers,“The Practial Handbook of Genetic
Algorithms,Applications”,CRC Press,Second Ediction, 2001.

[11] 王有傳，「以模糊理論及類神經網路為基礎利用遺傳演算法的語者辨認」，
私立淡江大學電機工程研究所碩士論文，民國八十五年六月。

[12] 鄭信源編著，Verilog硬體描述語言數位電路設計實務，
儒林圖書有限公司，民國八十九年一月。

[13] 鄭群星編著，Xilinx FPGA數位電路設計入門，東華書局，民國九十一年十月。

[14] Ken Coffman,“Real World FPGA Design with Verilog”, Prentice Hall,2001.

[15] 唐佩忠編著，VHDL與數位邏輯設計，高立圖書有限公司，民國八十八年。

[16] Charles H. Roth.,“Digital system design using VHDL”, PWS publishing
company,1998.

[17] 胡振華編著，VHDL與FPGA設計，全華科技圖書股份有限公司，民國九十年。

[18] 董蘭榮編著，Xilinx FPGA電路設計與實習，滄海書局，民國九十年。