An application of tabu search to classification problems

We present an improved method for clustering by using the combinatorial optimization technique called tabu search, for obtaining homogeneous and well-separated classes. The algorithm intends to find the optimal partition of a set of objects from the point of view of the within-classes variance criterion, trying to escape from local minima. Two versions of the method are presented: the original one, that introduces the variance value in tabu list, and the improved one, that penalizes only some partition features. Differences and comparisons are pointed out.