Paralelização de Metaheurísticas para Execução Autonômica em Grades Computacionais
Resumo
Na busca por melhores serviços ou maiores lucros, a utilização de metaheurísticas tem sido um importante aliado da indústria para resolver questões operacionais complexas em tempos computacionais aceitáveis. O desenvolvimento de metaheurísticas paralelas eficientes é difícil e, para executar instâncias reais, os algoritmos necessitam de muito poder computacional. Enquanto a computação em grades pode oferecer tal poder computacional, suas características específicas criam uma complexidade adicional para desenvolver aplicações eficientes. Este trabalho propõe uma estratégia simples de paralelização para executar metaheurísticas seqüenciais em grades computacionais. O objetivo é eliminar a necessidade do desenvolvedor encarar a tarefa de paralelizar uma metaheurística, e mostrar que executando múltiplas instâncias de uma metaheurística seqüencial de forma coordenada em paralelo é possível reduzir o tempo para alcançar boas soluções. A paralelização proposta é composta de duas camadas: um middleware de gerenciamento da execução na grade e a estratégia de coordenação das metaheurísticas seqüenciais. Para validar essa proposta foram desenvolvidas duas novas metaheurísticas paralelas, uma para o problema do torneio com viagens espelhado e a outra para o problema da árvore geradora de custo mínimo com restrição de diâmetro. Ambas as paralelizações foram capazes de melhorar, para várias instâncias, os melhores resultados conhecidos na literatura.
Referências
A. P. F. Araújo. Paralelização Autonômica de Metaheurísticas em Ambientes de Grid. PhD thesis, Departamento de Informática, PUC-Rio, 2008.
J. Beasley. Welcome to OR-Library. Disponível em http://people.brunel.ac.uk/mastjjb/jeb/info.html, última visita em 20 de Maio de 2008.
C. Boeres, A. Sena, A. Nascimento, J. Silva, D. Q. Vianna, and V. Rebello. On the advantages of an alternative MPI execution model for the grids. In Proceedings of the 7th IEEE International Symposium on Cluster Computing and the Grid, pages 575–582, Rio de Janeiro, 2007. IEEE Press.
V.-D. Cung, S.Martins, C. Ribeiro, and C. Roucairol. Strategies for the parallel implementation of metaheuristics. In C. Ribeiro and P. Hansen, editors, Essays and Surveys in Metaheuristics, pages 263–308. Kluwer Academic Publishers, 2002.
K. Easton, G. Nemhauser, and M. Trick. The traveling tournament problem: Description and benchmarks. In T. Walsh, editor, Principles and Practice of Constraint Programming, volume 2239 of Lecture Notes in Computer Science, pages 580–589. Springer, 2001.
K. Easton, G. Nemhauser, and M. Trick. Solving the travelling tournament problem: A combined integer programming and constraint programming approach. In E. Burke and P. Causmaecker, editors, Selected Papers from the 4th International Conference on the Practice and Theory of Automated Timetabling, volume 2740 of Lecture Notes in Computer Science, pages 100–109. Springer, 2003.
I. Foster. The grid: A new infrastructure for 21st century science. Physics Today, 55:42–47, 2002.
M. R. Garey and D. S. Johnson. Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman, 1979.
L. Gouveia and T. L. Magnanti. Network flow models for designing diameter-constrained minimum-spanning and Steiner trees. Networks, 41:159–173, 2003.
M. Gruber and G. Raidl. Variable neighborhood search for the bounded diameter minimum spanning tree problem. In 18th Mini Euro Conference on Variable Neighborhood Search, pages 1–11, Tenerife, 2005.
H. Lourenço, O. Martins, and T. Stutzle. Iterated local search. In F. Glover and G. Kochenberger, editors, Handbook of Metaheuristics, pages 321–353. Kluwer Academic Publishers, 2003.
M. Resende and C. Ribeiro. Greedy randomized adaptive search procedures. In F. Glover and G. Kochenberger, editors, Handbook of Metaheuristics, pages 219–249. Kluwer Academic Publishers, 2003.
C. Ribeiro and S. Urrutia. Heuristics for the mirrored traveling tournament problem. European Journal of Operational Research, 179:775–787, 2007.
A. Santos. Modelos e Algoritmos para o Problema da Árvore Geradora de Custo Mínimo com Restrição de Diâmetro. PhD thesis, Departamento de Informática, PUCRio, 2006.
