|
При выполнении скрещивания выбирается вероятность скрещивания Rc и генерируется случайное число N e. Если Rc > N c, то случайным образом выбирается точка скрещивания z (z mod с = 0) и выполняется скрещивание (рисунки 2.8 и 2.9). Точка скрещивания z определяет номер объекта кластеризации, начиная с нечетких степеней принадлежности которого происходит обмен частями хромосом-родитслей. Условие z mod с —0 обеспечивает обмен всеми нечеткими степенями принадлежности некоторого объекта, го есть выполнение условия: У]г/у(х;.)= 1 (Vxi е Х ), где с количество кластем ров X j ( j е {2,...,с}), u f{xf) ФП объекта xi кластеру X j . При выполнении мутации выбирается вероятность мутации Rir и генерируется случайное число N т. Если Rm> N m, то случайным образом выбирается точка мутации z (z mod с = 0) и выполняется мутация. Точка мутации z определяет номер объекта, для нечетких степеней принадлежности которого будет выполняться му тация. Затем случайным образом выбирается точка w (н’б{ 1 ), определяющая номер мутирующего гена (нечеткой степени принадлежности объекта кластеру w) для объекта с номером z (рисунки 2.10 и 2.11). Также генерируется случайное число а е [0 s(w), 1s(w)], где s(w) значение нечеткой степени принадлежности объекта г кластеру w. Тогда новое значение нечеткой степени принадлежности в точке мутации, определяющей принадлежность объекта z кластеру w, находится как: s(w) = ^(w) + а . (2.20) Нечеткие степени принадлежности данного объекта z другим кластерам с номерами, не равными w, изменяются следующим образом: s(t) = s ( t ) a / ( c l ) (t = \,c, t * w ) . (2.21) В этом случае теистический алгоритм имеет следующий вид. 1. Случайным образом создается популяция размером Р в соответствии с формулой (2.1) для нечетких степеней принадлежности объектов кластерам и формулой (2.6) для центров кластеров с проверкой условия «жизне91 |
4.3.4 Генетический алгоритм для хромосомы, закодированной нечеткнми степенями принадлежности объектов центрам кластеров Как уже отмечалось выше, при кодировании хромосомы нечеткими степенями принадлежности объектов центрам кластеров первые с координат соответствуют нечетким степеням принадлежности первого объекта нечетким кластерам, вторые с координат —нечетким степеням принадлежности второго объекта кластерам и т.н. Следовательно, сумма первых с координат хромосомы, сумма вторых с координат хромосомы и т.п. равна единице. Пример хромосомы для случая разбиения множества объектов на 4 кластера приведен на рисунке 4.6. Генетический алгоритм реализуется так же, как и ГА, приведенный в пп. 4.3.3. Однако имеются некоторые отличия при выполнении операций скрещивания и мутации. Отметим, что начальная популяция генерируется таким образом, чтобы она состояла только из «жизнеспособных» хромосом, иначе эффективность применения ГА будет значительно снижена. Выбор родителей осуществляется с использованием вероятностного отбора на основе формулы (4.38). При выполнении скрещивания выбирается вероятность скрещивания Rc и генерируется случайное число Nc. Если Rc > N с, то случайным образом выбирается точка скрещивания z (z mod с = 0 ) и выполняется скрещиватше (рисунки 4.7 п 4.8). Точка скрещивания z также определяет номер объекта кластеризации, начиная с нечетких степеней принадлежности которого происходит обмен частями хромосом-родителей. Выполнение условия z mod с 0 обеспечивает обмен всеми нечеткими степенями принадлежности некоторого объекта, а, следовательно, выполнеС пие условия: ^ и}(х,) = 1 (Ух, е X ), где с количество нечетких кластеров j=i X (j е {2,...,с}), iij(xt) ФП объекта х, кластеру X . 272 1 1 1 0 ,6 0,1 0 ,2 0 ,1 0,4 0,4 0 ,1 0 ,1 т I Точка мутации Рисунок 4.9 Хромосома до выполнения операции мутации 1 1 1 0 ,6 0,1 0 ,2 0 ,1 0,35 0,55 0,05 0,05 тI I I Точка мутации Рисунок 4.10 Хромосома после выполнения операции мутации при а 0,15 При выполнении мутации выбирается вероятность мутации Rm и генерируется случайное число N m. Если Rm> N m, то случайным образом выбирается точка мутации z (z mod с = 0 ) и выполняется мутация. Точка мутации z также определяет номер объекта, для нечетких степеней принадлежности которого будет выполняться мутация. Далее случайным образом выбирается точка w (w e{l,...,c} ), определяющая номер мутирующего гена (нечеткой степени принадлежности объекта кластеру w) для объекта с номером z (рисунки 4.9 и 4.10). Также генерируется случайное число а е [ 0 s(w), 1s(u')], где ,v(vv) значение нечеткой степени принадлежности объекта z кластеру w. Тогда новое значение нечеткой степени принадлежности в точке мутации, определяющей принадлежность объекта z кластеру w, находится как: 274 s(u') = ,v(w)+ a (4.40) Соответствующим образом изменяются и нечеткие степенипринадлежности данного объекта z другим кластерам с номерами, не равными w : 1. Случайнымобразом=создается популяция размером Р в соответствии с формулой (4.1) для нечетких степеней принадлежности объектов кластерам и формулой (4.7) для центров кластеров с проверкой условия «жизнеспособности» хромосом, то есть требования о разбиения на заданное число кластеров: с —с* (рисунок 4.6): . 2. При g < G (G и. g максимальное и текущее количество поколений ГА соответственно) вычисляется значение функции соответствия (4.36) для каждой хромосомы и создается.i?c •Р /2 Пар хромосом-родителей. 3. Выполняются,операции;скрещивания (рисунки 4.7 и 4.8):и мутации (рисунки 4.9 и 4.10) для текущей популяции с проверкой условия «жизнеспособности» хромосом, то есть требования о разбиения на заданное количество кластеров: с = с 4; Создается новая популяция размером Р , дополненная хромосомамиотпрысками в количестве Рс ■Р , затем Рс •Р хромосом с худшими значениями функции соответствия (4.36) отбрасываются. Если g < G , осуществляется переход к шагу 2.-Если g > G , то работа ГА завершается и осуществляется переход к шагу 5. . 5. Выбирается лучшая хромосома, которая минимизирует функцию соответствия (4.36) и для нее вычисляются новые координаты центров нечетких кластеров в соответствии (4.7). Нечеткая кластеризация на основе ГА с использованием хромосом, кодированных нечеткими степенями принадлежности объектов центрам кла(4.41) 275 |