|
лизацию одного шага генетического алгоритма с хромосомой постоянной длины при кодировании хромосом степенями принадлежности объектов центрам кластеров. Функция GeneticAlgorithmClusterCenters,т : вызывает функцию InitialPopillationС.т; вызывает функцию FitnessFunctionC.m; вызывает функцию Probability.m; вызывает функцию Parents.ni; вызывает функцию CrossoverC.m; вызывает функцию MutationC.m. Функция GeneticA IgorithmMembershipFunctions: вызывает функцию InitialPopulationMF.m; вызывает функцию FitnessFunctionMF.m; вызывает функцию Probability.m; вызывает функцию Parents.ni; вызывает функцию CrossoverMF.ni; вызывает функцию MutationMF.m. Следует отметить, что функции GeneticAlgorithmClusterCenters.nl и GeneticAlgorithmMembershipFunctions вызывают как общие для них функции Probability.m и Parents.m, так и индивидуальные функции. Функции InitialPopulationC.m реализует создание исходной популяции с хромосомой постоянной или переменной длины при кодировании хромосом координатами центров кластеров. Функция InitialPopulationMF.m реализует создание исходной популяции с хромосомой постоянной длины при кодировании хромосом степенями принадлежности объектов центрам кластеров. Функция FitnessFunctionC.m вычисляет массив значений целевой функции (показателя качества кластеризации) для популяции с хромосомой 220 |
Для оценки слож ности вычисления нечеткого общ его гиперобъема 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 |