Aplicación de Pointer Networks al Problema del Viajante

Lucas Forni

Grupo de Investigación sobre

Inteligencia Computacional e Ingeniería de Software

UTN-FRCU

Concepción del Uruguay, Argentina fornil@frcu.utn.edu.ar

Resumen—El Problema del Viajante de Comercio (TSP) es un desafío clásico en optimización combinatoria. En este trabajo, exploramos una aproximación poco usual al TSP utilizando redes neuronales de punteros (Ptr-Nets). Estas redes, capaces de generar secuencias de salida de longitud variable, se muestran prometedoras para abordar problemas de optimización combinatoria. Proponemos confeccionar un nuevo conjunto de datos de soluciones para el TSP, generado a partir de metaheurísticas como optimización por colonias de hormigas, búsqueda tabú y algoritmos genéticos. Este dataset servirá para entrenar una Ptr-Net y evaluar su capacidad para aprender patrones de solución y generalizar a instancias más grandes. Los resultados obtenidos permitirán comparar el desempeño de la Ptr-Net con las metaheurísticas tradicionales en términos de calidad de la solución y tiempo de ejecución.

Keywords—Pointer Networks, Problema del Viajante, Optimización Combinatoria, Metaheurísticas.

I. Introducción

El problema del viajante de comercio (Traveling Salesman Problem, TSP) es uno de los problemas de optimización combinatoria más interesantes. Su formulación original fue realizada en 1934 por Hassler Whitney [1]. En este problema, un agente debe visitar 𝑛 clientes situados en ciudades interconectadas formando un grafo completo 𝐾 .

𝑛

Cada interconexión (arcos del grafo) entre dos ciudades (vértices del grafo) 𝑖𝑗 tiene asociado un peso o distancia 𝑑

𝑖𝑗

ϵℜ . El agente quiere recorrer la mínima distancia total

0

posible, visitando a cada cliente exactamente una vez y volviendo a la ciudad de origen, es decir, quiere encontrar el circuito de Hamilton de longitud mínima. Este TSP es uno de los primeros problemas que demostró ser NP-hard [2]. Hoy en día, hay una gran cantidad de documentos sobre sus diferentes variantes y soluciones[3].

Por otro lado, Pointer Network[4] (Ptr-Net) es una arquitectura neuronal presentada en 2017 que busca aprender la probabilidad condicionada de una secuencia de salida con elementos que son tokens discretos correspondientes a las posiciones en la secuencia de entrada. Para estos problemas el tamaño de salida depende de la longitud de la entrada, que es variable. Muchos problemas de optimización combinatoria pertenecen a esta clase, entre ellos TSP.

En su trabajo los autores generaron un dataset que utiliza el algoritmo Held-Karp para generar soluciones exactas para hasta 20 ciudades. Para instancias más grandes se usan otros algoritmos que producen soluciones aproximadas.

II. Objetivo

El objetivo de este trabajo es generar un dataset para instancias de 100 ciudades, resueltas por Ant Colony Optimization, Tabu Search, Genetic Algorithms, para así entrenar la red neuronal con arquitectura Ptr-Net utilizando este dataset y evaluar su capacidad de generalización a instancias de mayor tamaño, comparando el rendimiento en tiempo y calidad de la solución respecto de las metaheurísticas previamente mencionadas.

III. APORTE

Se analizará la habilidad de la red para aprender patrones de solución y su capacidad para generalizar a instancias de mayor tamaño de TSP.

El dataset y código utilizado quedarán a disposición de la comunidad.

IV. Conclusiones y Trabajos Futuros

Se han descrito los aspectos conceptuales de una arquitectura poco utilizada que resuelve instancias de TSP de manera razonable. Se ha propuesto la creación de un dataset a partir de metaheurísticas, su posterior utilización en el entrenamiento de la red neuronal, y la evaluación de los resultados que proporciona. Al basarse en metaheurísticas como Ant Colony Optimization, Tabu Search y Genetic Algorithms garantiza la obtención de soluciones de buena calidad en tiempos de respuesta razonables para el dataset, que luego podrán ser comparados con el modelo entrenado. Este trabajo sirve como base para

XXX-X-XXXX-XXXX-X/XX/$XX.00 ©20XX IEEE

extenderse a otros problemas similares, como puede ser el Problema de Enrutamiento de Vehículos.

Agradecimientos

Le agradezco a Dr. Ing. Carlos A. Casanova P., director del grupo de investigación, sus acertados comentarios han sido fundamentales para el desarrollo de este trabajo.

También al Grupo de Investigación en Inteligencia Computacional e Ingeniería de Software (GIICIS), perteneciente a la Universidad Tecnológica Nacional, Facultad Regional de Concepción del Uruguay. Que durante tres años sus integrantes me han brindado espacio para ahondar en mis intereses, el apoyo y consejos necesarios para mejorar en ellos.

Referencias

[1] Merrill M. Flood, (1956) The Traveling-Salesman Problem.

Operations Research 4(1):61-75. https://doi.org/10.1287/opre.4.1.61

[2] Karp, R.M. (2010). Reducibility Among Combinatorial Problems. In: Jünger, M., et al. 50 Years of Integer Programming 1958-2008. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-68279-0_8

[3] Huerta, I. I., Neira, D. A., Ortega, D. A., Varas, V., Godoy, J., & Asin-Acha, R. (2022). Improving the state-of-the-art in the traveling salesman problem: An anytime automatic algorithm selection. Expert Systems with Applications, 187, 115948.

[4] Vinyals, O., Fortunato, M., & Jaitly, N. (2015). Pointer networks. Advances in neural information processing systems, 28.