GRASP com path-relinking para agrupamento de dados biológicos

Abstract

Clustering is an unsupervised method of classifying data into clusters. In clustering problems, it is not previously known how many and which classes are needed to describe coherently a set of data.In computational biology, data clustering proved to be useful in problems of patterns discovery in data such as protein classification, prediction of protein localization in cell units and cancer diagnosis.Recently, optimization techniques like metaheuristics, have been used frequently in the literature as an alternative or adjunct to increase the efficiency and effectiveness of the classic tools of clustering, usually based on statistical and mathematical methods. In this study we proposed hybrid algorithms based on metaheuristics GRASP and Path-Relinking for the clustering problem of biological data, aiming to obtain better solutions when compared to using only the GRASP in its standard form. Therefore, in this work, we considered the hypothesis that using the Path-Relinking as a strategy for intensifying GRASP, improves performance and quality of solutions. We consider hybridization of the GRASP proposed by Nascimento et al. [2010b], with four variants of Path-Relinking: forward, backward, mixed, and greedy randomized adaptative. The validation of solutions is given by comparing with the classic algorithms k-means, k-medians, PAM (Partitioning Around Medoids) as well as GRASP proposed by Nascimento et al. (2010).The experiments were performed with real data from 10 biological instances, and results showed that the hybrid model improved the clustering task. We obtained further exploration of the search space, more cohesive clusters, increase of robustness and reduction of computational time. Greedy Randomized Adaptive and Mixed showed the best results.