Кит Йейтс - Математика жизни и смерти. 7 математических принципов, формирующих нашу жизнь

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

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

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

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

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

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