Das neuronale Netz mit einer Amöbe löste das Problem der Handlungsreisenden für 8 Städte

Lösungen des Problems des Handlungsreisenden, das durch ein Amöben-basiertes Computersystem erhalten wird. Beispiele für Verkäufertouren in vier, fünf, sechs, sieben und acht Städten, die in Experimenten erhalten wurden, bei denen jede Tour auf den entsprechenden Kanälen aus der rechten Abbildung rot dargestellt ist. Die linken Felder zeigen die Durchlichtbilder der Ausgangszustände (

Eine Gruppe japanischer Forscher von der Keio-Universität in Tokio hat gezeigt, dass Amöben in der Lage sind, ungefähre Lösungen für ein überraschend komplexes mathematisches Problem zu generieren, das als Problem des Handlungsreisenden bekannt ist .

Die Aufgabe des Verkäufers ist eine der bekanntesten kombinatorischen Optimierungsaufgaben, die darin besteht, die rentabelste Route zu finden, die mindestens einmal durch diese Städte führt und dann in die ursprüngliche Stadt zurückkehrt.

Die Optimierungsaussage des Problems gehört jedoch wie die meisten seiner Sonderfälle zur Klasse der NP-harten Probleme. Die Version des „Entscheidungsproblems“ (dh die, bei der die Frage aufgeworfen wird, ob die Route nicht länger als der angegebene Wert von k existiert) gehört zur Klasse der NP-vollständigen Probleme.

Die Schwierigkeit, die richtige Lösung zu berechnen, nimmt exponentiell zu, wenn mehr Städte zur Aufgabe hinzugefügt werden. Zum Beispiel gibt es für vier Städte drei Lösungen und für sechs Städte - 360. In Zukunft setzt sich das exponentielle Wachstum fort.

Trotz des großen Rechenaufwands gibt es eine große Anzahl heuristischer und genauer Algorithmen, die einige Fälle mit Zehntausenden von Städten vollständig lösen können, und selbst Probleme mit Millionen von Städten können innerhalb von 0,05% angenähert werden . Der angegebene Link enthält Versuche, eine Instanz von 1.904.711 Städten der Erde von der Basis der National Geographical Society aus zu lösen.


Basis der National Geographical Society von 1.904.711 Städten

Derzeit beträgt der Rekord für die Mindestentfernung für die Städte der Erde 7 515 772 107 km. Er wurde am 13. März 2018 mithilfe des heuristischen LKH- Algorithmus festgelegt.

Das klassische Verkäuferproblem in der Informatik wird als Benchmark für Optimierungsalgorithmen verwendet.

Amöben sind einzellige Organismen, die keine Ahnung von der Komplexität der kombinatorischen Optimierung haben. Sie haben nichts, was dem Zentralnervensystem auch nur annähernd ähnelt, was sie zu weniger geeigneten Kandidaten für die Lösung von Problemen dieser Komplexität macht. Japanische Forscher haben jedoch herausgefunden, dass eine bestimmte Art von Amöbe verwendet werden kann, um nahezu optimale Lösungen für das Problem der reisenden Verkäufer für acht Städte zu berechnen.


Einem wissenschaftlichen Artikel zufolge nahm eine Amöbe namens Physarum polycephalum , die zuvor in mehreren anderen Experimenten als biologischer Computer verwendet worden war, an den Experimenten teil. Diese Kreatur wird im biologischen Rechnen als besonders nützlich angesehen, da sie verschiedene Bereiche ihres Körpers auf der Suche nach einem effizienteren Weg zur Nahrungsaufnahme erweitern kann und das Licht hasst.

Um diesen natürlichen Ernährungsmechanismus in einen Computer umzuwandeln, platzierten japanische Forscher die Amöbe auf einer speziellen Platte mit 64 Kanälen, in deren Richtung das Tier den Körper dehnen konnte. Amöbe versucht ständig, den Körper zu erweitern, um den größtmöglichen Bereich der Nährstoffplatte abzudecken. Trotzdem kann jeder Kanal in der Platte beleuchtet werden, wodurch die Amöbe aus einem Gefühl der Abneigung gegen Licht aus diesem Kanal austritt.

Um das Problem des Handlungsreisenden zu simulieren, wurde jedem der 64 Kanäle auf dem Schild ein Stadtcode zwischen A und H zugewiesen, zusätzlich zu einer Zahl von 1 bis 8, die die Reihenfolge der Städte angibt (die Reihenfolge der Städte entspricht der Reihenfolge, in der sie vom Verkäufer besucht wurden).

Um die Amöbe zu programmieren, verwendeten die Forscher ein neuronales Netzwerk, das Daten zur aktuellen Position der Amöbe und zur Entfernung zwischen Städten enthielt, um bestimmte Kanäle zu beleuchten. Das neuronale Netz beleuchtete eher Städte (Kanäle) mit größeren Entfernungen zwischen ihnen.

Wenn der Algorithmus und die Amöbe interagieren, nimmt letztere eine Form an, die ungefähre Lösungen für das Problem des Handlungsreisenden darstellt. Interessanterweise wächst die Zeit, die die Amöbe benötigt, um diese nahezu optimalen Lösungen zu erhalten, linear , obwohl die Anzahl der Lösungsoptionen exponentiell zunimmt. In naher Zukunft werden Forscher Chips mit Zehntausenden von Kanälen herstellen, damit die Amöbe versuchen kann, das Problem der reisenden Verkäufer in Hunderten von Städten zu lösen.

Der wissenschaftliche Artikel wurde am 19. Dezember 2018 in der Zeitschrift Royal Society Open Science (doi: 10.1098 / rsos.180396) veröffentlicht.