Изучение различных кодировок генотипа

ГЛАВА 3. ПРАКТИМУМ

 

Исследование генетического алгоритма.

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

Цель работы – изучение генетического алгоритма в простейшем его варианте с целочисленным кодированием хромосом.

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

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

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

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

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

М6 – популяция 60 особей, турнирный отбор (размер 3), однородное скрещивание (p_c = 0,85), мутация (p_m = 0,2), инверсия (p_I = 0,03), условие остановки - 70 итераций;

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

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

Для всех вариантов: Длина гена m = 12.

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

№	Функция y (x)	Поисковый интервал
(1)	100(x 2 – x 12)2 + (1 – x 1)2	x 1 Î (–10; 10); x 2 Î (-10; 10);
(2)	(x 1 – 1)2 + (x 2 – 3)2 + 4(x 3 + 5)2	x 1 Î (–10; 10); x 2 Î (-10; 10); x 3 Î (-10; 10);
(3)	8 x 12 + 4 x 1 x 2 + 5 x 22	x 1 Î (–5,12; 5,12); x 2 Î (–5,12; 5,12);
(4)	4(x 1 – 5)2 + (x 2 – 6)2	x 1 Î (0; 10); x 2 Î (0; 10);
(5)	(x 2 – x 12)2 + (1 – x 1)2	x 1 Î (–5,12; 5,12); x 2 Î (–5,12; 5,12);
(6)	(x 2 – x 12)2 + 100(1 – x 12)2	x 1 Î (0; 5,12); x 2 Î (0; 5,12);
(7)	3(x 1 – 4)2 + 5(x 2 + 3)2 + 7(2 x 3 + 1)2	x 1 Î (–5,12; 5,12); x 2 Î (–5,12; 5,12); x 3 Î (–5,12; 5,12);
(8)	x 13 + x 22 – 3 x 1 – 2 x 2 + 2	x 1 Î (–5,12; 1); x 2 Î (–5,12; 1);

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

Вариант
Метод	М1	М2	М3	М4	М5	М6	М7	М8
Тестовая функция	(1)	(2)	(3)	(4)	(5)	(6)	(7)	(8)

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

1.Изложить суть операторов скрещивания и мутации. В чем состоит их роль в поисковом процессе?

2.Чем отличается однородное скрещивание от 1 и 2-точечного скрещивания?

3.Какие основные отличия генетических алгоритмов от классических методов оптимизации Вы знаете?

4.Вручную расписать первые 2 итерации генетического алгоритма для задачи минимизации функции y(x) = x₁² +x₂² со следующими параметрами: целочисленное кодирование (m = 4 бит/ген); численность популяции N = 5; разрыв поколений T = 1 (элитных особей нет); турнирный отбор (размер 2); 1-точечное скрещивание (p_c = 0,8); мутация (p_m = 0,1); остальные параметры и псевдослучайные величины взять произвольными по необходимости.

5.Допустим, перед Вами стоит следующая абстрактная задача: сгенерировать слово «САПР» с помощью генетического алгоритма. Как бы Вы определили сущность особи для данной задачи? Как бы кодировали ее генотип? Каким образом бы Вы задали функцию приспособленности? Желательно рассмотреть два варианта: а) поисковый процесс работает только с 3-значными комбинациями букв; б) в поисковом процессе могут участвовать слова различной длины.

Содержание отчета

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

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

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

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

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

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

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

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

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

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

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

Изучение различных кодировок генотипа.

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

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

М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-a скрещивание (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-a скрещивание (p_c = 0,7), мутация (p_m = 0,07). Условие остановки - 70 итераций;

М7 – популяция 100 особей, турнирный отбор (размер 4). Для целочисленной кодировки: 1-точечное скрещивание (p_c = 0,9), мутация (p_m = 0,1). Для вещественной кодировки: BLX-a скрещивание (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)	–12 x 2 + 4 x 12 + 4 x 22 – 4 x 1 x 2	x 1 Î (–10; 10); x 2 Î (-10; 10);
(10)	(x 1 – 2)4 + (x 1 – 2 x 2)2	x 1 Î (–10; 10); x 2 Î (-10; 10);
(11)	(x 1 x 2 x 3 – 1)2 + 5[ x 3(x 1 + x 2) – 2]2 + + 2(x 1 + x 2 + x 3 – 3)2	x 1 Î (–5,12; 5,12); x 2 Î (–5,12; 5,12); x 3 Î (–5,12; 5,12);
(12)	4 x 12 + 3 x 22 – 4 x 1 x 22 + x 1	x 1 Î (-5; 10); x 2 Î (0; 10);
(13)	(x 12 + x 2 – 11)2 + (x 1 + x 22 – 7)2	x 1 Î (–5,12; 5,12); x 2 Î (–5,12; 5,12);
(14)	100(x 2 – x 13)2 + (1 – x 1)2	x 1 Î (0; 5,12); x 2 Î (0; 5,12);
(15)	[1.5 – x 1(1 – x 2)]2 + [2.25 – x 1(1 – x 22)]2 + + [2.625 – x 1(1 – x 23)]2	x 1 Î (–5,12; 5,12); x 2 Î (–5,12; 5,12);
(16)	(x 1 + 10 x 2)2 + 5(x 3 – x 4)2 + (x 2 – 2 x 3)4 + 10(x 1 – x 4)4 (матрица Гессе в точке x * - сингулярная)	x 1 Î (–5,12; 5,12); x 2 Î (–5,12; 5,12); x 3 Î (–5,12; 5,12); x 4 Î (–5,12; 5,12);
(17)	100(x 2 – x 12)2 + (1 – x 1)2 + 90(x 4 – x 32)2 + (1 – x 3)3 + 10.1[(x 2 – 1)2 + (x 4 – 1)2] + 19.8(x 2 – 1)(x 4 – 1) (функция имеет несколько локальных минимумов)	x 1 Î (–5,12; 5,12); x 2 Î (–5,12; 5,12); x 3 Î (–5,12; 5,12); x 4 Î (–5,12; 5,12);
(18)	(2 x 12 + 3 x 22)exp(x 12 – x 22) (функция не унимодальная)	x 1 Î (–5,12; 10); x 2 Î (–5,12; 10);
(19)	0.1(12 + x 12 + (1 + x 22)/ x 12 + (x 12 x 22 + 100)/(x 14 x 24))	x 1 Î (–5,12; 3); x 2 Î (–5,12; 3);
(20)	100[ x 3 – 0.25(x 1 + x 2)2]2 + (1 – x 1)2 + (1 – x 2)2	x 1 Î (–5,12; 3); x 2 Î (–5,12; 3); x 3 Î (–5,12; 5,12);

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

Вариант
Метод	М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.Качественный анализ результатов работы алгоритма (пример см. в разд. 6.1), статистическая оценка (среднее по 50 прогонам и ее стандартная ошибка).

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

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

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

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