Муравьиный алгоритм – всего лишь один из целого семейства так называемых алгоритмов роевого интеллекта, вдохновленных природой. Стаи скворцов или косяки рыб способны очень резко – и при этом согласованно и синхронно – менять направление движения, несмотря на то что каждая особь может коммуницировать лишь с небольшим числом особей по соседству. Информация о появлении хищника неподалеку от одного края косяка рыбы, например, быстро распространяется на другой его край. Заимствуя эти принципы локального взаимодействия, разработчики алгоритмов могут использовать огромные «стаи» исполнительных устройств, объединенных в информационную сеть, для исследования окружающей среды. Их быстрое, «роевое» взаимодействие позволяет им узнавать об открытиях, сделанных другими участниками «роя» в поисках оптимального окружения.
Самый известный природный алгоритм – эволюция. В своей простейшей форме эволюция объединяет признаки родителей, чтобы производить детей. Дети, которые лучше подготовлены к выживанию и размножению в своем окружении, в следующем поколении передадут свои признаки бóльшему числу потомков. Иногда между поколениями происходят мутации, что привносит в популяцию новые признаки, которые могут быть лучше или хуже уже имеющихся. Для создания биоразнообразия, способного решить некоторые из самых сложных проблем планеты, достаточно исполнять всего лишь три простые процедуры – отбирать, комбинировать и мутировать.
Но прежде, чем петь дифирамбы этой биологически-эволюционной панацее, надо признать, что эволюционные решения часто бывают хорошими, но редко, а то и вовсе никогда – безупречными. Документальные фильмы и познавательные статьи о дикой природе изобилуют примерами «идеальной» адаптации животных к окружающей среде. От обитающих в пустыне сумчатых крыс, которые научились обходиться вовсе без воды, извлекая всю необходимую влагу из своего корма, до нототениевидных рыб, которые вырабатывают белки-«незамерзайки», чтобы выжить в океане при отрицательных температурах, – эволюция способствовала появлению животных, блестяще приспособленных к сложным средам обитания.
Однако слепой ход эволюции, которая просто перебирает имеющиеся возможности, не следует путать с целенаправленным поиском совершенства. Эволюция, как правило, находит решение, которое подходит больше, чем любое предыдущее решение для этой среды, но не всегда лучшее.
Популяция обыкновенной рыжей белки в Великобритании является классическим примером. С ее острыми когтями, гибкими задними лапами и длинным хвостом, необходимым для равновесия, она хорошо приспособлена для лазания по деревьям в поисках пищи. Ее зубы непрерывно растут на протяжении всей жизни, позволяя белкам разгрызать твердую наружную оболочку орехов, не теряя при этом резцы. Казалось, она идеально приспособилась к окружающей среде – но тут появился еще более приспособленный родственник. Значительно более крупная серая белка находит и съедает больше пищи, а также более эффективно переваривает и хранит ее. Хотя серые белки никогда не нападали на рыжих и не убивали их, превосходная адаптация быстро сделала их вид доминирующим в широколиственных лесах Англии и Уэльса; они превзошли рыжих в межвидовой конкуренции и захватили их экологическую нишу. Наше восприятие «образцовой» адаптации отдельно взятых видов, вероятно, продиктовано не столько реальными результатами эволюционного поиска оптимального варианта, сколько нашим ограниченным представлением о том, что такое по-настоящему идеальное решение.
Несмотря на то что эволюция не всегда находила лучшее решение, ученые-компьютерщики многократно заимствовали ключевые постулаты наиболее известного из естественных алгоритмов – прежде всего, в виде так называемых генетических алгоритмов. Эти инструменты используются для решения задач планирования (в том числе для составления расписания матчей ведущих спортивных лиг) и для поиска хороших, если не идеальных, решений сложных задач класса NP – таких, как задача о рюкзаке.
Задача о рюкзаке – это история торговца, который хочет унести с собой на рынок как можно больше товаров в рюкзаке с ограниченной вместимостью. Он не может взять с собой все, поэтому приходится выбирать. Разные предметы имеют разные размеры и принесут разную прибыль. Наилучшее решение проблемы рюкзака – отобрать товары, которые принесут самый большой доход. Вариации задачи о рюкзаке возникают при необходимости вырезать фигурные формы из теста или при попытке сэкономить на оберточной бумаге, упаковывая подарки на Рождество. Та же проблема возникает при погрузке судов и фур. Когда диспетчер загрузки определяет, какие куски данных нужно загрузить и в каком порядке, чтобы максимально использовать ограниченную пропускную способность интернет-канала, он пытается решить задачу о рюкзаке.
Генетический алгоритм начинается с генерации заданного числа потенциальных решений проблемы. Эти решения являются родительским поколением. Для задачи о рюкзаке это родительское поколение создает списки пакетов – наборы предметов, которые могут поместиться в рюкзак. Алгоритм ранжирует решения по тому, насколько хорошо они решают проблему. В задаче о рюкзаке критерием ранжирования становится прибыль, которую может принести каждый набор предметов, помещающийся в рюкзак. Затем выбираются два лучших решения – наборы, приносящие наибольшую прибыль. Некоторые наборы из одного хорошего решения отбрасываются, а остальные комбинируются с некоторыми наборами из другого хорошего решения. Существует также возможность «мутации» – случайно выбранный набор может быть удален из рюкзака и заменен другим. Как только в новом поколении создано первое дочернее решение, выбираются еще два наиболее эффективных родительских, которые будут воспроизводиться. Таким образом, лучшие решения в родительском поколении передают свои характеристики бóльшему количеству дочерних решений в следующем поколении. Этот комбинированный процесс повторяется до тех пор, пока не возникнет достаточно «дочек», чтобы заменить все оригинальные решения в родительском поколении. Сделавшие свое дело родительские решения уничтожаются, а дочерние переходят в статус родительских и весь цикл «отбор – комбинация – мутация» начинается заново.
Дочерним решениям присущ случайный характер, поэтому алгоритм не гарантирует, что все «дочки» будут лучше своих «родителей». Вообще-то, многие окажутся даже хуже. Однако, выбирая, какие из дочерних решений станут воспроизводиться – это можно назвать виртуальным дарвинизмом, – алгоритм отбрасывает неполноценные решения и позволяет передать свои характеристики следующему поколению только лучшим. Как и в случае с другими алгоритмами оптимизации, в результате мы можем получить локальный оптимум, любое изменение которого приведет к снижению качества, но не достичь наилучшего из возможных решений. К счастью, случайные процессы комбинирования и мутации позволяют отойти от этих локальных пиков и двигаться в сторону еще более совершенных решений.
Случайность, являющаяся столь важной особенностью генетических алгоритмов, играет определенную роль и в нашей повседневной жизни. Когда вам надоест прежний плейлист, постоянно прокручивающий одни и те же песни одних и тех же групп, вы можете нажать на кнопку Shuffle. В своей чистой форме функция просто выберет для вас случайную песню. Это как генетический алгоритм без стадий отбора и комбинации, но с высокой степенью мутации. Возможно, это один из способов найти новую группу, которая вам понравится, но, возможно, вам придется пробираться через кучу песен Джастина Бибера или One Direction, чтобы найти что-то стоящее.
