Metaheurística GRASP com Memória Adaptativa para a solução do Problema da árvore Geradora Mínima Generalizado
Resumo
O Problema da Árvore de Cobertura Mínima Generalizado (PAGMG) consiste em, dado um grafo G cujos vértices estão divididos em grupos, encontrar uma árvore que cubra todos os grupos de G, de forma que a soma do custo das arestas de T seja mínima. Aplicações deste problema são encontradas em redes de telecomunicações, redes de distribuição de energia elétrica, e em sistemas de irrigação agrícola. Este trabalho apresenta uma metaheuristica GRASP com memória adaptativa para a solução do PAGMG. Resultados experimentais mostram a eficiência do método proposto.
Referências
Dror, M., Haouari, M., and Chaouachi, J. S. (2000). Generalized spanning trees. European Journal of Operational Research, 120:583–592.
Feo, T., Resende, M., and Smith, S. (1994). A greedy randomized adaptive search procedure for maximum independent set. Operations Research, 42:860–878.
Feremans, C., Labbé, M., and Laporte, G. (2000). The generalized minimum spanning tree problem: Polyhedral analysis ans branch-and-cut algorithm. Technical report, Université Libre de Bruxelles, Bruxelas, Bélgica. Available at [link].
Fischetti, M., Salazar, J. J., and Toth, P. (1995). The symmetric generalized traveling salesman polytope. Networks, 26:113–123.
Glover, F., Laguna, M., and Martí, R. (2000). Fundamentals of scatter-search and path relinking. Control ans Cybernetics, 36:653–684.
Golden, B., Raghavan, S., and Stanojević, D. (2005). Heuristic search for the generalized minimum spanning tree. INFORMS Journal on Computing, 17:290–304.
Goncalves, L. B., Ochi, L. S., and Martins, S. L. (2005). A grasp with adaptive memory for a period vehicle routing problem. In Mohammadian, M., editor, Proceedings of International Conference on Computational Intelligence for Modelling, Control & Automation (CIMCA 2005), volume 1, pages 721–727, Vienna, Austria. IEEE Computer Society.
Kansal, A. R. and Torquato, S. (2001). Globally and locally minimal weigth spanning tree networks. Physica A, 301:601–619.
Myung, Y. S., Lee, C. H., and Tcha, D. W. (1995). On the generalized minimum spanning tree problem. Networks, 26:231–241.
Prais, M. and Ribeiro, C. (2000). Reactive GRASP: An application to a matrix decomposition problem in TDMA traffic assignment. INFORMS Journal on Computing, 12:164–176.
Reinelt, G. (1991). TSPLIB a traveling salesman problem library. ORSA Journal on Computing, 3:376–384.
Resende, M. and Ribeiro, C. (2003). GRASP and path-relinking: Recent advances and applications. In Ibaraki, T. and Yoshitomi, Y., editors, Proceedings of the Fifth Metaheuristics International Conference (MIC2003), pages 1–6.
Shyu, S. J., Yin, P. Y., Lin, B. M. T., and Haouari, M. (2003). Ant-tree: An ant colony optimization approach to the generalized minimum spanning tree problem. Journal of Experimental and Theoretical Artificial Inteligence, 15:103–112.
Silva, G., Andrade, M. R. Q., Ochi, L. S., Martins, S. L., and Plastino, A. New heuristics for the maximum diversity problem. STATUS: To appear in Journal of Heuristics SPRINGER.
Feo, T., Resende, M., and Smith, S. (1994). A greedy randomized adaptive search procedure for maximum independent set. Operations Research, 42:860–878.
Feremans, C., Labbé, M., and Laporte, G. (2000). The generalized minimum spanning tree problem: Polyhedral analysis ans branch-and-cut algorithm. Technical report, Université Libre de Bruxelles, Bruxelas, Bélgica. Available at [link].
Fischetti, M., Salazar, J. J., and Toth, P. (1995). The symmetric generalized traveling salesman polytope. Networks, 26:113–123.
Glover, F., Laguna, M., and Martí, R. (2000). Fundamentals of scatter-search and path relinking. Control ans Cybernetics, 36:653–684.
Golden, B., Raghavan, S., and Stanojević, D. (2005). Heuristic search for the generalized minimum spanning tree. INFORMS Journal on Computing, 17:290–304.
Goncalves, L. B., Ochi, L. S., and Martins, S. L. (2005). A grasp with adaptive memory for a period vehicle routing problem. In Mohammadian, M., editor, Proceedings of International Conference on Computational Intelligence for Modelling, Control & Automation (CIMCA 2005), volume 1, pages 721–727, Vienna, Austria. IEEE Computer Society.
Kansal, A. R. and Torquato, S. (2001). Globally and locally minimal weigth spanning tree networks. Physica A, 301:601–619.
Myung, Y. S., Lee, C. H., and Tcha, D. W. (1995). On the generalized minimum spanning tree problem. Networks, 26:231–241.
Prais, M. and Ribeiro, C. (2000). Reactive GRASP: An application to a matrix decomposition problem in TDMA traffic assignment. INFORMS Journal on Computing, 12:164–176.
Reinelt, G. (1991). TSPLIB a traveling salesman problem library. ORSA Journal on Computing, 3:376–384.
Resende, M. and Ribeiro, C. (2003). GRASP and path-relinking: Recent advances and applications. In Ibaraki, T. and Yoshitomi, Y., editors, Proceedings of the Fifth Metaheuristics International Conference (MIC2003), pages 1–6.
Shyu, S. J., Yin, P. Y., Lin, B. M. T., and Haouari, M. (2003). Ant-tree: An ant colony optimization approach to the generalized minimum spanning tree problem. Journal of Experimental and Theoretical Artificial Inteligence, 15:103–112.
Silva, G., Andrade, M. R. Q., Ochi, L. S., Martins, S. L., and Plastino, A. New heuristics for the maximum diversity problem. STATUS: To appear in Journal of Heuristics SPRINGER.
Publicado
30/06/2007
Como Citar
FERREIRA, Cristiane Maria Santos; OCHI, Luiz Satoru.
Metaheurística GRASP com Memória Adaptativa para a solução do Problema da árvore Geradora Mínima Generalizado. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (ENIAC), 6. , 2007, Rio de Janeiro/RJ.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2007
.
p. 1202-1211.
ISSN 2763-9061.
