22. Ниши в генетическом алгоритме
В различных оптимизационных задачах часто приходится иметь дело с функциями, имеющими несколько оптимальных решений. Основной генетический алгоритм в таких случаях находит только глобальный оптимум, но если имеется несколько оптимумов с одним и тем же значением, то он отыскивает только один из них. В некоторых задачах бывает важным найти не только глобальный оптимум, но и локальные оптимумы (не обязательно все). Концепция реализации в генетических алгоритмах подхода, основанного на известных из биологии понятиях ниш и видов, позволяет находить большую часть оптимумов [7].
В биологии формирование популяций, существующих в биологических нишах, соответствует отысканию локальных оптимумов приспособленности к условиям окружающей среды.
Практически применяемый в генетическом алгоритме метод образования ниш и видов основан на так называемой функции соучастия (sharing function). Эта функция определяет уровень близости и степень соучастия для каждой хромосомы в популяции. Функция соучастия обозначается s(dij), где dij – мера расстояния между хромосомами chi и chj.
Под словом «расстояние» подразумевается «различие». Для вычисления расстояния между хромосомами могут использоваться различные подходы. В расчете расстояния может использоваться и фенотип, и генотип. Например, с использованием генотипа можно вычислять расстояние в соответствии с метрикой Хемминга:
|
|
(65) |
,
где
символом
обозначена операция «исключающее ИЛИ»,
возвращающая 1 при равенстве операндов
и 0 – в противном случае, а суммирование
производится по всем генам генотипа.
Функция соучастия s(dij) должна обладать следующими свойствами:
0 < s(dij) < 1 для каждого dij,
s(0) = 1,
Одна из функций, для которой эти условия выполняются, имеет вид
|
|
(66) |
,где σs и ω – константы, рассчитываемые в зависимости от ряда факторов, в частности, от предполагаемого количества пиков оптимизируемой функции.
Новое значение функции приспособленности хромосомы chi может рассчитываться по следующей формуле [7]:
|
|
(67) |
,где N обозначает количество хромосом в популяции.
Если хромосома chi находится в своей нише в одиночестве, то Fs(chi) = F(chi). В противном случае значение функции приспособленности уменьшается пропорционально количеству и степени близости соседствующих хромосом. Из выражения (67) следует, что увеличение количества похожих друг на друга (т.е. принадлежащих к одной и той же нише) хромосом ограничено, поскольку такое увеличение приводит к уменьшению значения функции приспособленности. В программе FlexTool при реализации генетического алгоритма с нишами представляемый метод используется на завершающем этапе обработки каждого поколения