Skip to main content
Log in

An efficient hybrid evolutionary optimization algorithm based on PSO and SA for clustering

  • Published:
Journal of Zhejiang University-SCIENCE A Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Anderson, E., 1935. The irises of the Gaspé peninsula. Bull. Am. Iris Soc., 59:2–5.

    Google Scholar 

  • 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

    Google Scholar 

  • 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.

    Google Scholar 

  • 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]

    Article  Google Scholar 

  • 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.

    Google Scholar 

  • Eberhart, R., Shi, Y., 2001. Particle Swarm Optimization: Development, Application and Resources. IEEE Congress on Evolutionary Computation, 1:81–86.

    Google Scholar 

  • 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]

    Article  Google Scholar 

  • 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]

    MathSciNet  MATH  Google Scholar 

  • Fisher, R.A., 1936. The use of multiple measurements in taxonomic problems. Ann. Eug., 7:179–188.

    Article  Google Scholar 

  • 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]

    Article  Google Scholar 

  • 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.

    Google Scholar 

  • Hu, X., Shi, Y., Eberhart, R., 2004. Recent Advances in Particle Swarm. IEEE Congress on Evolutionary Computation, 1:90–97.

    Google Scholar 

  • 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]

    Article  Google Scholar 

  • Kennedy, J., Eberhart, R., 1995. Particle Swarm Optimization. IEEE Int. Conf. on Neural Networks, 4:1942–1948.

    Google Scholar 

  • 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]

    Article  Google Scholar 

  • 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.

    MathSciNet  MATH  Google Scholar 

  • 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]

    Article  MathSciNet  MATH  Google Scholar 

  • 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]

    Article  MATH  Google Scholar 

  • 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]

    Article  Google Scholar 

  • 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]

    Article  Google Scholar 

  • 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]

    Article  MATH  Google Scholar 

  • 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.

    Google Scholar 

  • 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]

    Article  Google Scholar 

  • 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]

    MathSciNet  MATH  Google Scholar 

  • 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]

    Article  Google Scholar 

  • 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]

    Article  Google Scholar 

  • 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]

    Article  Google Scholar 

  • 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]

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Taher Niknam.

Rights and permissions

Reprints 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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1631/jzus.A0820196

Key words

CLC number

Navigation