Решения задачи коммивояжера, полученные вычислительной системой на основе амёбы. Примеры туров коммивояжёра по четырём, пяти, шести, семи и восьми городам, полученные в экспериментах, где каждый тур окрашен в красный цвет на соответствующих каналах с правого рисунка. Левые панели показывают переданные светлые изображения начальных состояний (
Группа японских исследователей из Университета Кейо в Токио продемонстрировала, что амёбы способна генерировать приближённые решения удивительно сложной математической задачи, известной как задача коммивояжера.
Задача коммивояжёра — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город.
Оптимизационная постановка задачи относится к классу NP-трудных задач, впрочем, как и большинство её частных случаев. Версия «decision problem» (то есть такая, в которой ставится вопрос, существует ли маршрут не длиннее, чем заданное значение k) относится к классу NP-полных задач.
Сложность вычисления правильного решения возрастает экспоненциально, чем больше городов добавляется к задаче. Например, для четырёх городов есть три варианта решения, а для шести городов — 360. В дальнейшем продолжается экспоненциальный рост.
Несмотря на большую вычислительную сложность, известно большое количество эвристических и точных алгоритмов, которые способны полностью решить некоторые случаи с десятками тысяч городов, и даже проблемы с миллионами городов могут быть аппроксимированы в пределах 0,05%. По указанной ссылке приведены попытки решения для инстанса из 1 904 711 городов Земли из базы Национального географического общества.
База Национального географического общества из 1 904 711 городов
На данный момент рекорд по минимальному расстоянию для городов Земли составляет 7 515 772 107 км, он установлен 13 марта 2018 года с помощью эвристического алгоритма LKH.
Классическая задача коммивояжёра в информатике используется в качестве эталонного теста для алгоритмов оптимизации.
Амёбы — одноклеточные организмы, не имеющие понятия о сложности комбинаторной оптимизации. У них нет ничего даже отдалённо напоминающего центральную нервную систему, что делает их менее подходящими кандидатами для решения задачи такой сложности. Тем не менее, японские исследователи обнаружили, что определённый тип амёбы можно использовать для расчёта почти оптимальных решений задачи коммивояжера для восьми городов.
Согласно научной статье, в экспериментах участвовала амёба под названием Physarum polycephalum, которая раньше уже использовалась в качестве биологического компьютера в нескольких других экспериментах. Данное существо считают особенно полезным в биологических вычислениях, потому что она может расширять различные области своего тела в поисках более эффективного способа получения пищи, и она ненавидит свет.
Чтобы превратить этот естественный механизм питания в компьютер, японские исследователи поместили амёбу на специальную пластину с 64 каналами, в направлении которых животное могло вытягивать тело. Амёба постоянно пытается расширить тело, чтобы покрыть как можно большую площадь пластины с питательным веществом. Тем не менее, каждый канал в пластине можно осветить, что заставляет амебу из чувства отвращения к свету убраться из этого канала.
Для моделирования задачи коммивояжера каждому из 64 каналов на табличке был присвоен код города между A и H, в дополнение к номеру от 1 до 8, который указывает порядок городов (порядок городов соответствует порядку их посещения коммивояжёром).
Для программирования амёбы исследователи использовали нейронную сеть, которая включала данные о текущем положении амебы и расстоянии между городами, чтобы осветить определённые каналы. Нейронная сеть была обучена с большей вероятностью освещать города (каналы) с бóльшими расстояниями между ними.
При взаимодействии алгоритма и амёбы последняя принимает форму, которая представляет приблизительные решения задачи коммивояжера. Самое интересное, что количество времени, которое требуется амёбе для получения этих почти оптимальных решений, растёт линейно, хотя количество вариантов решения увеличивается экспоненциально. В ближайшее время исследователи собираются изготовить чипы с десятками тысяч каналов, чтобы амёба могла попробовать решить задачу коммивояжера на сотнях городов.
Научная статья опубликована 19 декабря 2018 года в журнале Royal Society Open Science (doi: 10.1098/rsos.180396).
Автор: alizar
