В 2010 году исследователи из Хоккайдского университета поставили чашку Петри. На дно налили влажный агар, разложили 36 овсяных хлопьев в точках, соответствующих крупнейшим городам вокруг Токио, а кусочек слизевика поместили в центр — в точку, соответствующую Токио. Участки, соответствующие горам и водоёмам, засветили лампой — физарум избегает яркого света и сам обходил эти зоны, воспроизводя реальные географические ограничения при прокладке железных дорог.
Через 26 часов посмотрели что получилось.
Сеть из протоплазматических трубок, которую вырастил слизевик, воспроизводила топологию реальной железнодорожной сети токийской агломерации. Узел за узлом. Причём не просто воспроизводила — по трём инженерным критериям одновременно: стоимости (суммарная длина трубок), транспортной эффективности (среднее время пути между узлами) и устойчивости (сколько соединений можно убрать, прежде чем сеть развалится).
Так, а что такое физарум и почему он один
Физарум многоголовый (Physarum polycephalum) — это миксомицет, слизевик. Формально не гриб, не животное и не растение — отдельный таксон, амёбозои. В стадии плазмодия, которую используют в экспериментах, это одна-единственная клетка с миллионами ядер внутри. Синцитий. Ни мозга, ни нервной системы, ни даже отдельных клеток. Одна непрерывная цитоплазма, упакованная в общую мембрану.
Живёт в лесной подстилке, разыскивает бактерий и гниющую органику. Основная задача — найти источники питания и проложить к ним снабжающие пути как можно экономнее. Именно поэтому у него возникла способность строить эффективные сети.
Никакой переработки информации в привычном смысле нет. Только физика и химия.
Физика внутри трубок
Внутри физарума постоянно движется протоплазма — ритмичное пульсирующее течение туда-обратно. Стенки трубок сделаны из актин-миозиновых волокон — тех же белков, что сокращают мышцы. Трубки буквально сжимаются и разжимаются, перекачивая жидкость.
Тут ключевой момент.
Поток жидкости через цилиндрическую трубку описывается уравнением Хагена-Пуазейля. Объёмный расход пропорционален четвёртой степени радиуса: Q ∝ r4. Удвоить диаметр трубки — значит увеличить поток через неё в шестнадцать раз.
Из этого вырастает положительная обратная связь. Где поток сильнее — там стенки трубки испытывают большее напряжение сдвига, активнее реагируют, и трубка утолщается. Толстая трубка пропускает ещё больше потока. Тонкие трубки, через которые почти ничего не течёт, постепенно атрофируются и рассасываются.
Никакого центрального управления. Каждый участок трубки реагирует только на то, что происходит в нём прямо сейчас. Глобальная оптимальная сеть возникает как результат этих локальных правил.
Лабиринт, 2000 год
Тосиюки Накагаки — биолог из Хоккайдского университета, специалист по самоорганизации живых систем. В 2000 году вместе с Хироясу Ямадой и Аготой Тот опубликовал в журнале Nature статью «Решение лабиринтов амёбоидным организмом».
Эксперимент, собственно, элементарный — лабиринт из пластиковой плёнки на агаровой пластине, овсяные хлопья в двух точках — на входе и выходе. Физарум сначала заполняет весь лабиринт, потом начинает отступать из тупиковых ветвей и постепенно стягивается в единственную трубку — ту, что соединяет два источника пищи по наикратчайшему пути.
Статья получила широкое внимание, потому что показала: поиск кратчайшего пути — задача, для которой мы пишем алгоритмы и прогоняем их на процессорах — решается одноклеточным без какого-либо вычисления в привычном смысле слова.
Токийская агломерация, 2010 год
Ацуси Теро — математик из Хоккайдского университета, работавший совместно с группой Накагаки. Сейчас доцент Кюсюского университета. В 2010 году в журнале «Наука» (Science, т. 327, с. 439-442) его группа опубликовала результаты эксперимента с картой Токио.
Слизевику не давали карту метро. Ему дали только хлопья и световые барьеры. Форма сети возникла сама.
Чтобы оценить результат, исследователи сравнили сеть физарума с реальной сетью по трём критериям. Стоимость — суммарная длина всех трубок против суммарной длины всех линий метро. Эффективность — среднее время пути между двумя случайными узлами. Устойчивость — насколько связность сети снижается при выходе из строя одного соединения.
По всем трём показателям сеть физарума оказалась сопоставима с реальной токийской системой. Слизевик нашёл разумный компромисс между тремя критериями, которые тянут в разные стороны: минимальная стоимость требует как можно меньше трубок, высокая эффективность требует прямых соединений везде, высокая устойчивость требует избыточных петель на случай отказа. Японские инженеры решали этот компромисс десятилетиями.
И, как мы уже писали выше, физарум решил его за 26 часов.
Теро с коллегами формализовали правила физарума в виде системы дифференциальных уравнений. В центре — то самое уравнение Хагена-Пуазейля плюс правило адаптации диаметра трубки в ответ на поток. Получился алгоритм, который в литературе называют физарум-вдохновлённым.
Алгоритм применяли к задачам Штейнера — соединить несколько точек минимальной суммарной длиной кабеля или трубопровода. Это NP-трудная задача, и точных решений для больших экземпляров нет. Алгоритм физарума находит хорошие приближения быстро и без глобального планирования. Его тестировали на задачах проектирования транспортных сетей, оптимизации цепочек поставок и маршрутизации в сенсорных сетях.
К сожалению, есть ограничение. Увы, настоящий физарум работает в двух измерениях и нуждается во влажной среде. Это аналоговый решатель конкретного класса задач, не компьютер общего назначения. Алгоритм переносится в любую среду, биологический оригинал — нет.
Инетерсные статьи
https://habr.com/ru/companies/sberbank/articles/1071036/
ссылка на оригинал статьи https://habr.com/ru/articles/1074296/