Application of metaheuristics to k-means clustering
A.V. Lisin, R.T. Faizullin


Omsk State Technical University, Omsk, Russia

Full text of article: Russian language.


We introduce an approach to image segmentation with a k-means algorithm by reducing the clustering problem to a continuous optimization problem, which is solved by metaheuristics algorithms using a gravitational search algorithm as an example. The approach is substantiated and numerical experiment results are discussed.

clustering, k-means, image processing, continuous optimization.

Lisin AV, Faizullin RT. Application of methaheuristics to k-means clustering. Computer Optics 2015; 39(3): 405-12. DOI: 10.18287/0134-2452-2015-39-3-406-412.


  1. Segaran T. Programming Collective Intelligence. O’Reilly Media; 2007.
  2. Inaba M, Katoh N, Imai H. Applications of Weighted Voronoi Diagrams and Randomization to Variance-based K-clustering: (Extended Abstract). Proceedings of the Tenth Annual Symposium on Computational 1994; 10: 332-339.
  3. Lloyd S. Least squares quantization in PCM. Information Theory, IEEE Transactions on 1982; Vol. 28(2): 129-137.
  4. Lisin AV, Faizullin RT. Heuristic algorithm for finding approximate solution of Steiner problem based on physical analogies [in Russian]. Computer Optics 2013; 37(4): 503-510.
  5. Dulkeyt VI, Faizullin RT. Approximate solving of travelling salesman problem by recursive plotting of auxiliary curve [in Russian]. Applied Discrete Mathematic 2009; 1(3): 72-78.
  6. Sundaram RK. A First Course in Optimization Theory. Cambridge University Press; 1996.
  7. Avriel M. Nonlinear Programming: Analysis and Methods. Dover Publishing; 2003.
  8. Duman S, Güvenç U, Yörükeren N. Gravitational Search Algorithm for Economic Dispatch with Valve-Point Effects. International Review of Electrical Engineering 2010; 5: 2890-2895.
  9. Rashedi E, Nezamabadi-pour H, Saryazdi S. GSA: A Gravitational Search Algorithm. Information Science 2009; 179: 2232–2248.
  10. Zinovjev AU. Multi dimension data visualization. Krasnoyarsk State Technical University Press; 2000.
  11. Cormen T, Rivest R, Leiserson C. Introduction to algorithms. McGraw-Hill Science/Engineering/Math; 2001.

© 2009, IPSI RAS
151, Molodogvardeiskaya str., Samara, 443001, Russia; E-mail: ; Tel: +7 (846) 242-41-24 (Executive secretary), +7 (846) 332-56-22 (Issuing editor), Fax: +7 (846) 332-56-20