Масштабирование функции приспособленности

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

мируют практически одинаковое количество потомков в следующих поколениях, что считается нежелательным явлением. Преждевремен­ная сходимость алгоритма заключается в том, что в популяции начи­нают доминировать наилучшие, но еще не оптимальные хромосомы. Такая возможность характерна для алгоритмов с селекцией по мето­ду колеса рулетки. Через несколько поколений при селекции, пропор­циональной значению функции приспособленности, популяция будет состоять исключительно из копий наилучшей хромосомы исходной популяции. Представляется маловероятным, что именно эта хромо­сома будет соответствовать оптимальному решению, поскольку ис­ходная популяция - это, как правило, небольшая случайная выборка из всего пространства поиска. Масштабирование функции приспособ­ленности предохраняет популяцию от доминирования неоптималь­ной хромосомы и тем самым предотвращает преждевременную схо­димость генетического алгоритма.

Масштабирование заключается в соответствующем преобразо­вании функции приспособленности. Различают 3 основных метода масштабирования: линейное, сигма-отсечение и степенное [15, 33].

Линейное масштабирование (linear scaling) заключается в пре­образовании функции приспособленности F к форме F через линей­ную зависимость вида

F = a-F + Ь,

где а и Ь - константы, которые следует подбирать таким образом, что­бы среднее значение функции приспособленности после масштаби­рования было равно ее среднему значению до масштабирования, а максимальное значение функции приспособленности после мас­штабирования было кратным ее среднему значению. Коэффициент кратности чаще всего выбирается в пределах от 1,2 до 2. Необходи­мо следить за тем, чтобы функция F не принимала отрицательные значения.

Сигма-отсечение (sigma truncation) - метод масштабиро­вания, основанный на преобразовании функции приспособленности F к форме F согласно выражению

F = F + (F-c-cx),

где F обозначает среднее значение функции приспособленности по всей популяции, с - малое натуральное число (как правило, от 1 до 5), а с - стандартное отклонение по популяции. Если расчетные зна­чения F' отрицательны, то они принимаются равными нулю.

Степенное масштабирование (power law scaling) представля­ет собой метод масштабирования, при котором функция приспособ­ленности F преобразуется к форме F' согласно выражению

F'=F^k,

где к - число, близкое 1. Значение к обычно подбирается эмпиричес­ки с учетом специфики решаемой задачи. Например, можно исполь­зовать к= 1,005.

4.8. Модификации классического генетического алгоритма

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

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

".= £

где р означает размерность задачи, xj< _min и x_{fc max} определяют соответ­ственно минимальное и максимальное значение k-vo параметра, x_Ki и х/у - обозначают соответственно /с-й параметр /-й и у-й особей. Очевидно, что расстояние между хромосомами рассчитывается на основе соответствующих им фенотипов.

Функция соучастия s(cf;y) должна обладать следующими свойст­вами:

О < s(djj) < 1 для каждого d/j,

s(0)=1, lim s(dj:) = O.

d_e-xo

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

1~(djjlo-_sf, если d_f<or_e,

ij) =

О в противном случае,

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

В программе FlexTool o_s = 0,5 * g~^1/p> где q обозначает задава­емое пользователем примерное количество пиков оптимизируемой функции. Значение со принимается равным 1, что означает одинако­вую степень соучастия соседних особей. В этом случае новое значе­ние функции приспособленности хромосомы сп,- рассчитывается по формуле

*

(4.17)

/=(ch,)

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

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

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

Дата добавления: 2015-06-04