|
В первом случае следует использовать ГА с хромосомой постоянной длины, а во втором ГА с хромосомой переменной длины. Для некоторого количества кластеров с хромосома может быть закодирована координатами центров всех кластеров или нечеткими степенями принадлежности объектов центрам кластеров числами из интервала [0,1]. 2.3.1 Кодирование хромосомы координатами центров кластеров При кодировании хромосомы координатами центрами кластеров длина хромосомы равна с •q , где с количество кластеров, q количество элементов мониторинга. При этом первые q элементов хромосомы соответствуют координатам центра первого кластера, вторые q элементов —координатам центра второго кластера и т.п. [28]. Диапазон изменения значения каждого гена (координаты центра кластера) определяется интервалом [Dmm9 Dmax], где Dmm и Dmax минимальный и максимальный баллы выбранной порядковой шкалы, гак как оценивание объектов по каждому элементу мониторинга производится с использованием некоторой порядковой шкалы путём выставления баллов. 2.3.2 Кодирование хромосомы нечеткими степенями принадлежности объектов центрам кластеров При кодировании хромосомы нечеткими степенями принадлежности объектов центрам нечетких кластеров длина хромосомы будет равна с •п , где с количество кластеров, п количество объектов. При этом первые с элементов хромосомы соответствуют степеням принадлежности первого объекта центрам кластеров, вторые с элементов хромосомы —степеням принадлежности второго объекта центрам кластеров и т.п. Диапазон изменения значения каждого гена определяется интервалом [0, 1], границы которого соответствуют минимальной и максимальной нечетким степеням принадлежности объекта кластеру [28]. Кодирование хромосомы нечеткими степенями 84 |
вала [0 ,1] (что позволит в ряде случаев избежать потери информации во время операции скрещивания, так как хромосомы-родители будут обмениваться только нечеткими степенями-принадлежностей объектов центрам кластеров, а не координатами центров кластеров). 4.3.1 Кодирование хромосомы координатами центрами кластеров При кодировании хромосомы координатами центрами кластеров длина хромосомы будет равна с •q , где с количество кластеров, q<количество критериев. При этом первые q элементов хромосомы будут соответствовать координатам центра первого кластера, вторые q элементов координатам центра второго кластера и т.п. [98]. Так как оценивание объектов по каждому критерию производится с использованием некоторой порядковой шкалы путём выставления баллов, тодиапазон изменения значения каждого гена (координаты центра кластера) определяется интервалом [Dmm, Dnm\, где Dmm и Dmax минимальный и максимальный баллы выбранной порядковой шкалы. 4.3.2 Кодирование хромосомы нечеткими степенями принадлежности объектов центрам кластеров При кодировании хромосомы нечеткими степенями принадлежности объектов центрам нечетких кластеров длина хромосомы будет равна с ■п , где с количество кластеров, п —количество объектов. При этом первые с элементов хромосомы будут соответствовать нечетким степеням принадлежности первого объекта центрам кластеров, вторые с элементов хромосомы — нечетким степеням принадлежности второго объекта центрам кластеров и т.п. В случае кодирования хромосомы нечеткими степенями принадлежности объектов нечетким кластерам диапазон изменения значения каждого гена определяется интервалом [0 , 1j , границы которого соответствуют минимальной и максимальной нечетким степеням принадлежности объекта кластеру [98]. 267 4.3.4 Генетический алгоритм для хромосомы, закодированной нечеткнми степенями принадлежности объектов центрам кластеров Как уже отмечалось выше, при кодировании хромосомы нечеткими степенями принадлежности объектов центрам кластеров первые с координат соответствуют нечетким степеням принадлежности первого объекта нечетким кластерам, вторые с координат —нечетким степеням принадлежности второго объекта кластерам и т.н. Следовательно, сумма первых с координат хромосомы, сумма вторых с координат хромосомы и т.п. равна единице. Пример хромосомы для случая разбиения множества объектов на 4 кластера приведен на рисунке 4.6. Генетический алгоритм реализуется так же, как и ГА, приведенный в пп. 4.3.3. Однако имеются некоторые отличия при выполнении операций скрещивания и мутации. Отметим, что начальная популяция генерируется таким образом, чтобы она состояла только из «жизнеспособных» хромосом, иначе эффективность применения ГА будет значительно снижена. Выбор родителей осуществляется с использованием вероятностного отбора на основе формулы (4.38). При выполнении скрещивания выбирается вероятность скрещивания Rc и генерируется случайное число Nc. Если Rc > N с, то случайным образом выбирается точка скрещивания z (z mod с = 0 ) и выполняется скрещиватше (рисунки 4.7 п 4.8). Точка скрещивания z также определяет номер объекта кластеризации, начиная с нечетких степеней принадлежности которого происходит обмен частями хромосом-родителей. Выполнение условия z mod с 0 обеспечивает обмен всеми нечеткими степенями принадлежности некоторого объекта, а, следовательно, выполнеС пие условия: ^ и}(х,) = 1 (Ух, е X ), где с количество нечетких кластеров j=i X (j е {2,...,с}), iij(xt) ФП объекта х, кластеру X . 272 степенями принадлежностиобъектов1центрам •кластеров-диапазон: изменения значения каждого гена определяется интервалом [0, 1], границы которого . соответствуют минимальной и максимальной степеням принадлежности объ' екта кластеру.. '• Однако, кодирование хромосомы степенями принадлежности, объектов центрам: кластеров^для PGM-алгоритма на основе НМТ-1 и; PFCM-алгоритма на основе-HMTl приводит к тому, что выполнение операции скрещивания не приносит/ожидаемого эффекта, а выполнение операции мутации; существенн о усложняется: Например, при использовании РСМ-алгоритма на основе НМТ1 возможностные степени принадлежности: связаны, между собой ограничением (4.45),.поэтому в качестве точек, скрещивания могут выбираться-только с точек, что явно;-недостаточно: Выполнение операции мутации одногогена требует, пересчета значений еще п Г гена, связанных ограничением (4‘.45) с. мутирующим геном. . При комбинировании* РРСМталгоритма на основе НМТ1 и;ГА при кодировании хромосомы должны, однозначно-использоваться’координаты^ центров кластеров. Это объясняется тем, что для PFCM-алгоритма на основе НМТ1 при кодировании хромосомы нечеткими и возможностными степенями принадлежности объектов кластеризации центрам кластеров длина хромосомы будет в два раза длиннее, чем для:любых других алгоритмов кластеризации при кодировании’ хромосомы нечеткими степенями принадлежности (или. возможностными степенями типичности) объектов кластеризации центрам кластеров, так как каждому объекту xi (/ —1,/г) ставятся в соответствие ФП и , (х;) и ФТ (7 = 1,с). Таким образом, длина хромосомы будет равна 2 •с ■п, где с число кластеров, п количество объектов. При этом первые с элементов хромосомы будут соответствовать нечетким степеням принадлежности первого объекта центрам кластеров, вто• ’' 304 |