Abstract
The K-means algorithm is one of the most popular techniques in clustering. Nevertheless, the performance of the K-means algorithm depends highly on initial cluster centers and converges to local minima. This paper proposes a hybrid evolutionary programming based clustering algorithm, called PSO-SA, by combining particle swarm optimization (PSO) and simulated annealing (SA). The basic idea is to search around the global solution by SA and to increase the information exchange among particles using a mutation operator to escape local optima. Three datasets, Iris, Wisconsin Breast Cancer, and Ripley’s Glass, have been considered to show the effectiveness of the proposed clustering algorithm in providing optimal clusters. The simulation results show that the PSO-SA clustering algorithm not only has a better response but also converges more quickly than the K-means, PSO, and SA algorithms.
Similar content being viewed by others
References
Anderson, E., 1935. The irises of the Gaspé peninsula. Bull. Am. Iris Soc., 59:2–5.
Angeline, P.J., 1998. Using Selection to Improve Particle Swarm Optimization. IEEE Int. Conf. on Computational Intelligence, p.84–89.
Cai, X., Cui, Z., Zeng, J., Tan, Y., 2007. Performance dependent adaptive particle swarm optimization. Int. J. Innov. Comput. Inf. Control, 3(6):1697–1706
Chang, J.F., Chu, S.C., Roddick, J.F., Pan, S.J., 2005. A parallel particle swarm optimization algorithm with communication strategies. J. Inf. Sci. Eng., 21(4):809–818.
Christober Asir Rajan, C., Mohan, M.R., 2007. An evolutionary programming based simulated annealing method for solving the unit commitment problem. Int. J. Electr. Power Energy Syst., 29(7):540–550. [doi:10.1016/j.ijepes.2006.12.001]
Chu, S.C., Tsai, P., Pan, J.S., 2006. Parallel Particle Swarm Optimization Algorithms with Adaptive Simulated Annealing. Studies in Computational Intelligence Book Series. Springer Berlin Heidelberg, 31:261–279.
Eberhart, R., Shi, Y., 2001. Particle Swarm Optimization: Development, Application and Resources. IEEE Congress on Evolutionary Computation, 1:81–86.
Esmin, A.A..A., Lambert-Torres, G., Zambroni de Souza, A.C., 2005. A hybrid particle swarm optimization applied to loss power minimization. IEEE Trans. Power Syst., 20(2):859–866. [doi:10.1109/TPWRS.2005.846049]
Fathian, M., Amiri, B., Maroosi, A., 2007. Application of honey-bee mating optimization algorithm on clustering. Appl. Math. Comput., 190(2):1502–1513. [doi:10.1016/j.amc.2007.02.029]
Fisher, R.A., 1936. The use of multiple measurements in taxonomic problems. Ann. Eug., 7:179–188.
Gaing, Z.L., 2003. Particle swarm optimization to solving the economic dispatch considering the generator constraints. IEEE Trans. Power Syst., 18(3):1187–1195. [doi:10.1109/PWRS.2003.814889]
Gaing, Z.L., 2004. A particle swarm optimization approach for optimum design of PID controller in AVR system. IEEE Trans. Power Syst., 19(2):384–391.
Hu, X., Shi, Y., Eberhart, R., 2004. Recent Advances in Particle Swarm. IEEE Congress on Evolutionary Computation, 1:90–97.
Kao, Y.T., Zahara, E., Kao, I.W., 2008. A hybridized approach to data clustering. Exp. Syst. Appl., 34(3):1754–1762. [doi:10.1016/j.eswa.2007.01.028]
Kennedy, J., Eberhart, R., 1995. Particle Swarm Optimization. IEEE Int. Conf. on Neural Networks, 4:1942–1948.
Laszlo, M., Mukherjee, S., 2007. A genetic algorithm that exchanges neighboring centers for k-means clustering. Pattern Recog. Lett., 28(16):2359–2366. [doi:10.1016/j.patrec.2007.08.006]
MacQueen, J.B., 1967. Some Methods for Classification and Analysis of Multivariate Observations. Proc. 5th Berkeley Symp. on Mathematical Statistics and Probability, 1:281–297.
Meer, K., 2007. Simulated annealing versus metropolis for a TSP instance. Inf. Processing Lett., 104(6):216–219. [doi:10.1016/j.ipl.2007.06.016]
Mingoti, S.A., Lima, J.O., 2006. Comparing SOM neural network with fuzzy c-means, k-means and traditional hierarchical clustering algorithms. Eur. J. Oper. Res., 174(3):1742–1759. [doi:10.1016/j.ejor.2005.03.039]
Miranda, V., Fonseca, N., 2002. EPSO-Evolutionary Particle Swarm Optimization, a New Algorithm with Applications in Power Systems. IEEE/PES Transmission and Distribution Conf. and Exhibition: Asia Pacific, 2:745–750. [doi:10.1109/TDC.2002.1177567]
Naka, S., Genji, T., Yura, T., Fukuyama, Y., 2003. A hybrid particle swarm optimization for distribution state estimation. IEEE Trans. Power Syst., 18(1):60–68. [doi:10.1109/TPWRS.2002.807051]
Ng, M.K., Wang, J.C., 2002. Clustering categorical data sets using tabu search techniques. Pattern Recog., 35(12): 2783–2790. [doi:10.1016/S0031-3203(02)00021-3]
Niknam, T., 2006. An Approach Based on Particle Swarm Optimization for Optimal Operation of Distribution Network Considering Distributed Generators. IEEE 32nd Annual Conf. on Industrial Electronics, p.633–637. [doi:10.1109/IECON.2006.347222]
Niknam, T., Bahmani Firouzi, B., Nayeripour, M., 2008a. An efficient hybrid evolutionary algorithm for cluster analysis. World Appl. Sci. J., 4(2):300–307.
Niknam, T., Olamaie, J., Amiri, B., 2008b. A hybrid evolutionary algorithm based on ACO and SA for cluster analysis. J. Appl. Sci., 8(15):2695–2702. [doi:10.3923/jas.2008.2695.2702]
Olamaei, J., Niknam, T., Gharehpetian, G., 2008. Application of particle swarm optimization for distribution feeder reconfiguration considering distributed generators. Appl. Math. Comput., 201(1-2):575–586. [doi:10.1016/j.amc.2007.12.053]
Saber, A.Y., Senjyu, T., Yona, A., Urasaki, N., Funabashi, T., 2007. Fuzzy unit commitment solution-a novel twofold simulated annealing approach. Electr. Power Syst. Res., 77(12):1699–1712. [doi:10.1016/j.epsr.2006.12.002]
Shi, Y., Eberhart, R., 1998. A Modified Particle Swarm Optimizer. Proc. IEEE World Congress on Computational Intelligence, p.69–73. [doi:10.1109/ICEC.1998.699146]
Sung, C.S., Jin, H.W., 2000. A tabu-search-based heuristic for clustering. Pattern Recog., 33(5):849–858. [doi:10.1016/S0031-3203(99)00090-4]
Tsai, C.F., Tsai, C.W., Wu, H.C., Yang, T., 2004. ACODF: a novel data clustering approach for data mining in large databases. J. Syst. Software, 73(1):133–145. [doi:10.1016/S0164-1212(03)00216-4]
Wu, T.H., Chang, C.C., Chung, S.H., 2008. A simulated annealing algorithm for manufacturing cell formation problems. Exp. Syst. Appl., 34(3):1609–1617. [doi:10.1016/j.eswa.2007.01.012]
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Niknam, T., Amiri, B., Olamaei, J. et al. An efficient hybrid evolutionary optimization algorithm based on PSO and SA for clustering. J. Zhejiang Univ. Sci. A 10, 512–519 (2009). https://doi.org/10.1631/jzus.A0820196
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1631/jzus.A0820196
Key words
- Simulated annealing (SA)
- Data clustering
- Hybrid evolutionary optimization algorithm
- K-means clustering
- Particle swarm optimization (PSO)