211service.com
Shrinking Blob Computing Travelling Salesman Solutions
Das Problem des Handlungsreisenden ist eine der bekanntesten Herausforderungen in der Mathematik. Dies ist das Problem, den kürzesten Weg zu finden, um mehrere Städte einmal zu besuchen und dann zum Ausgangspunkt zurückzukehren.
Natürlich ist es einfach, auf diese Weise Routen zu finden, die jede Stadt besuchen. Die große Herausforderung besteht darin, die kürzeste zu finden.
Es gibt einen ausfallsicheren Weg, dies zu tun – durch pure rohe Gewalt. Das bedeutet, die Länge jeder Tour zu messen und herauszufinden, welche die kürzeste ist. Das Problem ist, dass diese Aufgabe mit der Zahl der Städte immer länger wird. Tatsächlich ist dies für eine große Anzahl von Städten rechnerisch nicht durchführbar.
Es ist leicht vorstellbar, dass es eine clevere mathematische Abkürzung geben könnte, die dieses Problem löst. Nicht so. Tatsächlich sind sich Mathematiker einig, dass man nie eine allgemeine Abkürzung finden wird (dies ist die sogenannte P=NP-Debatte).
Stattdessen sind sie auf Optimierungsverfahren angewiesen, die nach kurzen Lösungen suchen, aber nicht nachweisen können, dass diese tatsächlich die kürzesten sind.
Die Herausforderung für alle praktischen Zwecke besteht also darin, Algorithmen zu finden, die gute Ergebnisse liefern und recheneffizient sind.
Heute zeigen Jeff Jones und Andrew Adamatzky von der University of the West of England in Großbritannien einen ungewöhnlichen Ansatz. Diese Jungs sagen, dass eine vernünftige Lösung gefunden werden kann, indem man die Städte als eine Reihe von Punkten in einer virtuellen Petrischale darstellt, die Punkte in einen virtuellen Klecks eintaucht und dann den Klecks verkleinert.
Vereinfacht gesagt klammert sich der Klecks beim Schrumpfen an die Punkte und verbindet sie mit einer minimalen Oberfläche, ähnlich einer Seifenblasenoberfläche. Wenn der Klecks schrumpft, passt er sich morphologisch an die Konfiguration der Städte an, heißt es.
Wenn alle Punkte auf der Oberfläche des Klecks liegen, ist die resultierende Oberfläche eine Lösung für das Problem des Handlungsreisenden, die im Allgemeinen ziemlich gut ist.
Die magische Zutat bei all dem ist der besondere Glibber. Es besteht aus vielen Partikeln, die sich jeweils nach einer Reihe einfacher Regeln bewegen, wie autonome Agenten. Diese sitzen in einem Meer von Chemoattractants, einem virtuellen Duft, von dem die Partikel angezogen werden. In jeder Phase der Berechnung spürt jedes Partikel den Chemolockstoff um sich herum und bewegt sich dann in Richtung des Bereichs mit der höchsten Konzentration. Während es sich bewegt, hinterlässt es seine eigene Spur des Chemoattraktors, damit andere Partikel folgen.
Das Ergebnis ist eine Art intelligenter Blob, der emergentes Verhalten zeigt, beispielsweise die Fähigkeit, seine Oberfläche zu minimieren.
Jones und Adamatzky haben diesen intelligenten Schmierer auf Herz und Nieren geprüft, indem sie ihn bei Problemen mit Handelsreisenden verloren haben, die aus 20 Städten bestehen, die zufällig in einer virtuellen Petrischale verteilt sind. Sie haben platziert Videos vom Schrumpfprozess hier .
Die Ergebnisse sind gut, aber nicht perfekt. Die erstellten 20 verschiedene Szenarien von 20 Städten und ließen den Blob jeweils 6 Mal laufen. Dann verglichen sie die kürzeste Route des Blobs mit dem tatsächlich kürzesten Weg, der durch rohe Gewalt gefunden wurde. Jones und Adamatzky sagen, dass, wenn diese kürzeste Route die Länge 1 hat, der intelligente Blob Touren mit einer durchschnittlichen besten Tourlänge von 1,04, einer durchschnittlichen durchschnittlichen Tourlänge von 1,07 und einer durchschnittlichen schlechtesten Tourlänge von 1,09 gefunden hat.
Das ist nicht schlecht. Der wirkliche Vorteil liegt jedoch in der Einfachheit des Ansatzes, der im Wesentlichen emergent ist und keine speziellen Optimierungsprozesse beinhaltet. Am Ende wird auch eine Karte der Route erstellt (obwohl einige menschliche Interpretation erforderlich ist, um sie zu verstehen).
Es gibt natürlich Nachteile. Es gibt einige Konfigurationen von Städten, die der Blob nicht bewältigen kann. Diese treten auf, wenn die kürzeste Route eher eine Art Meerenge zwischen zwei Städten als eine Verbindung bildet, wie die Straße von Gibraltar zwischen dem Atlantik und dem Mittelmeer. Stattdessen neigt der Blob dazu, sie zu verbinden.
Dennoch ist dies eine interessante Form des unkonventionellen Computings, die eine faszinierende Alternative zu herkömmlichen Handlungsreisenden-Algorithmen darstellt. Es hat die größte Ähnlichkeit mit Gummiband-Ansätzen, die die Städte mit einem Gummiband umgeben und dann nach und nach versuchen, das Band zu dehnen, um Städte darin zu verbinden. Der große Unterschied besteht darin, dass die Materialeigenschaften des Blobs emergent und nicht vorprogrammiert sind.
Jones und Adamatzky sagen, dass der nächste Schritt darin bestehen würde, ein physikalisches Modell dieses Systems zu erstellen, in dem ein echter Klecks die Arbeit verrichtet, möglicherweise unter Verwendung der viskoelastischen Minimierung der freien Energie. Die Gestaltung eines solchen Materials kann jedoch schwierig sein.
Ein anderer Ansatz, der eine breitere Anwendung finden könnte, wäre, die Eigenschaften dieser unkonventionellen Berechnung in einen klassischen Algorithmus zu destillieren.
Das Beste von allem ist die Aussicht, dass Logistikmanager Lieferrouten planen, indem sie Straßennetzmodelle in Bottiche mit intelligenter Schmiere eintauchen. Wir werden also gespannt auf diese neue Wissenschaft der Handelsreisenden-Alchemie warten.
Ref: arxiv.org/abs/1303.4969 : Berechnung des Travelling Salesman Problems durch einen schrumpfenden Blob