Solution du problème du voyageur de commerce à l'aide d'un dispositif combinatoire magnonique

Jul 27, 2023

Rapports scientifiques volume 13, Numéro d'article : 11708 (2023) Citer cet article

207 Accès

Détails des métriques

Le problème du voyageur de commerce (TSP) est un problème de prise de décision essentiel pour un certain nombre d'applications pratiques. Aujourd'hui, ce problème est résolu sur les calculateurs numériques exploitant une architecture de type booléen en vérifiant une à une un certain nombre de routes possibles. Dans ce travail, nous décrivons un type particulier de matériel pour la solution TSP. Il s'agit d'un dispositif combinatoire magnonique comprenant des parties magnétiques et électriques connectées dans le circuit en anneau actif. Il existe un certain nombre de voies de propagation possibles dans le maillage magnétique constitué de déphaseurs, de filtres de fréquence et d'atténuateurs. Les déphaseurs imitent les villes en TSP tandis que la distance entre les villes est codée dans l'atténuation du signal. L'ensemble de filtres de fréquence permet aux ondes de différentes fréquences de se propager sur les différentes routes. Le principe de fonctionnement est basé sur la superposition d'ondes classique. Un certain nombre d'ondes arrivent en parallèle sur toutes les routes possibles, accumulant différents déphasages et amortissements d'amplitude. Cependant, seules les ondes qui accumulent un certain déphasage seront amplifiées par la partie électrique. L'amplification concerne en premier lieu les ondes qui possèdent les pertes de propagation minimales. Cela rend ce type d'appareil adapté à la solution TSP, où les vagues sont similaires aux vendeurs voyageant sur tous les itinéraires possibles à la fois. Nous présentons les résultats de la modélisation numérique illustrant les solutions TSP pour quatre et six villes. Nous présentons également des données expérimentales pour la solution TSP avec quatre villes. Le prototype est constitué de composants disponibles dans le commerce, notamment des déphaseurs/filtres magnétiques, des câbles coaxiaux, des séparateurs, des atténuateurs et un amplificateur à large bande. Il existe trois exemples de recherche de l'itinéraire le plus court entre les villes pour trois ensembles différents de distances de ville à ville. L'approche proposée est évolutive aux TSP avec un plus grand nombre de villes. Les limites et les défis physiques sont également abordés.

TSP est l'un des problèmes d'optimisation combinatoire les plus connus1. Cela peut s'énoncer comme suit : "Étant donné une liste de villes et les distances entre chaque paire de villes, trouvez l'itinéraire le plus court possible qui visite chaque ville exactement une fois et revient à la ville d'origine." Il s’agit d’un problème de dureté en temps polynomial non déterministe (NP-difficile), ce qui signifie qu’il n’y a aucune garantie d’obtenir l’itinéraire optimal ni aucun algorithme exact pour le résoudre en temps polynomial. Le TSP est important dans diverses applications pratiques, notamment le transport2, la planification3 et la génomique4. Mathématiquement, il peut être défini comme étant donné un ensemble de \(n\) villes, nommé \(\left\{{c}_{1},{c}_{2},\dots ,{c}_{n }\right\}\), et les permutations \(\left\{{\sigma }_{1},{\sigma }_{2},\dots ,{\sigma }_{n!}\right\} \). L'objectif est de choisir \({\sigma }_{i}\) tel que la somme de toutes les distances euclidiennes entre les villes d'un tour soit minimisée. TSP peut être modélisé comme un graphe pondéré non orienté, comme le montre la figure 1, où les villes sont les sommets du graphe, les chemins sont les bords du graphe et la distance d'un chemin est le poids du bord. TSP peut être résolu en vérifiant un par un tous les itinéraires possibles \(\left(n-1\right)!/2\). Il est relativement facile de vérifier tous les itinéraires possibles pour un petit nombre de villes. Par exemple, il existe des itinéraires \(\left(4-1\right)!/2=3\) pour le TSP avec quatre villes. Le nombre d'itinéraires possibles augmente proportionnellement à la factorielle \(n\), ce qui rend difficile la résolution d'un grand nombre de villes à l'aide d'appareils informatiques classiques.

Graphique pondéré non orienté pour TSP avec quatre villes. Les villes sont les sommets du graphique, les chemins sont les bords du graphique et la distance d'un chemin est le poids du bord.

Il y a eu plusieurs tentatives pour construire du matériel spécial pour la solution TSP5,6. Par exemple, le TSP de 6 villes a été résolu à l’aide d’un réseau optique de type Kohonen6. Cependant, aucune de ces approches n’a abouti à un dispositif pratiquement viable. Récemment, diverses techniques d'optimisation utilisées en intelligence artificielle (IA) ont été appliquées à TSP7. Cela peut accélérer considérablement la solution TSP, mais ne peut pas offrir un avantage fondamental implémenté sur du matériel conventionnel.