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

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

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

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

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

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

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

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

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

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

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