Основной принцип работы диплоидных генетических алгоритмов заключается в возможности кодирования одних и тех же свойств особи (переменных) хромосомными наборами, полученными от обоих родителей. При этом проявляются свойства в дочерней особи в зависимости от отношений доминантности и рецессивности между гомологичными (находящимися в одинаковых позициях) генами родительских хромосом.
По аналогии с разработанными биологами феноменологическими моделями возможна реализация как механизма полного доминирования, исключающего активность гена в рецессивном состоянии, так и механизма, учитывающего проявление одновременной активности генов, но в разной степени. В качестве примера организации такого генетического алгоритма рассмотрим первый механизм.
Среди различных преимуществ диплоидности особое внимание обращается на уменьшение скорости фенотипического вырождения популяции вследствие сохранения рецессивных хромосомных наборов, что приводит к возможности выхода из локальных оптимумов ошибки при образовании особи с лучшими свойствами с участием рецессивных генов.
Обозначим в виде 0 и 1 рецессивные значения, а в виде 0 и 1 – доминантные. Для разрешения конфликтов между доминантными и рецессивными генами в гомологичных парах при определении свойств конкретной особи сформулированы правила, приведённые в таблице. При составлении правил учитывается соотношение приспособленностей родительских особей.
Более приспособленный родитель | |||||
1 | 0 | 1 | 0 | ||
Менее приспособленный родитель | 1 | 1 | 0 | 1 | 1 |
0 | 1 | 0 | 0 | 0 | |
1 | 1 | 0 | 1 | 0 | |
0 | 1 | 0 | 1 | 0 |
Общий подход при составлении правил таков. Из пары гомологичных генов в фенотипе проявляет себя тот, который обладает более сильным признаком активности. Любой доминантный ген подавляет любой рецессивный. Если оба гена имеют одинаковый приоритет, активность одного из них в таблице правил меняется принудительно в соответствии с соотношением приспособленностей родительских хромосом.
Рассмотрим примеры основных генетических операторов, применяемых в диплоидном генетическом алгоритме.
В случае мутации изменяется значение или признак активности гена зиготы одного или обоих родителей, причём, в общем случае, в различных позициях:
– хромосома до мутации:
Зигота более приспособленного родителя | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
Зигота менее приспособленного родителя | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
Декодируемый генотип | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
– хромосома после мутаций в 4-й и 6-й позициях родительских зигот соответственно:
Зигота более приспособленного родителя | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
Зигота менее приспособленного родителя | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
Декодируемый генотип | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
В представленном примере замена рецессивной единицы на рецессивный ноль зиготы более приспособленного родителя не вызвало изменения генотипа в 4-й позиции гена, поскольку доминирующей осталась единица зиготы второго родителя. В то же время замена доминантного нуля на рецессивный ноль зиготы второго родителя привело к изменению значения гена в 6-й позиции, поскольку при одинаковой активности приоритет был отдан гену более приспособленного родителя.
Инверсия в диплоидном генетическом алгоритме представляет собой простые инверсии родительских зигот в случайных позициях генов. На следующем примере проиллюстрирована инверсия в 4-й и 6-й позициях родительских зигот:
– хромосома до инверсии:
Зигота более приспособленного родителя | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
Зигота менее приспособленного родителя | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
Декодируемый генотип | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
– хромосома после инверсии в 4-й и 6-й позициях родительских зигот соответственно:
Зигота более приспособленного родителя | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
Зигота менее приспособленного родителя | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
Декодируемый генотип | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
Получение такой дочерней особи, как в примере, в результате инверсии родительской хромосомы в гаплоидном генетическом алгоритме было бы в принципе невозможно.
Оператор кроссовера в диплоидном генетическом алгоритме применяется в отдельности в случайных позициях к зиготам каждой из двух родительских особей, в результате чего образуются две зиготы для дочерней особи, как показано на следующем примере:
– кроссовер хромосомы более приспособленного родителя в 4-й позиции:
1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
– возможные зиготы от более приспособленного родителя:
1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 |
0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 |
и выбирается одна из зигот, например, вторая;
– кроссовер хромосомы менее приспособленного родителя в 6-й позиции:
0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
– возможные зиготы от более приспособленного родителя:
0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
и выбирается одна из зигот, например, первая;
– дочерняя хромосома после кроссовера в 4-й и 6-й позициях родительских особей соответственно:
Зигота более приспособленного родителя | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 |
Зигота менее приспособленного родителя | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
Декодируемый генотип | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 |
Вычислительные эксперименты показали более эффективную работу диплоидных генетических алгоритмов, чем гаплоидных, с точки зрения нахождения глобального решения. При этом отмечается, что диплоидные алгоритмы работают медленнее, то есть требуется больше поколений для начала вырождения популяции.
По материалам изданий:
1. Дударов С. П. Математические основы генетических алгоритмов: учеб. пособие/ С. П. Дударов. – М.: РХТУ им. Д. И. Менделеева, 2012. – 56 с.;
2. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности/ Г. К. Вороновский, К. В. Махотило, С. Н. Петрашев, С. А. Сергеев. – Харьков: ОСНОВА, 1997. – 112 с.