Hybridization of GRASP Metaheuristic with Data Mining Techniques

In this work, we propose a hybridization of GRASP metaheuristic that incorporates a data mining process. We believe that patterns obtained from a set of sub-optimal solutions, by using data mining techniques, can be used to guide the search for better solutions in metaheuristics procedures. In this hybrid GRASP proposal, after executing a significant number of GRASP iterations, the data mining process extracts patterns from an elite set of solutions which will guide the following iterations. To validate this proposal we have worked on the Set Packing Problem as a case study. Computational experiments, comparing traditional GRASP and different hybrid approaches, show that employing frequent patterns mined from an elite set of solutions conducted to better results. Besides, additional performed experiments evidence that data mining strategies accelerate the process of finding good solutions. ^★★Work sponsored by CNPq research grants 300879/00-8 and 475124/03-0. ^†Work sponsored by CNPq research grant 475124/03-0.