3. В качестве родителя выбирается хромосома sn если случайное число z попал в / -й интервал: [рм >Р/]>гДе Ро = ®• 4. Шаги 2-3 повторяются для определения второй хромосомы родителя. Две выбранные таким образом хромосомы будут использоваться в качестве родителей при выполнении операции скрещивания. Пусть при реализации ГА используется одноточечное скрещивание и одноточечная мутация. При выполнении операции скрещивания выбирается вероятность скрещивания Rc и генерируется случайное число N c. Если RC> N C, то случайным образом выбирается точка скрещивания z ( : g {1 •q}) и выполняется скрещивание. При выполнении операции мутации выбирается вероятность мутации Rn, и генерируется случайное число N т . Если Rm> N m, то случайным образом выбирается точка мутации z (z е {1 •q}) и выполняется мутация. Тогда генетический алгоритм имеет следующий вид (рисунок 2.6) [28]. 1. Случайным образом создается популяция размером Р в соответствии с формулой (2.1) для ФП объектов кластерам и формулой (2.6) для центров кластеров с проверкой условия «жизнеспособности» хромосом, то есть требования о разбиения на заданное количество кластеров: с с (рисунок 2. 1). 2. При g 3. Выполняются операции скрещивания (рисунки 2.2 и 2.3) и мутации (рисунки 2.4 и 2.5) для текущей популяции с проверкой условия «жизнеспособности» хромосом, то есть требования о разбиения на заданное количество кластеров: с =с *. 4. Создается новая популяция размером Р , дополненная хромосомамиотпрысками в количестве Rc -P, затем Рс -Р хромосом с худшими значе87 |
1. На горизонтальной оси откладывается ряд чисел р, (/ \ , Р ) . 2. Генерируется случайное число z = random([0,11). 3. В качестве родителя выбирается хромосома s,, если случайное число z попал в l -й интервал: [р,_,,/?/], где р 0 = 0 . 4. Шаги 2-3 повторяются для определения второй хромосомы родителя. Далее две выбранные хромосомы-родители будут использоваться при выполнении операции скрещивания. В дальнейшем предполагается, что используется одноточечное скрещивание и одноточечная мутация. При выполнении операции скрещивания выбирается вероятность скрещивания Rc и генерируется случайное число Nc. Если Rc > N c, то случайным образом выбирается точка скрещивания г ( г е {1 ■q}) и выполняется скрещивание. При выполнении операции мутации выбирается вероятность мутации Rm и генерируется случайное число Nm. Если Rm> N m, то случайным образом выбирается точка мутации : ( : е с •q \) и выполняется мутация. Тогда генетический алгоритм имеет вид [98]. 1. Случайным образом создается популяция размером Р в соответствии с формулой (4.1) для ФП объектов кластерам и формулой (4.7) для центров кластеров с проверкой условия «жизнеспособности» хромосом, то есть требования о разбиения на заданное количество кластеров: с = с (рисунок 4.1). 2. При g < G ( С и g максимальное и текущее количество похсолений ГА соответственно) вычисляется значение функции соответствия (4.36) для каждой хромосомы и создается Rc ■Р/2 пар хромосом-родителей. 3. Выполняются операции скрещивания (рисунки 4.2 и 4.3) и мутации (рисунки 4.4 и 4.5) для текущей популяции с проверкой условия «жизнеспособности» хромосом, то есть требования о разбиения на заданное количество кластеров: с с . 269 s(u') = ,v(w)+ a (4.40) Соответствующим образом изменяются и нечеткие степенипринадлежности данного объекта z другим кластерам с номерами, не равными w : 1. Случайнымобразом=создается популяция размером Р в соответствии с формулой (4.1) для нечетких степеней принадлежности объектов кластерам и формулой (4.7) для центров кластеров с проверкой условия «жизнеспособности» хромосом, то есть требования о разбиения на заданное число кластеров: с —с* (рисунок 4.6): . 2. При g < G (G и. g максимальное и текущее количество поколений ГА соответственно) вычисляется значение функции соответствия (4.36) для каждой хромосомы и создается.i?c •Р /2 Пар хромосом-родителей. 3. Выполняются,операции;скрещивания (рисунки 4.7 и 4.8):и мутации (рисунки 4.9 и 4.10) для текущей популяции с проверкой условия «жизнеспособности» хромосом, то есть требования о разбиения на заданное количество кластеров: с = с 4; Создается новая популяция размером Р , дополненная хромосомамиотпрысками в количестве Рс ■Р , затем Рс •Р хромосом с худшими значениями функции соответствия (4.36) отбрасываются. Если g < G , осуществляется переход к шагу 2.-Если g > G , то работа ГА завершается и осуществляется переход к шагу 5. . 5. Выбирается лучшая хромосома, которая минимизирует функцию соответствия (4.36) и для нее вычисляются новые координаты центров нечетких кластеров в соответствии (4.7). Нечеткая кластеризация на основе ГА с использованием хромосом, кодированных нечеткими степенями принадлежности объектов центрам кла(4.41) 275 чайным образом выбирается точка скрещивания z и выполняется скрещивание.' При выполнении операции мутации выбирается вероятность мутации Rm и генерируется случайное число N т. Если Rm> N m, то случайным образом выбирается точка мутации г и выполняется мутация. Тогда генетический алгоритм имеет вид [76, 120, 125]. Г. Случайным образом создается популяция размером Р. При этом выполняется проверка условия: /?;, <т 2. 2. При g < G (G и g максимальное и текущее количество поколений ГА соответственно) реализуется FCM-алгоритм на основе ИНМТ2 с вычислением значения функции соответствия по формуле (5.40) для каждой, хромосомы и создается /?с -Р /2 пар хромосом-родителей. 3. Выполняются операций скрещивания и мутации-для текущей популяции. При этомвыполняется проверка условия:' щ <т2.. Для хромосомотпрысков реализуется PGM-алгоритм на основе ИНМТ2 и вычисляются значения.функции соответствия по формуле (5.40). 4. Создается новая популяция размером. (Р + /?с -Р)-, дополненная хромосомами-отпрысками в количестве Rc ■Р , затем Rc Р хромосом, с худшими значениями функции соответствия (5.40) отбрасываются. Если. g < G , осуществляется переход к шагу 2’. ' 5. Выбирается лучшая хромосома, которая минимизирует функцию соответствия (5.40). Для каждого объекта определяется его-принадлежность к кластерам. Одновременно с популяцией хромосом вида (5.46) существуют'«популяции» значений функции соответствия, координат центров, кластеров.и степеней принадлежности объектов центрам кластеров. Предлагаемый метод кластеризации позволяет учесть свойство кластерной относительности объектов и получить адекватные результаты кластеризации для множества объектов, содержащего-кластеры существенно разной плотности или существенно разного объема. 359 |