結合基因與C-Means演算法則之向量量化器設計之研究

蔡汶錫

指導教授 ： 黃文吉

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

摘要

本論文提出一個memetic algorithm (MA) 的演算法則來設計向量量化器。此演算法則使用steady-state genetic algorithm (GA) 做全域的搜尋，並採用C-Means演算法則進行局部的改善。與一般利用generational GA 做全域搜尋的MA比較之，本論文所提出的 MA 有效降低了vector quantization (VQ)訓練時的計算時間。除此之外，此演算法的結果接近全域最佳解，且對於初始的碼字選擇並不敏銳。最後的統計數據顯示，本論文所提出的steady-state MA與利用generational GA演算法執行全域搜尋的MA於相同基因族群個數的情況下，steady-state MA明顯的降低了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 (GA) 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 reduce 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.

並列關鍵字

Memetic algorithm ； Vector quantizers ； Steady-state genetic algorithm ； C-Means algorithm

參考文獻

[2] Coe, S., Areibi, S., Moussa, M., A hardware Memetic accelerator for VLSI circuit partitioning, Computers and Electrical Engineering, Vol. 33, 99.233-248, 2007.

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

[4] Gersho, A., and Gray, R.M., Vector Quantization and Signal Compression, Kluwer, Norwood, Massachusetts, 1992.

[5] Goldberg, D.E., and Deb, K., “A comparative analysis of selection schemes used in genetic algorithms,” In G.J.E. rawlins, editor, Fundations of Genetic Algorithm, pp.69-93, Morgan Kaufman, 1991.

[7] Radcliffe, N. J., and Surry, P.D., “Formal memetic algorithms,” Lecture Notes in Computer Science, Vol. 865, pp.1-16, 1994.