Одним из центральных понятий при эволюционном моделировании является функция приспособленности. При оптимизации с помощью генетического алгоритма в качестве функции приспособленности используется критерий оптимальности решаемой. Для расчёта приспособленности особи её необходимо перекодировать в вещественную форму.
В большинстве случаев имеющийся формализованный вид критерия оптимальности может быть без проблем использован напрямую в качестве функции приспособленности. Тем не менее, иногда возникает необходимость в его предварительном преобразовании – масштабировании.
Масштабирование функции приспособленности чаще всего выполняется по двум причинам. Во-первых, для предотвращения преждевременной сходимости генетического алгоритма. Она заключается в том, что в популяции начинают доминировать лучшие, но не оптимальные особи. В этом случае через несколько поколений популяция окажется вырожденной, то есть будет состоять из копий одной из таких особей.
Во-вторых, в случаях, когда в популяции сохраняется значительная неоднородность, но средняя приспособленность популяции ненамного отличается от максимального значения. Здесь масштабирование функции приспособленности позволяет предупредить возникновение ситуации, в которой средние и наилучшие особи формируют примерно одинаковое количество потомков в новых поколениях.
Применяют три основных способа масштабирования:
– линейное;
– сигма-отсечение;
– степенное.
Линейное масштабирование заключается в таком преобразовании функции приспособленности, при котором её среднее значение до масштабирования было бы равно её среднему значению после него, а приспособленность лучшей особи отличалась бы от средней приспособленности в 1,2–2,0 раза. Для выполнения указанных требований специально подбирают коэффициенты a и b масштабирующей зависимости:
Сигма-отсечение – метод масштабирования, основанный на преобразовании функции приспособленности с помощью выражения (формула приведена для решения задачи максимизации):
где – средняя приспособленность популяции при её начальной генерации; c – малое натуральное число (как правило, из отрезка от 1 до 5); σ – стандартное (среднеквадратичное) отклонение принадлежностей особей по популяции.
Степенное масштабирование – это метод, при котором функция преобразуется к новой форме согласно выражению:
где γ – число, немногим большее единицы, например, 1,005. Оно подбирается эмпирически с учётом специфики решаемой задачи.
По материалам учебного пособия:
Дударов С. П. Математические основы генетических алгоритмов: учеб. пособие/ С. П. Дударов. – М.: РХТУ им. Д. И. Менделеева, 2012. – 56 с.