本研究針對向量量化器之設計，提出一種新穎的設計演算法，稱為CRA(Codebook Reorganization Algorithm)。向量量化器之設計涉及眾多訓練向量的分群過程，因此本質上是資料分群問題的應用；而求解資料分群問題的演算法複雜度已被證明屬於NP-complete範疇，因此無法用窮舉式搜尋法來求解。實務上皆是利用啟發式演算法來求解。
　　傳統上設計向量量化器最著名的演算法為GLA演算法。此法特色是非常快速，缺點是容易找到品質不佳的局部解。西元1989年學者Zeger提出SRD演算法，改善了GLA演算法的缺點，此法具備全域搜尋的能力，理論上有能力找到全域最佳解，在實務上該方法足以提供近似最佳解的效能。
　　本研究提出的CRA演算法，經由實驗結果顯示其分群效果明顯優於GLA演算法，且其效能優於SRD演算法，能在更短的時間內找到比上述方法更好的解。

　　The research proposed a novel approach named CRA(Codebook reorganization Algorithm), for the vector quantizer design. The vector quantizer design involves a clustering process of many training vectors. It is an application of the data clustering problem in natural. The complexity of algorithms for solving the data clustering problem has been proved to be NP-complete.
　　GLA algorithm is the most famous known algorithm in the field of vector quantizer design. It runs very fast ,but it’s ability to find the global optimum is poor. In most cases, it can only find a poor local optimum. In 1989, Zeger proposed the SRD algorithm to overcome the weakness of the GLA algorithm. Theoretically, it has the ability to find the global optimum. In practice, it can achieve the near optimal performance
　　The performance of CRA algorithm is superior to the above two algorithms demonstrated by the experimental results. It can find better codebooks then GLA. It can find a codebook as good as SRD in less time.

[1] C. Blum,and A. Roli “Metaheuristics in combinatorial optimization: overview and conceptural comparsison” ,ACM Computing Surveys,pp.268-308,vol.35,no.3,Sep. 2003.
[2] I.O. Bohachevsky,M.E. Johnson,and M.L.Stein, “Generalized simulated annealing for function optimization”, Technometrics, pp. 209-217,vol.28,no.3,Aug. 1986.
[3] P.S. Bradley,and U.M. Fayyad,"Refining initial points for k-means clustering”,Proc.of the 5th International Conference on Maching Learning, pp.91-99,1998.
[4] P. Brucker,“On the complexity of clustering problems.” Lectures Notes in
Economics and Mathematical Systems ,pp.45-54,1978.
[5] S.C.Chu,and J. F. Roddick,“Pattern clustering using incremental splitting for
non-uniformly distributed data” Fifth International Conference on Knowledge
Based Intelligent Information Engineering Systems and Allied Technologies,
pp.1037-1041,vol.69,2001.
[6] W.H. Equitz,“A new vector quantization clustering algorithm” IEEE Trans. on
acoustics, speech ,and signal processing. vol.37,no.10,Oct. 1989.
[7] U. Faigle,W. Kern,“Some convergence results for probabilistic tabu search”ORSA Journal on Computing,vol.4,pp.32-37,1992.
[8] P. Franti,J. Kivijarvi,Timo Kaukoranta,and Olli Nevalainen ,”Genetic algorithms for codebook generation in vector quantization”,Report A-1996-5, University of Joensuu, Department of Computer Science,1996.
[9]B.L. Fox,“Integrating and accelerating tabu search,simulated annealing and genetic algorithms”,Annals of Operations Research ,pp. 47-67,1993.
[10]P. Franti , and J. Kivijarvi “Randomised local search algorithm for the clustering problem”,Pattern Analysis and Applications , pp.358-369,vol.3 ,2000.
[11]P. Franti, J. Kivijarvi, and O. Nevalainen “Tabu search algorithm for codebook generation in vector quantization”, Pattern Recognition, pp.1139-1148,vol.31,no.8,1998.
[12]L.P.P.P. Van Ginneken,and R.H.J.M. Otten ,“An inner loop criterion for simulated annealing”,Physics Letters ,pp.429-435,vol.130,no.8-9,Jul. 1988.
[13]F. Glover,“Future path for integer programming and links to artificial intelligence”,Computer and Operation Research,pp.533-549,vol.5,1986.
[14]Alain Hertz,Eric Taillard,and Dominique de Werra,“A tutorial on tabu search”,Proc. of Giomate di Lavoro AIrO’95 (Enterprise Systems: Management of Technological and Organizational Changs),pp.13-24,1995.
[15]F. Herrera ,and J.L. Verdegay,“Genetic algorithms and soft computing”, Physica-Verlag, Heidelberg,pp.8,1996.
[16]J. Holland,“Adaption in natural and artifical systems: an introductory analysis with applications to biology,control,and artifical intelligence”,University of Michigan Press,1975.
[17]S. Kirkpatrick, C.C. Gelatt , Jr. ,and M. P. Vecchi ,”Optimization by simulated annealing”,Science, pp. 671-680,vol. 220, May 1983.
[18]K. Krishna ,and M.N. Murty,“Genetic k-means algorithm”,IEEE Trans. on Systems, Man and Cybernetics, pp.433-439,vol.29,no.3, 1999.
[19]Y. Linde ,A. Buzo ,and R.M. Gray,“An algorithm for vector quantizer design”,IEEE Trans. Comm. ,pp.84-95,vol.28,no.1,1980.
[20]Ngoc-Ai Lu,and Darryl R. Morrell,“VQ codebook design using improved simulated annealing algorithms”, IEEE Trans. on Acoustics, Speech, and Signal Processing, pp.673-676,vol.1,Apr. 1991.
[21]Ujjwal Maulik,and Sanghamitra Bandyopadhyay,“Genetic algorithm-based clustering technique”,Pattern Recognition,pp.1455-1465,vol.33,2000.
[22]JB. McQueen,“Some methods of classifcation and analysis of multivariate observations”,Proc. Symp. Math. and Probability,5th.,Berkeley,pp.281-296,1967.
[23]Surendra Nahar,Sartaj Sahni,and Eugene Shragowitz,“Simulated annealing and combinatorial optimization”,Proc. of 23rd Design Automation Conference,pp293-299,1986
[24]J.M. Pena, J.A. Lozano, and P. Larranaga,“An empirical comparision of four initialization methods for the k-means algorithm”,Pattern Recognition Letters, pp.1027-1040.vol.20,Oct.1999.
[25]Nalini K.Ratha,Anil K. Jain,and Moon J. Chung,“Clustering using a coarse-grained parallel genetic algorithm”,Proc. of the Computer Architectures for Machine Perception, pp. 331-338, Como(Italy),Sep.18-20,1995.
[26]G. Rudolph,”Convergence analysis of canonical genetic algorithms”,IEEE Trans. Neural Networks,vol.5,no.1,pp.96-101,1994.
[27]S.Z. Selim ,and M.A. Ismail,“K-Means-Type algorithm: a generalized convergence theorem and characterization of local optimality”,IEEE trans on Pattern Analysis and Machine Intelligence,vol.6,pp.81-87,1984.
[28]R.E. Smith,B.A.Dike, and S.A.Stegmann,“Fitness inheritance in genetic algorithms”,Proc. of the 1995 ACM Symp. On Applied Computing,pp.345-350.
[29]The USC-SIPI Image Database, http://sipi.usc.edu/services/database/Database.html
[30]Jacques Vaisey,and Allen Gersho,“Simulated annealing and coodbook design”,Proc. IEEE Int. Conf. Acoust. Speech, Signal Processing,pp.1176-1179, April 1998.
[31]K. Zeger,and A. Gersho,“Stochastic relaxation algorithm for improved vector quantization design”,Electron Lett.,pp.896-898,vol.25,no.14,Jul 1989.
[32]K. Zeger,J. Vaisey,and A. Gersho,“Globally optimal vector quantizer design by stochastic relaxation”,IEEE Trans. On Signal Processing,pp.310-322,vol.40,no.2 ,Feb. 1992.
[33]Xiaowei Zheng,Bryant A. Julstrom,and Weidong Cheng “Design of vector quantization codebooks using a genetic algorithm”,Proc. of the IEEE Conference on Evolutionary Computation, pages 525-529,1997.
[34]蔡瑜明,”半導體後段IC封裝最適排程之研究-禁忌搜尋法之應用”,國立中山大學，碩士論文，2003.pp. 533-549,1986.
[35]蘇木春,張孝德,”機器學習：類神經網路、模糊系統以及基因演算法則”,全華科技圖書股份有限公司,台北市,2000.