Применение эвристических операторов

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

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

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

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

М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). Условие остановки - 50 итераций. Дополнительные операторы: уплотнение сетки целочисленного кодирования (условие применения – 30 итераций);

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

М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). Условие остановки - 70 итераций. Дополнительные операторы: уплотнение сетки целочисленного кодирования (условие применения – 50 итераций);

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

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

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

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

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

1.Имеет ли смысл оператор уплотнения сетки для вещественного кодирования?

2.Опишите механизм работы оператора уплотнения целочисленной сетки.

3.Допустим, существует некий обратный оператор для оператора уплотнения сетки. Пусть он называется оператор разрежения сетки и эффект его работы заключается в уменьшении частоты размещения узлов сетки. Имеет ли он смысл? Если да, то какой?

4.Для чего нужен оператор популяционного всплеска?

5.По какому условию могут запускаться дополнительные генетические операторы? Придумайте и изложите свои варианты.

6.Изложите Ваши мысли по поводу эффективности следующих схем:

а) генетический алгоритм выполняет некоторое количество итераций и локализует предполагаемый минимум в поисковом пространстве. Далее лучшая особь используется в качестве стартовой точки для поиска любым классическим методом оптимизации;

б) по определенному условию (например, через каждые k итераций) запускается классический метод оптимизации, используя в качестве стартовой точки лучшую особь генетического алгоритма. Затем он выполняет несколько итераций, пытаясь улучшить фенотип взятой особи, и помещает ее на прежнее место в популяцию. Данная схема называется оператором обучения лидера[2].

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

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

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

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

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

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

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

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

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

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

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

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

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