Содержание к диссертации
Введение
1. Основные понятия 17
1.1 Элементы алгебры отношений и упорядоченных множеств 17
1.2 Элементы теории решеток 23
2. Методы анализа и синтеза нечетких автоматов 26
2.1 Методы анализа и синтеза нечетких автоматов без функции выхода 28
2.2. Методы анализа и синтеза нечетких автоматов с функцией выхода 49
3. Исследование функционального поведения нечетких автоматов 69
3.1 Постановка задачи и основные определения 70
3.2 Индексы и периоды нечетких матриц 77
3.3 Индексы и периоды нечетких графов 84
Заключение 99
Список литературы 101
Публикации автора по теме диссертации 107
Приложение 1 109
Приложение 2 114
Приложение 3 118
- Элементы алгебры отношений и упорядоченных множеств
- Методы анализа и синтеза нечетких автоматов без функции выхода
- Методы анализа и синтеза нечетких автоматов с функцией выхода
- Индексы и периоды нечетких матриц
Введение к работе
Развитие науки и техники ведет ко всё большему усложнению как объектов исследования, так и систем их моделирующих. Возрастает сложность устройств, технологических процессов производства, что в свою очередь ведет к усложнению моделирования разнообразных объектов и процессов с ними непосредственно связанных. Ос обенно усложняются вопросы, связанные с моделированием систем «человек - машина», где остро ставятся задачи эффективного управления системами организационно-технического, экономического и социального характера.
Одним из математических методов моделирования систем и явлений является построение их дискретных моделей. В общем случае, при некоторых допущениях, любая система может быть представлена в виде некоторого объекта, который может находиться в различных состояниях. Данные состояния меняются дискретно под воздействием внешней среды (входных сигналов) и, в свою очередь, сам объект формирует реакцию на воздействие внешней среды (с помощью выходных сигналов).
Такое поведение систем часто описывается дискретными моделями, в частности, различными видами автоматов.
Естественным образом такие модели появляются при решении научных и технических, фундаментальных и прикладных задач, при построении и исследовании физических, химических, и других естественнонаучных, а также социальных, экономических и технических объектов. К таковым относятся многочисленные задачи, связанные с вычислительной техникой, информационно-коммуникационными технологиями, экономикой,
Различные виды конечных автоматов и близкие им математические объекты служат для описания и анализа технических устройств, различных систем и процессов, программ и алгоритмов. Многие сложные концепции теоретической информатики были разработаны на базе теории конечных автоматов. Теория конечных автоматов имеет многочисленные приложения в технической и практической информатике составляет существенную часть теоретической информатики.
Автоматы как математическая модель рассматриваются в теории с одной стороны как алфавитные преобразователи информации, реализующие отображение множества входных сигналов во множество выходных сигналов, а с другой стороны, как динамические системы, изменяющие свои состояния под воздействием внешних сигналов и внутренних факторов.
Первое направление теории автоматов получило развитие в рамках работ академика Глушкова и его последователей, второе — рассматривал в своих работах Арбиб и ряд других исследователей.
Математической моделью устройства преобразования информации является трехосновная алгебраическая система, называемая автоматом, и представляющая собой алгебру A = (S,X,Y,8,a ), с тремя основными множествами S, X, Y и двумя бинарными операциями 8: S х X — S, co:SxX Y. При этом, множество S называется множеством состояний,4 Х- множеством входных сигналов, Y- множеством выходных сигналов. Операция 8 - называется функцией переходов автомата и показывает, как входной сигнал х преобразует состояние я в новое состояние s = 8(s,x). Операция со называется выходной функцией автомата А и указывает значение сигнала на выходе у — oo{s,x) в зависимости от состояния автомата s и значения входного сигнала х.
В качестве динамических систем наиболее часто изучают, автоматы вида A = (S,X,8), лишенные функции выхода, так называемые полуавтоматы.
Задачи анализа, синтеза, а также задачи, связанные с исследованием функционального поведения автоматов, нашли отражение в работах Айзермана, Гилла, Трахтенброта, Минского, Шеннона, Джона фон Неймана, Яблонского, Богомолова, Твердохлебова и многих других.
В зависимости от специфики рассматриваемых задач, некоторый объект может моделироваться автоматом, у которого множество состояний и множество выходных сигналов наделены дополнительной математической структурой (например, структурой линейного пространства, упорядоченного множества и другими), которая сохраняется функциями переходов и выходными функциями этого автомата ([8], [16]). Так, многие известные задачи математического моделирования приводят к понятиям линейных [7], упорядоченных [10], булевозначных [20], вероятностью [6] автоматов. Исследованиям таких автоматов посвящены, например, работы Скорнякова Л.А.[23], Сытника А.А. [25], Сперанского Д.В., Салия В.Н., Плоткина Б.И. и Филькенштейна М.Я. и многих других. Так или иначе, многочисленные исследования в этих направлениях характеризуются широким спектром использования алгебраических средств, так что автоматы того или иного вида становятся предметом исследований в алгебраической теории автоматов, которая очень тесным образом связана со многими разделами универсальной алгебры.
Первоначально при решении задач, в которых приходилось сталкиваться с неопределенностью того или иного вида, использовался аппарат теории вероятности. Однако по мере того, как в область интересов исследователей начали попадать процессы функционирования биологических, социальных, экономических систем, то есть вопросы, связанные с восприятием мира живыми существами, и в частности человеком, аппарата теории вероятности во многих случаях оказалось недостаточно. К таким системам относятся, например, всевозможные экспертные и биомедицинские системы, в которых появляется неопределенность, связанная с нечеткостью рассуждений, восприятия и нечеткостью в принятии решений экспертом.
К примеру, промоделировать изменение состояния некоего пациента детерминированным автоматом не представляется возможным, ввиду того, что эти изменения не определяются однозначно. Сложно сказать в какой точно момент состояние пациента изменилось с «хорошего» на «удовлетворительное». Подобные системы описывается с помощью аппарата нечетких моделей. Впервые модели такого рода ввел в обиход профессор Лотфи Заде (Lotfi Zadeh), опубликовавший в 1965 году основополагающую работу "Fuzzy Sets" в журнале "Information and Control" [79]. Началом практического использования аппарата нечетких множеств можно считать работу Ви (Wee W.G.) и Фу (Fu K.S.) [78] в которой они предложили модель нечеткого автомата, а так же рассмотрели возможность применения его в качестве модели обучающей системы. Далее в 1975г. Мамдани и Ассилиан [60] из Лондонского колледжа Королевы Мэри (Mamdani and Assilian) построили первый нечеткий контролер для управления простым паровым двигателем. Концепцию первого нечеткого контроллера составляют идеи нечеткого логического вывода и нечеткого алгоритма, изложенные Заде в 1973 году [30]. В 1982 Холмблад и Остергад (Holmblad and Osregaad) разработали первый промышленный нечеткий контроллер [46], который был внедрен в управление процессом обжига цемента на заводе в Дании. Несколько позже Бартоломеем Коско (Bart Kosko) была доказана теорема о нечеткой аппроксимации (Fuzzy Approximation Theorem) [54], согласно которой любая математическая система может быть аппроксимирована системой, основанной на нечеткой логике. Другими словами, с помощью естественноязыковых высказываний-правил "если - то", с последующей их формализацией средствами теории нечетких множеств, можно сколько угодно точно отразить произвольную взаимосвязь "вход-выход" без использования сложного аппарата дифференциального и интегрального исчисления, традиционно применяемого в управлении и идентификации.
В январе 1997 года язык нечеткого управления FCL Fuzzy Control Language внесен в Международный стандарт программируемых контроллеров IEC 1131-7. Системы на нечетких множествах разработаны и успешно внедрены в таких областях, как: медицинская диагностика, техническая диагностика, финансовый менеджмент, управление персоналом, биржевое прогнозирование, распознавание образов, разведка ископаемых, выявление мошенничества, управление компьютерными сетями, управление технологическими процессами, управление транспортом, поиск информации в Интернете, радиосвязь и телевидение.
Ви и Фу предложили конструкцию нечеткой автоматной модели, являющейся обобщением конструкции детерминированных автоматов, в которой неопределенность выражалась в том, что изменения состояний определялись не однозначно, а также имели некоторую оценку, например из отрезка [0,1]. Данная модель активно использовалась различными авторами для описания поведения систем с неоднозначно определенными состояниями.
Вместе с тем задачи синтеза и анализа для данных моделей не рассматривались, поскольку непосредственный перенос результатов решения задач синтеза и анализа детерминированных автоматов на случай автоматов нечетких чрезвычайно затруднителен и требует построения новых методов и разработки аппарата исследования. Тем не менее, решение данных задач позволит расширить диапазон средств моделирования.
Некоторые попытки в данном направлении предприняли Малик, Морденсон и Сен (Malik D.S., Mordeson J.N., Sen М.К), которые в [59] предложили один из возможных вариантов минимизации нечеткого автомата, а в работе [58] предложили способ описания полугруппы преобразований нечеткого автомата, а также соединений нечетких автоматов (это требовалось при решении конкретных технических задач), однако в силу того, что ими не использовался алгебраический аппарат, построения получились избыточно сложными, громоздкими и не универсальными. В силу этого представляется необходимым привнести алгебраические методы в теорию моделей нечетких систем, что позволит использовать методы теории конечных детерминированных автоматов при решении задач синтеза и анализа автоматов нечетких.
Особый интерес для исследования представляют также нечеткие матрицы, которые играют важную роль в задачах кластеризации и поиска информации, поскольку являются представлением нечетких отношений в моделях, основанных на нечетких множествах (см., например, [62, 72]). Однако область применения нечетких матриц не исчерпывается задачами кластерного анализа, а также задачами классификации образов (с использованием субъективной меры сходства).
Нечеткие матрицы является одним из языков для описания дискретных систем, не допускающих точного описания [13, 21]. Примером такой системы, как уже отмечалось выше, является нечеткий автомат. Функция переходов для каждого входного сигнала нечеткого автомата представляется нечеткой матрицей. Итерации входного сигнала соответствует возведение данной матрицы в степень. В связи с этим, при решении достаточно большого числа задач исследуют степени различных вещественнозначных матриц (нечетких как частный случай), исследуют их поведение относительно различных операций сложения и умножения, как, например, max-min умножение [38, 76], максимум-сложения [29, 67] (линейные системы с синхронизацией).
Изучение степеней нечетких матриц и графов, является важным с точки зрения анализа функциональных свойств нечетких моделей, таких как нечеткие автоматы.
Нечеткие матрицы являются обобщением булевых матриц, которые в свою очередь достаточно давно являются объектом исследования различных авторов. В частности, Поплавским В.Б. в [17, 18] исследовалась последовательность определителей степеней булевых матриц. В свою очередь, теория булевых матриц ведет своё начало от теории матриц с неотрицательными элементами, большинство наиболее известных результатов для которых были получены между 1906 и 1912 годами Перроном и Фробениусом.
Благодаря широким областям применения нечеткой логики, нечеткие матрицы, а так же нечеткие графы используются в области нейронных сетей [33, 52], например, в нечетких клеточных нейронных сетях [74, 75], которые разрабатывались и применялись при решении задач связанных с обработкой изображений. Задача нахождения степеней нечеткой матрицы также тесно связана с такими задачами как исследование функционирования нечеткой двунаправленной ассоциативной памяти, нахождение решений нечетких уравнений отношения (см., например, [66, 77, 39]).
Одними из наиболее важных характеристик нечетких матриц являются значения их индекса и периода. Изучением степеней нечетких матриц одним из первых начал заниматься Томасон (Thomason), который заметил, что степени нечетких матриц, либо сходятся, либо обладают конечным периодом [76]. Однако следует отметить, что данные характеристики свойственны не только матрицам, но также и всем конечным циклическим полугруппам, и для каждой циклической полугруппы определены две характеристики называемые индексом и периодом циклической полугруппы соответственно (см. [11]).
Известно, что любая квадратная нечеткая матрица образует относительно операции min-max-умножения циклическую полугруппу.
Так как общий состав элементов нечеткой матрицы при возведении её в степень не расширяется, циклическая полугруппа, порожденная нечеткой, матрицей, конечна и потому для каждой такой матрицы А определены индекс ind(A) и период р(А).
Отметим, что для нечетких матриц остаются открытыми ряд вопросов, например, о минимальной размерности нечеткой матрицы, имеющей заданные индекс и период, о реализуемости индексов и периодов нечеткими матрицами фиксированной размерности, об устройстве нечеткой матрицы с заданными индексом и периодом, о максимальном индексе и периоде нечеткой матрицы фиксированной размерности, а также вопрос об индексах и периодах нечетких графов того или иного типа (под индексом и периодом нечеткого графа будем понимать индекс и период его матрицы смежности).
Ответы на эти вопросы позволят решать задачи управления поведением, задачи синхронизации и диагностирования нечетких автоматов. Некоторые из перечисленных выше задач успешно решались для частных случаев нечетких матриц, таких как булевы матрицы, стохастические матрицы. Так в первую очередь исследовались идемпотенты булевых матриц (матрицы имеющие индекс равный нулю и период равный единице), поскольку их характеризация в алгебраических системах важна как для построения структурной теории таких систем, так и в приложениях (см. [51, 55]). Первая характеризационная теорема об идемпотентах над булевой алгеброй была получена в 1963 году Розенблаттом (Rosenblatt D., см. [65]), им были описаны графы идемпотентных булевых матриц. Далее, Шейным (Schein В., [70]) идемпотентные булевы матрицы были охарактеризованы в терминах квазипорядков. Грегори, Киркленд и Пуллман (Gregory D., Kirkland S., Pullman N.) в [45], установили, что идемпотентная булева матрица может быть редуцирована к некоторой блочной форме одновременной перестановкой строк и столбцов. Из последних результатов в данной области " следует отметить работу [3], в которой Бисли Л.Б., Гутерман А.Э., Канг К.-Т. и Сонг С.-З. получили новую структурную характеризацию идемпотентных : булевых матриц над бинарной булевой алгеброй. Данная характеризация применяется авторами для описания всех булевых матриц мажорирующихся идемпотентами.
Отдельно изучались перестановочные двоичные булевы матрицы. Так независимо друг от друга Ким [49] и Шварц [68] сф ормулировали необходимое условие сходимости последовательности степеней перестановочных двоичных булевых матриц. В 1997-1999 годах независимо друг от друга Аткин (Atkin A.O.L) [28] и Мартин Гавалек (Gavalec М.) [41] вывели оценку периода для перестановочных нечетких матриц.
Так же особый интерес представляют собой оценки сверху значений индекса и периода нечеткой матрицы общего вида. Шварц в своей работе [69] показал, что индекс двоичной булевой матрицы размерности п не может превосходить (я-l) , аналогичную оценку получил Розенблатт в [64]. Ли в работе [57] показал, что период нечеткой матрицы размерности п делит [nj, где [п]- наименьшее общее кратное чисел 1,2,...и. В [56] Ли (Li J.X.) показал, что для индекса нечеткой матрицы справедлива оценка Ind(A) (n-l)[n]. Гавалек в [42] показал, что задача вычисления периода нечеткой матрицы является NP-полной.
Таким образом, всё вышесказанное определило актуальность следующей цели.
Цель работы. Целью работы является исследование и разработка нечетких математических моделей дискретных систем (нечетких автоматов, нечетких матриц и нечетких графов), а также исследование таких характеристик нечетких матриц и графов как их индекс и период.
Для достижения данной цели необходимо решить следующие задачи:
-разработать формальный аппарат (принципы) построения математических моделей для исследования нечетких систем (задача синтеза);
-разработать методы структурной декомпозиции и моделирования нечетких систем (задача анализа);
-разработать программные комплексы для моделирования и исследования функционального поведения нечетких дискретных систем.
Методы исследования. В работе использовались методы теории конечных автоматов и теории графов, теории алгоритмов и теории решеток, методы универсальной алгебры и логики, теории чисел и полугрупп.
Достоверность и обоснованность научных положений и результатов исследований подтверждаются корректностью применения апробированного математического аппарата универсальной алгебры, теории полугрупп, математической логики, а также согласованностью теоретических результатов с данными, полученными экспериментальным путем автором и другими исследователями.
Научная новизна диссертации заключается в следующем:
- для нечетких моделей дискретных систем: нечетких автоматов без функции выхода (полуавтоматов), нечетких автоматов с функцией выхода введены понятия подавтомата, гомоморфизма, конгруэнции, фактор-автомата; для введенных конструкций доказаны теоремы о гомоморфизмах; показано, что множество конгруэнции и множество подавтоматов нечеткого автомата (также полуавтомата) являются решетками;
- на основе полученных теоретических данных предложен новый алгоритм, строящий наибольшую конгруэнцию нечеткого автомата (также полуавтомата), содержащуюся в некотором отношении эквивалентности на множестве его состояний; на основе данного алгоритма предложен новый метод минимизации нечеткого автомата;
- проведен компьютерный эксперимент по подсчету индексов и периодов нечетких матриц фиксированных размерностей: до размерности 6x6 - нечеткие матрицы с числом порогов равным двум и до размерности 4x4 с числом порогов до четырех включительно; показано, что не все индексы реализуются нечеткими матрицами фиксированной размерности;
- получены оценки для индексов и периодов нечетких графов определенных типов; решены задачи нахождения индексов и периодов некоторых видов графов (неориентированные, бесконтурные, функциональные и др.); показано, что индекс нечеткой матрицы размерности (индекс п-вершинного нечеткого графа) не превышает (п-\) ; данная оценка лучше оценки, полученной ранее Ли [56];
- разработан программный комплекс для исследования свойств нечетких моделей дискретных систем (нечетких автоматов, нечетких полуавтоматов); разработан программный комплекс, позволяющий использовать компьютеры локальной сети для нахождения индексов и периодов нечетких матриц больших размерностей;
-рассмотрена возможность применения полученных результатов в моделях биомедицинских систем; показана возможность повышения семантической концентрации информации содержащейся в нечетких моделях за счет снижения степени детализации нечеткости. Научная и практическая ценность работы. Научная ценность работы заключается в разработке понятийного и методологического аппарата для нечетких моделей дискретных систем, что позволяет использовать методы теории конечных детерминированных автоматов при изучении автоматов нечетких. Доказан ряд теорем применительно к нечетким автоматам. Предложить новый метод минимизации нечетких автоматов. Данный метод позволяет уменьшить число состояний нечеткого автомата и упростить его техническую реализацию. В случае с экспертными системами это позволяет повысить семантическую концентрацию информации, а также снизить степень детализации нечеткости.
Полученные новые оценки для индексов и периодов нечетких матриц и графов определенных типов, а также решенные в рамках исследования задачи нахождения индексов и периодов некоторых видов графов (неориентированных, бесконтурных, функциональных и др.) позволят исследователям решать задачи управления поведением, задачи синхронизации и диагностирования нечетких автоматов.
Разработанные программные комплексы позволяют исследовать -свойства нечетких моделей дискретных систем (нечетких автоматов, нечетких полуавтоматов), а также использовать компьютеры локальной сети для нахождения индексов и периодов матриц больших размерностей (данная задача является NP-полной).
Полученные теоретические результаты позволяют повысить семантическую концентрацию информации содержащейся в нечетких моделях биомедицинских систем за счет снижения степени детализации нечеткости, что позволяет получить качественные суждения о состоянии больного при моделировании в терминах «хорошее», «удовлетворительное», «критическое», а не в терминах n-состояний в которых может находиться модель. На защиту выносятся:
-понятийный и методологический аппарат для нечетких полуавтоматов и собственно нечетких автоматов;
-теоремы о гомоморфизмах, конгруэнциях и фактор-автоматах нечеткого полуавтомата и собственно нечеткого автомата;
-множество подавтоматов и множество конгруэнции нечеткого полуавтомата и собственно нечеткого автомата являются решетками;
-новый метод построения наибольшей конгруэнции для нечеткого полуавтомата и собственно нечеткого автомата; новый метод минимизации нечеткого полуавтомата и собственно нечеткого автомата;
-оценки для индексов и периодов нечетких матриц и графов определенных типов;
-решение задач по нахождению индексов и периодов некоторых видов графов (неориентированных, бесконтурных, функциональных и др.);
-программный комплекс, позволяющий использовать компьютеры локальной сети для нахождения индексов и периодов нечетких матриц больших размерностей;
-программный комплекс для исследования свойств нечетких моделей дискретных систем (нечетких автоматов, нечетких полуавтоматов).
Апробация работы. Основные результаты диссертационного исследования докладывались и обсуждались на XIV и XV Международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов» (МГУ, г. Москва, 2007, 2008 г.); Международной научной конференции «Компьютерные науки и информационные технологии» (СГУ, г. Саратов, 2007 г.); VIII Всероссийской научно-технической конференции. (ВСГТУ, г. Улан-Удэ, 2007 г.); Ежегодной конференции по итогам научно-исследовательской работы Саратовского государственного социально-экономического университета «Социально-экономическое развитие России: Проблемы, поиски, решения» (Саратов, 2007, 2008 г.). Публикации. Основные результаты опубликованы в работах [М1]-[М12]. Работа [МЗ] опубликована в издании, включенном в «Перечень ведущих рецензируемых научных журналов и изданий, в которых должны быть опубликованы основные научные результаты диссертации на соискание ученой степени доктора и кандидата наук». Разработанный автором программный комплекс для исследования свойств нечетких моделей дискретных систем зарегистрирован в Отраслевом фонде алгоритмов и программ [М8].
Структура и объем диссертации. Работа состоит из введения, трех глав, заключения, библиографии, включающей 81 наименование, и трех приложений. Общий объем работы 130 стр.
В первой главе диссертационного исследования излагаются основные понятия и обозначения из алгебры отношений, теории упорядоченных множеств, а также теории решеток, систематически используемые в диссертации. Более специальные определения вводятся в начале каждой главы.
Вторая глава исследования посвящена методам анализа и синтеза конечных нечетких автоматов. Приведенные в работе исследования нечетких автоматов следуют уже сложившемуся и традиционному кругу вопросов анализа и синтеза конечных детерминированных автоматов: принципиальное значение имеют теоремы о гомоморфизмах, конгруэнциях и фактор-автоматах, задачи минимизации. Данные вопросы, например, успешно решались для булевозначных автоматов Салием В. Н. [20].
Третья часть диссертационного исследования посвящена исследованию функционального поведения нечетких автоматов, а именно исследованию таких характеристик его матриц и графов переходов как индекс и период.
Сделаем несколько замечаний технического характера. Нумерация теорем, лемм, следствий и примеров в диссертации сквозная с учетом номера главы и номера раздела, нумерация формул своя в каждом разделе. Например, ссылка «теорема 2.1.7» означает теорему 2.1.7 из первого раздела второй главы. Окончание доказательства обозначается символом П.
Элементы алгебры отношений и упорядоченных множеств
Бинарным отношением между множествами А и В называется любое подмножество декартова произведения Ах В. Таким образом, подмножество представляет собой некоторое множество пар (a,b), где а є А, ЬєВ. Обычно мы будем обозначать отношения строчными греческими буквами, например р, и писать pczAxB. Определение 1.1.2 Пусть А, В - произвольные множества и р - бинарное отношение между элементами множеств А и В (рс:АхВ). Положим по определению, что р 1 =1 (Ь,а)єВхА\(а,Ь) =р\ и для произвольных а є A, XczA р(а) = [Ъ еВ\(а,Ь) є р), р(х) = {be в\(3а є Х)((а,Ь) є р)} . Определение 1.1.3 Пусть р, т с Ах А, т.е. являются бинарными отношениями между элементами множества А, тогда их композиция рост определяется следующим образом: рост — \{а,с) є Ах А\(ЗЬ єА)((а,Ь) єр&(/?,с)єоч.
Определение 1.1.3 Пусть А 0 и pczAxA, тогда: 1) Если отношение р такое, что {Уа,Ьє A)\ia,b) є р = a = b), то отношение р называется тождественным и обозначается как АА ; 2) р называется рефлексивным, если (Уа є А)((а,а) є /?); 3) р называется симметричным, если (\/а,Ь є A)\ia,b) є р= (Ь,а)є. р); 4) р называется антисимметричным, если (\/а,Ьє A){ia,b)e р8і{Ь,а)є. р= a-b j; 5) р называется транзитивным, если (\/а,Ъ,с є A)((a,b) є p&(b,c)ep= (а,с) є /?); Определение 1.1.4 Отношение р на множестве А называется отношением порядка (или сокращенно «порядком», также иногда называют «частичным порядком»), если оно рефлексивно, антисимметрично и транзитивно. Тождественное бинарное отношение АА является порядком на множестве А, который называют тривиальным. Часто для обозначения порядка р используют также символ и вместо (a,b) є р пишут а b. Если для любых а,Ь є А либо а b, либо Ъ а то такой порядок называют полным. Определение 1.1.5 Упорядоченным множеством (у - множеством, частично упорядоченным множеством) называется пара (А, ), где А непустое множество, а бинарное отношение порядка на А. Выражение а Ь читается по-разному: «а меньше (меньше или равен, не больше, содержится в, включается в) Ь» или соответственно «Ь больше (больше или равен, не меньше содержит, включает) а. Тот же смысл имеет и запись Ъ а. Наконец, в том случае, когда а Ъ и аФЪ, пишут знак строгого неравенства: а Ь или Ъ а. Отметим, что в каждом конкретном случае в упорядоченном множестве для обозначения порядка, как правило, имеется свой традиционный знак.
Пример 1.1.1 1) Множество N натуральных чисел с естественным для них порядком ; 2) Для произвольного множества А через Р(Л) обозначим множество всех его подмножеств. Теоретико-множественное включение с: упорядочивает множество Р(А); 3) (Ж) множество всех натуральных чисел N с отношением делимости, которое для чисел т,пєЩ определяется по формуле: т п = (Зк є iV)(w = mk). Определение 1.1.6 Наименьшим (наибольшим) элементом упорядоченного множества (А, ) называется его элемент 0-ноль (1-единица), удовлетворяющий в (А, ) тождественному неравенству 0 а {а 1), для любого а є А. Очевидно, что каждое упорядоченное множество имеет только один наименьший элемент (очевидное следствие антисимметричности). Пример 1.1.2 1) Число 1 является наименьшим элементом в упорядоченных множествах (N, ) и (N,), однако ни то, ни другое упорядоченное множество не имеет наибольшего элемента. 2) Множество Z целых чисел, упорядоченных обычным отношением , не имеет ни наименьшего ни наибольшего элемента. 3) В упорядоченном множестве (Р( 4),с:) наименьшим будет пустое подмножество 0, а само множество А - наибольшим.
Элемент а упорядоченного множества (А, ) называется минимальным, если в множестве А нет элементов строго меньших чем а. Аналогично элемент а называется максимальным в (А, ), если в этом упорядоченном множестве нет элементов, строго больших, чем а. Эти конструкции таковы: 1) Если L - является решеткой по определению 1.2.1, тогда определим на L таким образом, что а b тогда и только тогда, когда а = а лЬ. 2) Если L - является решеткой по определению 1.2.4, тогда определим операции v и л: avb- sup {а, 6}, а лЬ = mf{a,b}. Определение 1.2.5 Частично упорядоченное множество А называется полным, если для любого его подмножества А с: А существуют sup A (vA ) и inf + (лА ). Все полные упорядоченные множества являются решетками, а решетка L которая является полной как упорядоченное множество называется полной решеткой. Теорема 1.2.1 (Биркгофф, 1930) Пусть А - упорядоченное множество такое, что лА (W ) существует для любого его подмножества А с: А, тогда А - полная решетка. Также теорема 1.2.1 часто доказывается в следующей формулировке, очевидно эквивалентной предыдущей. Теорема 1.2.2 Частично упорядоченное множество А тогда и только тогда является полной решеткой, когда: 1) оно имеет наименьший элемент 0 (наибольший элемент 1); 2) для любого его непустого подмножества А существует точная верхняя грань vA (существует точная нижняя грань лА )
Методы анализа и синтеза нечетких автоматов без функции выхода
Нечеткая автоматная модель активно использовалась различными авторами для описания поведения систем с неоднозначно определенными состояниями.
Вместе с тем, задачи анализа и синтеза для нечетких автоматов без функции выхода (нечетких полуавтоматов) не рассматривались. Для данного вида нечетких автоматов в данном разделе впервые вводятся такие понятия как гомоморфизм, конгруэнция и фактор-автомат.
В рамках этих понятий доказываются аналоги теорем о гомоморфизмах, описывается решетка конгруэнции нечеткого автомата, так же описывается один из возможных методов минимизации нечеткого автомата, основанный на построении его наибольшей конгруэнции и последующей его факторизации
Нечетким автоматом (или нечетким полуавтоматом) называется тройка A = (S, X, 5), где S и X непустые конечные множества (множество состояний и множество входных сигналов), a S:Sx X- M(S)-отображение, нечеткая функция переходов.
Подмножество S множества S называется устойчивым в нечетком автомате A = (S,X,S), если (V/ ES )(\/XE X)(suppS(s ,x)c: S ), где supp -носитель нечеткого вектора, supp// = {.у є 51 /J(S) 0}.
Нечеткий автомат A ={S ,Х,6 ) называется подавтоматом нечеткого автомата A = (S,X,S), если S - устойчивое подмножество множества состояний нечеткого автомата А, а 8 =8\. v - сужение функции переходов на множестве S .
Далее будем 8 и 8 обозначать через 8, так как смешение здесь вряд ли возможно, а ряд доказательств при этом соглашении выглядят более стройно. Совокупность всех подавтоматов нечеткого автомата А обозначают Sub А. Равенство 8(sl,x)(s2) = l истолковывается следующим образом: автомат А из состояния s{, под действием входного сигнала х может перейти в состояние s2 с мерой / є [0,1]. (В зависимости от ограничений, накладываемых на значения данной меры, можно получить различные виды автоматов: детерминированные, недетерминированные, булевозначные, вероятностные.)
Взаимно однозначные сюръективные гомоморфизмы называют изоморфизмами. Нечеткий автомат В, являющийся гомоморфным образом нечеткого автомата А, представляет собой как бы огрубленную модель А. Он сохраняет основные особенности функционирования А (выражаемые функцией перехода ,), однако, теряет часть информации о состояниях, не различая некоторые из них.
Пусть это не так, и (3s eS2)(3xeX)(suppS(s ,x) S2), т.е. (3s0 eS\S2)(3xeX)(S(s ,x)(s0) 0). С другой стороны так как A{eSubA, то (\/s eS XVxe X)(suppS(s,x) с Sx). Так как S2 е=І5 то s eSr Поскольку S(s\x)(sQ) 0 и Ах является подавтоматом нечеткого автомата А, то по определению s0 є S}.
С другой стороны, рассуждая аналогично, так как S3 S2, то s є S2. Поскольку S(s ,x)(s0) 0 и A2E.Sub А, то по определению S0GS2. Таким образом, ((s0 eSl)&(s0GS2)) = (s0eSlf\S2), что противоречит нашему допущению, т.е. мы доказали, что Аъ є Sub А. Считая пустое множество состояний множеством состояний пустого подавтомата, получаем, что для любых двух подавтоматов существует наибольший из содержащихся в них подавтоматов. Поскольку сам автомат А является наибольшим своим подавтоматом, множество Sub А всех подавтоматов нечеткого автомата А образует решетку относительно теоретико-множественного включения. П
Методы анализа и синтеза нечетких автоматов с функцией выхода
Как уже отмечалось выше, нечеткие автоматы пригодны для моделирования поведения реальных систем, не допускающих «четкого» описания, однако, достаточно часто автоматные модели таких систем имеют функцию выхода, что в случае с нечеткими автоматами затрудняет использование результатов полученных в предыдущем разделе. Необходимо обобщить результаты, полученные в разделе 2.1 на случай нечетких автоматов с функцией выхода.
В данном разделе для нечетких автоматов с функцией выхода впервые вводятся такие понятия как гомоморфизм, конгруэнция и фактор-автомат (определения 2.2.1 - 2.2.6). В рамках этих понятий доказываются аналоги теорем о гомоморфизмах (теоремы 2.2.1 - 2.2.5), описывается решетка конгруэнции нечеткого автомата (теорема 2.2.6), предлагается один из возможных методов минимизации нечеткого автомата основанный на построении его наибольшей конгруэнции и последующей его факторизации (теорема 2.2.7, алгоритм 2.2.1). Важно, что при этом получивший нечеткий автомат будет полностью сохранять функциональное поведение исходного автомата.
В зависимости от ограничений, накладываемых на значения данных мер, можно получить различные виды автоматов: детерминированные, недетерминированные, булевозначные [20], вероятностные). Равенство (1) означает, что если мера уверенности в том, что автомат А переходит из одного состояния в некоторое другое не нулевая, то это равносильно тому, что нечеткий вектор co(s,x) будет ненулевым.
Нечеткий автомат A = (S ,X,Y,S ,a) ) называется подавтоматом нечеткого автомата A = (S, X, Y, S, со), если S - устойчивое подмножество множества состояний нечеткого автомата A, a S =S\ . и со =а \ , -сужения функции переходов и функции выходов соответственно.
Далее будем 5 и д , со и со обозначать через S и со соответственно, так как смешение здесь вряд ли возможно, а ряд доказательств при этом соглашении выглядят более стройно.
Совокупность всех подавтоматов нечеткого автомата А обозначают Sub(A). Пусть cp:S-+T есть некоторое отображение. Оно естественным образом продолжается до отображения множества M{S) в множество М{Т). По определению (p(ju)(t) = max /J(S) , где /л є M(S), a t є Т .
Считая пустое множество состояний множеством состояний пустого подавтомата, получаем, что для любых двух подавтоматов существует наибольший из содержащихся в них подавтоматов. Поскольку сам автомат А является наибольшим своим подавтоматом, множество Sub А всех подавтоматов нечеткого автомата А образует решетку относительно теоретико-множественного включения. П
Покажем выполнение второго условия: co{s,x) = co{sx,х) co{s2,x)-... = o){sk_x,x) = co{s\x) для любых хєХ. Таким образом, получаем, что в является конгруэнцией нечеткого автомата А. Аналогичным образом, методом математической индукции, доказывается тот факт, что наименьшая эквивалентность, содержащая произвольное семейство конгруэнции, также является конгруэнцией. D Лемма 2.2.1 Пусть р - некоторое отношение эквивалентности на множестве состояний нечеткого автомата А, тогда оно содержит в себе семейство конгруэнции, одна из которых - рм является наибольшей в отношении эквивалентности р Доказательство. Семейство конгруэнции не пусто, поскольку, очевидно, содержит в себе As, а наибольшая конгруэнция - рм , очевидно, является объединением всех конгруэнции содержащихся в р (см. теорему 2.2.6). D Пусть р - некоторое отношение эквивалентности на множестве состояний нечеткого автомата А, определим рекурсивно следующую последовательность отношений: Pi=P» Pk=\(s s )ePk-i max S(s,x)(t )= max S(s ,x)(t ),Vt є S,VxєX\ l epk.x t ґєРк і Лемма 2.2.2. Пусть p - некоторое отношение эквивалентности на множестве состояний нечеткого автомата А и {рк},х - семейство определенных выше отношений, тогда /73A2-2A-2-2Pw Доказательство. По построению последовательности {/?А} , очевидно, что включение выполняет, т.е. для (\/к e N)(pk+l с рк). Таким образом, необходимо показать, что (\/к eN)(pM czpk). Докажем данное утверждение индукцией по числу к.
Используя далее теорему 2.2.7, мы можем предложить алгоритм, аналогичный алгоритму 2.1.1, строящий наибольшую конгруэнцию нечеткого автомата А с функцией выхода, содержащуюся в некотором отношении эквивалентности на множестве его состояний. Построение конгруэнции нечеткого автомата A = (S,X,Y,S,a ).
Индексы и периоды нечетких матриц
Как известно, элементы нечеткой матрицы могут принимать любые значение из отрезка однако в силу того, что мы используем минимаксное умножение, конкретные значения элементов матрицы при вычислении индекса и периода не существенны, важны результаты попарного сравнения элементов. Таким образом, задавая порядковые соотношения между элементами, мы получаем целый класс нечетких матриц с одинаковым индексом и одинаковым периодом. Следовательно, чтобы выяснить, какие индексы и периоды реализуемы нечеткими матрицами заданной размерности, необходимо зафиксировать число порогов, рассмотреть все возможные порядковые соотношения между элементами матриц и для матриц - представителей подсчитать значение индекса и периода. Всею сфиксированнымпериодом 67904955351 777386131 33229860 1106670 18504 2780220 Всего:68719476736 Следует отметить, что задача нахождения индексов и периодов нечетких матриц является достаточно сложной и ресурсоемкой, это связано в первую очередь с тем, что данная задача, как показал Гавалек в [42], является NP-полной, а во-вторых, это связано с быстрым ростом числа матриц. Поэтому достаточно естественным представляется: 1) использовать несколько компьютеров локальной вычислительной сети для подсчета индексов и периодов нечетких матриц (а также как частный случай двоичных булевых матриц); 2) создать базу данных индексов и периодов всех нечетких матриц определенных размерностей. Для решения задачи подсчета индексов и периодов нечетких матриц фиксированной размерности (с помощью которой и было получены данные таблиц 3.2.1 — 3.2.8) был разработан специальный программный комплекс состоящий из: 1) сервера баз данных (использовалось готовое решение - MS SQL Server), 2) диспетчера заданий, 3) клиентских частей. Общая схема взаимодействия этих модулей представлена на рисунке 3.2.1.
Метод работы программного комплекса следующий: диспетчер заданий опрашивает базу данных и на основе результата формирует пул необработанных заданий. Клиентские части при запуске обращаются к диспетчеру заданий для получения конкретных заданий из пула на нахождение индексов и периодов некоторой группы нечетких матриц. Диспетчер заданий закрепляет за каждой клиентской частью некоторое задание и периодически опрашивает клиентов о процессе обсчета данных. Если со стороны клиентской части в процессе обсчета произошла какая-либо ошибка, то задание выдается вторично и выполняется заново, если клиент не отвечает, то с выданного ему задания снимается закрепление и оно попадает в пул необработанных заданий. После завершения обсчета клиентские части передают диспетчеру сведения о том, что они закончили обсчет, и отправляют результаты на сервер баз данных; задания считаются выполненными и удаляются из пула; результаты хранятся на сервере баз данных. Если пул заданий не пуст, то клиенты получают новые задания. Как уже отмечалось выше, с помощью данного программного комплекса были обсчитаны двоичные булевы матрицы до размерности 6x6 включительно, было задействовано около 10 клиентов. Обсчет двоичных булевых матриц размерности 6x6 занял около семи часов. В приложении 2. можно ознакомиться с процедурой быстрого умножения булевых матриц использованной в данном программном комплексе.
Направленным (или ориентированным) нечетким графом называется пара G = (V,a), где V - конечное непустое множество (вершины графа), а а — нечеткое отношение на множестве V. Пара (u,v) называется дугой графа (или ориентированным ребром) с началом и и концом v; d(u,v) — значение функции принадлежности для ребра (ii,v) (вес ребра). Причем вершины являются инцидентными в том и только в том случае, если a(u,v) 0. Отношения а называют нечетким отношением смежности, а соответствующую ему нечеткую матрицу А{ос) — нечеткой матрицей смежности графа G.
Легко видеть, что нечеткий орграф является частным случаем взвешенного орграфа, у которого дуги имеют вес из отрезка [0,l]. Говоря об индексе и периоде графа G (нечеткого графа G), будем иметь в виду индекс и период его матрицы смежности (нечеткой матрицы смежности) и писать ind{G) и p(G) (ind(G) и p(G)) соответственно.
Граф, не имеющий контуров, называется бесконтурным. Если для любой пары вершин и и v графа G существует путь из и в v и путь из v в и, то такой граф G называется сильносвязным. Максимальный (по включению) сильносвязный подграф некоторого графа называется его сильносвязной компонентой. Любая сильносвязная компонента может состоять либо из несколько вершин (в данном случае она должна содержать хотя бы один контур), либо из одной вершины и . Сильносвязная компонента состоящая из одной вершины и, и не содежащая петли (и,и) называется ацикличной.
Похожие диссертации на Методы анализа и синтеза математических моделей нечетких дискретных систем
