Zmniejszające się Blob Computes Traveling Salesman Solutions

Problem komiwojażera to jedno z bardziej znanych wyzwań matematycznych. To problem ze znalezieniem najkrótszej drogi na jednokrotne zwiedzenie kilku miast, a następnie powrót do miejsca pochodzenia.

Oczywiście łatwo jest znaleźć trasy, które w ten sposób odwiedzają każde miasto. Wielkim wyzwaniem jest znalezienie najkrótszego.

Jest jeden bezpieczny sposób na zrobienie tego - czystą brutalną siłą. Oznacza to mierzenie długości każdej trasy i ustalenie, która jest najkrótsza. Problem w tym, że zadanie to wydłuża się wraz ze wzrostem liczby miast. Rzeczywiście, w przypadku dużej liczby miast jest to niewykonalne obliczeniowo.

Łatwo sobie wyobrazić, że może istnieć jakiś sprytny matematyczny skrót, który rozwiąże ten problem. Bynajmniej. W rzeczywistości matematycy zwykle zgadzają się, że nigdy nie uda się znaleźć ogólnego skrótu (jest to tak zwana debata P=NP).

Zamiast tego muszą polegać na procesach optymalizacyjnych, które szukają krótkich rozwiązań, ale nie są w stanie udowodnić, że rzeczywiście są one najkrótsze.

Tak więc wyzwaniem dla wszystkich celów praktycznych jest znalezienie algorytmów, które dają dobre wyniki i są wydajne obliczeniowo.

Dziś Jeff Jones i Andrew Adamatzky z University of the West of England w Wielkiej Brytanii ujawniają niezwykłe podejście. Ci faceci twierdzą, że rozsądne rozwiązanie można znaleźć, przedstawiając miasta jako serię kropek na wirtualnej szalce Petriego, zanurzając kropki w blobie wirtualnej mazi, a następnie zmniejszając blob.

W uproszczeniu, kropelka przylega do kropek, gdy się kurczy, łącząc je z minimalną powierzchnią, przypominającą powierzchnię bańki mydlanej. Mówią, że w miarę jak plama się kurczy, morfologicznie dostosowuje się do konfiguracji miast.

Kiedy wszystkie kropki leżą na powierzchni plamy, uzyskana powierzchnia jest rozwiązaniem problemu komiwojażera, który ogólnie jest całkiem niezły.

Magicznym składnikiem tego wszystkiego jest specjalna maź. Składa się z wielu cząstek, z których każda porusza się zgodnie z zestawem prostych zasad, jak autonomiczne agenty. Znajdują się one w morzu chemoatraktantów, wirtualnym zapachu, do którego przyciągane są cząsteczki. Na każdym etapie obliczeń każda cząsteczka wyczuwa otaczający ją chemoatraktant, a następnie przemieszcza się w kierunku obszaru o najwyższym stężeniu. Gdy się porusza, pozostawia po sobie ślad chemoatraktantu, za którym podążają inne cząsteczki.

Rezultatem jest rodzaj inteligentnej plamy, która wykazuje wyłaniające się zachowanie, takie jak zdolność do minimalizowania swojej powierzchni.

Jones i Adamatzky sprawdzili tę inteligentną mazię, stawiając ją na przegranej z problemami komiwojażerów, składającymi się z 20 losowo rozmieszczonych miast na wirtualnej szalce Petriego. Umieścili filmy z procesu kurczenia się tutaj .

Wyniki są dobre, ale nie doskonałe. Stworzyliśmy 20 różnych scenariuszy 20 miast i uruchomiliśmy bloba 6 razy w każdym. Następnie porównali najkrótszą trasę kropelki z rzeczywistą najkrótszą ścieżką znalezioną przez brutalną siłę. Jones i Adamatzky twierdzą, że jeśli ta najkrótsza trasa ma długość 1, inteligentny obiekt typu blob znalazł trasy o średniej najlepszej długości trasy wynoszącej 1,04, średniej długości trasy wynoszącej 1,07 i średniej najgorszej długości trasy wynoszącej 1,09.

To nie jest złe. Jednak prawdziwą zaletą jest prostota podejścia, które jest zasadniczo wyłaniające się i nie wymaga specjalnych procesów optymalizacyjnych. Tworzy również mapę trasy na końcu (chociaż potrzebna jest pewna ludzka interpretacja, aby to zrozumieć).

Oczywiście są wady. Są pewne konfiguracje miast, z którymi blob sobie nie radzi. Dzieje się tak, gdy najkrótsza trasa tworzy rodzaj cieśniny między dwoma miastami, a nie połączenie, jak Cieśnina Gibraltarska między Oceanem Atlantyckim a Morzem Śródziemnym. Zamiast tego plamka ma tendencję do ich łączenia.

Niemniej jednak jest to interesująca forma niekonwencjonalnych obliczeń, która stanowi fascynującą alternatywę dla konwencjonalnych algorytmów komiwojażera. Jest najbardziej podobny do podejść z gumką, które otaczają miasta gumką, a następnie stopniowo próbują rozciągać pasy, aby połączyć miasta w ich obrębie. Duża różnica polega na tym, że właściwości materiału plamki są wyłaniające się, a nie zaprogramowane.

Jones i Adamatzky twierdzą, że następnym krokiem byłoby stworzenie fizycznego modelu tego układu, w którym pracę wykonuje prawdziwa kropla, być może przy użyciu lepkosprężystej minimalizacji swobodnej energii. Zaprojektowanie takiego materiału może jednak być trudne.

Innym podejściem, które mogłoby mieć szersze zastosowanie, byłoby wydestylowanie właściwości tego niekonwencjonalnego obliczenia w klasyczny algorytm.

Najlepszą ze wszystkiego jest perspektywa menedżerów logistyki planujących trasy dostaw poprzez zanurzanie modeli sieci drogowej w kadziach inteligentnej mazi. Poczekamy więc z niecierpliwością na tę nową naukę o alchemii komiwojażera.

Nr ref.: arxiv.org/abs/1303.496 : Obliczenie problemu komiwojażera przez kurczącego się bloba

ukryć