Практические занятия 3, 4. Изучение различных кодировок генотипа.

Требования задания

Цель работы – исследование двух основных способов кодирования генотипа хромосом в генетическом алгоритме и их эффективности.

М1 – популяция 100 особей, турнирный отбор (размер 2). Для целочисленной кодировки: 1-точечное скрещивание (p_c = 0,7), мутация (p_m = 0,1), инверсия (p_I = 0,05). Для вещественной кодировки: 1-точечное скрещивание (p_c = 0,7), мутация (p_m = 0,1). Условие остановки - 100 итераций;

М2 – популяция 100 особей, турнирный отбор (размер 3). Для целочисленной кодировки: 2-точечное скрещивание (p_c = 0,8), мутация (p_m = 0,03), инверсия (p_I = 0,03). Для вещественной кодировки: BLX- скрещивание (p_c = 0,8), мутация (p_m = 0,15). Условие остановки - 50 итераций;

М3 – популяция 100 особей, турнирный отбор (размер 4). Для целочисленной кодировки: однородное скрещивание (p_c = 0,9), мутация (p_m = 0,05). Для вещественной кодировки: 1-точечное скрещивание (p_c = 0,65), мутация (p_m = 0,08). Условие остановки - разница приспособленности лидера и «наихудшей» особи меньше 0,01;

М4 – популяция 100 особей, турнирный отбор (размер 5). Для целочисленной кодировки: 1-точечное скрещивание (p_c = 0,75), инверсия (p_I = 0,07). Для вещественной кодировки: 1-точечное скрещивание (p_c = 0,75), мутация (p_m = 0,1). Условие остановки - 50 итераций;

М5 – популяция 100 особей, турнирный отбор (размер 2). Для целочисленной кодировки: 2-точечное скрещивание (p_c = 0,8), инверсия (p_I = 0,1). Для вещественной кодировки: 2-точечное скрещивание (p_c = 0,7), мутация (p_m = 0,12). Условие остановки - 100 итераций;

М6 – популяция 100 особей, турнирный отбор (размер 3). Для целочисленной кодировки: однородное скрещивание (p_c = 0,85), мутация (p_m = 0,2), инверсия (p_I = 0,03). Для вещественной кодировки: BLX- скрещивание (p_c = 0,7), мутация (p_m = 0,07). Условие остановки - 70 итераций;

М7 – популяция 100 особей, турнирный отбор (размер 4). Для целочисленной кодировки: 1-точечное скрещивание (p_c = 0,9), мутация (p_m = 0,1). Для вещественной кодировки: BLX- скрещивание (p_c = 0,7), мутация (p_m = 0,13). Условие остановки - 70 итераций;

М8 – популяция 100 особей, турнирный отбор (размер 5). Для целочисленной кодировки: 2-точечное скрещивание (p_c = 0,7), мутация (p_m = 0,15). Для вещественной кодировки: 1-точечное скрещивание (p_c = 0,7), мутация (p_m = 0,1). Условие остановки – разница приспособленности лидера и «наихудшей» особи меньше 0,01.

Для всех вариантов: Длина гена m = 12 (при целочисленном кодировании).

Таблица тестовых функций

№	Функция y(x)	Поисковый интервал
(9)	–12x2 + 4x12 + 4x22 – 4x1x2	x1  (–10; 10); x2  (-10; 10);
(10)	(x1 – 2)4 + (x1 – 2x2)2	x1  (–10; 10); x2  (-10; 10);
(11)	(x1x2x3 – 1)2 + 5[x3(x1 + x2) – 2]2 + + 2(x1 + x2 + x3 – 3)2	x1  (–5,12; 5,12); x2  (–5,12; 5,12); x3  (–5,12; 5,12);
(12)	4x12 + 3x22 – 4x1x22 + x1	x1  (-5; 10); x2  (0; 10);
(13)	(x12 + x2 – 11)2 + (x1 + x22 – 7)2	x1  (–5,12; 5,12); x2  (–5,12; 5,12);
(14)	100(x2 – x13)2 + (1 – x1)2	x1  (0; 5,12); x2  (0; 5,12);
(15)	[1.5 – x1(1 – x2)]2 + [2.25 – x1(1 – x22)]2 + + [2.625 – x1(1 – x23)]2	x1  (–5,12; 5,12); x2  (–5,12; 5,12);
(16)	(x1 + 10x2)2 + 5(x3 – x4)2 + (x2 – 2x3)4 + 10(x1 – x4)4 (матрица Гессе в точке x* - сингулярная)	x1  (–5,12; 5,12); x2  (–5,12; 5,12); x3  (–5,12; 5,12); x4  (–5,12; 5,12);
(17)	100(x2 – x12)2 + (1 – x1)2 + 90(x4 – x32)2 + (1 – x3)3 +  10.1[(x2 – 1)2 + (x4 – 1)2] + 19.8(x2 – 1)(x4 – 1) (функция имеет несколько локальных минимумов)	x1  (–5,12; 5,12); x2  (–5,12; 5,12); x3  (–5,12; 5,12); x4  (–5,12; 5,12);
(18)	(2x12 + 3x22)exp(x12 – x22) (функция не унимодальная)	x1  (–5,12; 10); x2  (–5,12; 10);
(19)	0.1(12 + x12 + (1 + x22)/x12 + (x12x22 + 100)/(x14x24))	x1  (–5,12; 3); x2  (–5,12; 3);
(20)	100[x3 – 0.25(x1 + x2)2]2 + (1 – x1)2 + (1 – x2)2	x1  (–5,12; 3); x2  (–5,12; 3); x3  (–5,12; 5,12);

Варианты задания

Вариант	1	2	3	4	5	6	7	8
Метод	М1	М2	М3	М4	М5	М6	М7	М8
Тестовая функция	(9) (20)	(10) (19)	(11) (18)	(12) (17)	(13) (16)	(14) (15)	(15) (14)	(16) (13)

Контрольные вопросы

1. Изложить суть целочисленного и вещественного кодирования.

2. В чем проявляются недостатки целочисленного кодирования по отношению к вещественному?

3. Вместо целочисленного кодирования часто применяют код Грея. Какие, по Вашему мнению, у него есть преимущества перед цепочкой из двоичного алфавита?

4. Изменятся ли генетические операторы для целочисленного кодирования в случае применения их к хромосомам в коде Грея. Если да, то какие и каким образом?

Содержание отчета по практическим занятиям

1. Цель работы и требования задания.

2. Краткое описание алгоритма на основании материала лекционного курса и описание схемы пошагового выполнения вычислительного алгоритма.

3. Укрупненная блок-схема программы с пояснением всех ее частей.

4. Спецификация программы, раскрывающая смысл входных и выходных данных, основных переменных и функций.

5. Текст программы с детальными комментариями ведущих операторов программы.

6. Результаты тестирования программы на наборе целевых функций с указанием числа итераций и количества вычислений целевой функции. Журнал вычислений, иллюстрирующий поисковый процесс и изменение ключевых переменных.

7. Сначала алгоритм проверяется при целочисленном кодировании, затем при вещественном.

8. Качественный анализ результатов работы алгоритма, статистическая оценка (среднее по 50 прогонам и ее стандартная ошибка).

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

10. Графики функции, построенные в среде MathCAD или MatLab (если целевая функция зависит не более чем от двух переменных, то построить трехмерный график и контурные графики по всем парам переменных функции, иначе – только контурные графики).

11. Выводы по работе.

12. Ответы на контрольные вопросы.

13. Список использованной литературы.