GRASP with path-relinking for data clustering: a case study for biological data

R.M.D. Frinhani, R.M.A. Silva, G.R. Mateus, P. Festa, and M.G.C. Resende

Experimental Algorithms, Proceedings of the 10th International Symposium (SEA 2011), Lecture Notes in Computer Sciencevol. 6630, pp. 410-420, 2011. 


Cluster analysis has been applied to several domains with numerous applications. In this paper, we propose several GRASP with path-relinking heuristics for data clustering problems using as case study biological datasets. All these variants are based on the construction and local search procedures introduced by Nascimento et. al [22]. We hybridize  the GRASP proposed by Nascimento et. al [22] with four alternatives for relinking method: forward, backward, mixed, and randomized. To our knowledge, GRASP with path-relinking has never been applied to cluster biological datasets. Extensive comparative experiments with other algorithms on a large set of test instances, according to different distance metrics (Euclidean, city block, cosine, and Pearson), show that the best of the proposed variants is both effective and efficient.

PDF file of full paper


Go back

Mauricio G.C. Resende's Home Page

Last modified: 17 May 2011

Copyright Notice