臺灣博碩士論文加值系統

本文提出一種以改良式基因(memetic algorithm, MA)演算法來設計向量量化器(vector quantizers, VQs)，此演算法是先用穩態型基因演算法(Steady-State genetic Algorithm, SSGA)來做全域搜尋，並再以C-Means演算法做局部改善，相較於其他改良式基因演算法使用世代型基因演算法(generational GA)去做全域搜尋。本文所提出的改良式基因演算法能有效降低向量量化器碼簿訓練時間，除此之外，其結果也最接近全域最佳解，且對初始的碼字選擇較不敏感。模擬結果顯示，本演算法在設計向量量化器上比其他改良式基因演算法在相同的基因族群個數下，擁有穩定效能且更能大幅降低CPU計算時間。

A novel memetic algorithm (MA) for the design of vector quantizers (VQs) is presented in this paper. The algorithm uses steady-state genetic algorithm (SSGA) for the global search and C-Means algorithm for the local improvement. As compared with the usual MA using the generational GA for global search, the proposed MA effectively reduces the computational time for VQ training. In addition, it attains near global optimal solution, and its performance is insensitive to the selection of initial codewords. Numerical results show that the proposed algorithm has significantly lower CPU time over other MA counterparts running on the same genetic population size for VQ design.

中文摘要...................................................i
英文摘要..................................................ii
誌謝.....................................................iii
目錄......................................................iv
表目錄....................................................vi
圖目錄...................................................vii
第一章 緒論...............................................1
1.1 研究背景與研究動機.................................1
1.2 文獻回顧...........................................4
1.3 全文架構...........................................6
第二章 理論基礎...........................................7
2.1 向量量化器的基本原理...............................7
2.2 基因演算法介紹 ..................................10
2.2.1 再生與選擇........................................11
2.2.2 交配與突變........................................13
2.3 C-Means 演算法....................................16
2.4 基本型改良式基因演算法............................21
2.4.1 再生..............................................21
2.4.2 交配..............................................22
2.4.3 突變..............................................22
2.4.4 局部微調..........................................23
第三章 穩態型改良式基因演算法的實現......................26
第四章 實驗結果與效能比較................................31
第五章 結論..............................................37
第六章 未來展望..........................................38
參考文獻..................................................39
簡 歷..................................................41

1.陳培殷，資料壓縮概論，滄海書局，台中，民國九十年
2.陳源聰，一種新穎的向量量化器設計方式碼簿重組演算法，國立成功大學，碩士論文，民國九十三年。
3.蔡汶錫，結合基因與C-Means演算法則之向量量化器設計之研究，國立臺灣師範大學，碩士論文，民國九十七年。
4.J. H. Holland, “Adaptation in Natural and Artificial Systems”, Ann Arbor, Michigan: Cambridge, Massachusetts:MIT Press, 1992.
5.R. L. Haupt, “Optimum population size and mutation rate for a simple real genetic algorithm that optimizes array factors”, IEEE Int. Symposium on Antennas and Propagation Society, vol. 2, pp. 1034-1037, 2000.
6.A. E. Eiben, and J. D. Smith, “Introduction to evolutionary computing”, (Springer-Verlag, Germany), 2003.
7.C. M. Ou, .Vector “Quantization Based on Steady-State Memetic Algorithm”, Journal of Marine Science and Technology, Vol. 18, 4, 553-557, 2010.
8.C. M. Ou, J. J. Chen and W. J. Hwang, “Hybrid Genetic Algorithm for Design of Robust Communication Systems”, Journal of Software, Vol. 1, 3, 24-31, 2006.
9.C. M. Ou, W. J. Hwang, W. W. Hu and T. Y. Lo, “Concurrent Genetic Optimization for Joint Design of Source and Channel Codes”, Neurocomputing, Vol. 70, 1-3, 130-138, 2006.
10.M. Srinivas and L. M. Patnaik, “Genetic algorithm: a survey”, IEEE Computer Society, Vol. 27, 17 -26, 1994.
11.S. Coe, S. Areibi and M.. Moussa, “A hardware memetic accelerator for VLSI circuit partitioning, Computers and Electrical Engineering”, Elsevier, USA, Vol. 33, 233-248, 2007.
12.N. J. Radcliffe and P. D. Surry, “Formal memetic algorithms Lecture Notes in Computer Science”, Springer, Germany, Vol. 865, 1-16, 1994.
13.P. Merz and B. Freisleben, “Genetic algorithms for binary quadratic programming, Proceedings the Genetic and Evolutionary Computation Conference”, Morgan Kauffman, USA, 417-424, 1999.
14.A. Gersho and R. M. Gray, “Vector quantization and signal compression”, (Springer-Verlag, Germany), 1992.
15.T. Kanungo, D.M. Mount, N.S. Netanyahu, C.D. Piatko, R. Silverman and A.Y. Wu, “An efficient k-means clustering algorithm: analysis and implementation”, IEEE Transactions on Pattern Analysis and Machine Intelligence, USA, Vol. 24, 881-892, 2002.
16.P. Scheunders, “A genetic c-means clustering algorithm applied to color image quantization”, Pattern Recognition, Elsevier, USA, Vol. 30, 859-866, 1997.
17.D. E. Goldberg and K. Deb, “A comparative analysis of selection schemes used in genetic algorithms”, G.J.E. rawlins, Morgan Kaufmann, California, Vol. 1, 69-93, 1991.
18.K. Rasheed and B. D. Davisson, “Effect of global parallelism on the behave of a steady state genetic algorithm for design optimization”, Proc. Congress on Evolutionary Computation(CEC’ 99), Vol.1, 6-9, 1999.
19.C. M. Ou and Z. L. Zhang, “A Superior Vector Quantization Based on Steady-State Memetic Algorithm”, International Conference on Intelligent Networks and Intelligent Systems, Tianjin, China, 469-474, 2009.