|
две хромосомы равной длины при с = 3 = с2 = 3 ); две хромосомы разной длины при с1=3 и с2 = 2. В случае, когда хромосомы-родители имеют равную длину, операция скрещивания выполняется так же, как в ГА с хромосомой постоянной длины (п. 2.3.3, рисунки 2.2 и 2.3). На рисунках 2.13 и 2.14 приведены примеры хромосом разной длины (с{=3 и с2 = 2 ) до и после выполнения операции скрещивания. Операция мутации в ГА с хромосомой переменной длины аналогична операции мутации в ГА с хромосомой постоянной длины (п. 2.3.3, рисунки 2.4 и 2.5). В целом реализация ГА с хромосомой переменной длины аналогична реализации ГА с хромосомой постоянной длины (п. 2.3.3), за исключением особенностей выполнения операции скрещивания [66, 67]. 2.3.6 Анализ проблемы реализации генетического алгоритма с хромосомой переменной длины, закодированной нечеткими степенями принадлежности объектов центрам кластеров Ввиду особенностей способа кодирования хромосомы нечеткими степенями принадлежностей объектов центрам кластеров (п. 2.3.4, рисунок 2.7) и особенностей реализации операции скрещивания для хромосом, закодированной нечеткими степенями принадлежности объектов центрам кластеров (рисунки 2.8 и 2.9) реализация ГА с хромосомой переменной длины, закодированной нечеткими степенями принадлежности объектов центрам кластеров, не представляется возможным. Это объясняется следующим. Хромосома, закодированная нечеткими степенями принадлежности объектов цешрам кластеров, состоит из п «блоков» (по количеству объектов п) длиной с (по количеству кластеров с). Тогда выполнение операции скрещивания может привести к абсурдной ситуации, когда часть объектов кластеризации разбивается на одно число кластеров (например, сх), а другая часть объектов кластеризации —на другое число кластеров (например, с2, с2 Фсх), и всё это в одной хромосоме. Следовательно, ГА с хромосомой переменной длины, за95 |
вала [0 ,1] (что позволит в ряде случаев избежать потери информации во время операции скрещивания, так как хромосомы-родители будут обмениваться только нечеткими степенями-принадлежностей объектов центрам кластеров, а не координатами центров кластеров). 4.3.1 Кодирование хромосомы координатами центрами кластеров При кодировании хромосомы координатами центрами кластеров длина хромосомы будет равна с •q , где с количество кластеров, q<количество критериев. При этом первые q элементов хромосомы будут соответствовать координатам центра первого кластера, вторые q элементов координатам центра второго кластера и т.п. [98]. Так как оценивание объектов по каждому критерию производится с использованием некоторой порядковой шкалы путём выставления баллов, тодиапазон изменения значения каждого гена (координаты центра кластера) определяется интервалом [Dmm, Dnm\, где Dmm и Dmax минимальный и максимальный баллы выбранной порядковой шкалы. 4.3.2 Кодирование хромосомы нечеткими степенями принадлежности объектов центрам кластеров При кодировании хромосомы нечеткими степенями принадлежности объектов центрам нечетких кластеров длина хромосомы будет равна с ■п , где с количество кластеров, п —количество объектов. При этом первые с элементов хромосомы будут соответствовать нечетким степеням принадлежности первого объекта центрам кластеров, вторые с элементов хромосомы — нечетким степеням принадлежности второго объекта центрам кластеров и т.п. В случае кодирования хромосомы нечеткими степенями принадлежности объектов нечетким кластерам диапазон изменения значения каждого гена определяется интервалом [0 , 1j , границы которого соответствуют минимальной и максимальной нечетким степеням принадлежности объекта кластеру [98]. 267 вания хромосом координатами центров кластеров с Д11ФГ1 приносит существенный выигрыш по проценту генераций лучшего значения функции соответствия'при некотором увеличении времени реализации ГА. Более подробный анализ оценки эффективности способов кодирования хромосом приведен в ПРИЛОЖЕНИИ 4 (п. П.4.6). В ряде случаев когда количество объектов п невелико по сравнению с количеством критериев q —использование кодирования хромосом нечеткими степенями принадлежности объектов центрам кластеров позволяет сократить затраты времени на получение искомого результата нечеткой кластеризации по сравнению с использованием кодирования хромосом координатами центров кластеров с ДПФП. Это объясняется тем, что при выполнении операции скрещивания хромосомы-родители обмениваются только нечеткими степеням и-принадлежностей объектов центрам кластеров, а не координатами центров кластеров, что позволяет избежать потери возможно полезной информации о расположении центров кластеров. Если количество объектов п невелико по сравнению с количеством критериев q (количеством координат центра кластера), то попытка перевести некоторый г'-й объект (г = 1,и ) из j -го кластера в г'-й за счет изменения его нечетких степеней принадлежности центрам кластеров может оказаться более эффективной, чем попытка изменения координат всего кластера. Кроме того, вычислительная сложность расчета одной хромосомы при использовании кодирования хромосом нечеткими степенями принадлежности объектов центрам кластеров ниже, чем при использовании кодирования хромосом координатами центров кластеров с ДПФП, чго может дать некоторый выигрыш по времени. Кодирование хромосомы координатами центров кластеров без ДПФП Кодирование хромосомы координатами центров кластеров о ДПФП Кодирование хромосомы степенями при!шдлсжности объектов центрам кластеров 11 -c-q-n + +( 3 c n q 2 n ) c 11 -c-q-/i + + ( 6 c n q 2 n ) c 8 -с ■q ■п + + (3 •с ■п q —и) •с 284 |