Abstract
Clustering is a hard combinatorial problem which has many applications in science and practice. Genetic algorithms (GAs) have turned out to be very effective in solving the clustering problem. However, GAs have many parameters, the optimal selection of which depends on the problem instance. We introduce a new self-adaptive GA that finds the parameter setup on-line during the execution of the algorithm. In this way, the algorithm is able to find the most suitable combination of the available components. The method is robust and achieves results comparable to or better than a carefully fine-tuned non-adaptive GA.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Delport, V. and M. Koschorreck. (1995). “Genetic Algorithm for Codebook Design in Vector Quantization.” Electronics Letters 31, 84–85.
Dubes, R. and A. Jain. (1987). Algorithms that Cluster Data. New Jersey: Prentice-Hall, Englewood Cliffs.
Equitz, W.H. (1989). “A New Vector Quantization Clustering Algorithm.” IEEE Trans. Acoustics, Speech Signal Processing 37, 1568–1575.
Everitt, B.S. (1992). Cluster Analysis, 3rd edn. London: Edward Arnold/Halsted Press.
Fränti, P. (2000). “Genetic Algorithm with Deterministic Crossover for Vector Quantization.” Pattern Recognition Letters 21, 61–68.
Fränti, P., T. Kaukoranta, and O. Nevalainen. (1997). “On the Splitting Method for VQ Codebook Generation.” Optical Engineering 36, 3043–3051.
Fränti, P. and J. Kivijärvi. (2000). “Randomised Local Search Algorithm for the Clustering Problem.” Pattern Analysis & Applications 3, 358–369.
Fränti, P., J. Kivijärvi, T. Kaukoranta, and O. Nevalainen. (1997). “Genetic Algorithms for Large Scale Clustering Problems.” The Computer Journal 40, 547–554.
Fränti, P., J. Kivijärvi, and O. Nevalainen. (1998). “Tabu Search Algorithm for Codebook Generation in VQ.” Pattern Recognition 31, 1139–1148.
Gersho, A. and R.M. Gray. (1992). Vector Quantization and Signal Compression. Dordrecht: Kluwer Academic Publishers.
Gyllenberg, M., T. Koski, and M. Verlaan. (1997). “Classification of Binary Vectors by Stochastic Complexity.” Journal of Multivariate Analysis 63, 47–72.
Hinterding, R., Z. Michalewicz, and A.E. Eiben. (1997). “Adaptation in Evolutionary Computation: A Survey.” In Proceedings of the 4th IEEE International Conference on Evolutionary Computation, Indianapolis, pp. 65–69.
Kaufman, L. and P.J. Rousseeuw. (1990). Finding Groups in Data: An Introduction to Cluster Analysis. New York: John Wiley & Sons.
Kaukoranta, T., P. Fränti, and O. Nevalainen. (1998). “Iterative Split-and-Merge Algorithm for VQ Codebook Generation.” Optical Engineering 37, 2726–2732.
Kaukoranta, T., P. Fränti, and O. Nevalainen. (2000). “AFast Exact GLABased on Code Vector Activity Detection.” IEEE Transactions on Image Processing 9, 1337–1342.
McQueen, J.B. (1967). “Some Methods of Classification and Analysis of Multivariate Observations.” In Proc. 5th Berkeley Symp. Mathemat. Statist. Probability 1, Univ. of California, Berkeley, USA, pp. 281–296.
Pan, J.S., F.R. McInnes, and M.A. Jack. (1995). “VQ Codebook Design Using Genetic Algorithms.” Electronics Letters 31, 1418–1419.
Ward, J.H. (1963). “Hierarchical Grouping to Optimize an Objective Function.” J. Amer. Statist. Assoc. 58, 236–244.
Zeger, K. and A. Gersho. (1989). “Stochastic Relaxation Algorithm for Improved Vector Quantiser Design.” Electronics Letters 25, 896–898.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Kivijärvi, J., Fränti, P. & Nevalainen, O. Self-Adaptive Genetic Algorithm for Clustering. Journal of Heuristics 9, 113–129 (2003). https://doi.org/10.1023/A:1022521428870
Issue Date:
DOI: https://doi.org/10.1023/A:1022521428870