Шон Кэрролл - Вселенная

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

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

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

* * *

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

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

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

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

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

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

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

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

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