• Добавить в закладки
  • Facebook
  • Twitter
  • Telegram
  • VK
  • Печать
  • Email
  • Скопировать ссылку
11 июля
Дмитрий Васильков
2 113

Стадное чувство: как математики вдохновляются жизнью животных

6.3

Выражение «стадное чувство» нечасто используется в положительном смысле. Между тем в природе сплошь да рядом живые организмы, обладающие сравнительно низким индивидуальным интеллектом, объединяются в сообщества, которые ведут себя намного умнее и организованнее, чем каждый из их членов по отдельности. Это навело математиков и физиков конца XX века на мысль о применении роевого, то есть коллективного, интеллекта в нашей жизни для решения сложных задач.

«Кит в небесах», рой птиц над полем в сельской местноти, Великобритания / ©James Wainscoat, Unsplash

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

Получается, что большинство практических задач комбинаторной оптимизации (например, маршрутизация грузовиков) требуют особого подхода. Эвристические методы, к которым относятся и роевые алгоритмы, производят относительно ограниченный поиск решений и находят, возможно, не лучшее, но точно близкое к нему решение за разумное время «методом проб и ошибок». Лучшие же современные алгоритмы позволяют находить решения, на 95-99% приближенные к оптимальным. 

В этом месте нам стоит на минуту задержаться и объяснить, каким образом мы рассчитываем эффективность таких решений.

  • Во-первых, для большинства задач можно получить оценку сверху (или снизу, в зависимости от задачи) для глобального оптимума, при этом не имея возможности найти сам глобальный оптимум. Например, перед нами стоит задача оптимально погрузить изделия сложной формы и большой массы в вагон — теоретический оптимум достигается при использовании 100% грузоподъемности и вагона, но не нарушатся ли при этом другие ограничения, ответить невозможно, не решив задачу оптимизации. Если роевой алгоритм находит решение, позволяющее достичь загрузки на 95% грузоподъемности, это можно считать приближенной оценкой точности алгоритма.
  • Во-вторых, иногда мы можем узнать оптимальное значение функции, но при этом практическую ценность имеет значение аргумента, при котором функция достигнет оптимума, а найти его можно, только решив задачу оптимизации. Например: есть сложный производственный процесс с большим количеством переделов. Мы знаем, что минимальные издержки на производство партии продукции могут составить 95 рублей, но не знаем, как надо настроить оборудование и в какой последовательности обрабатывать изделия, чтобы достичь такого уровня затрат. Роевой алгоритм предлагает настройки и последовательность операций, при которых издержки составят 100 рублей. Таким образом, оценочная точность алгоритма составит 95%.

А теперь представьте, что есть организмы в животном мире, которые, конечно же, не знают, что такое математика, но бессознательно ежедневно действуют оптимально и эффективно. Жизнь некоторых из этих животных вдохновила ученых на разработку алгоритмов. Такие алгоритмы называют биоинспирированными, так как они повторяют поведение животных или природных явлений. Так, например, отдельная птица или рыба и не подозревает, что стая, в которой она живет, ведет себя как бы разумно. Каждая особь (в алгоритме — частица) меняет свою позицию в пространстве, ориентируясь на свой опыт и на положение соседей. Это помогает птицам не сталкиваться друг с другом и лететь по оптимальному маршруту к нужному месту. 

Такое системное поведение животных иллюстрирует понятие «автосинхронизации», или «закона пяти процентов», встречающееся, в том числе, и в мире людей. Если в каком-то обществе 5% участников одновременно совершают определенное действие, например начинают аплодировать артистам на сцене, то остальные люди автоматически начинают делать то же самое: сначала порознь, а потом и синхронно. Похожим образом работает и муравьиный алгоритм: отдельный муравей будет очень долго искать оптимальный путь от еды или строительных материалов до дома. Но группа муравьев, объединенных в колонию, быстро находит наилучшее решение. Секрет заключается в феромонах, которые выделяют эти насекомые. Чем путь туда-обратно быстрее, тем больше по нему пробежит муравьев и тем сильнее будет запах внешней секреции, который как бы сигнализирует: «Следуй за мной».

© Airwolfhound

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

© City Church Christchurchб Unsplash

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

Стая волков, Йеллоустоунский парк, США / © Doug Smith, NPS

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

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

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

Квантово-вдохновленные (quantum-inspired) алгоритмы применяют в фармакологии, промышленности, логистике, финансовой сфере и в поиске материалов. То есть везде, где можно оптимизировать путь, расписание или какой-то процесс. Пока считается, что quantum-inspired алгоритмы дают максимальный экономический эффект. Однако нет предела совершенству, и, хотя коммивояжер, выходя из дома на работу, уже может не ломать голову над маршрутом (по крайней мере, на 95-99%), остается еще много нерешенных задач оптимизации из разных областей науки, бизнеса и повседневной жизни, которые только предстоит решить с помощью квантово-вдохновленных алгоритмов.

*Дмитрий Васильков, основатель и CEO QuSolve

Нашли опечатку? Выделите фрагмент и нажмите Ctrl + Enter.
Подписывайтесь на нас в Telegram, Яндекс.Новостях и VK
9 часов назад
Сергей Васильев

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

Вчера, 15:54
Александра Медведева

Международная команда исследователей впервые провела наиболее полную оценку биоразнообразия самой высокой горы мира. Анализируя экологическую ДНК, выделенную из проб воды, отобранных на высоте 4,5-5,5 километра, они обнаружили генетический материал представителей 187 отрядов, что составляет 16,3% от всех известных отрядов живых организмов Земли.

Позавчера, 14:35
Анна Новиковская

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

14 августа
Иван Лавренов

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

Позавчера, 14:35
Анна Новиковская

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

Позавчера, 13:26
Михаил Орлов

Рядом с местом добычи медных руд в пустыне Атакама, расположенной на территории Чили, образовался очень большой круглый провал. Его диаметр достигает 32 метров, а глубина превышает 200 метров. Местные власти расследуют причины случившегося.

2 августа
Александр Березин

Если западным странам удастся «лишить Кремль нефтяных доходов», то мир ждет геополитическое землетрясение. Только не обязательно в ту сторону, о которой вы сейчас подумали. На фоне того, что последует за «лишением», шок 1973 года может показаться детской игрой. Naked Science попробует оценить размах «потолочного катаклизма» заранее.

31 июля
Александр Березин

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

27 июля
Алиса Гаджиева

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

[miniorange_social_login]

Комментарии

Написать комментарий

Подтвердить?
Подтвердить?
Не получилось опубликовать!

Вы попытались написать запрещенную фразу или вас забанили за частые нарушения.

Понятно
Жалоба отправлена

Мы обязательно проверим комментарий и
при необходимости примем меры.

Спасибо
Аккаунт заблокирован!

Из-за нарушений правил сайта на ваш аккаунт были наложены ограничения. Если это ошибка, напишите нам.

Понятно
Что-то пошло не так!

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

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

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

Понятно
Ваше сообщение получено

Мы скоро прочитаем его и свяжемся с Вами по указанной почте. Спасибо за интерес к проекту.

Понятно

Сообщить об опечатке

Текст, который будет отправлен нашим редакторам: