|
Анализ результатов кластеризации при фиксированном количестве элементов мониторинга q 5 и различном количестве объектов we {10,...,20) для популяции из 30 хромосом показал, что уже при п = 15 преимущество использования кодирования хромосом координатами центров кластеров по сравнению с использованием кодирования хромосомы степенями принадлежности объектов центрам кластеров по проценту генераций лучшего значения функции соответствия становиться явным (в 1,5 раза), а при /7= 20 бесспорным (в 4,6 раза). Таким образом, кодирование хромосомы степенями принадлежности объектов центрам кластеров целесообразно использовать, если количество объектов кластеризации п невелико по сравнению с количеством элементов мониторинга q и превосходит его не более чем в 2-3 раза. Поскольку при решении подавляющего большинства различных прикладных задач количество объектов кластеризации п значительно превосходит количество элементов мониторинга q , то наибольшее применение будет находить именно кодирование хромосом координатами центров кластеров. Так как любой ГА является алгоритмом поиска субглобального, а не глобального оптимума функции соответствия, то результаты поиска при его комбинировании с FCM-алгоритмом на основе НМТ1 зависят от «качества» начальной популяции хромосом. Пусть «лучшее» значение функции соответствия при реализации комбинированного метода нечеткой кластеризации —минимальное возможное (вычисленное) значение функции соответствия, найденное по результатам ряда генераций комбинированного метода нечеткой кластеризации. Как показал анализ, процент «хороших» генераций комбинированного метода нечеткой кластеризации, на которых может быть получено «лучшее» значение функции соответствия при кодировании хромосом координатами центров кластеров, составляет от 90% до 100% для популяции размером в 3050 хромосом. Таким образом, оптимальным размером популяции является размер в 30-50 хромосом. 118 |
.мосом;координатами центров.кластеров«с ДПФП, так.как при его реализации значи тельно увеличивается.время: поискаи количество поколений ГА , необходимые для.получепияадекватных результатов кластеризации; ' Кроме того3 для;'повышения эффективности ГА при кодировании хрог мосом координатами центров кластеров без ДПФП необходимо значительное увеличение размера популяции, так как это, возможно (но не’обязательно), «обогатит» популяцию «хорошими» хромосомами.. Однако увеличение размера популяции неизбежно,увеличивает и время, поиска оптимальногореше: ння. ' V Поскольку любой ГА является алгоритмом поиска субгловального, а:не глобального; оптимума функции; соответствия,, то результаты поиска, при его комбинировании с ГСМ^алгоритмоМ :на основе НМТ1 зависят «качества» начал ьной:популяцшт хромосом. Если-под «лучшим» значением функции/соответствия,при»реализацииКМНК понимать минимальное' возможное (вычисленное).значение функции. . .соответствия, вычисленное по результатам ряда генераций КМНК, то процент «хороших» генераций, на которых было получено «лучшее» значение функции соответствия прикодировании хромосомкоординатами? центров кластеров без ДПФП. составляет от 70% до 80% для популяции размером в 30-50 хромосом. В то же время процент «хороших» генераций КМНК, на которых было получено «лучшее» значением функции соответствия при кодировании хромосом координатами центров кластеров с ДПФП, составляет, от 90% до 100% для популяции размером в 30-50 хромосом. Таким образом, оптимальным размером популяции является размер в 30-50 хромосом. Несмотря на то, что при использовании кодирования хромосом координатами центров кластеров с ДПФП, вычислительная сложность-расчета . одной хромосомы выше, чем при использовании кодирования хромосом координатами центров кластеров без ДПФП (таблица 4.2), применение кодиро283 3. Разработан комбинированный метод нечеткой кластеризации, реализующий поочередное выполнение FCM-алгоритма на основе НМТГ и генетического алгоритма, позволяющий значительно уменьшить время и количество поколений, необходимых для получения адекватных результатов нечеткой кластеризации. Предложен способ формирования расширенной популяции хромосом, реализующий сохранение генетического материала и «жизнеспособность» хромосом, обеспечивающих разбиение множества объектов на.заданное число кластеров с, при использовании комбинированного метода нечеткой кластеризации. В качестве функции соответствия генетического алгоритма предложено использовать индекс Се —Бени ХВ:, который должен быть. минимизирован,.если нет оснований для, использования других показателей качества кластеризации для оценки качества кластеризации. • • ... 4. Разработаны и: исследованы способы кодирования хромосом при реализациигенетического алгоритма. .Показано; что кодирование хромосом может осуществляться как координатами центров кластеров без дополнительного и с дополнительным пересчетом функций принадлежности, так и степенями принадлежности объектов центрам кластеров. Выявлены преимущества:использования кодирования хромосом координатами центров кластеров с дополнительным пересчетом функций принадлежности. Даны рекомендации по использованию способов кодирования хромосом и настройке таких параметров генетического алгоритма как размер популяции, количество поколений, коэффициенты скрещивания и. мутации, количество точек скрещивания и мутации: Указано, что.в ряде практических задач кодирование хромосом степенями принадлежности центрам кластеров обеспечивает уменьшение времени поиска оптимального нечеткого разбиения^ так как в этом случае при выполнении операций скрещивания и мутации изменяется степень принадлежности только одного объекта кластерам, а не центра кластера в целом. Реализован способ исключения (отбраковки) из популяции «нежизнеспособных» хромосом, для которых кластеризация выполняется на количество кластеров меньшее,, чем наперед заданное.значение с (то есть с < с ), 321 Т ак, например, анализ результатов кластеризации, при ф иксированном количестве критериев 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 |