Группа исследователей из Университета Кейо в Токио доказала, что амеба может решать знаменитую «задачу коммивояжера» с близкими к правильным результатами. И то, как она это делает, позволяет ей при определенных условиях обогнать по скорости вычислений компьютер.

Задача коммивояжера заключается в том, что нужно рассчитать кратчайший маршрут между базой и несколькими покупателями, которых нужно объехать и доставить им товар. Ее отличает экспоненциальный рост сложности – при 4 покупателях есть лишь 3 возможных решения, но при 6 покупателях количество вариантов возрастает до 360. В общем виде задача была решена в 90-е годы, и сегодня можно получить результат даже для миллионов покупателей, что востребовано в международной логистике.


Амеба Physarum polycephalum вечно голодна и боится солнечного света. Ученые создали подобие лабиринта – в емкости есть 64 сектора, где расположена пища, а сама амеба размещается в центре и должна сместиться, чтобы добраться до еды. Над лабиринтом смонтирована система освещения, которая формирует световые «барьеры» на пути к еде. Нейросеть управляет освещением так, чтобы оставлять в тени для амебы заданное количество целей и подсвечивать пути между ними тем ярче, чем больше расстояние. То есть, амебе нужно найти кратчайшие пути между объектами, чтобы покушать и избежать света.

Выяснилось, что микроорганизм почти всегда решает эту задачу идеально точно. И скорость принятия решений увеличивается линейно при усложнении задачи, хотя в IT-науке рост вычислительных операций в этом случае должен расти по экспоненте. Это трудно объяснить с позиции науки, поэтому эксперименты продолжаются. Сейчас заказаны пробирки с архитектурой для имитации десятков тысяч объектов-кормушек – интересно наблюдать за поведением амебы при таком лавинообразном усложнении условий задачи.
Источник
Аналогичное разумное поведение есть у грибов при поиске корма:

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

Оптимальный маршрут коммивояжёра через 15 крупнейших городов Германии. Указанный маршрут является самым коротким из всех возможных 43 589 145 600 вариантов

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

Сложность вычисления правильного решения возрастает экспоненциально, чем больше городов добавляется к задаче. Например, для четырёх городов есть три варианта решения, а для шести городов — 360. Если есть маршрут с десятью или более городами, количество возможных маршрутов исчисляется миллионами.

Группа японских исследователей из Университета Кейо в Токио продемонстрировала, что такие сложные задачи может решать простейшая амёба. За миллионы лет эволюции слизь Physarum polycephalum научилась делать две вещи: двигаться к еде и избегать света




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

Для программирования амёбы исследователи использовали нейронную сеть, которая включала данные о текущем положении амебы и расстоянии между городами, чтобы осветить определённые каналы. Нейронная сеть была обучена с большей вероятностью освещать города (каналы) с бóльшими расстояниями между ними.

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

via
via