Ameby w biokomputerze. Rozwiązały problem komiwojażera

Naukowcy wykazali, że ameba - jednokomórkowy organizm - ma wyjątkowe możliwości obliczeniowe, które pewnego dnia mogą stanowić alternatywę dla metod stosowanych w konwencjonalnych komputerach. Badacze pod kierownictwem Masashi Aono na japońskim Uniwersytecie Keio wybrali amebę, aby rozwiązać problem z Traveling Salesman (TSP). TSP jest problemem optymalizacyjnym, w którym celem jest znalezienie najkrótszej trasy między kilkoma miastami, tak aby każde miasto było odwiedzane dokładnie raz, a punkty początkowe i końcowe były takie same. Ten niezwykły eksperyment został opisany w artykule opublikowanym w tym tygodniu w prestiżowym magazynie Royal Society Open Science.

Japoński badacz ułożył amebę na specjalnej płytce, która otoczona była 64 kanałami, w które ameba może wsunąć swoje ciało. Płytkę tę następnie umieszcza się na pożywce bogatej w składniki odżywcze.

Problem komiwojażera (ang. travelling salesman problem, TSP) to zagadnienie optymalizacyjne. Nazwa pochodzi od typowej ilustracji problemu, przedstawiającej go z punktu widzenia wędrownego sprzedawcy (komiwojażera): dane jest n miast, które komiwojażer ma odwiedzić, oraz odległość / cena podróży / czas podróży pomiędzy każdą parą miast. Celem jest znalezienie najkrótszej / najtańszej / najszybszej drogi łączącej wszystkie miasta, zaczynającej się i kończącej się w określonym punkcie. Główną trudnością problemu jest duża liczba danych do analizy. Problem komiwojażera jest uważany za "NP trudny", co oznacza, że ​​złożoność obliczania poprawnego rozwiązania wzrasta wykładniczo, m więcej miast jest dodawanych do zbioru. Na przykład istnieją tylko trzy możliwe rozwiązania, jeśli mamy cztery miasta, ale mamy już 360 ​​możliwych rozwiązań, jeśli obliczamy podróż między sześcioma miastami. W przypadku ośmiu miast liczba możliwych tras wzrasta do 2520.

Elon Musk: niedługo Neuralink połączy mózg z komputerem

W nowym badaniu naukowcy odkryli, że ameba może znaleźć prawie optymalne rozwiązania TSP w czasie, który rośnie tylko liniowo gdy ilość miast rośnie z czterech do ośmiu. Naukowcy twierdzą wręcz, że "urządzenia i architektury obliczeniowe inspirowane rozwiązaniami znanymi z biologii, uzupełnią i w niektórych przypadkach przewyższą konwencjonalne technologie rozwiązywania trudnych obliczeniowo problemów. Dzieje się tak ze względu na na zdolność żywych organizmów do podejmowania właściwych decyzji w niepewnych środowiskach oraz tendencje do zmniejszania zużycia energii". Naukowcy badają amebę Physarum polycephalum wybraną do tego celu ze względu na jej intrygujące zdecentralizowane możliwości obliczeniowe. Ciało ameby zmienia się by wybrać optymalną trasę pośród źródeł żywności, tworzy regularne schematy i przewiduje okresowe wydarzenia. Wybranie najlepszej trasy poprawnie i szybko jest podstawową umiejętnością żywych organizmów, która odpowiada rozwiązywaniu trudnych obliczeniowo problemów. Ameba może rozciągać różne rejony swojego ciała, aby znaleźć najskuteczniejszą drogę do źródła pożywienia. Jednokomórkowy Physarum polycephalum poszukuje rozwiązania problemu komiwojażera (TSP) poprzez zmianę swojego kształtu, tak aby zminimalizować ryzyko narażenia się na bodźce świetlne. Światła bowiem te organizmy wyjątkowo nie lubią.

Szef BlackBerry ostrzega przed komputerami kwantowymi

Japoński badacz umieścił amebę na specjalnej płytce, która otoczona była 64 kanałami, w które ameba może wsunąć swoje ciało. Płytkę tę następnie układa się na pożywce bogatej w składniki odżywcze. Ameba stara się wydłużyć swoje ciało, aby pokryć jak największą część płytki i wchłonąć składniki odżywcze. Jednak każdy kanał może być także oświetlony, co powoduje wycofanie się ameby z tej części płytki. Aby modelować problem komiwojażera, każdemu z 64 kanałów na tabliczce przypisano kod miasta między literami A i H oraz liczbę od 1 do 8, która wskazuje kolejność miast. Na przykład, jeśli ameba rozszerzy swoje ciało na kanały A3, B2, C4 i D1, właściwym rozwiązaniem dla problemu komiwojażera będzie D, B, A, C, D. D1 wskazuje, że D powinno być pierwszym miastem w planie handlowca, B2 oznacza, że ​​B powinno być drugim miastem i tak dalej.

Kryptografia odporna na kwantowe komputery powstanie za 20 lat

Aby poprowadzić amebę w kierunku rozwiązania problemu komiwojażera, naukowcy wykorzystali sieć neuronową, która rejestruje dane o aktualnej pozycji ameby i odległości między miastami. Kiedy algorytm manipuluje mikroprocesorem, na którym znajduje się ameba, w zasadzie zachęca ją do przyjmowania form reprezentujących przybliżone rozwiązania problemu komiwojażera. Ogólnie rzecz biorąc, modelowanie TSP z amebą wykorzystuje naturalną tendencję tego organizmu do poszukiwania stabilnej równowagi. Aby poprowadzić amebę w kierunku optymalnego lub prawie optymalnego rozwiązania, kluczem jest kontrolowanie światła. Sieć neuronowa została zaprojektowana w taki sposób, że częściej wybiera oświetlenie tych miast, które są bardziej od siebie oddalone. Ponieważ kanały reprezentujące krótsze trasy są rzadziej oświetlane, ameba może rozprzestrzeniać się w tych kanałach i kontynuować eksplorację innych nieoświetlonych kanałów w celu maksymalizacji pola powierzchni na płytce.

Stephen Hawking w najnowszej książce ostrzega przed superludźmi

Naukowcy opracowali również symulację komputerową o nazwie AmoebaTSP, która naśladuje niektóre z głównych cech tego, w jaki sposób ameba rozwiązuje problem, w tym ciągły ruch, który ma stałą prędkość i jest równy dla różnych kanałów. Na razie jednak eksperyment japońskich badaczy pozostaje w laboratorium, ale stanowi podstawę dla niskoenergetycznych komputerów biologicznych, które wykorzystują naturalne mechanizmy ameb i innych mikroorganizmów do obliczania. W przyszłości naukowcy planują dalsze ulepszanie zdolności obliczeniowych ameby. Mają nadzieję, że będzie możliwe wyprodukowanie chipów zawierających dziesiątki tysięcy kanałów, dzięki czemu ameba będzie w stanie rozwiązać problemy z handlowcami, które dotyczą setek miast.