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

Мощность популяции 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 каждой особи ведет к экспоненциальному росту размеров популяции. Поэтому для каждой особи срок жизни вычисляется индивидуально в зависимости от значения ее ЦФ.

 

Стратегия определения срока жизни

Наиболее часто используются следующие три способа определения срока жизни.

Для их определения введем следующие обозначения:

 - среднее значение ЦФ по популяции;

f_max  - максимальное значение ЦФ по популяции;

f_min -   минимальное значение ЦФ по популяции;

f_{a max}  - абсолютное максимальное значение;

f _{a min} - абсолютное минимальное значение;

L_max  - максимальный срок жизни;

L_min – минимальный срок жизни;

 

1. При пропорциональном методе определения срока жизни

L_f определяется по следующей формуле:

L_f = min ,

где η = ∙(L_max - L_min) (используется для всех формул).

2. При линейном методе определения срока жизни

3. В билинейном методе определения срока жизни

         , если ≥ f [ i ]

L_f =

  , если < f [i]

                                                            

Очевидно, что первый метод соответствует пропорциональному отбору отбора родителей - «рулетке». К минимальному сроку жизни добавляется премиальный срок, который пропорционален значению ЦФ для данной особи. Однако, эта стратегия имеет серьезный недостаток - она не учитывает информацию, о некоторых объективных характеристиках особи, такой, например, как отношение  (или ) целевой функции по популяции.

Эту проблему решает вторая (линейная) стратегия, где срок жизни определяется исходя из значения ЦФ данной особи относительно максимального значения в популяции f_max. Но этот метод тоже имеет свои недостатки - если в популяции много особей имеют значение ЦФ стремящееся к максимальному  значению, то такой подход приведет к чрезмерному увеличению размера популяции.

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

 

Адаптивные ГА

В адаптивных генетических алгоритмах изменяются параметры ГА, прежде всего, вероятности кроссинговера и мутации Р_с и Р_т.

Для оптимизации, особенно мультимодальных функций, наиболее существенными являются две характеристики ГА:

- способность сходиться к оптимуму (локальному  или глобальному) после нахождения области, содержащей этот оптимум;

- способность находить новые области в пространстве решений в поисках глобального оптимума.

Баланс между этими характеристиками ГА определяется значениями вероятности Р_с и Р_т и типом используемых генетических операторов (прежде всего кроссинговера). Увеличение значений P_c  и P_m ведет к расширению пространства поиска.

Обычно используют следующие значения вероятностей Р_с  [0.5;1] и

P_m . Далее мы рассмотрим другой подход, который использует различные значения Р_с и Р_т в зависимости от значения ЦФ текущих особей. Для мультимодальных функций существует серьезная проблема преждевременной сходимости к локальным экстремумам.

Чтобы изменять Р_с и Р_т адаптивно, с целью предотвращения преждевременной сходимости к локальному экстремуму, надо научиться идентифицировать ситуации, когда ГА сходится к оптимуму. Рассмотрим этот подход на примере поиска максимума для мультимодальной функции (которая имеет несколько экстремумов), которая показана на рисунке.

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

Поскольку вероятности Р_с и Р_т должны увеличиваться при преждевременной сходимости к локальному оптимуму (чтобы «выпрыгнуть из ловушки» локального экстремума), то значение

должны изменяться обратно пропорционально разности :

P_c = , P_m = .

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

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

Чтобы решить эту проблему, нужно сохранить хорошие решения текущей популяции. Это можно сделать, полагая  низкие значения

вероятности Р_с и Р_т для особей с высоким значением ЦФ и высокие значения Р_с и Р_т для плохих особей с низкими значениями ЦФ. Тогда лучшие решения будут способствовать сходимости, а худшие - предотвращать ГА от «ловушек» локальных экстремумов. Таким образом, значение Р_с   и Р_т должны зависеть не только от разности , но еще и от значений ЦФ конкретных особей. Чем ближе значение функции к максимальному, тем меньше должно быть значение Р_с и  Р_т:

, k₁ ≤ 1,

, k₂ ≤ 1,

где  - лучшее значение целевой функции у двух родителей.

Положим P_c=P_m=0 для решений, имеющих максимальное значение ЦФ и

           P_c = k₁,         

           P_m= k₂, .

 

Отметим, что для плохих решений  значения вероятностей

Р_с и Р_т в соответствии с формулой могут быть больше 1, что некорректно. Поэтому для плохих решений примем:

           P_c = k₃,         

           P_m= k₄, .

 

В итоге получим:

 

P_c =

k₃, иначе

 

P_m=

k₄, иначе

 

k₁ = k₃ = 1;

k₂ = k₄ = 0.5.

 

Лучшие решения при этом сохраняются и переходят в следующее поколение. Этот факт может привести к чрезмерному росту популяции, что чревато преждевременной сходимостью. Поэтому иногда дополнительно вводится одна (default) мутация (с вероятностью P_d - 0.005) для всех особей популяции.

Существуют и более строгие адаптивные ГА, где вероятности Р_с и Р_т вычисляются аналитически, но они, как правило, сильно привязаны к конкретным задачам. Достаточно эффективным средством адаптации является использование «нечетких контроллеров» в виде, например, системы продукций в нечеткой логике.

 

РЬ?