|
способности» хромосом, то есть требования о разбиения на заданное число кластеров: с = с (рисунок 2.7). 2. При g 3. Выполняются операции скрещивания (рисунки 2.8 и 2.9) и мутации (рисунки 2.10 и 2.11) для текущей популяции с проверкой условия «жизнеспособности» хромосом, то есть требования о разбиения на заданное количество кластеров: с с*. 4. Создается новая популяция размером Р, дополненная хромосомамиотпрысками в количестве Рс •Р , затем Рс •Р хромосом с худшими значениями функции соответствия (2.16) отбрасываются. Если g < G , осуществляется переход к шагу 2. Если g > G , то работа ГА завершается и осуществляется переход к шагу 5. 5. Выбирается лучшая хромосома, которая минимизирует функцию соответствия (2.16) и для нее вычисляются новые координаты центров нечетких кластеров в соответствии (2.6). Нечеткая кластеризация на основе ГА с использованием хромосом постоянной длины, закодированных нечеткими степенями принадлежности объектов центрам кластеров, позволяет получить более адекватные результаты кластеризации с нахождением субминимума индекса Се Бени, но как и в случае использования ГА с использованием хромосом постоянной длины, закодированных координатами центров кластеров, требует большого количества смен поколений G для получения искомого нечеткого разбиения. 2.3.5 Генетический алгоритм с хромосомой переменной длины, закодированной координатами центров кластеров Если оптимальное количество кластеров заранее неизвестно, то в ГА длина хромосомы может варьироваться от cmin -q до стах •q , где стт и стах 92 |
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 I I I I I I I I V,' vi V,2 v22 < Vj v; Рисунок 4.4 fТочка мутации Хромосома до выполшгния операп ии мутации 1 1 v v; vi V,2 к V,2 •f *1 < Точка мутации Рисунок 4.5 Хромосома после выполнения операции мутации 4. Создается новая популяция размером Р , дополненная хромосомамиотпрысками в количестве Rc ■Р , затем Rc ■Р хромосом с худшими значениями функции соответствия (4.36) отбрасываются. Если g < G , осуществляется переход к шагу 2. Если g >G , то работа ГА завершается и осуществляется переход к шагу 5. 5. Выбирается лучшая хромосома, которая минимизирует функцию соответствия (4.36). Для каждого объекта кластеризации определяются нечеткие степени принадлежности к нечетким кластерам с новыми центрами кластеров в соответствии с формулой (4.6). Как показывает анализ, нечеткая кластеризация на основе ГА с использованием хромосом, закодированных координатами центров кластеров, позволяет получить более адекватные результаты кластеризации с нахождением субминимума индекса Се Бени по формуле (4.36), однако требует большого количества смен поколений G . 271 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 |