Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
10. Ниши в генетическом алгоритме: сущность образования ниш и видов, мера расстояния между хромосомами, функция соучастия.
Ниши в генетическом алгоритме
В различных оптимизационных задачах часто приходится иметь дело с функциями, имеющими несколько оптимальных решений. Основной генетический алгоритм в таких случаях находит только глобальный оптимум, но если имеется несколько оптимумов с одним и тем же значением, то он отыскивает только один из них. В некоторых задачах бывает важным найти не только глобальный оптимум, но и локальные оптимумы (не обязательно все). Концепция реализации в генетических алгоритмах подхода, основанного на известных из биологии понятиях ниш и видов, позволяет находить большую часть оптимумов. Практически применяемый в генетическом алгоритме метод образования ниш и видов основан на так называемой функции соучастия (sharing function). Эта функция определяет уровень близости и степень соучастия для каждой хромосомы в популяции. Функция соучастия обозначается s(dj), где dj - мера расстояния между хромосомами chi, и chj. В программе FlexTool это расстояние определяется по формуле
где p означает размерность задачи, xk,min и хк,mах определяют соответственно минимальное и максимальное значение k-го параметра, xk,j и xk,j - обозначают соответственно k-й параметр i-й и j-й особей.
В программе FlexTool функции соучастия принимает вид
где N обозначает количество хромосом в популяции.
Если хромосома chi находится в своей нише в одиночестве, то Fs(chj) = F(chi). В противном случае значение функции приспособленности уменьшается пропорционально количеству и степени близости соседствующих хромосом. Из выражения последней формулы следует, что увеличение количества похожих друг на друга (т.е. принадлежащих к одной и той же нише) хромосом ограничено, поскольку такое увеличение приводит к уменьшению значения функции приспособленности. В программе FlexTool при реализации генетического алгоритма с нишами представляемый метод используется на завершающем этапе обработки каждого поколения.
Имеются также и различные модификации процедуры образования ниш для генетического алгоритма. Например, можно определить меру расстояния между хромосомами не на уровне фенотипа (т.е. параметров задачи), а на уровне генотипа. В этом случае аргументом функции соучастия будет расстояние Хемминга между кодовыми последовательностями.