|
ниями функции соответствия (2.16) отбрасываются. Если g < G, осуществляется переход к шагу 2. Если g > G , то работа ГА завершается и осуществляется переход к шагу 5. 5. Выбирается лучшая хромосома, которая минимизирует функцию соответствия (2.16). Для каждого объекта кластеризации определяются нечеткие степени принадлежности к нечетким кластерам с новыми центрами кластеров в соответствии с формулой (2.5). Нечеткая кластеризация на основе ГА с использованием хромосом постоянной длины, закодированных координатами центров кластеров, позволяет получить более адекватные результаты кластеризации с нахождением субминимума индекса Се Бени по формуле (2.16), однако требует большого количества смен поколении G . 2.3.4 Генетический алгоритм с хромосомой постоянной длины, закодированной нечеткими степенями принадлежности объектов центрам кластеров При кодировании хромосомы нечеткими степенями принадлежности объектов центрам кластеров сумма первых с координат хромосомы, сумма вторых с координат хромосомы и т.п. равна единице, так как первые с координат соответствуют нечетким степеням принадлежности первого объекта нечетким кластерам, вторые с координат нечетким степеням принадлежности второго объекта кластерам и т.п. Пример хромосомы для случая разбиения множества объектов на 4 кластера приведен на рисунке 2.7. Генетический алгоритм реализуется так же, как и ГА, приведенный в п. 2.3.3, но имеется ряд отличий при выполнении операций скрещивания и мутации. Начальная популяция, как и в п. 2.3.3, формируется таким образом, чтобы она состояла только из «жизнеспособных» хромосом, иначе эффективность применения ГА будет значительно снижена. Выбор родителей осуществляется с использованием вероятностного отбора на основе формулы (2.18). 88 |
I I I I I I I I V,' vi V,2 v22 < Vj v; Рисунок 4.4 fТочка мутации Хромосома до выполшгния операп ии мутации 1 1 v v; vi V,2 к V,2 •f *1 < Точка мутации Рисунок 4.5 Хромосома после выполнения операции мутации 4. Создается новая популяция размером Р , дополненная хромосомамиотпрысками в количестве Rc ■Р , затем Rc ■Р хромосом с худшими значениями функции соответствия (4.36) отбрасываются. Если g < G , осуществляется переход к шагу 2. Если g >G , то работа ГА завершается и осуществляется переход к шагу 5. 5. Выбирается лучшая хромосома, которая минимизирует функцию соответствия (4.36). Для каждого объекта кластеризации определяются нечеткие степени принадлежности к нечетким кластерам с новыми центрами кластеров в соответствии с формулой (4.6). Как показывает анализ, нечеткая кластеризация на основе ГА с использованием хромосом, закодированных координатами центров кластеров, позволяет получить более адекватные результаты кластеризации с нахождением субминимума индекса Се Бени по формуле (4.36), однако требует большого количества смен поколений G . 271 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 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 |