Генетические алгоритмы с изменяемой мощностью популяций

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

На разных этапах работы ГА оптимальное значение N может быть различным. На начальном этапе N должно быть большим, а на заключительном N можно уменьшить.

При одном из подходов в ГА с изменяемым размером популяции каждой особи после ее рождения на текущем этапе оценки ЦФ присваивается «время жизни» (life time) L_f параметр, зависящий от ЦФ особи. Таким образом, каждая особь живет определенное число поколений и умирает по окончании срока жизни. Очевидно, значение этого параметра влияет на размер популяции. В этом случае ГА можно реализовать, например, следующим образом.

Нестационарный_ГА

{

t=0;

Инициализация;

Оценка ЦФ p(t);

While (условие окончания не выполнено)

{

t=t+l;

Увеличение возраста каждой особи на 1;

Рекомбинация p(t):

Мутация p(t):

Оценка ЦФ p(t):

Определение срока жизни особей;

Удаление из p(t) всех особей с возрастом больше срока жизни;

}

}

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

r^t_cr+r^t_m = r^t_a = r ∙P.

Тогда |P(t+1)|=|P(t)|+r^t_a–D(t) - число особей в новой популяции. Срок жизни для каждой особи определяется после оценки ЦФ (по формулам, приведенным ниже) и является окончательным, то есть постоянным в процессе эволюции. В таком случае особь живет определенное число поколений, а затем умирает. Срок жизни определяет число поколений, в течении которых особь держится в популяции. Очевидно, что в этом случае, чем больше срок жизни, тем больше потомков может дать особь, так как на каждом этапе родители для рекомбинации выбираются случайно с равной вероятностью. При этом подходе важнейшую роль играет метод определения срока жизни особи.

Очевидно, постоянное значении L_f ≥ 2 каждой особи ведет к экспоненциальному росту размеров популяции. Поэтому для каждой особи срок жизни вычисляется индивидуально в зависимости от значения ее ЦФ.