Лекция 9 (Гиренко - Лекции), страница 2

В классическом ГА начальная популяция формируется случайным образом. Фиксируется размер популяции (количество особей в ней будем обозначать символом N), который не изменяется в течение работы всего алгоритма. Каждая особь генерируется как случайная L-битная строка, где L — длина кодировки особи, она тоже фиксирована и для всех особей одинакова.

Следует заметить, что каждая особь является одним из решений поставленной задачи. Более приспособленные особи — это более подходящие ответы. Этим ГА отличается от большинства других алгоритмов оптимизации, которые оперируют лишь с одним решением, улучшая его.

Шаг алгоритма состоит из трех стадий: генерация промежуточной популяции (intermediate generation) путем отбора (selection) текущего поколения (current generation), скрещивание (recombination) особей промежуточной популяции путем кроссовера (crossover), что приводит к формированию нового поколения (next generation), и мутация нового поколения. На рисунке изображены первые две стадии:

Промежуточная популяция — это набор особей, которые получили право размножаться. Приспособленные особи могут быть записаны туда несколько раз. «Плохие» особи с большой вероятностью туда вообще не попадут.

В классическом ГА вероятность каждой особи попасть в промежуточную популяцию пропорциональна ее приспособленности, т. е. работает пропорциональный отбор (proportional selection). Можно его реализовать следующим образом: пусть особи располагаются на колесе рулетки, так что размер сектора каждой особи пропорционален ее приспособленности. Изначально промежуточная популяция пуста. N раз запуская рулетку, выберем требуемое количество особей для записи в промежуточную популяцию. Ни одна выбранная особь не удаляется с рулетки. Такой отбор называется стохастическая выборка.

Другой способ отбора, который также является пропорциональным, это остаточная стохастическая выборка. Для каждой особи вычисляется отношение ее приспособленности к средней приспособленности популяции. Целая часть этого отношения указывает, сколько раз нужно записать особь в промежуточную популяцию, а дробная — это ее вероятность попасть туда еще раз. Пусть, к примеру, для некоторой особи i f_i ⁄ <f> = 1.36 (<f> — средняя приспособленность текущей популяции). Тогда она будет выбрана один раз, а затем с вероятностью 0.36 еще раз. Реализовать такой способ отбора удобно следующим образом: расположим особи на рулетке так же, как было описано. Теперь пусть у рулетки не одна стрелка, а N, причем они отсекают одинаковые сектора. Тогда один запуск рулетки выберет сразу все N особей, которые нужно записать в промежуточную популяцию.

После отбора особи промежуточной популяции случайным образом разбиваются на пары. Каждая из них с вероятностью p_c скрещивается, т. е. к ней применяется оператор кроссовера, в результате чего получаются два потомка. Они записываются в новое поколение. Если же паре не выпало скрещиваться, в новое поколение записываются сами особи этой пары.

В классическом генетическом алгоритме применяется одноточечный оператор кроссовера (1-point crossover): для родительских хромосом (т. е. строк) случайным образом выбирается точка раздела, и они обмениваются отсеченными частями. Полученные две строки являются потомками:

11010 01100101101 ⇒ 10110 01100101101

10110 10011101001 ⇒ 11010 10011101001

К полученному в результате скрещивания новому поколению применяется оператор мутации. Каждый бит каждой особи популяции с вероятностью p_m инвертируется. Эта вероятность обычно очень мала, менее 1%.

1011001100101101 ⇒ 1011001101101101

Таким образом, процесс отбора, скрещивания и мутации приводит к формированию нового поколения. Шаг алгоритма завершается объявлением нового поколения текущим. Далее все действия повторяются.

Вообще говоря, такой процесс эволюции может продолжаться до бесконечности. Критерием останова может служить заданное количество поколений или схождение (convergence) популяции.

Схождением называется такое состояние популяции, когда все строки популяции почти одинаковы и находятся в области некоторого экстремума. В такой ситуации кроссовер практически никак не изменяет популяции. А вышедшие из этой области за счет мутации особи склонны вымирать, так как чаще имеют меньшую приспособленность, особенно если данный экстремум является глобальным максимумом. Таким образом, схождение популяции обычно означает, что найдено лучшее или близкое к нему решение.

Ответом на поставленную задачу может служить набор параметров, кодируемый наилучшей особью последнего поколения.

Пример на языке C:

#include <…>

…

int main()

{

const int N = 1000;

int a[N]; // массив «особей»

//заполняем нулями

fill(a, a+N, 0);

for (;;)

{

//выбираем лучших, отсортировав по возрастанию...

sort(a, a+N);

//... и тогда лучшие окажутся во второй половине массива.

//скопируем лучших в первую половину, куда они оставили потомство, //а первые умерли:

copy(a+N/2, a+N, a /*куда*/);

//мутация в случайную сторону каждого элемента:

for (int i = 0; i < N; ++i)

if (rand()%2 == 1)

a[i] += 1;

else

a[i] -= 1;

//Посмотрим на среднее состояние популяции. Оно всё лучше и лучше.

cout << accumulate(a, a+N, 0) / N << endl;

}

}