Разработка программного обеспечения для проверки транзитивности нечетких отношений

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

Введение

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

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

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

Проверка транзитивности нечеткого отношения

Для проверки транзитивности нечеткого бинарного отношения воспользуемся следующим определением [3].

Определение 1. Нечеткое бинарное отношение называется транзитивным, если

где  – функция принадлежности нечеткого бинарного отношения  на .

Из определения следует, что ввиду необходимости перебора и сравнения всех элементов для проверки транзитивности нечеткого отношения требуется сравнительно большое количество операций. Для проверки на транзитивность множества  мощности  потребуется совершить  раз  операций.

Для проверки бинарного отношения на транзитивность для четких множеств используется понятие композиции отношений.  Определим понятие композиции для нечетких отношений.

Определение 2. Композицией нечетких бинарных отношений  называется нечеткое бинарное отношение  с функцией принадлежности:

μ_(ρ_1∘ρ_2 ) (x,y)=max┬(z∈X)⁡min┬⁡〖{μ_(ρ_1 ) (x,z),μ_(ρ_2 ) (z,y)}.〗

Соответственно, композиция отношения  на себя:

μ_(ρ^2 ) (x,y)=max┬(z∈X)⁡〖min{μ_ρ (x,z),μ_ρ (z,y)}.〗

Тогда, для проверки на транзитивность можно воспользоваться свойством транзитивных отношений:

Свойство 1. Если отношение ρ транзитивно, то выполняется ρ 2 ⊆ ρ

Транзитивное замыкание

Алгоритм нахождения транзитивного замыкания нечеткого отношения, как и способ проверки на транзитивность с помощью композиции отношений, основан на нахождении композиции .

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

Trρ = ρ∪ρ 2∪…∪ρ n−1 

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

Для сокращения вычислений на каждом этапе будет использоваться следующее утверждение (доказательство приведено в [1]).

Утверждение 1. Пусть матрице  нечеткого отношения  поставлена в соответствие матрица , полученная из  заменой всех ненулевых элементов на единицы. Тогда нулевые элементы матриц  и  отношения , заданного на множестве  мощности  совпадают.

Программная реализация

Для написания программы использовался язык Python, а также библиотека NumPy для работы с матрицами и PyQt для проектирования интерфейса. Приведены алгоритмы работы и описания функций, реализующих проверку на транзитивность и расчет транзитивного замыкания нечеткого отношения.

1.        Проверка на транзитивность, с использованием 1 способа:

Функция tr_relation получает на вход матрицу  нечеткого бинарного отношения предпочтения , заданного на множестве альтернатив  мощности . Заводится переменная-флаг равная нулю, которая прервет последующий алгоритм в случае нарушения условия, описанного в (1). Нумерация строк и столбцов внутри матрицы начинается с нуля.

• Последовательно, начиная с нуля, выбирается строка. Индекс строки ключевого элемента далее обозначается x.
• Аналогично выбирается столбец. Индекс столбца ключевого элемента далее обозначается у.
• Таким образом, выбран элемент (x, y) ρ  , который будет проверен на транзитивность по условию (1). Значение элемента для последующего сравнения копируется в отдельную переменную.
• Последовательно перебираются все возможные значения Z   от 0   до n-1  Для каждого  Z значение min{ (x, z), (z, y)} ρ ρ сравнивается с выбранным элементом. Если условие (1) не выполняется, «поднимается» флаг и перебор завершается досрочно, функция выдает сообщение о том, что отношение не транзитивно.
• Если перебор последовательно были перебраны и сравнены все элементы и флаг не был поднят – выводится сообщение о транзитивности отношения.

Вычислительная сложность алгоритма для наихудшего случая (полный перебор для транзитивного отношения) составляет  Однако, из-за возможности досрочного завершения алгоритма, в среднем результаты будут лучше. 

2.        Проверка на транзитивность с использованием композиции  (2):

Вход функции tr_check аналогичен предыдущей. Заводится новый массив размерности , в котором будут хранится значения функций принадлежности для отношения . Нумерация строк и столбцов внутри матриц начинается с нуля.

• Последовательно, начиная с нуля, выбирается строка. Индекс строки ключевого элемента далее обозначается x
• Аналогично выбирается столбец. Индекс столбца ключевого элемента далее обозначается у.
• Таким образом, выбран элемент  нового массива для вычисления. Заводим отдельную переменную max_val для хранения максимального значения, приравниваем к нулю.
• Последовательно перебираются все возможные значения  от  до  Для каждого  значение  сравнивается с max_val. Если минимальное значение больше – то max_val приравнивается к нему.
• Значение   нового массива обновляется в соответствии с max_val, значение временной переменной обнуляется, выбирается новый ключевой элемент.

Выходом данного алгоритма будет матрица бинарного нечеткого отношения . Далее данная матрица сравнивается с входной поэлементно с использованием функции np.less_equal, входящей в библиотеку NumPy, на основании свойства 1 делается вывод о транзитивности отношения.

Алгоритм имеет вычислительную сложность  для любого случая и требует выделения памяти для хранения нового массива размерности .

3.        Транзитивное замыкание нечеткого бинарного отношения:

На вход функции tr_zam также подается матрица  нечеткого бинарного отношения предпочтения , заданного на множестве альтернатив  мощности . Создается массив , полученный из  заменой всех ненулевых элементов на единицы, а также массив  для хранения результата.

• Последовательно, начиная с двойки, матрица  возводится в степень , где  принимает значения от . С помощью функции argwhere, встроенной в NumPy, создается массив  с индексами ненулевых элементов данной матрицы .
• Заводится массив  для хранения результатов на текущем проходе алгоритма.
• Для каждого элемента, индекс которого хранится в массиве  повторяются шаги 4 и 5 алгоритма проверки на транзитивность с использованием композиции отношения на себя. Массив  заполняется результатами.
• В массив  записывается результат дизъюнкции массива  и , возвращение на 1 шаг,  увеличивается на единицу.

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

Модельные примеры

Пример 1. Проверить транзитивность нечеткого отношения , заданного матрицей .

Для проверки используется первый способ, описанный ранее. Нужно перебрать элементы и проверить выполнение (1) для каждого из них.

Для элемента  соотношение (1) не выполняется. Отношение не является транзитивным. Если бы соотношение выполнялось для , проверялись бы последующие элементы.

Пример 2. Для нечеткого нетранзитивного отношения , заданного матрицей  из предыдущего примера, найти транзитивное замыкание.

Создается матрица , полученная из  заменой всех ненулевых элементов на единицы.

Матрица R возводится в квадрат:

Ненулевые элементы  выписываются в массив . Таким образом, используя утверждение 1 для вычисления , нужно будет пройтись только по трем элементам, остальные будут равны нулю. Для вычисления используется соотношение (2).

Тогда, матрица композиции отношения  на себя:

Для вычисления транзитивного замыкания используется (3):

Получено транзитивное замыкание отношения .

Заключение

Написано программное обеспечение для реализации проверки транзитивности нечеткого отношения и расчета транзитивного замыкания. Применение алгоритмов продемонстрировано на модельных примерах. На примере показано сокращение количества вычислений при использовании сформулированного утверждения. Выходные данные программного обеспечения совпали с полученным решением.

1. Смерчинская С.О., Ящина Н.П. Агрегирование нечетких отношений строгого порядка // Известия высших учебных заведений. Математика. 2022, №7, С. 30-43.
2. Гусева А.И., Тихомирова А.Н. Дискретная математика для информатиков и экономистов: Учебное пособие. ‒М.: НИЯУ МИФИ, 2010. С. 260-264.
3. Губко М.В. Лекции по принятию решений в условиях нечеткой информации. Версия 1. [Электронный ресурс] // Aup.ru: Административно-управленческий портал. ‒М.: ИПУ РАН, 2004. URL: http://www.aup.ru/files/m539/m539.pdf (дата обращения 19.01.2023).