§ 8.3. Представленпе нечеткого алгоритма в виде графа

Во многих случаях нечеткий алгоритм удобно представлять в виде ориентированного графа [23]. Каждой дуге ставят в соответствие инструкцию условия и инструкцию операции. Входные, выходные, внутренние переменные в нечетком алгоритме представляются нечеткими множествами. Выполнение алгоритма эквивалентно поиску в графе пути, связывающего помеченные вершины: начальные и конечные. Приведем необходимые для дальнейшего изложения известные определения графа и пути в графе.

Определение 8.2. Графом G называется тройка {V, U, ф), где V = {ѵУ — множество элементов, называемых вершинами графа и = {и) — мпожество элементов, называемых ребрами графа, причем V (\и —Ф, ф — функция, ставящая в соответствие каждому ребру и^и упорядоченную или неупорядоченную пару вершин (ѵі, Ѵг), Vi и Ѵг называются концами ребра и. Если множество С/ и F конечно, то граф называется конечным. Если ф(м) = (Уі, Уг)—упорядоченная пара (т. е.    (г;,, Ѵг) Ф

Ф{ѵ2, V,)), то ребро и называется ориентированным ребром или дугой, исходящей из вершины Ѵі и входящей в вершину Ѵг, Ѵі, называется началом, Уг — концом дуги и. Граф, все ребра которого ориентированные, называется ориентированным графом.

Определение 8.3. Последовательность вершин и ребер графа G. ViUiVj^u^ ... Vi^_^UnVi^ называется путем [ѵі^, г;;„] из

вершины Ѵі^ в вершину Уі„, если ф (ц^) =   і^і^) для

к — \, 2, ..., п. Вершина г;^ называется началом, а концом пути, число п называется длиной пути.

Определение 8.4. Нечеткая программа есть четверка (X, Y, Z, G), где Х = (хі, ..., Х;) — вектор входа, Y — = {Уі, ..., Уп)—вектор программы (внутренние переменные), Z = (Zj, ..., Zm) — вектор выхода, G — ориептироваппый граф:

1)   Хі, уі, Zi — нечеткие переменные, определяющие нечеткие множества на ?7, F, TF;

2)   в графе G существует точно одна вершина, называемая начальной (стартовой), которая не является конечной вершиной никакой дуги, и существует точно одна вершина, называемая конечной (финальной), которая не является начальной вершиной никакой дуги: любая вершина графа находится на некотором пути из стартовой S в финальную вершину Я;

3)   в графе G любая дуга а, не ведущая в Н, связана с нечетким отношением Ва{Х, F) и нечеткой инструкцией Y — = fa{X, F); каждая дуга а, ведущая в Н, связана с нечетким отношением Ra{X, Y) и инструкцией z = fa{z, х, у), где R — нечеткое отношение и / — нечеткая операция типа пересечения, объединения, операция нечеткой арифметики, оператор размывания, оператор типа моідификаторов и т. д.

Далее понадобятся следующие свойства печетких множеств.

Пусть А ш В нечеткие подмножества соответственно на U и V, Д — нечеткое отношение в UXV, А* = R ° В — нечеткое множество в U, индуцированное В, В* = В° А — нечеткое множество в F, индуцированное А\

П (і?, U) — проекция R на U, тогда справедливы следующие свойства:

Свойство 8.1. П(у1ЛВ, и) = АПА*, П(ЛЛВ, Ѵ) = В^В*.

Свойство 8.2. Если А' = Л{АНВ, U), то А'ВВ = ARB.

Свойство 8.3. ARB* имеет наивысшую степень истинности среди всех ARC для любого нечеткого множества С из F.

В графе, описывающем алгоритм, выделяются дуги с условием и без условия (далее вместо знака равенства, обозначающего пересылку значения, будем использовать стрелку -^-):

а)   без условия; F /„(X, F);

б)   с условием: если Ra{X, F), то F ■*-fa{X, F);

в)   с условием:

Заметим, что условие б) эквивалентно условию в форме в)

(свойство 8.1). Такую замену можно пояснить следующим образом: Y* представляет собой ту величину, которая удовлетворяет

отпошеппю На при наличии X, а пересечепие У* П У есть та часть У, которая удовлетворяет отношению Ra-

Возможны следующие условия завершения работы.

1.   Если Z имеет не нулевую степень принадлежности.

2.   Если существуют элементы пз Z, чьи стенѳни принадлежности выше, чем некоторый заранее заданный порог.

3.   Если осуществлено заранее заданное число шагов или

минимальное число шагов для достижения определенного заранее результата.

4. Если пользователь, оценивая по своему критерию результаты очередного цикла, останавливает работу.

Пример 8.6. Рассмотрим алгоритм, изображенный на рис. 8.2, где несколько = {0,814, 1|5, 0,816};

Проследим последовательность выполнения.

На дуге (SV) присваиваются начальные значения (вторая строка табл. 8.2).

Далее возможны последовательно следующие переходы

где где

Далее вычисляем:

где

Выполнение продолжается аналогично для SVVV, SVVVII, SVVVV и т. д., пока будет удовлетворено выбранное условие завершения.