4.8.6. Ниши в генетическом алгоритме

В различных оптимизационных задачах часто приходится иметь дело с функциями, имеющими несколько оптимальных решений. Основной генетический алгоритм в таких случаях находит только глобальный оптимум, но если имеется несколько оптимумов с одним и тем же значением, то он отыскивает только один из них. В некоторых задачах бывает важным найти не только глобальный оптимум, но и локальные оптимумы (не обязательно все). Концепция реализации в генетических алгоритмах подхода, основанного на известных из биологии понятиях ниш и видов, позволяет находить большую часть оптимумов. Практически применяемый в генетическом алгоритме метод образования ниш и видов основан на так называемой функции соучастия (sharing function). Эта функция определяет уровень близости и степень соучастия для каждой хромосомы в популяции. Функция соучастия обозначается , где  - мера расстояния между хромосомами  и . В программе FlexTool [48] это расстояние определяется по формуле

,

где  означает размерность задачи,  и  определяют соответственно минимальное и максимальное значение –го параметра,  и  - обозначают соответственно -й параметр -й и -й особей. Очевидно, что расстояние между хромосомами рассчитывается на основе соответствующих им фенотипов.

Функция соучастия  должна обладать следующими свойствами:

 для каждого ,

,

.

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

где  и  - константы.

В программе FlexTool , где  обозначает задаваемое пользователем примерное количество пиков оптимизируемой функции. Значение со принимается равным 1, что означает одинаковую степень соучастия соседних особей. В этом случае новое значение функции приспособленности хромосомы  рассчитывается по формуле

,            (4.17)

где  обозначает количество хромосом в популяции.

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

Имеются также и различные модификации процедуры образования ниш для генетического алгоритма. Например, можно определить меру расстояния между хромосомами не на уровне фенотипа (т.е. параметров задачи), а на уровне генотипа. В этом случае аргументом функции соучастия будет расстояние Хемминга между кодовыми последовательностями [15]. Известны и другие подходы к модификации функции приспособленности для генетического алгоритма с нишами [33].