Głaz: Brainless Oorganizm Budujący Sieci Transportowe

Jedna ogromna komórka, bez układu nerwowego

Physarum polycephalum nie jest grzybem, rośliną ani zwierzęciem — to glaz plazmowy, jedna komórka, która może rosnąć i pokryć talerz posiłku, zawierając miliony nukleów dzielących się wspólnym cytoplasmem bez wewnętrznych komórkowych ścian. Nie ma u niego mózgu, nerwów ani mięśni w znaczeniu zwierzęcym. Jednak podczas forageowania robi coś, co wydaje się nieco przypominać planowanie: rozrasta się wzdłuż źródła pokarmu, eksploruje wszystkie kierunki, a następnie cofa się od niewykorzystanych gałęzi i zwiększona jest ta, które działają, aż reszta stanowi efektywną sieć łączącą każde znalezione źródło pokarmu.

Zmysłowość, poruszanie się i wykłady: cała zasada działania

Model obliczeniowy, który powtarza to zachowanie, opracowany przez Jeffa Jonesa w 2010 roku, nie symuluje biochemii organizmu w żadnym stopniu. Zamiast tego przedstawia Głazu jako tysiące niezależnych agentów cząsteczkowych poruszających się po wspólnej poli dwuwymiarowej ścieżkowej. Każdy agent wykonuje trzy kroki na każdym ticku:

1. Zmysłowość -- czyta pole ścieżek w trzech punktach przed sobą: bokiem do przodu lewo, prosto naprzód, bokiem do przodu prawo (stały kąt i odległość czujnika z orientacji agenta na chwilę przed tickiem) 2. Obrot -- obraca się w stronę czujnika o najwyższej wartości ścieżki; jeśli prosto naprzód jest najwyższe, to kontynuuje poruszanie się; jeśli żaden nie wydaje się zauważalny, obraca się małą losową ilością 3. Poruszanie się + Wykłady -- przesuwa się do przodu i upuszcza chemiczne wykłady na nowym pozycji; każda komórka pola zdecremuje i rozprzestrzeni się nieco na każdym ticku To jest cała algebra. Nikt z agentów nie wie, gdzie znajduje się żadna źródło jedzenia, ile istnieje innych agentów, ani w jakim kształcie będzie mieć końcowy siatka. Zachowanie to jest stigmergiczne — koordynacja dzieje się całą porą poprzez współdzielone środowisko, pole ścieżek, a nie bezpośrednio komunikację. Agent, który przypadkowo wędruje w kierunku źródła jedzenia, upuszcza tam wykłady; bliskie agenty odczuwają te wykłady i są przyciągane do nich również, tworząc pętlę zwracającą się na siebie, która zmienia pojedynczy szczęśliwy ścieżkę w dobrze wygrzewaną drogę, podczas gdy ścieżki, które nikt nie potwierdza, po prostu zgaszczą się ze zdekrementowaniem pola.

1. SENSE  -- read the trail field at three points ahead of the agent:
            front-left, straight-ahead, front-right (a fixed sensor angle
            and distance from the agent's current heading)
2. TURN   -- rotate toward whichever sensor reads the highest trail value;
            if straight-ahead is highest, keep going; if none stand out,
            turn by a small random amount
3. MOVE + DEPOSIT -- step forward and drop trail chemical at the new
            position; every cell of the field decays and diffuses a
            little each tick

Dlaczego sieć pozostaje efektywna, nie tylko połączona

Próba naiwnej wypełniania powodowałaby połączenie wszystkich źródeł pokarmu, ale za pomocą gęstej, ścieżkowej i odpadliwej sieci. To, co sprawia, że wzór Physarum jest interesujący, to aktywne uszczuplanie nadmiernych połączeń: ścieżka, która jest tylko nieco krótsza od alternatywy, zasila się drogą o niewielkim więcej, wygrywa większą część ruchu agentów, a przegranym połączeniem przerasta się ze względu na to, że już nie ma niczego, co ją wspiera. Organizm nie oblicza najkrótszej ścieżki w sensie teoretycznym grafowym — nigdy nie widzi grafu — ale uszczuplanie-zwrotem-reinforcement działa jako rozproszonego optymalizatora, który konverguje ku czemuś bliskiemu do drzewa o najmniejszej kosztowności, i robi to ciągle i adaptacyjnie, gdy pojawiają się lub znikają źródła pokarmu.

Eksperyment z siecią kolejową w Tokio

Najbardziej znane wykazanie tego faktu pochodzi z badania prowadzonego w 2010 roku przez Atushi Tera, opublikowanego w czasopiśmie Science. Badacze umieszczyli kawałki owoców trąci —Physarum'ovo ulubione jedzenie— na wilgotnej powierzchni położonej w exact geograficznym układzie miast wokół Wielkiego Tokio, z plazmodium zaczynającym się w pozycji centralnego Tokio. Po około dniu glizma rozwijała sieć łącząca kawałki owoców, która nieco podobnie odzwierciedlała rzeczywistą system kolejowy w Tokio: porównywalna długość łącz, porównywalny efektywność transportu i porównywalna wytrzymałość, co oznacza, że sieć przetrwała symulowaną stratę pojedynczych połączeń tak dobrze jak rzeczywisty system kolejowy. Nikt nie zaprojektował tej sieci; wyrastała z exact opisanej powyżej pętli sense-turn-deposit, uruchomionej na substracie bez żadnego zrozumienia, że rozwiązuje problem transportu.

Od biologii do algorytmu

Dzięki temu, że model jest bardzo tanio symulowalny i tworzy organiczne, gałęźce podobne, wytrzymałe struktury, "algorytm Głazu" został przyjęty poza biologię. Jego zastosowania obejmują aproksymację rozwiązań dla problemów projektowania sieci i najkrótszych ścieżek, generowanie proceduralnych sieci drogowych i rzek w grach oraz w oprogramowaniu do visualizacji, a także jako motywowane przez fizykę alternatywy dla bardziej sztywnych algorytmów grafowych, gdy cel polega na budowie sieci, która degradowa się łagodnie zamiast jednej, której optimum jest dowodzone, ale jest ciepła. Najbardziej podobny do niego algorytm to kolonizacja mrakotników, który używa tych samej stigmergii opartej na ścieżkach, lecz modeluje dyskretnych agentów przemieszczających się po grafie zdefiniowanym w advanced, a nie kontynuowym polu — w przypadku Głazu grafu nie ma już od początku, on rosnie go.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Slime Mold Network (Physarum) i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.