KDD-BR 2021: Using Graph Neural Networks for Link Prediction in TSP Problem
Resumo
No problema do caixeiro viajante (TSP), o objetivo é encontrar uma rota que passe por todas as cidades e retorne à cidade de origem com a menor distância total percorrida. Como um problema NP-completo, encontrar soluções não é fácil, e várias heurísticas foram propostas. Atualmente, com o avanço no uso do Aprendizado de Máquina (AM), é possível usar o AM para prever conexões entre cidades na solução ótima. Nosso modelo, baseado em redes neurais de grafos, obteve uma pontuação F1 de 0,10645 na tabela de classificação pública do KDD-BR 2021, o suficiente para superar a solução gulosa. Isso mostra que o AM pode ser uma boa técnica para gerar soluções mais rapidamente ou até mesmo construir soluções melhores.
Palavras-chave:
Graph-based neural networks, TSP problem, Machine Learning
Referências
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009). Introduction to algorithms. MIT press.
Dwivedi, V. P., Joshi, C. K., Laurent, T., Bengio, Y., and Bresson, X. (2020). Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982.
Joshi, C. K., Cappart, Q., Rousseau, L.-M., Laurent, T., and Bresson, X. (2020). Learning tsp requires rethinking generalization. arXiv preprint arXiv:2006.07054.
Joshi, C. K., Laurent, T., and Bresson, X. (2019). An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.01227.
Menger, K. (1932). Das botenproblem. Ergebnisse eines mathematischen kolloquiums, 2(4):11–12.
Prates, M., Avelar, P., Lemos, H., Lamb, L., and Vardi, M. (2019). Learning to solve np-complete problems: A graph neural network for decision tsp. Proceedings of the AAAI Conference on Artificial Intelligence, 33:4731–4738.
Wang, Y., Sun, Y., Liu, Z., Sarma, S. E., Bronstein, M. M., and Solomon, J. M. (2019). Dynamic graph cnn for learning on point clouds. Acm Transactions On Graphics (tog), 38(5):1–12.
Dwivedi, V. P., Joshi, C. K., Laurent, T., Bengio, Y., and Bresson, X. (2020). Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982.
Joshi, C. K., Cappart, Q., Rousseau, L.-M., Laurent, T., and Bresson, X. (2020). Learning tsp requires rethinking generalization. arXiv preprint arXiv:2006.07054.
Joshi, C. K., Laurent, T., and Bresson, X. (2019). An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.01227.
Menger, K. (1932). Das botenproblem. Ergebnisse eines mathematischen kolloquiums, 2(4):11–12.
Prates, M., Avelar, P., Lemos, H., Lamb, L., and Vardi, M. (2019). Learning to solve np-complete problems: A graph neural network for decision tsp. Proceedings of the AAAI Conference on Artificial Intelligence, 33:4731–4738.
Wang, Y., Sun, Y., Liu, Z., Sarma, S. E., Bronstein, M. M., and Solomon, J. M. (2019). Dynamic graph cnn for learning on point clouds. Acm Transactions On Graphics (tog), 38(5):1–12.
Publicado
29/11/2021
Como Citar
AFONSO, Bruno Klaus de Aquino; OLIVEIRA, Willian Dihanster Gomes de; LAMOSA, Jéssica Domingues; BERTON, Lilian.
KDD-BR 2021: Using Graph Neural Networks for Link Prediction in TSP Problem. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (ENIAC), 18. , 2021, Evento Online.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2021
.
p. 791-794.
ISSN 2763-9061.
DOI: https://doi.org/10.5753/eniac.2021.18426.
