Вселенная

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

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

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

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

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

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

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

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

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

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

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

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

* * *

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

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

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

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

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