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

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

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

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

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

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

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

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

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

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

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

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

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

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

Закладка

Скопировать ссылку

Email

Печать

Twitter

VK

Telegram