Лабораторная работа № 5. «Изучение методов оптимизации на основе теории нечетких бинарных отношений»

«Изучение методов оптимизации на основе теории нечетких бинарных отношений»

ВВЕДЕНИЕ

 

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

 

Цель работы - ознакомление с основными свойствами и операциями над нечеткими отношениями и их применением в задачах принятия решений.

 

Краткие теоретические сведения

 

Нечеткие бинарные отношения

Определение. Нечеткое бинарное отношение - нечеткое подмножество декартового произведения двух базовых множеств X и Y.

 

Пусть X={0; 1}. Тогда X ´ X={(0, 0), (0, 1), (1, 0), (1, 1)}.

 

Пример нечеткого отношения

 

 

Графический способ задания Матричный способ задания:

бинарного отношения:

 

 

Понятие включения для нечетких множеств задается так:

 

 

С бинарными отношениями можно производить те же действия, что и с обычными нечеткими множествами.

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

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

 

.

 

Функцию принадлежности для нечеткого бинарного отношения обычно обозначают так же, как и само отношение. Например, r₁ - имя бинарного отношения; r₁(x, y) - функция принадлежности этого отношения. Она задается следующим образом:

 

.

Пример. Пусть бинарные отношения r₁ и r₂ заданы следующими матрицами:

 

Тогда их композиция есть нечеткое бинарное отношение, задаваемое матрицей

 

Операция композиции имеет единичное бинарное отношение - это бинарное отношение, задаваемое единичной матрицей:

 

Обратное бинарное отношение

 

Пусть имеется бинарное отношение r(x, y), тогда его обратное отношение определяется так

.

 

С точки зрения матричного представления отношений эта операция сводится к транспонированию матриц.

 

Специальные бинарные отношения

 

Различают следующие свойства бинарных отношений:

 

1. Рефлексивность - E Ì r, т.е. для любого x r(x, x)=1.

2. Слабая рефлексивность: для любой пары (x, y) r(x, y) £ r(x, x).

3. Сильная рефлексивность: для любой пары (x, y) выполняется следующее r(x, x)=1 Ù r(x, y)< 1.

4. Антирефлексивность: rÇ E или для любого x r(x, x)=0.

5. Слабая антирефлексивность: r(x, y) ³ r(x, x).

6.^* Сильная антирефлексивность: для любого y¹ x r(x, x)=0 Ù r(x, y)> 0.

7. Симметричность: r=r^-1 или для любой пары (x, y) r(x, y)=r(y, x).

8. Антисимметричность: rÇ r^-1 Ì E или min (r(x, y), r(y, x))=0 при x ¹ y.

9. Асимметричность: rÇ r^-1=Æ или min (r(x, y), r(y, x))=0 при x= y.

10. Сильная полнота: rÈ r^-1 =X или max (r(x, y), r(y, x))=1 при x = y.

11.^* Слабая полнота (связность, линейность): max (r(x, y), r(y, x))> 0.

12. Транзитивность: .

 

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

 

Имеет место следующая теорема о декомпозиции нечеткого бинарного отношения:

Для любого бинарного отношения имеет место следующая формула:

 

При этом любые отношения классов 1-12, кроме обозначенных (*), являются таковыми вместе с любым своим a-уровнем (0< a< 1). Например, отношение r транзитивно тогда и только тогда, когда любой его a-уровень, рассматриваемый как четкое бинарное отношение, транзитивен.

 

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

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

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

 

1. Транзитивным расширением бинарного отношения r_Т называется любое транзитивное бинарное отношение, включающее r: rÌ r_Т.

2. Минимальное из транзитивных расширений r называется его транзитивным замыканием :

.

Теорема

Имеет место следующее равенство

,

где r^k - k-я степень отношения, то есть

 

r¹=r;...; .

Если множество X конечно, причем мощность его равна: ê X ê =n, то

.

Если же r также и рефлексивно, то

.

 

Пример. Задача кластеризации в криминалистике.

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

 

 

Рис. 1

 

Были приглашены эксперты - физиономисты, которые, проанализировав эти фотографии, составили отношения сходства (рис. 1). Здесь каждой фотографии соответствует вершина графа, а дуги имеют значения, соответствующие степени сходства лиц, оцененные экспертами. Интервал [0, 1] здесь заменен на множество целых чисел {1, 2, …, 10}. Это рефлексивное и симметричное отношение. Однако очевидно, что это отношение не транзитивно и, следовательно, не является отношением эквивалентности. Операционист выполнил транзитивное замыкание данного отношения (рис. 2):

 

Рис. 2

Построим a-уровни этого нечеткого отношения эквивалентности для a = 10, 9, 8, 7 (рис. 3). Получаемые четкие отношения эквивалентности , , , соответствуют различным требованиям к степени сходства.

 

 

 

 

 

С требованием сходства 0.7 мы получили требуемое разделение лиц на две семьи: {1, 2, 5} и {3, 4}.

 

Нечеткое отношение предпочтения

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

Исходя из данного отношения r, можно построить 3 отношения, связанных с ним:

1. Отношение безразличия r^I.

2. Отношение эквивалентности r^e.

3. Отношение строгого предпочтения r^S.

На языке операций над множествами имеем:

 

 

 

 

На языке элементов это соответствует формулам:

 

 

 

.

 

Свойства построенных отношений:

1. r^I и r^e являются рефлексивными и симметричными.

2. r^S антирефлексивно и антисимметрично.

3. если r транзитивно, то r^e и r^S транзитивны.

 

 

Нечеткое множество недоминируемых альтернатив

 

Рассмотрим отношение . Используя это отношение, мы можем построить нечеткое множество недоминируемых альтернатив . Данное множество можно считать нечетким аналогом множества Парето. Зафиксируем элемент x. Тогда r^S(y, x) становится функцией y, которую можно рассматривать как функцию принадлежности элемента x некоторому множеству доминант Д(x). При этом r^S(y, x) характеризует степень предпочтительности элемента y перед элементом x.

Поскольку нас интересует, насколько x недоминируемо, то построим множество, дополнительное к Д(x):

.

Его функция принадлежности выражается так:

.

Она выражает степень принадлежности некоторого элемента y к недоминантам x, т.е. к множеству .

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

 

 

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

 

.

 

Пример. Пусть базовое множество альтернатив состоит из четырех элементов x₁, x₂, x₃, x₄. Отношение r задается матрицей:

 

Выполняя действия для нахождения отношения , получим

 

Таблица действий для отношения :

	x1	x2	x3	x4
y1	1-0	1-0	1-0.2	1-0
y2	1-0.3	1-0	1-0	1-0.5
y3	1-0	1-0.4	1-0	1-0
y4	1-0.5	1-0	1-0.2	1-0

Таким образом, элемент x₁ доминирует с максимальной силой 0.5; x₂ - 0.6; x₃ - 0.8; x₄ - 0.5.

 

Тогда x₃ является максимально недоминируемым элементом этого множества.

З А Д А Н И Е

 

1. Изучить по конспекту лекций и предлагаемой литературе основные понятия и определения теории нечетких отношений и ознакомиться с их классификацией. Ознакомиться по настоящим методическим указаниям с простейшими операциями над нечеткими отношениями.

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

3. Построить алгоритм одной из рассматриваемых операций, указанной преподавателем.

4. Составить и отладить программу на языке высокого уровня, реализующую построенный алгоритм.

5. Оформить отчет о выполненной лабораторной работе.

 

С О Д Е Р Ж А Н И Е О Т Ч Е Т А

 

Отчет должен содержать следующие обязательные части:

 

1. Алгоритм операции над нечеткими отношениями, указанной преподавателем.

2. Листинг текста программы на языке высокого уровня, реализующей построенный алгоритм.

3. Листинг протокола работы программы, реализующей алгоритм операции, предложенной преподавателем.

4. Протокол классификации отношения, предложенного преподавателем.

 

К О Н Т Р О Л Ь Н Ы Е В О П Р О С Ы

 

1. Какие способы формализации нечеткости Вы знаете?

2. Каковы источники возникновения нечеткости бинарных отношений?

3. Какие классы нечетких бинарных отношений Вы знаете?

4. Приведите определения основных классов нечетких бинарных отношений.

5. Приведите определения основных операций над нечеткими бинарными отношениями (объединение, пересечение, включение, композиция).

 

ЛИТЕРАТУРА

 

1. Зайченко Ю.П. Исследование операций. - Киев: Вiща шк., 1988.-552 с.

2. Нечеткие множества в моделях управления и искусственного интеллекта / Под ред. Д.А. Поспелова.- М.: Наука, 1986.- 312 c.

3. Обработка нечеткой информации в системах принятия решений. Под ред. А.Н. Борисова М.: Радио и связь, 1988.- 303 c.