Изучение различных кодировок генотипа
ГЛАВА 3. ПРАКТИМУМ
Исследование генетического алгоритма.
Требования задания
Цель работы – изучение генетического алгоритма в простейшем его варианте с целочисленным кодированием хромосом.
М1 – популяция 100 особей, турнирный отбор (размер 2), 1-точечное скрещивание (pc = 0,7), мутация (pm = 0,1), инверсия (pI = 0,05), условие остановки - 100 итераций;
М2 – популяция 50 особей, турнирный отбор (размер 3), 2-точечное скрещивание (pc = 0,8), мутация (pm = 0,03), инверсия (pI = 0,03), условие остановки - 50 итераций;
М3 – популяция 30 особей, турнирный отбор (размер 4), однородное скрещивание (pc = 0,9), мутация (pm = 0,05), условие остановки - разница приспособленности лидера и «наихудшей» особи меньше 0,01;
М4 – популяция 70 особей, турнирный отбор (размер 5), 1-точечное скрещивание (pc = 0,75), инверсия (pI = 0,07), условие остановки - 50 итераций;
М5 – популяция 100 особей, турнирный отбор (размер 2), 2-точечное скрещивание (pc = 0,8), инверсия (pI = 0,1), условие остановки - 100 итераций;
М6 – популяция 60 особей, турнирный отбор (размер 3), однородное скрещивание (pc = 0,85), мутация (pm = 0,2), инверсия (pI = 0,03), условие остановки - 70 итераций;
М7 – популяция 70 особей, турнирный отбор (размер 4), 1-точечное скрещивание (pc = 0,9), мутация (pm = 0,1), условие остановки - 70 итераций;
М8 – популяция 30 особей, турнирный отбор (размер 5), 2-точечное скрещивание (pc = 0,7), мутация (pm = 0,15), условие остановки – разница приспособленности лидера и «наихудшей» особи меньше 0,01.
Для всех вариантов: Длина гена m = 12.
Таблица тестовых функций
| № | Функция y(x) | Поисковый интервал |
| (1) | 100(x2 – x12)2 + (1 – x1)2 | x1 Î (–10; 10); x2 Î (-10; 10); |
| (2) | (x1 – 1)2 + (x2 – 3)2 + 4(x3 + 5)2 | x1 Î (–10; 10); x2 Î (-10; 10); x3 Î (-10; 10); |
| (3) | 8x12 + 4x1x2 + 5x22 | x1 Î (–5,12; 5,12); x2 Î (–5,12; 5,12); |
| (4) | 4(x1 – 5)2 + (x2 – 6)2 | x1 Î (0; 10); x2 Î (0; 10); |
| (5) | (x2 – x12)2 + (1 – x1)2 | x1 Î (–5,12; 5,12);x2 Î (–5,12; 5,12); |
| (6) | (x2 – x12)2 + 100(1 – x12)2 | x1 Î (0; 5,12);x2 Î (0; 5,12); |
| (7) | 3(x1 – 4)2 + 5(x2 + 3)2 + 7(2x3 + 1)2 | x1 Î (–5,12; 5,12);x2 Î (–5,12; 5,12); x3 Î (–5,12; 5,12); |
| (8) | x13 + x22 – 3x1 – 2x2 + 2 | x1 Î (–5,12; 1);x2 Î (–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) = x12 +x22 со следующими параметрами: целочисленное кодирование (m = 4 бит/ген); численность популяции N = 5; разрыв поколений T = 1 (элитных особей нет); турнирный отбор (размер 2); 1-точечное скрещивание (pc = 0,8); мутация (pm = 0,1); остальные параметры и псевдослучайные величины взять произвольными по необходимости.
5.Допустим, перед Вами стоит следующая абстрактная задача: сгенерировать слово «САПР» с помощью генетического алгоритма. Как бы Вы определили сущность особи для данной задачи? Как бы кодировали ее генотип? Каким образом бы Вы задали функцию приспособленности? Желательно рассмотреть два варианта: а) поисковый процесс работает только с 3-значными комбинациями букв; б) в поисковом процессе могут участвовать слова различной длины.
Содержание отчета
1. Цель работы и требования задания.
2. Краткое описание алгоритма на основании материала лекционного курса и описание схемы пошагового выполнения вычислительного алгоритма.
3. Укрупненнаяблок-схема программы с пояснением всех ее частей.
4. Спецификация программы, раскрывающая смысл входных и выходных данных, основных переменных и функций.
5. Текст программы с детальными комментариями ведущих операторов программы.
6. Результаты тестирования программы на наборе целевых функций с указанием числа итераций и количества вычислений целевой функции. Журнал вычислений, иллюстрирующий поисковый процесс и изменение ключевых переменных.
7. Качественный анализ результатов работы алгоритма (пример см. в разд. 6.1), статистическая оценка (среднее по 50 прогонам и ее стандартная ошибка).
8. При неудовлетворительных результатах поиска, исходя из анализа результатов алгоритма, необходимо улучшить результат за счет подгонки данных в задании начальных параметров. Весь процесс отладки алгоритма с соответствующими графиками, комментариями и выводами также должен быть документирован в отчете.
9. Графики функции, построенные в среде MathCAD или MatLab (если целевая функция зависит не более чем от двух переменных, то построить трехмерный график и контурные графики по всем парам переменных функции, иначе – только контурные графики).
10. Выводы по работе.
11. Ответы на контрольные вопросы.
Изучение различных кодировок генотипа.
Требования задания
Цель работы – исследование двух основных способов кодирования генотипа хромосом в генетическом алгоритме и их эффективности.
М1 – популяция 100 особей, турнирный отбор (размер 2). Для целочисленной кодировки: 1-точечное скрещивание (pc = 0,7), мутация (pm = 0,1), инверсия (pI = 0,05). Для вещественной кодировки: 1-точечное скрещивание (pc = 0,7), мутация (pm = 0,1). Условие остановки - 100 итераций;
М2 – популяция 100 особей, турнирный отбор (размер 3). Для целочисленной кодировки: 2-точечное скрещивание (pc = 0,8), мутация (pm = 0,03), инверсия (pI = 0,03). Для вещественной кодировки: BLX-a скрещивание (pc = 0,8), мутация (pm = 0,15). Условие остановки - 50 итераций;
М3 – популяция 100 особей, турнирный отбор (размер 4). Для целочисленной кодировки: однородное скрещивание (pc = 0,9), мутация (pm = 0,05). Для вещественной кодировки: 1-точечное скрещивание (pc = 0,65), мутация (pm = 0,08). Условие остановки - разница приспособленности лидера и «наихудшей» особи меньше 0,01;
М4 – популяция 100 особей, турнирный отбор (размер 5). Для целочисленной кодировки: 1-точечное скрещивание (pc = 0,75), инверсия (pI = 0,07). Для вещественной кодировки: 1-точечное скрещивание (pc = 0,75), мутация (pm = 0,1). Условие остановки - 50 итераций;
М5 – популяция 100 особей, турнирный отбор (размер 2). Для целочисленной кодировки: 2-точечное скрещивание (pc = 0,8), инверсия (pI = 0,1). Для вещественной кодировки: 2-точечное скрещивание (pc = 0,7), мутация (pm = 0,12). Условие остановки - 100 итераций;
М6 – популяция 100 особей, турнирный отбор (размер 3). Для целочисленной кодировки: однородное скрещивание (pc = 0,85), мутация (pm = 0,2), инверсия (pI = 0,03). Для вещественной кодировки: BLX-a скрещивание (pc = 0,7), мутация (pm = 0,07). Условие остановки - 70 итераций;
М7 – популяция 100 особей, турнирный отбор (размер 4). Для целочисленной кодировки: 1-точечное скрещивание (pc = 0,9), мутация (pm = 0,1). Для вещественной кодировки: BLX-a скрещивание (pc = 0,7), мутация (pm = 0,13). Условие остановки - 70 итераций;
М8 – популяция 100 особей, турнирный отбор (размер 5). Для целочисленной кодировки: 2-точечное скрещивание (pc = 0,7), мутация (pm = 0,15). Для вещественной кодировки: 1-точечное скрещивание (pc = 0,7), мутация (pm = 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 |
| Тестовая функция | (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. Ответы на контрольные вопросы.