кодированной нечеткими степенями принадлежности объектов центрам кластеров, не реализуем. 2.4 Комбинирование FCM-алгоритма на основе нечетких множеств первого типа и генетического алгоритма Комбинирование FCM-алгоритма на основе HMTI и ГА с хромосомой постоянной (переменной) длины позволяет значительно уменьшить количество поколений (?, необходимое для получения адекватных результатов нечеткой кластеризации, и, следовательно, повысить эффективность применения ГА [184]. Комбинированный метод нечеткой кластеризации предполагает поочередное выполнение FCM-алгоритма на основе НМТ1 и ГА с хромосомой постоянной (переменной) длины [28, 37, 62, 64]. Данный метод нечеткой кластеризации может быть использован как при кодировании хромосом координатами центров кластеров в ГА с хромосомой постоянной (переменной) длины, так и при кодировании хромосом нечеткими степенями принадлежности объектов центрам кластеров в ГА с хромосомой постоянной длины. 2.4.1 Комбинирование FCM-алгоритма на основе нечетких множеств первого типа и генетического алгоритма с хромосомой постоянной длины при кодировании хромосом координатами центров кластеров Комбинированный метод нечеткой кластеризации с поочередным выполнением FCM-алгоритма на основе НМТ1 и ГА с хромосомой постоянной длины при кодировании хромосом координатами центров кластеров выполняется следующим образом [28, 62]. 1. Выполняется один шаг FCM-алгоритма на основе НМТ1 при формировании хромосом начальной популяции размером Р. 2. При g < G (G и g максимальное и текущее количество поколений ГА соответственно) выполняется один шаг ГА с реализацией операций 96 |
к другому. При этом будет наблюдаться плохая (медленная) сходимость к оптимальному решению (с минимальным значением индекса Се Бени по формуле (4.36)). Это объясняется тем, что при выполнении операции скрещивания и мутации новые хромосомы могут формально описывать разбиение на заданное количество кластеров с = с , а реально на меньшее количество кластеров. В результате такие хромосомы будут признаваться «нежизнеспособными» и будут отбрасываться в процессе отбора. 4.4 Комбинирование FCM-алгоритма на основе нечеткнх множеств первого типа и генетического алгоритма Комбинирование FCM-алгоритма на основе F1MT1 и ГА позволяет значительно уменьшить количество поколений G , необходимое для получения адекватных результатов нечеткой кластеризации, а, следовательно, повысить эффективность применения ГА. Но и в этом случае существенное влияние на результаты кластеризации оказывает то, что в процессе выполнения операций скрещивания и мутации могут быть сгенерированы «нежизнеспособные» хромосомы. Предлагаемый комбинированный метод нечеткой кластеризации (КМНК) предполагает поочередное выполнение FCM-алгоритма на основе НМТ1 и ГА [98, 99, 118, 122]. Комбинированный метод нечеткой кластеризации может быть использован как при кодировании хромосом координатами центров кластеров, так и при кодировании хромосом нечеткими степенями принадлежности объектов центрам кластеров. При этом предлагается новый подход к формированию расширенной популяции. В случае кодирования хромосомы координатами центров кластеров возможны два варианта реализации ГА: без дополнительного пересчета функций принадлежности (ДПФП) и с ДПФП. 277 нечетких множеств первого типа и генетического алгоритма нри кодировании хромосом координатами центров кластеров без дополнительного пересчета значений функций принадлежности Комбинированный метод нечеткой кластеризации, предполагающий поочередное выполнение 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 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. |