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


Гость, оставишь комментарий?
Имя:*
E-Mail:


Свежее новое
  • Как искусственный интеллект помогает в изучении иностранного языка ?
  • Технологии стали неотъемлемой частью нашей жизни. Они развиваются так быстро, что люди не успевают за ними. Мы не можем отрицать его силу или
  • Mail.Ru Group запустили чемпионат по искусственному интеллекту Mini AI Cup #3!
  • На конец лета выпало событие, которое наверняка заинтересует многих любителей поразмышлять о будущем разумных машин. Неделю назад, 30 августа,
  • Искусственный интеллект против команды профессиональных геймеров в DOTA 2. Кто победит?
  • Искусственный интеллект уже подтвердил, что может легко расправится со своими соперниками людьми, играя с ними в шахматы, Го или покер. Как он
  • Обработку разведданных с дронов США поручат искусственному интеллекту
  • Как известно, большинство частных компаний избегают использовать свой потенциал при разработке систем искусственного интеллекта для оборонных целей.
Последние комментарии
Теория и Практика Технологической Сингулярности и Искусственного Интеллекта
На сегодня развитие IT в США значительно опережает состояние в России, где нет своего компьютера, нет своей операционной системы, нет своей
Как работает Любовь? Квантовая связь нейронной активности Людей
про квантовые коммуникации прочитал - интересно. Спасибо. Про любовь - не увидел. Жалко.
Топ 10 компаний, занимающихся разработкой искусственного интеллекта
Спасибо, перечень интересный, но знакомый. Единая проблема всех ИИ-разработчиков - не понимание того, что сознание - это не статистика, а пойти по
Теория и Практика Технологической Сингулярности и Искусственного Интеллекта
Технологическая сингулярность по мнению Вернора Винджа будет развиваться следующим образом: 1. Компьютеры обретут сознание, и возникнет мощный ИИ; 2.
Теория и Практика Технологической Сингулярности и Искусственного Интеллекта
Может ли технологическая сингулярность, т.е. взрывное ускорение научно-технического прогресса, появиться только в России или необходимо, чтобы она
Мы в социальных сетях
Статистика
0  
Всего статей 1511
1  
Всего комментариев 50
0  
Пользователей 48