A Tabu Search Algorithm for Partitioning

Javier Trejos (jtrejoscariari.ucr.ac.cr)
Eduardo Piza (epizacariari.ucr.ac.cr)
Alex Murillo (alexmurillo65hotmail.com)

Abstract: We present an original method for partitioning by automatic classi- fication, using the optimization technique of tabu search. The method uses a classical tabu search scheme based on transfers for the minimization of the within variance; it introduces in the tabu list the indicator of the object transfered. This method is compared with two stochastic optimization-based methods proposed by the authors (one based on simulated annealing and the other on a genetic algorithm), and with the classical k-means and Ward methods. Results of the tabu search are significantly better than the classical and genetic methods, and slightly better than our simulated annealing method.

Keywords: Clustering, data mining, tabu search, metaheuristics.

Category 1: Applications -- Science and Engineering (Data-Mining )

Category 2: Combinatorial Optimization (Meta Heuristics )

Category 3: Applications -- Science and Engineering (Statistics )

Citation: Preprint 1-1999 CIMPA, University of Costa Rica 2060 San Jose, Costa Rica. March 1999

Download: [PDF]

Entry Submitted: 12/03/2004
Entry Accepted: 12/03/2004
Entry Last Modified: 12/03/2004

Modify/Update this entry