Пример работы ГА и анализа результатов

При использовании ГА для решения задачи оптимизации необходимо:

1. Определить количество и тип переменных задачи, которые необходимо закодировать в хромосоме.

2. Задать критерий оценки особей в качестве функции приспособленности (целевой функции).

3. Выбрать способ кодирования и его параметры.

4. Эмпирически подобрать параметры ГА (размер популяции, тип селекции, генетические операторы и их вероятности, величина разрыва поколений).

Стоит отметить, что параметры ГА, упомянутые в пункте 4 (а также, иногда, те, что указаны в пунктах 2 и 3), часто задаются методом проб и ошибок, на основе анализа получаемых результатов. Для анализа результатов работы ГА необходимо произвести серию запусков алгоритма. Описанная общая схема решения задачи с использованием ГА показана на рис. 13.

Пример (для задачи минимизации функции):

, n = 10, x_i Î [-5,12; 5,12].

Параметр n задает количество переменных функции z. Необходимо найти такие значения переменных x_i , при которых функция z принимает наименьшее значение.

1. Определение неизвестных переменных задачи.По условию поставленной задачи необходимо найти значения переменных x_i, минимизирующие значение функции z, поэтому в хромосоме будем кодировать значения x_i. Таким образом, каждый i-й ген хромосомы будет соответствовать i-й переменной функции z.

Рис. 13

2. Задание функции приспособленности.имеет смысл определить приспособленность особи как значение, которое зависит от функции z при подстановке в нее вектора параметров x (генотипа этой особи). Поскольку рассматривается задача минимизации функции z, то принимается, что чем меньше значение z, тем лучше приспособлена особь. Приспособленность l-й особи f_l определяется по следующей формуле:

f_l = z_l,

где z_l – значение функции z в точке, соответствующей l-й особи.

3. Выбор способа кодирования.В качестве способа представления генетической информации рассматривается целочисленное кодирование с 10-разрядными генами. Учитывая, что содержимое каждого гена может принимать одно из 2¹⁰ = 1024 значений в диапазоне от [-5,12; 5,12], получается, что переменные x_i кодируются в хромосоме с точностью до 0,01.

4. Определение параметров ГА.Для решения задачи рассматривается популяция из 20 особей. Для отбора особей используется турнирная селекция. В качестве генетических операторов предлагается применить 1-точечное скрещивание и битовую мутацию. Вероятности применения операторов скрещивания и мутации задаются равными 0,7 и L^-1 = 0,01 (где L – длина хромосомы в битах, в данном случае L = 100) соответственно. Новое поколение формируется только из особей-потомков, т.е. величина разрыва поколений T равна 1. Результат работы ГА с выбранными параметрами представлен на рис. 14.

Рис. 14. Динамика z_min(k) и <z>(k). Популяция из 20 особей, турнирная селекция, одноточечное скрещивание (p_c= 0,7), битовая мутация (p_m = 0,01).

Показаны зависимости изменения среднего <z> и наименьшего z_min по популяции значения функции z от номера поколения k. Данные усреднены по 50 независимым запускам. Тонкими огибающими линиями показаны статистические 95%-ные доверительные интервалы по 50 запускам. Из рисунка видно, что после 20 поколения значение z_min практически стабилизировалось и перестало «улучшаться». Из этого следует, что генерации новых хороших особей не происходит, и следует увеличить вероятность мутации, например, до 0,1. Результаты работы ГА с измененным значением вероятности мутации показаны на рис. 15.

Рис. 15. Динамика z_min(t) и <z>(t). Популяция из 20 особей, турнирная селекция, одноточечное скрещивание (p_c = 0,7), битовая мутация (p_m = 0,1).

Увеличение вероятности мутации улучшило результат работы ГА. Стоит отметить, что теперь эволюционный процесс стабилизировался значительно позднее, примерно после 60 поколения. Минимальное значение функции z, достигнутое за отрезок из первых 100 поколений, примерно равно 9,7. Чтобы улучшить результат, имеет смысл установить разрыв поколений, например, равным T = 0,97. Результат представлен на рис. 16.

Увеличение разрыва поколений привело к ускорению эволюционного поиска за счет сохранения 3% элитных особей от популяции на каждой итерации ГА. Хотя на стабилизацию значения z_min потребовалось почти 80 поколений, было найдено новое минимальное значение функции z равно 6,8.

Аналитически можно найти, что минимум функции z лежит в точке x_i = 0, i = 1, 2,…, 10 и значение z_min = 0. В случае поиска минимума функции z с точностью 0,01, для ГА с параметрами, соответствующими графику на рис. 16, решение не было найдено с заданной точностью ни в

Рис. 16. Динамика z_min(t) и <z>(t). Популяция из 20 особей, турнирная селекция, разрыв поколений T = 0,97, одноточечное скрещивание (p_c = 0,7), битовая мутация (p_m = 0,1).

одном из 50 запусков. Чтобы найти решение имеет смысл увеличить размер популяции до 100 особей. Полученная динамика z_min(t) и <z>(t) изображена на рис. 17.

Рис. 17. Динамика z_min(t) и <z>(t). Популяция из 100 особей, турнирная селекция, разрыв поколений T = 0,97, одноточечное скрещивание (p_c = 0,7), битовая мутация (p_m = 0,1).

В 48 из 50 запусков был найден минимум функции z с точностью 0,01. Среднее количество вычислений целевой функции, использованное для нахождения решения, равно 1904,26.