Развитие генетических алгоритмов привело к возникновению множества различных генетических операторов (см. рис.).
Основные (базовые) генетические операторы были предложены Холландом для реализации его репродуктивного плана. К ним относятся мутация, инверсия и кроссовер.
Модифицированные операторы основываются на принципах базовых. Они были предложены исследователями генетических алгоритмов в разное время с целью обеспечения более широкого спектра получаемых потомков и улучшения оптимизационной способности алгоритма на каждой эпохе эволюционного процесса.
Новые операторы также в разное время предложены исследователями генетических алгоритмов, однако в их основе не используются принципы базовых операторов.
Рассмотрим подробнее набор базовых генетических операторов.
Мутация заключается в замене гена в случайной позиции родительской хромосомы на другое значение.
На следующем примере иллюстрируется мутация родительской хромосомы в 4-й позиции гена:
– родительская хромосома:
a |
b |
c |
d1 |
e |
f |
g |
h |
– дочерняя хромосома:
a |
b |
c |
d2 |
e |
f |
g |
h |
Так, например, при бинарном кодировании если d1 = 0, то d2 = 1, и наоборот.
Инверсия представляет собой разрыв родительской хромосомы в случайной позиции гена и изменение очерёдности двух полученных фрагментов в дочерней особи.
На следующем примере проиллюстрирована инверсия в 4-й позиции гена: дочерняя хромосома
– родительская хромосома:
a |
b |
c |
d |
e |
f |
g |
h |
– дочерняя хромосома:
d |
e |
f |
g |
h |
a |
b |
c |
Кроссовер (скрещивание) – это генетический оператор, применяемый к двум родительским особям: каждая из них делится на два фрагмента в одной и той же случайной позиции гена. Дочерние особи представляют собой комбинации первого и второго фрагментов хромосом разных родителей.
На следующем примере показан пример скрещивания в 4-й позиции родительских генов:
– родительские хромосомы:
a1 |
b1 |
c1 |
d1 |
e1 |
f1 |
g1 |
h1 |
a2 |
b2 |
c2 |
d2 |
e2 |
f2 |
g2 |
h2 |
– возможные дочерние хромосомы:
a1 |
b1 |
c1 |
d2 |
e2 |
f2 |
g2 |
h2 |
a2 |
b2 |
c2 |
d1 |
e1 |
f1 |
g1 |
h1 |
В дальнейшем в новое поколение популяции включается, как правило, лишь одна из дочерних особей.
Дударов С. П. Математические основы генетических алгоритмов: учеб. пособие/ С. П. Дударов. – М.: РХТУ им. Д. И. Менделеева, 2012. – 56 с.