Authors: Mathurin Soh ¹; Anderson Nguetoum Likeufack ¹

• 1 Unité de Recherche en Informatique Fondamentale, Ingénierie et Applications [Dschang]

[en]
In this paper, we propose a hybrid approach for solving the symmetric traveling salesman problem. The proposed approach combines the ant colony algorithm (ACO) with neural networks based on the attention mechanism. The idea is to use the predictive capacity of neural networks to guide the behaviour of ants in choosing the next cities to visit and to use the prediction results of the latter to update the pheromone matrix, thereby improving the quality of the solutions obtained. In concrete terms, attention is focused on the most promising cities by taking into account both distance and pheromone information thanks to the attention mechanism, which makes it possible to assign weights to each city according to its degree of relevance. These weights are then used to predict the next towns to visit for each city. Experimental results on instancesTSP from the TSPLIB library demonstrate that this hybrid approach is better compared to the classic ACO.

[fr]
Dans cet article, nous proposons une approche hybride pour résoudre le problème du voyageur de commerce symétrique. L'approche proposée combine l'algorithme des colonies de fourmis (ACO) avec des réseaux neuronaux basés sur le mécanisme d'attention. L'idée est d'utiliser la capacité prédictive des réseaux neuronaux pour guider le comportement des fourmis dans le choix des prochaines villes à visiter et d'utiliser les résultats de la prédiction de ces dernières pour mettre à jour la matrice de phéromones, améliorant ainsi la qualité des solutions obtenues. Concrètement, l'attention est portée sur les villes les plus prometteuses en tenant compte à la fois des informations de distance et de phéromone grâce au mécanisme d'attention qui permet d'attribuer des poids à chaque ville en fonction de son degré de pertinence. Ces poids sont ensuite utilisés pour prédire les prochaines villes à visiter pour chaque ville. Résultats expérimentaux sur des instancesTSP de la bibliothèque TSPLIB démontrent que cette approche hybride est meilleure que l'ACO classique.