5. СНОВА О ГЕНЕТИЧЕСКИХ АЛГОРИТМАХ

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

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

Мы привыкли к тому, что какой-нибудь проект описывается одной единственной точкой из пространства переменных, которой однозначно соответствует опять-таки одна точка из пространства критериев. Этот примитивный уровень сложности представлений соответствует способу хранения генетической информации у гаплоидных организмов. У диплоидных организмов все значительнее интереснее — особь определена как бы на двух точках одновременно (отцовская и материнская хромосомы),

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

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

Это явление было понято еще в 20-х годах и описано С. С. Четвериковым, предложившим концепцию генетического груза, отягощающего популяцию информацией, хранящейся в рецессивных генах [28]. Часто диплоидную популяцию сравнивают с айсбергом, только верхушка которого, ассоциируемая с генами, проявившимися в фенотипе, видна над водой. Большая же часть айсберга скрыта от нашего взора. Но достаточно ситуации измениться, как вид айсберга изменится: он повернется другим боком, но не утонет.

Трудно утверждать, что представленная ниже версия эволюции диплоидной популяции точно следует биологическим теориям, но с ее помощью мы добились в основных чертах того, чего хотели [29,30].

Для начала мы ввели четырехбуквенный алфавит в котором и обозначают рецессивную 1 и рецессивный 0, а и — доминантную 1 и доминантный 0. Одновременно мы сформулировали правила полного доминирования при определении экспрессии генов вновь образованной особи, представленные на рис. 25 в виде таблицы разрешения конфликтов.

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

Рис. 25. Таблица разрешения конфликтов признаков в паре гомологичных генов

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

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

Использованное нами правило разрешения конфликта признаков несколько отличается от того, что предложил Хольштайн в 1971 [31] или Вонг в 1995 [32]. В отличие от них мы принимали во внимание степень относительной приспособленности родителей, чьи гаметы достались рассматриваемой особи, и в паре активных гомологов сохраняли активным ген более приспособленного родителя, а в паре пассивных оставляли пассивным ген менее успешного индивида.

Рис. 26. Пример использования таблицы разрешения конфликтов

Для определенности принято, что гамета А принадлежала родителю с более высоким индексом приспособленности

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

Рис. 27. (см. скан) Процесс образования зиготы потомка от зигот родителей

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

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

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

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

Рис. 28. (см. скан) Популяция гаплоидных генотипов, выродившаяся в начале координат

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

Рис. 29. Выродившаяся диплоидная популяция

Итак, внезапно целевая функция приобретает вид

Это одна из широко известных тестовых функций, предложенных Швефелем. Она имеет более 10 миллионов локальных экстремумов, глобальный же минимум по каждой из координат лежит в точке

Рис. 30 иллюстрирует процесс поиска экстремума диплоидной и гаплоидной популяциями по двум первым координатам вектора переменных.

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

К 500 поколению обе популяции достигают приблизительно одинакового фенотипического разнообразия, но дальше процесс развивается у них по—разному.

Рис. 30. (см. скан) Поиск экстремума тестовой функции (12) предварительно вырожденными диплоидной и гаплоидной популяциями: * — глобальный экстремум; — — субоптимальный минимум; • - особь популяции.

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

Сказанное особенно верно для гаплоидной популяции. Она быстро сходится, но если ей подворачивается хороший локальный экстремум, существует риск, что она застрянет в нем. К 3000 поколению гаплоидная популяция находит 4 лучших экстремума (глобальный, 2 субоптимальных и субсубоптимальный) и начинает концентрировать особей в их окрестностях. Но к 6000 поколению она полностью вырождается в субоптимальном минимуме по 1-ой и еще трем координатам вектора переменных, хотя по 2-ой и остальным пяти координатам находит глобальное решение.

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

В наших экспериментах диплоидная популяция тоже не всегда могла справиться с задачей, но делала это в 8 случаях из 10, что существенно превосходит результаты, демонстрируемые гаплоидной.

Диплоидная популяция работает медленнее. К 3000 поколению уже просматриваются отдельные группы особей, но не так отчетливо как у гаплоидной. Даже к 6000 поколению популяция оказывается невырожденной, хотя большая ее половина лежит в окрестности глобального экстремума по всем координатам. Маленькие группы сохраняются в субоптимальных экстремумах. Если предположить, что в этот момент снова произойдет изменение рельефа целевой функции, она, по сравнению с гаплоидной, окажется лучше подготовленной к очередной адаптации.

Следует признать, что тестовая функция (12) относится к разряду простых для ГА. То, что гаплоидная популяция не нашла решение за 6000 поколений, объясняется только чрезвычайно сложными для нее начальными условиями поиска. В норме популяция из 100 особей, сгенерированная обычным образом, находит решение за 2000—2500 поколений по всем координатам и очень точно. Диплоидная популяция всегда проигрывает ей в

скорости, но в трудных условиях дольше сохраняет работоспособность и находит более выгодные решения.

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