Часть 5. Модифицированные генетические операторы

Современные генетические алгоритмы развивались, в том числе, в направлении совершенствования и модификации базовых генетических операторов. Рассмотрим эти модификации.

Модифицированные операторы мутации включают:

– многопозиционную мутацию;
– селективную мутацию.

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

Пример двухпозиционной мутации в 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 с.


Если у вас есть статья, заметка или обзор, которыми вы хотите поделиться с аудиторией нашего сайта, присылайте информацию на: neuronus.com@yandex.ru.
Гость, оставишь комментарий?
Имя:*
E-Mail:


Последние комментарии
Дрон-камикадзе и ракеты с искусственным интеллектом: как в России создали умные боеприпасы и планируют применять в деле
Современная микроэлектроника, включая микроконтроллеры и процессоры для современных ПК, является продуктом высокотехнологического производства и
Как работает Любовь? Квантовая связь нейронной активности Людей
ребят,вот вам смешно,а квантовая связь влюбленных то существует.и я не шучу. мой парень видел глюки и в этих глюках присутствовала я.(если что,в
Почему космос не имеет начала и конца: комментарии учёных
Земля находится трёх слонах, которые стоят на черепахе
Судьба ледокола «Арктика» остается неопределенной после повреждения одного из двигателей
Народ теперь что бы накачать мышцы и убрать лишний жир можно без спорта и диет, просто надел и забыл. Опробовал лично и результат удивил уже через
Сообщение о покупке водородной яхты Билом Гейтсом оказалось ложным
Народ теперь что бы накачать мышцы и убрать лишний жир можно без спорта и диет, просто надел и забыл. Опробовал лично и результат удивил уже через
Мы в социальных сетях
Статистика
0  
Всего статей 2562
0  
Всего комментариев 1031
0  
Пользователей 264