Barbara
UNE APPROCHE NOVATRICE POUR RÉSOUDRE LE PROBLÈME DU VOYAGEUR DE COMMERCE EN UTILISANT UN RÉSEAU DE NEURONES TRANSFORMER
Le problème du voyageur de commerce (TSP) est l’un des défis classiques de l’optimisation combinatoire. Bien qu’il soit étudié depuis longtemps, aucune méthode exacte n’est actuellement connue pour garantir la solution optimale. Avec les avancées dans le domaine de l’intelligence artificielle, de nouvelles propositions pour aborder le TSP ont vu le jour. Dans cet article, nous utilisons un réseau de neurones Transformer pour trouver de bonnes solutions à ce problème.
LE TSP ET LE FONCTIONNEMENT DU RÉSEAU DE NEURONES TRANSFORMER
Le TSP est un problème NP-difficile, ce qui signifie qu’aucune méthode connue à ce jour ne conduit à la solution optimale en un temps polynomial. Le TSP est défini par une liste de villes et les distances entre chaque paire de villes. L’objectif est de trouver la route la plus courte possible qui visite chaque ville une seule fois et revient à la ville d’origine.
Dans ce projet, nous utilisons une architecture de réseau Transformer. Le modèle est divisé en deux composants. D’abord, l’encodeur Transformer prend en entrée un ensemble de jetons, c’est-à-dire des vecteurs représentant les nœuds dans un graphe G, et les transforme dans un nouvel espace latent grâce aux couches d’auto-attention. Ensuite, le décodeur Transformer est alimenté avec un jeton fictif z, qui indique au modèle de commencer à construire la tournée, plus les embeddings graphiques de l’encodeur, et génère une distribution de probabilité modélisant la probabilité que chaque nœud du graphe soit sélectionné comme candidat suivant dans la tournée. Le modèle est entraîné avec l’algorithme REINFORCE pour minimiser la longueur moyenne des tournées générées à partir de graphes aléatoires avec 50 nœuds chacun.
NOTRE MÉTHODE ET L’OPÉRATEUR D’ATTENTION
Notre méthode consiste à utiliser l’opérateur d’attention, en particulier l’attention croisée. Nous considérons que le TSP peut être formulé comme un problème de jeu de données vers séquence. Nous avons un ensemble de nœuds pour lesquels un ordre n’est pas défini, et nous voulons comprendre comment les trier de manière à ce que le circuit résultant soit le plus court possible. La représentation du concept d’ordre dans un réseau neuronal est généralement effectuée avec un codage positionnel, où chaque jeton dans un ensemble d’entrée est sommé avec un vecteur particulier, dont les composantes sont uniques pour une position spécifique.
Le noyau de notre méthode est l’opérateur d’attention, en particulier l’attention croisée. Le Q correspond à l’encodage positionnel, tandis que les clés et les valeurs sont extraites d’une couche d’auto-attention précédente, qui est libre d’opérer sur tous les nœuds de G. Ainsi, lorsque nous calculons la matrice d’attention croisée, nous obtenons une matrice où chaque ligne est une distribution de probabilité de la vraisemblance d’une position donnée pour être similaire à un nœud donné.
CONCLUSION
Notre approche novatrice pour résoudre le problème du voyageur de commerce en utilisant un réseau de neurones Transformer est prometteuse. Nous avons réussi à obtenir de bons résultats en évitant l’utilisation d’éléments auto-régressifs, ce qui permet une approche plus rapide et plus efficace pour résoudre ce problème d’optimisation combinatoire.
