|
Для повышения эффективности ГА предлагается в процессе формирования расширенной популяции хромосом очередного поколения ГА учитывать популяцию размером Р, полученную в предыдущем поколении, и новую популяцию размером (Р + Rc •Р)9 полученную в текущем поколении. При этом для всех хромосом новой популяции размером (Р + Rc •Р) выполняется один шаг РСМ-алгоритма на основе НМТ1. В результате формируется расширенная популяция размером (2 •F + Лс •Р ), хромосомы которой упорядочиваются по возрастанию значений функции соответствия (индекса Се — Бени) по формуле (2.16). Результирующая популяция размером Р получается путём отбрасывания из расширенной популяции размером (2 -P + RC P) хромосом с худшими значениями функции соответствия по формуле (2.16). Для упорядочения кластеров от «лучшего» к «худшему» можно использовать величину расстояния dy от центра кластера v, = до «идеального объекта» с «идеальными» оценками по всем q элементам мониторинга. Например, если «идеальные» оценки представляются вектором /=i Таким образом, чем больше расстояние от «идеального объекта» до центра кластера, тем более «худшим» является кластер и попавшие в него объекты. 2.4.2 Комбинирование FCM-алгоритма на основе нечетких множеств первого типа и генетического алгоритма с хромосомой переменной длины при кодировании хромосом координатами центров кластеров Комбинированный метод нечеткой кластеризации с поочередным выполнением РСМ-алгоритма на основе НМТ1 и ГА с хромосомой переменной длины при кодировании хромосом координатами центров кластеров реализуется аналогично комбинированному методу нечеткой кластеризации с поочередным выполнением FCM-алгоритма на основе НМТ1 и ГА с хромосомой (1, 1), то: (2.22) 98 |
нечетких множеств первого типа и генетического алгоритма нри кодировании хромосом координатами центров кластеров без дополнительного пересчета значений функций принадлежности Комбинированный метод нечеткой кластеризации, предполагающий поочередное выполнение FCM-алгоритма на основе НМ Т1 и ГА при кодировании хромосом координатами центров кластеров без ДПФП может быть реализован,следующим образом [98, 99, 122]. 1. Выполняется один шаг FCM-алгоритма па'основе НМТ1 при формировании хромосом начальной популяции размером Р‘. 2. При g < G (G иg максимальное и текущее'количество поколений ГА соответственно) выполняется один шаг ГА с реализацией операций скрещивания н мутации и вычислением значений функции соответствия по формуле (4.36) для новой популяции хромосом размером (Р + Rc ■Р ). 3. Для новой популяции размером (Р + Rc ■Р), представленной хромосомами, закодированными координатами центров кластеров, выполняется один шаг FCM-алгоритма’на основе НМТ1 с вычислением новых значений ФП (нечетких степеней принадлежности) объектов центрам кластеров в соответствии с формулой (4.6), новых координат центров кластеров в соответствии с формулой (4.7) и значений функции соответствия по формуле (4.36). 4. Из расширенной популяции размером (2 ■Р + Rc ■Р), полученной путем объединения популяции размером Р предыдущего шага и популяции размером (Р + Rc ■Р) текущего шага, удаляются «нежизнеспособные» (Р + Rt ■Р) хромосом с максимальными значениями функции соответствия по формуле (4.36). Если g < G , осуществляется переход к шагу 2. Если g >G, то работа ГА завершается и осуществляется переход к шагу 5. 5. Выбирается лучшая хромосома, которая минимизирует функцию соответствия по формуле (4.36). Искомые координаты центров нечетких кла4;4.1 Комбинирование FCM-алгоритма.на основе 278 стеров определяются па основе лучшей хромосомы. В качестве результирующих нечетких степеней принадлежности объектов центрам кластеров полагаются степени принадлежности объектов центрам кластеров, соответствующие лучшей хромосоме и уже вычисленные в ходе реализации КМЖК. Так как FCM-алгоритм: является итерационным алгоритмом,, то при реализации. FA в каждом поколении, наряду, с «главной» популяцией хромосом, закодированных координатами центров кластеров, вычисляется «вспомогательная»популяция нечетких степеней принадлежности объектов центрам кластеров. Для-повышения эффективности ifА. предлагается и процессе формирования.расширенной популяции хромосом очередного поколения FA учитывать популяцию размером Р., полученную в*предыдущем, поколении, и новую популяцию размером1(Р + Rc •Р), полученную в:текущем поколении. При-этом для всех хромосом новой популяции размером. (Р-+ Rc ■Р) вьшолняется один шаг FCM-алгоритма наоснове НМТ1. При этом значения функции соответствия хромосомпопуляций размером Р , полученной в.предыдущем поколении, и новой' популяции размером (Р + Rc ■Р) текущего поколения, на первых шагах КМНК могут существенно отличаться друг от друга (например, в новой популяции размером (Р + Rc •Р} могут присутствовать, и* «нежизнеспособные» хромосомы со значением функции соответствия, равным 100). В результате формируется расширенная популяция. размером: (2 •Р + Rc ■Р), хромосомы которой упорядочиваются, по возрастанию зпаченш“ функции соответствия (индекса Се Бени) по формуле (4.36). Результирующая популяция размером Р получается путём отбрасывания из расширенной популяции размером (2 •Р -s-Rc ■Р) хромосом с худшими значениями функции соответствия по формуле (4.36). Для упорядочения кластеров от «лучшего» к «худшему» можно использовать величину расстояния от центра кластера у,. = (v',vj,...,vjf) до «идеального объекта» с «идеальными» оценками по всем q критериям. Например,если «идеальные» оценки представляются вектором (Г, ...,1), то: 279 d j = i ( l v ' ) 2 0 = 1,с). •(4.42) . • ' l-\ Таким образом, чем больше расстояние от «идеального объекта» до' центра кластера, тем более «худшим» является нечёткий кластер и. попавшие в него объекты. 4.4;2 Комбинирование FCM-алгоритма1на основе нечетких множеств первого типа и генетического алгоритма при кодировании хромосом координатами центров кластеров с дополнительным нересчетом зиачений* функций принадлежности Комбинированный метод печеткой кластеризации, предполагающий, поочередное выполнение; FCM-алгоритма-на основе НМТ1' и ГА при кодировании хромосом координатами центров кластеров с ДПФП реализуется аналогично КМНК, приведешюму. в пп. 4.4.1,. однако на шаге 3 производится дополнительный •пересчет ФП для. новой популяции хромосом? размером (Р+ R,. -Р). Несмотря на некоторое увеличение вычислительной сложности, использование ДПФП позволяет уменьшить количество: поколений ГА, необходимое для получения адекватных-результатов нечеткой кластеризации, и, кроме того, сократить временные затраты на'реапизацию КМНК.. КМНК с поочередным выполнением FCM-алгоритма-на. основе Н М Л и ГА при кодировании хромосом координатами центров кластеров с ДПФП выполняется следующим образом [98, 99, 122]. 11. Выполняется один шаг FCM-алгоритма на основе НМТ1 при формировании хромосом начальной популяции размером; Р. 2. При g < G (G и g максимальное и текущее количество поколений ГА соответственно) выполняется одинт а г ГА с реализацией операций скрещивания и мутации и вычислением значений функции соответствия по формуле (4.36) для новой популяции хромосом размером (Р + Rc ■Р). 280. |