Решения задачи коммивояжера, полученные вычислительной системой на основе амёбы. Примеры туров коммивояжёра по четырём, пяти, шести, семи и восьми городам, полученные в экспериментах, где каждый тур окрашен в красный цвет на соответствующих каналах с правого рисунка. Левые панели показывают переданные светлые изображения начальных состояний (
Группа японских исследователей из Университета Кейо в Токио продемонстрировала, что амёба способна генерировать приближённые решения удивительно сложной математической задачи, известной как задача коммивояжера.
Задача коммивояжёра — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город.
Оптимизационная постановка задачи относится к классу 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, который указывает порядок городов (порядок городов соответствует порядку их посещения коммивояжёром).
Для программирования амёбы исследователи использовали нейронную сеть, которая включала данные о текущем положении амебы и расстоянии между городами, чтобы осветить определённые каналы. Нейронная сеть была обучена с большей вероятностью освещать города (каналы) с бoльшими расстояниями между ними.
При взаимодействии алгоритма и амёбы последняя принимает форму, которая представляет приблизительные решения задачи коммивояжера. Самое интересное, что количество времени, которое требуется амёбе для получения этих почти оптимальных решений, растёт линейно, хотя количество вариантов решения увеличивается экспоненциально. В ближайшее время исследователи собираются изготовить чипы с десятками тысяч каналов, чтобы амёба могла попробовать решить задачу коммивояжера на сотнях городов.
Научная статья опубликована 19 декабря 2018 года в журнале Royal Society Open Science (doi: 10.1098/rsos.180396).
Комментарии (31)
helgihabr
24.12.2018 22:36+4Т.е. амеба выбирала менее подсвеченные каналы, т.к. это, очевидно, ее меньше раздражало?
Каким образом это можно назвать решением или поиском кратчайшего пути?Gibboustooth
24.12.2018 23:57Возможно, интенсивность подсветки каналов меняется динамически зависит от того, какие каналы амеба уже выбрала. Т.е. если она заползла в канал D1, то каналы A2, B2 и C2 будут подсвечиваться в соответствии с расстояниями от D до, соответственно, A, B и C.
Hardcoin
25.12.2018 10:53Каким образом это можно назвать решением
Численно совпадает (примерно).
helgihabr
25.12.2018 11:07Я понял, что результат устроил ученых.
Но, судя по переводу, решала задачу нейросеть:
Нейронная сеть была обучена с большей вероятностью освещать города (каналы) с бoльшими расстояниями между ними.
А амеба уже занимала более комфортное для себя положение (как результат раздражения ее светом и «поощрения» пит. вещ.)
igor_suhorukov
25.12.2018 00:22+3Так это же классика исследованийВстречаются как то Петька с Чапаевым, говорит Петька:
— Товарищ Чапаев, дайте 5 рублей на опыты!
Чапаев достает и отдает деньги. Через 3 дня проходит около сарая и видит, заходя в сарай, что лежит Петька пьяный в стельку, а рядом лежит блокнот. Берет и читает:
— Опыт 1-й: берем таракана, отрываем ему 2-е ноги, свистим таракан убегает!
Опыт 2-й: берем отрываем таракану еще 2-е ноги, свистим таракан убегает!
Опыт 2-й: берем отрываем таракану последние ноги, свистим таракан стоит!
Вывод: таракан без ног не слышит!mapron
25.12.2018 17:14+1Я как-то слышал вариант этого анекдота со сверчком. Я еще задумался тогда, какая ирония, неправильными методами получить верный результат)
DrPass
25.12.2018 00:35Я правильно понимаю, что вместо амёбы можно было поставить восемь банок и кидать в них шарики по указанию нейросети?
Sychuan
25.12.2018 01:32Нет, не правильно. Нейросеть там для того, чтобы закодировать для амебы саму задачу и заставить амебу ее решать, чего она сама по себе делать не будет+заставить ее найти хороший локальный минимум, а не первый попавшийся.
napa3um
25.12.2018 07:57Да, вполне себе близкая аналогия, ещё можно усилить её, сделав шарики магнитными (чем больше шариков в канале, тем больше вероятность примагнитить ещё шариков), и сделав шарики сдувающимся «в одиночестве» (чем меньше шариков вокруг, тем быстрее уменьшается объём шарика). По сути, описанное в статье является слегка замаскированной реализацией муравьиного алгоритма, только в качестве муравьёв выступают ложноножки, а в качестве феромонов — плазма, заполняющая эти ложноножки внутри. Ценностью явлляется, видимо, сама конструкция «биологического чипа», акселерирующего ACO-based алгоритмы (к которым при должном остроумии можно свести большинство NP-полных задач, допускающих приближённые решения), то она есть. Но думать, будто открыты какие-то новые интеллектуальные свойства амёб, конечно, глупо, амёбы выступают лишь в качестве удобных (посмотрим, когда технологию сделают серийной) и миниатюрных био-моделей известного алгоритма.
gen4
25.12.2018 00:42Ждал статью на русском, чтобы понять, как же там все это устроили. Не помогло :(
plus79501445397
25.12.2018 10:30До хабра на русском раньше были подобные заметки, например на ленте.
gen4
25.12.2018 15:06супер, спасибо
для тех, кому лень, выношу:
Исследователи поместили Physarum polycephalum внутрь чипа, который представляет собой круглую выемку с выходящими из нее 64 узкими каналами. Внутри выемки и в каналах находится питательное вещество, и слизевик старается проникнуть в них, чтобы максимизировать поступление в клетку питательных веществ.
Каждый из восьми городов (A, B, C и другие) в задаче представлен восемью каналами с порядковыми номерами, показывающими, каким по счету может быть город при посещении коммивояжером. Когда слизевик проникает в город A с номером 3, во всех остальных каналах с тем же номером (B3, С3) загорается свет, отпугивающий слизевика. Таким образом, предотвращается одновременное посещение городов. Кроме того, в компьютер, управляющий светом, заложена информация о расстоянии между городами. Если слизевик после посещения города А начинает проникать в каналы В и С, но при этом С находится от А ближе, чем В, то в последнем также загорается свет, отпугивающий плазмоид. Так достигается выбор оптимального маршрута.
masai
25.12.2018 01:11Как говорит мой коллега, ждём статьи, в которой бактериями распознают MNIST. :)
NoRegrets
25.12.2018 12:19Афера века. Жду следующую статью, в которой они будут стебаться над журналом, опубликовавшим первую статью.
NoRegrets
26.12.2018 21:17Видимо рецензенты журнала, так же как и минусаторы, думали, что все это выглядит серьезно и наукообразно. Тут тебе и нейронная сеть и вообще какой-то свежий подход с биологической субстанцией. На самом деле здесь написана чушь.
Нейронная сеть, которая выбирает, какие каналы нужно подсветить, а какие нет, исходя из расстояния до города. Что, теперь для того чтобы это сделать нужна нейронная сеть? Я думаю тут без блокчейна не обойтись. Амеба, которая выбирает один из предложенных приоритетных вариантов, придает видимость, что тут есть какая-то, новизна. На самом деле эту задачу, с успехом, мог выполнить и рандом.
В общем, если дело действительно обстоит так, как написано, то это статья — детектор.
plus79501445397
25.12.2018 12:38Самое интересное, что количество времени, которое требуется амёбе для получения этих почти оптимальных решений, растёт линейно, хотя количество вариантов решения увеличивается экспоненциально. В ближайшее время исследователи собираются изготовить чипы с десятками тысяч каналов, чтобы амёба могла попробовать решить задачу коммивояжера на сотнях городов
Мне одному кажется, что «линейный рост» до 8 городов — это «ниачем»? ;)
Нет, я вполне согласен с тем, что амебы, пчелы, муравьи за многие миллионы лет эволюции могли выработать эффективные алгоритмы поведения, которые интересно изучать и в определенных случаях извлекать пользу от их применения. Но насколько хватит условных ресурсов амеб (пчел, муравьев) для сохранения «линейного роста» при практически значимых действительно больших N, когда «количество вариантов решения увеличивается экспоненциально» (от N)?
К сожалению ответа в статье нет и нам предлагается лишь ждать (надеяться и верить), когда они «изготовят чипы»,
чтобы «амёба могла попробовать решить задачу коммивояжера на сотнях городов»…Hardcoin
25.12.2018 21:49Суть не в использовании амёбы для решения практических задач, суть в изучении законов природы. В данном случае на стыке дисциплин.
эффективные алгоритмы поведения, которые интересно изучать и в определенных случаях извлекать пользу от их применения
В основном польза именно от этого. Даже если они проверят на сотне городов, это не будет иметь реального практического смысла, компьютер решает эту задачу быстро, а его использование заметно удобнее. Но направление исследований интересное.
napa3um
27.12.2018 05:08-1Суть — в освоении бабла. Увы, наука как и любой другой социальный институт не избавлена от «человеческого фактора», там тоже хотят кушать. Шнобелевская премия, например, придумана как раз для того, чтобы уличать подобных исследователей (но, конечно, под неё попадает лишь мизерная часть подобных исследований). Описанное в статье не является ни фундаментальным исследованием (результат заранее известен и из него никаких новых умозаключений сделать не получится), ни разработкой практической технологии (муравьиный алгоритм в транзисторном чипе можно реализовать гораздо эффективнее). У лаборатории есть оборудование, есть амёбы и есть план на количество научных публикаций — так и появляются подобные статьи.
aleksandrzhmydyak
25.12.2018 13:16Прочитав статью, вспомнил про «механические» вычисления на примере какого-то собора: на натянутую ткань подвешивали грузики таким образом получали оптимальную по прочности форму купола.
Stepan555
25.12.2018 17:11+2По-моему автор сам не понял как это работало. Во всяком случае, по описанию ничего не понятно. Каким образом задавался порядок обхода и расстояние между городами? Просто подвели несколько каналов — одни амёбе нравятся, другие нет. А как она узнала в каком порядке их обходить? Как считывался вычисленный амёбой маршрут? На фотках тоже, кстати, никакого маршрута не видно, видна паутина каких-то кривых каналов, которые на оптимальный маршрут ну никак не похожи. Кроме того, это очень частный случай, когда все города расположены на одном кольце.
Facenapalm
25.12.2018 21:11Неужели поведение амёбы так сложно смоделировать? Ну и учитывая, что нейросети приходится регулировать освещение на всех возможных переходах, которых n?, линейной сложностью тут и не пахнет.
Siddthartha
25.12.2018 21:50не экспотенциально, а по факториалу.
в случае полного перебора — n! — соответственно, растет быстрее, чем обычная экспонента с постоянной базой a^n.
VDG
26.12.2018 04:14Состояние слизевика можно представить точкой в гиперкубе, в данном случае в 64-мерном. Слизевик пытается занять все каналы, т.е перейти из точки (0,0...0) в точку (1,1...1), но внешняя среда по только ей известному закону запрещает ему одновременно находиться в некоторых размерностях. На каждое своё движение точки слизевик получает от внешней среды новое запрещённое состояние (опять же в виде точки в гиперкубе), запоминает его и выбирает куда двигать свою точку на основе всех уже известных ему запрещённых состояний.
Посещают мысли, что аналогичным образом ведёт себя нейрон. Только в отличие от слизевика, охотящегося за едой, нейрон охотится за активностью других нейронов — дендритное дерево также активно в поиске как плазмодий. Слизевик/нейрон, можно сказать, строит модель внешнего мира и находит в ней локальный максимум.
leR12
амёба = это живое соответствие богу. ибо живое. делится и не умирает!
CrzyDocTI
Да прибудет с нами создатель наш Летающий Макаронный Монстр