Пчелы и алгоритмы
Одним из направлений научных исследований в наши дни стал анализ природных форм, поведения биологических объектов, с последующими попытками применить полученные знания на практике - для решения тех или иных инженерных и математических задач. Природа в разных своих проявлениях подкидывает ученым интересные идеи, за которые может ухватиться по-настоящему любопытный человек. В некоторых информационных технологиях алгоритмы, подсмотренные в животном мире, уже приносят потрясающие результаты.
Крейг Тови (Craig Tovey) стал известен своей работой над алгоритмом “Honey Bee Algorithm”, который, имитируя поведение колонии пчел, оптимизирует веб-трафик на серверах. Своими идеями на этот счет он поделился недавно с научным сообществом, выступив с докладом в Техасе, на собрании национальной ассоциации содействия развитию науки.
В 2016 году его “Алгоритм пчелиной колонии” получил престижную премию “Золотой гусь”, внедрение алгоритма реально принесло пользу - сократило расходы на веб-хостинг.
Изучая маршруты движения пчел, ученый обнаружил закономерности, которые остаются постоянными. Алгоритм поиска пищи, которым руководствуются насекомыми, эволюционировал в течение миллионов лет и достиг своего совершенства. Ещё миллион лет он будет таким же. Сравните это с сегодняшней ситуацией в микроэлектронике: вы выпускаете новый чип, но через несколько лет он уже устаревает как морально, так и технологически.
Является ли применение решений, имитирующих природу правильным и необходимым в каждой конкретной инженерной задаче, зависит от ее сущности. Часто лучше всего использовать традиционные научные методы, разработанные человечеством - они более эффективны. Когда реальная проблема статична и четко определена, есть предсказуемые исходные данные - тогда методы, основанные на биологии проигрывают классическим теориям оптимизации.
Типичным примером такой задачи является “Проблема коммивояжера” (Traveling Salesman Problem). Алгоритм должен вычислить оптимальный маршрут, по которому проследует продавец, чтобы посетить все намеченные пункты. Комивояжер должен проехать как можно меньшее расстояние (за как можно меньшее время), посетив сотни и тысячи городов и поселков на карте.
Подходы, ориентированные на природные алгоритмы, найдут в этой задаче неплохие (но не лучшие) решения для примерно сотни пунктов. Классическая теория оптимизации быстро предложит наилучший вариант с десятками тысяч пунктов - она обыгрывает эволюцию в этом. Научная методология здесь примерно в 10 миллиардов раз лучше справляется с задачей.
Но жизнь непостоянна и статичных задач со всеми известными исходными данными очень мало. И тут на помощь приходит природа - каждое живое существо очень хорошо справляется с той или иной проблемой, которую перед ним поставила необходимость борьбы за существование.
Добавив элемент непредсказуемости в инженерную задачу мы можем попробовать найти решение, основанное на поведении тех или иных животных, растений или микроорганизмов. И тогда муравьи или пчелы могут дать ответ лучший, чем все наши современные методы оптимизации и мощности суперкомпьютеров для их расчета. Это удивительно, но это так.
В указанной выше задаче пункты статичны - города не перемещаются по карте, а когда добавится элемент движения, то неполнота исходных данных приведет к тому, что биологические алгоритмы будут более эффективными.
В нормальном состоянии трафик на серверах распределяется как обычно, но когда приближается ураган - пользователи начинают проверять прогноз погоды в десятки и сотни раз чаще, чем обычно. Когда на финансовых рынках паника - все внимание сосредотачивается в этом направлении. Запросы в интернете будут меняться в зависимости от происходящих событий и пропускную способность в сторону тех или иных сайтов нужно увеличивать. Здесь и пришли на помощь пчелы со своим поведением.
Пчелы эволюционировали в условиях когда они имеют дело с цветочными полянами, которые постоянно меняют свои характеристики. На одном лугу могут быть растения, доступные для сбора нектара в 10 часов утра, но закрывающие бутоны после полудня. А может вообще начаться дождь и вылет будет невозможным. Алгоритмы поведения пчел основаны на приспособлении насекомых к потокам спроса-предложения, подобно тем, которые обслуживает веб-сервер. Поэтому Тови с коллегами смогли воспользоваться идеями, подаренными самой природой.
Хотя классические алгоритмы эффективнее природных в ряде случаев, иногда наблюдение за живыми существами может принести потрясающие результаты. Взять к примеру слизевиков - простейшие существа питаются той органикой, что находится рядом с ними, если положить кусочки пищи рядом с ним, слизевик будет расширяться, стремясь поглотить их, он как бы соединит все кусочки друг с другом с помощью своего тела.
И это будет прообраз эффективного соединение многих точек друг с другом. В одном из исследований кусочки еды разместили в местах, соответствующих крупным городам на карте Японии. Слизевик в процессе роста практически полностью повторил топологию железнодорожной сети страны, а ведь ее маршруты вырабатывались десятилетиями! Так природа показывает, что может быть потрясающе эффективной и работать не хуже науки.
Забавно, что несмотря на свои многочисленные исследования с пчелами, сам Тови не может к ним приблизиться - у него наследственная аллергия к укусам этих насекомых. Его семье приходится держать дома специальные шприцы с противоядием, однако даже в этих условиях пчелы помогли ученому. Из всего на свете можно извлечь пользу ;-)
