Категории
 
Ссылки
 

Шмели решают задачу коммивояжера

Шмели решают задачу коммивояжера

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

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

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

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

По виду маршрутов стало ясно, что первые полеты носили явно случайный характер, что само собой разумеется. По общепринятой теории, и последующие маршруты при обнаружении новых цветков должны были бы быть рандомными. Но оказалось, что после обнаружения более короткого маршрута, шмель запоминает его и в дальнейшем использует в основном только его, периодически пробуя и новые варианты. В результате, этот метод проб и ошибок приводил к тому, что в среднем после 26 вылетов (на языке алгоритмов их можно назвать итерациями) шмель двигался уже по оптимальному маршруту. Путь после оптимизации сокращался на 80%, т.е. в пять раз.

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