Выражение «стадное чувство» редко применяется положительно. Однако во множестве живых организмов с невысоким индивидуальным интеллектом наблюдается объединение в сообщества, действующие более разумно и упорядоченно, чем каждый из членов в отдельности. Это заставило математиков и физиков конца XX века размышлять о применении роевого интеллекта в нашей жизни для решения сложных задач.
Представьте себе курьера, который должен доставить пиццу по разным адресам города и вернуться в ресторан. Как ему спланировать маршрут наилучшим образом? Математики называют это задачей коммивояжера. Методы решения таких задач делят на точные и эвристические. Первые, классические, основаны на полном переборе всех вариантов, что делает их неэффективными при большом количестве адресов: поиск ответа может занять много лет.
Большинство практических задач комбинаторной оптимизации (таких как маршрутизация грузовиков) требуют специального подхода. Эвристические методы, включающие роевые алгоритмы, производят сравнительно ограниченный поиск решений и находят, возможно, не наилучшее, но близкое к нему решение за разумное время «методом проб и ошибок». Наилучшие современные алгоритмы позволяют находить решения, приближенные к оптимальным на 95-99%.
Прежде чем двигаться дальше, нужно остановиться и рассказать о том, как мы оцениваем результативность подобных решений.
- Для многих задач можно определить верхнюю (или нижнюю) границу глобального оптимума без его нахождения. Например, при погрузке изделий в вагон теоретический оптимум достигается при полной загрузке, но не учтены все ограничения. Если роевой алгоритм достигнет загрузки на 95%, это будет приближенной оценкой точности.
- Во-вторых, иногда мы можем определить оптимальное значение функции, но практическая ценность имеет значение аргумента, при котором функция достигнет максимума. Его можно найти, решив задачу оптимизации. Например: есть сложный производственный процесс с большим количеством переделов. Знаем, что минимальные издержки на производство партии продукции могут составить 95 рублей, но не знаем, как надо настроить оборудование и в какой последовательности обрабатывать изделия, чтобы достичь такого уровня затрат. Роевой алгоритм предлагает настройки и последовательность операций, при которых издержки составят 100 рублей. Таким образом, оценочная точность алгоритма составит 95%.
Существуют организмы в мире животных, которые, хотя и не осознают математики, ежедневно действуют максимально эффективно. Жизнь некоторых из этих существ вдохновила ученых на создание алгоритмов. Такие алгоритмы считаются биоинспирированными, поскольку повторяют поведение животных или явления природы. Например, отдельная птица или рыба не подозревает, что стая ведет себя разумно. Каждая особь (в алгоритме — частица) меняет свое положение в пространстве, руководствуясь своим опытом и положением соседей. Это позволяет птицам избегать столкновений и лететь по оптимальному маршруту к месту назначения.
Подобное системное поведение животных демонстрирует понятие «автосинхронизации», или «закона пяти процентов», которое наблюдается также в мире людей. Если 5% участников общества одновременно выполняют определённое действие, например начинают аплодировать артистам на сцене, то остальные люди автоматически начинают поступать так же: сначала порознь, а затем синхронно. Муравьиный алгоритм функционирует подобным образом: отдельный муравей долго ищет оптимальный путь от еды или строительных материалов до дома. Но группа муравьев, объединённая в колонию, быстро находит наилучшее решение. Секрет заключается в феромонах, которые выделяют эти насекомые. Чем путь туда-обратно быстрее, тем больше по нему пробежит муравьев и тем сильнее будет запах внешней секреции, который как бы сигнализирует: «Следуй за мной».
К эвристическим алгоритмам относят не только роевые. Некоторые вдохновлены строгой иерархией в животном мире, вертикальными связями, а не горизонтальными, как в случае роя. Например, в пчелином мире разведчики отправляются на поиски нектара вокруг улья и передают координаты базы. Чем больше предполагается найти на лужайке нужных цветов, тем дольше и ярче танец пчелы. Остальные жители улья, если информация их удовлетворяет, отправляются на сбор нектара. Разведчики же улетают искать другие поляны, причем радиус поиска с каждым заходом увеличивается. Поиск останавливается, когда пчелы находят наилучшую по всем параметрам локацию или оптимальное решение, если говорим о пчелином алгоритме.
Алгоритм серых волков, созданный в 2014 году, также включает предводителей-агентов. В дикой природе у стаи есть чёткая иерархия и распределение обязанностей, что напрямую влияет на охотничье поведение хищников. Это послужило основой для алгоритма. При поиске добычи (оптимального решения) предполагается, что альфа-самец (лучший кандидат) и бета-волки имеют более чёткое представление о месте, где может находиться добыча. Остальная часть стаи корректирует своё поведение и местоположение в зависимости от позиции лучших поисковых агентов.
Подходящий алгоритм выбирают исходя из конкретной задачи; единого шаблона не существует. Теорема о бесплатном обедеНаблюдается тенденция: если алгоритм хорошо справляется с определенными задачами, то его эффективность падает при работе с другими. Важно учитывать вычислительные затраты, доступность программного обеспечения и отведенное время для поиска решения, чтобы выбрать подходящий алгоритм. Тем не менее, даже самый хороший алгоритм не гарантирует нахождение наилучшего решения, которое в науке называют глобальным оптимумом. Лишь квантовый компьютер теоретически способен находить глобальный оптимум за разумное время.
Достаточно мощный квантовый компьютер позволил бы быстро и точно решать масштабные и сложные задачи оптимизации, но его пока нет. В нашем распоряжении есть эвристические алгоритмы, успешно применяемые на обычных машинах. К тому же, мы уже можем использовать явления из квантовой физики в природных алгоритмах. Например, квантово-вдохновленный алгоритм роя частиц использует эффект туннелирования для преодоления высоких барьеров.
Представьте игру в боулинг, где кегли стоят за холмом. Ваши силы недостаточны, чтобы шар преодолел его вершину. В классическом мире выход один — отказаться от игры. Но в квантовом мире частицы не идут наверх, а проникают сквозь него. Не имея достаточной энергии, они проходят через препятствие. Это нарушает законы классической механики и демонстрирует квантовую природу явления, применяемую современными алгоритмами. Эффект ускоряет вычисления и помогает избежать застревания в локальном оптимуме при поиске глобального.
Квантово-вдохновленные алгоритмы находят применение в фармакологии, промышленности, логистике, финансах и поиске новых материалов. В тех сферах, где можно оптимизировать маршруты, расписание или процессы. Полагают, что квантово-вдохновленные алгоритмы обеспечивают наибольшую экономическую выгоду. Несмотря на это, стремление к совершенству не знает границ. Хотя для коммивояжера уже не составляет труда рассчитать оптимальный маршрут (как минимум, на 95-99%), множество задач оптимизации в науке, бизнесе и повседневной жизни остаются неразрешенными и ждут своего решения с помощью квантово-вдохновленных алгоритмов.
*Дмитрий Васильков, основатель и CEO QuSolve