Подобно мушкам-дрозофилам, компьютерные программы скрещиваются, обмениваясь фрагментами своего кода; их потомство подвергается мутациям и жестокому отбору; и так повторяется много раз, чтобы новое стало непостижимо эффективнее старого. Это не кошмарный сон марксиста 40-х годов, надорвавшегося в борьбе с генетикой и кибернетикой, а произведение двух названных "лженаук" - ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ.

В траве сидит лягушка, смотрит своими выразительными глазками на реальный мир и реагирует на его объекты. Как? Да без философий и довольно-таки незамысловато. Не движется - игнорировать. Движется, но далеко - игнорировать. Движется, близко, большое - спасаться. Движется, близко, маленькое, полосатое - игнорировать. Движется, близко, маленькое, не полосатое - атаковать. Этими да еще сотней подобных врожденных алгоритмов поведения и определяется нехитрая жизнь лягушки. Кто ее научил жить так? Кто эти алгоритмы разработал? Креационист скажет, что бог не только создал всё сущее, но и озаботился запрограммировать всё сразу и на все случаи. Этой гипотезой в данной статье мы пользоваться не будем. Спросим лучше эволюциониста. Но он ответит вопросом: а что можно сказать о лягушке с алгоритмами поведения, существенно отличающимися от перечисленных выше? О лягушке, которая шарахается от пня и тучи, добровольно лезет в пасть змеи и под каблук ботинка, глотает пчел и ос и игнорирует мух и комаров? Несомненно, жить она будет тяжело, но недолго, в связи с чем ее неадекватные алгоритмы поведения не сохранятся ни в веках, ни даже в ближайших поколениях. Природа не скупится ни на время, ни на жертвы, когда программирует жизнь. Разумеется, это утверждение относится не только к лягушкам и не только к стадии "бета-тестирования" уже сформировавшихся организмов. Так, например, у человека, царя природы, 20% беременностей прерывается естественным выкидышем на сроке до 14-й недели, то есть еще в процессе "альфа-тестирования" будущего организма, причем генетические анализы свидетельствуют, что это происходит чаще всего "к счастью". Природа беспощадно уничтожает не только неудачные "релизы" и "версии" живых программ - отдельные организмы, но и целые неудачные семейства живых программ - виды организмов. Сейчас Землю населяет около 5 миллионов видов животных и растений, но за долгую историю жизни вымерло около 5 миллиардов видов. Конечно, такой метод программирования может показаться весьма расточительным. Зато живые программы, написанные природой за 3,5 миллиарда лет, имеют просто колоссальную эффективность.

Можно ли назвать живой организм программой? Можно и нужно. Каждый организм, от вируса до кита, от вымершего трилобита до ныне процветающего человека, - это прежде всего от нескольких килобайт до нескольких сотен мегабайт генетической информации, записанной универсальным генетическим кодом в длинных молекулах ДНК (за исключением ретровирусов типа СПИД, где вместо ДНК используется РНК). Генетический код не двоичный, а четверичный, то есть информация представляется последовательностью оснований четырех видов: A - аденин, G - гуанин, T - тимин и C - цитозин (в РНК вместо T используется U - урацил). Один "байт" генетического кода - это тройка оснований (например, TAG), кодирующая либо одну из 20 аминокислот, из которых собираются все белки всех живых организмов, либо команды "start" и "stop", управляющие сборкой белков. Генетический код избыточен, поскольку большинство аминокислот кодируется несколькими различными тройками оснований. Генетическая информация - это полная программа сборки живого организма и обеспечения всех аспектов его функционирования. Задумайтесь над этим. Что записано в ДНК вируса гриппа? Только то, что, будучи соответствующим образом введенной в мышечную клетку, эта ДНК заставит клетку изготовить тысячи и миллионы вирусов гриппа, идентичных родительскому, то есть таких, которые уже доказали на практике, что они способны обмануть иммунитет, ввести свою ДНК в мышечную клетку и заставить ее... У попа была собака, он ее любил... Впрочем, все не так уж однообразно. Иммунитет совершенствуется, а вирусы мутируют. Вирусу гриппа уже практически некуда мутировать: за XX век он исчерпал почти все удачные вариации своего генетического кода, убив при этом 60 миллионов человек - больше, чем обе мировые войны. Но и люди в долгу не остались, хотя и не подсчитывают, во сколько септиллионов жертв обошлось вирусу гриппа то, что он пока существует. А что записано в ДНК человека? Повторюсь: полная программа сборки и функционирования человеческого организма - от первого деления оплодотворенной яйцеклетки до смерти. Например, возрастные особенности поведения и телосложения, таланты и слабости, внешняя привлекательность и способность к обучению, родительские инстинкты и иммунитет. Пусть читатель продолжит. При этом не следует преувеличивать роль воспитания и образования и забывать о том, что у человека и шимпанзе генетическая информация идентична на 98%, и о том, что некоторые формы слабоумия вызываются единственным дефектом единственного гена.

Как же природа пишет свои живые программы? Удивительно просто, неразумно и не так, как программируют люди. Генетическое программирование заключается в многократном циклическом повторении трех действий: 1) размножение, 2) мутирование, 3) отбор. Размножение бывает бесполое и половое. При бесполом размножении генетическая информация единственного родителя передается его многочисленным потомкам без изменений, и поэтому вся нагрузка по модифицированию живой программы ложится на мутации. При половом размножении генетическая информация, взятая от двух родителей, рекомбинирует, то есть ДНК потомства составляется из фрагментов ДНК его родителей. Природа везде, где только может, отдает предпочтение половому способу размножения: более эффективного средства для создания новых программ из старых она не изобрела. Для успешного скрещивания живые программы вовсе не обязаны делиться именно на два типа - мужской и женский пол: у дрожжей, например, 5 полов, а у одного вида слизевиков - 14. Но родителей всегда только два, причем генетические коды их потомства состоят из генетических кодов их обоих. Хотя слово "мутация" навязчиво рифмуется со словом "радиация", это просто любая ошибка чтения-записи-хранения генетического кода. Именно мутирование создает новую генетическую информацию. Случайная замена одного основания другим приводит к тому, что кодируемый белок приобретает новые свойства, худшие или лучшие. Случайно потерянный фрагмент генетического кода может быть как жизненно важным, так и лишним или даже вредным. Случайная вставка постороннего фрагмента генетического кода (от вируса или от другого участка той же ДНК) приводит к удлинению ДНК и кодируемых белковых цепей - это тот путь, который привел от простеньких первых организмов к сложнейшим современным. Итак, размножением и мутированием природа делает из старых живых программ новые. Но эти новые в среднем не лучше, а хуже старых (подчеркиваю - в среднем), потому следующий шаг генетического программирования - это жестокое тестирование живых программ, то есть отбор. Каждая ДНК должна реализовать себя "в белке", превратиться в эффективно функционирующий организм. Только наилучшие из живых программ выживут и размножатся, чем и начнут следующий цикл генетического программирования.

Этот длинный экскурс в биологию необходим для того, чтобы читатель увидел глубокие аналогии между генетикой и кибернетикой и осознал не менее глубокую разницу в подходах к программированию у природы и у людей. Создавая программу, человек знает не только то, что программа должна сделать, но и то, как она это сделает, то есть полный алгоритм решения проблемы. А если алгоритм не известен, то как тогда программировать? Проблем с неизвестными алгоритмами решения предостаточно, и некоторые из них мы рассмотрим ниже. Как их решать? Не попытаться ли сделать это методом природы? То есть сгенерировать случайную популяцию алгоритмов (разумеется, никудышных поначалу) и позволить им размножаться, модифицируя их код рекомбинациями и мутациями и отбирая в каждом поколении самые эффективные для решения данной проблемы. Первые попытки генетического подхода к программированию были предприняты на рубеже 50-х и 60-х годов; они основывались только на мутациях и отборе. В начале 60-х начали использовать механизм спаривания программ, но эта операция первоначально не соответствовала природной рекомбинации и касалась узкого множества свойств программ. В середине 60-х Дж.Х.Холланд ввел генетические алгоритмы, вполне аналогичные природным, и в течение следующего десятилетия разработал соответствующую систему генетического программирования, которую назвал системой классификатора (classifier system, CS). Понятие CS весьма широко: это система правил, по которым выполняются определенные действия всякий раз, когда удовлетворяются условия применения этих правил. Более конкретно CS можно представить как множество цепочек битов, в каждой из которых часть битов соответствует входу системы (условиям), а остальные биты - выходу (действиям), сами же цепочки - это правила. Например, упомянутые в начале статьи алгоритмы лягушки образуют CS вида {0***00, 10**00, 111*10, 110100, 110001}, где 0=нет, 1=да, *=безразлично, а порядок символов в цепочках такой: движется? близко? большое? полосатое? спасаться! атаковать! (Троичный код использован для краткости.) Любую программу, написанную на каком-либо стандартном языке программирования, можно переписать в виде CS, но смысла в этом нет: CS эффективны как раз там, где бессильно традиционное программирование. За 30 лет развития концепции генетических алгоритмов появилась тьма разнообразных толкований, модификаций, подходов, научных школ и околонаучных сект. Спорят о том, всегда ли применять мутации и какие, как эффективнее проводить скрещивание, какие правила отбора лучше, описывать ли генетические алгоритмы только линейными цепочками или допускать разветвленные структуры (чего природа не делает). Заинтересованный читатель может найти в Сети массу информации по ключевым словам "genetic algorithms" и "evolutionary programming". Я же ограничусь здесь лишь еще несколькими словами о научной стороне метода и его применениях.

Генетическое программирование решения некоторой проблемы начинается с определения формата генетического алгоритма, то есть числа и длин цепочек, составляющих CS. Затем случайным образом генерируется популяция из определенного числа (100-100000) CS нулевого поколения. В среднем эти случайные алгоритмы решают проблему "никак". Степень эффективности каждого алгоритма находится посредством оценочной функции, специально сконструированной под данную проблему (эта функция может определять прибыль в бизнесе, вероятность правильного ответа, счет в игре и т.д.). Лучшие алгоритмы награждаются тем, что они остаются жить в следующем поколении, а худших наказывают уничтожением, заменяя потомством лучших, получаемым путем случайной рекомбинации кодов. Для увеличения разнообразия добавляют мутации: биты кода случайным образом с низкой вероятностью (порядка 1/10000) меняются на противоположные. К полученному таким образом первому поколению CS снова применяют оценочную функцию. И так тысячи раз. Лучшие алгоритмы последнего поколения обеспечивают очень высокие значения оценочной функции, то есть хорошо решают проблему. Почему так получается? Генетический алгоритм - это последовательность битов. Все такие последовательности образуют пространство, а определенная на них оценочная функция как бы создает над этим пространством ландшафт с холмами и впадинами. Эффективный алгоритм - это точка, соответствующая вершине одного из самых высоких холмов; ее-то и надо найти. В нулевом поколении точки-алгоритмы рассыпаны по ландшафту хаотически и однородно, но после многих циклов отбора выжившие алгоритмы конденсируются возле вершин самых высоких холмов. Число алгоритмов в популяции невообразимо меньше числа точек пространства, потому кажется весьма вероятным пропустить искомые холмы, но этого не происходит благодаря механизму рекомбинации кодов: потомки рассыпаются по тем областям пространства, где родители не побывали. Вот так они и ищут вершины эффективности. Совсем как живые.

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

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

Дилемма заключенного - жемчужина теории игр, социологии и политологии. Эта простая игра моделирует сложные стратегии сотрудничества и предательства. Играют двое. Каждый игрок имеет два варианта поведения: пойти на сотрудничество с партнером или предать его. Если оба игрока предают друг друга, то получают по 0 очков. Если оба идут на сотрудничество, то получают по 3 очка. Если один хочет сотрудничать, а другой его предает, то обманутому 0 очков, а предателю - целых 5. Какой стратегии должен придерживаться игрок, чтобы при многократном повторении игры набрать побольше очков? Долгое время наилучшей из известных считалась стратегия "око за око": начать с сотрудничества, но перейти к копированию действия партнера в предыдущей игре, если тот прибег к предательству. Когда генетические алгоритмы применили для анализа дилеммы заключенного, они быстро переоткрыли стратегию "око за око", а далее эволюционировали к еще более эффективной новой стратегии "блеф": периодически заманивать партнера в сотрудничество и предавать его, а когда он перестает поддаваться на эту уловку - переходить к "око за око". Как в жизни.

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

Конструирование газовой турбины - ядро проектов по разработке новых реактивных двигателей, продолжающихся до 5 лет и стоящих до 2 миллиардов долларов. В конструкции турбины участвует более 100 параметров и 50 условий, так что существует около 10 в 380-й степени различных решений, а вот теории наилучшей конструкции нет. В одном довольно типичном случае инженеру понадобилось 8 недель вычислений на рабочей станции, чтобы достичь удовлетворительного варианта конструкции. Дальнейшее применение традиционного метода оптимизации позволило за сутки повысить эффективность конструкции турбины в 2 раза, после чего оптимизация завязла, достигнув вершины холма оценочной функции. Но этот холм оказался не самым высоким. За двое суток размножения и отбора генетические алгоритмы обнаружили другой холм, на 50% выше найденного традиционными средствами. В этом и заключается сила генетических алгоритмов: они не застревают на ближайшем локальном максимуме, а зондируют все пространство решений.

В заключение позволю себе одно философское замечание. У природы есть чему поучиться, а поучиться никогда не вредно. Но это вовсе не означает, что простым копированием методов природы можно далеко продвинуться в развитии техники. Спасибо природе за саму идею о летательном аппарате тяжелее воздуха, однако сто лет назад первые такие (нелетающие) аппараты совершенно напрасно махали крыльями по-птичьи. "Боинг-747" крыльями не машет. Я думаю, что то же будет и с генетическими алгоритмами. Когда по своему совершенству и масштабам применения они дорастут до современной авиации, у них останется очень мало исходных природных черт. А что добавится? То, до чего природа не додумалась, то есть самое интересное.

Сергей СЕРЫЙ