Практика 1.2: Генетический алгоритм, скрещивание

Используем формулу $F = G_{10} \frac{F_{max}-F_{min}}{G_{max}}+F_{min},$ где $G_{max} = 2^m-1$ и $G_{10}$ - генотип, $m$ - длина гена, $F$ - фенотип.

Задание: провести скрещивание двух особей, определить генотипы, фенотипы и значение функции приспособленности особей-потомков.

Пример решения задачи

Дано

$f = x^2+y^2$ - функция приспособленности

Первый родительский пул (в нем генотипы 3х родителей): $0010 | 0110$ $1010 | 0100$ $1100 | 1001$ Второй родительский пул (в нем генотипы 2х родителей ): $1111 | 0000$ $1000 | 1010$

Длина гена:$m = 4$

Поисковый интервал: $F \in [0; 8]$

Точка рассечения №1 : между 3 и 4 разрядами хромосомы

Точка рассечения №2 : между 5 и 6 разрядами хромосомы

Решение

Шаг 1. Турнирный отбор

Проведем турнирный отбор между родителями по формуле $F = G_{10} \frac{F_{max}-F_{min}}{G_{max}}+F_{min},$ определим фенотип родителей. Для этого необходимо перевести генотип из двоичной системы в десятичную и подставим в формулу.

0010 -> 2 | 0110 -> 6

1010 -> 10 | 0100 -> 4

1100 ->12 | 1001 -> 9

Полученные значения подставим в функцию приспособленности и выберем лучшего родителя в каждом пуле.

1. Для первого родителя из пула: $F_x = 2 *\frac{8-0}{15}+ 0 = \frac{16}{15} = 1.07$ $F_y = 6 *\frac{8-0}{15}+ 0 = \frac{48}{15} = 3.2$ $f_1(F_x, F_y) = 10.24+1.14 = 11.4$
2. Для второго родителя из пула: $F_x = 10 *\frac{8-0}{15}+ 0 = \frac{80}{15} = 5.3$ $F_y = 4 *\frac{8-0}{15}+ 0 = \frac{32}{15} = 2.13$ $f_2(F_x, F_y) = 28.4+4.5 = 32.9$
3. Для третьего родителя из пула: $F_x = 12 *\frac{8-0}{15}+ 0 = \frac{96}{15} = 6.4$ $F_y = 9 *\frac{8-0}{15}+ 0 = \frac{72}{15} = 4.8$ $f_3(F_x, F_y) = 41+23 = 64$ Первый родитель является лучшим. Рассмотрим второй пул.
4. Для первого родителя из пула: $F_x = 15 *\frac{8-0}{15}+ 0 = \frac{120}{15} = 8$ $F_y = 0*\frac{8-0}{15}+ 0 = \frac{0}{15} = 0$ $f_1(F_x, F_y) = 64+0 = 64$
5. Для второго родителя из пула: $F_x = 8 *\frac{8-0}{15}+ 0 = \frac{64}{15} = 4.2$ $F_y = 10 *\frac{8-0}{15}+ 0 = \frac{80}{15} = 5.3$ $f_2(F_x, F_y) = 18.2+28.1 = 36.3$ Второй родитель является лучшим из данного пула.

Шаг 2. Скрещивание

В генотипе двух родителей меняем местами указанные в условии промежутки (точки рассечения). В данном случае:

$G_1$ 001|00|110 -> 001|01|110

$G_2$ 100|01|010 -> 100|00|010

Шаг 3. Фенотип потомков

Вычисляем фенотип и функцию приспособленности потомков.

1. Для первого потомка: $F_x = 2 *\frac{8-0}{15}+ 0 = \frac{16}{15} = 1.07$ $F_y = 14*\frac{8-0}{15}+ 0 = \frac{112}{15} = 7.4$ $f_1(F_x, F_y) = 1.14 + 54.76 = 55.9$
2. Для второго потомка: $F_x = 8 *\frac{8-0}{15}+ 0 = \frac{64}{15} = 4.2$ $F_y = 2 *\frac{8-0}{15}+ 0 = \frac{16}{15} = 1.07$ $f_2(F_x, F_y) = 17.64+1.14 = 18.76$

   Ответ

Генотип: $G_1 = 00101110$

Фенотип: $F_1 = (1.07, 7.4)$

Функция приспособленности: $f_1 = 55.9$

Генотип: $G_2 = 10000010$

Фенотип: $F_2 = (4.2, 1.07)$

Функция приспособленности: $f_2 = 18.78$