Наука часто опирается в решении своих задач на естественный мир природы. Животные с их уникальными способностями, строением тела и поведением могут вдохновлять специалистов из разных сфер на разработку полезных технологий.
На этот раз вдохновителем стала амеба. Японские ученые на основе наблюдений за ней смогли разработать аналоговый компьютер, решающий так называемую задачу коммивояжера. Самое интересное, что обычным компьютерам она не под силу.
Хитрая проблема
Для начала стоит представить работу самого коммивояжера. Он должен посетить разные города, чтобы представить клиентам свою продукцию, а затем вернуться домой. Нет смысла ездить в один и тот же город два раза, но в то же время маршрут должен быть наиболее экономным. Казалось бы, зная расстояние между каждыми двумя точками назначения, эту задачу вполне можно решить. Но на самом деле эта задача не так проста.
Проблему коммивояжера сформулировали еще в 1930 году, и ее непросто решить обычными вычислениями. Более того, обычный цифровой компьютер может не справиться с ней, если количество городов будет насчитывать несколько десятков. При этом существуют методы решения этой задачи посредством приближений и эвристики.
Логистическая оптимизация
С точки зрения задач оптимизации этот путь коммивояжера крайне интересен. Подобные условия часто встречаются в практической логистике, когда необходимо выбирать оптимальные маршруты с целью экономии ресурсов. Один коммивояжер едва ли посетит за день даже десяток городов, но для крупной компании наподобие Amazon важно рассчитывать сотни и тысячи маршрутов, доставляя миллионы посылок.
О важности данной задачи свидетельствует и тот факт, что исследователи разрабатывают специальные компьютеры – машины Изинга. Но даже они не могут рассматриваться в качестве универсального средства решения задачи коммивояжера. Машина Изинга требует сложной предварительной подготовки, а также характеризуется невысокой точностью.
И вот на помощь ученым приходят амебы, которые предлагают эффективную модель решения этой непростой задачи.
Экспериментальный путь
В 2019 году было проведено исследование поведения амебы в рамках системы из 64 условных точек назначения, своего рода участков с питательными веществами. Как выяснилось, амеба смогла найти оптимальный маршрут, посетив все 64 «города». Хотя и эти результаты были далеко не идеальными даже на фоне вычислений мощного компьютера, ученые решили продолжить исследования.
В новой серии исследований команда ученых из Университета Хоккайдо под руководством Сейя Касаи воссоздала модель поведения амебы. Они разработали аналоговую электронную систему, имитирующую амебу. Причем данная модель может быть собрана на обычной плате.
Оптимальное решение
Искусственный «мозг» амебы искал решение в условиях электронной среды, где значения сопротивления на перекрестках поперечных полос являются ограничениями и требованиями. Аналоговая модель воспроизводит эффективные и уникальные возможности оптимизации, которые амеба приобрела в процессе эволюции с ее механизмами естественного отбора.
Схема позволяет искать оптимальные решения, похожие на поведение настоящей амебы. Модель определила кратчайший маршрут для 4 пунктов назначения и проявила себя с более высокой эффективностью по сравнению с широко используемым алгоритмом в оптимизации локальных сетей под названием 2-opt.
Новые возможности
На данном этапе результаты научных исследований поведения амебы применительно к задаче коммивояжера сложно назвать наилучшими по сравнению со многими альтернативными моделями решений, однако они обнадеживают. Пока тестирование касалось лишь небольших по масштабу задач с малым количеством городов, но сама по себе возможность разработки компьютера на основе поведения живого организма вдохновляет исследователей.
Даже несмотря на низкую скорость поиска решения, аналоговая схема «мозга» амебы может справляться с важными задачами из реальной жизни. Это же направление в принципе может положить начало новому поколению нетрадиционных компьютеров. Ведь также важно учитывать технологическую простоту созданного японскими учеными компьютера. Для него требуется компактная схема, которая в итоге может быть применена в огромном массиве вычислительных процессов как энергосберегающий микрочип.