Практическое занятие 8. Исследование схемы «генетический алгоритм – классический метод оптимизации».

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

Цель работы – модификация программы, исполненной на практическом занятии №6 для изучения схемы «генетический алгоритм – классический метод оптимизации». При выполнении данной лабораторной работы предлагается выбрать целочисленное кодирование хромосом.

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

М2 – популяция 50 особей, турнирный отбор (размер 3), 2-точечное скрещивание (p_c = 0,8), мутация (p_m = 0,03), инверсия (p_I = 0,03), условие остановки - 50 итераций. После останова генетического алгоритма лучшую особь используем в качестве стартовой точки для метода Бройдена–Флетчера–Гольдфарба–Шенно (150 итераций);

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

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

М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 итераций. После останова генетического алгоритма лучшую особь используем в качестве стартовой точки для метода Розенброка (200 итераций);

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

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

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

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

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

1. В чем, по Вашему мнению, преимущество данной гибридной схемы перед классическим генетическим алгоритмом? Перед классическим методом?

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

3. Необходимо ли накладывать на классический метод оптимизации те же ограничения, что накладываются на генетический алгоритм при задании поисковых интервалов для каждого параметра? Что может произойти, если их не накладывать?

4. Какие еще варианты совместного применения классических методов оптимизации и генетического алгоритма Вы можете придумать? Обоснуйте их эффективность.

5. Допустим, что есть некая схема «классический метод оптимизации – генетический алгоритм». Каким образом классический метод может «помочь» генетическому алгоритму перед поиском? Изложите ваши идеи.

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

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

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

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

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

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

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

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

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

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

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

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

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