3.2.2. Описание алгоритмов

Во всех исследованиях, как правило, приводятся не только функционалы качества разбиения, но и алгоритмы поиска экстремума рассматриваемого функционала.

3.2.2.1. Алгоритм Распини

[150] минимизирует критерий в виде (3.27), так что находится решение

Как отмечали И. И. Елисеева и В. О. Рукавишников касательно функционала Э. Г. Распини, «поиск экстремального значения критерия качества целесообразно проводить с использованием градиентных методов, обеспечивающих быструю сходимость алгоритмов» Дальнейшее изложение алгоритма, минимизирующего функционал , основано на описании процедуры, представленном в работе [22].

Пусть где вычисляется по формуле (3.25), а функция вычисляется в соответствии с соотношением Кроме того,

для удобства преобразований можно ввести также следующие обо значения:

выражающее значение на шаге вычислительного процесса

где символом обозначается на шаге вычислительного процесса а также

так что на шаге вычислительного процесса задача будет заключаться в нахождении

Следует отметить, что представляет собой дифференцируемую функцию, частные производные которой находятся по следующим формулам:

и, поскольку — полином четвертой степени, то его частная производная в точке на шаге вычислительного процесса будет определяться следующим соотношением:

где, в свою очередь, — значение принадлежности объекта кластеру на b шаге вычислительного процесса.

Параметры алгоритма:

с — число нечетких кластеров в искомом разбиении Р;

— порог расстояния между объектами;

Схема алгоритма:

1. Выбираются начальное разбиение на с нечетких классов, описываемое с непустыми функциями принадлежности, так что матрица начального разбиения имеет с строк и столбцов; присваиваются значения

2. Вычисляется в соответствии с соотношением (3.86) и соответствии с соотношением (3.87); вычисляется значение и сравнивается со значением : вычисляется некоторое пороговое значение если ) , так что алгоритм прекращает работу;

3. Полагается для объекта вычисляются значения частных производных по формулам (3.92), (3.90), (3.91) соответственно;

4. Если выполняется приближенное равенство то осуществляется переход на шаг 7; в противном случае осуществляется переход на шаг 5;

5. Для определения направления движения отыскивается наименьший положительный корень полинома где

где, в свою очередь,

причем относительные размеры нечетких кластеров, номера которых устанавливаются по формулам (3.93) и (3.94), определяются по формуле

Поскольку то в силу правила Декарта полином имеет один или три положительных корня; отыскивается наименьший положительный корень полинома и сопоставляется с так что

6. Производится коррекция вектора степеней принадлежности объекта в соответствии со следующим правилом:

где символами обозначены измененные значения наибольшей и наименьшей степеней принадлежности объекта; с учетом коррекции степеней принадлежности (3.95) и (3.96) производится также коррекция соответствующих полагается

7. Если просмотрены не все то полагается и осуществляется переход на шаг 3, в противном случае производится проверка изменения матрицы разбиения если имели место изменения то полагается и осуществляется переход на шаг 2, в противном случае полагается и алгоритм прекращает работу.

В работах [151], [152], [39] представлены результаты, развивающие идеи, изложенные в [149], [150].