Современные генетические алгоритмы развивались, в том числе, в направлении совершенствования и модификации базовых генетических операторов. Рассмотрим эти модификации.
Модифицированные операторы мутации включают:
– многопозиционную мутацию;
– селективную мутацию.
Многопозиционная мутация подразумевает изменение значений генов в нескольких случайных позициях родительской хромосомы.
Пример двухпозиционной мутации в 3-й и 8-й позициях показан ниже:
– родительская хромосома:
a | b | c1 | d | e | f | g | h1 |
– дочерняя хромосома:
a | b | c2 | d | e | f | g | h2 |
Селективная мутация заключается в последовательном выполнении основного оператора мутации применительно к родительской хромосоме поочерёдно в нескольких случайных позициях, анализе приспособленностей получающихся потомков и выборе из всех возможных дочерних хромосом единственной для нового поколения популяции.
Пример селективной мутации для двух случайных позиций представлен далее:
– родительская хромосома:
a | b | c1 | d | e | f | g | h1 |
– возможные дочерние хромосомы:
a | b | c2 | d | e | f | g | h1 |
a | b | c1 | d | e | f | g | h2 |
К модифицированным операторам инверсии относятся:
– многопозиционная инверсия;
– селективная инверсия;
– фрагментарная инверсия.
Многопозиционная инверсия представляет собой деление родительской хромосомы в нескольких случайных позициях с последующей расстановкой получившихся фрагментов в случайном порядке.
Пример двухпозиционной инверсии представлен ниже:
– родительская хромосома:
a | b | c | d | e | f | g | h |
– дочерняя хромосома:
f | g | h | a | b | c | d | e |
Селективная инверсия – это последовательный процесс применения основного оператора инверсии к одной родительской особи поочерёдно в нескольких случайных позициях, анализа приспособленностей получающихся потомков и выбора из всех возможных дочерних хромосом единственной для нового поколения популяции.
Далее приведён пример селективной инверсии для двух случайных позиций:
– родительская хромосома:
a | b | c | d | e | f | g | h |
– возможные дочерние хромосомы:
c | d | e | f | g | h | a | b |
h | a | b | c | d | e | f | g |
Фрагментарная инверсия заключается во взаимной перестановке двух или нескольких непересекающихся фрагментов родительской хромосомы, взятых в случайных позициях. Для сохранения полезного генетического материала предпочтительно, чтобы эти фрагменты имели одинаковую длину, но в общем случае она может быть разной. В отличие от других разновидностей инверсии здесь сумма длин перестанавливаемых фрагментов должна быть меньше общего размера хромосомы.
Ниже показан пример фрагментарной инверсии:
– родительская хромосома:
a | b | c | d | e | f | g | h |
– дочерняя хромосома:
a | f | g | d | e | b | c | h |
Среди модифицированных операторов кроссовера можно выделить: – многохромосомный кроссовер;
– многопозиционный кроссовер;
– однородный кроссовер;
– шаблонный кроссовер.
Многохромосомный кроссовер – это модифицированный генетический оператор скрещивания более двух (P) родительских хромосом в P–1 случайной позиции с получением дочерних особей, из которых выбирается одна для нового поколения популяции.
Пример трёххромосомного кроссовера представлен ниже:
– родительские хромосомы:
a1 | b1 | c1 | d1 | e1 | f1 | g1 | h1 |
a2 | b2 | c2 | d2 | e2 | f2 | g2 | h2 |
a3 | b3 | c3 | d3 | e3 | f3 | g3 | h3 |
– возможные дочерние хромосомы:
a1 | b1 | c1 | d2 | e2 | f3 | g3 | h3 |
a2 | b2 | c2 | d3 | e3 | f2 | g2 | h2 |
a2 | b2 | c2 | d1 | e1 | f3 | g3 | h3 |
a2 | b2 | c2 | d3 | e3 | f1 | g1 | h1 |
a3 | b3 | c3 | d1 | e1 | f2 | g2 | h2 |
a3 | b3 | c3 | d2 | e2 | f1 | g1 | h1 |
Зависимость количества возможных дочерних особей D от числа родительских хромосом для многохромосомного кроссовера определяется формулой:
P = P!
Многопозиционный кроссовер – это скрещивание двух родительских хромосом в нескольких (более одной) случайных позициях с получением двух возможных потомков и выбором из них одного для нового поколения популяции.
Ниже показан пример двухпозиционного кроссовера в позициях 4-го и 6-го генов
– родительские хромосомы:
a1 | b1 | c1 | d1 | e1 | f1 | g1 | h1 |
a2 | b2 | c2 | d2 | e2 | f2 | g2 | h2 |
– возможные дочерние хромосомы:
a1 | b1 | c1 | d2 | e2 | f1 | g1 | h1 |
a2 | b2 | c2 | d1 | e1 | f2 | g2 | h2 |
Особенность однородного кроссовера заключается в синтезе дочерних хромосом из расположенных в соответствующих позициях генов родителей, выбираемых случайным образом. Для этого параметром настройки алгоритма вводится пороговое значение однородного кроссовера. При определении значения каждого следующего гена, если новое случайное число превышает заданный порог, используется ген первого родителя, иначе – второго. Вторая возможная дочерняя хромосома синтезируется по противоположному условию: при превышении порога – ген второго родителя, в противном случае – первого. В новое поколение популяции, как правило, включается один из потомков.
Проиллюстрируем выполнение однородного кроссовера на следующем примере:
– родительские хромосомы:
a1 | b1 | c1 | d1 | e1 | f1 | g1 | h1 |
a2 | b2 | c2 | d2 | e2 | f2 | g2 | h2 |
– пороговое значение 0,7 для случайных чисел из интервала [0, 1];
– вектор случайных чисел:
0,0 | 0,9 | 1,0 | 0,4 | 0,8 | 0,2 | 0,1 | 0,4 |
– родительские хромосомы:
a1 | b2 | c2 | d1 | e2 | f1 | g1 | h1 |
a2 | b1 | c1 | d2 | e1 | f2 | g2 | h2 |
Результат применения однородного кроссовера может быть идентичен результату применения многопозиционного кроссовера. Принципиальное отличие – использование порогового параметра, который в пределе при большом количестве применений оператора устанавливает среднее соотношение между объёмами генетического материала родителей.
Шаблонный кроссовер может использоваться в бинарных генетических алгоритмах. Для этого помимо двух родительских хромосом необходим шаблон, в качестве которого может быть использован генетический материал любой третьей хромосомы особи популяции, фактически заменяющий вектор случайных чисел однородного кроссовера. Если в некоторой позиции шаблонной хромосомы ген принимает значение 0, то в дочернюю хромосому в данную позицию встаёт ген первого родителя, иначе – второго. Противоположным образом формируется вторая дочерняя хромосома. Из двух потомков в новое поколение популяции входит, как правило, один.
Проиллюстрируем данный оператор на примере:
– родительские хромосомы:
a1 | b1 | c1 | d1 | e1 | f1 | g1 | h1 |
a2 | b2 | c2 | d2 | e2 | f2 | g2 | h2 |
– шаблонная хромосома:
0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |
– дочерние хромосомы:
a1 | b2 | c2 | d1 | e1 | f1 | g2 | h1 |
a2 | b1 | c1 | d2 | e2 | f2 | g1 | h2 |
При выборе соответствующей опции алгоритма в качестве шаблона может быть использована лучшая особь популяции.
По материалам учебного пособия:
Дударов С. П. Математические основы генетических алгоритмов: учеб. пособие/ С. П. Дударов. – М.: РХТУ им. Д. И. Менделеева, 2012. – 56 с.