Амеба находит приближенные решения NP задачи за линейное время

Исследователи продемонстрировали, что амеба — одноклеточный организм, состоящий в основном из гелеобразной протоплазмы — обладает уникальными вычислительными способностями, которые однажды могут предложить конкурентоспособную альтернативу методам, используемым в обычных компьютерах.

Ученые во главе с Масаси Аоно из Университета Кейо назначили амебу для решения задачи коммивояжера (TSP). TSP — это задача оптимизации, цель которой состоит в том, чтобы найти кратчайший маршрут между несколькими городами, чтобы каждый город посещался ровно один раз, а начальная и конечная точки совпадали.

Проблема поиска сложна, и это означает, что с ростом числа городов время, необходимое компьютеру для ее решения, растет в геометрической прогрессии. Сложность обусловлена ​​большим количеством возможных решений. Например, для четырех городов существует только три возможных маршрута. Но для восьми городов число возможных маршрутов увеличивается уже до 2520.

В новом исследовании ученые обнаружили, что амеба может найти разумные (почти оптимальные) решения для TSP за промежуток времени, который растет только линейно, так как число городов увеличивается от четырех до восьми. Хотя обычные компьютеры также могут находить приближенные решения за линейное время, подход амебы полностью отличается от традиционных алгоритмов. Как объясняют ученые, амеба исследует пространство раствора путем непрерывного перераспределения геля в его аморфном теле с постоянной скоростью, а также путем обработки оптической обратной связи параллельно, а не последовательно.

Хотя обычный компьютер все еще может решать TSP намного быстрее, чем амеба, особенно для небольших задач, новые результаты являются интригующими и могут привести к разработке новых аналоговых компьютеров, которые получают приближенные решения сложных задач гораздо больших размеров в линейной время.

Как это устроено

Специфическим типом амебы, которую использовали ученые, был плазмодий или «настоящая слизистая плесень», который весит около 12 мг и потребляет овсяные хлопья. Эта амеба постоянно деформирует свое аморфное тело, многократно подавая и удаляя гель со скоростью около 1 мм / секунду, создавая псевдоподобные придатки.

В своих экспериментах исследователи поместили амебу в центр звездчатого чипа, который представляет собой круглую пластину с 64 узкими каналами, выступающими наружу, а затем поместили чип поверх пластины с агаром. Амеба находится внутри чипа, но все еще может двигаться в 64 канала.

Чтобы максимизировать поглощение питательных веществ, амеба пытается расширяться внутри чипа, чтобы войти в контакт с как можно большим количеством агара. Однако амеба не любит свет. Поскольку каждый канал может быть избирательно освещен светом, можно заставить амебу отступить от освещенных каналов.

Чтобы смоделировать TSP, каждый канал в звездчатом чипе представляет собой упорядоченный город на маршруте продавца. Например, в случае с четырьмя городами, помеченными A-D, если амеба занимает каналы A4, B2, C1 и D3, то соответствующим решением для TSP является C, B, D, A, C.

Чтобы направить амебу к оптимальному или почти оптимальному решению, ключ заключается в управлении светом. Для этого исследователи используют модель нейронной сети, в которой каждые шесть секунд система обновляет, какие каналы подсвечиваются. Модель включает в себя информацию о расстоянии между каждой парой городов, а также обратную связь от текущей позиции амебы в каналах.

Модель гарантирует, что амеба найдет правильное решение для TSP несколькими способами. Например, как только амеба заняла определенную часть определенного канала, скажем, A3, каналы A1, A2 и все другие каналы «A» подсвечиваются, чтобы запретить посещение города A дважды. Кроме того, B3, C3, D3 и все другие «3» каналы подсвечиваются, чтобы запретить одновременные посещения нескольких городов.

Модель учитывает расстояния между городами, упрощая освещение каналов, представляющих города с более длинными расстояниями, чем с более короткими расстояниями. Например, скажем, амеба занимает канал B2 и начала вторгаться в каналы C3 и D3 в равных мерах, а расстояние между городами B и C равно 100, а расстояние между городами B и D равно 50. Большее расстояние между B и C в конце концов заставляет систему освещать канал C3, вызывая отступление амебы из этого канала, но позволяя ей продолжать движение в D3.

В целом, моделирование TSP с помощью амебы использует естественную тенденцию амебы к поиску стабильного равновесия. Поскольку каналы, представляющие более короткие маршруты, с меньшей вероятностью будут освещены, амеба может распространяться в этих каналах и продолжать исследовать другие неосвещенные каналы, чтобы максимизировать площадь своей поверхности на пластине агара.

Исследователи также разработали компьютерную симуляцию под названием AmoebaTSP, которая имитирует некоторые основные особенности того, как амеба решает проблему, в том числе непрерывное движение геля, когда он подается с постоянной скоростью и выводится из различных каналов.

В будущем исследователи планируют еще больше улучшить вычислительные способности амебы.

«Мы рассмотрим далее, как эти сложные пространственно-временные колебательные динамики повышают вычислительную производительность при поиске решений более высокого качества за более короткое время», — сказал соавтор работы Сонг-Джу Ким в университете Кейо. «Если это можно уточнить, знания будут способствовать созданию новых аналоговых компьютеров, которые используют пространственно-временную динамику электрического тока в его цепи.»

«Конечно, запуская некоторые другие алгоритмы на традиционных цифровых компьютерах для линейного времени, мы можем получить приблизительные решения для TSP. С другой стороны, при запуске наших имитационных моделей (AmoebaTSP или его разработанных версий) на традиционных компьютерах, как мы это делали в этом исследования, аналоговая и параллельная пространственно-временная динамика требуют нелинейного времени для моделирования их как цифровых и последовательных процессов, поэтому мы пытаемся получить гораздо более качественные решения, чем те, которые получены из традиционных, запустив наши модели на аналоговых компьютерах для линейного времени».

Исследователи также ожидают, что, изготовив более крупную микросхему, амеба сможет решить проблемы TSP с сотнями городов, хотя для этого потребуются десятки тысяч каналов.

Liping Zhu, Song-Ju Kim, Masahiko Hara, and Masashi Aono. «Remarkable problem-solving ability of unicellular amoeboid organism and its mechanism.» Royal Society Open Science. royalsocietypublishing.org/doi/10.1098/rsos.180396