Слизоподібний черв’як: Клітина без мозку, що будує залізничні мережі

Jedna gigantična komorka, без нервової системи

Physarum polycephalum не є грибом, рослиною чи твариною — це пустинне слизне міцелій, одна клітина, яка може рости і покривати тарілку для вечері, містить мільйони ядер, що діляться за допомогою спільного цитоплазму, без внутрішніх клітинних стін. У ньому немає мозку, нервів або м'язів у тій самій формі, що й у тваринах. Проте, коли він досліджує, він робить щось, що на диво схоже на планування: він розповсюджується від джерела їжі, досліджує в усіх напрямках, потім відтягується від неефективних гілок і посилює ті, які працюють, поки не залишиться струнка, ефективна мережа, що з'єднує всі знайдені джерела їжі.

Відчуття, рух, відкладення: вся система правил

Обчислювальний модель, яка відтворює цю поведінку, розроблена Джефом Джоузом у 2010 році, не моделює внутрішівну біохімію організму. Замість цього Physarum представляється тисячами незалежних агентів частинок, які рухаються по спільній 2D трасі. Кожен агент виконує три кроки на кожному циклі:

1. ВІДЧУВАННЯ – читає трасу на трьох точках попереду агента: передньо-ліва, прямо перед, передньо-права (фікльований кут датчика та відстань від поточної орієнтації агента) 2. ПОЛІТ – повертається до того датчика, який читає найвищий рівень траси; якщо прямо перед є найвищим, продовжує рухатися; якщо нічого не виділяється, повертається на невелику випадкову кількість 3. РУХ + ВІДЛОЖЕННЯ – робить крок вперед і залишає хімічний слід у новій позиції; кожна клітина поля згасає та трохи розсіюється на кожному циклі Це вся алгоритм. Жоден агент не знає, де знаходиться будь-який джерело їжі, скільки інших агентів існує або який вигляд матиме мережа в кінці. Поведінка є стегіргічною – координація відбувається повністю через спільне середовище, трасову площину, а не шляхом прямого спілкування. Агент, який випадково натрапляє на джерело їжі, залишає там слід; сусідні агенти відчувають цей слід і тягнуться до нього, створюючи позитивний зворотний зв’язок, який перетворює один випадковий вдалий шлях на добре зношену дорогу, тоді як шляхи, які ніхто не підтримує, просто згасають, оскільки поле згасає та розсіюється трохи на кожному циклі.

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

Чому мережа залишається ефективною, а не просто підключеною

Наївний алгоритм заповнення (flood-fill) також з’єднував би усі джерела їжі, але з густим і марним вузлом шляхів. Що робить закономірність Physarum цікавою, полягає в тому, що розклад активізує видалення надлишкових зв’язків: шлях, який дещо коротший за альтернативу, накопичує сліди трохи швидше, виграє більше трафіку агента, і програшний шлях зникає, оскільки нічого не підтримує його далі. Організм не обчислює найкоротший шлях у графі-теоретичному сенсі — він ніколи не бачить графа — але боротьба між розкладанням та посиленням діє як розподілений оптимізатор, який збігається до чогось близького до мінімального дерева витрат, і це відбувається безперервно та адаптивно, коли з’являються або зникають джерела їжі.

Експеримент з мережею Токійського залізничного транспорту

Найвідоміший приклад цього було дослідження 2010 року, проведене Atsushi Tero та його колегами, опубліковане в журналі Science. Дослідники розмістили овес – улюблений корм Physarum – на вологому покритті у точному географічному розташуванні міст Великого Токіо, з путочом від позиції центрального Токіо. Протягом приблизно одного дня слизний мох сформував мережу, яка з’єднувала овес і що відповідала реальній залізничній систем Токіо: порівнянна загальна довжина, порівняна ефективність транспорту та порівняна стійкість до відмов, тобто мережа витримала втрату окремих зв'язків приблизно так само добре, як і справжня залізниця. Жоден інженер не проєктував цю мережу; вона виникла в результаті циклу «відчуття – перетворення – відкладання», що працює на субстраті, який не знав про те, що вирішує транспортну проблему.

Від біології до алгоритму

Оскільки модель дуже дешева для симуляції та виробляє органічні, розгалужені, стійкі до збоїв структури, алгоритм ‘Physarum’ добре сприйнято за межами біології. Його використовували для наближення рішень проблем проектування мереж і найкоротших шляхів, для створення процедурних мереж доріг та рік у іграх та програмному забезпеченні для візуалізації, а також як фізично обґрунтована альтернатива більш жорстким алгоритмам графа, коли метою є мережа, яка поступово деградує, а не така, що доводиться непростою, але доведеною оптимальною.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Slime Mold Network (Physarum) і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.