Implementação Paralela de uma Metaheurística GRASP com Path-Relinking para o Problema da Árvore Geradora de Custo Mínimo com Grupamentos
Resumo
A metaheurística GRASP é um processo iterativo, cujas iterações consistem de duas fases: uma fase de construção e outra de busca local. O algoritmo retorna a melhor solução encontrada depois de um determinado número de iterações. Neste trabalho, a metaheurística GRASP é aplicada conjuntamente à técnica path-relinking a um problema variante da Árvore Geradora Mínima (AGM), denominado Árvore Geradora de custo Mínimo com Grupamentos (AGMG). O objetivo é reduzir o tempo computacional e melhorar a qualidade das soluções GRASP através de uma implementação paralela desta metaheurística. Os resultados obtidos mostraram speedup linear para esta implementação.
Referências
AIEX, R. M. (2002). Uma investigação experimental da distribuição de probabilidade do tempo de solução em heurísticas GRASP e sua aplicação na análise de implementações paralelas. Tese de Doutorado, PUC - Rio, Departamento de Informática, Rio de Janeiro.
DROR M.; HAOUARI M. and CHAOUACHI J. (2000) Generalized Spanning Trees. European Journal of Operational Research, 120, p. 583-592.
FEO T. A. and RESENDE M. G. C. (1995). Greedy Randomized Adaptive Search Procedures. Journal of Global Optimization 6, p. 109-133.
FEREMANS, C.; LABBÃO, M. and LAPORTE, G. (2002). A comparative analysis of several formulations for the generalized minimum spanning tree problem. Networks, 39, p.29-34.
FLEURENT, C. and GLOVER, F.( 1999). Improved constructive multistart strategies for the quadratic assignment problem using adaptive memory. INFORMS Journal on Computing, 11:198-204.
HOLLAND, J. H. (1975). Adaptation in Natural and Artificial System. MIT Press.
LAGUNA, M. and MARTÍ, R. (1999). GRASP and pathrelinking for 2-layer straight line crossing minimization. INFORMS Journal on Computing, 11:44-52.
MARINHO E. H.(2005). Heurísticas Busca Tabu para o Problema de Programação de Tripulações de Ônibus Urbano, Dissertação de Mestrado em Computação, Universidade Federal Fluminense, Niterói RJ.
MORELLI C. D. S. e VIEIRA L. T. (1999). Análise de Métodos Heurísticos de Característica Gulosa. IV Semana Acadêmica do PPGC (Programa de Pós-Graduação em Computação).
OCHI L.; BRUNO L. e FERNANDO C. (2003). Técnicas Para Melhorar o Desempenho de Algoritmos Evolutivos: Uma Aplicação Para o Problema de Árvore Geradora de custo Mínimo Com Grupamentos. III Congresso Brasileiro de Computação. Itajaí-SC, p. 661-672.
POP P. C. (2004). New Models of the Generalized Minimum Spanning Tree Problem. Journal of Mathematical Modelling and Algorithms, pp 153-166.
RESENDE M. G. C. and RIBEIRO C. C. (2003). Greedy randomized adaptive search procedures. In Handbook of Metaheuristics, F. Glover and G. Kochenberger, eds., Kluwer Academic Publishers, pp. 219-249.
ROSSETI, I. C. M. (2003). Estratégias sequênciais e paralelas de GRASP com reconexão por caminhos para o problema de síntese de redes a 2-caminhos. Tese de Doutorado, PUC - Rio, Departamento de Informática, Rio de Janeiro.
SNIR, M.; OTTO, S.T. and WALKER, D. W. (1996). MPI: The Complete Reference. The MIT Press.
CORMEN, T. ; LEISERSON, C. E.; RIVEST, R. L. and STEIN, C (2002). Algoritmos: Teoria e Prática. Tradução da 2a edição Americana. Editora Campus.
ALVARENGA, F. V. e ROCHA, M. L. Melhorando o Desempenho da Metaheurística GRASP Utilizando a Técnica Path-Relinking: Uma Aplicação para o Problema da Árvore Geradora de Custo Mínimo com Grupamentos. XVIII SBPO. Goiânia-GO. Publicação em CD-ROM.
DROR M.; HAOUARI M. and CHAOUACHI J. (2000) Generalized Spanning Trees. European Journal of Operational Research, 120, p. 583-592.
FEO T. A. and RESENDE M. G. C. (1995). Greedy Randomized Adaptive Search Procedures. Journal of Global Optimization 6, p. 109-133.
FEREMANS, C.; LABBÃO, M. and LAPORTE, G. (2002). A comparative analysis of several formulations for the generalized minimum spanning tree problem. Networks, 39, p.29-34.
FLEURENT, C. and GLOVER, F.( 1999). Improved constructive multistart strategies for the quadratic assignment problem using adaptive memory. INFORMS Journal on Computing, 11:198-204.
HOLLAND, J. H. (1975). Adaptation in Natural and Artificial System. MIT Press.
LAGUNA, M. and MARTÍ, R. (1999). GRASP and pathrelinking for 2-layer straight line crossing minimization. INFORMS Journal on Computing, 11:44-52.
MARINHO E. H.(2005). Heurísticas Busca Tabu para o Problema de Programação de Tripulações de Ônibus Urbano, Dissertação de Mestrado em Computação, Universidade Federal Fluminense, Niterói RJ.
MORELLI C. D. S. e VIEIRA L. T. (1999). Análise de Métodos Heurísticos de Característica Gulosa. IV Semana Acadêmica do PPGC (Programa de Pós-Graduação em Computação).
OCHI L.; BRUNO L. e FERNANDO C. (2003). Técnicas Para Melhorar o Desempenho de Algoritmos Evolutivos: Uma Aplicação Para o Problema de Árvore Geradora de custo Mínimo Com Grupamentos. III Congresso Brasileiro de Computação. Itajaí-SC, p. 661-672.
POP P. C. (2004). New Models of the Generalized Minimum Spanning Tree Problem. Journal of Mathematical Modelling and Algorithms, pp 153-166.
RESENDE M. G. C. and RIBEIRO C. C. (2003). Greedy randomized adaptive search procedures. In Handbook of Metaheuristics, F. Glover and G. Kochenberger, eds., Kluwer Academic Publishers, pp. 219-249.
ROSSETI, I. C. M. (2003). Estratégias sequênciais e paralelas de GRASP com reconexão por caminhos para o problema de síntese de redes a 2-caminhos. Tese de Doutorado, PUC - Rio, Departamento de Informática, Rio de Janeiro.
SNIR, M.; OTTO, S.T. and WALKER, D. W. (1996). MPI: The Complete Reference. The MIT Press.
CORMEN, T. ; LEISERSON, C. E.; RIVEST, R. L. and STEIN, C (2002). Algoritmos: Teoria e Prática. Tradução da 2a edição Americana. Editora Campus.
ALVARENGA, F. V. e ROCHA, M. L. Melhorando o Desempenho da Metaheurística GRASP Utilizando a Técnica Path-Relinking: Uma Aplicação para o Problema da Árvore Geradora de Custo Mínimo com Grupamentos. XVIII SBPO. Goiânia-GO. Publicação em CD-ROM.
Publicado
24/10/2007
Como Citar
ALVARENGA, Fabiano Vieira de; ROCHA, Marcelo Lisboa; PEREIRA, Marluce Rodrigues.
Implementação Paralela de uma Metaheurística GRASP com Path-Relinking para o Problema da Árvore Geradora de Custo Mínimo com Grupamentos. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 8. , 2007, Gramado.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2007
.
p. 137-144.
DOI: https://doi.org/10.5753/wscad.2007.18763.
