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

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

Муравьиный алгоритм – всего лишь один из целого семейства так называемых алгоритмов роевого интеллекта, вдохновленных природой. Стаи скворцов или косяки рыб способны очень резко – и при этом согласованно и синхронно – менять направление движения, несмотря на то что каждая особь может коммуницировать лишь с небольшим числом особей по соседству. Информация о появлении хищника неподалеку от одного края косяка рыбы, например, быстро распространяется на другой его край. Заимствуя эти принципы локального взаимодействия, разработчики алгоритмов могут использовать огромные «стаи» исполнительных устройств, объединенных в информационную сеть, для исследования окружающей среды. Их быстрое, «роевое» взаимодействие позволяет им узнавать об открытиях, сделанных другими участниками «роя» в поисках оптимального окружения.

Самый известный природный алгоритм – эволюция. В своей простейшей форме эволюция объединяет признаки родителей, чтобы производить детей. Дети, которые лучше подготовлены к выживанию и размножению в своем окружении, в следующем поколении передадут свои признаки бóльшему числу потомков. Иногда между поколениями происходят мутации, что привносит в популяцию новые признаки, которые могут быть лучше или хуже уже имеющихся. Для создания биоразнообразия, способного решить некоторые из самых сложных проблем планеты, достаточно исполнять всего лишь три простые процедуры – отбирать, комбинировать и мутировать.

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

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

Популяция обыкновенной рыжей белки в Великобритании является классическим примером. С ее острыми когтями, гибкими задними лапами и длинным хвостом, необходимым для равновесия, она хорошо приспособлена для лазания по деревьям в поисках пищи. Ее зубы непрерывно растут на протяжении всей жизни, позволяя белкам разгрызать твердую наружную оболочку орехов, не теряя при этом резцы. Казалось, она идеально приспособилась к окружающей среде – но тут появился еще более приспособленный родственник. Значительно более крупная серая белка находит и съедает больше пищи, а также более эффективно переваривает и хранит ее. Хотя серые белки никогда не нападали на рыжих и не убивали их, превосходная адаптация быстро сделала их вид доминирующим в широколиственных лесах Англии и Уэльса; они превзошли рыжих в межвидовой конкуренции и захватили их экологическую нишу. Наше восприятие «образцовой» адаптации отдельно взятых видов, вероятно, продиктовано не столько реальными результатами эволюционного поиска оптимального варианта, сколько нашим ограниченным представлением о том, что такое по-настоящему идеальное решение.

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

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

Генетический алгоритм начинается с генерации заданного числа потенциальных решений проблемы. Эти решения являются родительским поколением. Для задачи о рюкзаке это родительское поколение создает списки пакетов – наборы предметов, которые могут поместиться в рюкзак. Алгоритм ранжирует решения по тому, насколько хорошо они решают проблему. В задаче о рюкзаке критерием ранжирования становится прибыль, которую может принести каждый набор предметов, помещающийся в рюкзак. Затем выбираются два лучших решения – наборы, приносящие наибольшую прибыль. Некоторые наборы из одного хорошего решения отбрасываются, а остальные комбинируются с некоторыми наборами из другого хорошего решения. Существует также возможность «мутации» – случайно выбранный набор может быть удален из рюкзака и заменен другим. Как только в новом поколении создано первое дочернее решение, выбираются еще два наиболее эффективных родительских, которые будут воспроизводиться. Таким образом, лучшие решения в родительском поколении передают свои характеристики бóльшему количеству дочерних решений в следующем поколении. Этот комбинированный процесс повторяется до тех пор, пока не возникнет достаточно «дочек», чтобы заменить все оригинальные решения в родительском поколении. Сделавшие свое дело родительские решения уничтожаются, а дочерние переходят в статус родительских и весь цикл «отбор – комбинация – мутация» начинается заново.

Дочерним решениям присущ случайный характер, поэтому алгоритм не гарантирует, что все «дочки» будут лучше своих «родителей». Вообще-то, многие окажутся даже хуже. Однако, выбирая, какие из дочерних решений станут воспроизводиться – это можно назвать виртуальным дарвинизмом, – алгоритм отбрасывает неполноценные решения и позволяет передать свои характеристики следующему поколению только лучшим. Как и в случае с другими алгоритмами оптимизации, в результате мы можем получить локальный оптимум, любое изменение которого приведет к снижению качества, но не достичь наилучшего из возможных решений. К счастью, случайные процессы комбинирования и мутации позволяют отойти от этих локальных пиков и двигаться в сторону еще более совершенных решений.

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

Многие музыкальные стриминговые сервисы сегодня предлагают гораздо более сложные алгоритмы, чтобы разнообразить ваш плейлист. Если в последнее время вы часто слушали Beatles и Боба Дилана, генетический алгоритм может предложить вам попробовать группу, которая сочетает в себе некоторые характеристики этих двух исполнителей, – например, Traveling Wilburys (супергруппа Боба Дилана и Джорджа Харрисона). Пропуская песни или прослушивая их целиком, вы сигнализируете о том, насколько они вам подходят, давая алгоритму понять, из каких решений он должен исходить впредь.

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