СОГЛАСНО учению Дарвина, жизнь — это борьба, в кото­рой лишь сильнейшие выжи­вают и производят потомство. То, что утверждает жизнь, оказывается полезным и при решении задач на компьютере. В частности, програм­мы, использующие так называемые генетические алгоритмы, находят решения путем применения механиз­ма естественного отбора. Сначала алгоритм выдвигает возможные ре­шения. Затем, подобно биологиче­ским организмам, решения «скрещи­ваются», или обмениваются «гена­ми», в каждом поколении. Иногда происходят   мутации, или спонтан­ные изменения в генах. Только «сильнейшие» решения выживают и могут породить даже еще лучшие решения (см. статью Джона Холланда «Генетические алгоритмы» на с. 32). Чтобы понять, как работает гене­тический алгоритм, возьмем один из простейших и с его помощью прове­дем некоторые эксперименты.

 

 

 

 

 

 Для реализации своего алгоритма я вы­брал язык С, но с тем же успехом можно воспользоваться любым дру­гим языком программирования. У меня ушло около двух дней на то, чтобы написать версию, которую мы здесь рассмотрим. Больше всего времени я потратил на создание сер­висных процедур, чтобы программу было удобно выполнять, изменять   установку параметров, показывать результирующие популяции и статистические данные об их поведении.

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

 

 

 

 

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

Так как я впервые составлял гене­тический алгоритм, то решил воспо­льзоваться простой задачей, реше­ние которой мне было известно. Та­кой подход позволил мне упростить отладку программы и лучше понять работу алгоритма. Приспособить же его для решения более сложных за­дач не составляло особого труда.

Для эксперимента я выбрал задачу об отыскании максимального значе­ния функции f(x) = х + |sin(32x)|. Значения х (называемые областью определения функции) я ограничил диапазоном от 0 до т. Так что функ­ция имела 32 периода колебаний, прибавляемых к прямой линии f(x) = х (см. рисунок слева). По­скольку f(x) всегда положительна, ею можно воспользоваться как кри­терием жизнеспособности. Цель за­ключалась в том, чтобы найти ин­дивидуальную цепочку (значение х), которая давала бы наибольшее зна­чение для f(x).

Первым делом надо решить, ка­ким образом следует представлять структуры из области определения задачи, чтобы ваш генетический ал­горитм мог их обрабатывать. Я представил значения х в виде двоич­ных цепочек, как это описано в статье Холланда. В своих первона­чальных экспериментах я принял длину L цепочек равной 16 битам (L = 16). Таким образом, у меня бы­ло 2^L = 2¹⁶ = 65536 возможных зна­чений х.               (С увеличением длины це­почек повышается точность решения задачи.) Далее, значения х я поста­вил в соответствие этим 2^L цепоч­кам следующим образом: цепочка 0000000000000000    представляет х = 0,  0000000000000001  — это х = 1(p/2^L),  0000000000000010 — 2(p/2^L) и так далее вплоть до 1111111111111111, что соответствует максимальному значению области определения,     х = (2^L - 1) * (p/2^L) = p - p/2^L. (Само значение p

исключается, поскольку не остается цепочки для его представления.) Чтобы проверить свою интуицию, попробуйте сообразить, какое значе­ние     представляет цепочка 1000000000000000?

Короче говоря, двоичные цепочки представляют 2^L значений х, кото­рые равномерно распределены на интервале между 0 и p. Следова­тельно, алгоритм производит поиск в пространстве двоичных цепочек, или, что эквивалентно, — поиск сре­ди всех возможных значений х. Фрагмент программы на языке С на с. 84 (алгоритм отображения) пока­зывает, каким образом можно ре­ализовать это отображение от дво­ичной цепочки, которая хранится как элемент символьного массива в рам­ках языка С. Например, он отобра­зит 1000000000000000 (приблизитель­но) на точку p/2. Степень пригод­ности  индивидуальной  двоичной цепочки S как раз измеряется самой функцией   f(x),   где   х = МарStringToX(S).

Теперь, когда мы располагаем этим 'отображением двоичных цепо­чек на область изменения функции f(x), было бы поучительно рассмот­реть вопрос об отображении целе­вых областей так, как это было сде­лано у Холланда. Например, схема 0*************** состоит из всех цепочек, начинающихся с 0. Здесь * означает «безразличное» зна­чение: не важно, что стоит на этом месте — 0 или 1. Последовательность О*************** отража­ется на первую половину области определения, т. е. между 0 и p/2. По­следовательность 1**************** соответствует другой ее половине между p/2 и p. Для функ­ции f(x) среднее значение на области 1***************   выше,

чем на 0***************. Таким образом, в случайной популя­ции цепочек естественно ожидать, что средняя пригодность особей в первой области выше, чем среди представителей второй.

В моей реализации присутствуют также некоторые подпрограммы, прослеживающие за особями в лю­бой области, заданной пользовате­лем (например, все цепочки, начина­ющиеся с 1 или заканчивающиеся 001, и так далее). В каждом поколе­нии программа будет подсчитывать число особей, которые принадлежат каждой области. Она будет также вычислять среднюю пригодность среди этих особей, оценивая, таким образом, пригодность областей.

Чтобы проявить более глубокую интуицию, попытайтесь отразить другие последовательности на области изменения х и исследовать слу­чайные особи, которые попадают в эти области. Можете ли вы указать последовательности,  разбивающие каждое колебание в f(x) на восемь непрерывных   областей?   Какова средняя пригодность особей в этих областях?

ПОСЛЕ того как вы убедитесь, что первая версия вашей про­граммы работает правильно, можно добавить процедуры, реализующие основу генетического алгоритма. Алгоритм, которым я воспользовал­ся, представлен на с. 84.

Программа    EvaluatePopulation представляет собой простой цикл по всем особям популяции, присваива­ющий каждой из них значение f(x) как меру ее пригодности, или жиз­неспособности. Процедура DoTour-namentSelection проводит серию еди­ноборств между случайно выбран­ными особями и обычно (но не всег­да) копирует сильнейшую особь па­ры (i, j) в NewPop. Одна из версий этого алгоритма показана на с. 84. Здесь URandOl возвращает (равно­мерно распределенные)  значения между 0 и 1. В результате более пригодные особи имеют тенденцию производить более многочисленное потомство в новом поколении по сравнению с менее пригодными. Тем не менее может оказаться полезным копировать сильнейшую особь но­вых популяций в каждом поколении.

Заметим,  что  при  значениях
Urand0l, больших 0,75, влияние фактора отбора становится более сильным (менее пригодным цепоч­кам становится труднее попасть в NewPop), в то время как меньшие значения приводят к снижению вли­яния механизма отбора. Если испо­льзуется значение 0,5, то никакого отбора, вообще говоря, не будет.

Процедура ModifyPopulation до­лжна случайным образом произво­дить операцию скрещивания на не­которых парах в NewPop; обычно процент скрещивания равен 75 (т. е. скрещиваются 75% пар). В своем ал­горитме я пользовался операцией «одиночной  точки»,  которая  в статье Холланда осуществляла кроссинговер. В моей версии также име­ет место операция мутации, которая изменяет небольшое, случайно вы­бранное число битов отдельных це­почек, подставляя 0 вместо 1, и на­оборот. Процент мутаций обычно составляет 0,5% на бит — другими словами, каждый бит имеет вероят­ность подвергнуться мутации, рав­ную 0,005.

После того как работа по реализа­ции алгоритма завершена, можно приступать к экспериментам. По­пробуйте запустить систему со слу­чайной популяцией из 200 особей и продолжайте эксперимент в течение 50 поколений, собирая статистику о том, как изменяется средняя пригод­ность, и отмечая наивысшие резуль­таты, достигнутые отдельными осо­бями в каждом поколении. Вы можете

жете    сравнивать    полученные результаты для различной числен­ности популяций и различных про­центов скрещивания и мутаций. Мне интереснее всего было сравнивать средние результаты по нескольким прогонам программы при различ­ных исходных значениях, вырабаты­ваемых   генератором   случайных чисел.

Один из наиболее полезных экспе­риментов для понимания динамики эволюционирующих популяций за­ключается в том, чтобы прослежи­вать за особями из'восьми областей, разбивающих 32 периода f(x), о ко­торых я говорил выше. Эти области определяются последовательностями

*****000********, *****001******** и так далее до *****111********. Заме­тим, что последовательности *****011******** и
*****100******** лежат в централь­ной части каждого пика, которая со­держит точки наибольшей при­годности.

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

Пользуясь этими восемью обла­стями, я пытался проследить, на­сколько хорошо алгоритм настраи­вается

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

При размере популяции в 400 осо­бей, проценте скрещивания 75% и проценте мутаций 0,1% программа подтверждала предсказания теории в 67% случаев. Я пришел к выводу, что, чем выше процент скрещивания и мутаций и чем меньше числен­ность популяции, тем реже под­тверждаются предсказания. Эти ре­зультаты можно разумно объяс­нить, как мне кажется, тем, что высокая частота скрещивания и му­таций способствует разрешению хо­роших «строительных блоков», и для популяций меньшего размера ошибки в случайных выборках «раз­мывают» предсказываемые законо­мерности.

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

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

аналогично тому, как в естественной эволюции различные виды населяют свои ниши.

Конечно, вы можете применять генетический алгоритм не только к задачам оптимизации. Мне понадо­билось всего около четырех часов на то, чтобы изменить описанную здесь программу и создать на ее основе версию, в которой особи представляют стратегии игры для одной из разновидностей «Дилеммы заключенного». В этой игре каждый из двух заключенных стоит перед выбором: либо проявить солидар­ность с соучастником (храня молча­ние о совместном преступлении) и получить три года, либо попытаться выйти на свободу, выдав сообщни­ка. К сожалению, вам не известно, что собирается делать партнер: если вы молчите, а он выдает вас, то вы получаете 10 лет, а он выходит на свободу. Если же оба выдают друг друга, то каждый получает по семь

Мой модифицированный генетиче­

ский алгоритм исследовал стратегии этой игры множество раз, играя с одним и тем же партнером. Двоич­ная цепочка каждой особи представ­ляет два числа (р, q), где р — веро­ятность того, что особь будет мол­чать,  если партнер молчал  в предыдущей партии, a q — вероят­ность того, что особь промолчит, если партнер ее выдал. Например, (1;0) — это стратегия «око за око», а (0,1; 0,1) приблизительно соответ­ствует стратегии «всегда выдавай».

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

(метки), ассоциированные с игрока­ми, придерживающимися стратегии «око за око». Таким образом, они могут процветать, отыскивая в каче­стве партнеров солидарных особей и избегая предателей.

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

Если вы желаете получить копию оптимизационной программы (напи­санной на языке С), пошлите запрос на английском языке по адресу:

Amateur Scientist, Scientific American, 415 Madison Avenue, New York, NY 10017-1111.