Треугольные нормы, транзитивное замыкание нечетких бинарных отношений и нечеткие выводы тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

РОССИЙСКАЯ АКАДЕМИЯ НАУК

ИНСТИТУТ ВЫСОКОПРОИЗВОДИТЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ

СИСТЕМ РАН

ТГБ ШГ~

1 1 ноя ш

ВУ ТХАНЬ НГУЕН

ТРЕУГОЛЬНЫЕ НОРМЫ, ТРАНЗИТИВНОЕ ЗАМЫКАНИЕ НЕЧЕТКИХ БИНАРНЫХ ОТНОШЕНИЙ И НЕЧЕТКИЕ ВЫВОДЫ

Специальность 01.01.09 - Математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

На правах рукописи

УДК 519.68:007.5

МОСКВА-1996

Работа выполнена в Институте высокопроизводительных вычислительных систем РАН.

(

Научный руководитель:- доктор физико-математических наук,

профессор A.A. Третьяков.

Официальные оппоненты:

Ведущая организация:

Защита диссертации состоится " АЬР^ДЙ 1<ВД6 г. в //_Г*часон на заседании диссертационного совета К 200.45.01 Института Высокопроизводственных Вычислительных Систем по адресу: г. Москва, ул. Вавилова, д. 37.

С диссертацией можно ознакомиться в библиотеке ИВВС РАН.

Автореферат разослан "г.

доктор физико-математических наук, профессор А.Н. Сотников, кандидат физико-математических наук, доцент В.В. Морозов.

Научно-Исследовательский Вычислительный Центр МГУ им. М.В. Ломоносова.

/7 .л. нЗр

Ученый секретарь диссертационного совета, к.ф-м.н.

^iWikUjAy Миронов С.В.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Актуальность работы.

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

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

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

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

Цель работы

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

Научная новизна работы

Научная новизна диссертационной работы заключается в следующем:

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

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

3. Впервые предложены новые понятия и определения (Б_Т) транзитивного отношения, верхнего (Б_Т) транзитивного замыкания нечетких бинарных отношений.

4. Предложены новые алгоритмы нечетких выводов для решения задачи навигации автономного транспортного средства.

5. Предположено обобщение методов дефаззификацни и процессе нечеткого управления.

6. На основе теоретических результатов транзитивного отношения нечетких бинарных отношений и алгоритмов нечетких выводов решается задача коммивояжера.

Научная и практическая ценность

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

Разработанный в диссертации новый алгоритм блоков нечетких выводов позволяет решать задачу навигации автономного транспортного средства, в которой не учитываются условия стабильности системы и уменьшается число операции в процессе вычислений в ЭВМ. Результаты этого алгоритма заложены в проекте "Маневр и обход неожиданно появившихся препятствий средствами нечеткого управления" под руководством профессора Градитского Валерия и Захарова Валерия Ропотного центра института проблемы механики РАН.

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

нечеткого упрлнлепия. Оно яиляется обобщенно двух классических методом (метода центра тяжести и метод среднего значения максимума) дефаззифпкашш н теории нечеткого контроля.

Основные положения, выносимые на защиту

1. Нечеткие числа, операции над нечеткими числами, тины нечетких чисел и их свойства.

2. (5_Т) Транзитивное отношение нечетких бинарных отношений и верхнее <8_Т) транзитивное замыкание нечетких бинарных отношений. Процедуры вычислительных процессов аппроксимации лингвистических неременных в поисково - информационной системе с применением верхнего (Б_Т) транзитивного замыкания нечетких бинарных отношений.

3. Способ применения блоков нечетких выводов и сравнение эффективности новых алгоритмов с другими классическими математическими методами в задаче навигации автономного транспортного средства.

4. Результаты применения верхнего (Б_Т) транзитивного замыкания нечетких бинарных отношений и алгоритмов нечетких выводов и нечеткой задаче коммивояжера.

5. Обобщение методов дефаззификации в теории нечеткого управления.

Апробация работы

Диссертационная работа и ее приложения докладывались и обсуждались на научных семинарах в ХЬУ научно-технической конференции МИРЭА (май, 1996), на научных семинарах в отделе прикладной математики ИВВС РАН (марта 1996 и сентябрь 1996).

Публикация

По теме диссертации публикована 1 научная статья, доклад на ХЬУ научно-технической конференции МИРЭА (май, 1996), доклад на научной конференции в Крыму (сентябрь, 1996), в печати 4 стати в сборнике вопросы кибернетики РАН и трудах МИРЭА. Этот список статей приведен в конце автореферата.

Структура и объем диссертации

Диссертация состоит из введения, трех глав, заключения, приложения и списка литературы. Объем диссертации составляет страниц, включая рисунки, таблицы и список литературы.

СОДЕРЖАНИЕ РАБОТЫ

Во введении.

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

Проведено рассмотрение различных типов нечетких чисел как нечеткие числа (Ь_Ю-тииа, так и нечеткие числа трапециидального типа. Исследованы особенности расширенных арифметических операций над нечеткими числами и свойства алгебры нечетких чисел, основанные на принципе обобщения Заде.

Нечетким числом А называется нечеткое множество числовой оси К, имеющее функцию принадлежности цА:и~»[0,1Ь где Я- множество действительных чисел, 3(И)={ц]ц:К->[0,1 ]}- множество всех нечетких чисел числовой оси.

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

исходного отображения (р: X-(Х,У- произвольные множества ) на

класс нечетких множеств, а также обобщить определения операций над нечетким множеством

Пусть X), 1=1, г, Х=Х1хХ2Х...хХг, -декартовое произведение универсумов и A1.A2.---.Ar - нечеткие множества в X1.X2.---.Xr :оответственно. Декартовое произведение А1,Аг,...,Аг определяется :лсдуюшим образом

А1хА2Х,...)хАгд/хшт(цА1(Х1),...,ЦАг(Хг))/(Х1,...,Хг).

Пусть /- отображения X в У такое, что у~Г(Х,,...,Хг).

Гогда нечетким множеством В, получаемым в результате применения / к \]ХА2Х,...,ХАГ по принципу обобщения Заде, является нечеткое множество, ьчеющее следующую функцию принадлежности:

цв(у)А «ир 1тп(цА1(х1),-- -ЦАг(Хг)), и

11,12.....1г

у=Г(11,12,..,1г)

цв(у) АО если Г(у)=0.

В сняли с принципом обобщения имеется следующая теорема Теорема.

Пусть В=1"(А1,А2.....Аг). Имеет место следующее утверждение:

|Г(АЬА2, ..,Аг)]«=Г(А1„,А2„,...,АГа),

тогда и только тогда, когда: УуеУ, 3 .....х'г,

Ив(у) = ИА1х хАг(

С помощью этого принципа, в работах Жанн, Напиас, Мижумото п Топако , Васс ... изучаются расширенные операции над нечеткими числами. Для нечетких чисел цд> Ив. ИсеЗ(К) и Ух.у.геЯ имеет место следующие соотношения:

С=А*Ворс(г)А у ИА(Х)лцв(У),

г=1'у

где * арифметические расширенные операции сложения, алгебраической

суммой, умножения, вычитания и деления (©, + ,8,0,0) над А,В,С.

Нечеткое число (Ь-И)- типа может быть задано с помошыо функции принадлежности (Ь-Н)-тина, которое удовлетворяет следующим свойствам:

a) Ц-х)ДЬ(х) , К(-х)ДИ(х),

b) Ь(0)ЛК(0)Л 1,

где Ь и И- певозрастающие функции на множестве неотрицательных действительных чисел.

Нечеткое число трапециидальпого типа представляется следующим образом:

А В СП3"

где ОА и 01= внешние зоны. АВ = низкая полутень. ВС = стержень. СО = верхняя полутень. АО = основа. Во второй главе.

Н рамках работы лап краткий об.тор и теории треугольных норм и копорм.

Оператор Т-порма, Т(р,ч) является двухместной функцией

Т:|0,1 |х|0,1|-> [0,1] удовлетворяющейся следующими требованиями:

Т(0,0)=0, Т(р,1)=Т(1,р)=р,

Т(р,ч)=Т(ч,р), Т(р,я)<Т(г,8), если р<г и Т(р,Т(я,г))=Т(Т(р,ч),г), где р,я,г,ве1.

Оператор Т-конормы в I2 является двухместной функцией

5:[0,1|х[0,1]->• [0,1) удовлетворяющейся следующими требованиями:

5(0,0)=0, 8(р,0)=5(0,р)=р,

5(р,я)=5(ч,р), 5(р,ч) <5(г,8), если р<г и 5(р,5^,г))=5(5(р,я),г), где р,ч,г,зе1.

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

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

Пусть Т - Т-порма ив- Б-конорма. Тогда (5_Т)-композиция двух нечетких отношений И и С на Е называется нечеткое отношение Р в котором композиция определяется следующим образом V х,у,геЕ: Цн»с(х,у)А 8 Т(ри(х,г), цс(г,у)),

— хеЕ

или

№с(х,У)АТ(ия(х,г),Мо(2,у))=

5(8(......5(Т(рк(х,х),рк(х,у)),Т(цк(х,г),рк(г,у)))

,....),Т(цк(х,у),цк(у,у)))

и обозначается

цо).

Будем использовать следующее рекурсивное обозначение К^н'-^К, ¡>2, ^ЛИ.

Нечеткое отношение R называется (S_T) - транзитивным, если R2 с R или, другими словами:

Vx,y: ця2(х,у)А S T(nR(x,z),nR(z,y)) ^ цк(х,у).

— zsE

Нечеткое отношение G называется верхним (S_T) - транзитивным замыканием для нечеткого отношения R, если

1. G - (S_T)-Tpaii3HTHBiioe отношение.

2. Vx.yeE: цк(х,у)<цо(х,у).

3. I 1йо(х,у)-№(х,у)]Д min 2 lHGo(x,y)-HR(x,y)].

i.yeE Со

S-объедииением двух нечетких отношений R, G на ЕхЕ называется нечеткое отношение S(R,G) на ЕхЕ, определяемое следующим образом

MS(R,G)(x,y)^S^R(x,y), HG(x,y)) и обозначим S -объединение двух нечетких отношений R, G на ЕхЕ через RVG. Пусть R - нечеткое отношение. Тогда ряд

RVR2V ... VR"V ... называется (S,S_T)-Процедурой.

Обозначим через R* результат применения этой процедуры к нечеткому отношению R. R* Д RVR2V...VR'... где ieN. Теорема.

Для каждого нечеткого отношения R существует одно и только одно верхнее (S_T) - транзитивное замыкание. Теорема.

Пусть нечеткое отношение R - рефлексивное и симметричное. Тогда, если S не является S-конормой вида шах и все члены |iR(x,y)>0, то верхнее (S_T) - транзитивное замыкание отношения R будет тривиальным отношением G: HG(x,y)=l, Vx,yeE. Теорема.

Пусть нечеткое отношение R - рефлексивное и симметричное, и для некоторого к выполняет равенство:

Rk+i = Rk где Rk= Rk-i.R к>2 н s=max, T=min. Тогда верхнее (S_T) транзитивное замыкание G = Rk. Теорема.

Пусть нечеткое отношение R - рефлексивное и симметричное, card(E)=n, S=max, T=min и G - верхнее (S_T) транзитивное замыкание нечеткого отношения R. Тогда существует keN такое, что G=Rk и k<n-l.

Теорема.

Если (5_Т) -композиция ассоциативная, коммутачпикая и О -(5_Т) -тран.читипмые отношения па Е, то (5_Т) композиция - также

(5_Т) транзитивное отношение на Е. Теорема.

Ее ли (5_Т) - композиция дистрибутивна относительно 5, то К* является (в_Т) - транзитивным отношением. Теорема.

Пусть задано отношение И, 5=тах и Т-пекоторая Т-норма, тогда (5,5_Т) - процедура сходится к его верхнему (5_Т) - транзитивному замыканию К*. Теорема.

Если сагс!(Х)=п, 5=тах и Т - любая Т-норма, то при (5,5_Т) -процедуре будет

Ё'= ЯУ.....УИк , к<п-1.

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

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

Экспериментально разработанная математическая модель информационно-поисковой системы применяется и частности в проекте вычислительного центра университета Южной Калифорнии. В третьей главе

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

Если |У(| является Б и У2-У1 является П, то является М Если |У(| является Б и У2-У1 является О, то является Б Если |У1) является М , то ^ является М

[Блок выводов 2]

Если 02-01 является П и является М, то <о является ОБ

Если 02-01 является П и является Б, то со является ОМ

Если 02-01 является О и является М, то а> является ПБ

Если 02-01 является П и является Б, то со является ПМ

где ОБ=отрицательный большой, ОМ=отрицателышй маленький, ПБ=положителышй большой, ПМ=положителы[ый маленький

и где О является центром препятствия, Рс является точкой проекции и го и И является радиусом препятствия и радиусом проекции соответственно. 01 является угол между сегментами 1 и ¡+1, 02 - угол между сегментами ¡+1 и 1+2 соответственно, о является уголь проекции точки столкновения.

Исследована нечеткой задачи коммивояжера с применением верхнего (8_Т) транзитивного замыкания нечетких бинарных отношений и блоков нечетких выводов.

Разработано обобщения метод дефаззифцкации для процесса нечеткого управления. Основа этого метода дефаззификации состоит из двух шагов.

1. Преобразуется возможное распределение соответствующее нечеткому множеству дефаззификации в вероятностное распределение, удовлетворяющее некоторыми условиями.

2. Выбирается значение дефаззификации, получающее на предыдущем

шаге.

Предполагаем, что нечеткое множество нечеткого иьшода системы управления нечетко» логикой V, задано функцией принадлежности а>1 определено на У={у),у2, . . у,,}. Предполагаем ещё, что штах=мах|<»1].

1.1

Первым шагом и этом метоле дефаззификации является преобразование V и Е, другое нечеткое множество определено па У. Мы будем определять функции принадлежности V; с номотыо следующего отображения:

То,|) : V -» Е,

где

си, если Ю|>а

(1-р)ю| если Ю(<а Здесь а, Р являются параметрами преобразования и ае[0,1], Ре[0,1]. Это преобразование называется адаптивным преобразованием нечеткого множества.

Вторым шагом в этом методе дефаззификащш является нормировка полученной последовательности у;.

р.- У|- для псех 1= 1,п

л ]=«

Последним шагом в процессе адаптивной дефаззификации является эпределение значения дефаззификации:

1

Георема.

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

1. а=0 или а>0 и р=0 то имеет метод дефаззификации центра ■яжести.

2. а=тах{а>|} и Р=1 то имеет метод дефаззификации среднего

течения максимума. ? заключении.

Сформулированы основные результаты, полученные в диссертации. 1. Проведено исследование и систематизация общих свойств нечетких исел и отношений, создана нечеткая арифметика, изучены различные тины [ечетких чисел, наиболее широко используемые для представления ¡ечеткости системы.

2. .Введены новые понятия и определения на основе классов треугольных норм и треугольных конорм, транзитивного замыкания нечетких бинарных отношений (Б_Т) транзитивное отношение, (Б_Т) композиция и верхнее (Б_Т) транзитивное замыкание нечетких бинарных отношений. Получены результаты и процедуры вычисления, аппроксимации лингвистических переменных на ЭВМ. Новые результаты применены в информационно-поисковой системе.

3. Предложен новый алгоритм нечетких выводов для решения задачи ' навигации автономного транспортного средства. Этот алгоритм применен в проекте института проблемы механики РАН.

4. Исследована нечеткой задача коммивояжера с применением алгоритма верхнего (8_Т) транзитивного замыкания и блоков нечетких выводов.

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

Разработаны на персональном компьютере две программы:

1. Первая программа реализована алгоритмами верхнего (8_Т) транзитивного замыкания нечетких бинарных отношений о информационно-поисковой системе.

2. Вторая программа реализована новым алгоритмом нечетких выводов в задаче навигации автономного транспортного средства.

Основные результаты работы изложены в следующих публикациях:

1. Ву Тхань. Оператор Т-нормы и Методы (Б_Т) транзитивного замыкания нечетких бинарных отношений - Сборник научных трудов МИРЭА "Управление и моделирование в сложных тацшческих системах"., Москва., 1995., с. 130-137.

2. Ву Тхань. Нечеткие отношения и вывод в задачах интеллектуального управления. Сборник трудов международного научно-технического семинара "Современные технологии в задачах управления и обработки информации"., Алушта., 1996., с. 33-34.

3. Ву Тхань. Нечеткие выводы в процессе нечеткого управления. Сборник научных трудов "ХЬУ научно-технической конференции МИРЭА". (в печати).

4. П.В. Купцов, Ву Тхань. Моделирование нечетких управляющих систем, методы дефаззификации. Сборник трудов МИРЭА. (в печати).

5. Ву 'Гхань. Обобщенные методы транзитивного замыкания нечетких отношений. Вопросы Кибернетики 1996. (п печати).

6. Ву Тхапь. Методы дефаззификации и задачах интеллектуального управления. Вопросы Кибернетики 1996. (в печати).

УПП «Репрография»

Заказ № 2$ (6 тираж ^ экз.