• Добавить в закладки
  • Facebook
  • Twitter
  • Telegram
  • VK
  • Печать
  • Email
  • Скопировать ссылку
11.07.2022
Дмитрий Васильков
3 903

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

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
Предстоящие мероприятия
Вчера, 21:01
Юлия Трепалина

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

Вчера, 19:20
Березин Александр

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

Вчера, 14:46
Юлия Трепалина

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

20 апреля
Полина Меньшова

Распространено мнение, что, чем чаще пара занимается сексом, тем сильнее каждый из партнеров доволен отношениями. Международная команда исследователей проверила этот тезис.

18 апреля
Игорь Байдов

В 2006 году исследователи из Великобритании объявили, что легендарный антикитерский механизм, древнегреческий «компьютер», мог быть всего лишь игрушкой для демонстрации астрономических явлений. Авторы нового исследования подтвердили это, построив математическую модель на основе данных своих коллег, которая показала, что шестерни устройства заклинивало при запуске. Но несмотря на полученные результаты, ученые пытаются спасти репутацию древнего чуда техники, обвинив предыдущую команду в ряде ошибок.

18 апреля
Любовь

Примерно 41-42 тысячи лет назад на Земле произошел кратковременный сдвиг магнитных полюсов, который мог способствовать вымиранию неандертальцев, но не Homo sapiens — их выживание авторы нового исследования связали с появлением теплой одежды и добычей охры.

8 апреля
Березин Александр

До 13 тысяч лет назад в Северной Америке жил вид, который ученые до недавнего времени считали волком. Компания Colossal Biosciences объявила о возрождении этого вымершего вида, но биологические детали ставят ее заявление под серьезное сомнение.

2 апреля
Березин Александр

Известный американский отраслевой обозреватель Эрик Бергер взял интервью у экипажа космического корабля Boeing, из-за технических проблем которого два астронавта задержались на орбите на девять месяцев вместо одной недели. Детали, которые они озвучили, указывают на серьезные проблемы Starliner, о которых ранее умалчивали. Люди провели немало времени при глубоко нештатной температуре. При слегка другом сценарии миссии экипаж корабля мог погибнуть. Официальные заявления NASA и Boeing сразу после июньского полета к МКС, судя по интервью, были заведомо неправдивыми.

16 апреля
Андрей

Многие знают, как популярны сувениры из окаменелостей — зубы древних акул или полированные панцири аммонитов. Но чем реже встречаются такие артефакты, тем они ценнее, то есть на них можно много заработать. И это проблема для палеонтологов. Американский специалист по тираннозаврам оценил ущерб, который нанесла коммерческая добыча костей T. rex и подсчитал среднюю цену таких образцов. Оказалось, больше половины найденных тирексов находится в частных руках, а значит, для науки они недоступны или ненадежны.

[miniorange_social_login]

Комментарии

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

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

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

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

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

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

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

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

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

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

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

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

Понятно