Le réseau neuronal avec une amibe a résolu le problème des vendeurs ambulants pour 8 villes

Solutions au problème du voyageur de commerce obtenu par un système informatique basé sur l'amibe. Exemples de visites de vendeurs dans quatre, cinq, six, sept et huit villes, obtenues à titre expérimental, où chaque visite est peinte en rouge sur les canaux correspondants de la figure de droite. Les panneaux de gauche montrent les images en lumière transmise des états initiaux (

Un groupe de chercheurs japonais de l'Université Keio de Tokyo a démontré que l'amibe est capable de générer des solutions approximatives à un problème mathématique étonnamment complexe connu sous le nom de problème du voyageur de commerce .

La tâche du vendeur est l'une des tâches d'optimisation combinatoire les plus célèbres, qui consiste à trouver l'itinéraire le plus rentable qui traverse ces villes au moins une fois puis retourne à la ville d'origine.

Cependant, la déclaration d'optimisation du problème appartient à la classe des problèmes NP-difficiles, comme la plupart de ses cas spéciaux. La version du «problème de décision» (c'est-à-dire celle dans laquelle se pose la question de savoir si la route n'existe pas plus longtemps que la valeur donnée de k) appartient à la classe des problèmes NP-complets.

La difficulté de calculer la bonne solution augmente de façon exponentielle à mesure que de nouvelles villes s'ajoutent à la tâche. Par exemple, pour quatre villes, il existe trois solutions et pour six villes - 360. À l'avenir, la croissance exponentielle se poursuit.

Malgré la grande complexité de calcul, il existe un grand nombre d'algorithmes heuristiques et précis qui peuvent résoudre complètement certains cas avec des dizaines de milliers de villes, et même des problèmes avec des millions de villes peuvent être estimés à 0,05% près . Le lien indiqué contient des tentatives de résolution pour une instance de 1 904 711 villes de la Terre à partir de la base de la National Geographical Society.


Base de la National Geographical Society de 1 904 711 villes

À l'heure actuelle, le record de la distance minimale pour les villes de la Terre est de 7 515 772 107 km, il a été établi le 13 mars 2018 à l'aide de l'algorithme heuristique LKH .

Le problème classique des vendeurs en informatique est utilisé comme référence pour les algorithmes d'optimisation.

Les amibes sont des organismes unicellulaires qui n'ont aucune idée de la complexité de l'optimisation combinatoire. Ils n'ont rien qui ressemble à distance au système nerveux central, ce qui les rend moins aptes à résoudre des problèmes d'une telle complexité. Cependant, des chercheurs japonais ont découvert qu'un certain type d'amibe peut être utilisé pour calculer des solutions quasi optimales au problème des vendeurs ambulants dans huit villes.


Selon un article scientifique , une amibe appelée Physarum polycephalum , qui avait précédemment été utilisée comme ordinateur biologique dans plusieurs autres expériences, a participé aux expériences. Cette créature est considérée comme particulièrement utile en informatique biologique car elle peut étendre diverses zones de son corps à la recherche d'un moyen plus efficace d'obtenir de la nourriture et elle déteste la lumière.

Pour transformer ce mécanisme naturel de nutrition en ordinateur, des chercheurs japonais ont placé l'amibe sur une plaque spéciale à 64 canaux, dans le sens où l'animal pouvait étirer le corps. Amoeba essaie constamment d'élargir le corps pour couvrir la plus grande surface possible de la plaque nutritive. Néanmoins, chaque canal de la plaque peut être éclairé, ce qui amène l'amibe à sortir de ce canal d'une sensation d'aversion pour la lumière.

Pour simuler le problème des vendeurs ambulants, chacun des 64 canaux de la plaque s'est vu attribuer un code de ville entre A et H, en plus d'un numéro de 1 à 8, qui indique l'ordre des villes (l'ordre des villes correspond à l'ordre dans lequel elles ont été visitées par le vendeur).

Pour programmer l'amibe, les chercheurs ont utilisé un réseau de neurones qui comprenait des données sur la position actuelle de l'amibe et la distance entre les villes pour éclairer des canaux spécifiques. Le réseau de neurones était plus susceptible d'éclairer les villes (canaux) avec de plus grandes distances entre elles.

Lorsque l'algorithme et l'amibe interagissent, ce dernier prend une forme qui représente des solutions approximatives au problème du voyageur de commerce. Plus intéressant encore, le temps qu'il faut à l'amibe pour obtenir ces solutions presque optimales croît de façon linéaire , bien que le nombre d'options de solution augmente de façon exponentielle . Dans un avenir proche, les chercheurs vont fabriquer des puces avec des dizaines de milliers de canaux afin que l'amibe puisse essayer de résoudre le problème des vendeurs ambulants dans des centaines de villes.

L'article scientifique a été publié le 19 décembre 2018 dans la revue Royal Society Open Science (doi: 10.1098 / rsos.180396).