Geum.ru

Романько Дмитрий Андреевич моу гимназия №19, класс 9 Научные руководители: Блюмин С. Л., д ф. м н., проф кафедры пм лгту шуйкова И. А., к т. н., доц кафедры пмиит лгпу г. Липецк. 2008 решение

Вид материалаРешение

Содержание


Цель работы
План исследования
Нечеткие реляционные уравнения вида Q ◦ R = S , где ◦ = (мах, Т)
Применение нечетких реляционных уравнений в задачах диагностики
Исходными данными
Математическая модель задачи диагностики
Подобный материал:



Одиннадцатая региональная молодежная научная

и инженерная выставка

«Шаг в будущее, Центральная Россия»


Решение нечетких реляционных уравнений


Автор Романько Дмитрий Андреевич

МОУ Гимназия №19, класс 9


Научные руководители:

Блюмин С.Л., д.ф.-м.н., проф. кафедры ПМ ЛГТУ

Шуйкова И.А. , к.т.н., доц. кафедры ПМиИТ ЛГПУ


г. Липецк. 2008

Решение нечетких реляционных уравнений.

Романько Дмитрий Андреевич

Россия, Липецкая область, г. Липецк, МОУ Гимназия №19, 9 класс


Аннотация


В работе рассматриваются нечеткие реляционные уравнения вида
Q ◦ R = S , где ◦ = (мах, Т), которые применяются в различных системах искусственного интеллекта, в частности в задачах диагностики. Формализация задач диагностики, описание их математических моделей, позволяет в дальнейшем применять их в различных прикладных областях: медицине, системах технической диагностики, металлургии и т.д.

Изложение основ решения нечетких реляционных уравнений предваряет раздел, описывающий расширения стандартных логических операций, в частности, описываются инвертор, t-норма и t-конорма. Представлены различные типы нечетких реляционных уравнений – простейшие, полиномиальные и системы полиномиальных уравнений. Приведены алгоритмы решения указанных типов уравнений, позволяющие в дальнейшем произвести их компьютерную реализацию.

Цель работы: изучить нечеткие реляционные уравнения вида Q ◦ R = S ,
где ◦ = (мах, Т) и провести сравнительный анализ методов решения четких и нечетких матричных уравнений.

Методы, используемые в работе: теория матриц и методы решения матричных уравнений, основы нечеткой алгебры – расширение стандартных логических операций, нечеткие соответствия и отношения; нечеткие реляционные уравнения Q ◦ R = S , где ◦ = (мах, Т) и методы их решения.

Апробация работы проводилась на основе задач решения матричных уравнений . Уравнения вида Q ◦ R = S, где Q – матрица, R – вектор, были подобраны таким образом, чтобы они были разрешимы как с помощью четкого подхода, так и с помощью методов нечеткой алгебры. Решения указанных уравнений с операцией ◦ – обычного умножения матриц приведены методом Гаусса. Решения уравнений, в которых ◦= (мах, Т) проводились методами решения нечетких реляционных уравнений.

Выводы. Сравнительный анализ полученных результатов решения четких и нечетких матричных уравнений показал, что они отличаются как численно, так и количеством самих решений. Операция ◦= (мах, Т) позволяет оставаться «в пределах» отрезка [0;1] и получать соответствующие результаты. Классическое умножение вещественных матриц, к которым, в частности, относятся и нечеткие отношения, позволяет в качестве результата получать любые вещественные числа (не ограниченные отрезком [0;1]). Операция ◦= (мах, Т) обеспечивает и возможность прикладной интерпретации нечетких реляционных уравнений в системах диагностики.

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


Решение нечетких реляционных уравнений.

Романько Дмитрий Андреевич

Россия, Липецкая область, г. Липецк, МОУ Гимназия №19, 9 класс


План исследования


В работе рассматриваются нечеткие реляционные уравнения и методы их решения.

В ходе исследования были поставлены и решены следующие задачи:
  1. Изучение литературы по основам нечеткой алгебры:

– расширение стандартных логических операций;

– нечеткие соответствия и отношения;

– композиция нечетких соответствий и отношений;

– нечеткие реляционные уравнения.
  1. Составление и решение нечетких реляционных уравнений Q ◦ R = S , где ◦ = (мах, Т)

– простейшие уравнения;

– полиномиальные уравнения;

– системы полиномиальных уравнений.
  1. Решение матричных уравнений методами четкой и нечеткой математики.

– решение составленных матричных уравнений методом Гаусса;

– решение составленных матричных уравнений методами нечеткой математики;
  1. Анализ решений матричных уравнений предложенными способами.

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

Исследование опирается на следующие библиографические источники:


  1. Асаи К.и др. Прикладные нечеткие системы. – М.: Мир, 1993.
  2. Блюмин С.Л., Шуйкова И.А., Сараев П.В., Черпаков И.В. Нечеткая логика: алгебраические основы и приложения. – Л.:ЛЭГИ, 2002.



Решение нечетких реляционных уравнений.

Романько Дмитрий Андреевич

Россия, Липецкая область, г. Липецк, МОУ Гимназия №19, 9 класс


    1. Расширение стандартных логических операций
    1. Нечеткая алгебра

При переходе от булевой алгебре к нечеткой часть аксиом булевой алгебры перестает выполняться. Стремление наиболее полно сохранить эту выполнимость приводит к необходимости изменения существующих операций или введения новых [2]. Одни из которых -  и . В этом случае для произвольного  выполняются  и . Легко проверить, что и коммутативны, ассоциативны, но не связаны дистрибутивным законом. Более того, существует связь между старыми и новыми операциями:

и , то есть имеется дистрибутивность и относительно конъюнкции и дизъюнкции соответственно.

Нечеткая алгебра представляет собой структуру < X, +, ·, ‘, 0, 1 > c заданной системой аксиом. Символы операций выбраны исключительно для простоты формулировок, их не следует воспринимать как соответствующие арифметические или логические операции. Пусть , . Система аксиом, адекватная нечеткой алгебре, имеет вид:

1.  1’. ,

2. , 2’. ,

3. , 3’. ,

4. , 4’. ,

5. , 5’. ,

6. , 6’. 

7. 

8. ,

9. , 9’. ,

10. , 10’. ,

11. . 11’. 

Подалгебра тех элементов из X, для которых 

(или, что равносильно, ), является булевой алгеброй, в которой , . Выбирая различные операции +, ·,¯ , 0, 1, удовлетворяющие указанной

системе аксиом, получаем различные нечеткие алгебры.

Рассмотрим отрезок L = [0, 1]. Отображения L → L и L2 → L будем рассматривать как унарную и бинарную функции соответственно. Введем на L новые операции.

Определение. Инвертором (нечетким отрицанием) N называется унарная строго убывающая функция, удовлетворяющая условиям

,  и .

В аксиоматической форме:

,

;

;

.

Аксиома N1 — граничное условие, устанавливающее поведение инвертора на границе отрезка, N2 — правило двойного отрицания, N3 — наиболее существенное требование: изменение порядка последовательности значений из L.

Из N1 и N2 следует, что , поэтому, заменив N1 на , получим эквивалентную систему аксиом. Существует множество функций, удовлетворяющих

N1–N3. Наиболее простая и часто используемая из них .

Определяя инвертор подобным образом, имеем выполнимость всех аксиом:

,  и  при

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


    1. t-норма, t-конорма

Пусть на множестве M определена бинарная функция  ,

тогда  при  . Зафиксируем сначала значение

 , затем  . Будем называть полученные унарные

функции O1 и O2 частными функциями O. Если, например, для фиксированного y0 имеет место при  , то O1 — функция, изменяющая частный порядок по первой переменной. Если же при  , функцию будем называть сохраняющей частный порядок по этой переменной. Аналогично можно ввести понятие функции изменяющей (сохраняющей) порядок по второй переменной.

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

Рассмотрим введение расширения стандартных логических операций – конъюнкции и дизъюнкции.

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

 и , .

Аксиоматическое определение t-нормы:

,

Свойства:

;

;

;

.

Типичной t-нормой является взятие минимума (логическое произведение)

. Другие часто используемые t-нормы - t-норма Лукасевича (Lukasiewicz) или граничное произведение , алгебраическое произведение . На рисунке 1 показаны примеры наиболее простых t-норм.



Рис 1. Примеры t-норм.

Свойства:

.

.

.

Определение. t-конормой (s-нормой) S называется коммутативная, ассоциативная бинарная функция, частные функции которой сохраняют порядок, имеющая 0 в качестве нейтрального элемента, и для которой выполняются условия  и . На рисунке 2 показаны примеры наиболее простых t-конорм.



Рис 2. Примеры t-конорм.

Свойства:

.

.

 удовлетворяет S1–S4, где T и N — любые t-норма и инвертор соответственно.


    1. Нечеткие соответствия и отношения

Пусть X, Y — непустые четкие множества. Нечетким соответствием R является нечеткое подмножество декартова произведения множеств X ×Y .Множество X называют областью отправления, а множество Y — областью прибытия нечеткого соответствия.

Пусть X — непустое множество. Нечетким отношением R является нечеткое подмножество декартова произведения . X – область задания нечеткого отношения.

Пусть . Нечеткое отношение «Приблизительно равняется», заданное на множестве U может быть определено, как:

µ R(1,1) = µ R(2,2) = µ R(3,3)= 1

µ R(1,2) = µ R(2,1) = µ R(2,3)= µ R(3,2)= 0.8

µ R(1,3) = µ R(3,1) = 0,3

Композицией нечеткого множества А, заданного на множестве Х и нечеткого соответствия R, заданного на , называется нечеткое множество

А ◦ R={(y, µ А ◦ R (y))}.

µА ◦ R = supT{ µА(x); µR(x,y)},  ,  где Т – t-норма.

В частном случае вместо t-нормы может выступать операция min.

Композиция А ◦ R представляет собой проекцию нечетного соответствия R

на множестве А.

Пусть множество Х={x1, x2, x3}. На множестве Х задано нечеткое множество

C= {(x1, 0.2), (x2, 1), (x3, 0,2)}. Нечеткое отношение R задано на .

R =

Произведением sup – min множества С на отношение R представляет собой нечеткое множество.

С ◦ R =  ◦= 

Пусть на  и  заданы нечеткие соответствия ,

. Композицией соответствий называется нечеткое соответствие

R ◦ S = S = {((u, w) , μR◦S (u, w))}, заданное на .

µR ◦ S (u,w) = supT{ µR(u, υ), µS(υ, w)}, где Т – t-норма.

В частном случае вместо t-нормы может выступать операция min.

Рассмотрим нечеткое отношение R = «х значительно больше, чем у»

R =

Задано также нечеткое отношение S = «y очень близко к z»

S =

sup-min композиция соответствий определяется следующем образом

R ◦ S =  ◦ =

Композицию соответствий можно рассматривать как произведение матриц, задающих соответствия. Только вместо операции умножения при этом используется операция взятия Т-нормы, а вместо операции сложения используется взятия максимума.


  1. Нечеткие реляционные уравнения вида Q ◦ R = S , где ◦ = (мах, Т)
    1. Простейшие нечеткие реляционные уравнения [2]

Рассмотрим простейший случай, когда известные в обеих частях представляют собой числа из .Требуется найти x, удовлетворяющее одному из уравнений

при 



Решение может быть найдено как пересечения решений двух соответствующих неравенств: например,  и . Введем ряд так называемых разностных операторов:

, .

Предложение. T+ (a, b) существует при любых 

Предложение. Если , то .

Неравенство , имеет решение . Решение двойственного ему неравенства, существует при , им будет отрезок . Пересечение решений неравенств является решением .

Кроме того, - необходимое и достаточное условие его разрешимости. Таким образом, решением уравнения будет отрезок , если .


Если каждое из уравнение  разрешимо, то



Пример. 

Уравнение разрешимо, так как 

Решением является отрезок [0.5; 1]


    1. Полиномиальные уравнения

Нечеткое реляционное уравнение вида

или 

при заданных  и ◦, будем называть полиномиальным. Символ T в левых частях — символ транспонирования.

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

То есть, если max{ai}≥b, то уравнение разрешимо

Предложение. Для того, чтобы уравнение имело непустое множество решений, необходимо и достаточно, чтобы его решением было , где

. Кроме того, оно будет являться максимальным решением.

Далее находятся минимальные решения по формуле:



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

Пример. (0.2, 0.7, 0, 0.5)◦(x1 , x2 , x3 , x4 )T = 0.4 при ◦ = ,

. - Граничное произведение.

Уравнение разрешимо, т.к. ; . Максимальное решение

.

 и , следовательно, существует два минимальных решения:

,

.


    1. Системы полиномиальных уравнений

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

Предложение. Для того, чтобы система имела непустое множество решений, необходимо и достаточно, чтобы решением этой системы было  ,где Gj — максимальное решение j-го полиномиального уравнения.

Пусть М – множество минимальных решений системы полиномиальных уравнений. Составляются всевозможные объединения .

Для того, чтобы система имела минимальные решения, необходимо и достаточно, чтобы минимальные элементы (а также несравнимые ни с одним из оставшихся), взятые из объединения min-решений всех уравнений, входящих в систему, являлись решением системы.


Пример.

 ◦= 

Где ◦ 
  1. 
  2. 
  3. 

 разрешимы, т.к. 
  1. 

,

,

,


  1. 

,

,

,


  1. 

,

,

,



 =- является собой решением системы полиномиальных уравнений и представляет собой максимальное решение.

Минимальные решения:
    1. , 

,

,

; 
    1. 

,


    1. , 

,

,

; 

Составим всевозможные объединения минимальных решений:

;

;

;

;

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

; – минимальное решение. Проверим вектор, находящийся между минимальным и максимальным решением: (0.7, 0.4, 0.1). При выполнении операции ◦ равенство верно, следовательно, решение также верно.

Примеры систем полиномиальных уравнений также приведены в приложении 1.


  1. Решение матричных уравнений в четкой и нечеткой математике
    1. Решение матричных уравнений методом Гаусса

Решим уравнение из пункта 2.3 с помощью метода Гаусса:


 <=><=>

<=>  <=> 











Проверка:



Примеры решения систем полиномиальных уравнений с помощью метода Гаусса приведены в приложении 2.

Сравнительный анализ полученных результатов решения четких и нечетких матричных уравнений показал, что они отличаются как численно, так и количеством самих решений. Причем, уравнения, которые являются неразрешимыми в нечеткой математике, могут быть разрешимы в четкой математике и наоборот. Операция ◦= (мах, Т) позволяет оставаться «в пределах» отрезка [0;1] и получать соответствующие результаты. Классическое умножение вещественных матриц, к которым, в частности, относятся и нечеткие отношения, позволяет в качестве результата получать любые вещественные числа (не ограниченные отрезком [0;1]). Операция ◦= (мах, Т) обеспечивает и возможность прикладной интерпретации нечетких реляционных уравнений в системах диагностики.


    1. Применение нечетких реляционных уравнений в задачах диагностики

Целью задачи диагностики является определение причин отклонений в функционировании технических систем или определение (исключение) того или иного заболевания (нарушения) в живых системах [1]. Математическая модель задач диагностики может быть описана на основе нечетких реляционных уравнений

X ◦ Q = S , где ◦ = (мах, Т).

Рассмотрим задачу диагностики в терминах медицинской области.

Имеется группа из М болезней, которые схожи между собой по соответствующим им симптомам.

Каждая болезнь может характеризоваться N симптомами. Набор симптомов является фиксированным и позволяет диагностировать каждую болезнь из группы.

Исходными данными является вектор N симптомов, свойственных схожей группе M болезней. Компоненты вектора определяются экспертом на основе субъективных наблюдений или, если это возможно, объективных измерений.



На компоненты вектора накладываются ограничения

.

Субъективные оценки экспертов переводятся их вербальных оценок (согласно предварительно разработанной шкале в соответствии с данной предметной областью) в их числовые эквиваленты из отрезка [0; 1].

Результаты объективных измерений также должны быть переведены в числа отрезка [0; 1] согласно шкале перевода для каждого измерения.

Результатами будет являться вектор «выраженности» каждой из предполагаемых болезней у пациента.



На компоненты вектора накладываются ограничения .

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

Математическая модель задачи диагностики


Нечеткое отношение Q = представляет собой заранее заданное отношение (полученное на основе опроса экспертов в данной предметной области), каждая компонента aij которого – степень наличия j-го симптома у i-й болезни.

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

Развитием представленной работы может служить, в частности, проблема поиска наиболее адекватной для исследуемой предметной области операции ◦, правомерность использования которой должна подтверждаться достоверными результатами.


Библиографический список:


  1. Асаи К.и др. Прикладные нечеткие системы. – М.: Мир, 1993.
  2. Блюмин С.Л., Шуйкова И.А., Сараев П.В., Черпаков И.В. Нечеткая логика: алгебраические основы и приложения. – Л.:ЛЭГИ, 2002.


Приложение 1

Решение систем полиномиальных уравнений методами нечеткой алгебры.

Задача 1.


 ◦= 

Где ◦ 
  1. 
  2. 
  3. 

 разрешимы, т.к. 
  1. 














  1. 














  1. 















 =– не является решением системы полиномиальных уравнений следовательно система решений не имеет.

Задача 2.


 ◦= 

Где ◦ 


  1. 
  2. 
  3. 

 разрешимы, т.к. 
  1. 














  1. 














  1. 















 =– не является решением системы полиномиальных уравнений следовательно система решений не имеет.


Приложение 2

Решение системы полиномиальных уравнений из приложения 1 с помощью метода Гаусса.

Задача 1.

 <=><=>


<=>  <=> 









Проверка подтверждает правильность найденных корней..


Задача 2.

 <=><=>


<=>  <=> 










Проверка подтверждает правильность найденных корней.