Вселенная. Происхождение жизни, смысл нашего существования и огромный космос

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

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

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

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

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

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

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

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