» » Шмели и задача коммивояжёра

Шмели и задача коммивояжёра


Шмели и задача коммивояжёра

Шмели и задача коммивояжёра

На фото — сидящий на цветке бодяка земляной шмель (Bombus terrestris) с антенной на спине. Антенна нужна для отслеживания траектории полета шмеля во время сбора нектара и пыльцы. Ее длина 16 мм, вес — меньше 3 мг, что составляет всего 1,5% от массы шмеля, так что она не влияет на его поведение.

Шмели, как и многие другие животные-собиратели, стараются оптимизировать пройденный путь между гнездом и регулярно посещаемыми местами сбора нектара.

В некотором смысле они решают задачу коммивояжёра, которая формулируется, например, так: в стране есть несколько городов, расстояния между которыми известны; требуется найти самый короткий путь, проходящий через все города по одному разу. Такая, казалось бы, незамысловатая задача оказалась неожиданно трудной. Даже ответ на вопрос «существует ли путь короче заданной величины L?» — это NP-полная задача. То есть, с одной стороны, она принадлежит классу NP — такие задачи мы не умеем «быстро» (за полиномиальное время) решать, но можем «быстро» проверить, верно ли предъявленное кем-то решение, — а с другой стороны, любая другая задача из этого класса «быстро» к ней сводится.

Самый «простой» подход к решению — перебрать все варианты путей. Проблема в том, что с ростом числа городов количество вариантов растет очень быстро (как факториал от числа городов). Например, всего для 60 городов количество возможных путей уже мало отличается от числа атомов во Вселенной, а полный перебор даже на современных суперкомпьютерах теряет смысл еще раньше. При этом нельзя сказать, что люди совсем ничего не могут поделать: есть эвристические алгоритмы, которые находят приближенные решения, то есть пути, довольно близкие к оптимальным (с точностью до нескольких процентов), — для некоторых приложений этого хватает.

Помимо чисто прикладных вопросов (с помощью оптимизации путей в графе моделируются многие реальные процессы), задача коммивояжёра связана (как, впрочем, и любая другая NP-полная задача) и с важнейшей нерешенной проблемой равенства классов P и NP. Достаточно сказать, что на предположении (или надежде) о том, что эти классы не равны, держится современная криптография и, как следствие, банковская и многие другие системы. Не случайно Математический институт Клэя включил ее в список из семи задач тысячелетия, за решение которых предлагается премия в миллион долларов (про решение одной из этих задач см.: Полное доказательство гипотезы Пуанкаре предъявлено уже тремя независимыми группами математиков, «Элементы», 03.08.2006).

В общем, у людей есть некоторый прогресс с задачей коммивояжёра, но от полного решения мы пока далеки. А как обстоят дела у шмелей? Для изучения их поведения используют искусственные цветки с искусственным нектаром. Поскольку настоящие цветы нравятся шмелям больше, эксперименты проводят осенью или на территории, очищенной от настоящих цветков. Сначала испытуемому шмелю дают время понять, что сомнительного вида сооружения — это и есть цветы, затем наблюдают за ним в течение нескольких десятков вылетов. Каждый цветок на тестовом поле дает столько нектара, что для полной заправки (75–100 микролитров) шмелю нужно обязательно посетить за один вылет все цветы.

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


Шмели и задача коммивояжёра

Шмели и задача коммивояжёра

Искусственный цветок и система слежения за шмелями. На штативе закреплена камера и датчики движения, которые управляются с ноутбука. «Цветок» — это стаканчик со сладким сиропом, который медленно пропитывает небольшую желтую губку. Букет из таких не соберешь... Фото из статьи M. Lihoreau et al., 2012. Radar Tracking and Motion-Sensitive Cameras on Flowers Reveal the Development of Pollinator Multi-Destination Routes over Large Spatial Scales


В одном из исследований ученые смотрели, как шмели на практике будут решать задачу коммивояжёра. Для этого они на тестовом поле расположили 5 искусственных цветков в вершинах правильного пятиугольника. Когда цветки находились друг от друга на достаточно большом расстоянии (25 м) и шмели-фуражиры не видели, где следующая цель, то в первые вылеты они активно исследовали пространство: от уже найденного цветка совершали петли в поисках нового. С опытом (с увеличением числа вылетов) оптимизировалась последовательность посещения уже известных цветков и выпрямлялся путь между двумя соседними цветками. В итоге шмели находили кратчайший путь для сбора нектара: в эксперименте расстояние, пролетаемое насекомым в последнем полете, было на 80% меньше по сравнению с первым вылетом. И происходило это довольно быстро: в среднем — на 26-м полете, когда шмель перебирал всего около 20 маршрутов из 120 возможных (120 = 5!).

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


Шмели и задача коммивояжёра

Шмели и задача коммивояжёра

«Цветы» бывают и такими. Во всяком случае, за неимением более подходящих вариантов шмели готовы в это поверить. Фото с сайта phys.org


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

Шмель последовательно разрабатывает свой путь на поле с пятью искусственными цветками (синие кружки), на котором располагается его гнездо (белый кружок). Съемка вылетов 6 шмелей. Видео воспроизводится с ускорением в 600 раз

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

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

Фото © Stephan Wolf с сайта scienceintheclouds.blogspot.com.

Галина Клинк

27 ноябрь 2019 /
  • Не нравится
  • 0
  • Нравится

Похожие новости

Шмели перенимают новые знания от товарищей

Ученые провели исследование механизмов обучения у шмелей. Сначала одна группа этих насекомых освоила нехарактерный для шмелей поведенческий алгоритм добычи сладкого сиропа. Другие шмели, наблюдая за

Перенимая опыт у товарищей, шмели подходят к делу с умом

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

Растения приспосабливаются к новым опылителям всего за несколько поколений

Швейцарские ученые изучили дивергентную эволюцию репы под действием разных опылителей: шмелей и мух-журчалок. Всего за девять поколений растения приобрели новые признаки: опыляемые шмелями растения

Мух-журчалок из разных регионов привлекают разные признаки цветков

Биологи из Индии и Швеции провели масштабное исследование предпочтений мух-журчалок к конкретным цветкам в трех географических регионах. Выявив признаки, привлекательные и непривлекательные для

Математический гений, отказавшийся от приза в 1 миллион долларов

В 2003 году российский математик Григорий Перельман доказал гипотезу Пуанкаре – задачу, которой более 100 лет и которая заключалась в том, что любая фигура без отверстия может быть превращена в

Из жизни пчёл

Пчеловод при помощи дыма не успокаивает пчел, а создает как бы имитацию пожара. Пчелы, являясь древними обитателями леса, при появлении дыма набрасываются на мед, чтобы запастись им на дальнюю
Комментарии

НАПИСАТЬ КОММЕНТАРИЙ

Ваше Имя:
Ваш E-Mail:
Код:
Кликните на изображение чтобы обновить код, если он неразборчив
Введите код:
Популярные новости
Камеры заднего видаКалькулятор тарифов Яндекс на таксиОсновные преимущества керамической плиткиАвтосвет, нюансы ремонта и обслуживанияЭкстрасенсы помогают следствию в раскрытии преступленийВьетнамские дети попрыгали через мертвую змею вместо скакалкиНа реке Генхе в Китае появился редкий вращающийся ледяной дискСамостоятельные путешествия, что важно знать