Министерство образования и науки Российской Федерации САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Д.К. Потапов НЕКЛ...
27 downloads
294 Views
3MB Size
Report
This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
Report copyright / DMCA form
Министерство образования и науки Российской Федерации САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Д.К. Потапов НЕКЛАССИЧЕСКИЕ ЛОГИКИ Учебное пособие
Санкт-Петербург 2006
УДК 510.64 Р е ц е н з е н т ы:
кафедра компьютерных технологий и систем Санкт-Петербургского государственного университета (заведующий кафедрой доктор физикоматематических наук, профессор Е.И. Веремей); доктор технических наук, старший научный сотрудник В.А. Матвеев (заведующий кафедрой общих математических и естественнонаучных дисциплин НОУ Академия управления и экономики, г. СанктПетербург)
Печатается по постановлению Редакционно-издательского совета факультета прикладной математики – процессов управления Санкт-Петербургского государственного университета
Потапов Д.К. Неклассические логики: Учебное пособие. – СПб.: СПбГУ, 2006. – 108 с. В пособии рассматриваются неклассические логики, используемые для представления знаний, спецификации и анализа поведения программ. Излагаются элементы неклассических логик, аппарат нечёткой логики, рассмотрена программная реализация моделей нечёткой логики с помощью инструментального средства математической системы MATLAB 7.0.4 – пакета Fuzzy Logic Toolbox (пакет нечёткой логики). Основу учебного пособия составляют материалы курса лекций, который читается автором на факультете прикладной математики – процессов управления Санкт-Петербургского государственного университета в рамках дисциплины «Неклассические логики». Пособие предназначено для студентов математических факультетов университетов, а также читателей, интересующихся новыми информационными технологиями. Одобрено Учебно-методической комиссией факультета прикладной математики – процессов управления Санкт-Петербургского государственного университета. Библиогр. 25 назв.
© Д.К. Потапов, 2006 © Санкт-Петербургский государственный университет, 2006
Потапов Д.К. Неклассические логики
ОГЛАВЛЕНИЕ
Предисловие ................................................................................ 5 Введение ...................................................................................... 6 Глава I. Неклассические логики ................................................ 8 1.1. Пропозициональные логики ............................................................................... 8 1.1.1. Интуиционистские логики .......................................................................................... 8 1.1.2. Многозначные логики ................................................................................................. 8 1.1.3. Нечёткие логики и нечёткие подмножества............................................................... 9 1.1.4. Модальные логики .................................................................................................... 12 1.1.5. Временные (темпоральные) логики.......................................................................... 15
1.2. Предикатные логики .......................................................................................... 16 1.2.1. Многосортные логики первого порядка................................................................... 16 1.2.2. Слабая логика второго порядка ................................................................................ 16 1.2.3. Бесконечные логики .................................................................................................. 17 1.2.4. Логика с новыми кванторами ................................................................................... 17
1.3. Предикатные временные логики и их приложение к программированию 18 1.4. Алгоритмические логики................................................................................... 21 1.5. Задачи и упражнения.......................................................................................... 24
Глава II. Нечёткая информация и выводы .............................. 26 2.1. Нечёткие множества ........................................................................................... 27 2.1.1. Основные характеристики нечётких множеств........................................................ 28 2.1.2. О методах построения функций принадлежности нечётких множеств .................. 30
2.2. Операции над нечёткими множествами .......................................................... 31 2.2.1. Логические операции ................................................................................................ 31 2.2.2. Алгебраические операции......................................................................................... 34
2.3. Нечёткая и лингвистическая переменные ...................................................... 36 2.3.1. Нечёткие числа .......................................................................................................... 38 2.3.2. Операции над нечёткими числами............................................................................ 38 2.3.3. Нечёткие числа (L-R) типа........................................................................................ 39
2.4. Нечёткие отношения .......................................................................................... 41 2.5. Нечёткие выводы ................................................................................................ 44 2.5.1. Алгоритм Mamdani.................................................................................................... 46 2.5.2. Алгоритм Tsukamoto ................................................................................................. 47 2.5.3. Алгоритм Sugeno ....................................................................................................... 47 2.5.4. Алгоритм Larsen ........................................................................................................ 48 2.5.5. Упрощённый алгоритм нечёткого вывода................................................................ 49 2.5.6. Методы приведения к чёткости ................................................................................ 50 2.5.7. Нисходящие нечёткие выводы.................................................................................. 51
2.6. Пример: нечёткий регулятор ............................................................................ 52 2.7. Эффективность систем принятия решений, использующих методы нечёткой логики......................................................................................................... 53 3
Оглавление
Глава III. Пакет Fuzzy Logic Toolbox ...................................... 55 3.1. Назначение и возможности пакета Fuzzy Logic Toolbox ............................... 55 3.2. Графический интерфейс Fuzzy Logic Toolbox................................................. 55 3.2.1. Состав графического интерфейса ............................................................................. 55 3.2.2. Построение нечёткой аппроксимирующей системы ............................................... 55 3.2.3. Построение экспертной системы: сколько дать на «чай»? ...................................... 60 3.2.4. Экспорт и импорт результатов.................................................................................. 64 3.2.5. Создание пользовательских функций принадлежности .......................................... 65
3.3. Графический интерфейс гибридных систем ................................................... 66 3.4. Графический интерфейс программы кластеризации.................................... 71 3.5. Работа с Fuzzy Logic Toolbox в режиме командной строки........................... 72 3.5.1. Возможности работы в режиме командной строки ................................................. 72 3.5.2. Функции вызова программ графического интерфейса ............................................ 72 3.5.3. Задание функций принадлежности........................................................................... 73 3.5.4. Функции сохранения, открытия и использования созданной системы................... 80 3.5.5. Функции использования графического окна............................................................ 81 3.5.6. Функции создания, просмотра структуры и редактирования систем нечёткого вывода.................................................................................................................................. 82 3.5.7. Функции создания и/или обучения гибридных сетей с архитектурой ANFIS........ 86 3.5.8. Функция кластеризации ............................................................................................ 89 3.5.9. Функция генерации FIS-структуры .......................................................................... 90 3.5.10. Функция генерации структуры нечёткого вывода ................................................. 91 3.5.11. Функция возврата центров кластеров..................................................................... 92 3.5.12. Другие различные функции .................................................................................... 93 3.5.13. Функции вызова диалоговых окон интерфейса ..................................................... 95
3.6. Работа Fuzzy Logic с блоками Simulink............................................................ 96 3.6.1. Пример: контроль уровня воды в баке ..................................................................... 96 3.6.2. Построение нечёткой модели с использованием блоков Simulink.......................... 99 3.6.3. Демонстрационные примеры работы с пакетом Fuzzy Logic Toolbox.................. 100
Список литературы ................................................................. 106
4
Потапов Д.К. Неклассические логики
Предисловие Учебное пособие предназначено для студентов третьего курса направления 010400 «Информационные технологии», изучающих неклассические логики. Дисциплина «Неклассические логики» относится к циклу «математические и естественнонаучные дисциплины» ГОС ВПО и входит в число дисциплин федерального компонента. Семестровый курс «Неклассические логики» является непосредственным продолжением курсов «Основы дискретной математики» и «Математическая логика и теория алгоритмов». Пособие состоит из трёх глав: неклассические логики, нечёткая информация и выводы, пакет Fuzzy Logic Toolbox. Взаимосвязь разделов линейна, т.е. для изучения каждой последующей главы необходимо освоить предыдущие главы. Перед экзаменом студентам полезно проделать предложенные задачи и упражнения. В первой главе рассказывается об основных неклассических логиках, базирующихся как на исчислении высказываний (пропозициональные логики), так и на исчислении предикатов (предикатные логики). Излагаются основы нечётких логик, темпоральных (временных или динамических) логик, а также алгоритмических логик. Показывается роль неклассических логик в построении программ, анализе и доказательстве их правильности. Во второй главе подробно излагается аппарат нечёткой логики. В третьей главе рассмотрена программная реализация моделей нечёткой логики с помощью инструментального средства математической системы MATLAB 7.0.4 – пакета Fuzzy Logic Toolbox (пакет нечёткой логики).
Основы неклассических логик, излагаемые в настоящем пособии, могут использоваться при изучении ряда профилирующих дисциплин для подготовки специалистов по информатике, вычислительной технике, прикладной математике, автоматике и автоматизированному управлению.
Д.К. Потапов, 2006 год
5
Введение
Введение Логические теории делятся на два класса, образуя системы классической и неклассической логики. Классическая логика как система знаний сформировалась ещё в 4 в. до н.э. в трудах выдающегося древнегреческого мыслителя Аристотеля. Неклассическая логика возникла в конце 19 – начале 20 века в результате критики и дополнений некоторых основных положений парадигмы классической логики. Среди основных её представителей можно назвать Г. Фреге, Б. Рассела, Р. Карнапа, Я. Лукашевича, А. Тарского, С. Лесьневского, Н.А. Васильева, К. Гёделя, Г. фон Вригта, С. Крипке, Я. Хинтикку. Неклассическая логика включает в себя модальную логику, занимающуюся исследованием различных модальностей (возможности и необходимости, обязательности знания, доказуемости и др.); темпоральную (временную) логику, эксплицирующую процесс кумулятивного приобретения и накопления знаний, характерный для математизированных наук; многозначную логику, предполагающую более чем два значения истинности высказываний; релевантную логику, учитывающую связи высказываний по содержанию; паранепротиворечивую логику, допускающую использование противоречивых высказываний; нефрегевскую логику, принимающую во внимание ситуации как значения высказываний; квантовую логику, предполагающую нарушение законов классической логики в микромире; вероятностную логику, связанную с вероятностным характером (индуктивных) умозаключений и др. Идущий в настоящее время процесс порождения всё новых и новых систем неклассической логики позволяет охарактеризовать современное состояние логики как период логического плюрализма. Европейская культурная традиция со времён Аристотеля предъявляет к логике требования строгости, полноты и непротиворечивости. Любое высказывание может иметь только два значения истинности – истина или ложь. Третьего не дано (закон исключённого третьего). Эта классическая логика была формализована на языке математики (алгебра логики) в конце XIX века в виде Булевой логики. Однако, в повседневной жизни человек оперирует нестрогой логикой, его суждения и высказывания зачастую противоречивы, а цели, которые он ставит себе в жизни, несовместны. Но, как ни странно, эти нестрогость и противоречивость обыденной логики отнюдь не мешают людям успешно достигать жизненных целей. В рамках Европейской культурной традиции это нонсенс, поскольку неполнота и противоречия рассматриваются в ней либо как следствие временного незнания, которое в ходе прогресса науки должно быть устранено, либо как признак слабости интеллекта (так называемая «женская логика»). Но как быть с тем непреложным фактом, что очень многие успешные представительности прекрасного пола используют именно «женскую логику»? Быть может, неполнота и противоречивость не дефект логики, но атрибут мира и мышления? Как в классической физике на рубеже XIX-XX веков возник мировоззренческий кризис, разрешившийся сменой парадигмы – принятием квантовой теории и теории относительности, так и в классической логике возник своеобразный кризис, разрешившийся признанием неполноты, нестрогости и противоречивости не недостатками, но напротив, атрибутами мышления. Нетрудно увидеть аналогии между принципом неопределённости Гейзенберга и сформулированным основателем теории нечётких множеств Л. Заде принципом несовместности: «По мере возрастания сложности исследуемых нами систем наша способность делать точные и в то же время значимые суждения об их поведении уменьшается, вплоть до некоторого порога, за которым точность и осмысленность (релевантность) становятся практически несовместимыми характеристиками». При этом необходимо иметь в виду, что тот мировоззренческий кризис, о котором сказано выше, актуален только для человека, сформировавшегося в рамках Европейской культурной традиции. Для так называемого «Восточного» взгляда на мир неполнота, нечёткость и противоречивость как мышления, так и мира всегда были очевидны. 6
Потапов Д.К. Неклассические логики Логики, отличные от Булевой, в настоящее время принято определять термином «неклассические логики». Неклассические логики можно разделить на две большие группы – многозначные и нечёткозначимые. К первой группе относятся логики, в которых значения истинности высказываний могут принимать не только значения 0 и 1, как в Булевой, где 0 – ложь, 1 – истина, но из интервала [0, 1] (дискретного или непрерывного). Первые многозначные логики были предложены ещё в начале XX века – трёхзначные логики Лукашевича, k-значные логики Поста и др. В нечёткозначимых логиках значения истинности принимают нечётко определённые значения. Например, высказывание может быть почти истинно, примерно истинно, не совсем истинно и т.п. Эти логики имеют своим математическим основанием теорию нечётких множеств (понятие нечёткого множества было введено в 1965 г. Лотфи Заде). Как известно, аппарат нечётких множеств и нечёткой логики уже давно (более 10 лет) с успехом применяется для решения задач, в которых исходные данные являются ненадёжными и слабо формализованными. Сильные стороны такого подхода: • описание условий и метода решения задачи на языке, близком к естественному; • универсальность: согласно знаменитой теореме FАТ (Fuzzy Approximation Theorem), доказанной Б. Коско (B. Kosko) в 1993 г., любая математическая система может быть аппроксимирована системой, основанной на нечёткой логике; • эффективность (связана с универсальностью), поясняемая рядом теорем, аналогичных теоремам о полноте для искусственных нейронных сетей, например, теоремой вида: для каждой вещественной непрерывной функции g, заданной на компакте U, и для произвольного e > 0 существует нечёткая экспертная система, формирующая выходную функцию f (x ) такую, что sup g ( x) - f ( x ) £ e , где || ∙ || – символ принятого расстояния xÎU
между функциями. Вместе с тем для нечётких экспертных и управляющих систем характерны и определённые недостатки: 1) исходный набор постулируемых нечётких правил формулируется экспертомчеловеком и может оказаться неполным или противоречивым; 2) вид и параметры функций принадлежности, описывающих входные и выходные переменные системы, выбираются субъективно и могут оказаться не вполне отражающими реальную действительность. Для устранения, по крайней мере частично, указанных недостатков рядом авторов было предложено выполнять нечёткие экспертные и управляющие системы адаптивными – корректируя, по мере работы системы, и правила и параметры функций принадлежности. Среди нескольких вариантов такой адаптации одним из самых удачных, по-видимому, является метод так называемых гибридных нейронных сетей. Гибридная нейронная сеть формально по структуре идентична многослойной нейронной сети с обучением, например, по алгоритму обратного распространения ошибки, но скрытые слои в ней соответствуют этапам функционирования нечёткой системы. Так: • 1-й слой нейронов выполняет функцию введения нечёткости на основе заданных функций принадлежности входов; • 2-й слой отображает совокупность нечётких правил; • 3-й слой выполняет функцию приведения к чёткости. Каждый из этих слоёв характеризуется набором параметров (параметрами функций принадлежности, нечётких решающих правил, активационных функций, весами связей), настройка которых производится, в сущности, так же, как для обычных нейронных сетей. В пособии рассмотрены теоретические аспекты составляющих подобных сетей, а именно, аппарат нечёткой логики, основы теории гибридных сетей применительно к задачам управления и принятия решений в условиях неопределённости. Особое внимание уделено программной реализации моделей указанных подходов инструментальными средствами математической системы MATLAB 7.0.4. 7
Глава I. Неклассические логики
Глава I. Неклассические логики В курсах «Основы дискретной математики» и «Математическая логика и теория алгоритмов» изучались основные формальные исчисления – исчисление высказываний и исчисление предикатов. Рассмотрение этих исчислений не случайно. Практика математических исследований позволяет сформулировать тезис о выразимости всех утверждений и доказательств классической математики с помощью исчисления предикатов. Таким образом, эмпирически справедлив Тезис Гильберта. Любое математическое утверждение может быть записано на языке исчисления предикатов, а любое математическое доказательство можно провести в рамках исчисления предикатов. Вместе с тем формализация утверждений и доказательств вызывает известные неудобства и на практике рассматриваются различные модификации логики высказываний и логики предикатов (неклассические логики), приспособленные для решения соответствующих им задач. Ниже рассмотрим основные неклассические логики, которые делятся на пропозициональные (т.е. модифицирующие логику высказываний) и предикатные (т.е. видоизменяющие логику предикатов). Кроме того, изложим некоторые элементы темпоральных и алгоритмических логик, которые используются для создания и анализа программ.
1.1. Пропозициональные логики 1.1.1. Интуиционистские логики Интуиционистские логики – логики, с помощью которых описываются способы вывода высказываний, истинных с точки зрения интуиционизма, т.е. совокупности идей и методов, для которой основным критерием истинности математического суждения является интуитивная убедительность возможности мысленного эксперимента, связываемого с этим суждением. Основное отличие интуиционистского исчисления высказываний состоит в замене в исчислении высказываний закона исключённого третьего (состоящего в доказуемости всевозможных формул j Ú Øj ) или эквивалентного ему закона двойного отрицания ( ØØj ® j ) более слабым принципом противоречия: j ® (Øj ® y ) . Таким образом, интуиционистское исчисление высказываний получается из исчисления высказываний заменой десятой схемы аксиом на принцип противоречия. Всякая формула, выводимая в интуиционистском исчислении высказываний, приемлема с интуиционистской точки зрения. Аналогично интуиционистскому исчислению высказываний интуиционистское исчисление предикатов является ослаблением исчисления предикатов. При этом становятся недоказуемыми формулы вида "x (j ( x ) Ú Øj ( x )) , а из Ø$x j ( x ) не выводится "xØj ( x ) .
1.1.2. Многозначные логики Рассмотренная в курсах «Основы дискретной математики» и «Математическая логика и теория алгоритмов» двузначная логика допускает следующее обобщение на k-значный случай. Функцией k-значной логики от n переменных x1 , x2 ,..., xn называется любая функция f : {0,1,..., k - 1}n ® {0,1,..., k - 1}. В качестве формул k-значной логики рассматриваются термы сигнатуры S k = {Ù ( 2 ) ,Ú ( 2 ) , ×d }d Î{0,1,..., k -1} , интерпретации которых определяются по индукции согласно следующим соотношениям для любых формул φ и ψ: 8
Потапов Д.К. Неклассические логики ìk - 1, если f (j ) = d , f (j d ) = í î0, если f (j ) ¹ d , - f (j Ù y ) = min{ f (j ), f (y )} , - f (j Ú y ) = max{ f (j ), f (y )} ( f (j Ù y ) = f (j ) Ç f (y ) , f (j Ú y ) = f (j ) È f (y ) ). Аналогично теореме о функциональной полноте для двузначной логики доказывается Теорема 1.1.1. Всякая функция f k-значной логики представляется в виде -
f ( x1 ,..., x n ) =
Ú
( d1 ,...,d n )Î{0 ,..., k -1}n
f (d 1 ,...,d n ) Ù x1d1 Ù ... Ù x nd n .
□
Правая часть в последнем равенстве называется совершенной дизъюнктивной нормальной формой (СДНФ). По аналогии с двузначной логикой в k-значной логике система функций { f i | i Î I } называется полной, если любая функция k-значной логики представима в виде терма сигнатуры { f i |i Î I} . Из представления произвольной функции k-значной логики в виде СДНФ следует, что совокупность функций x Ù y , x Ú y , x d , где d Î {0,1,..., k - 1} , образует полную систему. Обобщениями k-значной логики являются счётнозначная и континуумзначная логики, в которых функции f имеют соответственно счётное или континуальное число значений.
1.1.3. Нечёткие логики и нечёткие подмножества Одним из важнейших классов, который можно рассматривать как модификацию класса многозначных логик, является класс вероятностных или нечётких логик, составляющий основу теории вероятностей. Каждая нечёткая логика представляет исчисление высказываний, у которого всякая пропозициональная переменная А интерпретируется некоторым значением P( A) = c (где с – элемент числового интервала [0;1] ), называемым вероятностью для переменной А. Число с задаёт степень определённости или степень чёткости для переменной А. При этом, если значение с равно или близко к нулю, считается, что степень чёткости, т.е. вероятность для переменной А, мала, а если с равно или близко к единице, то степень чёткости или вероятность для переменной А велика. В нечётких логиках формулы исчисления высказываний называются событиями, а их интерпретации Р – вероятностями. Если P(j ) = 1 (соответственно P(j ) = 0 ), то событие j называется достоверным (невозможным). При этом вероятности событий определяются в соответствии со следующими соотношениями для любых событий j и y : 1) P(j Ú Øj ) = 1 ( j Ú Øj – достоверное событие); 2) P(j Ù Øj ) = 0 ( j Ù Øj – невозможное событие); 3) если P(j Ù y ) = 0 (т.е. события j и y несовместны), то P(j Ú y ) = P(j ) + P(y ) . 4) если секвенция j ├y доказуема (т.е. событие j влечет событие y ), то P(j ) £ P(y ) . Из соотношений 1–4 выводится следующее Предложение 1.1.2. Для любых событий j и y справедливы следующие соотношения: (а) P(Øj ) = 1 - P(j ) (вероятность события j и вероятность дополнительного события Øj в сумме равна единице); (б) если секвенция ├ j доказуема, то P(j ) = 1 (доказуемое событие достоверно); (в) если секвенция j ├ доказуема, то P(j ) = 0 (противоречивое событие невозможно); 9
Глава I. Неклассические логики (г) P(j Ú y ) £ P(j ) + P(y ) ; (д) P(j Ú y ) = P(j ) + P(y ) - P(j Ù y ) . Доказательство. Для доказательства пункта (а) рассмотрим соотношение 3 при y = Øj , посылка которого выполняется по соотношению 2. Тогда на основании соотношения 1 получаем P(j ) + P(Øj ) = P(j Ú Øj ) = 1 . Пункт (б) вытекает из соотношений 1 и 4 и эквивалентности j º (j Ú Øj ) для любой доказуемой формулы j . Если секвенция j ├ доказуема, то доказуема секвенция ├ Øj . Тогда P(Øj ) = 1 и на основании пункта (а) получаем P(j ) = 0. Тем самым установлен пункт (в). Для доказательства пункта (г) рассмотрим несовместные события j и Øj Ù y . Тогда в силу эквивалентности j Ú y º j Ú Øj Ù y и соотношения 3 имеем P(j Ú y ) = P(j ) + P(Øj Ù y ) . С другой стороны, из доказуемости секвенции Øj Ù y ├y на основании соотношения 4 получаем P(Øj Ù y ) £ P(y ) . Следовательно, P(j Ú y ) £ P(j ) + P(y ) . Из соотношения (Øj Ù y ) Ú (j Ù y ) º y и несовместности событий Øj Ù y и j Ù y в силу соотношения 3 справедливо равенство P(Øj Ù y ) + P(j Ù y ) = P(y ) , откуда получаем P(Øj Ù y ) = P(y ) - P(j Ù y ) и, значит, P(j Ú y ) = P(j ) + P(Øj Ù y ) = = P(j ) + P(y ) - P(j Ù y ) . Таким образом, справедлив пункт (д). □ С нечёткими логиками тесно связаны нечёткие подмножества данного множества. Пусть М – некоторое множество, A Í M . Принадлежность элементов из М подмножеству А полностью определяется характеристической функцией ì1, если x Î A, m A ( x) = í î0, если x Î M \ A. Теперь допустим, что функция m A может принимать любое значение в интервале [0;1]. В соответствии с этим элемент x Î M может не принадлежать множеству A ( m A ( x ) = 0) , может быть элементом A ( m A = 1) , а может принадлежать множеству А в некоторой небольшой (когда m A (x ) близко к 0) или большой (когда m A (x ) близко к 1) степени. Теперь, как и функции m A с условием r m A Í {0,1} , функции m A с условием r m A Í [0,1] дают полную информацию о степени вхождения каждого элемента множества М в множество А. На основании последнего замечания любая функция m : M ® [0, 1] называется нечётким подмножеством множества М. Таким образом, нечёткое множество А – это множество пар {(x, m (x )) | x Î M } . Пример 1.1.1. 1. В нечётком множестве A = {( x1 ,0.9), ( x 2 ,0), ( x3 ,0.2), ( x 4 ,1), ( x5 ,0.3)} элемент x1 содержится в значительной степени, x 2 не содержится, x3 содержится в небольшой степени, x 4 содержится полностью, а x5 содержится в немного большей степени, чем x3 . 2. В качестве нечётких можно рассматривать подмножества множества вещественных чисел, состоящих из чисел, приблизительно равных данному вещественному числу а. □ Определим основные теоретико-множественные отношения и операции на нечётких подмножествах. Пусть A1 « m1 и A1 « m1 – нечёткие подмножества множества М. Говорят, что А1 содержится в А2 или имеется включение А1 в А2, если m 1 ( x ) £ m 2 ( x ) для любого x Î M . Нечёткие подмножества А1 и А2 называются равными или совпадающими, если m1 = m 2 . 10
Потапов Д.К. Неклассические логики Нечёткое подмножество А1 называется дополнением нечёткого подмножества А2, если m1 (x ) = 1 - m 2 (x ) для любого x Î M . Нечёткое подмножество B « m называется пересечением (объединением) нечётких подмножеств А1 и А2 и обозначается через A1 Ù A2 (соответственно через A1 Ú A2 ), если m (x ) = min {m1 (x ), m 2 (x )} (m (x ) = max{m1 (x ), m 2 (x )}) для любого x Î M . Непосредственно проверяется, что система Á = {m | m : M ® [0;1]}; Ù, Ú, × ,0,1 , состоящая из всех нечётких подмножеств данного множества М с операциями пересечения, объединения, дополнения, константами 0 : M ® {0} и 1 : M ® {1}, удовлетворяет следующим теоретико-множественным законам: ассоциативности, коммутативности, идемпотентности, дистрибутивности, поглощения, де Моргана, двойного отрицания. Кроме того, выполняются действия с константами A Ú 0 = A, A Ù 0 = 0, A Ú 1 = 1, A Ù 1 = A . Таким образом, любая система Á является дистрибутивной решёткой. Однако в отличие от булевых алгебр в этой решётке не выполняются законы дополнения: соотношения A Ù A = 0 и A Ú A = 1 верны лишь для констант 0 и 1. Определим понятия нечёткой контактной схемы и нечёткой функции проводимости, заменяя в определениях контактной схемы и функции проводимости между полюсами пропозициональные переменные логики высказываний на пропозициональные переменные (т.е. элементарные события) нечёткой логики. При этом каждому контакту х ставится в соответствие значение m ( x ) Î [0, 1] , называемое током контакта. Затем по индукции определяется ток m нечеткой функции проводимости исходя из соотношений m ( x Ù y ) = min (m ( x ), m ( y )) (для последовательного соединения x Ù y ) и m ( x Ú y ) = max (m ( x ), m ( y )) (для параллельного соединения x Ú y ). Токами нечёткой контактной схемы называется совокупность токов нечётких функций проводимости. Пример 1.1.2. Если ток контакта х равен 0,3, ток контакта у – 0,6, то ток последовательного соединения x Ù y равен 0,3, а ток параллельного соединения x Ú y – 0,6. □ При рассмотрении предикатных нечётких логик определяется понятие нечёткого nместного отношения P (n ) на множествах A1 , A2 ,..., An в виде функции m P : A1 ´ A2 ´ ... ´ An ® [0; 1] . Способы задания нечётких отношений соответствуют общим способам задания функций. Это, например, перечисление всех элементов множества m P , если множества A1 , A2 ,..., An конечны, или аналитическое задание в виде арифметического терма. Бинарные
{
}
нечёткие отношения P ( 2 ) могут задаваться в виде поверхности ( x, y, z ) Î R 3 | z = m P ( x, y ) , в виде матрицы весов W = (w ij ) , где w ij = m P (a1i , a 2j ), a1i Î A1 , a 2j Î A2 , или в виде взвешенного графа с матрицей весов W. Пример 1.1.3. Предположим, необходимо построить нечёткое отношение m : A ´ B ® [0,1] , которое описывает упрощённую схему поиска неисправности в автомобиле. С этой целью в качестве множества А рассмотрим множество предпосылок или причин неисправности {a1 , a 2 , a3 , a 4 } , к котором а1 – “неисправность аккумулятора”, а2 – “неисправность карбюратора”, а3 – “низкое качество бензина”, а4 – “неисправность системы зажигания”. В качестве множества В определим множество заключений или проявлений неисправности {b1 , b2 , b3 }, где b1 – “двигатель не запускается”, b2 – “двигатель работает неустойчиво”, b3 – “двигатель не развивает полной мощности”. При этом между каждым элементом множества предпосылок и каждым элементом множества следствий существует некоторая, вообще говоря неоднозначная, причинно-следственная связь. 11
Глава I. Неклассические логики Функция m , описывающая степень уверенности в том, что та или иная причина неисправности может привести к тому или иному следствию, определяется исходя из субъективного опыта механика, марки автомобиля, условий его эксплуатации и учёта других факторов. Нечёткое отношение m может быть записано, например, в виде следующего множества: {((a1 , b1 ),1), ((a1 , b2 ),0.1), ((a1 , b3 ),0.2), ((a 2 , b1 ),0.8), ((a 2 , b2 ),0.9), ((a 2 , b3 ),1), ((a3 , b1 ),0.7 ), ((a3 , b2 ),0.8), ((a3 , b3 ),0.5), ((a 4 , b1 ),1), ((a4 , b2 ),0.5), ((a 4 , b3 ),0.2 )} . Матрица весов для нечёткого отношения m имеет следующий вид: æ 1 0.1 0.2 ö ÷ ç ç 0.8 0.9 1 ÷ ç 0.7 0.8 0.5 ÷ . □ ÷ ç ç 1 0.5 0.2 ÷ ø è Вышеизложенные определения позволяют естественным образом проинтерпретировать классические логики (исчисления высказываний и предикатов) в виде нечётких логик. Более того, нечёткие логики являются обобщениями классических логик, придающими каждому высказыванию некоторую степень уверенности. За последние годы теория и практика, связанная с нечёткими логиками, получили весьма заметное развитие. Системы нечёткого вывода позволяют решать задачи автоматического управления, классификации данных, распознавания образов, принятия решений, машинного обучения и многие другие. Эта проблематика исследований тесно связана с целым рядом других научно-прикладных направлений, таких как: нечёткое моделирование, нечёткие экспертные системы, нечёткая ассоциативная память, нечёткие логические контроллеры, нечёткие регуляторы и нечёткие системы. Подробное изложение основ нечётких логик, а также моделирования на базе нечётких логик можно найти в книге [15].
1.1.4. Модальные логики Модальная логика – область логики, в которой наряду с обычными высказываниями рассматриваются модальные высказывания, т.е. высказывания, характеризующие степень достоверности суждений. Различают три типа модальностей, каждый из которых подразделяется на виды: – модальности общего вида: “необходимо”, “возможно”, “невозможно”, “случайно”; – модальности, связанные с характеристиками действий и поступками людей в обществе: “обязательно”, “разрешено”, “запрещено”, “безразлично” и др.; – модальности, являющиеся характеристиками знаний: “доказано”, “не доказано”, “опровергнуто”, “не опровергнуто”, “знает”, “верит”, “убеждён”, “сомневается”. Язык основных пропозициональных модальных логик получается добавлением к алфавиту исчисления высказываний новых одноместных связок (модальных операторов) □ (необходимо) и ◊ (возможно). В силу эквивалентности формул ◊ j и Ø □ Ø j в качестве исходного берётся один модальный оператор, например □, а другой выводится из аксиом ├◊ j ↔ Ø □ Ø j . Определим модальные исчисления I 0 и T , называемые исчислениями Фейса-фон Вригта. Исчисление I 0 получается из исчисления высказываний – введением символа □; – добавлением в определение формул фразы “если j – формула, то □ j – формула” (при этом формулы, содержащие модальный символ □, называются модальностями); – введением дополнительной схемы аксиомы □ (j ® y ) ├ (□φ→□ψ);
12
Потапов Д.К. Неклассические логики – введением дополнительного правила вывода (Г├φ)/(Г├□φ), называемого правилом Гёделя. Исчисление Т получается из исчисления I0 добавлением схемы аксиом □φ├φ. Следующее исчисление S4 образуется за счёт добавления к исчислению Т аксиомы □φ├□□φ. Если же к исчислению Т добавить аксиому Ø □φ├ □ Ø □φ, то получают исчисление S5. Наконец, исчисление Брауэра получается добавлением к исчислению Т следующей аксиомы Брауэра: φ├□◊φ. Можно показать, что все вышеприведённые модальные исчисления непротиворечивы. При рассмотрении предикатной модальной логики к модальным аксиомам добавляются аксиомы, описывающие действие модальных операторов на кванторы, например, так называемая аксиома Баркан: "x □φ├ □ "x φ. Специфика понятия истинности в модальных логиках позволяет вводить дополнительные аксиомы и правила вывода и изучать их выразительные возможности. Система модальной логики может быть проинтерпретирована в терминах многозначной логики (простейшая система – как трёхзначная: “истина”, “ложь”, “возможно”). Это обстоятельство, а также возможность применения модальной логики к построению теории “правдоподобных” выводов указывают на её глубокое родство с вероятностной логикой. Приведём некоторые семантические интерпретации пропозициональных модальных логик. Пусть дана формула j ( A1 , A2 ,..., An ) . m-означиванием формулы φ (где m>0) называется любая функция n v m (j ) : {0,1,..., m} ® {0,1,..., m}, которая по любым значениям переменных Аi из множества {0,1,..., m} выдаёт значения для формулы φ снова из множества {0,1,..., m}. При этом значению 0 соответствует истина. Функция vm (×) , которая ставит в соответствие каждой формуле φ исчисления I её mозначивание vm (j ) , называется m-означиванием исчисления I. Формула φ называется v m -общезначимой (обозначается ╞vmφ), если vm (j ) º 0 . Означивание v m называется характеристическим, если выполняются следующие условия: а) для любой формулы j ( A1 ,..., An ) исчисления высказываний функция vm (j ) | {0,1}n совпадает с истинностной функцией f Øj ; б) класс теорем исчисления I совпадает с классом v m -общезначимых формул. Очевидно, что m-означивание, задаваемое следующими соотношениями, удовлетворяет условию а) определения характеристического означивания: ìï0, если v m* (j ) = m, * v m (Øj ) = í ïîm, если v m* (j ) ¹ m; vm* (j Ù y ) = max( vm* (j ), v m* (y )); v m* (j Ú y ) = min( v m* (j ), v *m (y )); ìï0, если v m* (j ) ³ v m* (y ), v m* (j ® y ) = í * ïîv m (y ), если v m* (j ) < v m* (y ); ìï0, если v m* = 0, vm* ( □ j ) = í ïîm, если v m* ¹ 0; ìï0, если v m* (j ) ¹ m, vm* ( ◊ j ) = í ïîm, если v m* (j ) = m. 13
Глава I. Неклассические логики Теорема 1.1.3. В модальных исчислениях T, S4 и S5 любая доказуемая формула v m* общезначима. В исчислениях T, S4 и S5 нет характеристического означивания. □ Из приведённой выше теоремы вытекает, что исчисления T, S4 и S5 весьма существенно отличаются от классической логики и близки к логике интуиционистской. Среди различных семантических интерпретаций модальных логик важное место занимает семантика Крипке. Моделью Крипке называется система W , R, G, v , где: - W – фиксированное непустое множество, называемое множеством возможных миров; - R – рефлексивное бинарное отношение на множестве W, для которого условие ( w, w¢) Î R означает, что мир w¢ достижим из мира w ; - G Î W – фиксированный элемент, называемый действительным миром; - v – отображение Т-означивания или Т-оценивания, которое любой формуле j ( A1 ,..., An ) и любому миру w ставит в соответствие функцию v(j , w) : {0,1}n ® {0,1} , удовлетворяющую следующим условиям: v(Øj , w) = 1 Û v (j , w) = 0; v(j Ù y , w) = 1 Û v (j , w) = v (y , w) = 1; v(j Ú y , w) = 1 Û v(j , w) = 1 или v (y , w) = 1; v(j ® y , w) = 1 Û v(j , w) = 0 или v(y , w) = 1; v( □ j , w) = 1 Û v(j , w¢) = 1 для любого w¢ Î R({w}); v( ◊ j , w) = 1 Û v (j , w¢) = 1 для некоторого w¢ Î R({w}). По определению необходимость в модели Крипке означает истинность во всех возможных достижимых мирах, а возможность – истинность хотя бы в одном из достижимых миров. Таким образом, в моделях Крипке необходимость ведёт себя как всеобщность, а возможность – как существование. Т-означивание v называется В-означиванием (соответственно S4-означиванием, S5означиванием), если отношение R является симметричным (предпорядком, отношением эквивалентности). Множество формул Х называется I-выполнимым, где I Î {T , B, S4, S5} , если существует такое I-означивание v , что v(j , G ) = 1 для любой формулы j Î X . Множество формул, не являющееся I-выполнимым, называется I-невыполнимым. Формула j называется Iопровержимой (соответственно I-общезначимой), если множество {Øj} I-выполнимо (Iневыполнимо). Теорема 1.1.4. (теорема о непротиворечивости модальных исчислений). В модальных исчислениях T, S4 и S5 любая доказуемая формула соответственно T-, S4- и S5общезначима. □ Исчисление I называется полным по Крипке, если всякая не выводимая в I формула исчисления I I-опровержима. Теорема 1.1.5. (теорема о полноте модальных исчислений). Исчисления T и S4 полны по Крипке. □ Для предикатных модальных исчислений модели Крипке имеют вид W , R, G , D, m , v , где D = {Dw | w ÎW } , Dw – носитель мира w , m – интерпретация предикатных символов в D , v – означивание, определяющее истинность формул на элементах
UD
w
. При этом для
wÎW
исчислений, содержащих аксиому Баркан, требуется выполнение импликации ( w, w¢) Î R Þ Dw¢ Í Dw . Символы □ и ◊ могут пониматься иначе, чем “необходимость” и “возможность”. Например, допускаются следующие интерпретации: 14
Потапов Д.К. Неклассические логики - □ – “обязательность”, а ◊ – “позволение”; - □ – “доказуемость”, а ◊ – “непротиворечивость”; - □ – “везде” или “всегда”, а ◊ – “кое-где” или “иногда”; Последние модальности называются пространственно-временными и рассматриваются в следующем пункте.
1.1.5. Временные (темпоральные) логики Временные или темпоральные логики – это модальные логики, которые получаются добавлением к логике высказываний новых символов, отражающих свойства времени. Рассмотрение реального процесса во времени заставляет отступиться от двузначной логики. Например, между периодом, когда идёт дождь, и периодом, когда дождь прекратился, имеется промежуточное состояние, когда количество капель слишком мало, для того чтобы сказать, что идёт дождь, но слишком велико, чтобы утверждать, что дождь уже закончился. Таким образом, появляется третье значение высказывания: “ни истинно, ни ложно”. Временная логика Прайора – это логика будущего. Она содержит новый символ F, который называется символом будущего, и новый символ G. При этом для любой формулы j формула Fj интерпретируется как “будет j ”, а формула Gj читается как “всегда будет j ” и связана с формулой Fj следующей аксиомой: ├ Gj « ØFØj . Кроме того, к исчислению высказываний добавляются схемы аксиом F (j Ú y ) º Fj Ú Fy , F Fj ├ Fj и дополнительные правила вывода. Возможность и необходимость определяются через символы F и G следующими соотношениями: ◊ j = j Ú Fj , □ j = j Ù Gj . Прайор показал, что полученное модальное исчисление, содержащееся во временной логике, сильнее исчисления S4, но слабее S5. Леммон предложил минимальную временную логику, основанную на модальностях Р – “было” и F – “будет”. Предложенное им исчисление добавляет к исчислению высказываний аксиомы ØFØ(j ® y ) ├ ( Fj ® Fy ), FØPØj ├ j , ØPØ(j ® y ) ├ ( Pj ® Py ) , PØFØj ├ j и дополнительные правила вывода. Данная логика не делает никаких предположений о природе времени: его бесконечности в прошлом или будущем, непрерывности или неразветвлённости. Во временной логике фон Вригта к исчислению высказываний добавляется бинарная связка T , позволяющая по формулам j и y строить формулу (jTy ) , которая читается как “сейчас происходит событие j , а затем, т.е. в следующий момент времени, происходит событие y ”. С помощью формул (j1T (j 2T (j 3T ...y ...))) , в которых формулы j1 ,...,j n являются описаниями состояний, описывается история мира. При этом любая такая формула называется фрагментом истории. Термин “история” имеет двойственное значение: он может означать последовательность как самих полных описаний мира, так и их описаний. К исчислению высказываний добавляются аксиомы ((j1 Ú j 2 )T (y 1 Ú y 2 )) º (j1Ty 1 ) Ú (j1Ty 2 ) Ú (j 2Ty 1 ) Ú (j 2Ty 2 ) , (jTy ) Ù (jTc ) ├ (jT (y Ù c )) , j º (jT (y Ú Øy )) , ├ Ø(jT (y Ù Øy )) и дополнительное правило вывода. Время в этой темпоральной логике дискретно и линейно упорядочено. Если число полных состояний мира равно 2 n , то число возможных историй в m последующих моментах равно 2 mn . 15
Глава I. Неклассические логики
1.2. Предикатные логики 1.2.1. Многосортные логики первого порядка Двусортная логика первого порядка очень похожа на обычную логику первого порядка (логику предикатов), за исключение того, что имеется два сорта переменных. Пример 1.2.1. 1. Аксиомы линейного пространства можно естественным образом записать, имея один сорт переменных u , v, w,... для векторов, а другой сорт a , b , g ,... – для скаляров (элементов поля). Таким образом, линейное пространство состоит из тройки D, F, × , где F = F ; + F , ×F , 0,1 – поле, а D = V ; +; 0 – векторная система с операцией сложения векторов и выделенным нулевым вектором, × – умножение на скаляр. 2. При изучении групп нередко рассматривается класс групп U = A; × ; e , в которых все элементы а имеют конечный порядок, т.е. такое наименьшее натуральное число n > 0 , что a n = e . Условие конечности порядков всех элементов выражается формулой "x $n ³ 1 ( x n » e) , которая не является формулой исчисления предикатов. Более того, в силу неограниченности конечных порядков по теореме компактности формулы исчисления предикатов, описывающей класс групп, у которых все элементы имеют конечные порядки, не существует вовсе. С другой стороны, введение двусортных систем U, N, (×)× (где N = N; £ , (×) × – операция возведения элементов группы U в натуральные степени), а также квантора "1 для элементов системы U и квантора $2 для элементов системы N позволяют записать искомую формулу в виде "1 x$2 n((n ³ 1) Ù ( x n » e)) . □ В общем случае двусортная или двуосновная алгебраическая система U, B, å состоит из двух обычных алгебраических систем U и B , а также некоторых операций и отношений на их объединении, соответствующих символам сигнатуры å . Двусортная (или многосортная) логика только внешне сильнее (хотя часто более естественна, чем обычная логика), поскольку любую двусортную систему U, B, å можно превратить в обычную систему A U B; A, B,... с одноместными предикатами A и B для выделения различных сортов элементов. Это сведение позволяет перенести многие результаты логики первого порядка на многосортную логику, предоставляющую известное удобство для работы. При рассмотрении двусортных систем U, B, å с фиксированной системой B получается так называемая B -логика. Например, R -логика удобна при изучении евклидовых пространств, поскольку поле скаляров R фиксировано. Если система B бесконечна, то B логика сильнее логики первого порядка. В частности, для B -логики неверна теорема компактности.
1.2.2. Слабая логика второго порядка Слабая логика второго порядка – это логика, в которой некоторым естественным образом строится понятие конечного. Пусть дана некоторая сигнатура å, x, y, z ,... – переменные, из которых строятся формулы сигнатуры å . Расширим сигнатуру å до сигнатуры å * введением нового предикатного символа принадлежности Îи добавим к старому списку новые переменные a, b, c,... . Таким образом получается двусортный алфавит å U{x, y, z ,...},{Î} U {a, b, c,...} . Данную алгебраическую систему U = A; å
16
расширим до
Потапов Д.К. Неклассические логики системы наследственно конечных множеств HF(U) = U, HF( A);Î| ( A U HF( A)) над U в соответствии со следующей схемой: HF0 ( A) = Æ , HFn +1 ( A) = { X | X – конечное подмножество A U HFn ( A)} , HF( A) = U HFn ( A) . nÎw
Элементы множества HF( A) называют допустимыми множествами над A . Очевидно, что любое натуральное число, а также любая конечная последовательность натуральных чисел являются допустимым множеством над любым множеством A . В слабой логике второго порядка разрешается использовать формулы сигнатуры å * , в которых переменные a, b, c,... интерпретируются множествами из HF( A) . Слабая логика второго порядка имеет ту же силу, что и w ; £ -логика, но значительно более естественна в алгебраическом контексте, поскольку позволяет непосредственно работать с целыми числами, конечными множествами, конечными последовательностями и т.д.
1.2.3. Бесконечные логики Слабая логика второго порядка позволяет определить понятие конечного в семантике логики. Бесконечные логики, напротив, вводят в синтаксис бесконечные конструкции, подобные бесконечной формуле "x (( x » 0) Ú (2 x » 0) Ú ...). Логика Lw1w допускает дополнительно следующее правило образования: если F « {j n | n Î w} – счётное множество формул, то Ù F « Ù j n (конъюнкция F ) и nÎw
Ú F « Ú j n (дизъюнкция F ) являются формулами. Обозначение логики Lw1w объясняется nÎw
тем, что в ней допустимы счетные ( < w1 ) конъюнкции и дизъюнкции и только конечное число ( < w ) кванторов. Логика Lw1w позволяет выражать те понятия, которые выразимы в логике первого порядка по модулю счётного количества информации. Пример 1.2.2. Рассмотрим некоторый тип p( x) Î D (T ) , состоящий из формул счётной сигнатуры å . Если p(x) – главный тип, то он определяется лишь счётным множеством формул F ( x) = {j n ( x) | n Î w} . Переходя к логике Lw1w , получаем, что тип p(x) определяется уже формулой Ù F (x ) . □ Для Lw1w верна теорема Лёвенгейма-Скулема, а теорема компактности неверна. Для справедливости теоремы о полноте для счётных теорий T нужно добавить бесконечное правило вывода.
1.2.4. Логика с новыми кванторами Рассмотрим исчисление предикатов некоторой сигнатуры å . Пусть Q – новый символ. Добавим к правилам образования формул следующее: если j – формула, то Qxj также является формулой. Существует много различных интерпретаций для Q . Например, можно определить, что U ╞ Qxj ( x) тогда и только тогда, когда существует бесконечно много элементов a , для которых U ╞ j (a) (формула j истинна на элементе a в системе U ). Эта логика, обозначаемая через L(Q 0 ) , эквивалентна слабой логике второго порядка. Если определить, что U ╞ Qxj ( x) тогда и только тогда, когда существует несчётно много элементов a , для которых U ╞ j (a) , то получается логика с квантором “существует несчётно много”. В этой логике, обозначаемой через L(Q) , справедлива и теорема компактности, и теорема о полноте, но неверна теорема Лёвенгейма-Скулема. При этом понятие 17
Глава I. Неклассические логики “существует несчётно много” обеспечивает математически точную модель для неформального понятия “много”. Используя терминологию “много” и “мало” для “несчётности” и “ненесчётности” соответственно, при формализации можно ввести следующие аксиомы Кейслера: 1) ├ "yØQx ( x » y ) (для любого y существует мало x , для которых x = y ); 2) "x (j ® y ), Qxj ├ Qxy (если j ® y для всех x и имеется много x , удовлетворяющих j , то много x удовлетворяют y ); 3) Qx(j Ú y ) ├ Qxj Ú Qxy (если много x удовлетворяют j Ú y , то много x удовлетворяют j или много x удовлетворяют y ); 4) ØQx$yj , "xØQyj ├ ØQy$xj (если существует мало x , для которых $yj ( x, y ) , и если для каждого x существует мало y , для которых j ( x, y ) , то существует мало y , для которых $xj ( x, y ) ). Особая роль логики первого порядка среди всех логик объясняется следующей теоремой. Теорема 1.2.1. (теорема Линдстрёма). Логика первого порядка является единственной логикой, замкнутой относительно Ù, Ø, $ и удовлетворяющей теоремам компактности и Лёвенгейма-Скулема. □
1.3. Предикатные временные логики и их приложение к программированию Временные логики используются в программировании для описания и верификации программ. При этом описание программы состоит в выражении с помощью языка временной логики свойств программы, характеризующих её правильное вычислительное поведение, а её верификация – в использовании аппарата временного исчисления для доказательства того, что данная программа обладает интересующим свойством. Программы рассматриваются как объекты, выраженные на формальном языке, обладающие определённой информационной и логической структурой и подлежащие исполнению на автоматических устройствах. Исследование программ проводится преимущественно на основе двух моделей вычислений: последовательных программ с памятью, или операторных программ, и рекурсивных программ. При этом обе модели строятся над некоторой абстрактной алгебраической структурой U конечной сигнатуры å . Определение класса программ слагается из трёх частей: схемы программы (синтаксиса), интерпретации и семантики. Схема программы – это конструктивный объект, показывающий, как строится программа с использованием сигнатурных символов. Интерпретация – это задание конкретного носителя и сопоставление символам сигнатуры конкретных операций и отношений на носителе. Семантика – это способ сопоставления каждой программе результата её выполнения. Как правило, с программами связывают вычисляемые ими функции. Интерпретация обычно входит в семантику как параметр, поэтому схема программы задаёт множество программ и вычисляемых ими функций, которое получается при варьировании интерпретаций над некоторым запасом базовых операций. Схема программы с памятью, или операторная схема задаётся в виде конечного ориентированного графа переходов, имеющего обычно одну входную и одну выходную вершины, вершины с одной (преобразователи) и двумя (распознаватели) исходящими дугами. С помощью символов сигнатуры å , включающего константные символы, и счётного множества символов переменных обычным образом строятся множество T (å) функциональных термов и множество PT (å) предикатных термов, состоящее из термов c P (t1 ,..., t n ) (где t1 ,..., t n ÎT (å) ) от характеристических функций ìï1, если x Î P, c P ( x) = í ïî0 , если x Ï P. 18
Потапов Д.К. Неклассические логики Каждому распознавателю сопоставляется некоторый предикатный терм, а преобразователю – оператор присваивания, имеющий вид x := t , где x – символ переменной, а t – функциональный терм. Конечная совокупность ( x1 ,..., xk ) всех переменных в схеме образует её память. Интерпретация в дополнение к конкретизации базовых операций предписывает каждой переменной область её изменения. Для программ с памятью наиболее обычна так называемая операционная семантика, состоящая из алгоритма выполнения программы на заданном состоянии памяти. Программа выполняется при движении по графу переходов. При попадании на распознаватель вычисляется предикатный терм и происходит переход по дуге, соответствующей значению характеристической функции. При попадании на преобразователь с оператором x := t вычисляется значение t и присваивается переменной x . Результат выполнения программы – состояние памяти при попадании на выходную вершину. Схема рекурсивной программы, или рекурсивная схема, использует кроме функциональных так называемые условные термы, образующие вместе с первым множество вычислительных термов. Условный терм задаёт вычисление посредством разбора случаев, имеет вид (p | t1 | t 2 ) , где p – предикатный, а t1 и t 2 – вычислительные термы, и соответствует конструкции условного выражения: if p then t1 else t 2 . Рекурсивная схема состоит из главного вычислительного терма с входными переменными и конечного набора рекурсивных уравнений вида f ( x1 ,..., xn ) = t , где f – символ, определяемой функции, x1 ,..., xn - переменные, t - терм с переменными из множества {x1 ,..., xn } и с символами определяемых функций из набора уравнений. При естественных предположениях на интерпретацию базовых операций система уравнений относительно определяемых функций всегда имеет так называемую наименьшую неподвижную точку – совокупность функций, удовлетворяющих уравнениям, с графиками, содержащимися в графиках любых других решений уравнений. Подставляя в главный терм вместо символов определяемых функций соответствующие компоненты наименьшей неподвижной точки, получают функциональный терм, задающий некоторую функцию входных переменных, которая и объявляется функцией, вычисляемой рекурсивной программой. Пусть П – программа, j - формула, относящаяся к входным данным, которая должна быть истинна перед выполнением программы П, y - формула, которая должна быть истинна после выполнения программы П. Формула j называется предусловием, а y - постусловием П. Программа П называется частично правильной относительно j и y , если всякий раз, когда предусловие j истинно перед выполнением П и П заканчивает работу, постусловие y будет также истинно. В этом случае используется запись {j }П{y } . Программа П называется тотально правильной относительно j и y , если она частично правильна относительно j и y , и обязательно завершает работу, если j истинна (т.е. исполнение П обязательно завершается и y истинна в любом состоянии памяти компьютера, которое может получиться при выполнении П; последнее условие на y соответствует □y в модальной логике). В этом случае используется запись {j }П ¯ {y } . Предусловие j и постусловие y вязаны с конкретной задачей, которую требуется решить и для решения которой написана программа П. Нам требуется доказать, что она правильна. С целью верификации компьютерных программ создана темпоральная логика Пнуели, позволяющая доказывать наличие у данной программы свойств, характеризующих её правильное вычислительное поведение. При этом понятие внешнего времени, или темпоральности, существенно лишь для верификации программ, связанных с параллельными вычислениями, поскольку в последовательных программах имеются “внутренние часы”, а именно 19
Глава I. Неклассические логики само выполнение. Зная метку в последовательной программе, а также значения программных переменных, можно точно определить, в каком месте программы находится процесс вычисления. При обращении же к недетерминированным, параллельным программам, в которых выполнение состоит из перемешанных между собой операций из различных процессов, требуется различать “где” и “когда” и сохранять внешнюю временную шкалу, независимую от выполнения. Таким образом, логика Пнуели предназначена для верификации программ, связанных с параллельными вычислениями. Временная логика Пнуели строится как логика первого порядка с добавлением одноместного предиката L(x) , выделяющего множество меток l , в которых могут находиться вычислительные процессы. Отношение L даёт средства для описания контрольного компонента программных состояний. Кроме того, логика Пнуели содержит дополнительные символы F (когда-нибудь будет), G (всегда будет) и À (в следующий момент будет), следующие аксиомы: G (j ® y ) ├ (Gj ® Gy ) , À(j ® y ) ├ (Àj ® Ày ) , Gj ├ j , Gj ├ ÀGj , Gj ├ Àj , ├ ÀØj « ØÀj , j , G (j ® Àj ) ├ Gj , а также правила вывода. Γ├φ , Γ, ψ├φ; Γ├"x(L(x)Ùψ®Àφ) . Γ├Gφ Γ, ψ├Gφ Последнее правило называется инвариантным правилом, согласно которому для установления инвариантности (неизменности) свойства j в данной программе нужно установить, что это свойство имеет место в начале программы и сохраняется после выполнения каждой команды этой программы. С помощью инвариантного правила доказывается следующее свойство исключения критических связей: j ├ GØ( L(l1 ) Ù ... Ù L(l n )) , где j - формула, выражающая исходные условия программы (и включающая значения программных переменных, предусловие и исходные метки всех параллельных процессов), li метка критической секции i -го процесса. Расшифруем понятие критической секции. В параллельных вычислениях параллельные процессы могут включать блоки (секции), содержащие команды, критические для кооперирования этих процессов. Иначе говоря, пока один процесс находится в своей критической секции и выполняет команды этой секции, второй процесс не должен входить в свою критическую секцию, поскольку изменения в ячейках памяти, происходящие при выполнении команд идущего первого процесса, могут исказить вычисления, на которые сориентирован второй процесс. Второй процесс должен ждать (и для этого требуется понятие “внешнего времени”), пока содержимое используемых ячеек не окажется требуемым. Ожидание происходит в силу выполнения специальных команд программы, называемых семафорными инструкциями. Пример 1.3.1. Рассмотрим параллельную программу с двумя критическими секциями КС1 и КС2. Семафорная инструкция – оператор “wait … then …” с семафорной переменной x1 , которой изначально присваивается значение 1:
20
Потапов Д.К. Неклассические логики
КС1
процесс 1 l0 : wait x1 > 0 then x1 := x1 - 1; l1 : t1 := x3 * x 4 ; l 2 : x3 := t1 ; l3 : x1 := x1 + 1;
КС2
l 4 : end
процесс 2 m0 : wait x1 > 0 then x1 := x1 - 1; m1 : t 2 := x3 / x 2 ; m2 : x 2 := t 2 ; m3 : x1 := x1 + 1; m4 : end
Предположим, что при выполнении процесса 1 значение x1 уменьшилось до 0. Тогда компьютер вынужден остановить процесс 2, поскольку преградой к его выполнению является семафорная инструкция под меткой m0 , для выполнения которой необходимо, чтобы x1 было больше 0. Следовательно, компьютер начнёт выполнять команды с метками l1 , l 2 , l3 и только после этого перейдет к продолжению выполнения процесса 2. Другими словами, пока процесс 1 находится в своей критической секции КС1, процесс 2 не достигнет своей критической секции КС2. То же самое будет происходить в случае, когда процесс 2 начнёт выполняться первым. □
1.4. Алгоритмические логики Алгоритмические логики создаются с целью описания семантики языков программирования и включают формулы вида {j }S{y } , читающиеся как “если до выполнения оператора S было истинно j , то после его выполнения будет истинно y ”. Эти логики были изобретены Р.У. Флойдом (1967 г.), Ч. Хоаром (1969 г.) и представителями польской логической школы (А. Сальвиницкий и др. (1970 г.)). Хоар определил простой язык программирования через логическую систему аксиом и правил вывода для доказательства частичной правильности программ. Им показано, что определение семантики языка не в терминах выполнения программы, а в терминах доказательства её правильности упрощает процесс построения программы. На базе работы Хоара проводились исследования в области аксиоматических определений языков программирования. Появилось много работ по аксиоматизации различных конструкций: от оператора присваивания до различных форм циклов, от вызова процедур до сопрограмм. В 1973 г. были сформулированы правила доказательства правильности для большинства конструкций языка Паскаль. В 1975 г. была построена автоматическая система верификации для языка Паскаль, основанная на аксиомах и правилах вывода. В 1979 г. был определён язык программирования Евклид, в проект которого с самого начала была заложена идея аксиоматизации. В 1976 г. Э. Дейкстра предложил метод доказательства правильности программ. Суть метода заключается в том, чтобы строить программу вместе с доказательством, причём доказательство должно опережать построение программы. Дейкстра определил для простого языка программирования слабейшие предусловия и показал, как их можно использовать в качестве исчисления для вывода программ. Стало ясно, что использование формализма может привести к построению программ более надёжным способом. Опишем принципы построения алгоритмической логики L 0 . Память в L 0 разделена на ячейки. Каждая ячейка имеет идентификатор, представляющий собой слово из латинских букв и цифр и начинающийся с буквы. Ячейки содержат натуральные числа. Программа в L 0 состоит из операторов. Исходный оператор – оператор присваивания x := t , где x - идентификатор, а t - терм сигнатуры å = {+ ( 2) , × котором в качестве переменных используются идентификаторы. 21
( 2)
, £ ( 2) } U {n ( 0) | n Î w } , в
Глава I. Неклассические логики Пусть j - формула сигнатуры å 0 , истинная на состоянии памяти после присваивания, (j ) tx - формула, истинная до присваивания. Тогда по оператору присваивания строится формула {(j ) tx }x := t{j } . Пример 1.4.1. Если формула j равна ( x < 2 ) и t = x + 1 , то формула (j ) tx равна ( x + 1 < 2 ). Следовательно, чтобы после присваивания x := x + 1 стало истинным ( x < 2 ), требуется, чтобы до присваивания выполнялось неравенство т.е. x +1 < 2 , ╞ {( x + 1 < 2)}x := x + 1{( x < 2)} . □ Пусть два оператора S1 и S 2 выполняются один за другим. Тогда композиции S1 S 2 операторов S1 и S 2 соответствует правило вывода {j }S1{y }; {c }S 2 {q }; y ® c . {j }S1S 2 {q } Условный оператор – это конструкция IF j1 ® S1 D j 2 ® S 2 D ... D j n ® S n FI , где j1 ,...,j n – бескванторные формулы сигнатуры å 0 , а S1 ,..., S n – последовательности операторов. При работе условного оператора проверяются формулы j i при текущем состоянии памяти. Если ни одна из формул j i не истинна, то фиксируется ошибка. Если же некоторые j i истинны, то по некоторым приоритетам выбирается одна из них и выполняется соответствующая последовательность операторов S i . Если каждая из команд S i описана в логике L 0 формулой y i S i c , то условный оператор описывается формулой {(j1 ® y 1 ) Ù ... Ù (j n ® y n )}IF j 1 ® S1 D j 2 ® S 2 D ... D j n ® S n FI {c } . Операторам цикла соответствуют конструкции DO j1 ® S1 D ... D j n ® S n OUT y 1 ® T1 D ... D y m ® Tm OD . Выполняется оператор цикла следующим образом. Проверяются формулы j1 , ... ,j n , y 1 , ... ,y m при текущем состоянии памяти. Если ни одна из них не истинна, то фиксируется ошибка. Если же некоторые истинны, то по некоторым приоритетам выбирается одна из них. Если выбрана j i , то выполняется соответствующая последовательность операторов S i и выполнение цикла возобновляется. Если выбрана y j , то выполняется соответствующая последовательность операторов T j и выполнение цикла завершается. Если каждая из команд S i описана в логике L 0 формулой {j i¢}S i {c i } , а T j – формулой {y ¢j }T j {q } , то однократное выполнение цикла описывается формулой {(j1 ® j1¢ ) Ù ... Ù (j n ® j n¢ ) Ù (y 1 ® y 1¢ ) Ù ... Ù (y 1 ® y 1¢ ) Ù (j1 Ú ... Ú j n Ú y 1 Ú ... Ú y m )} IF j1 ® S1 D ... D j n ® S n D y 1 ® T1 D ... D y m ® Tm FI{q }. Двукратное выполнение цикла соответствует формуле {(j1 ® j1¢ ) Ù ... Ù (j n ® j n¢ ) Ù (y 1 ® y 1¢ ) Ù ... Ù (y 1 ® y 1¢ ) Ù (j1 Ú ... Ú j n Ú y 1 Ú ... Ú y m )} IF j1 ® S1 D ... D j n ® S n D y 1 ® T1 D ... D y m ® Tm FI{c 1 Ú ... Ú c n } {(j1 ® j1¢ ) Ù ... Ù (j n ® j n¢ ) Ù (y 1 ® y 1¢ ) Ù ... Ù (y 1 ® y 1¢ ) Ù (j1 Ú ... Ú j n Ú y 1 Ú ... Ú y m ) Ù ( c 1 Ú ... Ú c n )}IFj 1 ® S1 D ...D j n ® S n D y 1 ® T1 D ... D y m ® Tm FI{q } и т.д. до бесконечности. Обозначив через DO k {q } условие правильности k шагов цикла, получаем, что корректность цикла равносильна истинности формулы Ù DO k {q } . Но эта kÎw \{0}
формула имеет бесконечную длину и не является формулой логики L 0 . Появление таких 22
Потапов Д.К. Неклассические логики формул, относящихся к логике Lw1w , порождает серьёзные проблемы для алгоритмических логик. Опишем алгоритмическую логику Хоара, которая является основой для логики выводов правильных программ и допускает интерпретации в терминах программных конструкций. Следующие аксиомы, называемые аксиомами Хоара или правилами верификации, определяют предусловия как достаточные условия, гарантирующие, что исполнение соответствующего оператора при успешном завершении приведёт к желательным постусловиям. А1. {(j ) tx }x := t{j } (аксиома присваивания). А2. {j }S{y } Ù (y ® c ) ® {j }S{c } (аксиома ослабления постусловия). А3. {j }S{y } Ù ( c ® j ) ® {c }S{y } (аксиома усиления предусловия). А4. {j }S1 {y } Ù {y }S 2 {c } ® {j }S1 S 2 {c } (аксиома композиции). А5. {j Ù y }S{c } Ù (j Ù Øy ® c ) ® {j } if y then S{c } (аксиома условного оператора). А6. ({j Ù y }S1{c }) Ù ({j Ù Øy }S 2 {c }) ® {j } if y then S1 else S 2 {c } (аксиома альтернативного оператора). А7. {j Ù y }S{j } ® {j }repeat S untily {j Ù Øy } (аксиома оператора цикла until (до)). А8. {j Ù y }S{j } ® {j } while y do S{j Ù Øy } (аксиома оператора цикла while (пока)). В аксиомах А7 и А8 утверждается, что формула j истинна перед выполнением и после выполнения каждого шага цикла. Эта формула называется инвариантной формулой или инвариантом цикла. Аксиомы А1–А8 можно использовать для проверки согласованности передачи данных от оператора к оператору, для анализа структурных свойств текстов программ, для установления условий окончания цикла. Кроме того, аксиомы можно использовать для анализа результатов выполнения программы. Пример 1.4.2. Рассмотрим задачу нахождения частного q и остатка r от деления n на m . Входные данные: n, m - натуральные числа, где m > 0 . Выходные данные: q, r - натуральные числа. Описание программы S: задать (n, m) r := n; q := 0; while m £ r do begin r := r - m; q := q + 1 end; выдать (q, r ). Сформулируем предусловие j : m > 0.
Сформулируем постусловие y :
( r < m) Ù ( n » m × q + r ) . Требуется доказать, что или
╞ {j }S{y } ╞ {m > 0}S{(r < m) Ù (n » m × q + r )} . 23
Глава I. Неклассические логики Доказательство. є 1 2 3 4 5 6 7 8 9 10 11 12
Формулы
Аксиомы и правила вывода в формальной арифметике аксиома А1 аксиома А1 А3 к пунктам 1 и 2 А4 к пунктам 3 и 4 арифметика аксиома А1 аксиома А1 А4 к пунктам 7 и 8 А2 к пунктам 6 и 9 А8 к пункту 10
j ® (n » n + m × 0) {(n » n + m × 0)}r := n{( n » r + m × 0)} {(n » n + m × 0)}q := 0{(n » r + m × q)} {j }r := n{(n » r + m × 0)} {j }r := n; q := 0{( n » r + m × q)} (n » r + m × q) Ù (m £ r ) ® (n » (r - m) + m × (q + 1)) {(n » (r - m) + m × (q + 1))}r := r - m{(n » r + m × (q + 1))} {(n » r + m × (q + 1))}q := q + 1{(n » r + m × q )} {(n » (r - m) + m × (q + 1))}r := r - m; q := q + 1{( n » r + m × q )} {(n » r + m × q ) Ù (m £ r )}r := r - m; q := q + 1{(n » r + m × q)} {(n » r + m × q ) Ù (m £ r )} while m £ r do begin r := r - m; q := q + 1 end {(n » r + m × q ) Ù Ø(m £ r )} А4 к пунктам 5 и 11 {j }S{(n » r + m × q ) Ù Ø(m £ r )}
В силу того, что система N; £ является вполне упорядоченным множеством и на каждом шаге значение r уменьшается на положительную величину r , найдётся такое значение r , для которого не будет выполняться условие m £ r , и циклический процесс завершится. Таким образом, установлено, что {j }S ¯ {y } , т.е. программа S является тотально правильной. □
1.5. Задачи и упражнения 1. Доказать, что (а) все выводимые в интуиционистском исчислении высказываний формулы выводимы в исчислении высказываний; (б) формулы (ØØj ® j ) и j Ú Øj не выводимы в интуиционистском исчислении высказываний; (в) если в интуиционистском исчислении высказываний доказуемо Г, j ├y , то в интуиционистском исчислении высказываний доказуемо Г├ (j ® y ) . 2. Показать, что система функций, состоящая из функции x Ú y и всех функций ì j, если x = i, является полной в k - значной логике. eij ( x ) = í 0 , если x ¹ i , î 3. Доказать, что для любых событий j ,y ,j1 ,...,j n справедливы следующие соотношения: (а) P(j Ù y ) £ P(j ); (б) P(j Ù y ) ³ P(j ) + P(y ) - 1 ; (в) P(j 1 Ú ... Ú j n ) £ P(j 1 ) + ... + P(j n ) ; (г) если события j1 ,...,j n попарно несовместны, то P(j 1 Ú ... Ú j n ) = P(j1 ) + ... + P(j n ) . 4. Для нечётких подмножеств A = {( x,0.3), ( y,0.9), ( z ,1)} и B = {( x,0.7), ( y ,0), ( z ,0.1)} найти A, B, A Ù A, B Ú B, A Ù B, A Ú B . 24
Потапов Д.К. Неклассические логики 5. Доказать следующие секвенции: (а) j ├ ◊ j ; (б) ◊ $xØj ├ $xØ □ j . 6. Представить алгебру матриц в виде многосортной алгебраической системы, для которой соответствующей формулой многосортной логики выразимо множество матриц, имеющих конечный порядок. 7. Написать программу разложения натурального числа на простые сомножители и доказать её тотальную правильность с помощью алгоритмической логики Хоара.
25
Глава II. Нечёткая информация и выводы
Глава II. Нечёткая информация и выводы Пожалуй, наиболее поразительным свойством человеческого интеллекта является способность принимать правильные решения в обстановке неполной и нечёткой информации. Построение моделей приближённых рассуждений человека и использование их в компьютерных системах будущих поколений представляет сегодня одну из важнейших проблем науки. Значительное продвижение в этом направлении сделано 30 лет тому назад профессором Калифорнийского университета (Беркли) Лотфи А. Заде (Lotfi A. Zadeh). Его работа «Fuzzy Sets», появившаяся в 1965 г. в журнале Information and Control, № 8, заложила основы моделирования интеллектуальной деятельности человека и явилась начальным толчком к развитию новой математической теории. Л. Заде расширил классическое канторовское понятие множества, допустив, что характеристическая функция (функция принадлежности элемента множеству) может принимать любые значения в интервале [0;1], а не только значения 0 либо 1. Такие множества были названы им нечёткими (fuzzy). Он определил также ряд операций над нечёткими множествами и предложил обобщение известных методов логического вывода modus ponens и modus tollens. Введя затем понятие лингвистической переменной и допустив, что в качестве её значений (термов) выступают нечёткие множества, Л. Заде создал аппарат для описания процессов интеллектуальной деятельности, включая нечёткость и неопределённость выражений. Дальнейшие работы профессора Л. Заде и его последователей заложили прочный фундамент новой теории и создали предпосылки для внедрения методов нечёткого управления в инженерную практику. Уже к 1990 г. по этой проблематике опубликовано свыше 10000 работ, а число исследователей достигло 10000, причём в США, Европе и СССР по 200-300 человек, около 1000 – в Японии, 2000-3000 – в Индии и около 5000 исследователей в Китае. В последние 5-7 лет началось использование новых методов и моделей в промышленности и в военном деле. Спектр приложений их широк: от управления процессом отправления и остановки поезда метрополитена, управления грузовыми лифтами и доменной печью до стиральных машин, пылесосов и СВЧ-печей. При этом нечёткие системы позволяют повысить качество продукции при уменьшении ресурсо- и энергозатрат и обеспечивают более высокую устойчивость к воздействию мешающих факторов по сравнению с традиционными системами автоматического управления. Другими словами, новые подходы позволяют расширить сферу приложения систем автоматизации за пределы применимости классической теории. В этом плане любопытна точка зрения Л. Заде: «Я считаю, что излишнее стремление к точности стало оказывать действие, сводящее на нет теорию управления и теорию систем, так как оно приводит к тому, что исследования в этой области сосредоточиваются на тех и только тех проблемах, которые поддаются точному решению. В результате многие классы важных проблем, в которых данные, цели и ограничения являются слишком сложными или плохо определёнными для того, чтобы допустить точный математический анализ, оставались и остаются в стороне по той причине, что они не поддаются математической трактовке. Для того чтобы сказать что-либо существенное для проблем подобного рода, мы должны отказаться от наших требований точности и допустить результаты, которые являются несколько размытыми или неопределёнными». Смещение центра исследований нечётких систем в сторону практических приложений привело к постановке целого ряда проблем, таких как новые архитектуры компьютеров для нечётких вычислений, элементная база нечётких компьютеров и контроллеров, инструментальные средства разработки, инженерные методы расчёта и разработки нечётких систем управления и многое другое. 26
Потапов Д.К. Неклассические логики Математическая теория нечётких множеств позволяет описывать нечёткие понятия и знания, оперировать этими знаниями и делать нечёткие выводы. Нечёткое управление оказывается особенно полезным, когда технологические процессы являются слишком сложными для анализа с помощью общепринятых количественных методов или когда доступные источники информации интерпретируются качественно, неточно или неопределённо. Нечёткая логика, на которой основано нечёткое управление, ближе по духу к человеческому мышлению и естественным языкам, чем традиционные логические системы. Нечёткая логика, в основном, обеспечивает эффективные средства отображения неопределённостей и неточностей реального мира. Наличие математических средств отражения нечёткости исходной информации позволяет построить модель, адекватную реальности. Вспомните прогноз погоды на любом из телевизионных каналов: завтра температура воздуха +5o C, возможен дождь. В этом случае даже профессиональные синоптики не могут точно сказать будет дождь или нет. Это и есть проявление нечёткой логики: погода завтра может быть в данном случае как просто пасмурной, так и дождливой: события здесь предсказываются с некоторой долей уверенности (рангом). Рассмотрим теперь другой пример, связанный с возрастом человека. До 15 лет нельзя однозначно утверждать, что человек молодой (например, 14-летие относится к термину молодой с рангом около 0,9). Зато диапазону от 15 до 35 лет можно смело присвоить ранг 1, т.е. человек в этом возрасте молодой. После 35 лет человек вроде уже не молодой, но ещё и не старый, здесь принадлежность (ранг) термина молодой возрасту будет принимать значения в интервале от 0 до 1. И чем больше возраст человека, тем меньше становится его принадлежность к молодым, т.е. ранг будет стремиться к нулю.
1
10 15 35 50 лет Нечёткое множество для термина молодой Рассуждая таким образом, было получено нечёткое множество, описывающее понятие молодости для всего диапазона возрастов человека. Если ввести остальные термины (например, очень молодой, старый и т.д.), то можно охарактеризовать такую переменную как возраст, состоящую из нескольких нечётких множеств и полностью перекрывающую весь жизненный период.
2.1. Нечёткие множества Пусть Е – универсальное множество, x – элемент Е, а R – некоторое свойство. Обычное (чёткое) подмножество А универсального множества Е, элементы которого удовлетворяют свойству R, определяется как множество упорядоченных пар A = {m A ( x) / x}, где m A (x) – характеристическая функция, принимающая значение 1, если x удовлетворяет свойству R, и 0 – в противном случае. Нечёткое подмножество отличается от обычного тем, что для элементов x из Е нет однозначного ответа «да-нет» относительно свойства R. В связи с этим нечёткое подмножество А универсального множества Е определяется как множество упорядоченных пар A = {m A ( x) / x}, 27
Глава II. Нечёткая информация и выводы где m A (x) – характеристическая функция принадлежности (или просто функция принадлежности), принимающая значения в некотором вполне упорядоченном множестве М (например, М=[0,1]). Примеры функций принадлежности: μА(х) μА(х) 1
1
0
4
5
8
x
0
20
30
50
х
Функция принадлежности указывает степень (или уровень) принадлежности элемента х подмножеству А. Множество М называют множеством принадлежностей. Если М={0, 1}, то нечёткое подмножество А может рассматриваться как обычное или чёткое множество. Степень принадлежности – это не вероятность, т.к. неизвестна функция распределения, нет повторяемости экспериментов. Так, если взять из рассмотренного ранее примера прогноза погоды два взаимоисключающих события: будет дождь и не будет и присвоить им некоторые ранги, то сумма этих рангов необязательно будет равна 1, но если равенство всё-таки есть, то нечёткое множество считается нормированным. Значения функции принадлежности могут быть взяты только из априорных знаний, интуиции (опыта), опроса экспертов. Пр им еры з апи си нечёт кого множ еств а. Пусть Е = { x 1, x 2, x 3, x 4, х5}, М = [0, 1]; А – нечёткое множество, для которого
m A ( x1 ) = 0,3; m A ( x 2 ) = 0; m A ( x 3 ) = 1; m A ( x 4 ) = 0,5; m A ( x5 ) = 0,9. Тогда А можно представить в виде A = {0,3 / x1 ;0 / x 2 ;1 / x3 ;0,5 / x 4 ;0,9 / x5 }, или A = {0,3 / x1 + 0 / x 2 + 1 / x 3 + 0,5 / x 4 + 0,9 / x 5 }, или
х1 х2 А =0,3 0
х3 1
х4 х5 0,5 0,9
Замечание. Здесь знак «+» не является обозначением операции сложения, а имеет смысл объединения.
2.1.1. Основные характеристики нечётких множеств Пусть М = [0, 1] и А – нечёткое множество с элементами из универсального множества Е и множеством принадлежностей М. • Величина sup m A ( x ) называется высотой нечёткого множества А. Нечёткое xÎ E
множество А нормально, если его высота равна 1, т.е. верхняя граница его функции принадлежности равна 1 ( sup m A ( x ) = 1 ). При sup m ( x) < 1 нечёткое множество называется xÎ E
xÎ E
субнормальным. • Нечёткое множество пусто, если "x Î E m A ( x ) = 0 . Непустое субнормальное множество можно нормализовать по формуле
28
Потапов Д.К. Неклассические логики
m A ( x) :=
m A ( x) . sup m A ( x) xÎE
• Нечёткое множество унимодально, если m A ( x) = 1 только на одном х из Е. • Носителем нечёткого множества А является обычное подмножество со свойством m A ( x ) > 0 , т.е. носитель A = {x : x Î E , m A ( x ) > 0} . • Элементы x Î E , для которых m A ( x) = 0,5 , называются точками перехода множества А. Примеры нечётких множ еств. 1. Пусть Е = {0, 1, 2, . . . , 10}, М = [0, 1]. Нечёткое множество «Несколько» можно определить следующим образом: «Несколько» = 0,5/3+0,8/4+1/5+1/6+0,8/7+0,5/8; его характеристики: высота = 1, носитель = {3, 4, 5, 6, 7, 8}, точка перехода – {3, 8}. 2. Пусть Е = {0, 1, 2, 3, ..., п,…}. Нечёткое множество «Малый» можно определить: 1 " Малый " = {m Малый ( n) = / n}. 1 + ( n / 10) 2 3. Пусть Е – {1, 2, 3, ..., 100} и соответствует понятию «Возраст», тогда нечёткое множество «Молодой» может быть определено с помощью ì1, x Î [1;25], ï m Молодой ( x) = í 1 ï1 + (( x - 25) / 5) 2 , x > 25. î Нечёткое множество «Молодой» на универсальном множестве Е' = {ИВАНОВ, ПЕТРОВ, СИДОРОВ,...} задаётся с помощью функции принадлежности m Молодой ( x ) на Е = {1, 2, 3, ..., 100} (возраст), называемой по отношению к Е' функцией совместимости, при этом: m Молодой (СИДОРОВ ) := m Молодой ( x), где х – возраст СИДОРОВА. 4. Представить в виде нечёткого множества понятие «мужчина среднего роста»: A={0/155+0,1/160+0,3/165+0,8/170+1/175+1/180+0,5/185+0/190}. 5. Пусть Е = {ЗАПОРОЖЕЦ, ЖИГУЛИ, МЕРСЕДЕС,...} – множество марок автомобилей, а Е' = [0, ∞) – универсальное множество «Стоимость», тогда на Е' мы можем определить нечёткие множества типа: «Для бедных», «Для среднего класса», «Престижные», с функциями принадлежности вида рис. 2.1.
Рис. 2.1. Примеры функций принадлежности Имея эти функции и зная стоимости автомобилей из Е в данный момент времени, мы тем самым определим на Е' нечёткие множества с этими же названиями. Так, например, нечёткое множество «Для бедных», заданное на универсальном множестве Е={ЗАПОРОЖЕЦ, ЖИГУЛИ, МЕРСЕДЕС,...}, выглядит так, как показано на рис. 2.2.
29
Глава II. Нечёткая информация и выводы
Рис. 2.2. Пример задания нечёткого множества Аналогично можно определить нечёткое множество «Скоростные», «Средние», «Тихоходные» и т.д. 6. Пусть Е – множество целых чисел: Е ={ - 8, - 5, - 3, 0, 1 , 2 , 4 , 6 , 9 } . Тогда нечёткое подмножество чисел, по абсолютной величине близких к нулю, можно определить, например, так: А = {0/-8+0,5/-5+0,6/-3+1/0+0,9/1+0,8/2+0,6/4+0,3/6+0/9}.
2.1.2. О методах построения функций принадлежности нечётких множеств В приведённых выше примерах использованы прямые методы, когда эксперт либо просто задаёт для каждого хÎЕ значение m A (x ) , либо определяет функцию совместимости. Как правило, прямые методы задания функции принадлежности используются для измеримых понятий, таких как скорость, время, расстояние, давление, температура и т.д., или когда выделяются полярные значения. Во многих задачах при характеристике объекта можно выделить набор признаков и для каждого из них определить полярные значения, соответствующие значениям функции принадлежности, 0 или 1. Например, в задаче распознавания лиц можно выделить шкалы, приведённые в табл. 2.1. Таблица 2.1. Шкалы в задаче распознавания лиц 0 x1 x2 x3
высота лба профиль носа длина носа
низкий курносый короткий
1 высокий горбатый длинный
x4 x5
разрез глаз цвет глаз
узкие светлые
широкие темные
x6
форма подбородка остроконечный квадратный
x7
толщина губ
тонкие
толстые
x8
цвет лица
темный
светлый
x9
очертание лица
овальное
квадратное
Для конкретного лица А эксперт, исходя из приведённой шкалы, задаёт m A ( x) Î [0,1] , формируя векторную функцию принадлежности {m A ( x1 ), m A ( x 2 ),..., m A ( x9 )}. 30
Потапов Д.К. Неклассические логики При прямых методах используются также групповые прямые методы, когда, например, группе экспертов предъявляют конкретное лицо и каждый должен дать один из двух ответов: «этот человек лысый» или «этот человек не лысый», тогда количество утвердительных ответов, делённое на общее число экспертов, даёт значение m лысый (данного лица). В этом примере можно действовать через функцию совместимости, но тогда придётся считать число волосинок на голове у каждого из предъявленных эксперту лиц. Косвенные методы определения значений функции принадлежности используются в случаях, когда нет элементарных измеримых свойств, через которые определяется интересующее нас нечёткое множество. Как правило, это методы попарных сравнений. Если бы значения функций принадлежности были нам известны, например, m A ( xi ) = w i , i = 1,2,..., n, то попарные сравнения можно представить матрицей отношений A = {aij } , где {aij } = w i / w j (операция деления). На практике эксперт сам формирует матрицу А, при этом предполагается, что диагональные элементы равны 1, а для элементов симметричных относительно диагонали aij = 1 / a ji , т.е. если один элемент оценивается в a раз сильнее, чем другой, то этот последний должен быть в 1/ a раз сильнее, чем первый. В общем случае задача сводится в к поиску вектора w, удовлетворяющего уравнению вида Aw = l max w , где l max – наибольшее собственное значение матрицы А. Поскольку матрица А положительна по построению, решение данной задачи существует и является положительным. Можно отметить ещё два подхода: • использование типовых форм кривых для задания функций принадлежности (в форме (L-R)-типа – см. ниже) с уточнением их параметров в соответствии с данными эксперимента; • использование относительных частот по данным эксперимента в качестве значений принадлежности.
2.2. Операции над нечёткими множествами 2.2.1. Логические операции Включение. Пусть А и В – нечёткие множества на универсальном множестве Е. Говорят, что А содержится в В, если "x Î E m A ( x) £ m B ( x) . Обозначение: A Ì B . Иногда используют термин доминирование, т.е. в случае, когда A Ì B , говорят, что В доминирует А. Равенство. А и В равны, если "x Î E m A ( x ) = m B ( x ) . Обозначение: А=В. Дополнение. Пусть М = [0, 1], А и В – нечёткие множества, заданные на Е. А и В дополняют друг друга, если "x Î E m A ( x) = 1 - m B ( x ) . Обозначение: B = A или A = B . Очевидно, что A = A (дополнение определено для M=[0,1], но очевидно, что его можно определить для любого упорядоченного M). Пересечение. A Ç B – наибольшее нечёткое подмножество, содержащееся одновременно в A и B: m AÇ B ( x) = min( m A ( x), m B ( x)). Объединение. A È B – наименьшее нечёткое подмножество, включающее как A, так и B, с функцией принадлежности: m AÈ B ( x) = max( m A ( x ), m B ( x )). Разность. A - B = A Ç B с функцией принадлежности: m A- B ( x) = m AÇ B ( x) = min( m A ( x),1 - m B ( x)). 31
Глава II. Нечёткая информация и выводы Дизъюнктивная сумма A Å B = ( A - B) È ( B - A) = ( A Ç B ) È ( A Ç B) с функцией принадлежности: m A- B ( x) = max(min( m A ( x ),1 - m B ( x )); min(1 - m A ( x ), m B ( x ))). П р и м е р ы . Пусть A = 0,4 / x1 + 0,2 / x 2 + 0 / x3 + 1 / x 4 ; B = 0,7 / x1 + 0,9 / x 2 + 0,1 / x3 + 1 / x 4 ; C = 0,1 / x1 + 1 / x 2 + 0,2 / x3 + 0,9 / x 4 . Здесь: 1) A Ì B , т.е. А содержится в В или В доминирует А; С несравнимо ни с А, ни с В, т.е. пары {A,C} и {B,C} – пары недоминируемых нечётких множеств. 2) A ¹ B ¹ C . 3) A = 0,6/x1 + 0,8 / x 2 + 1 / x3 + 0 / x 4 ; B = 0,3 / x1 + 0,1 / x 2 + 0,9 / x 3 + 0 / x 4 . 4) A Ç B = 0,4/x1 + 0,2 / x 2 + 0 / x3 + 1 / x 4 . 5) A È B = 0,7/x1 + 0,9 / x 2 + 0,1 / x3 + 1 / x 4 . 6) A - B = A Ç B = 0,3/x1 + 0,1 / x 2 + 0 / x3 + 0 / x 4 ; B - A = A Ç B = 0,6/x1 + 0,8 / x 2 + 0,1 / x 3 + 0 / x 4 . 7) A Å B = 0,6/x1 + 0,8 / x 2 + 0,1 / x3 + 0 / x 4 ; Н а г л я д н о е п р е д с т а в л е н и е л о г и ч е с к и х о п е р а ц и й н ад н ечёт ки ми множествами. Дл я н ечёт ки х м ножеств можно строить визуальное представление. Рассмотрим прямоугольную систему координат, на оси ординат которой откладываются значения m A (x ) , на оси абсцисс в произвольном порядке расположены элементы Е (мы уже использовали такое представление в примерах нечётких множеств). Если Е по своей природе упорядочено, то этот порядок желательно сохранить в расположении элементов на оси абсцисс. Такое представление делает наглядными простые логические операции над нечёткими множествами (см. рис. 2.3).
Рис. 2.3. Графическая интерпретация логических операций: a – нечёткое множество А; б – нечёткое множество A; в – пересечение A Ç A ; г – объединение A È A На рис. 2.3а заштрихованная часть соответствует нечёткому множеству А и, если говорить точно, изображает область значений А и всех нечётких множеств, содержащихся в А. На рис. 2.3б, в, г даны A; A Ç A ; A È A . 32
Потапов Д.К. Неклассические логики Сво й ств а оп ерац ий È и Ç Пусть А, В, С – нечёткие множества, тогда выполняются следующие свойства: A Ç B = B Ç Aü 1) ý – коммутативность; A È B = B È Aþ 2) 3) 4) 5) 6) 7) 8)
( A Ç B) Ç C = A Ç ( B Ç C )ü ý – ассоциативность; ( A È B) È C = A È ( B È C )þ A Ç A = Aü ý – идемпотентность; A È A = Aþ A Ç ( B È C ) = ( A Ç B) È ( A Ç C )ü ý – дистрибутивность; A È ( B Ç C ) = ( A È B) Ç ( A È C )þ A È Æ = A , где Æ – пустое множество, т.е. m Æ ( x ) = 0 "x Î E ; A Ç Æ = Æ; A Ç E = A, где Е – универсальное множество; A È E = E;
A Ç B = A Ç B üï ý – теоремы де Моргана. A È B = A È B ïþ В отличие от чётких множеств, для нечётких множеств в общем случае: A Ç A ¹ Æ, A È A ¹ E (что, в частности, проиллюстрировано выше в примере наглядного представления нечётких множеств). Замечание. Введённые выше операции над нечёткими множествами основаны на использовании операций max и min. В теории нечётких множеств разрабатываются вопросы построения обобщённых, параметризованных операторов пересечения, объединения и дополнения, позволяющих учесть разнообразные смысловые оттенки соответствующих им связок «и», «или», «не». Один из подходов к операторам пересечения и объединения заключается в их определении в классе треугольных норм и конорм. Треугольной нормой (t-нормой) называется двуместная действительная функция T : [0,1] ´ [0,1] ® [0,1], удовлетворяющая следующим условиям: 1) T (0,0) = 0; T (m A ,1) = m A ; T (1, m A ) = m A – ограниченность; 2) T ( m A , m B ) £ T (m C , m D ), если m A £ m С , m B £ m D – монотонность; 9)
3) T ( m A , m B ) = T ( m B , m A ) – коммутативность; 4) T ( m A , T ( m B , m c )) = T (T (m A , m B ), m C ) – ассоциативность. Пр и м еры т ре уг о л ь н ы х н о рм min ( m A , m B ) произведение m A × m B max (0, m A + m B - 1). Треугольной конормой (t-конормой) называется двуместная действительная функция S : [0,1] ´ [0,1] ® [0,1] со свойствами: 1) S (1, 1) = 1; S ( m A ,0) = m A ; S (0, m A ) = m A – ограниченность; 2) S ( m A , m B ) ³ S ( m C , m D ), если m A ³ m С , m B ³ m D – монотонность; 3) S ( m A , m B ) = S ( m B , m A ) – коммутативность; 33
Глава II. Нечёткая информация и выводы 4) S ( m A , S ( m B , m C )) ³ S ( S ( m A , m B ), m C ) – ассоциативность. Примеры t-конорм max ( m A , m B ) m A + mB - m A × mB min (1, m A + m B ).
2.2.2. Алгебраические операции Алгебраическое произведение А и В обозначается A × B и определяется так: "x Î E m A× B ( x) = m A ( x) m B ( x ). Алгебраическая сумма этих множеств обозначается A +ˆ B и определяется так: "x Î E m A+ˆ B ( x ) = m A ( x) + m B ( x) - m A ( x ) m B ( x ). Для операций {×, +ˆ } выполняются свойства: A× B = B × A ü ý – коммутативность; A +ˆ B = B +ˆ Aþ ( A × B) × C = A × ( B × C ) ü 2) ý – ассоциативность; ( A +ˆ B) +ˆ C = A +ˆ ( B +ˆ C )þ 3) A × Æ = Æ, A +ˆ Æ = A , A × E = A, A +ˆ E = E; 1)
A × B = A +ˆ B ü ý – теоремы де Моргана. A +ˆ B = A × B þ Не выполняются: A× A = A ü 1) ý – идемпотентность; A +ˆ A = Aþ A × ( B +ˆ C ) = ( A × B) +ˆ ( A × C ) ü 2) ý – дистрибутивность; A +ˆ ( B × C ) = ( A +ˆ B) × ( A +ˆ C )þ 4)
3) а также A × A = Æ, A +ˆ A = E. З а м е ч а н и е . При совместном использования операций {È, Ç, ,+ˆ , ×} выполняются свойства: 1) A × ( B È C ) = ( A × B) È ( A × C ); 2) A × ( B Ç C ) = ( A × B) Ç ( A × C ); 3) A +ˆ ( B È C ) = ( A +ˆ B) È ( A +ˆ C ); 4) A +ˆ ( B Ç C ) = ( A +ˆ B) Ç ( A +ˆ C ). На основе операции алгебраического произведения определяется операция возведения в степень a нечёткого множества А, где a – положительное число. Нечёткое множество Aa определяется функцией принадлежности m aA = m aA (x). Частным случаем возведения в степень являются: 1) CON ( A) = A 2 – операция концентрирования (уплотнения); 2) DIL( A) = A 0 ,5 – операция растяжения, которые используются при работе с лингвистическими неопределённостями (рис. 2.4).
34
Потапов Д.К. Неклассические логики
Рис. 2.4. Иллюстрация к понятию операций концентрирования (уплотнения) и растяжения Умножение на число. Если a – положительное число, такое, что a max m A ( x ) £ 1, то xÎA
нечёткое множество aA имеет функцию принадлежности: m aA ( x ) = am A ( x). Выпуклая комбинация нечётких множеств. Пусть A1 , A2 ,..., An – нечёткие множества универсального множества Е, w1 , w 2 ,...,w n – неотрицательные числа, сумма которых равна 1. Выпуклой комбинацией A1 , A2 ,..., An называется нечёткое множество А с функцией принадлежности: "x Î E m A ( x1 , x 2 ,..., x n ) = w1 m A1 ( x ) + w 2 m A2 ( x ) + ... + w n m An ( x ). Декартово (прямое) произведение нечётких множеств. Пусть A1 , A2 ,..., An – нечёткие подмножества универсальных множеств E1 , E2 ,..., En соответственно. Декартово, или прямое произведение A = A1 ´ A2 ´ ... ´ An является нечётким подмножеством множества E = E1 ´ E 2 ´ ... ´ E n с функцией принадлежности:
m A ( x1 , x 2 ,..., x n ) = min( m A1 ( x1 ), m A2 ( x 2 ),... + m An ( x n )). Оператор увеличения нечёткости используется для преобразования чётких множеств в нечёткие и для увеличения нечёткости нечёткого множества. Пусть А – нечёткое множество, Е – универсальное множество и для всех x Î E определены нечёткие множества К(х). Совокупность всех К(х) называется ядром оператора увеличения нечёткости Ф. Результатом действия оператора Ф на нечёткое множество А является нечёткое множество вида F ( A, K ) = U m A ( x ) K ( x ), xÎE
где m A ( x) K ( x) – произведение числа на нечёткое множество. Пр и м ер . Пусть E = {1, 2, 3, 4}; A = 0,8 / 1 + 0,6 / 2 + 0 / 3 + 0 / 4; K (1) = 1 / 1 + 0,4 / 2; K (2) = 1 / 2 + 0, 4 / 1 + 0,4 / 3; K (3) = 1 / 3 + 0,5 / 4; K (4) = 1 / 4. Тогда F ( A, K ) = m A (1) K (1) È m A (2) K (2) È m A (3) K (3) È m A (4) K (4) = = 0,8(1 / 1 + 0,4 / 2) È 0,6(1 / 2 + 0, 4 / 1 + 0,4 / 3) = 0,8 / 1 + 0,6 / 2 + 0, 24 / 3. Чёткое множество a -уровня (или уровня a ). Множеством a -уровня нечёткого множества А универсального множества Е называется чёткое подмножество Aa универсального множества Е, определяемое в виде Aa = {x : m A ( x ) ³ a }, где a £ 1. 35
Глава II. Нечёткая информация и выводы Пр и м ер . Пусть A = 0,2 / x1 + 0 / x 2 + 0,5 / x 3 + 1 / x 4 , тогда A0,3 = {x3 , x 4 }, A0, 7 = {x 4 }. Достаточно очевидное свойство: если a1 ³ a 2 , то Aa 1 Í Aa 2 .
2.3. Нечёткая и лингвистическая переменные Понятие нечёткой и лингвистической переменных используется при описании объектов и явлений с помощью нечётких множеств. Нечёткая переменная характеризуется тройкой a , X , A , где
a – наименование переменной; X – универсальное множество (область определения a ); А – нечёткое множество на X, описывающее ограничения (т.е. m A (x) ) на значения нечёткой переменной a . Лингвистической переменной называется набор b , T , X , G , M , где b – наименование лингвистической переменной; Т – множество её значений (терм-множество), представляющих собой наименования нечётких переменных, областью определения каждой из которых является множество X. Множество Т называется базовым терм-множеством лингвистической переменной; G – синтаксическая процедура, позволяющая оперировать элементами терм-множества Т, в частности, генерировать новые термы (значения). Множество T È G (T ) , где G(Т) – множество сгенерированных термов, называется расширенным терм-множеством лингвистической переменной; М – семантическая процедура, позволяющая превратить каждое новое значение лингвистической переменной, образуемое процедурой G, в нечёткую переменную, т.е. сформировать соответствующее нечёткое множество. Значениями лингвистической переменной являются не числа, а слова естественного языка, называемые термами. Например, в случае управления мобильным роботом можно ввести две лингвистические переменные: «дистанция» (расстояние до помехи) и «направление» (угол между продольной осью робота и направлением на помеху). Зам еч ан и е. Чтобы избежать большого количества символов: 1) символ b используют как для названия самой переменной, так и для всех её значений; 2) пользуются одним и тем же символом для обозначения нечёткого множества и его названия, например терм «Молодой», являющийся значением лингвистической переменной b =«возраст», одновременно есть и нечёткое множество М («Молодой»). Присвоение нескольких значений символам предполагает, что контекст позволяет разрешить возможные неопределённости. Пр и м еры . 1. Пусть эксперт определяет толщину выпускаемого изделия с помощью понятий «Малая толщина», «Средняя толщина» и «Большая толщина», при этом минимальная толщина равна 10 мм, а максимальная – 80 мм. Формализация такого описания может быть проведена с помощью следующей лингвистической переменной b , T , X , G , M , где b – толщина изделия; Т – {«Малая толщина», «Средняя толщина», «Большая толщина»}; X – [10, 80]; G – процедура образования новых термов с помощью связок «и», «или» и модификаторов типа «очень», «не», «слегка» и т.п. Например: «Малая или средняя толщина», «Очень малая толщина» и т.д.; 36
Потапов Д.К. Неклассические логики М – процедура задания на X = [10, 80] нечётких подмножеств A1 = «Малая толщина», А2 = «Средняя толщина», А3 = «Большая толщина», а также нечётких множеств для термов из G(Т) в соответствии с правилами трансляции нечётких связок и модификаторов «и», «или», «не», «очень», «слегка» и других операций над нечёткими множествами вида: 2 0,5 A Ç B, A È B, A , CONA = A , DILA = A и т.п. 2. Рассмотрим переменную «скорость автомобиля», которая оценивается по шкале «низкая», «средняя», «высокая». В этом примере лингвистической переменной является «скорость автомобиля», термами – лингвистические оценки «низкая», «средняя», «высокая», которые и составляют терм-множество. 3. Рассмотрим лингвистическую переменную «дистанция». Значениями её можно определить термы «далеко», «средняя», «близко» и «очень близко». Для физической реализации лингвистической переменной необходимо определить точные физические значения термов этой переменной. Пусть переменная «дистанция» может принимать любое значение из диапазона от нуля до бесконечности. Согласно положениям теории нечётких множеств, в таком случае каждому значению расстояния из указанного диапазона может быть поставлено в соответствие некоторое число от нуля до единицы, которое определяет степень принадлежности данного физического расстояния (допустим 40 см) к тому или иному терму лингвистической переменной «дистанция». Степень принадлежности определяется так называемой функцией принадлежности M(d), где d – расстояние до помехи. В нашем случае расстоянию 40 см можно задать степень принадлежностик терму «очень близко» равную 0,7, а к терму «близко» – 0,3. Конкретное определение степени принадлежности может проходить только при работе с экспертами. Переменной «направление», которая может принимать значения в диапазоне от 0 до 360 градусов, зададим термы «левое», «прямо» и «правое». Теперь необходимо задать выходные переменные. В рассматриваемом примере достаточно одной, которая будет называться «рулевой угол». Она может содержать термы: «резко влево», «влево», «прямо», «вправо», «резко вправо». Связь между входом и выходом запоминается в таблице нечётких правил (см. ниже п. 2.5.). Каждая запись в данной таблице соответствует своему нечёткому правилу, например: Если «дистанция» «близко» и «направление» «правое», тогда «рулевой угол» «резко влево». Таким образом, мобильный робот с нечёткой логикой будет работать по следующему принципу: данные с сенсоров о расстоянии до помехи и направлении на неё будут фазифицированы, обработаны согласно табличным правилам, дефазифицированы и полученные данные в виде управляющих сигналов поступят на привода робота. Зам еч ан и е. Наряду с рассмотренными выше базовыми значениями лингвистической переменной «Толщина» (Т = {«Малая толщина», «Средняя толщина», «Большая толщина»}) возможны значения, зависящие от области определения X. В данном случае значения лингвистической переменной «Толщина изделия» могут быть определены как «около 20 мм», «около 50 мм», «около 70 мм», т.е. в виде нечётких чисел. Терм-множество и расширенное терм-множество в условиях примера можно характеризовать функциями принадлежности, приведёнными на рис. 2.5 и 2.6.
Рис. 2.5. Функции принадлежности нечётких множеств: «Малая толщина» = A1 , «Средняя толщина»= A2 , «Большая толщина» = A3 37
Глава II. Нечёткая информация и выводы
Рис. 2.6. Функция принадлежности нечёткого множества «Малая или средняя толщина» = A1 È A2
2.3.1. Нечёткие числа Нечёткие числа – нечёткие переменные, определённые на числовой оси, т.е. нечёткое число определяется как нечёткое множество А на множестве действительных чисел R с функцией принадлежности m A ( x) Î [0,1], где х – действительное число, т.е. x Î R . Нечёткое число А нормально, если max m A ( x) = 1 ; выпуклое, если для любых x
x £ y £ z выполняется m A ( x) ³ m A ( y ) Ù m A ( z ). Множество a -уровня нечёткого числа А определяется как Aa = {x : m A ( x) ³ a }. Подмножество S A Ì R называется носителем нечёткого числа А, если S A = {x : m A ( x ) > 0}. Нечёткое число А унимодально, если условие m A ( x) = 1 справедливо только для одной точки действительной оси. Выпуклое нечёткое число А называется нечётким нулем, если m A (0) = sup( m A ( x )). x
Нечёткое число А положительно, если "x Î S A , x > 0 и отрицательно, если "x Î S A , x < 0 .
2.3.2. Операции над нечёткими числами Расширенные бинарные арифметические операции (сложение, умножение и пр.) для нечётких чисел определяются через соответствующие операции для чётких чисел с использованием принципа обобщения следующим образом. Пусть А и В – нечёткие числа, и ~ * – нечёткая операция, соответствующая произвольной алгебраической операции * над обычными числами. Тогда (используя здесь и в дальнейшем обозначения Ú вместо max и Ù вместо min ) можно записать x
x
x
C = A~ * B Û mC ( z ) =
Отсюда
38
x
Ú
Z = X *Y
( m A ( x) Ù m B ( y )).
Потапов Д.К. Неклассические логики
+ B Û mC ( z ) = C = A~
(m A ( x) Ù m B ( y)), Ú Z = X +Y
- B Û mC ( z ) = C = A~
(m A ( x) Ù m B ( y)), Ú Z = X -Y
C = A ~× B Û mC ( z) = ¸ B Û mC ( z ) = C = A~
Ú
(m A ( x) Ù m B ( y)),
Ú
(m A ( x) Ù m B ( y)),
Z = X ×Y
Z = X ¸Y
ax( A, B) Û mC ( z) = C = m~
~ C = m i n( A, B) Û mC ( z) =
(m A ( x) Ù m B ( y)), Ú Z =max(X ,Y ) (m A ( x) Ù m B ( y)). Ú Z =min(X ,Y )
2.3.3. Нечёткие числа (L-R) типа Нечёткие числа (L-R)-типа – это разновидность нечётких чисел специального вида, т.е. задаваемых по определённым правилам с целью снижения объёма вычислений при операциях над ними. Функции принадлежности нечётких чисел (L-R)-типа задаются с помощью невозрастающих на множестве неотрицательных действительных чисел функций действительного переменного L(х) и R(х), удовлетворяющих свойствам: а) L(- x ) = L( x), R (- x) = R ( x); б) L(0) = R (0). Очевидно, что к классу (L-R)-функций относятся функции, графики которых имеют вид, приведённый на рис. 2.7.
Рис. 2.7. Возможный вид (L-R)-функций Примерами аналитического задания (L-R)-функций могут быть p 1 -X L( x ) = e , p ³ 0; R ( x ) = , p ³ 0, p 1+ x и т.д. Пусть L(y) и R(y) – функции (L-R)-типа (конкретные). Унимодальное нечёткое число А с модой а (т.е. m A (a) = 1 ) с помощью L(y) и R(y) задаётся следующим образом:
39
Глава II. Нечёткая информация и выводы ì æa- xö ï Lç a ÷ при x £ a , ø ï è m A ( x) = í ï Ræç x - a ö÷ при x > a , ï çè b ÷ø î где а – мода; a > 0, b > 0 – левый и правый коэффициенты нечёткости. Таким образом, при заданных L(y) и R(y) нечёткое число (унимодальное) задаётся тройкой A = (a, a , b ). Толерантное нечёткое число задаётся, соответственно, четвёркой параметров A = (a1 , a 2 , a , b ), где a1 и a 2 – границы толерантности, т.е. в промежутке [ a1 , a 2 ] значение функции принадлежности равно 1. Примеры графиков функций принадлежности нечётких чисел (L-R)-типа приведены на рис. 2.8. Отметим, что в конкретных ситуациях функции L(y), R(y), а также параметры a , b нечётких чисел (a,a , b ) и (a1 , a 2 ,a , b ) должны подбираться таким образом, чтобы результат операции (сложения, вычитания, деления и т.д.) был точно или приблизительно равен нечёткому числу с теми же L(у) и R(у), а параметры a ¢ и b ¢ результата не выходили за рамки ограничений на эти параметры для исходных нечётких чисел, особенно если результат в дальнейшем будет участвовать в операциях.
Рис. 2.8. Примеры графиков функций принадлежности нечётких чисел (L-R)-типа Зам еч ан и е. Решение задач математического моделирования сложных систем с применением аппарата нечётких множеств требует выполнения большого объёма операций над разного рода лингвистическими и другими нечёткими переменными. Для удобства исполнения операций, а также для ввода-вывода и хранения данных, желательно работать с функциями принадлежности стандартного вида. Нечёткие множества, которыми приходится оперировать в большинстве задач, являются, как правило, унимодальными и нормальными. Одним из возможных методов аппроксимации унимодальных нечётких множеств является аппроксимация с помощью функций (L-R)-типа. Примеры (L-R)-представлений некоторых лингвистических переменных приведены в табл. 2.2.
40
Потапов Д.К. Неклассические логики Таблица 2.2. Возможное (L-R)-представление некоторых лингвистических переменных Терм лингвистической переменной Средний Малый
(L-R)-представление
Графическое представление
A = (a, a , b ) LR a = b > 0
ab
A = (a, ¥, b ) LR a = ¥
a =¥b
Большой
A = ( a , a , ¥ ) LR b = ¥
a b =¥
Приблизительно в диапазоне
A = (a1 , a 2 , a , b ) LR a = b > 0
Определённый
A = (a ,0,0) LR a = b = 0
Разнообразный: зона полной неопределённости
A = (a , ¥, ¥ ) LR a = b = ¥
a b
a1 a 2
a =0 b =0 a =b =¥
2.4. Нечёткие отношения Пусть E = E1 ´ E 2 ´ ... ´ E n – прямое произведение универсальных множеств и М – некоторое множество принадлежностей (например, М=[0,1]). Нечёткое n-арное отношение определяется как нечёткое подмножество R на Е, принимающее свои значения в М. В случае п=2 и М=[0,1] нечётким отношением R между множествами X = E1 и Y = E2 будет называться функция R : ( X , Y ) ® [0,1], которая ставит в соответствие каждой паре элементов ( x, y ) Î X ´ Y величину m R ( x, y ) Î [0,1]. Обозначение: нечёткое отношение на X ´ Y запишется в виде x Î X , y Î Y : xRy. В случае, когда X=Y, т.е. X и Y совпадают, нечёткое отношение R : X ´ X ® [0,1] называется нечётким отношением на множестве X. Пр и м еры . 1) Пусть X = {x1 , x 2 , x3 }, Y = { y1 , y 2 , y 3 , y 4 }, M = [0,1]. Нечёткое отношение R = XRY может быть задано, к примеру, табл. 2.3. Таблица 2.3. Задание нечёткого отношения y1
y2
y3
y4
x1
0
0
0,1 0,3
x2
0
0,8 1
x3
1
0,5 0,6 1
0,7
2) Пусть X = Y = (-¥, ¥), т.е. множество всех действительных чисел. Отношение x >> y ( x много больше y ) можно задать функцией принадлежности:
41
Глава II. Нечёткая информация и выводы ì0, если x £ y, ï mR = í 1 , если y < x. ï 2 î1 + (1 /( x - y ) ) 2
3) Отношение R, для которого m R ( x, y ) = e -k ( x- y ) , при достаточно больших k можно интерпретировать так: «x и y близкие друг к другу числа». Операции над нечёткими отношениями Объединение двух отношений R1 и R2 . Объединение двух отношений обозначается R1 È R2 и определяется выражением
m R1 È R2 ( x , y ) = m R1 ( x , y ) Ú m R2 ( x, y ). Пересечение двух отношений. Пересечение двух отношений R1 и R2 обозначается R1 Ç R2 и определяется выражением
m R1 Ç R2 ( x , y ) = m R1 ( x, y ) Ù m R2 ( x, y ). Алгебраическое произведение двух отношений. Алгебраическое произведение двух отношений R1 и R2 обозначается R1 × R2 и определяется выражением
m R1×R2 ( x , y ) = m R1 ( x, y ) × m R2 ( x, y ). Алгебраическая сумма двух отношений. Алгебраическая сумма двух отношений R1 и R2 обозначается R1 +ˆ R2 и определяется выражением
m R1 +ˆ R2 ( x, y ) = m R1 ( x , y ) + m R2 ( x , y ) - m R1 ( x, y ) × m R2 ( x, y ). Для введённых операций справедливы следующие свойства дистрибутивности: R1 Ç ( R2 È R3 ) = ( R1 Ç R2 ) È ( R1 Ç R3 ), R1 È ( R2 Ç R3 ) = ( R1 È R2 ) Ç ( R1 È R3 ), R1 × ( R2 È R3 ) = ( R1 × R2 ) È ( R1 × R3 ), R1 × ( R2 Ç R3 ) = ( R1 × R2 ) Ç ( R1 × R3 ), R1 +ˆ ( R2 È R3 ) = ( R1 +ˆ R2 ) È ( R1 +ˆ R3 ), R1 +ˆ ( R2 Ç R3 ) = ( R1 +ˆ R2 ) Ç ( R1 +ˆ R3 ). Дополнение отношения. Дополнение отношения R обозначается R и определяется функцией принадлежности: m R ( x, y ) = 1 - m R ( x, y ). Дизъюнктивная сумма двух отношений. Дизъюнктивная сумма двух отношений R1 и R2 обозначается R1 Å R2 и определяется выражением R1 Å R2 = ( R1 Ç R2 ) È ( R1 Ç R2 ). Обычное отношение, ближайшее к нечёткому. Пусть R – нечёткое отношение с функцией принадлежности m R ( x, y ). Обычное отношение, ближайшее к нечёткому, обозначается R и определяется выражением ì0, если m R ( x , y ) < 0,5, ï m R ( x , y ) = í1, если m R ( x , y ) > 0,5, ï î0 или 1, если m R ( x, y ) = 0,5. По договорённости принимают m R ( x, y ) = 0 при m R ( x, y ) = 0,5. 42
Потапов Д.К. Неклассические логики Композиция (свёртка) двух нечётких отношений. Пусть R1 – нечёткое отношение R1 : ( X ´ Y ) ® [0,1] между X и Y, и R2 – нечёткое отношение R2 : (Y ´ Z ) ® [0,1] между Y и Z. Нечёткое отношение между X и Z, обозначаемое R2 o R1 , определённое через R1 и R2 выражением
m R1o R2 ( x, z ) = Ú ( m R1 ( x, y ) Ù m R2 ( y, z )), y
называется (max-min)-композицией ((max-min)-свёрткой) отношений R1 и R2. Пр и м ер . Пусть R1 y1 y2 y3 x1 0,1 0,7 0,4 x2 1 0,5 0
R2 z1 z2 z3 z4 y1 0,9 0 1 0,2 y2 0,3 0,6 0 0,9 y3 0,1 1 0 0,5
Тогда
R1 o R2
z1
z2
z3
z4
x1
0,3 0,6 0,1 0,7
x2
0,9 0,5
1
0,5
При этом
m R1 o R2 ( x1 , z1 ) = ( m R1 ( x1 , y1 ) Ù m R2 ( y1 , z1 )) Ú (m R1 ( x1 , y 2 ) Ù m R2 ( y 2 , z1 )) Ú ( m R1 ( x1 , y 3 ) Ù Ù m R2 ( y 3 , z1 )) = (0,1 Ù 0,9) Ú (0,7 Ù 0.3) Ú (0, 4 Ù 0,1) = 0,1 Ú 0,3 Ú 0,1 = 0,3;
m R1o R2 ( x1 , z 3 ) = 0,1;
LLLLLLLL
m R1o R2 ( x 2 , z 4 ) = 0,5.
Зам еч ан и е. В данном примере вначале использован «аналитический» способ композиции отношений R1 и R2, т.е. i-я строка R1 «умножается» на j-й столбец R2 с использованием операции Ù полученный результат «свёртывается» с использованием операции Ú в m ( xi , z j ). Свойства (max-min)-композиции. Операция (max-min)-композиции ассоциативна, т.е. R3 o ( R2 o R1 ) = ( R3 o R2 ) o R1 , дистрибутивна относительно объединения, но недистрибутивна относительно пересечения: R3 o ( R2 È R1 ) = ( R3 o R2 ) È ( R3 o R1 ),
R3 o ( R2 Ç R1 ) ¹ ( R3 o R2 ) Ç ( R3 o R1 ). Кроме того, для (max-min)-композиции выполняется следующее важное свойство: если R1 Ì R2 , то R o R1 Ì R o R2 . mах-композиция. В выражении
m R1o R2 ( x, z ) = Ú (m R1 ( x, y ) Ù m R2 ( y, z )) y
43
Глава II. Нечёткая информация и выводы для (max-min)-композиции отношений R1 и R2 операцию Ù можно заменить любой другой, для которой выполняются те же ограничения, что и для Ù : ассоциативность и монотонность (в смысле неубывания) по каждому аргументу. Тогда
m R1o R2 ( x, z ) = Ú ( m R1 ( x, y ) * m R2 ( y , z )). y
В частности, операция Ù может быть заменена алгебраическим умножением, тогда говорят о (max-prod)-композиции.
2.5. Нечёткие выводы Используемый в различного рода экспертных и управляющих системах механизм нечётких выводов в своей основе имеет базу знаний, формируемую специалистами предметной области в виде совокупности нечётких предикатных правил вида: П1: если x есть А1, тогда y есть B1, П2: если x есть А2, тогда y есть B2, ……………………………………... Пn: если x есть Аn, тогда y есть Bn, где х – входная переменная (имя для известных значений данных), y – переменная вывода (имя для значения данных, которое будет вычислено); А и В – функции принадлежности, определённые соответственно на х и у. Пр и м ер п о до бн о г о п рав и л а. Если х – низко, то у – высоко. Приведём более детальное пояснение. Знание эксперта A ® B отражает нечёткое причинное отношение предпосылки и заключения, поэтому его можно назвать нечётким отношением и обозначить через R: R = A ® B, где « ® » называют нечёткой импликацией. Отношение R можно рассматривать как нечёткое подмножество прямого произведения X ´ Y полного множества предпосылок X и заключений Y. Таким образом, процесс получения (нечёткого) результата вывода В' с использованием данного наблюдения А' и знания A ® B можно представить в виде формулы B¢ = A ¢ o R = A ¢ o (A ® B), где « o »– введённая выше операция свёртки. Как операцию композиции, так и операцию импликации в алгебре нечётких множеств можно реализовывать по-разному (при этом, естественно, будет разниться и итоговый получаемый результат), но в любом случае общий логический вывод осуществляется за следующие четыре этапа. 1. Нечёткость (введение нечёткости, фазификация, fuzzification). Функции принадлежности, определённые на входных переменных применяются к их фактическим значениям для определения степени истинности каждой предпосылки каждого правила (фазификация – сопоставление множества значений х её функции принадлежности m (x), т.е. перевод значений х в нечёткий формат). 2. Логический вывод. Вычисленное значение истинности для предпосылок каждого правила применяется к заключениям каждого правила. Это приводит к одному нечёткому подмножеству, которое будет назначено каждой переменной вывода для каждого правила. В качестве правил логического вывода обычно используются только операции min (МИНИМУМ) или prod (УМНОЖЕНИЕ). В логическом выводе МИНИМУМА функция принадлежности вывода «отсекается» по высоте, соответствующей вычисленной степени истинности предпосылки правила (нечёткая логика «И»). В логическом выводе УМНОЖЕНИЯ функция 44
Потапов Д.К. Неклассические логики принадлежности вывода масштабируется при помощи вычисленной степени истинности предпосылки правила. 3. Композиция. Все нечёткие подмножества, назначенные к каждой переменной вывода (во всех правилах), объединяются вместе, чтобы формировать одно нечёткое подмножество для каждой переменной вывода. При подобном объединении обычно используются операции max (МАКСИМУМ) или sum (СУММА). При композиции МАКСИМУМА комбинированный вывод нечёткого подмножества конструируется как поточечный максимум по всем нечётким подмножествам (нечёткая логика «ИЛИ»). При композиции СУММЫ комбинированный вывод нечёткого подмножества конструируется как поточечная сумма по всем нечётким подмножествам, назначенным переменной вывода правилами логического вывода. 4. В заключение (дополнительно) – приведение к чёткости (дефазификация, defuzzification), которое используется, когда полезно преобразовать нечёткий набор выводов в чёткое число (дефазификация – процесс, обратный фазификации). Имеется большое количество методов приведения к чёткости, некоторые из которых рассмотрены ниже. Итак, все системы с нечёткой логикой функционирую по одному принципу: показания измерительных приборов фазифицируются (переводятся в нечёткий формат), обрабатываются, дефазифицируются и в виде привычных сигналов подаются на исполнительные устройства. Пример. Пусть некоторая система описывается следующими нечёткими правилами: П1: если х есть А, тогда w есть D, П2: если у есть В, тогда w есть Е, П3: если z есть С, тогда w есть F, где х, у и z – имена входных переменных, w – имя переменной вывода, А, В, С, D, E, F – заданные функции принадлежности (треугольной формы). Процедура получения логического вывода иллюстрируется рис. 2.9. Предполагается, что входные переменные приняли некоторые конкретные (чёткие) значения – х0, у0 и z0. В соответствии с приведёнными этапами, на этапе 1 для данных значений и исходя из функций принадлежности А, В, С, находятся степени истинности a ( x 0 ), a ( y 0 ) и a ( z 0 ) для предпосылок каждого из трёх приведённых правил (см. рис. 2.9). На этапе 2 происходит «отсекание» функций принадлежности заключений правил (т.е. D, Е, F) на уровнях a ( x 0 ),a ( y 0 ) и a ( z 0 ) . На этапе 3 рассматриваются усечённые на втором этапе функции принадлежности и производится их объединение с использованием операции max, в результате чего получается комбинированное нечёткое подмножество, описываемое функцией принадлежности m S (w ) и соответствующее логическому выводу для выходной переменной w . Наконец, на 4-м этапе – при необходимости – находится чёткое значение выходной переменной, например, с применением центроидного метода: чёткое значение выходной переменной определяется как центр тяжести для кривой m S (w ) , т.е.
w0 =
ò wm S (w )dw
W
ò m S (w )dw
.
W
Рассмотрим следующие наиболее часто используемые модификации алгоритма нечёткого вывода, полагая, для простоты, что базу знаний организуют два нечётких правила вида: П1: если х есть A1 и у есть B1, тогда z есть C1, П2: если х есть А2 и у есть В2, тогда z есть С2, 45
Глава II. Нечёткая информация и выводы где х и у – имена входных переменных, z – имя переменной вывода, A1, A2, B1, B2, C1, C2 – некоторые заданные функции принадлежности, при этом чёткое значение z0 необходимо определить на основе приведённой информации и чётких значений х0 и y0.
Рис. 2.9. Иллюстрация к процедуре логического вывода
2.5.1. Алгоритм Mamdani Данный алгоритм соответствует рассмотренному примеру и рис. 2.9. В рассматриваемой ситуации он математически может быть описан следующим образом. 1. Нечёткость: находятся степени истинности для предпосылок каждого правила: A1 (x0), A2(x0), B1(y0), B2(y0). 2. Нечёткий вывод: находятся уровни «отсечения» для предпосылок каждого из правил (с использованием операции МИНИМУМ) a 1 = A 1 ( x0 ) Ù B1 ( y 0 ),
a 2 = A 2 ( x0 ) Ù B 2 ( y 0 ), где через "Ù" обозначена операция логического минимума (min), затем находятся «усечённые» функции принадлежности ¢ С1 ( z ) = (a 1 Ù C1 ( z )), ¢ C 2 ( z ) = (a 2 Ù C 2 ( z )). 3. Композиция: с использованием операции МАКСИМУМ (max, далее обозначаемой как "Ú" ) производится объединение найденных усечённых функций, что приводит к получению итогового нечёткого подмножества для переменной выхода с функцией принадлежности ¢ ¢ m S ( z ) = C( z ) = C1 ( z ) Ú C 2 ( z ) = (a 1 Ù C1 ( z )) Ú (a 2 Ù C 2 ( z )). 4. Наконец, приведение к чёткости (для нахождения z0) проводится, например, центроидным методом.
46
Потапов Д.К. Неклассические логики
2.5.2. Алгоритм Tsukamoto Исходные посылки – как у предыдущего алгоритма, но в данном случае предполагается, что функции C1(z), С2(z) являются монотонными. 1. Первый этап – такой же, как в алгоритме Mamdani. 2. На втором этапе сначала находятся (как в алгоритме Mamdani) уровни «отсечения» a1 и a 2 , а затем – посредством решения уравнений a 1 = C1 ( z1 ), a 2 = C 2 ( z 2 ) – чёткие значения (z1 и z2) для каждого из исходных правил. 3. Определяется чёткое значение переменной вывода (как взвешенное среднее z1 и z2 ): a z + a 2 z2 z0 = 1 1 ; a1 + a 2 в общем случае (дискретный вариант центроидного метода) n
z0 =
å a i zi i =1 n
åa i
.
i =1
Пр и м ер . Пусть имеем A1 ( x 0 ) = 0,7, A 2 ( x 0 ) = 0,6, B1 ( y 0 ) = 0,3, B 2 ( y 0 ) = 0,8, соответствующие уровни отсечения a 1 = min( A 1 ( x 0 ), B1 ( y 0 )) = min( 0,7;0,3) = 0,3,
a 2 = min( A 2 ( x 0 ), B 2 ( y 0 )) = min( 0,6;0,8) = 0,6 и значения z1=8 и z2=4, найденные в результате решения уравнений C1 ( z1 ) = 0,3, C 2 ( z 2 ) = 0,6.
Рис. 2.10. Иллюстрация к алгоритму Tsukamoto При этом чёткое значение переменной вывода (см. рис. 2.10) z 0 = (8 × 0,3 + 4 × 0,6) /(0,3 + 0,6) = 6
2.5.3. Алгоритм Sugeno Sugeno и Takagi использовали набор правил в следующей форме (как и раньше, приводим пример двух правил): 47
Глава II. Нечёткая информация и выводы П1: если x есть A1 и y есть B1, тогда z1 = a1 x + b1 y, П2: если x есть A2 и y есть B2, тогда z 2 = a 2 x + b2 y. Пр ед ст ав л ен и е а л г о ри т м а 1. Первый этап – как в алгоритме Mamdani. 2. На втором этапе находятся a 1 = A 1 ( x0 ) Ù B1 ( y 0 ), a 2 = A 2 ( x0 ) Ù B 2 ( y 0 ) и индивидуальные выходы правил: z1* = a1 x0 + b1 y 0 , z 2 * = a 2 x 0 + b2 y 0 . 3. На третьем этапе определяется чёткое значение переменной вывода: a1 z1* + a 2 z 2* z0 = . a1 + a 2 Иллюстрирует алгоритм рис. 2.11.
Рис. 2.11. Иллюстрация к алгоритму Sugeno
2.5.4. Алгоритм Larsen В алгоритме Larsen нечёткая импликация моделируется с использованием оператора умножения. Оп и с ан и е ал г о ри т м а 1. Первый этап – как в алгоритме Mamdani. 2. На втором этапе, как в алгоритме Mamdani в начале находятся значения a 1 = A 1 ( x0 ) Ù B1 ( y 0 ),
a 2 = A 2 ( x0 ) Ù B 2 ( y 0 ), а затем – частные нечёткие подмножества a 1C1 ( z ), a 2 C 2 ( z ). 3. Находится итоговое нечёткое подмножество с функцией принадлежности m S ( z ) = C( z ) = (a 1C1 ( z )) Ú (a 2 C 2 ( z )) n
(в общем случае n правил m S ( z ) = C( z ) = Ú (a i C i ( z )). i =1
4. При необходимости производится приведение к чёткости (как в ранее рассмотренных алгоритмах).
48
Потапов Д.К. Неклассические логики Алгоритм Larsen иллюстрируется рис. 2.12.
Рис. 2.12. Иллюстрация алгоритма Larsen
2.5.5. Упрощённый алгоритм нечёткого вывода Исходные правила в данном случае задаются в виде: П1: если x есть A1 и y есть B1, тогда z1 = c1 , П2: если x есть A2 и y есть B2, тогда z 2 = c 2 , где c1 и c2- некоторые обычные (чёткие) числа. Оп и с ан и е ал г о ри т м а 1. Первый этап – как в алгоритме Mamdani. 2. На втором этапе находятся числа a 1 = A 1 ( x0 ) Ù B1 ( y 0 ), a 2 = A 2 ( x0 ) Ù B 2 ( y 0 ). 3. На третьем этапе находится чёткое значение выходной переменной по формуле a c + a 2 c2 , z0 = 1 1 a1 + a 2 или – в общем случае наличия n правил – по формуле n
z0 =
å a i ci i =1 n
åa i
.
i =1
Иллюстрация алгоритма приведена на рис. 2.13.
Рис. 2.13. Иллюстрация упрощённого алгоритма нечёткого вывода 49
Глава II. Нечёткая информация и выводы
2.5.6. Методы приведения к чёткости 1. Выше уже был рассмотрен один из данных методов – центроидный. Приведём соответствующие формулы еще раз. Для непрерывного варианта: ò zC( z )dz W z0 = ; ò C( z )dz W
для дискретного варианта: n
z0 =
å a i zi i =1 n
.
åa i i =1
2. Первый максимум (First-of-Maxima). Чёткая величина переменной вывода находится как наименьшее значение, при котором
Рис.2.14. Иллюстрация к методам приведения к чёткости: а – первый максимум; б – средний максимум достигается максимум итогового нечёткого множества, т.е. (см. рис. 2.14а) z 0 = min( z : C( z ) = max C(u )). u
3. Средний максимум (Middle-of-Maxima). Чёткое значение находится по формуле ò zdz z0 =
G
ò dz
,
G
где G – подмножество элементов, максимизирующих C (см. рис. 2.146). Дискретный вариант (если С – дискретно): 1 N z0 = å z j . N j =1 4. Критерий максимума (Max-Criterion). Чёткое значение выбирается произвольно среди множества элементов, доставляющих максимум С, т. е. z 0 Î ìí z : C( z ) = max C(u )üý. u î þ 5. Высотная дефазификация (Height defuzzification). Элемент области определения W , для которых значения функции принадлежности меньше, чем некоторый уровень a в расчёт не принимаются, и чёткое значение рассчитывается по формуле
50
Потапов Д.К. Неклассические логики z0 =
ò zC( z )dz
Ca
ò C( z)dz
,
Ca
где C a – нечёткое множество a - уровня (см. выше).
2.5.7. Нисходящие нечёткие выводы Рассмотренные до сих пор нечёткие выводы представляют собой восходящие выводы от предпосылок к заключению. В последние годы в диагностических нечётких системах начинают применяться нисходящие выводы. Рассмотрим механизм подобного вывода на примере. Возьмём упрощённую модель диагностики неисправности автомобиля с именами переменных: x1 – неисправность аккумулятора; x2 – отработка машинного масла; y1 – затруднения при запуске; y2 – ухудшение цвета выхлопных газов; y3 – недостаток мощности. Между xi и yj существуют нечёткие причинные отношения rij = xi ® y j , которые можно представить в виде некоторой матрицы R с элементами rij Î [0,1]. Конкретные входы (предпосылки) и выходы (заключения) можно рассматривать как нечёткие множества А и В на пространствах X и Y. Отношения этих множеств можно обозначить как B = A o R, где, как и раньше, знак « o » обозначает правило композиции нечётких выводов. В данном случае направление выводов является обратным к направлению выводов для правил, т.е. в случае диагностики имеется (задана) матрица R (знания эксперта), наблюдаются выходы B (или симптомы) и определяются входы А (или факторы). Пусть знания эксперта-автомеханика имеют вид é0,9 0,1 0,2 ù R = êë0,6 0,5 0,5úû, в результате осмотра автомобиля его состояние можно оценить как B = 0,9 / y1 + 0,1 / y 2 + 0,2 / y3 . Требуется определить причину такого состояния: A = a1 / x1 + a 2 / x 2 . Отношение введённых нечётких множеств можно представить в виде é0,9 0,1 0, 2 ù a2 ] o ê ú, ë0,6 0,5 0,5û либо, транспонируя, в виде нечётких векторов-столбцов: é 0,9ù é0,9 0,6ù ê 0,1ú = ê 0,1 0,5 ú o éa1 ù. ê ú ê ú êa ú êë0,2úû êë0,2 0,5úû ë 2 û При использовании (max-min)-композиции последнее соотношение преобразуется к виду 0,9 = (0,9 Ù a1 ) Ú (0,6 Ù a 2 ),
[0,9
0,1 0, 2] = [a1
0,1 = (0,1 Ù a1 ) Ú (0,5 Ù a 2 ), 0,2 = (0,2 Ù a1 ) Ú (0,5 Ù a 2 ). 51
Глава II. Нечёткая информация и выводы При решении данной системы заметим прежде всего, что в первом уравнении второй член правой части не влияет на правую часть, поэтому 0,9 = 0,9 Ù a1 , a1 ³ 0,9. Из второго уравнения получим: 0,1 ³ 0,5 Ù a 2 , a 2 £ 0,1. Полученное решение удовлетворяет третьему уравнению, таким образом имеем: 0,9 £ a1 £ 1,0, 0 £ a 2 £ 0,1, т.е. лучше заменить аккумулятор (a1 – параметр неисправности аккумулятора, а2 – параметр отработки машинного масла). На практике в задачах, подобных рассмотренной, количество переменных может быть существенным, могут одновременно использоваться различные композиции нечётких выводов, сама схема выводов может быть многокаскадной. Общих методов решения подобных задач в настоящее время, по-видимому, не существует.
2.6. Пример: нечёткий регулятор Приведём ещё один пример использования аппарата нечёткой логики, на этот раз – в задаче управления. Рассмотрим замкнутую систему регулирования, представленную на рис. 2.15, где через О обозначен объект управления, через Р – регулятор, а через и, у, е, х – соответственно, входной сигнал системы, её выходной сигнал, сигнал ошибки (рассогласования), поступающий на вход регулятора, и выходной сигнал регулятора. В рассматриваемой системе регулятор вырабатывает управляющий сигнал х в соответствии с выбранным алгоритмом регулирования, например, пропорционально сигналу ошибки, либо её
Рис. 2.9. Структура замкнутой системы управления интегралу и т.п. Покажем, что в данном случае для выработки такого сигнала применимы рассмотренные выше методы аппарата нечёткой логики. Предположим, что функции регулятора выполняет микроконтроллер, при этом аналоговый сигнал е ограничен диапазоном [-1, 1] и преобразуется в цифровую форму аналогоцифровым преобразователем (АЦП) с дискретностью 0,25, а выходной сигнал регулятора х формируется с помощью цифроаналогового преобразователя и имеет всего 5 уровней: -1, -0,5, 0, 0,5, 1. Принимая во внимание данные уровни, введём лингвистические переменные: A1: большой положительный, А2: малый положительный, A3: нулевой, А4: малый отрицательный, А5: большой отрицательный, и на дискретном множестве возможных значений сигнала рассогласования е определим функции принадлежности так, как это приведено в табл. 2.4. Предположим, далее, что функционирование регулятора определяется следующими правилами (надо сказать, типичными, для задачи управления): П1: если е=А3 и De =А3, то х=0, П2: если е=А2 и De =А2, то x=-0,5, 52
Потапов Д.К. Неклассические логики П3: если е=А4 и De =А4, то x=1, П4: если e=А1 и De =А1, то x=-1, где De – первая разность сигнала ошибки в текущий дискретный момент времени. Таблица 2.4. Значения функций принадлежности А1(е) А2(е)
-1 0 0
А3(е)
0
-0,75 -0,5 0 0 0 0
-0,25 0 0,25 0,5 0,75 1 0 0 0 0,3 0,7 1 0 0,3 0,7 1 0,7 0,3
0
0,3
0,7
1
0,7
0,3
0
0
А4(е) 0,3
0,7
1
0,7
0,3
0
0
0
0
А5(е)
0,7
0,3
0
0
0
0
0
0
1
Заметим, что набор правил может быть, вообще говоря, и каким-то другим. Если, например, используется упрощённый алгоритм нечёткого вывода, то при значениях, скажем, е=0,25 и De =0,5 имеем: a1 = min( 0,7;0,3) = 0,3 и х1=0, a 2 = min( 0,7;1) = 0,7 и х2=-0,5, a 3 = min( 0;0) = 0 и х3=1, a 4 = min( 0;0,3) = 0 и х4=-1, и выход регулятора
0,3 × 0 + 0,7 × (-0,5) + 0 × 1 + 0 × (-1) - 0,35 = = -0,35. 0,3 + 0,7 + 0 + 0 1 Аналогичным образом значения выходного сигнала регулятора рассчитываются при других значениях е и De . Отметим, что при проектировании подобных («нечётких») peгуляторов основным (и не формализуемым) этапом является задание набора нечётких правил. Другие аспекты: выбор формы функции принадлежности, алгоритма приведения к чёткости и т.п. представляются задачами более простыми. x=
2.7. Эффективность систем принятия решений, использующих методы нечёткой логики Возможность использования аппарата нечёткой логики базируется на следующих результатах. 1. В 1992 г. Wang показал, что нечёткая система, использующая набор правил Пi: если x i есть Ai и yi есть B i, тогда z i есть Ci , i=1,2,…,n, при: 1) гауссовских функциях принадлежности 1 æ x -a i1 ö ÷ - çç 2 è b i1 ÷ø
2
1 æ y -a i 2 - çç 2è bi 2
ö ÷ ÷ ø
2
1 æ z -a i 3 ö ÷ - çç 2 è b i 3 ÷ø
A i ( x) = e , Bi ( y) = e , C i ( z) = e 2) композиции в виде произведения (A i ( x ) and B i ( y )) = A i ( x)B i ( y ); 3) импликации в форме Larsen (A i ( x ) and B i ( y )) ® C i ( z ) = A i ( x )B i ( y )C i ( z ); 4) центроидном методе приведения к чёткости
53
2
.
Глава II. Нечёткая информация и выводы n
z0 =
åa A B i =1 n
i
i
åA B i
i =1
i
,
i
где a i – центры C i ; также является универсальным аппроксиматором, т.е. может аппроксимировать любую непрерывную функцию на компакте U с произвольной точностью (естественно, при n ® ¥ ). Иначе говоря, Wang доказал теорем у: для каждой вещественной непрерывной функции g, заданной на компакте U, и для произвольного e > 0 существует нечёткая экспертная система, формирующая выходную функцию f (x ) такую, что sup g ( x) - f ( x ) £ e , где || ∙ || – символ принятого расстояния между функциями. xÎU
2. В 1995 г. Castro показал, что логический контроллер Mamdani при: 1) симметричных треугольных функциях принадлежности: ì1 - ai - x , если ai - x £ a i , ï A i ( x) = í a i ï0, в противном случае, î ì1 - bi - y , если bi - y £ b i , ï bi Bi ( y) = í ï0, в противном случае, î ì1 - ci - z , если ci - z £ g i , ï Сi ( z) = í g i ï0, в противном случае; î 2) композиции с использованием операции min: (A i ( x) and B i ( y )) = min( A i ( x )B i ( y )); 3) импликации в форме Mamdani и центроидного метода приведения к чёткости: n
z0 =
åc i =1 n
i
min( A i ( x)B i ( y ))
å min( A ( x)B ( y )) i
i =1
,
i
где ci – центры C i ; также является универсальным аппроксиматором. Вообще говоря, системы с нечёткой логикой целесообразно применять для сложных процессов, когда нет простой математической модели; если экспертные знания об объекте или о процессе можно сформулировать только в лингвистической форме. Данные системы применять нецелесообразно, когда требуемый результат может быть получен каким-либо другим (стандартным) путём, или когда для объекта или процесса уже найдена адекватная и легко исследуемая математическая модель. Отметим, что основные недостатки систем с нечёткой логикой связаны с тем, что: • исходный набор постулируемых нечётких правил формулируется экспертомчеловеком и может оказаться неполным или противоречивым; • вид и параметры функций принадлежности, описывающих входные и выходные переменные системы, выбираются субъективно и могут оказаться не вполне отражающими реальную действительность.
54
Потапов Д.К. Неклассические логики
Глава III. Пакет Fuzzy Logic Toolbox 3.1. Назначение и возможности пакета Fuzzy Logic Toolbox Пакет Fuzzy Logic Toolbox (пакет нечёткой логики) – это совокупность прикладных программ, относящихся к теории размытых или нечётких множеств и позволяющих конструировать так называемые нечёткие экспертные и/или управляющие системы. Основные возможности пакета: · построение системы нечёткого вывода (экспертных систем, регуляторов, аппроксиматоров зависимостей); · построение адаптивных нечётких систем (гибридных нейронных сетей); · интерактивное динамическое моделирование в Simulink. Пакет позволяет работу: · в режиме графического интерфейса; · в режиме командной строки; · с использованием блоков и примеров пакета Simulink.
3.2. Графический интерфейс Fuzzy Logic Toolbox 3.2.1. Состав графического интерфейса В состав программных средств Fuzzy Logic Toolbox входят следующие основные программы, позволяющие работать в режиме графического интерфейса: · редактор нечёткой системы вывода Fuzzy Inference System Editor (FIS Editor или FIS-редактор) вместе со вспомогательными программами – редактором функций принадлежности (Membership Function Editor), редактором правил (Rule Editor), просмотрщиком правил (Rule Viewer) и просмотрщиком поверхности отклика (Surface Viewer); · редактор гибридных систем (ANFIS Editor, ANFIS-редактор); · программа нахождения центров кластеров (программа Clustering – кластеризация). Набор данных программ предоставляет пользователю максимальные удобства для создания, редактирования и использования различных систем нечёткого вывода.
3.2.2. Построение нечёткой аппроксимирующей системы Командой (функцией) Fuzzy из режима командной строки запускается основная интерфейсная программа пакета Fuzzy Logic – редактор нечёткой системы вывода (Fuzzy Inference System Editor, FIS Editor, FIS-редактор). Вид открывающегося при этом окна приведён на рис. 3.1.
Рис. 3.1. Вид окна FIS Editor 55
Глава III. Пакет Fuzzy Logic Toolbox Главное меню редактора содержит позиции: File – работа с файлами моделей (их создание, сохранение, считывание и печать); Edit – операции редактирования (добавление и исключение входных и выходных переменных); View – переход к дополнительному инструментарию. Представляется целесообразным выяснение различных опций и возможностей данного редактора и связанных с ним других программ изучить на каком-либо конкретном примере. Попробуем сконструировать нечёткую систему, отображающую зависимость между переменными x и y , заданную с помощью табл. 3.1 (легко видеть, что представленные в таблице данные отражают зависимость y = x 2 ). Таблица 3.1. Значения x и y x y
-1 1
-0.6 0.36
0 0
0.4 0.16
1 1
Требуемые действия отобразим следующими пунктами. 1. В позиции меню File выбираем опцию New FIS …►Sugeno (новая система типа Sugeno), при этом в блоке, отображаемом белым квадратом, в верхней части окна редактора появится надпись Untitled2 (sugeno). 2. Щёлкнем левой кнопкой мыши по блоку, озаглавленному input1 (вход1). Затем в правой части редактора в поле, озаглавленном Name (Имя), вместо input1 введём обозначение нашего аргумента, т.е. x. Обратим внимание, что если теперь сделать где-нибудь (вне блоков редактора) однократный щелчок мыши, то имя отмеченного блока изменится на x; то же достигается нажатием после ввода клавиши Enter. 3. Дважды щёлкнем по этому блоку. Перед нами откроется окно редактора функций принадлежности – Membership Function Editor (см. рис. 3.2). Войдем в позицию меню Edit данного редактора и выберем в нём опцию Add MFs… (Add Membership Functions – Добавить функций принадлежности). При этом появится диалоговое окно (рис. 3.3), позволяющее задать тип (MF type) и количество (Number of MFs) функций принадлежности (в данном случае всё относится к входному сигналу, т.е. к переменной x ). Выберем гауссовы функции принадлежности (gaussmf), а их количество зададим равным пяти – по числу значений аргумента в табл. 3.1. Подтвердим ввод информации нажатием кнопки ОК, после чего произойдёт возврат к окну редактора функций принадлежности.
Рис. 3.2. Окно редактора функций принадлежности 56
Потапов Д.К. Неклассические логики
Рис. 3.3. Диалоговое окно задания типа и количества функций принадлежности 4. В поле Range (Диапазон) установим диапазон изменения x от –1 до 1, т.е. диапазон, соответствующий табл. 3.1. Щёлкнем затем левой кнопкой мыши где-нибудь в поле редактора (или нажмём клавишу ввода Enter). Обратим внимание, что после этого произойдет соответствующее изменение диапазона в поле Display Range (Диапазон дисплея). 5. Обратимся к графикам заданных нами функций принадлежности, изображенным в верхней части окна редактора функций принадлежности. Заметим, что для успешного решения поставленной задачи необходимо, чтобы ординаты максимумов этих функций совпадали с заданными значениями аргумента x . Для левой, центральной и правой функций такое условие выполнено, но две другие необходимо «подвинуть» вдоль оси абсцисс. «Передвижка» делается весьма просто: подводим курсор к нужной кривой и щёлкаем левой кнопкой мыши. Кривая выбирается, окрашиваясь в красный цвет, после чего с помощью курсора её и можно подвинуть в нужную сторону (более точную установку можно провести, изменяя числовые значения в поле Params (Параметры) – в данном случае каждой функции принадлежности соответствуют два параметра, при этом первый определяет размах кривой, а второй – положение её центра). Для выбранной кривой, кроме этого, в поле Name можно изменять имя (завершая ввод каждого имени нажатием клавиши Enter). Проделаем требуемые перемещения кривых и зададим всем пяти кривым новые имена, например: · cамой левой – bn, · следующей – n, · центральной – z, · следующей за ней справа – p, · самой правой – bp. Нажмём кнопку Close и выйдем из редактора функций принадлежности, возвратившись при этом в окно редактора нечёткой системы (FIS Editor). 6. Сделаем однократный щелчок левой кнопкой мыши по голубому квадрату (блоку), озаглавленному output1 (выход1). В окошке Name заменим имя output1 на y (как в пункте 2). 7. Дважды щёлкнем по отмеченному блоку и перейдем к программе – редактору функций принадлежности. В позиции меню Edit выберем опцию Add MFs… Появляющееся диалоговое окно вида рис. 3.3 позволяет задать теперь в качестве функций принадлежности только линейные (linear) или постоянные (constant) – в зависимости от того, какой алгоритм Sugeno (1-го или 0-го порядка) мы выбираем. В рассматриваемой задаче необходимо выбрать постоянные функции принадлежности с общим числом 4 (по числу различных значений y в табл. 3.1). Подтвердим введённые данные нажатием кнопки ОК, после чего произойдет возврат в окно редактора функций принадлежности. 8. Обратим внимание, что здесь диапазон (Range) изменения, устанавливаемый по умолчанию – [0, 1], менять не нужно. Изменим лишь имена функций принадлежности (их графики при использовании алгоритма Sugeno для выходных переменных не приводятся), 57
Глава III. Пакет Fuzzy Logic Toolbox например, задав их как соответствующие числовые значения y , т.е. 0, 0.16, 0.36, 1; одновременно эти же числовые значения введём в поле Params (рис. 3.4). Затем закроем окно нажатием кнопки Close и вернёмся в окно FIS-редактора.
Рис. 3.4. Параметры функций принадлежности переменной y 9. Дважды щёлкнем левой кнопкой мыши по среднему (белому) блоку, при этом раскроется окно еще одной программы – редактора правил (Rule Editor). Введём соответствующие правила. При вводе каждого правила необходимо обозначать соответствие между каждой функцией принадлежности аргумента x и числовым значением y. Кривая, обозначенная нами bn, соответствует x = -1 , т.е. y = 1. Выберем, поэтому в левом поле (с заголовком x is) bn, а в правом 1 и нажмём кнопку Add rule (Добавить правило). Введённое правило появится в окне правил и будет представлять собой запись: 1. If ( x is bn) then ( y is 1) (1). Аналогично поступим для всех других значений x , в результате чего сформируется набор из 5 правил (см. рис. 3.5). Закроем окно редактора правил и возвратимся в окно FIS-редактора. Построение системы закончено и можно начать эксперименты по её исследованию. Заметим, что большинство опций выбиралось нами по умолчанию.
Рис. 3.5. Окно редактора правил 58
Потапов Д.К. Неклассические логики 10. Предварительно сохраним на диске (используя пункты меню File/Export►To Disk…) созданную систему под каким-либо именем, например, Proba. 11. Выберем позицию меню Edit. Как видно из выпадающего при этом подменю, с помощью пунктов Membership Functions… и Rules… можно совершить переход к двум выше рассмотренным программам – редакторам функций принадлежности и правил (то же можно сделать и нажатием клавиш Ctrl+2 или Ctrl+3), но сейчас нас будут интересовать два других пункта меню View – Rules (Просмотр правил) и Surface (Просмотр поверхности). Выберем пункт Rules меню View, при этом откроется окно (см. рис. 3.6) ещё одной программы – просмотра правил (Rule Viewer).
Рис. 3.6. Окно просмотра правил 12. В правой части окна в графической форме представлены функции принадлежности аргумента x , в левой – переменной выхода y с пояснением механизма принятия решения. Красная вертикальная черта, пересекающая графики в правой части окна, которую можно перемещать с помощью курсора, позволяет изменять значения переменной входа (это же можно делать, задавая числовые значения в поле Input (Вход)), при этом соответственно изменяются значения y в правой части окна. Зададим, например, x = 0.5 в поле Input и нажмём затем клавишу ввода (Enter). Значение y сразу изменится и станет равным 0.201. Таким образом, с помощью построенной модели и окна просмотра правил можно решать задачу интерполяции, т.е. задачу, решение которой и требовалось найти. Изменение аргумента путём перемещения красной вертикальной линии очень наглядно демонстрирует, как система определяет значения выхода. 13. Закроем окно просмотра правил и выбором пункта меню View/Surface перейдём к окну просмотра поверхности отклика (выхода), в нашем случае – к просмотру кривой y (x) (см. рис. 3.7). Видно, что смоделированное системой по таблице данных (табл. 3.1) отображение не очень-то напоминает функцию x 2 . Ну что ж, ничего удивительного в этом нет: число экспериментальных точек невелико, да и параметры функций принадлежности (для x ) выбраны, скорее всего, неоптимальным образом. Ниже мы рассмотрим возможность улучшения качества подобной модели.
59
Глава III. Пакет Fuzzy Logic Toolbox
Рис. 3.7. Окно просмотра поверхности отклика В заключение рассмотрения примера отметим, что с помощью вышеуказанных программ-редакторов на любом этапе проектирования нечёткой модели в неё можно внести необходимые коррективы, вплоть до задания какой-либо особенной пользовательской функции принадлежности. Из опций, устанавливаемых в FIS-редакторе по умолчания при использовании алгоритма Sugeno, можно отметить: · логический вывод организуется с помощью операции умножения (prod); · композиция – с помощью операции логической суммы (вероятностного ИЛИ, probor); · приведение к чёткости – дискретным вариантом центроидного метода (взвешенным средним, wtaver). Используя соответствующие поля в левой нижней части окна FIS-редактора, данные опции можно, при желании, изменить.
3.2.3. Построение экспертной системы: сколько дать на «чай»? Рассмотрим теперь методику построения нечёткой экспертной системы, которая должна помочь пользователю с ответом на вопрос: сколько дать «на чай» официанту за обслуживание в ресторане? Основываясь на каких-то устоявшихся обычаях и интуитивных представлениях, примем, что задача о чаевых может быть описана следующими предложениями. 1. Если обслуживание плохое или еда подгоревшая, то чаевые – малые. 2. Если обслуживание хорошее, то чаевые – средние. 3. Если обслуживание отличное или еда превосходная, то чаевые – щедрые. Качество обслуживания и еды будем оценивать по 11-балльной системе (0 – наихудшая оценка, 10 – наилучшая). Будем предполагать, далее, что малые чаевые составляют около 5% от стоимости обеда, средние – около 15% и щедрые – примерно 25%. Заметим, что представленной информации, в принципе, достаточно для проектирования нечёткой экспертной системы. Такая система будет иметь 2 входа (которые условно можно назвать «сервис» и «еда»), один выход («чаевые»), три правила типа «если… то» (в соответствии с тремя приведёнными предложениями) и по три значения (соответственно, 0 60
Потапов Д.К. Неклассические логики баллов, 5 баллов, 10 баллов и 5%, 15%, 25%) для центров функций принадлежности входов и выхода. Построим данную систему, используя алгоритм вывода Mamdani и, как в предыдущем примере, описывая требуемые действия по пунктам. 1. Командой fuzzy запускаем FIS-редактор. По умолчанию, исходный алгоритм вывода – типа Mamdani (о чём говорит надпись в центральном белом блоке) и здесь никаких изменений не требуется, но в системе должно быть два входа, поэтому через пункт меню Edit/Add Variable…►Input добавляем в систему этот второй вход (в окне редактора появляется второй жёлтый блок с именем input2). Делая далее однократный щелчок левой кнопкой мыши по блоку input1, меняем в поле имени его имя на «service» (сервис), завершая ввод нового имени нажатием клавиши Enter. Аналогичным образом устанавливаем имя «food» (еда) блоку input2 и «tips»(чаевые) – выходному блоку (справа вверху) output1. Присвоим сразу же и имя всей системе, например «Tips» (по-английски это и есть чаевые), выполнив это через пункт меню File/Export ► To Workspace… (Сохранить в рабочем пространстве как…). Вид окна редактора после указанных действий приведён на рис. 3.8.
Рис. 3.8. Вид окна FIS-редактора после задания структуры системы 2. Зададим теперь функции принадлежности переменных. Напомним ещё раз, что программу-редактор функций принадлежности можно открыть тремя способами: · через пункт меню Edit/Membership Functions…, · двойным щелчком левой кнопки мыши по иконке, отображающей соответствующую переменную, · нажатием клавиш Ctrl+2. Любым из приведённых способов перейдём к данной программе. Задание и редактирование функций принадлежности начнём с переменной «service». Сначала в полях Range и Display Range установим диапазон изменения и отображения этой переменной – от 0 до 10 (баллов), подтверждая ввод нажатием клавиши Enter. Затем через пункт меню Edit/Add MFs… перейдём к диалоговому окну вида рис. 3.3 и зададим в нём функции принадлежности гауссова типа (gaussmf) c общим числом 3. Нажмём кнопку ОК и возвратимся в окно редактора функций принадлежности. Не изменяя размах и положение заданных функций, заменим только их имена на «bad» (плохой), «good» (хороший), «excellent» (отличный) (как в пункте 5 предыдущего примера). 61
Глава III. Пакет Fuzzy Logic Toolbox Щелчком левой кнопки мыши по иконке «food» войдём в окно редактирования функций принадлежности для этой переменной. Зададим сначала диапазон её изменения от 0 до 10, а затем, поступая как ранее, зададим две функции принадлежности трапецеидальной формы (trapmf) с параметрами, соответственно, [0 0 1 3] и [7 9 10 10] и именами «burning» (подгоревшая) и «fantastic» (превосходная). Для выходной переменной «tips» укажем сначала диапазон изменения – от 0 до 30, потом зададим три функции принадлежности треугольной формы (trimf) с именами «small» (малые), «middle» (средние), «large» (щедрые) так, как это представлено на рис. 3.9. Заметим, что можно, разумеется, задать и какие-либо другие функции или выбрать их другие параметры.
Рис. 3.9. Функции принадлежности переменной «tips» 3. Перейдём к конструированию правил. Для этого выберем пункт меню Edit/Rules… Далее ввод правил производится так же, как в п. 9 предыдущего примера, и в соответствии с предложениями, описывающими задачу. Заметим, что в первом и третьем правилах в качестве «связки» в предпосылках правила необходимо использовать не «И» (and), а «ИЛИ» (or); при вводе второго правила, где отсутствует переменная «food», для неё выбирается опция none. Итоговый набор правил отображён рис. 3.10 и выглядит следующим образом: 1. If (service is bad) or (food is burning) then (tips is small) (1) 2. If (service is good) then (tips is middle) (1) 3. If (service is excellent) or (food is fantastic) then (tips is large) (1)
Рис. 3.10. Итоговый набор правил в задаче о чаевых 62
Потапов Д.К. Неклассические логики Такая (подробная, verbose) запись представляется достаточно понятной; единица в скобках после каждого правила указывает его «вес» (Weight), т.е. значимость правила. Данный вес можно менять, используя соответствующее поле в левой нижней части окна редактора правил. Правила представимы и в других формах: символической (symbolic) и индексной (indexed), при этом переход от одной формы к другой происходит через опции пункта меню редактора правил Options/Format. Вот как выглядят рассмотренные правила в символической форме: 1. (service= =bad)|(food= =burning) Þ (tips=small) (1) 2. (service= =good) Þ (tips=middle) (1) 3. (service= =excellent)|(food= =fantastic) Þ (tips=large) (1) По-видимому, здесь тоже понятно всё. Наконец, самый сжатый формат представления правил – индексный – является тем форматом, который в действительности используется программой. В этом формате приведённые правила выглядят так: 1 1, 1 (1): 2 2 0, 2 (1): 2 3 2, 3 (1): 2 Здесь первая колонка относится к первой входной переменной (соответственно, первое, второе или третье возможное значение), вторая – ко второй, третья (после запятой) – к выходной переменной, цифра в скобках показывает вес правила и последняя цифра (после двоеточия) – на тип «связки» (1 для «И», 2 для «ИЛИ»). На этом, собственно, конструирование экспертной системы закончено. Сохраним её на диске под выбранным именем (Tips). 4. Самое время теперь проверить систему в действии. Откроем (через пункт меню View/Rules) окно просмотра правил и установим значения переменных: service=0 (т.е. никуда негодный), food=10 (т.е. превосходная). Увидим ответ: tips=15 (т.е. средние). Ну что ж, с системой не поспоришь, надо платить (рис. 3.11). Можно проверить и другие варианты. В частности (может быть, не без удивления), выяснится, что нашей системой обслуживание ценится больше, чем качество еды: при наборе «service=10, food=3» система советует определить размер чаевых в 23.9%, в то время как набору «service=3, food=10» размер чаевых по рекомендации системы – 16.6% (от стоимости обеда). Впрочем, ничего удивительного здесь нет: это мы сами (не особенно подозревая об этом) заложили в систему соответствующие знания в виде совокупности приведённых правил.
Рис. 3.11. Окно просмотра правил в задаче о чаевых 63
Глава III. Пакет Fuzzy Logic Toolbox Подтверждением отмеченной зависимости выходной переменной от входных может служить вид поверхности отклика, который представляется при выборе пункта меню View/Surface (рис. 3.12); обратите внимание, что с помощью мышки график можно поворачивать во все стороны.
Рис. 3.12. Графический вид зависимости выходной переменной от входных В открывшемся окне, меняя имена переменных в полях ввода (X(input) и Y(input)), можно задать и просмотр одномерных зависимостей, например «tips» от «food» (рис. 3.13).
Рис. 3.13. Одномерная зависимость размера чаевых от качества еды
3.2.4. Экспорт и импорт результатов Когда вы сохраняете созданную вами нечёткую систему, используя пункты меню File/Export►To Disk…, на диске создаётся текстовый (ASCII) файл достаточно простого 64
Потапов Д.К. Неклассические логики формата с расширением .fis, который можно просматривать, при необходимости – редактировать вне системы MATLAB, а также использовать повторно при последующих сеансах работы с системой. Однако сохранение с использованием пунктов File/Export►To Workspace… на самом деле только «легализует» созданную вами систему (под каким-либо именем) в среде MATLAB в течение текущего сеанса работы и не допускает её повторного использования в других сеансах.
3.2.5. Создание пользовательских функций принадлежности Если по каким-либо причинам вас не устраивает ни одна из встроенных функций принадлежности, вы можете создать и использовать собственную подходящую функцию. Такая функция должна быть создана как М–файл (New M–File) со значениями от 0 до 1 и с числом аргументов не более 16. Приведём этапы создания данной функции под некоторым именем custmf. 1. Создаётся соответствующий М–файл с именем custmf.m. 2. Выбирается пункт Edit/Add Custom MF… (Редактирование/Добавить пользовательскую функцию принадлежности) в меню редактора функций принадлежности. 3. В поле M-File function name появляющегося диалогового окна Add customized membership function вводится имя созданного М–файла (custmf). 4. В поле Parameter list данного окна вводятся необходимые числовые параметры. 5. Наконец, в поле MF name (Имя функции принадлежности) вводится какое-либо (уникальное) имя задаваемой функции (например, custmf). 6. Указанный ввод подтверждается нажатием кнопки ОК (см. рис. 3.14).
Рис. 3.14. Окно задания функции принадлежности пользователя Ниже приведён пример М-файла некоторой пользовательской функции принадлежности дискретного типа, имеющей имя testmf1 и зависящей от 8 числовых параметров (каждый из диапазона [0, 10]): function out=testmf1(x, params) for i=1:length(x) if x(i)<params(1) y(i)=params(1); elseif x(i)<params(2) y(i)=params(2); elseif x(i)<params(3) y(i)=params(3); elseif x(i)<params(4) y(i)=params(4); elseif x(i)<params(5) 65
Глава III. Пакет Fuzzy Logic Toolbox y(i)=params(5); elseif x(i)<params(6) y(i)=params(6); elseif x(i)<params(7) y(i)=params(7); elseif x(i)<params(8) y(i)=params(8); else y(i)=0; end end out=.1*y/
3.3. Графический интерфейс гибридных систем Графический интерфейс гибридных (нечётких) нейронных систем вызывается функцией (из режима командной строки) anfisedit. Исполнение функции приводит к появлению окна редактора гибридных систем (ANFIS Editor, ANFIS-редактор), вид которого приведён на рис 3.15.
Рис. 3.15. Окно редактора гибридных систем С помощью данного редактора осуществляется создание или загрузка структуры гибридной системы, просмотр структуры, настройка её параметров, проверка качества функционирования такой системы. Создание структуры, настройка параметров и проверка осуществляются по выборкам (наборам данных) – обучающей (Training data), проверочной (Checking data) и тестирующей (Testing data), которые предварительно должны быть представлены в виде текстовых файлов (с расширением .dat и разделителями-табуляциями), первые колонки которых соответствуют входным переменным, а последняя (левая) – единственной выходной переменной; количество строк в таких файлах равно количеству образцов (примеров). Так, обучающая выборка сформированная по табл. 3.1, представляется в виде
66
Потапов Д.К. Неклассические логики -1 -0.6 0.0 0.4 1
1 0.36 0.00 0.16 1
Строгих рекомендаций по объёмам указанных выборок не существует, по-видимому, лучше всего исходить из принципа «чем больше, тем лучше». Обучающая и проверочная выборки непосредственно задействуются в процессе настройки параметров гибридной сети (проверочная – для выяснения ситуации: нет ли так называемого переобучения сети, при котором ошибка для обучающей последовательности стремится к нулю, а для проверочной – возрастает; впрочем, наличие проверочной выборки не является строго необходимым, оно лишь крайне желательно). Тестовая (или тестирующая выборка) применяется для проверки качества функционирования настроенной (обученной) сети. Поясним пункты меню и опции редактора. Пункты меню File и View, в общем, идентичны аналогичным пунктам FIS-редактора. Пункт меню Edit содержит подпункт – Undo (Отменить выполненное действие). Набор опций Load data (Загрузить данные) в нижней левой части окна редактора включает в себя: · тип (Type) загружаемых данных (для обучения – Training, для тестирования – Testing, для проверки – Checking, демонстрационные – Demo); · место (From), откуда должны загружаться данные (с диска – disk или из рабочей области MATLAB-workspace). К данным опциям относятся две кнопки, нажатие на которых приводит к требуемым действиям – Load Data… (Загрузить данные) и Clear Data (очистить, т.е. стереть введённые данные). Следующая группа опций (в середине нижней части окна ANFIS-редактора) объединена под именем Generate FIS (Создание нечёткой системы вывода). Данная группа включает в себя опции: · загрузку структуры системы с диска (Load from disk); · загрузку структуры системы из рабочей области MATLAB (Load from worksp.); · разбиение (деление) областей определения входных переменных (аргументов) на подобласти – независимо для каждого аргумента (Grid partition); · разбиение всей области определения аргументов (входных переменных) на подобласти – в комплексе для всех аргументов (Sub. clustering), а также кнопку Generate FIS…, нажатие которой приводит к процессу создания гибридной системы с точностью до ряда параметров. Следующая группа опций – Train FIS (Обучение нечёткой системы вывода) – позволяет определить метод «обучения» (Optim. Method) системы (т.е. метод настройки её параметров) – гибридный (hybrid) или обратного распространения ошибки (back-рrора), установить уровень текущей суммарной (по всем образцам) ошибки обучения (Error Tolerance), при достижении которого процесс обучения заканчивается и количество циклов обучения (Epochs), т.е. количество «прогонов» всех образцов (или примеров) обучающей выборки; процесс обучения, таким образом заканчивается либо при достижении отмеченного уровня ошибки обучения, либо при проведении заданного количества циклов. Кнопка Train Now (Начать обучение) процесс обучения, т.е. процесс настройки параметров гибридной сети. В правом верхнем углу окна ANFIS-редактора выдаётся информация (ANFIS Info.) о проектируемой системе: о количестве входов, выходов, функций принадлежности входов; нажатие кнопки Structure (Структура) позволяет увидеть структуру сети. Кнопка С1еаг Plot (Очистить) позволяет стереть все результаты.
67
Глава III. Пакет Fuzzy Logic Toolbox Опции Test FIS в правом нижнем углу окна позволяют провести проверку и тестирование созданной и обученной системы с выводом результатов в виде графиков (соответствующие графики для обучающей выборки – Training data, тестирующей выборки – Testing data и проверочной выборки – Checking data. Кнопка Test Now позволяет запустить указанные процессы. Работу с редактором рассмотрим на примере восстановления зависимости у=х2 по данным табл. 3.1. Предположим, что эти данные сохранены в файле Proba.dat. Создание и проверку системы, как и раньше, проведём по этапам. 1. В окне ANFIS-редактора выберем тип загружаемых данных Training и нажмём кнопку Load data.... В последующем стандартном окне диалога укажем местоположение и имя файла. Его открытие приводит к появлению в графической части окна редактора набора точек, соответствующих введённым данным (рис. 3.16).
Рис. 3.16. Окно ANFIS-редактора после загрузки обучающей выборки 2. В группе опций Generate FIS по умолчанию активизирована опция Grid partition. He будем её изменять и нажмём кнопку Generate FIS…, после чего появится диалоговое окно для задания числа и типов функций принадлежности. Установим 4, gbellmf, linear (рис. 3.17), нажмём кнопку OK. Произойдёт возврат в основное окно ANFIS-редактора. Теперь структура гибридной сети создана, и её графический вид можно просмотреть с помощью кнопки Structure (рис. 3.18).
68
Потапов Д.К. Неклассические логики
Рис. 3.17. Окно задания функций принадлежности
Рис. 3.18. Структура созданной гибридной сети 3. Перейдём к опциям Train FIS. He будем менять задаваемые по умолчанию метод настройки параметров (hybrid – гибридный) и уровень ошибки (0), но количество циклов 69
Глава III. Пакет Fuzzy Logic Toolbox обучения изменим на 40, после чего нажмём кнопку начала процесса обучения (Train Now). Получившийся результат в виде графика ошибки сети в зависимости от числа проведённых циклов обучения (из которого следует, что фактически обучение закончилось после восьмого цикла) представлен на рис. 3.19.
Рис. 3.19. Результат обучения сети 4. Теперь нажатием кнопки Test Now можно начать процесс тестирования обученной сети, но, поскольку использовалась только одна – обучающая – выборка, ничего особенно интересного ожидать не приходится. Действительно, выход обученной системы практически совпадает с точками обучающей выборки (рис. 3.20).
Рис. 3.20. Результат тестирования обученной системы 70
Потапов Д.К. Неклассические логики 5. Сохраним разработанную систему в файл на диске с именем Proba1 (с расширением .fis) и для исследования разработанной системы средствами FIS-редактора из командной строки MATLAB выполним команду fuzzy, а затем через пункты меню File/Import ► From Disk... откроем созданный файл. С созданной системой можно теперь выполнять все приемы редактирования (изменение имён переменных и т.п.) и исследования, которые были рассмотрены выше. Здесь нетрудно, кстати, убедиться, что качество аппроксимации данных существенно не улучшилось – слишком мало данных. Что можно сказать про эффективность использования гибридных систем (и ANFISредактора)? В данном случае может быть только одна выходная переменная, всем правилам приписывается один и тот же единичный вес. Вообще говоря, возникают значительные проблемы при большом (более 5-6) количестве входных переменных. Это – ограничения и недостатки подхода. Его несомненные достоинства: практически полная автоматизация процесса создания нечёткой (гибридной) системы, возможность просмотра сформированных правил и придания им содержательной (лингвистической) интерпретации, что позволяет, кстати говоря, рассматривать аппарат гибридных сетей как средство извлечения знаний из баз данных и существенно отличает данные сети от классических нейронных. Рекомендуемая область применения: построение аппроксиматоров зависимостей по экспериментальным данным, построение систем классификации (в случае бинарной или дискретной выходной переменной), изучение механизма явлений.
3.4. Графический интерфейс программы кластеризации В пакет Fuzzy Logic Toolbox входит ещё одна программа, позволяющая работу в режиме графического интерфейса, – программа Clustering (Кластеризация) выявления центров кластеров, т.е. точек в многомерном пространстве данных, около которых группируются (скапливаются) экспериментальные данные. Выявление подобных центров, надо сказать, является значимым этапом при предварительной обработке данных, поскольку позволяет сопоставить с этими центрами функции принадлежности переменных при последующем проектировании системы нечёткого вывода. Запуск программы Clustering осуществляется командой (функцией) findcluster. В появляющемся окне программы имеется (вверху) главное меню, содержащее достаточно стандартный набор пунктов (File, Edlt, View, Insert, Tools, Desktop, Window, Help) и набор управляющих кнопок и опций (справа). К этим кнопкам относятся: • кнопка загрузки файла данных Load Data…, • кнопка выбора алгоритма кластеризации – Methods, • четыре расположенные ниже кнопки опций алгоритма (их названия меняются в зависимости от выбранного алгоритма), • кнопка начала итеративного процесса нахождения центров кластеров (кластеризации) – Start, • кнопка сохранения результатов кластеризации (Save Center…), • кнопка очистки (стирания) графиков (Clear Plot), • кнопка справочной информации (Info), • кнопка завершения работы с программой (Close). В программе используются два алгоритма выявления центров кластеров: Fuzzy cmeans (который можно перевести как «Алгоритм нечётких центров») и Subtractive clustering («Вычитающая кластеризация»). Если не вдаваться в их детальное теоретическое изложение, а ограничиться выявлением различий на уровне пользователя, то можно отметить, что алгоритм Fuzzy c-means (fcm), являясь, пожалуй, более точным (если понятие точности вообще здесь применимо), для своей работы требует задания таких опций, как число кластеров (кнопка Cluster Num.) и число итераций (кнопка Max Iteration#). Ну, если число итераций ещё можно задать как-то наугад, то ошибка в задании числа кластеров может привести к непри71
Глава III. Пакет Fuzzy Logic Toolbox ятным последствиям. Алгоритм Subtractive clustering (subtractive) менее точен, но и менее требователен к априорной информации; при работе с ним можно сохранить опции, заданные в программе по умолчанию. На рис. 3.21 приведён пример использования программы для файла данных clusterdemo.dat из директории MATLAB704/toolbox/fuzzy/fuzdemos/ при использовании алгоритма subtractive. Заметим, что выводится только двумерное поле рассеяния, но изменяя переменные в соответствующих полях (X-axis и Y-axis), можно «просмотреть» всё многомерное пространство переменных.
Рис. 3.21. Результат работы программы Clustering (центры кластеров окрашены в чёрный цвет)
3.5. Работа с Fuzzy Logic Toolbox в режиме командной строки 3.5.1. Возможности работы в режиме командной строки Пакет Fuzzy Logic располагает большим набором функций, исполняемых из командной строки MATLAB и позволяющих, в принципе, не использовать при работе с системами нечёткого вывода рассмотренные программы графического интерфейса. Все функции делятся на группы: 1) вызова программ графического интерфейса; 2) задания функций принадлежности; 3) создания, редактирования, просмотра, открытия и сохранения систем нечёткого вывода; 4) дополнительные; 5) различные; 6) вызова диалоговых окон интерфейса; 7) блоков Simulink; 8) демонстрации возможностей пакета.
3.5.2. Функции вызова программ графического интерфейса К этой группе относятся функции: fuzzy – вызов FIS-редактора; 72
Потапов Д.К. Неклассические логики mfedit – вызов редактора функций принадлежности; ruleedit – вызов редактора правил; ruleview – вызов программы просмотра правил; surfview – вызов программы просмотра поверхности отклика; anfisedit – вызов ANFIS-редактора, findcluster – вызов программы кластеризации. Использование первых шести функций с аргументом (например, fuzzy(a), где а – имя переменной рабочего пространства, присвоенное системе нечёткого вывода), открывает соответствующую программу с одновременной загрузкой в неё рассматриваемой системы. Напртмер, fuzzy(/D:\Неклассические_логики\Tips.fis/). Функция findcluster(имя_файла) открывает программу кластеризации с одновременной загрузкой указанного файла данных. Например, findcluster(/D:\Неклассические_логики\Proba.dat/).
3.5.3. Задание функций принадлежности В данную группу включены 11 функций. 1. Функция dsigmf. Запись: у = dsigmf(x,[al cl a2 c2]) О п и с а н и е . Задаётся функция принадлежности, определяемая как разность двух сигмоидальных функций. Сигмоидальная функция, как известно, описывается выражением 1 f ( x, a, c ) = 1 + exp( - a( x - c )) и зависит от двух числовых параметров а и с. Описываемая функция, как отмечено, является разностью двух сигмоидальных: f1 ( x, a1 , c1 ) - f 2 ( x, a 2 , c 2 ), и зависит от четырёх параметров а1, с1, a2, с2 (вектора параметров [al cl a2 с2]). Пример (см. рис. 3.22). » х = 0:0.1:10; » y = dsigmf(x,[5 2 5 7]); » plot(x,y) » xlabel(/dsigmf, P = [5 2 5 7]/)
Рис. 3.22. Вид функции dsigmf(x,[5 2 5 7]) 73
Глава III. Пакет Fuzzy Logic Toolbox 2. Функция gauss2mf. Запись: у = gauss2mf(x,[sig1 c1 sig2 c2]) О п и с а н и е . Задаётся функция принадлежности, являющаяся разностью двух гауссовых функций, определяемая соотношением f ( x, s 1 , с1 , s 2 , с 2 ) = exp(- ( x - c1 ) 2 / s 1 2 ) - exp( -( x - c 2 ) 2 / s 2 2 ) и зависящую от четырёх параметров (s 1 , c1 , s 2 , c 2 ) или вектора параметров [sigl cl sig2 c2]. Пример (см. рис. 3.23). » х= (0:0.1:10)/; » y1 = gauss2mf(x, [2 4 1 8]); » у2 = gauss2mf(x, [2 5 1 7]); » у3 = gauss2mf(x, [2 6 1 6]); » y4 = gauss2mf(x, [2 7 1 5]); » y5 = gauss2mf(x, [2 8 1 4]); » plot(x, [y1 у2 у3 у4 у5]); » set(gcf, /name/, /gauss2mf/, /numbertitle/, /off/);
Рис. 3.23. Семейство кривых, определяемых функцией gauss2mf 3. Функция gaussmf. Запись: у = gaussmf(x,[sig с]) О п и с а н и е . Задаётся функция принадлежности гауссова типа, зависящая от двух параметров ([sig c]). Пример (см. рис. 3.24). » х = 0:0.1:10; » у = gaussmf(x,[2 5]); » plot(x,y) » xlabel(/gaussmf, P=[2 5]/)
74
Потапов Д.К. Неклассические логики
Рис. 3.24. Функция принадлежности гауссовой кривой 4. Функция gbellmf. Запись: у = gbellmf(x,params) О п и с а н и е . Задаётся функция принадлежности так называемого обобщённого колоколообразного типа с аналитическим описанием, зависящим от трёх числовых параметров: 1 f ( x, a, b, c ) = . (1 + ( x - c) / a )2b Пример (cм. рис. 3.25). » х = 0:0.1:10; » y = gbellmf(x,[2 4 6]); » plot(x,y) » xlabel(/gbellmf, P = [2 4 6]/)
Рис. 3.25. График обобщённой колоколообразной функции 75
Глава III. Пакет Fuzzy Logic Toolbox 5. Функция pimf. Запись: у = pimf(x,[a b с d]) О п и с а н и е . Задаётся так называемая π-образная функция принадлежности, получившая своё название из-за своеобразной формы. Функция вычисляется с использованием сплайн аппроксимации по четырём точкам, задаваемым вектором параметров. Параметры а и d определяют основание кривой, а параметры b и с – положение плоской вершины. Пример (см. рис. 3.26). » х = 0:0.1:10; » y = pimf(x,[1 4 5 10]); » plot(x,y) » xlabel(/pimf, P=[l 4 5 10]/)
Рис. 3.26. График π-образной функции 6. Функция psigmf. Запись: у = psigmf(x,[al cl a2 c2]) О п и с а н и е . Задаётся функция принадлежности, определяемая как произведение двух сигмоидальных функций f1 ( x, a1 , c1 ) × f 2 ( x, a 2 , c 2 ), и зависящая от четырёх параметров a1, с1, a2, c2 (вектора параметров [al cl а2 с2]). Пример (см. рис. 3.27). » х = 0:0.1:10; » y = psigmf(x,[2 3 -5 8]); » plot(x,y) » xlabel(/psigmf, P = [2 3 -5 8]/)
76
Потапов Д.К. Неклассические логики
Рис. 3.27. Пример использования функции psigmf 7. Функция smf. Запись: у = smf(x,[a b]) О п и с а н и е . Задаётся зависящая от двух параметров так называемая S-образная функция принадлежности. Параметры а и b определяют диапазон значений аргумента, где функция возрастает. Пример (см. рис. 3.28). » х = 0:0.1:10; » y = smf(x,[l 8]); » plot(x,y) » xlabel(/smf, P = [1 8]/)
Рис. 3.28. График S-образной функции 77
Глава III. Пакет Fuzzy Logic Toolbox 8. Функция sigmf. Запись: у = sigmf(x,[а с]) О п и с а н и е . Задаётся так называемая сигмоидальная функция принадлежности, определяемая выражением, приведённым выше и зависящим от двух параметров. Пример (см. рис. 3.29). » х = 0:0.1:10; » y = sigmf(x,[2 4]); » plot(x,y) » xlabel(/sigmf, P = [2 4]/)
Рис. 3.29. График сигмоидальной функции 9. Функция trapmf. Запись: у = trapmf(x,[a b с d]) О п и с а н и е . Задаётся так называемая трапецеидальная функция принадлежности, зависящая от четырёх параметров и определяемая формулой ì0, x £ a ï ïx - a , a £ x £ b ïb - a ï f ( x, a, b, c, d ) = í1, b £ x £ с , ï ïd - x , c £ x £ d ïd - c ï0, d £ x î при этом параметры a и d определяют основание кривой, а, b и с – положение вершины. Пример (см. рис. 3.30). » х = 0:0.1:10; » у = trapmf(x,[1 5 7 8]); » plot(x,y) » xlabel(/trapmf, P = [1 5 7 8]/) 78
Потапов Д.К. Неклассические логики
Рис. 3.30. Трапецеидальная функция принадлежности 10. Функция trimf. Запись: у = trimf(x,params) или y = trimf(x,[a b с]) О п и с а н и е . Задаётся зависящая от трёх параметров функция принадлежности треугольной формы, при этом параметры а и с определяют основание треугольника, а параметр b – координату его вершины. Пример (см. рис. 3.31). » х = 0:0.1:10; » y = trimf(x,[3 6 8]); » plot(x,y) » xlabel(/trimf, P=[3 6 8]/)
Рис. 3.31. График функции принадлежности треугольной формы 79
Глава III. Пакет Fuzzy Logic Toolbox 11. Функция zmf. Запись: у = zmf(x,[a b]) О п и с а н и е . Задаётся зависящая от двух параметров функция принадлежности так называемой Z-образной формы. Параметры определяют диапазон убывания функции. Пример (см. рис. 3.32). » х = 0:0.1:10; » y = zmf(x,[3 7]); » plot(x,y) » xlabel(/zmf, P = [3 7]/)
Рис. 3.32. Функция принадлежности Z-образной формы
3.5.4. Функции сохранения, открытия и использования созданной системы Чтение, использование и сохранение на диске созданной системы нечёткого вывода в режиме командной строки осуществляется функциями readfis(/имя_файла/), evalfis(вектор_параметров, имя), writefis(имя) или writefis( имя, /имя_файла/) Здесь имя_файла – наименование файла с записанной системой (без указания расширения), имя – идентификатор, который определён системе в рабочей среде MATLAB, вектор_параметров – набор значений входов, для которых требуется рассчитать выход (возможна и матрица параметров, тогда результат расчётов – вектор в случае одной выходной переменной или матрица при нескольких таких переменных). Примеры (применительно к ранее созданной и сохранённой на диске в виде файла с именем tips экспертной системе для задачи о чаевых): » readfis(/tips/); » evalfis([l 2],a) ans = 7.3949 » writefis(a) 80
Потапов Д.К. Неклассические логики ans = tips
3.5.5. Функции использования графического окна Следующие три функции позволяют использовать элементы графических изображений вне программ с графическим интерфейсом. 1. Команда (функция) plotfis(a) вызовет появление графического окна MATLAB с мнемоническим представлением разработанной системы (рис. 3.33).
Рис. 3.33. Мнемоническое представление системы нечёткого вывода 2. Команда (функция) plotmf выполняет аналогичную операцию, но по отношению к графикам функций принадлежности. На рис. 3.34 приведён результат выполнения функции plotmf(a,/input/,1).
Рис. 3.34. Результат выполнения функции plotmf(a,/input/,1) 81
Глава III. Пакет Fuzzy Logic Toolbox 3. Наконец, команда (функция) gensurf(a) также делает то же самое, но применительно к поверхности отклика (рис. 3.35).
Рис. 3.35. Результат выполнения функции gensurf(a)
3.5.6. Функции создания, просмотра структуры и редактирования систем нечёткого вывода Вообще, при желании можно совсем обойтись без программ графического интерфейса и, используя функции newfis (новая система), addvar (добавить переменную), addmf (добавить функцию принадлежности) и addrule (добавить правило), сконструировать систему нечёткого вывода целиком в режиме командной строки MATLAB. Процесс этот, надо сказать, значительно более трудоёмкий, чем с применением указанных программ, поэтому, не вдаваясь особенно в детали, приведём лишь пример построения такой системы в задаче о чаевых: а = newfis (/tips/); а = addmf(a,/input/,l,/service/,[0 10]); а = addmf(a,/input/,1,/bad/,/gaussmf/,[1.5 0]); а = addmf(a,/input/,1,/good/,/gaussmf/,[1.5 5]); а = addmf(a,/input/,1,/excellent/,/gaussmf/,[1.5 10]); а = addvar(a,/input/,/food/,[0 10]); a = addmf(a,/input/,2,/burning/,/trapmf/,[-2 0 1 3]); а = addmf(a,/input/,2,/fantastic/,/trapmf/,[7 9 10 12]); а = addvar(a,/output/,/tips/,[0 30]); a = addmf(a,/output/,1,/small/,/trimf/,[0 5 10]); a = addmf(a,/output/,l,/middle/,/trimf/,[10 15 20]); a = addmf(a,/output/,l,/large/,/trimf/,[20 25 30]); ruleList = [... 11112 20211 3 2 3 1 2]; a = addrule(a,ruleList); 82
Потапов Д.К. Неклассические логики При необходимости после просмотра элементов структуры (системы с идентификатором а) в режиме командной строки следует ввести команду вида а.метка, например, » a.type Получим ответ: ans = mamdani Получение информации по всем элементам структуры обеспечивается функцией getfis(a). Результат её выполнения: Name = Tips Туре = mamdani NumInputs = 2 InLabels = service food NumOutputs = 1 OutLabels = tips NumRules =3 AndMethod = min OrMethod = max ImpMethod = min AggMethod = max DefuzzMethod = centroid ans = Tips Функция setfis в определённом смысле противоположна функции getfis и позволяет изменять метки. Пример выполнения функции: » а = setfis(а,/name/,/tips/) а= name: /tips/ type: /mamdani/ andMethod: /min/ orMethod: /max/ defuzzMethod: /centroid/ impMethod: /min/ aggMethod: /max/ input: [1x2 struct] output: [ l xl struct] rule: [1x3 struct] Полный просмотр структуры системы нечёткого вывода осуществляется функцией showfis(a). Просмотр правил, включённых в систему нечёткого вывода, осуществляется с помощью функции showrule. Запись: showrule(имя) showrule(имя,номера_правил) showrule(fis,номера_правил,формат) showrule(fis,номера_правил,формат,язык) О п и с а н и е . В функции имя – это идентификатор рассматриваемой системы в среде MATLAB, номера_правил – список правил, которые нужно показать, формат – строковая переменная, имеющая значения /verbose/, /symbolic/ или /indexed/, язык – строковая пере83
Глава III. Пакет Fuzzy Logic Toolbox менная со значениями /english/, /francais/ или /deutsch/ (установки по умолчанию – /verbose/ и /english/). Примеры. » а = readfis(/tips/); » showrule(a,1) ans = 1. If (service is bad) or (food is burning) then (tips is small) (1) » showrule(a,[3 1],/symbolic/) ans= 3. (service= =excellent)|(food= =fantastic) Þ (tips=large) (1) 1. (service= =bad)|(food= =burning) Þ (tips=small) (1) Функция rmmf используется для удаления функции принадлежности из состава системы. Запись: имя = rmmf(имя, /varType /,varIndex,/ mf/,mflndex) О п и с а н и е . Параметры функции: имя – идентификатор системы в среде MATLAB, varType – строковая переменная со значениями /input/ или /output/, varIndex – порядковый номер переменной (по списку переменных входа или выхода), mf – строковая переменная, задающая функцию принадлежности, mflndex – порядковый данной функции. Функция rmvar удаляет переменную из состава системы. Запись: [новое_имя,errorStr] = rmvar(имя,/varType/,varIndex) новое_имя = rmvar(имя, / varType /,varIndex) О п и с а н и е . Здесь переменные varType и varIndex имеют тот же смысл, что и в предыдущей функции, переменная errorStr позволяет записать любое сообщение об ошибке, новое_имя – новое имя системы с исключённой переменной. Функция приведения к чёткости (дефазификации) defuzz позволяет по заданной функции принадлежности определить соответствующее чёткое значение. Запись: out = defuzz(x,mf,type) О п и с а н и е . Здесь х – обозначение числового аргумента, mf – тип функции принадлежности, type – задаваемый метод приведения к чёткости – строковая переменная, имеющая возможные значения: · centroid; · bisector; · mom; · som; · lom. Смысл этих значений был рассмотрен ранее. П р и м ер . » х = -10:0.1:10; » mf = trapmf(x,[-10 -8 -4 7]); » xx = defuzz(x,mf,/centroid/) xx = -3.2857 Функция evalmf вычисляет значения заданной функции принадлежности. Запись: у = evalmf(x,mfParams,mfType) О п и с а н и е . Здесь х – обозначение числового аргумента, mfParams – вектор необходимых числовых параметров, mfType – тип функции принадлежности. Пример. » х = 0:0.1:10; » mfparams = [2 4 6]; 84
Потапов Д.К. Неклассические логики » mftype = /gbellmf/; » у = evalmf(x,mfparams,mftype); » plot(x,y) » xlabel(/gbellmf, P = [2 4 6]/) Функция mf2mf позволяет заменять одну функцию принадлежности близкой ей по форме другой с некоторым «эквивалентным» набором числовых параметров. Запись: outParams = mf2mf(inParams,inType,outType) О п и с а н и е . inParams – набор параметров исходной функции, inType – тип исходной функции принадлежности, outType – тип эквивалентной функции принадлежности, outParams – набор преобразованных параметров. Пример (см. рис. 3.36). » х = 0:0.1:5; » mfp1 = [1 2 3]; » mfp2 = mf2mf(mfp1,/gbellmf/,/trimf/) mfp2 = 1 3 5 »plot(x,gbellmf(x,mfp1),x,trimf(x,mfp2))
Рис. 3.36. Графики исходной (колоколообразной) и эквивалентной (треугольной) функций принадлежности Функцию parsrule можно отнести к числу сервисных. Запись: новое_имя = parsrule(имя,текст_правил) новое_имя = parsrule(имя, текст_правил,формат) новое_имя = parsrule(имя, текст_правил,формат,язык) О п и с а н и е . В данной функции идентификаторы имя и новое_имя относятся к исходной и модернизированной системам с нечётким выводом, строковые переменные формат и язык имеют тот же смысл, что и в рассмотренной ранее функции showrule, текст правил – заданный в текстовой форме набор правил системы (на языке, определённой переменной язык; по умолчанию – английский, что допускает использование, в частности, русских имён для переменных, но требует английских связующих слов if, and, or, then, is). Функция выпол85
Глава III. Пакет Fuzzy Logic Toolbox няет грамматический разбор исходного текста и выдаёт набор нечётких правил в указанном формате (по умолчанию – подробный).
3.5.7. Функции создания и/или обучения гибридных сетей с архитектурой ANFIS Функция anfis записывается в виде: [имя,ошибка_о,шаг] = anfis(trnData) [имя,оншбка_о,шаг] = anfis(trnData,имя) [имя1,ошибка_о,шаг] =... anfis(trnData,имя,trnOpt,dispOpt) [имя1,ошибка_о,шаг,имя2,ошибка_п] =... anfis(trnData,trnOpt,dispOpt,chkData) [имя1,ошибка_о,шаг,имя2,ошибка_п] =... anfis(trnData,trnOpt,dispOpt,chkData,optMethod) Функция предназначена для создания и/или обучения гибридных сетей с архитектурой ANFIS. Значения аргументов функции: • trnData – матрица данных для обучения сети (обучающая выборка); последний столбец соответствует (единственной) выходной переменной, остальные столбцы – входным переменным; • имя – идентификатор создаваемой гибридной сети; если структура системы нечёткого вывода с таким идентификатором уже создана, то она будет использована для настройки числовых параметров, в противном случае структура будет создана при выполнении функции с опциями, по умолчанию соответствующими выполнению функции genfis1 (см. ниже); • trnOpt – вектор опций обучения с элементами: trnOpt(l): количество циклов обучения (по умолчанию 10), trnOpt(2): целевой уровень ошибки обучения (по умолчанию 0), trnOpt(3): начальный шаг алгоритма обучения (по умолчанию 0.01), trnOpt(4): коэффициент уменьшения шага (по умолчанию 0.9), trnOpt(5): коэффициент увеличения шага (по умолчанию 1.1); • dispOpt – вектор опций вида выводимой информации (по умолчанию все элементы – единичные, что означает вывод всех видов возможной информации в процессе выполнения функции) с элементами: dispOpt(l): ANFIS-информация, такая, как число входов, функции принадлежности и т.п., dispOpt(2): ошибка, dispOpt(3): шаг обновления (корректировки) по каждому параметру, dispOpt(4): конечные результаты; • chkData – матрица проверочных данных (проверочная выборка), имеющая такой же набор столбцов, что и матрица данных для обучения сети, но, вообще говоря, другое число строк; • optMethod – параметр, определяющий вид алгоритма обучения гибридной системы (1 – гибридный алгоритм, 0 – алгоритм обратного распространения ошибки; по умолчанию – 1). Процесс обучения сети заканчивается, когда выполнено заданное число циклов обучения или ошибка обучения уменьшилась до заданного уровня. При отсутствии некоторых аргументов их значения принимаются по умолчанию. Выходные параметры функции: • ошибка_о – массив (вектор) значений ошибок для обучающей выборки; • ошибка_п – массив (вектор) значений ошибок для проверочной выборки; • шаг – массив значений шага в алгоритме обучения; • имя1 – идентификатор (имя) сети, образованной исходя из минимальной ошибки обучения; 86
Потапов Д.К. Неклассические логики • имя2 – идентификатор (имя) сети, образованной исходя из минимальной ошибки для проверочной выборки. Пример 1 (см. рис. 3.37). » х = (0:0.1:10)/; » у = sin(2*x)./exp(x/5); » trnData = [x у]; » а = anfis(trnData); ANFIS info: Number of nodes: 12 Number of linear parameters: 4 Number of nonlinear parameters: 6 Total number of parameters: 10 Number of training data pairs: 101 Number of checking data pairs: 0 Number of fuzzy rules: 2 Start training ANFIS ... 1 0.313942 2 0.31388 3 0.313817 4 0.313753 5 0.313689 Step size increases to 0.011000 after epoch 5. 6 0.313624 7 0.313552 8 0.313479 9 0.313406 Step size increases to 0.012100 after epoch 9. 10 0.313332 Designated epoch number reached ® ANFIS training completed at epoch 10. » plot(x,y,x,evalfis(x,a),/-./); » legend(/Training Data/,/ANFIS Output/);
Рис. 3.37. Обучающая выборка и выход системы а 87
Глава III. Пакет Fuzzy Logic Toolbox Пример 2 (см. рис. 3.38). » x= (0:0.1:10)/; » у = sin(2*x)./exp(x/5); » trnData = [x y]; » numMFs = 5; » mfType = /gbellmf/; » epoch_n = 20; » in_fismat = genfis1(trnData,numMFs,mfType); » out_fismat = anfis(trnData,in_fismat,20); ANFIS info: Number of nodes: 24 Number of linear parameters: 10 Number of nonlinear parameters: 15 Total number of parameters: 25 Number of training data pairs: 101 Number of checking data pairs: 0 Number of fuzzy rules: 5 Start training ANFIS ... 1 0.0694086 2 0.0680259 3 0.066663 4 0.0653198 5 0.0639961 Step size increases to 0.011000 after epoch 5. 6 0.0626917 7 0.0612787 8 0.0598881 9 0.0585193 Step size increases to 0.012100 after epoch 9. 10 0.0571712 11 0.0557113 12 0.0542741 13 0.052858 Step size increases to 0.013310 after epoch 13. 14 0.0514612 15 0.0499449 16 0.0484475 17 0.0469667 Step size increases to 0.014641 after epoch 17. 18 0.0455003 19 0.0439022 20 0.0423184 Designated epoch number reached ® ANFIS training completed at epoch 20. » plot(x,y,x,evalfis(x,out_fismat),/-./); » legend(/Training Data/,/ANFIS Output/);
88
Потапов Д.К. Неклассические логики
Рис. 3.38. Обучающая выборка и выход системы fismat В примере 2 при проектировании гибридной системы заранее были заданы некоторые значения (количество и тип функций принадлежности, количество циклов обучения), в примере 1 для той же обучающей выборки все установки при проектировании системы выбраны по умолчанию. Отличие в качестве функционирования двух систем наглядно иллюстрируются рис. 3.37 и 3.38.
3.5.8. Функция кластеризации Функция fcm осуществляет кластеризацию с использованием алгоритма Fuzzy cmeans (см. выше). Она записывается в виде: [center,U,obj_fcn] = fcm(data,cluster_n) [center,U,obj_fcn] = fcm(data,cluster_n,options) О п и с а н и е . Аргументы функции: • data – матрица данных, каждый столбец которой соответствует одной из переменных, а каждая строка – одному из опытов; • cluster_n – число задаваемых кластеров (должно быть больше 1); • options – вектор опций функции с элементами: options(l): показатель для матрицы U (по умолчанию 2.0), options(2): максимальное число итераций при определении центров кластеров (по умолчанию 100), options(3): минимальная сумма улучшения (по умолчанию 1е-5), options(4): вывод информации в процессе итераций (по умолчанию 1). Выходные параметры функции: • center – матрица, элементы которой (по столбцам) являются координатами найденных центров кластеров, число строк равно числу центров; • U – матрица значений принадлежности данных к выявленным кластерам; • obj_fcn – значения целевой функции в процессе итераций. Пример. » load clusterdemo.dat; » data = сlusterdemo; » [center,U,obj_fcn] = fcm(data, 3);
89
Глава III. Пакет Fuzzy Logic Toolbox Iteration count = 1, obj. fcn = 56.554232 Iteration count = 2, obj. fcn = 42.996494 Iteration count = 3, obj. fcn = 42.931708 Iteration count = 4, obj. fcn = 42.639644 Iteration count = 5, obj. fcn = 41.191412 Iteration count = 6, obj. fcn = 34.682033 Iteration count = 7, obj. fcn = 21.215631 Iteration count = 8, obj. fcn = 15.681175 Iteration count = 9, obj. fcn = 15.434686 Iteration count = 10, obj. fcn = 15.430601 Iteration count = 11, obj. fcn = 15.430530 Iteration count = 12, obj. fcn = 15.430528 » center
center = 0.2051 0.5963 0.7939
0.5960 0.1923 0.7892
0.8090 0.5057 0.1968
3.5.9. Функция генерации FIS-структуры Функция genfis1 генерирует FIS-структуру по экспериментальным данным без проведения их кластеризации: имя = genfis1(data) имя = genfis1(data,numMFs,inmftype, outmftype) О п и с а н и е . Функцией генерируется структура системы нечёткого вывода типа Sugeno, являющая исходной для последующего формирования и обучения гибридной системы с помощью функции anfis. Аргументы функции: • data – матрица данных (обучающая выборка), последний столбец которой соответствует выходной переменной, а остальные – входным переменным и число строк в которой равно числу наборов экспериментальных данных (образцов); • numMFs – вектор, элементы которого определяют число функций принадлежности, задаваемых для каждого входа; если для всех входов задаётся одно и то число таких функций, данный аргумент задаётся как скаляр (один элемент); • inmftype – строковый массив, элементы которого – типы функций принадлежности, задаваемые для входных переменных; • outmftype – строковая переменная, определяющая тип функций принадлежности выходной переменной (возможны только значения /linear/ или /constant/). Число функций принадлежности выходной переменной равно числу нечётких правил, генерируемых genfis1, и зависит от элементов вектора numMFs. По умолчанию numMFs=2, inmftype=/gbellmf/. Значения по умолчанию устанавливаются, если функция применяется без трёх последних аргументов. Применение функции ограничено размерностью задачи: так, при N входных переменных с минимальным разбиением области определения каждой переменной на две подобласти будет генерироваться 2N правил, что при числе входов больше 5-6 делает анализ этих правил практически невозможным. Более экономной в этом плане является функция genfis2 (см. ниже). Пример (см. рис.3.39). » data = [rand(10,l) 10*rand(10,l)-5 rand(10,l)]; » numMFs = [3 7]; » mfType = str2mat(/pimf/,/trimf/); » fismat = genfis1(data,numMFs,mfType); » [x,mf] = plotmf(fismat,/input/,1); » subplot(2,l,l), plot(x,mf); 90
Потапов Д.К. Неклассические логики » xlabel(/input 1 (pimf)/); » [x,mf] =plotmf(fismat,/input/,2); » subplot(2,l,2), plot(x,mf); » xlabel(/input 2 (trimf)/); См. также пример 2 для функции anfis.
Рис. 3.39. Функции принадлежности, определённые genfis1
3.5.10. Функция генерации структуры нечёткого вывода Функция genfis2 генерирует структуру системы нечёткого вывода (типа Sugeno) с использованием алгоритма Subtractive clustering кластеризации данных: имя = genfis2(Xin,Xout,radii) имя = genfis2(Xin,Xout,radii,xBounds) имя = genfis2(Xin,Xout,radii,xBounds,options) Аргументами рассматриваемой функции являются: • Xin – матрица (массив) входных данных обучающей выборки, столбцы которой ассоциированы с входными переменными, а каждая строка – с отдельным опытом; • Xout – матрица выходных переменных обучающей выборки, столбцы которой представляют значения данных переменных, а число строк равно числу строк матрицы Xin; • radii (радиусы) – вектор, определяющий «области влияния» центров кластеров по каждой входной переменной (в предположении, что область определения данных переменных – многомерный параллелепипед) с неотрицательными элементами, меньшими единицы; пусть, например, число входов – 3, тогда radii = [0.5 0.4 0.3] означает, что по первой переменной «область влияния» составляет 0.5 от диапазона изменения этой переменной, а по второй и третьей – соответственно 0.4 и 0.3 (эти диапазоны определяются по элементам столбцов матрицы Xin). Если рассматриваемый аргумент задан как скаляр, то по всем переменным устанавливается один и тот же размер «области влияния» кластеров. Параметр имеет важное значение для проведения разбиения области определения входов на подобласти с последующим установлением числа нечётких правил; 91
Глава III. Пакет Fuzzy Logic Toolbox • XBounds – матрица с 2 строками и N столбцами (N – число столбцов в матрице Xin, т.е. число входных переменных), устанавливающая границы областей определения входных переменных. Данные этой матрицы используются для преобразования (масштабирования) входов к диапазону [–1, 1]. апример, Xbounds = [-10 0 -1; 10 50 1] задаёт диапазон [-10, 10] для первой переменной, [0, 50] – для второй и [-1, 1] – для третьей. Если рассматриваемый аргумент опущен, границы областей определяются как максимальные и минимальные элементы по столбцам матрицы Xin; • options – вектор опций, устанавливающий параметры алгоритма кластеризации (подробней см. при описании функции subclust). Функция genfis2, так же как genfisl, может применяться в комплекте с функцией anfis (для настройки параметров системы нечёткого вывода), но, в отличие от последней, genfis2 возвращает уже полностью определённую, готовую к использованию систему, не требующую, вообще говоря, дополнительной оптимизации. Функция genfis2 производит более экономное, чем genfisl разбиение пространства входов на подобласти и может, поэтому, являться эффективным инструментов для выявления правил из набора экспериментальных данных. Примеры а = genfis2(Xin,Xout,0.5) a = genfis2(Xin,Xout,[0.5 0.25 0.3])
3.5.11. Функция возврата центров кластеров Функция subclust возвращает центры кластеров. Запись: [G,S] = subclust(X,radii,xBounds,options) Функцией определяются центры кластеров набора экспериментальных данных, отражаемых матрицей X (столбцы матрицы соответствуют переменным, строки – экспериментальным «точкам» или опытам) на основе реализации «вычитающего» алгоритма кластеризации (Subtractive clustering). В его основе лежит предположение, что каждая экспериментальная точка может быть центром кластера, при этом вначале для каждой точки вычисляется мера правдоподобия данного предположения («потенциал точки»), основанная на плотности точек в заданной окрестности рассматриваемой. Дальнейшие вычисления происходят итеративно: • точка с наибольшим потенциалом объявляется центром первого кластера; • из отмеченной окрестности этой точки удаляются все остальные точки; • из оставшихся точек объявляется центр следующего кластера и т.д., пока не будут рассмотрены (исключены или объявлены центрами кластеров) все точки. Размеры окрестностей задаются элементами вектора radii, который (как и аргумент xBounds) аналогичен рассмотренному при описании функции genfis2. Аргумент options является вектором со следующими элементами: • options(1) = quashFactor (фактор подавления): используется для расширения «сферы влияния» выделенного центра кластера для «подавления» (уменьшения) потенциала точек, относящихся к данному кластеру; по умолчанию равен 1.25; • options(2) = acceptRatio (коэффициент принятия): устанавливает, больше какого значения по отношению к потенциалу принятого центра кластера должен быть потенциал точки, чтобы эту точку можно было объявить центром нового кластера; по умолчанию 0.5; • options(3)=rejectRatio (коэффициент отклонения): устанавливает, меньше какого значения по отношению к потенциалу принятого центра кластера должен быть потенциал точки, чтобы эту точку нельзя было объявить центром нового кластера; по умолчанию 0.15; • options(4) = verbose (подробности): если этот элемент ненулевой, то выдаётся подробная информация и процессе нахождения центров кластеров; по умолчанию – 0. Функция возвращает центры кластеров в виде матрицы С; каждая строка этой матрицы содержит координаты одного из найденных центров. Вектор S содержит элементы, опре-
92
Потапов Д.К. Неклассические логики деляющие диапазоны влияния центров кластеров по каждой переменной (для всех центров эти диапазоны одинаковы). Пример. » X = load(/clusterdemo.dat/); » [C,S] = subclust(X,0.5) C= 0.2220 0.5937 0.8113 0.7797 0.8191 0.1801 0.5914 0.1721 0.4872 S= 0.1904 0.1988 0.2251
3.5.12. Другие различные функции К этой группе относятся 10 функций: 1) convertfis – обеспечивает конвертацию FIS-матрицы пакета Fuzzy Logic версии 1.0 в FIS-структуру пакета Fuzzy Logic версии 2.0: имя_новое = convertfis(имя старое). 2) discfis – преобразует непрерывные функции принадлежности системы нечёткого вывода в дискретные (задаваемые наборами точек). 3) evalmmf – вычисляет значения одновременной нескольких функций принадлежности. Является многомерным аналогом функции evalmf. 4) fstrvcat – объединяет заданные векторы и матрицы в одну матрицу: Y = strvcat(yl,y2,y3,..). Функция возвращает матрицу Y, представляющую собой объединение матриц-аргументов yl,y2,y3,.., при этом для выравнивания размеров итоговой матрицы она дополняется нулями. Элементы аргументов могут быть строкового типа, при этом их символы преобразуются в числовую форму. 5) fuzarith – выполняет алгебраические операции над нечёткими множествами: С = fuzarith(X, А, В, operator). Здесь X – вектор, выполняющий роль универсального множества, А и В – векторы, определяющие нечёткие подмножества-операнды, С – вектор, определяющий нечёткое подмножество – результат операции, operator – строковая переменная, задающая вид операции и имеющая одно из возможных значений /sum/ (сумма), /sub/ (вычитание), /prod/ (умножение), /div/ (деление). Пример (см. рис. 3.40). >> point_n = 101; % this determines MF's resolution (задание количества точек универсального множества) >> min_x = -20; max_x = 20; % universe is [min_x, max_x] >> x = linspace(min_x, max_x, point_n)'; >> A = trapmf(x, [-10 -2 1 3]); % trapezoidal fuzzy set A (трапецеидальная функция принадлежности подмножества А) >> B = gaussmf(x, [2 5]); % Gaussian fuzzy set B (гауссова функция принадлежности подмножества В) >> C1 = fuzarith(x, A, B, 'sum'); >> subplot(2,1,1); >> plot(x, A, 'b--', x, B, 'm:', x, C1, 'c'); >> title('fuzzy addition A+B'); % нечёткая сумма А+В >> C2 = fuzarith(x, A, B, 'prod'); >> subplot(2,1,2); >> plot(x, A, 'b--', x, B, 'm:', x, C2, 'c'); >> title('fuzzy production A*B'); % нeчёткоe произведение А*В
93
Глава III. Пакет Fuzzy Logic Toolbox
Рис. 3.40. Результаты выполнения функции fuzarith 6) findrow – возвращает номера аргументов функции fstrvcat по их именам. 7) genparam – возвращает параметры заданных функций принадлежности, определяя их по набору входных экспериментальных данных. Данные результаты могут быть использованы как начальные приближения при последующем применении команды anfis. 8) mam2sug – преобразует систему нечёткого вывода с алгоритмом Mamdani в систему, использующую алгоритм Sugeno: имя_sug = mam2sug(имя_mam). Функция возвращает систему нечёткого вывода (с именем имя_sug), использующую алгоритм вывода Sugeno, по заданной системе имя_mam, использующей алгоритм Mamdani. Возвращаемая система имеет постоянные функции принадлежности выходных переменных (допускается их число больше 1), определяемые как центроиды функций принадлежности следствий нечётких правил алгоритма Mamdani. Предпосылки правил при преобразовании не изменяются. Пример (см. рис. 3.41). >> a=readfis('D:\Неклассические_логики\Tips'); >> b=mam2sug(a); >> subplot(2,1,1); gensurf(a); >> title('Exit of the Mamdani system (tips)'); % Выход системы Mamdani (чаевые) >> subplot(2,1,2); gensurf(b); >> title('Exit of the Sugeno system (tips)'); % Выход системы Sugeno (чаевые)
94
Потапов Д.К. Неклассические логики
Рис. 3.41. Иллюстрации к выполнению функции mam2sug З а м е ч а н и е . Проверка, проведённая автором, показала, что рассмотренная функция выполняется некорректно и приводит к неработающей системе вывода (попытки использования системы Sugeno вызывают сообщение об ошибке). Данный недостаток можно устранить, изменив в предпоследней строке файла mam2sug.m (в директории Matlab/toolbox/fuzzy/fuzzy/ ) defuzzmethod на defuzzMethod. 9) probor – выполняет операцию вероятностного ИЛИ над столбцами матрицыаргумента: Y = probor(X). Если матрица-аргумент X имеет два столбца, А и В, то функция возвращает матрицу Y = A+B-АВ; если аргумент содержит только один столбец, то Y = X. 10) sugmax – позволяет определить максимально возможные диапазоны изменения выходных переменных в заданной системе нечёткого вывода, использующей алгоритм Sugeno.
3.5.13. Функции вызова диалоговых окон интерфейса Данную группу образуют 12 функций: 1) cmfdlg – вызывает диалоговое окно для задания функции принадлежности пользователя, 2) cmthdlg – вызывает диалоговое окно для задания пользовательского алгоритма нечёткого вывода, 3) fisgui – позволяет генерировать элементы графического интерфейса пользователя, 4) gfmfdlg – вызывает диалоговое окно для задания числа и типа функции принадлежности при проектировании системы типа Sugeno (с последующим применением функции anfis), 5) mfdlg – вызывает диалоговое окно для задания дополнительной функции принадлежности, 6) mfdrag – обеспечивает «перетаскивание» функции принадлежности с использованием мыши, 7) popundo – возвращает из стека результаты отмены предыдущего действия, 8) pushundo – помещает в стек данные по отменяемому действию, 9) savedlg – вызывает диалоговое окно, выдающее запрос на сохранение результатов, 95
Глава III. Пакет Fuzzy Logic Toolbox 10) statmsg – помещает сообщения в поле состояния окна, 11) updtfis – обновляет элементы графического интерфейса пользователя, 12) wsdlg – вызывает диалоговое окно для выполнения операции сохранения в рабочем пространстве. В качестве примера приведём выполнение функции gfmfdlg (см. рис. 3.42): >> a=readfis('D:\Неклассические_логики\Tips'); >> gfmfdlg('#init',a) ans = '3 2' 'gaussmf' 'linear'
Рис. 3.42. Результат выполнения команды gfmfdlg
3.6. Работа Fuzzy Logic с блоками Simulink Системы нечёткого вывода, созданные тем или иным образом с помощью пакета Fuzzy Logic Toolbox, допускают интеграцию с инструментами пакета Simulink, что позволяет выполнять моделирование систем в рамках последнего.
3.6.1. Пример: контроль уровня воды в баке На рис. 3.43 изображён объект управления в виде бака с водой, к которому подходят две трубы: через одну трубу, снабжённую краном, вода втекает в бак, через другую – вытекает. Подачу воды в бак можно регулировать, больше или меньше открывая кран. Расход воды является неконтролируемым и зависит от диаметра выходной трубы (он фиксирован) и от текущего уровня воды в баке. Если понимать под выходной (регулируемой) переменной уровень воды, а под регулирующим элементом – кран, то можно отметить, что подобный объект регулирования, с точки зрения его математического описания, является динамическим и существенно нелинейным.
96
Потапов Д.К. Неклассические логики
Рис. 3.43. Схематическое представление объекта управления (бака с водой) Определим цель управления здесь как установление уровня воды в баке на требуемом (изменяющемся) уровне и попробуем решить соответствующую задачу управления средствами нечёткой логики. Очевидно, в регулятор, обеспечивающий достижение цели управления, должна поступать информация о несоответствии (разности) требуемого и фактического уровней воды, при этом данный регулятор должен вырабатывать управляющий сигнал на регулирующий элемент (кран). В первом приближении функционирование регулятора можно описать набором из следующих правил: 1. If (level is okay) then (valve is no_change) (1) 2. If (level is low) then (valve is open_fast) (1) 3. If (level is high) then (valve is close_fast) (1) 4. If (level is okay) and (rate is positive) then (valve is close_slow) (1) 5. If (level is okay) and (rate is negative) then (valve is open_slow) (1), что в переводе означает: 1. Если (уровень соответствует заданному), то (кран без изменения) (1) 2. Если (уровень низкий), то (кран быстро_открыть) (1) 3. Если (уровень высокий), то (кран быстро_закрыть) (1) 4. Если (уровень соответствует заданному) и (его прирост – положительный), то (кран надо медленно_закрывать) (1) 5. Если (уровень соответствует заданному) и (его прирост – отрицательный), то (кран надо медленно_открывать) (1) Модель системы управления уровнем воды в баке с нечётким регулятором, основанным на приведенных правилах, является одной из демонстрационных моделей пакетов Fuzzy Logic и Simulink. Её можно вызвать из командной строки командой sltank, что приведёт к открытию окна Simulink с блок-диаграммой указанной модели (рис. 3.44).
97
Глава III. Пакет Fuzzy Logic Toolbox
Рис. 3.44. Блок-диаграмма модели системы управления уровнем воды в баке с нечётким регулятором Одновременно блок Fuzzy Logic Controller будет сопоставлен с системой нечёткого вывода, записанной в файле tank.fis. Для изучения процесса функционирования системы необходимо нажать кнопку Start simulation панели инструментов блок-диаграммы модели и дважды щёлкнуть левой кнопкой мыши по блоку Comparison (Сравнение). В появившемся окне этого блока будут показаны изменяющиеся во времени сигналы заданного (последовательность импульсов прямоугольной формы) и фактического уровней воды (рис. 3.45). Как видно, переходный процесс в системе имеет апериодическую форму и заканчивается достаточно быстро, т.е. качество регулирования следует признать хорошим. Можно попытаться изменить характер функционирования системы, внося – например, с помощью рассмотренных программ с графическим интерфейсом (типа FIS-редактора и т.п.), определённые изменения в систему, задаваемую файлом tank.fis (изменяя правила, функции принадлежности, метод приведения к чёткости и т.д.). Разумеется, всё это лучше делать, остановив процесс моделирования. Выполнив (в режиме командной строки) команду sltankrule, перейдём к блок-диаграмме той же системы управления, но с нечётким регулятором с просмотрщиком правил (Fuzzy Controller with Ruleviewer, рис. 3.46).
Рис. 3.45. Результаты моделирования системы управления с нечётким регулятором 98
Потапов Д.К. Неклассические логики
Рис. 3.46. Блок Fuzzy Controller with Ruleviewer
3.6.2. Построение нечёткой модели с использованием блоков Simulink Для построения какой-то собственной моделирующей системы с использованием средств нечёткой логики и блоков Simulink рекомендуется просто скопировать блок Fuzzy Logic Controller из рассмотренной системы sltank (или какого-либо другого демонстрационного примера MATLAB) и поместить его в блок-диаграмму разрабатываемой системы. Из командной строки командой fuzblock можно также открыть библиотеку нечётких блоков пакета Simulink (в версии MATLAB 5.3, содержащей два блока: нечёткий регулятор – Fuzzy Logic Controller и нечёткий регулятор с просмотрщиком правил – Fuzzy Logic Controller with Ruleviewer, а в версии 5.2 – ещё и несколько демонстрационных блоков), которые могут быть использованы точно так же, при необходимости – с дополнительным редактированием. Отметим, что функционирование указанных блоков осуществляется с использованием системной S-функции sffis.mex. Запись этой функции такова: output = sffis(t, x, u, flag, fismat), где output – выход нечёткого регулятора, t, x и flag – стандартные аргументы системной функции Simulink, fismat – идентификатор (имя) нечёткой системы вывода, u – входной сигнал (вектор входных сигналов) регулятора. 99
Глава III. Пакет Fuzzy Logic Toolbox По смыслу данная функция аналогична рассмотренной выше функции evalfis, но она оптимизирована для работы в среде Simulink.
3.6.3. Демонстрационные примеры работы с пакетом Fuzzy Logic Toolbox Для ознакомления с пакетом Fuzzy Logic Toolbox можно использовать следующие функции (команды) в режиме командной строки: defuzzdm – обзор методов приведения к чёткости (дефазификации),
fcmdemo – демонстрация алгоритма кластеризации Fuzzy c-means (2D-графика),
100
Потапов Д.К. Неклассические логики fuzdemos – демонстрация графического интерфейса пакета Fuzzy Logic,
gasdemo – демонстрация использования аппарата гибридных сетей для решения задачи о выборе автомобиля, наиболее экономичного по расходу топлива,
101
Глава III. Пакет Fuzzy Logic Toolbox juggler – демонстрация системы жонглирования мячом с использованием нечёткого регулятора,
invkine – демонстрация нечёткого управления движением робота-манипулятора,
102
Потапов Д.К. Неклассические логики irisfcm – демонстрация алгоритма кластеризации Fuzzy c-means,
noisedm – демонстрация решения задачи фильтрации на основе методов нечёткой логики,
103
Глава III. Пакет Fuzzy Logic Toolbox slbb – демонстрация задачи «шар на качелях»,
slcp – демонстрация нечёткой системы управления перевёрнутым маятником,
sltank – демонстрация системы управления уровнем воды в баке с нечётким регулятором, sltankrule – то же, что в предыдущем случае, но с дополнительным просмотром нечётких правил,
104
Потапов Д.К. Неклассические логики sltbu – демонстрация функционирования нечёткой системы управления грузовиком.
С каждым из этих примеров связан М-файл, fis-файл или/и блок-диаграмма Simulink, запуск которых производится с помощью одной из указанных команд. Текст пояснений в примерах – на английском языке. Данные примеры доступны и через главное меню MATLAB (пункт Help/Examples and Demos, раздел Toolboxes/Fuzzy Logic). Дополнительную информацию можно получить, используя команду help fuzzy.
105
Список литературы
Список литературы 1. Аверин А.Н. и др. Нечёткие множества в моделях управления и искусственного интеллекта / Под ред. Д.А. Поспелова. – М.: Наука, 1986. – 312 с. 2. Булос Дж., Джефри Р. Вычислимость и логика. – М.: Мир, 1994. 3. Гиндикин С.Г. Алгебра логики в задачах. – М.: Наука, 1972. 4. Горбатов В.А. Фундаментальные основы дискретной математики. – М.: Физматлит, 2000. 5. Гуц А.К. Математическая логика и теория алгоритмов. – Омск: Наследие. ДиалогСибирь, 2003. 6. Дли М.И. Локально-аппроксимационные модели сложных объектов. – М.: Наука, Физматлит, 1999. – 112 с. 7. Дли М.И., Круглов В.В., Осокин М.В. Локально-аппроксимационные модели социально-экономических систем и процессов. – М.: Наука, Физматлит, 2000. – 224 с. 8. Ершов Ю.Л. Определимость и вычислимость. – Новосибирск: Научная книга, 1996. 9. Змитрович А.И. Интеллектуальные информационные системы. – Минск: НТООО «ТетраСистемс», 1997. – 367 с. 10. Ивин А.А. Логика времени // Неклассическая логика. – М.: Наука, 1979. 11. Корнеев В.В., Греев А.Ф., Васютин С.В., Райх В.В. Базы данных. Интеллектуальная обработка информации. – М.: Нолидж, 2000. – 352 с. 12. Кофман А., Алуха Х. Хил. Введение теории нечётких множеств в управление предприятием. – Минск: Высшая школа, 1992. – 223 с. 13. Круглов В.В., Дли М.И., Голунов Р.Ю. Нечёткая логика и искусственные нейронные сети: Учеб. пособие. – М.: Физматлит, 2001. – 224 с. 14. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М.: Наука, 1984. 15. Леоненков А.В. Нечёткое моделирование в среде MATLAB и fuzzyTECH. – СПб.: БХВ-Петербург, 2003. 16. Логический подход к искусственному интеллекту (от модальной логики к логике баз данных). – М.: Мир, 1998. – 495 с. 17. Непейвода Н.Н. Прикладная логика. – Новосибирск: Изд-во НГУ, 2000. 18. Пинус А.Г. Основы универсальной алгебры. – Новосибирск: Изд-во НГТУ, 2000. 19. Пинус А.Г. Условные термы и их применение в алгебре и теории вычислений. – Новосибирск: Изд-во НГТУ, 2002. 20. Прикладные нечёткие системы / Под ред. Т. Тэрано, К. Асаи, М. Сугэно. – М.: Мир, 1993. – 368 с. 21. Справочная книга по математической логике. Ч. 1-4 / Под ред. Дж. Барвайса. – М.: Наука, 1982. 22. Судоплатов С.В., Овчинникова Е.В. Математическая логика и теория алгоритмов: Учебник. – М.: ИНФРА-М; Новосибирск: Изд-во НГТУ, 2004. – 224 с.
106
Потапов Д.К. Неклассические логики 23. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики. – М.: ИНФРАМ; Новосибирск: Изд-во НГТУ, 2003. 24. Трильяс А., Альсина К., Вальверде А. Нужны ли в теории нечётких множеств операции MAX, MIN и 1-j? / В кн. «Нечёткие множества и теория возможностей» под ред. Р.Р. Ягера. – М., 1986. – С. 199-228. 25. Фейс Р. Модальная логика. – М.: Наука, 1974.
107
Учебное издание
Дмитрий Константинович Потапов
Неклассические логики Учебное пособие
Отпечатано копировально-множительным участком отдела обслуживания учебного процесса физического факультета СПбГУ. Приказ № 571/1 от 14.05.2003. Подписано в печать 16.01.2006 с оригинал-макета заказчика. Формат 30×42/4. Усл. печ. л. 6,3. Тираж 100 экз. Заказ № 278/с. 198504, СПб., Ст. Петергоф, ул. Ульяновская, д. 3, тел. 428-43-00.