Книга: Вселенная

Глава 34 Пробираясь по ландшафту

Глава 34

Пробираясь по ландшафту

В информатике, как и в жизни, часто встречается простая задача: найти конкретный элемент, выбрав его из множества вариантов. Рассмотрим задачу коммивояжера: имея список городов и расстояний между ними, нужно проложить между этими городами кратчайший маршрут, на котором каждый город будет встречаться только один раз. Задачу можно перефразировать. Возьмём список городов и расстояний между ними. Далее сделаем новый список, перечислив в нём все возможные маршруты, по которым коммивояжер заходит в каждый город как минимум один раз (это будет невероятно длинный, но всё-таки конечный список). Какой маршрут будет кратчайшим?

Поисковый алгоритм — это чётко сформулированная процедура для нахождения нужного элемента в списке объектов. Разумеется, можно перебрать все элементы один за другим, каждый раз спрашивая: «Этот?». Такой способ, вероятно, будет сложен, так как при поиске ответов на вполне разумные вопросы порой требуется отсортировать немыслимо огромные списки. В случае с задачей коммивояжера число возможных маршрутов возрастает примерно как факториал от числа охватываемых городов. Факториал числа n равен произведению 1 умножить на 2 умножить на 3 умножить на 4... умножить на (n ? 1). Таким образом, в случае с двадцатью семью городами потребуется проверить около 10²⁸ маршрутов. Если бы поиск шёл со скоростью миллиард маршрутов в секунду, то занял бы больше времени, чем существует наблюдаемая Вселенная.

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

Естественный отбор можно сравнить с поисковым алгоритмом. Эволюция решает следующую задачу: какой организм сможет наиболее эффективно размножаться и выживать в данной конкретной среде? Только поиск охватывает не организмы как таковые, а их геномы либо конкретные нуклеотидные последовательности в нити ДНК. В человеческом геноме содержится около трёх миллиардов нуклеотидов. Это много по сравнению, скажем, с бактериальным геномом, где насчитывается лишь несколько миллионов нуклеотидов. Но давайте не будем задаваться: у некоторых цветковых растений в ДНК имеется более 100 миллиардов пар нуклеотидных оснований. Некоторым организмам удастся выжить и размножиться, другим — нет. Однако как среди многих поколений найти такие последовательности ДНК, которые повышают шансы организма на выживание?

С вычислительной точки зрения эта проблема считается сложной. Каждый из трёх миллиардов наших нуклеотидов может соответствовать одной букве: А, Ц, Г или Т. Общее число возможных комбинаций в ДНК такого размера, как у человека, составляет не четырежды три миллиарда (что было бы ещё не так плохо), а четыре в степени три миллиарда: 4^3000000000, то есть единица, за которой следует примерно два миллиарда нулей. Это ошеломительно, грандиозно огромное число. Кроме того, оно завышено; некоторые нуклеотидные последовательности функционально идентичны друг другу, а из абсолютного большинства последовательностей организм бы просто не получился. Можно подсчитать гены, а не нуклеотиды; в таком случае число значительно уменьшится, хотя каждый ген допускает значительно больше четырёх форм. Итак, число остаётся огромным, а из-за взаимозависимости различных генетических функций любые подсчёты такого рода остаются в некоторой степени неопределёнными. Итак, при любом мыслимом раскладе проблема поиска «лучшего» организма путём перебора всех возможных геномов представляется титанической.

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

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

* * *

Можно наглядно представить проблему эволюционного поиска как целый ландшафт, участки которого соответствуют той или иной степени приспособленности. Идея такова: можно присвоить любому геному, существующему в определённой среде, числовое значение, которое будет соответствовать его «приспособленности». Это значение характеризует, с какой вероятностью организм, обладающий таким геномом, сможет оставить потомство в данной среде. Можно визуализировать приспособленность как холмистый ландшафт, со склонами и долинами, где «направлениям в пространстве» соответствуют различные формы, которые может принимать каждый ген, а «высоте над уровнем моря» — приспособленность. На самом деле, вычерчивая ландшафт приспособленности, мы учитываем всего один-два гена, но при этом держим в уме, что на самом деле речь идёт о 25000-мерном пространстве, по одному измерению на каждый ген. «Холм» с высоким значением приспособленности соответствует такому организму, который с очень высокой вероятностью оставит потомство (и чем больше, тем лучше), а в долине с низким значением приспособленности находится геном, передача которого последующим поколениям маловероятна.

Можно сказать, что эволюция подталкивает популяции, заставляя их закрепляться всё выше и выше в ландшафте, отдавая предпочтение тем генам, которые порождают более приспособленные организмы. Разумеется, это упрощение. Речь не идёт о едином фиксированном ландшафте приспособленности, который был бы актуален для всех видов всегда и в любых ситуациях. Как максимум можно рассматривать одну популяцию в конкретной экосистеме. Контуры ландшафта будут зависеть от всех свойств этой экосистемы. Виды появляются и вымирают, физические условия изменяются, поэтому со временем меняется и ландшафт. Тем не менее некоторые черты экосистемы могут оставаться стабильными достаточно долго, поэтому «фиксированный ландшафт» — удобная метафора для визуализации происходящих событий.

Биологи рассматривают мир не так, как физики. Концепция ландшафта существует и в физике — например, если нас интересует, в каком фазовом состоянии окажется система при заданных температуре и давлении. Однако физики, рассуждая о ландшафте, всегда имеют в виду шар, катящийся под уклон. Соответственно самыми предпочтительными точками ландшафта являются минимумы функции, нанесённой на графике (как правило, речь идёт о функции энергии), поскольку шары всегда катятся вниз. Биологи же размышляют о ловких горных козлах или о детях, играющих в «царя горы». Для них наиболее предпочтительными точками ландшафта являются максимальные значения приспособленности.

Вот как эволюция прощупывает ландшафт приспособленности, отыскивая наивысшие пики. Имеется популяция особей определённого вида, эти организмы занимают близкие точки на ландшафте. Особи рождаются, при удачном раскладе оставляют потомство и умирают. У их потомков будут уже немного иные геномы, и на ландшафте они также будут располагаться иначе — недалеко от родителей, но не там же, где они. Те, кто окажутся ниже по склону, получат меньше шансов оставить потомство, чем те, кто будет выше. Поколения сменяются, и вся популяция постепенно движется вверх по склону.

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

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

* * *

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

Возьмём несколько произвольно выбранных алгоритмов и попробуем с их помощью решить задачу. Далее выберем те из них, которые справляются с задачей лучше всего, и позволим им «мутировать», а по возможности также позволим им смешиваться с другими успешными алгоритмами. Отбросим все неуспешные стратегии и повторим процесс. Изучаемая популяция алгоритмов будет постепенно подниматься вверх по соответствующему ландшафту приспособленности, определяемому в соответствии с тем, насколько успешно каждая из стратегий позволяет решать ту проблему, которую она должна решать. (Фактически именно так Бэртел и Шостак искали конфигурации РНК, которые могли действовать в качестве катализаторов.)

Генетические алгоритмы прекрасно иллюстрируют некоторые интересные черты эволюции как генератора стратегий. Один подобный пример предложила специалист по информатике Мелани Митчелл. Она предлагает рассмотреть Робби — виртуального робота, живущего в простом мире. Этот мир представляет собой сетку размером 10?10 клеток. Прошлым вечером Робби закатил вечеринку, поэтому теперь по всей сетке разбросаны пустые банки. Наша задача — изобрести такую стратегию (однозначный набор инструкций, описывающих каждый шаг), которая позволит роботу Робби собрать все банки, разбросанные по сетке.

Можно предположить, что Робби достаточно переходить от одной банки к следующей и вся проблема заключается в том, чтобы найти кратчайший путь. Однако Робби имеет два существенных недостатка (возможно, слишком сильно погудел минувшей ночью). Во-первых, он не слишком далеко видит. Стоя в клетке, Робби может заметить банку в этой же клетке, а также в смежных клетках, расположенных непосредственно к северу, югу, востоку или западу от его клетки. Но этим всё ограничивается: он не может заметить банки ни в клетках по диагонали от себя, ни в каких-либо ещё более удалённых клетках.

Слева: мир робота Робби. Это сетка, состоящая из квадратных ячеек; некоторые из них пусты, а в других валяются банки. Поле зрения Робби выделено. Справа: Робби стоит в клетке с банкой, а поблизости также разбросаны банки

Итак, логично предположить, что Робби должен двигаться в соответствии с неким паттерном, систематически осматривая сетку и подбирая все банки, которые заметит. Но у Робби есть и второй недостаток: он абсолютно ничего не запоминает. Он не помнит, где уже был, какие банки подобрал; не помнит даже, что делал секунду назад. Он планирует следующий шаг, располагая информацией лишь о настоящем моменте, то есть не может решить «пойду сначала на восток, а потом поверну на юг», поскольку в таком случае учитываются два шага кряду.

С учётом всех этих ограничений очень просто перечислить все возможные стратегии, которых может придерживаться Робби. Он знает о пяти клетках: его собственная и ещё четыре, по одной в каждом из направлений, соответствующих сторонам света. Каждая клетка может быть в одном из трёх состояний: пуста, с банкой, либо располагаться за стеной (куда Робби попасть не может). «Состояние» Робби — это список всех параметров, которые известны ему о каждой из пяти доступных клеток: всего 3⁵ = 243 состояния. Робби может совершать семь действий: подбирать банку (если найдёт), перейти в одну из четырёх клеток по сторонам света, двинуться в произвольном направлении или просто стоять и ничего не делать.

Стратегия Робби — просто описание одного из семи действий для каждого из 243 состояний. Таким образом, общее число возможных стратегий составляет 7²⁴³, или примерно 10²⁰⁵. Вы не будете испытывать все стратегии подряд, просто чтобы найти оптимальную.

Можно проявить сообразительность и спроектировать такую стратегию, которая, на ваш взгляд, хорошо подходит для решения задачи. Именно так и поступила Митчелл: выбрала базовую стратегию, которая казалась «довольно хорошей — пусть, возможно, и не лучшей». Подход был прост: если Робби оказывается в клетке с банкой, он подбирает банку. Если клетка пуста, он отправляется искать банки в соседних клетках. Если в одной из них найдётся банка, то он переходит в эту клетку. Если ни в одной из соседних клеток банок не окажется, то делается шаг в произвольном направлении. Если банки найдутся в нескольких соседних клетках — Робби передвигается в указанном направлении. Назовём эту стратегию «контрольной». Как мы и рассчитывали, контрольная стратегия позволяет неплохо справиться с задачей: при большом числе попыток её КПД составляет около 69% оптимума.

В качестве альтернативы можно воспользоваться эволюционным методом и развивать стратегию путём направленной эволюции. Конкретная стратегия для Робби подобна конкретному списку нуклеотидов в спирали ДНК. Это дискретная строка, несущая информацию. Можно искусственно её развивать: начав с некоторого числа произвольно подобранных стратегий, позволить им поработать некоторое время, а потом выбрать оптимальные. Затем мы делаем по нескольку копий каждой «уцелевшей» стратегии, позволяем этим стратегиям «мутировать», случайным образом изменяя несколько конкретных действий, задаваемых каждой стратегией для того или иного состояния. Можно даже сымитировать половое размножение, разрезая стратегии и складывая новую стратегию из фрагментов двух старых. Процесс напоминает эволюцию. Можно ли подыскать для Робби такие стратегии, которые окажутся лучше «довольно хорошей», разработанной специально?

Да, можно. Эволюция легко даёт более эффективные стратегии, чем замысел. Спустя всего 250 поколений компьютер справлялся с задачей не хуже, чем это позволяла контрольная стратегия, а спустя 1000 поколений результат составил почти 97% оптимума.

После того как генетический алгоритм разовьётся, мы можем отмотать ситуацию назад и рассмотреть её этапы, чтобы понять, как алгоритм стал настолько эффективен. Самая сложная часть такого обратного проектирования всё явственнее переходит в разряд насущных проблем. Многие компьютерные программы работают в соответствии с генетически сформированными алгоритмами, которых, в сущности, не понимает ни один программист, а об этом уже страшно подумать. К счастью, Робби располагает довольно ограниченным числом вариантов, и мы с лёгкостью можем уяснить, что происходит.

Наилучшие стратегии Робби оптимизируют контрольную несколькими умными способами. Рассмотрим ситуацию: Робби стоит в клетке с банкой, а в клетках к востоку и к западу от него тоже лежат банки. Естественно, базовая стратегия требует, чтобы он поднял банку. Однако представьте себе, что будет дальше. Сделав шаг на восток или на запад, Робби, соответственно, потеряет из виду ту банку, которая лежала в противоположном направлении. Генетический алгоритм, хотя и был сформирован на основе только лишь случайной изменчивости и отбора, «догадался об этом» и выработал более выигрышную стратегию. Когда Робби оказывается в середине последовательности из трёх банок, он не берёт ту, что лежит в его клетке, а вместо этого уходит на восток или на запад, пока не достигнет края последовательности банок. Только тогда он подбирает последнюю банку. Затем, что логично, он отправляется обратно по ряду клеток с банками, подбирая банки по пути. Оказывается, этот и другие варианты проектирования гораздо более эффективны, чем «очевидная» контрольная стратегия.

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

* * *

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

Ландшафт приспособленности с изолированным пиком; найти такой пик путём естественного отбора сложно

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

Взяв отдельный геном, как узнать, что он соответствует изолированному «пику» на ландшафте приспособленности? Такие пики существуют почти наверняка, хотя могут встречаться реже, чем кажется на первый взгляд. В двумерном ландшафте отдельно стоящие пики будут встречаться практически неизбежно, но если в рассматриваемом пространстве больше измерений, например 25 000, по одному на каждый человеческий ген, то путей от одного пика к другому может оказаться значительно больше.

Возможный критерий геномов, который не мог сформироваться эволюционным путём, был предложен Майклом Бихи, критикующим теорию естественного отбора и выступающим в пользу теории разумного замысла. Пытаясь показать, что некоторые организмы не могли возникнуть путём обычной дарвиновской эволюции, Бихи выдвинул концепцию «неуменьшаемой сложности». По определению Бихи система, обладающая неуменьшаемой сложностью, — это такая система, функционирование которой зависит от взаимодействия множества элементов, причём каждый элемент необходим, чтобы система продолжала работать. Идея заключается в том, что некоторые системы состоят из столь тесно взаимосвязанных элементов, что не могли возникнуть поступательно; они должны были появиться сразу и целиком. Мы полагаем, что эволюция этого обеспечить не может.

Проблема в том, что неуменьшаемую сложность не так просто измерить. Чтобы проиллюстрировать этот феномен, Бихи приводит пример с обычной мышеловкой. В мышеловке есть пружинный механизм, спусковой рычаг и т. д. Уберите любую деталь, говорит он, и мышеловка станет бесполезной; она могла быть только спроектирована, но не могла образоваться в результате мелких изменений, каждое из которых имело бы какую-то пользу.

Вероятно, вы уже догадываетесь, что было дальше. Как минимум двое учёных (Джон Макдональд и Алекс Фиделибус) представили возможные «эволюционные пути», по которым могла развиваться мышеловка. Они спроектировали ряд моделей, изначально очень простых и постепенно усложнявшихся, но все эти мышеловки были рабочими. На каждом этапе мышеловка работала чуть лучше, чем на предыдущем, несмотря на то что различия между этапами были минимальны. На последнем этапе получилась настоящая современная мышеловка. В довершение всего Йоахим Дагг исследовал, как именно менялись с годами реальные мышеловки, показав, что (несмотря на то, что мышеловки являются плодом разумного замысла) они развивались постепенно, а не возникали сразу. Выражаясь словами Дагга, «популяции мышеловок изобилуют всеми предпосылками для эволюции» (изменчивостью, передачей информации и отбором).

Постепенная эволюция сложной мышеловки, показанная Джоном Макдональдом. Эволюция начинается с простой проволочки, которая смыкается, если её задеть. Постепенно мышеловка усложняется — в ней появляются: пружина; приманка, которая сначала просто лежит рядом, а потом закрепляется на дощечке; длинный «молоточек»; растяжка; скрепка, поддерживающая растяжку; короткая пружина, которая затем ещё более укорачивается; отдельная ловушка, удерживающая растяжку, отграничивающая молоточек от пружины, и, наконец, ещё более совершенная ловушка со спусковым механизмом

* * *

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

Одна из формулировок этого убеждения восходит ещё к Уильяму Пейли, предложившему аналогию с часовщиком. Пейли писал об этом ещё до того, как в науке появился Дарвин, но он приложил определённые усилия, чтобы опровергнуть любых будущих мыслителей-дарвинистов, которые стали бы отрицать центральную роль Бога, объясняя сложность мира. Он очень любил упоминать глаз. Слово «глаз» более двухсот раз фигурирует в работе Пейли «Natural Theology: or, Evidences of the Existence and Attributes of the Deity, Collected from the Appearances of Nature» («Естественная теология или свидетельства существования Бога и Его атрибутов, собранных из явлений природы»). Множество мелких компонентов, которые должны работать вместе, бесспорная функциональная эффективность глаза, те механизмы, которые предусмотрены в организме для защиты и сохранения глаз, — с точки зрения Пейли, всё это убедительно свидетельствовало о том, что существование глаз подразумевает «необходимость разумного Создателя».

По-видимому, в истории жизни глаза независимо возникали несколько десятков раз. Несложно проследить правдоподобные пути развития глаза. Поглощение фотонов — одно из простейших действий, совершаемых живыми существами. Эта способность может быть локализована в светочувствительных участках или «глазных пятнах», которые найдены у некоторых одноклеточных организмов. Учитывая, что такой организм способен реагировать на свет, это может представлять преимущество, поскольку помогает сориентироваться, откуда падает свет. Простейший способ реализации этого — поместить глазное пятно в утопленную чашечку, как у некоторых плоских червей. Углубляя чашечку, пока она не превратится в практически сферическую полость, организм приобретает примитивную линзу, примерно как в камере-обскуре; такая встречается у некоторых современных моллюсков. Если заполнить такую глазницу жидкостью, то улучшится и защита, и фокусировка. Многие этапы на этом пути не преодолеваются «единым прыжком»; напротив, эволюция может заимствовать механизмы, ранее использовавшиеся для других функций и возникшие по иным причинам.

Итак, идея ясна: мало того что глаз может сформироваться поэтапно, с постепенным усложнением и нарастанием приспособленности, так мы ещё и наблюдаем такое развитие на примере реальных существ, живущих сегодня. При этом у человеческого глаза при всей его изумительности есть очевидные недостатки, непростительные для талантливого инженера, но совершенно объяснимые в свете эволюции. Нервные волокна, передающие визуальную информацию в мозг, нерационально расположены перед сетчаткой, а не за ней. Глаз осьминога устроен лучше: у него и нервы, и сетчатка находятся сзади, поэтому у осьминога нет слепого пятна, которое есть у человека. Наша анатомия сохраняет следы случайных событий, происходивших на протяжении эволюции.