amibe-problème-du-voyageur
Une équipe de chercheurs japonais de l’Université Keio à Tokyo a démontré qu’une amibe est capable de générer des solutions approximatives à un problème mathématique extrêmement difficile, connu sous le nom de «problème du voyageur de commerce».

Un ordinateur basé sur une amibe

Le problème du vendeur voyageur se présente comme suit: étant donné le nombre arbitraire de villes et les distances qui les séparent, quel est le chemin le plus court qu’un vendeur peut emprunter pour se rendre dans chaque ville et revenir à sa ville d’origine. C’est un problème classique en informatique qui sert de test de référence pour l’optimisation des algorithmes.
Le problème du voyageur de commerce est considéré comme « NP hard », ce qui signifie que la complexité de calculer une solution correcte augmente de façon exponentielle, plus le nombre de villes ajoutées au problème augmente. Par exemple, il n’y a que trois solutions possibles s’il y a quatre villes, mais il y a 360 solutions possibles s’il y a six villes – ce problème continu d’augmenter de façon exponentielle.
Malgré l’augmentation exponentielle de la difficulté de calcul avec chaque ville ajoutée à l’itinéraire du vendeur, les informaticiens ont été en mesure de calculer la solution optimale à ce problème pour des milliers de villes depuis le début des années 90 et les récents efforts ont permis de calculer des solutions presque optimales pour des millions de villes.
Les amibes sont des organismes unicellulaires qui ne ressemblent en rien à un système nerveux central, ce qui les fait paraître comme des candidats peu aptes à résoudre un problème aussi complexe. Pourtant, comme l’ont démontré ces chercheurs japonais, un certain type d’amibe peut être utilisé pour calculer des solutions presque optimales au problème du voyageur dans huit villes au maximum.

Transformer ce mécanisme en ordinateur

Encore plus remarquable, le temps nécessaire à l’amibe pour obtenir ces solutions presque optimales augmente de façon linéaire, même si le nombre de solutions possibles augmente de manière exponentielle.
Comme détaillé dans un article publié cette semaine dans la Royal Society Open Science, l’amibe utilisée par les chercheurs s’appelle Physarum polycephalum, qui a été utilisée comme ordinateur biologique dans plusieurs autres expériences. La raison pour laquelle cette amibe est considérée comme particulièrement utile en informatique biologique est qu’elle peut étendre diverses régions de son corps pour trouver le moyen le plus efficace de se procurer de la nourriture.
Pour transformer ce mécanisme d’alimentation naturel en ordinateur, les chercheurs japonais ont placé l’amibe sur une assiette spéciale dotée de 64 canaux lui permettant d’étendre son corps. Cette plaque est ensuite placée sur un milieu riche en nutriments. L’amibe tente d’étendre son corps pour couvrir autant que possible la plaque et absorber les nutriments. Cependant, chaque canal de la plaque peut être illuminé, ce qui amène l’amibe à avoir une aversion de lumière et à se rétracter de ce canal.

Modéliser ce problème

Pour modéliser ce problème du voyageur de commerce, un code de ville entre A et H a été affecté à chacun des 64 canaux de la plaque, en plus d’un nombre compris entre 1 et 8 – indiquant l’ordre des villes. Ainsi, par exemple, si l’amibe s’étendait dans les canaux A3, B2, C4 et D1, la solution correcte au problème du voyageur serait D, B, A, C, D. La raison en est que D1 indique que D devrait être la première ville de l’itinéraire du vendeur, B2 indique que B devrait être la deuxième ville, A3 que A devrait être la troisième ville, etc.
Pour orienter l’amibe vers une solution au problème du voyageur, les chercheurs ont utilisé un réseau de neurones qui incorporerait des données sur la position actuelle de l’amibe et la distance entre les villes pour éclairer certains canaux. Le réseau de neurones a été conçu de sorte que les villes séparées par des distances plus grandes soient plus susceptibles d’être éclairées que les canaux qui ne le sont pas.
Source : Motherboard