|
принадлежности объектов центрам кластеров при использовании одноточечного скрещивания показали явное преимущество кодирования хромосомы степенями принадлежности объектов центрам кластеров для 1000 генераций лучшей хромосомы. Под «лучшим» поколением понималась поколение, в котором достигается минимальное значение функции соответствия, составившее для данного примера 0,015100303632 («лучшее» минимальное значение функции соответствия было определенно экспериментальным путем на основе 1000 генераций комбинированного метода нечеткой кластеризации). Следует отметить, что при выполнении операции мутации при кодировании хромосомы координатами центров кластеров выполнялась мутация двух генов из 20, то есть производилась мутация 10% генов, а при выполнении операции мутации при кодировании хромосомы степенями принадлежности объектов центрам кластеров выполнялась одновременная мутация четырех генов из 40 для соответствующих одному объекту степеней принадлежности (что объясняется спецификой формирования хромосомы). В этом случае также производилась мутация 10% генов. Как видно из таблиц 2.4 и 2.5, оптимальным размером популяции является размер в 30, 40 или 50 хромосом, обеспечивающий достижение оптимального нечеткого разбиения за минимальное время с достаточно высокой надежностью (около 100%). Дальнейшее увеличение размера популяции следует признать нерациональным ввиду значительного увеличения временных затрат. Кроме того, в таблице 2.5 приведены оценки эффективности применения классического FCM-алгоритма иа основе НМТ1 при выполнении 1000 генераций: математическое ожидание количества итераций для FCMалгоритма на основе НМТ1 составило 66,976 итераций, а время —0,008389 с., однако математическое ожидание значения показателя качества кластеризации (индекса Се Бени) составило 0,015523058294, что больше значения функции соответствия лучшей хромосомы 0,015100303632. Следует отметить, что при реализации классического FCM-алгоритма на основе НМТ1 для 116 |
П.4.1.2 Сравнительный анализ эффективности способов кодирования хромосом для FCM-алгоритма на основе нечетких множеств первого типа Анализ результатов оценки математического ожидания и дисперсии номера поколения лучшей хромосомы и времени расчета лучшей хромосомы при кодировании хромосомы координатами центров кластеров без ДПФП и с ДПФП и степенями принадлежности объектов центрам кластеров при использовании одноточечного скрещивания показал явное преимущество кодирования хромосомы степенями принадлежности объектов центрам кластеров для 1000 генераций лучшей хромосомы (таблицы П.4.4 и П.4.6). Под «лучшим» поколением понималась поколение, в котором достигается минимальное значение функции соответствия, составившее для данного примера 0,015100303632 («лучшее» минимальное значение функции соответствия было определенно экспериментальным путем на основе 1000 генераций КМНК). При выполнении операции мутации при кодировании хромосомы координатами центров кластеров выполнялась мутация двух генов из 20, то есть производилась мутация 1.0% генов. При выполнении операции мутации при кодировании хромосомы степенями принадлежности объектов центрам кластеров выполнялась одновременная мутация четырех генов из 40 для соответствующих одному объекту степеней принадлежности (что объясняется спецификой формирования хромосомы). В этом случае также производилась мутация 10% генов. Как видно из таблицы П.4.4 и рисунков П.4.1-П.4.4 при кодировании хромосомы координатами центров кластеров без ДПФП и с ДПФП при увеличении размера популяции наблюдается сближение значений математического ожидания номера поколения лучшей хромосомы и времени расчета лучшей хромосомы, однако дисперсия номера поколения лучшей хромосомы и времени расчета лучшей хромосомы при кодировании хромосомы координатами центров кластеров без ДПФП значительно превосходят одноименные 332 Таблица П.4.6 Оценка преимущества способов кодирования по достижению заданного минимума функции соответствия По процентному соотношению количества генераций лучшей хромосомы к общему количеству генераций По номеру поколения лучшей хромосомы По времени расчета лучшей хромосомы По значению функции соответствия Размер попу ЛЯЦИИ 3 к2 3 к 1 2 к 1 3 к2 3 к 1 2 к 1 3 к 2 3 к 1 2 к 1 3 к 2 3 к 1 2 к 1 10 1,3 1,68 1,28 1,065 1,246 1,170 1,471 1,612 1,096 1,121 1,159 1,034 20 1,1 1,47 1,24 1,059 1,142 1,079 1,460 1,482 1,015 1,086 1,138 1,048 30 1,1 1,39 1,27 1,064 1,106 1,039 1,459 1,464 1,003 1,049 1,117 1,065 40 1,07 1,35 1,26 1,062 1,096 1,032 1,416 1,396 0,986 1,025 1,119 1,092 50 1,02 1,27 1,25 1,058 1,080 1,021 1,428 1,399 0,980 1,008 1,089 1,081 Как видно из рисунков П.4.9-П.4.11 оптимальным размером популяции является размер в 30, 40 или 50 хромосом, обеспечивающий достижение оптимального нечеткого разбиения за минимальное время с достаточно высокой надежностью (около 100%). Дальнейшее увеличение размера популяции следует признать нерациональным ввиду значительного увеличения временных затрат. В таблице П.4.5 также приведены оценки эффективности применения классического FCM-алгоритма на основе НМТ1 при выполнении 1000 генераций. Хотя математическое ожидание количества итераций для FCMалгоритма на основе НМТ1 составило 66,976 итераций, а время 0,008389 с., однако математическое ожидание значения целевой функции составило 0,015523058294, что больше значения функции соответствия лучшей хромосомы 0,015100303632. При этом следует отметить, что при реализации классического FCM-алгоритма на основе НМТ1 для получения 1000 значений функции соответствия, равных 0,015100303632, пришлось выполнить 1 876 322 генераций FCM-алгоритма, то есть процент «хороших» генераций составил всего 0,053%. 338 Т ак, например, анализ результатов кластеризации, при ф иксированном количестве критериев q = 5 и различном количестве объ ектов п <={10,...,20} для популяции из 30 хром осом показал, что уж е при и = 15 преим ущ ество использования кодирования хром осом координатам и ц ентров кластеров с Д П Ф П по сравнению с использованием , коди рован и я хром осом ы степеням и принадлеж ности объектов центрам кластеров по проценту генерац и й-лучш его значения ф ункции соответстви я' становиться явны м (в 1,5 раза), а при п = 20 бесспорны м (в 4,6 раза). Таким образом , кодирование хром осом ы степ еням и п ринадлеж ности объектов центрам кластеров ц елесообразн о использовать, если количество объектов кластеризации п н евели ко по-сравнению с количеством критериев q и превосходит его не более чем в 2-3 раза. Т ак как при реш ении подавляю щ его больш и н ства разли чн ы х п рикладны х задач количество объектов кластеризации п зн ачи тельно п ревосходит количество критериев q , то н аибольш ее прим енение будет н аходить именно кодирование хромосом координатам и центров кластеров. Н а рисунках П .4 .12, П .4.14 и П .4.16 приведены прим еры граф ических зависимостей для значений показателя качества кластеризации (индекса С е Б ени) в зависимости от количества итераций классического РС М -алгоритм а на основе НМТ1 и,количества поколений при использовании К М Н К в случае кодирования хромосом с использованием координат центров кластеров без Д П Ф П и с ДП Ф П , а такж е с использованием степеней.принадлеж ности объектов центрам кластеров соответственно. П араметры м оделирования приведены в таблице Г1.4.7. Н а рисунках П .4.13, П .4.15 и П .4.17 показаны прим еры графических зависимостей оценки здоровья популяции н а основе значений показателя качества кластеризации (индекса С е Бени) для параметров м оделирования из таблицы П .4.7 в случае кодирования хромосом с использованием координат центров кластеров без Д П Ф П и с Д П Ф П , а такж е с использованием степеней принадлежности объектов центрам кластеров соответственно. 344 |