A Tabu search approach to the clustering problem

In this paper we consider the problem of clustering m objects into c clusters. The objects are represented by points in an n-dimensional Euclidean space, and the objective is to classify these m points into c clusters such that the distance between points within a cluster and its center (which is to be found) is minimized. The problem is a nonconvex program that has many local minima. It has been studied by many researchers and the most well-known algorithm for solving it is the k-means algorithm. In this paper, we develop a new algorithm for solving this problem based on a tabu search technique. Preliminary computational experience on the developed algorithm are encouraging and compare favorably with both the k-means and the simulated annealing algorithms.