§ 8.3. Представление нечеткого алгоритма в виде графа
Во многих случаях нечеткий алгоритм удобно представлять в виде ориентированного графа [23]. Каждой дуге ставят в соответствие инструкцию условия и инструкцию операции. Входные, выходные, внутренние переменные в нечетком алгоритме представляются нечеткими множествами. Выполнение алгоритма эквивалентно поиску в графе пути, связывающего помеченные вершины: начальные и конечные. Приведем необходимые для дальнейшего изложения известные определения графа и пути в графе.
Определение 8.2. Графом
называется тройка (V,
где
— множество элементов, называемых вершинами графа
— множество элементов, называемых ребрами графа, причем
— функция, ставящая в соответствие каждому ребру и
упорядоченную или неупорядоченную пару вершин
называются концами ребра и. Если множество
конечно, то граф называется конечным. Если
-упорядоченная пара (т. е.
то ребро и называется ориентированным ребром или дугой, исходящей из вершины и входящей в вершину
называется началом,
— концом дуги
. Граф, все ребра которого ориентированные, называется ориентированным графом.
Определение 8.3. Последовательность вершин и ребер графа
называется путем
из
вершины
в вершину
если
для
Вершина гл называется началом,
концом пути, число
называется длиной пути.
Определение 8.4. Нечеткая программа есть четверка
где
- вектор входа,
-вектор программы (внутренние переменные),
— вектор выхода,
— ориентированный граф:
— нечеткие переменные, определяющие нечеткие множества на
2) в графе
существует точно одна вершина, называемая начальной (стартовой), которая не является конечной вершиной никакой дуги, и существует точно одна вершина, называемая конечной (финальной), которая не является начальной вершиной никакой дуги: любая вершина графа находится на некотором пути из стартовой
в финальную вершину Н;
3) в графе
любая дуга а, не ведущая в Н, связана с нечетким отношением
и нечеткой инструкцией
; каждая дуга а, ведущая в Н, связана с нечетким отношением
и инструкцией
где
— нечеткое отношение и
— нечеткая операция типа пересечения, объединения, операция нечеткой арифметики, оператор размывания, оператор типа модификаторов и т. д.
Далее понадобятся следующие свойства нечетких множеств.
Пусть А и В нечеткие подмножества соответственно на
и
— нечеткое отношение в
— нечеткое множество в
индуцированное
— нечеткое множество в V, индуцированное А;
— проекция
на
тогда справедливы следующие свойства:
Свойство 8.1.
.
Свойство 8.2. Если
то
Свойство 8.3. АRВ имеет наивысшую степень истинности среди всех
для любого нечеткого множества С из V.
В графе, описывающем алгоритм, выделяются дуги с условием и без условия (далее вместо знака равенства, обозначающего пересылку значения, будем использовать стрелку
а) без условия:
;
б) с условием: если
то
в) с условием:
Заметим, что условие б) эквивалентно условию в форме в)
(свойство 8.1). Такую замену можно пояснить следующим образом:
представляет собой ту величину, которая удовлетворяет отношению
при наличии X, а пересечение
есть та часть Г, которая удовлетворяет отношению
Рис. 8.2. Граф нечеткого алгоритма
Возможны следующие условия завершения работы.
1. Если
имеет не нулевую степень принадлежности.
2. Если существуют элементы из
чьи степени принадлежности выше, чем некоторый заранее заданный порог.
3. Если осуществлено заранее заданное число шагов или минимальное число шагов для достижения определенного заранее результата.
4. Если пользователь, оценивая по своему критерию результаты очередного цикла, останавливает работу.
Пример 8.6. Рассмотрим алгоритм, изображенный на рис. 8.2, где несколько
Проследим последовательность выполнения.
Таблица 8.2 (см. скан)
Рис. 8.2. Граф нечеткого алгоритма
На дуге
присваиваются начальные значения (вторая строка табл. 8.2).
Далее возможны последовательно следующие переходы
где
где
Далее вычисляем:
где
Выполнение продолжается аналогично для
и т. д., пока будет удовлетворено выбранное условие завершения.