Хабрахабр

Нейросеть с амёбой решили задачу коммивояжера для 8 городов

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

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

Версия «decision problem» (то есть такая, в которой ставится вопрос, существует ли маршрут не длиннее, чем заданное значение k) относится к классу NP-полных задач. Оптимизационная постановка задачи относится к классу NP-трудных задач, впрочем, как и большинство её частных случаев.

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

По указанной ссылке приведены попытки решения для инстанса из 1 904 711 городов Земли из базы Национального географического общества. Несмотря на большую вычислительную сложность, известно большое количество эвристических и точных алгоритмов, которые способны полностью решить некоторые случаи с десятками тысяч городов, и даже проблемы с миллионами городов могут быть аппроксимированы в пределах 0,05%.


База Национального географического общества из 1 904 711 городов

На данный момент рекорд по минимальному расстоянию для городов Земли составляет 7 515 772 107 км, он установлен 13 марта 2018 года с помощью эвристического алгоритма LKH.

Классическая задача коммивояжёра в информатике используется в качестве эталонного теста для алгоритмов оптимизации.

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

Your browser does not support HTML5 video.

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

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

Для моделирования задачи коммивояжера каждому из 64 каналов на табличке был присвоен код города между A и H, в дополнение к номеру от 1 до 8, который указывает порядок городов (порядок городов соответствует порядку их посещения коммивояжёром).

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

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

1098/rsos. Научная статья опубликована 19 декабря 2018 года в журнале Royal Society Open Science (doi: 10. 180396).

Показать больше

Похожие публикации

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»