8/26/2021: Using AI to select a TSP algorithm of best performance for a given computing time limit, Isaias Huerta, University of Concepción

Date: Aug 26, 21

Title: Using AI to select a TSP algorithm of best performance for a given computing time limit

Speaker/presenter: Isaias Huerta

i) Presentation description:

A work presenting a new metaheuristic for the euclidean Traveling Salesman Problem (TSP) based on an Anytime Automatic Algorithm Selection model using a portfolio of five state-of-the-art solvers was carried out. A new spatial representation of nodes, in the form of a matrix grid, avoiding costly calculation of features was presented. Also, it was presented how to use a new compact staggered representation for the ranking of algorithms at each time step. Then, it was explained how to feed inputs (matrix grid) and outputs (staggered representation) into a classifying convolutional neural network to predict the ranking of the solvers at a given time. Available datasets for TSP and generated new instances to augment their number, reaching 6,689 instances, distributed into training and test sets, were used. 

Results show that the time required to predict the best solver is drastically reduced in comparison to previous traditional feature selection and machine learning methods. Furthermore, the prediction can be obtained at any time and, on average, the metasolver is better than running all the solvers separately on all the datasets, obtaining 79.8% accuracy.

References: 

• Huerta, I. I., Neira, D. A., Ortega, D. A., Varas, V., Godoy, J., & Asín-Achá, R. (2020). Anytime automatic algorithm selection for knapsack. Expert Systems with Applications, 158, 113613
• Huerta, I. I., Neira, D. A., Ortega, D. A., Varas, V., Godoy, J., & Asín-Achá, R. (2021). Improving the state-of-the-art in the Traveling Salesman Problem: An Anytime Automatic Algorithm Selection. Expert Systems with Applications, ??, ??. https://doi.org/10.1016/j.eswa.2021.115948 (Published online)