A Hybrid Data Mining GRASP with Path-Relinking

• Hugo Barbalho UFF
• Isabel Rosseti UFF
• Simone L. Martins UFF
• Alexandre Plastino UFF

Abstract

The exploration of hybrid metaheuristics — combination of metaheuristics with concepts and processes from other research areas — has been an important trend in combinatorial optimization research. In this work, we developed a hybrid version of the GRASP metaheuristic which incorporates the path-relinking procedure — a memory-based intensification strategy — and a data mining module. Computational experiments showed that employing the combination of path-relinking and data mining allowed GRASP to find better results in less computational time. Another contribution of this work is the application of the path-relinking hybrid proposal for the 2-path network design problem, which improved the state-of-the-art solutions for this problem.

References

A. Plastino, E. R. Fonseca, R. Fuchshuber, S. L. Martins, A. A. Freitas, M. Luis, and S. Salhi, A hybrid data mining metaheuristic for the p-median problem, Proceedings of the SIAM International Conference on Data Mining, pp. 305-316, 2009.

C. C. Ribeiro, S. L. Martins, and I. Rosseti, Metaheuristics for optimization problems in computer communications, Computer Communications, 30 (2007), pp. 656-669.

C. C. Ribeiro and I. Rosseti, Efficient parallel cooperative implementations of GRASP heuristics, Parallel Computing 33 (2007), pp. 21-35.

G. Dahl and B. Johannessen, The 2-path network problem, Networks, 43 (2004), pp. 190–199.

F. Glover, M. Laguna, and R. Martí, Fundamentals of scatter search and path-relinking, Control and Cybernetics 39, pp. 653–684, 2000.

T. A. Feo and M. G. C. Resende, A probabilistic heuristic for a computationally difficult set covering problem, Operations Research Letters, 8 (1989), pp. 67-71.

T. A. Feo and M. G. C. Resende, Greedy randomized adaptive search procedures, Journal of Global Optimization, 6 (1995), pp. 109-133.

P. Festa and M. G. C. Resende, An annotated bibliography of GRASP Part II: Applications, International Transactions in Operational Research, 16 (2009), pp. 131–172.

J. Han and M. Kamber, Data Mining: Concepts and Techniques, 2nd Ed., Morgan Kaufmann Publishers, 2006.

L. F. Santos, M. H. F. Ribeiro, A. Plastino, and S. L. Martins, A hybrid GRASP with data mining for the maximum diversity problem, Proceedings of the International Workshop on Hybrid Metaheuristics, LNCC 3636, pp. 116–127, 2005.

L. F. Santos, S. L. Martins, and A. Plastino, Applications of the DM-GRASP heuristic: A survey, International Transactions in Operational Research, 15 (2008), pp. 387–416.

L. F. Santos, C. V. Albuquerque, S. L. Martins, and A. Plastino, A hybrid GRASP with data mining for efficient server replication for reliable multicast, Proceedings of the IEEE GLOBECOM Conference, 2006.

M. Laguna and R. Martí, GRASP and path relinking for 2-layer straight line crossing minimization, INFORMS Journal on Computing 11 (1999), pp. 44–52.

M. H. F. Ribeiro, V. F. Trindade, A. Plastino, and S. L. Martins, Hybridization of GRASP metaheuristic with data mining techniques, Proceedings of the ECAI Workshop on Hybrid Metaheuristics, pp. 69-78, 2004.

R. Aiex, M. G. C. Resende, and C. C. Ribeiro, TTT plots: a perl program to create time-to-target plots, Optimization Letters, 4 (2007), pp. 355–366.

M. G. C. Resende and C. C. Ribeiro, Greedy randomized adaptive search procedures, Handbook of Metaheuristics, Kluwer Academic Publishers, 2003.

M. G. C. Resende and C. C. Ribeiro, GRASP with path-relinking: Recent advances and applications, Metaheuristics: Progress as Real Problem Solvers (T. Ibaraki et al. editors), (2005), 29–63.