Генетические алгоритмы

Формат: doc

Дата создания: 19.05.1998

Размер: 16.41 KB

Скачать реферат


1.1Генные мутации

В зависимости от величины структурных изменений в генах и хромосомах мутации делятся на несколько типов. В разделе 3.2. был введен простейший тип мутаций - точечная мутация, которая в общем случае q-битовых аллелей осуществляется в пределах одного гена, когда аллель, находящаяся в соответствующем локусе "родительского" генотипа, случайным образом подвергается изменению в одном из q битов генетической информации. В результате точечной мутации "мутанту" передается генотип "родителя", в котором один из генов содержит новую "слегка искаженную" аллель (рис. 4.1).

ген 1 ген 2 ген 3 ген 4

Родительский” генотип E( ): 0 1 1 0 1 0 1 1 1 0 1 1

1 2 3 4 5 6 7 8 9 10 11 12

Г енотип “мутант” E( ): 0 1 1 0 0 0 1 1 1 0 1 1

1 2 3 4 5 6 7 8 9 10 11 12

локус 1 локус 2 локус 3 локус 4

Рис. 4.1. Точечная мутация в пятом бите гена 2 изменяет аллель этого гена в генотипе "мутанта", оставляя гены 1, 3 и 4 без изменений

Одну из схем воспроизводства из родительской" гаметы E( ) мутанта с помощью точечной мутации можно представить в виде следующей процедуры:

1.

2. В генотипе случайным образом с вероятностью (1/n) определяется j-ый ген (jÎ[1,n]), в котором аллель "родительского" гена будет подвержена мутации.

3. Для выбранного гена случайным образом с вероятностью (1/q) в j-м локусе выбирается i-ый бит, в котором должна произойти точечная мутация.

4. В i-м бите j-ого локуса генотипа двоичное число bi принимает противоположное значение (0 заменяется на 1 или 1 заменяется на 0).

Генотип "мутанта" сформирован.

Более глубокие изменения генной информации происходят в результате генной мутации, когда в i-м гене "родительского" генотипа E( ) аллель, находящаяся в i-м локусе, полностью заменяется новой аллельной формой (рис.6.2).

ген 1 ген 2 ген 3 ген 4

Родительский” генотип E( ): 0 1 1 0 1 0 1 1 1 0 1 1

1 2 3 4 5 6 7 8 9 10 11 12

Г енотип “мутант” E( ): 0 1 1 0 0 0 1 1 1 0 1 1

1 2 3 4 5 6 7 8 9 10 11 12

локус 1 локус 2 локус 3 локус 4

Рис. 4.2. Генная мутация во 2 гене изменяет аллель этого гена в генотипе "мутанта", оставляя гены 1, 3 и 4 без изменений

Очевидно, что новые аллели должны принадлежать генофонду гена, подвергающегося мутации, и, как правило, отличаются от аллельных форм, уже имеющихся в хромосомном наборе популяции Pt для соответствующего локуса.

Очевидно, что новые аллели должны принадлежать генофонду гена, подвергающегося мутации, и, как правило, отличаются от аллельных форм, уже имеющихся в хромосомном наборе популяции Pt для соответствующего локуса.

Одна из схем реализации генной мутации в "родительском" генотипе E( ) может быть представлена следующим образом:

1.

2. В генотипе случайным образом с вероятностью (1/n) определяется j-ый ген (j Î[1,n]), в котором аллель "родительского" гена будет подвержена мутации.

3. Из генофонда j-ого гена Г(j) исключаются все аллели хромосомного набора популяции Pt, находящиеся в j-м локусе:

Г ( j ) := Г ( j )\

4. Если Г(j): = Æ, то Г(j):= .

5. Случайным образом с вероятностью (1/êГ(j)ê) из множества аллелей Г(j) выбирается альтернативный аллель .

6. В j-м локусе генотипа аллель "родительского" генотипа заменяется новой аллельной формой .

Генотип "мутанта" сформирован.

Для задачи оптимального разбиения графа G на два подграфа G1и G2 порядка n1 и n2, соответственно, точечная и генная мутации совпадают, т.к. локусы для каждого гена содержат по одному биту (q=1). С другой стороны, к формируемым генотипам E( ) предъявляется требование, чтобы число "I" в них равнялось порядку n1подграфа G1. В связи с этим генная мутация для рассматриваемого случая сводится к изменению аллельных форм в двух случайно выбранных генах "родительского" генотипа E( ): в одном гене аллель, равная “I" заменяется "0", а в другом гене аллель, равная "0" заменяется на "1".

Схема, реализующая генную мутацию генотипа E( ), который характеризует допустимое дихотомическое разбиение (X1, X2 ), имеет следующий вид:

1.

2. По генотипу образуется список номеров локусов I1 , содержащих "I", и список номеров локусов I0, содержащих "0".

3. Случайным образом с вероятностью (1/½ I1½) выбирается номер локуса iÎI1 , который будет подвержен генной мутации.

4. Случайным образом с вероятностью (1/êI0 ê) выбирается номер локуса j ÎI , который будет подвержен генной мутации.

5. Аллель "1", находящаяся в i-м локусе генотипа заменяется "0", а аллель "0", находящаяся в j-м локусе генотипа заменяется "1".

Генотип "мутанта" сформирован.

Рассмотренный алгоритм генной мутации описывает операцию однократного обмена вершинами между подмножествами X1 и X2 , которая заключается в том, что только одна вершина xiÎ X1 перемещается на другую сторону разреза в часть X2, вместо вершины vjÎX2, которая, в свою очередь, перемещается в часть X1 :

= [X1\{xi}] È {vj};

(6.1)

= [X2\{vj}] È {xi}.

Пример 6.1.

Пусть "родительский" генотип E( ) задает дихотомическое распределение

X1 = {x1, x3, x4, x10, x12} , X2 = {x2, x5, x6, x7, x8, x9, x11} :

*

*

"Родительский" генотип E( ):

1

0

1

1

0

0

0

0

0

1

0

1

1

2

3

4

5

6

7

8

9

10

11

12

Д ля случайно выбранных генов 2 и 12, отмеченных звездочкой, генная мутация позволяет воспроизвести "мутанта" с генотипом следующего вида:

Г енотип "мутанта" : 1 1 1 1 0 0 0 0 0 1 0 0 (25)

1 2 3 4 5 6 7 8 9 10 11 12

Подобные документы: