ТСМ-1 (1088236), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Шаг 3. k=k-1; d’=d.

Если k 1, то перейти к шагу 2. Иначе завершить вычисления.

В алгоритме операция a mod b означает остаток от деления a на b.

Пример 1.

6 mod 4 = 2

8 mod 5 = 3

0 mod 2 = 0

1 mod 3 = 1

4 mod 2 = 0

Пример 2.

Рассмотрим пересчет , представленного в таблице. Пусть .

Шаг 1. d’=14; k=n=2.

Шаг 2. d=[14/(3+1)]=[3 ]=3;

Z₂=(3 mod 2) (3-2 (14 mod (3+1)))+14 mod (3+1)=1 (3-2 2)+2=1;

Z₂=1.

Шаг 3. k=k-1=1 1; d’=3. Переходим к шагу 2.

Шаг 4. d=[3/(3+1)]=[ ]=0;

Z₁=(0 mod 2) (3-2 (3 mod (3+1)))+3 mod (3+1)=3 mod 4=3;

Z₁=3.

Пример 3.

Построим таблицу МКГ для случая: n=4; m₁=1; m₂=2; m₃=1; m₄=2.

Т.е. , где

Это количество комбинаций:

Построим в координатном пространстве гиперкуб (точнее его проекцию на подмножество )

Таблица 2.

0	0000	12	0200	24	1100
1	0001	13	0201	25	1101
2	0002	14	0202	26	1102
3	0012	15	0212	27	1112
4	0011	16	0211	28	1111
5	0010	17	0210	29	1110
6	0110	18	1210	30	1010
7	0111	19	1211	31	1011
8	0112	20	1212	32	1012
9	0102	21	1202	33	1002
10	0101	22	1201	34	1001
11	0100	23	1200	35	1000

На рисунке изображена последовательность обхода вершин гиперкуба в пространстве при z₁=0.

Данная последовательность обхода охватывает точки: 0 x_i 17.

Для того, чтобы закодировать оставшиеся точки: 18 x_i 35, можно использовать алгоритм пересчета.

Другой геометрический способ состоит в следующем. Необходимо изменить координату z₁ на 1, т.е. положить z₁=1. Это означает, что мы переходим в следующее сечение гиперкуба: при z₁=1. После этого необходимо осуществить обход следующего сечения в обратном порядке. Это означает, что в таблице устанавливаем z₁=1 для всех 18 x_i 35, а остальные коды перезаписывать зеркально в ячейки, расположенные после x_i=17.

Пример 4. Рассмотрим пересчет x_i → МКГ(x_i).

Шаг 1. d’=22; k=4; m₄=2.

Шаг 2. d=[22/(2+1)]=[7 ]=7;

z₄=(7 mod 2) (2-2 (22 mod (2+1)))+22 mod (2+1)=1 (2-2 1)+1=1;

z₄=1.

Шаг 3. k=4-1=3 1; d’=7.

Шаг 4. d=[7/(1+1)]=[3 ]=3; m₃=1;

z₃=(3 mod 2) (1-2 (7 mod (1+1)))+7 mod (1+1)=1 (1-2 1)+1=0;

z₃=0.

Шаг 5. k=3-1=2 1; d’=3; m₂=2.

Шаг 6. d=[3/(2+1)]=1;

z₂=(1 mod 2) (2-2 (3 mod (2+1)))+3 mod (2+1)=1 (2-2 0)+0=2;

z₂=2;

Шаг 7. k=2-1=1 1; d’=1; m₁=1;

Шаг 8. d=[1/(1+1)]=[ ]=0.

z₁=(0 mod 2) (1-2 (1 mod (1+0)))+1 mod (1+1)=1 mod 2=1;

z₁=1;

В итоге получаем: X_i=22 z=[1201]

Что соответствует таблице.

Для обратного пересчета их z в x_i можно использовать следующее соотношение:

S_Ⅰ

S_Ⅱ

S_Ⅲ

S_Ⅳ

Обозначим слагаемые через S_Ⅰ, S_Ⅱ, S_Ⅲ, S_Ⅳ.

Пример 5. Выполним пересчет:

z₁ z₂ z₃ z₄

z=[1 2 0 1] x_i=22;

m₁=1; m₂=2; m₃=1; m₄=2;

x_i=S_Ⅰ+S_Ⅱ+S_Ⅲ+S_Ⅳ.

S_Ⅰ=1(2+1)(1+1)(2+1)=1*3*2*3=18;

S_Ⅰ=18;

S_Ⅱ= ((z₁ mod 2)(m₂-2z₂)+z₂)(m₃+1)(m₄+1) + при j=2

+ (((z₁+z₂) mod 2)(m₃-2z₃)+z₃)(m₄+1) = при j=3

= ((1 mod 2)(2-2*2)+2)(1+1)(2+1) +

+ (((1+2) mod 2)(1-2*0)+0)(2+1) =

= (1*(-2)+2)*2*3 + (1*1+0)*3 = 0*2*3 + 1*3 = 0 + 3 = 3;

S_Ⅱ=3;

S_Ⅲ=((z₁+z₂+z₃) mod 2)(m₄-2z₄)=((1+2+0) mod 2)(2-2*1)=1*0=0;

S_Ⅲ=0;

S_Ⅳ=z₄=1;

S_Ⅳ=1;

x_i=18+3+0+1=22;

x_i=22.

Таким образом, имеем:

x_i z – оператор кодирования

z x_i – оператор декодирования

Будем считать что, если есть вектор переменных , то каждая переменная кодируется определенным фрагментом хромосомы, состоящая из фиксированного числа генов. Рядом стоящие фрагменты не отделяются друг от друга какими-либо маркерами. Тем не менее, при декодировании хромосомы в вектор переменных на протяжении всего моделируемого периода эволюции используется одна и та же маска мутирования хромосомы, определяющая план распределения наследственной информации на длине хромосомы.

x_i= [ ]

Хромосомы генерируются случайным образом путем последовательного заполнения разрядов (генов) в соответствии с равномерным законом распределения.

Всякие изменения в популяции затрагивают сначала генетический уровень, а только потом анализируются фенотипические последствия этих изменений.

Характеристики

Список файлов лекций