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