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

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

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

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

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

Баланс между этими характеристиками ГА определяется значениями вероятности Р_с и Р_т и типом используемых генетических операторов (прежде всего кроссинговера). Увеличение значений 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) для всех особей популяции.

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