A Hybrid Data Mining GRASP with Path-Relinking
Resumo
A exploração de metaheurísticas híbridas — combinação de metaheur ísticas com conceitos e processos de outras áreas — vem sendo uma importante linha de pesquisa em otimização combinatória. Nesse trabalho, desenvolvemos uma versão híbrida da metaheurísticaGRASP que incorpora a técnica de reconexão por caminhos e um módulo de mineração de dados. Experimentos computacionais mostraram que a combinação da técnica de reconexão por caminhos com mineração de dados contribuiu para que o GRASP encontrasse soluções melhores em um menor tempo computacional. Outra contribuição desse trabalho é a aplicação dessa proposta híbrida ao problema de síntese de redes a 2 caminhos, o que proporcionou melhores soluções para esse problema.
Referências
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.
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.
Publicado
19/07/2011
Como Citar
BARBALHO, Hugo; ROSSETI, Isabel; MARTINS, Simone L.; PLASTINO, Alexandre.
A Hybrid Data Mining GRASP with Path-Relinking. In: CONCURSO DE TRABALHOS DE INICIAÇÃO CIENTÍFICA DA SBC (CTIC-SBC), 30. , 2011, Natal/RN.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2011
.
p. 144-153.
