Часть 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:


Свежее новое
  • На B-52 испытали новую гиперзвуковую ракету
  • Б-52 — знаменитый североамериканский бомбардировщик стратегического назначения. Минобороны США планирует оснастить этот самолет новейшим комплексом
  • Две погасшие звезды слились воедино и образовали одну, которая «ожила»
  • Можно ли из двух мертвых тел создать одно живое? Оказывается, это реально, если речь идет о звездах. Астрономы открыли такую редкую звезду, которая
  • Трансгенные грибы могут истреблять разносчиков малярии и других москитов
  • Ученые из США и Буркина-Фасо провели эксперименты, доказавшие эффективность нового средства от москитов. Это генномодифицированный гриб вида
  • Ролик о массовом взлете конвертопланов Osprey и вертолетов CH-53E завораживает
  • По сети гуляет видео, где несколько десятков летательных аппаратов ВМС Соединенных Штатов Америки демонстрируют слаженный взлет. Этот завораживающий
  • Ученые нашли окаменелость, которая сохранила целую стаю рыбок
  • В Америке нашли окаменелость, в которой «законсервирована» целая стайка рыбок. Они застыли в процессе движения, которое, как считают ученые, было
Последние комментарии
Ролик о массовом взлете конвертопланов Osprey и вертолетов CH-53E завораживает
Сколько раз я задавал вопрос про аварийную посадку конвертоплана,но так и не получил ответа. Если у него двигатели не повернутся вверх,то как он
5 необъяснимых для науки загадок
Ваша цитата: "Масса - это сконцентрированная Энергия. Энергия - это не сконцентрированная Масса".   Мой комментарий: Чтобы увеличить (в общем случае
Исследование показало: рождение ребенка старит женщину на 11 лет, а бездетные люди живут меньше
Корреляция в данном случае заключается в том что работает программа размножения. Программа размножения с точки зрения системы не дать умереть виду,
Сколько придется лететь со скоростью света до ближайшей звезды?
Ни какого замедления времени и ни какого сокращения расстояния не происходит при полёте в Космосе со скоростью близкой к скорости света, а тем более
Сколько придется лететь со скоростью света до ближайшей звезды?
Ближайшая звезда к нам, это Солнце. Расстояние порядка 150 млн. км. (Астрономическая единица). Несложные арифметические действия и "вуаля", получаем
Мы в социальных сетях
Статистика
3  
Всего статей 2003
1  
Всего комментариев 333
2  
Пользователей 118