постоянной или переменной длины при кодировании хромосом координатами центров кластеров. Функция FitnessFunctionMF.m вычисляет массив значений целевой функции (показателя качества кластеризации) для популяции с хромосомой постоянной длины при кодировании хромосом степенями принадлежности объектов центрам кластеров. Функция Pmbability.ni вычисляет массив значений вероятностей для определения хромосом-родителей для новой популяции при любом способе кодирования хромосом. Функция Parents.ni определяет хромосомы-родители для выполнения операции скрещивания при любом способе кодирования хромосом. Функция CrossoverC.ni выполняет скрещивание хромосом-родителей для нахождения новой популяции с хромосомой постоянной или переменной длины при кодировании хромосом координатами центров кластеров. Функция CrossoverC.ni выполняет скрещивание хромосом-родителей для нахождения новой популяции с хромосомой постоянной или переменной длины при кодировании хромосом координатами центров кластеров. Функция MutationC.m выполняет мутацию хромосом-родителей для нахождения новой популяции с хромосомой постоянной длины при кодировании хромосом степенями принадлежности объектов центрам кластеров. Функция M utationC.m выполняет мутацию хромосом-родителей для нахождения новой популяции с хромосомой постоянной длины при кодировании хромосом степенями принадлежности объектов центрам кластеров. При работе с подкомплексом «FCM T1» на экран первоначально выводится диалоговое окно, приведенное на рисунке 4.4. В случае выбора одного из КМНК на экран выводятся диалоговые окна, позволяющие задать параметры ГА (рисунки 4.5 и 4.6). Как уже отмечалось ранее, результаты кластеризации выводятся в командное окно и текстовый файл ClusterDivision.txt. 221 |
Таблица 11.4.7 —Параметры моделирования Параметр ■Алгоритм у . FCM .'па основе НМТ1 j комбинирование ■FCM-алгоритма на основе НМТ1 и ГА (степени при. надлежности) комбинированно FCM-алгоритмана основе НМТ1 и ГА. ; центры кластеров без ДПФП i •. центры кластеров с ДПФП Общее количество поколений \ ' Р ■■ ■' 160 160 160 ; Номер «лучшей» итерации (поколения) 28 136 . 147 141 Размер популяции 30 30 30 Значение индекса Се—Бени •0,022516853056 0,015100303632 ■0,015100303632 0,015100303632 Время расчета «лучшей» итерации (поколения) (с.) 0,005 : ' 2,197 I ■■ 2,531. ’ 2,504 ; Номер поколения, при котором имеет место сходимость популяции •У 9 • 19 13 Время расчета сходимости популяции (с.) 0,541 ... . 1 0,616 i .; 0,573 А нализ графических зависим остей и данны х, приведенны х в таблице П .4.7, показал для данного прим ера преим ущ ество кодирования хром осом степенями принадлеж ности объектов центрам кластеров со сравнению с кодированием хромосом координатам и центров кластеров без Д П Ф П и с ДГ1ФП, а такж е преимущ ество кодирования хромосом координатам и центров кластеров с Д П Ф П по сравнению с кодированием хром осом координатам и центров кластеров без ДП Ф П . . И з рисунков П .4.13, П .4.15 и П .4.17 видно, что наблю дается быстрая сходим ость значений «среднего» и «минимального» здоровья популяции к «максимальному» здоровью (чём м еньш е значение индекса С е Бени, тем здоровье «максимальнее») при лю бом способе кодирования хром осом , однако при кодировании степенями принадлеж ности объектов центрам кластеров скорость сходимости оказалась максимальной. П ри этом при кодировании хромосом координатамицентров кластеров без Д П Ф П и с ДП Ф П номера поколений, на которых значение «максимально348 Для оценки слож ности вычисления нечеткого общ его гиперобъема F H по формуле (4.29) запиш ем нечеткую ковариационную матрицу j -го кластера при т = 2 : Z ( » , t O )2 ( * , v j R -------------------------------. I» , ) 2 .■-I Для вычисления всех ковариационных м атриц Ry следу ет выполнить: (((су -я + ( q 1+ q )п ) + ((« 1) + 2л )+ (и 1 + /г)) + !)• с арифметических операций. Вычиелетгие определителя матрицы разм ера с х с в системе M A TLA B 7.0 реализуется через L U -разлож ение, где L нормированная нижняя треугольная с х с -матрица, a U верхняя треугольная с х с -матрица [155]. Следовательно, вычисление определителя матрицы размера с х с требует выполнения Тх = о (с,,0"-’ 7)=<9(с2’31) операций [16]. П усть, кроме того, слож ность вычисления квадратного корня оценивается сверху константой Т2. Тогда сложность вычисления нечеткого общ его гиперобьем а F H можно оценить как: (((? 'ft G /—^ “? ) ' ^ 0 (О* —l) + 2• и) + ((w —l ) + / ? ) ) + l + 7j + Т2)с + + (с 0 = (3 •q п + 4 •п -I'J] + Т2) с 1 = (П.4.5) = 3 •q ■и ■с + 4 -п с + с -Ту + с -Т, 1 . Сравнивая формулы (П.4.4) и (П.4.5), мож но сделать вывод о больш ей вычислительной сложности расчета нечеткого общ его гиперобъема F H по сравнению со сложностью расчета индекса Се Бени Х В . П.4.6.5 Оценка сложности реализации генетического алгоритма Выполним оценку затрат памяти VBH через количество используемых О переменных [158] при реализации КМ НК при кодировании хромосом координатами центров кластеров с дополнительным пересчетом функций принадлежности и при кодировании хромосом степенями принадлеж ности объектов центрам кластеров. 383 функций принадлежности и при кодировании хромосомстепенями принадлежности объектов центрам кластеров соответственно. В таблице П.4.15 приведены оценки основных затрат памяти при реализации КМ Н К при кодировании хромосом координатами центров кластеров с дополнительным пересчетом функций принадлеж ности и при кодировании хромосом степенями принадлежности объектов центрам кластеров («жирным» шрифтом выделены переменные, для которы х затраты памяти различны). Общая «составляющ ая» затрат памяти V мож ет бы ть оценена как: V = // + «• q 42 •с ■q.+ 2 c n + 5 P + 3 R c P + 3 c n P + c n R c P , где п количество объектов кластеризации; q количество критериев; с количествокпастеров; Р размер популяции; R c коэф ф ициент скрещ ивания. П усть L n q . Т огда затраты памяти при кодировании степенями принадлеж ности объектов центрам, кластеров‘Превышают затраты памяти прикодировании координатами центров кластеров на следую щ ую величину: A V = V2 V t L -(2+ 3 •R c P + 3 P ) = ( n q ) ( 2 + 3 R ^ P + 3 P ) . Таким образом, чем больш е величина L = n q , тем больш е затраты памяти при кодировании степенями принадлеж ности объектов центрам кластеров; Следует отметить, что реализация классического FC M -алгоритма на основе НМТ1 требует значительно меньш их затрат памяти VFCM: основные затраты памяти связаны с созданием массива оценок объектов (n-q), массива центров кластеров (с ■q ), массива степеней принадлеж ности объектов центрам кластеров (с •п ) и массива разбиений на кластеры (и ), что соответствует первой и трем последним строкам таблицы П .4.15. Vгем ~ n q + c t i + cq + n. О днако, как уж е было отмечено в ГЛ А В Е 4, для получения адекватных результатов кластеризации требуется многократное выполнение классического FCM -алгоритма на основе НМ Т1. 385 |