Методы анализа и синтеза математических моделей нечетких дискретных систем

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

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

Такое поведение систем часто описывается дискретными моделями, в частности, различными видами автоматов.

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

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

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

Первое направление теории автоматов получило развитие в рамках работ академика Глушкова и его последователей, второе — рассматривал в своих работах Арбиб и ряд других исследователей.

Математической моделью устройства преобразования информации является трехосновная алгебраическая система, называемая автоматом, и представляющая собой алгебру, А = (5,X, У,8,со), с тремя основными множествами Б, X, У и двумя бинарными операциями 8:5 х X <5, со-.БхХ^У. При этом, множество? называется множеством состояний, 4 Хмножеством входных сигналов, Умножеством выходных сигналов. Операция 8 — называется функцией переходов автомата и показывает, как входной сигнал х преобразует состояние? в новое состояние ?' = Операция со называется выходной функцией автомата, А и указывает значение сигнала на выходе у — в зависимости от состояния автомата и значения входного сигнала х.

В качестве динамических систем наиболее часто изучают, автоматы вида, А = (5,Х, 8), лишенные функции выхода, так называемые полуавтоматы.

Задачи анализа, синтеза, а также задачи, связанные с исследованием функционального поведения автоматов, нашли отражение в работах Айзермана, Гилла, Трахтенброта, Минского, Шеннона, Джона фон Неймана, Яблонского, Богомолова, Твердохлебова и многих других.

В зависимости от специфики рассматриваемых задач, некоторый объект может моделироваться автоматом, у которого множество состояний и множество выходных сигналов наделены дополнительной математической структурой (например, структурой линейного пространства, упорядоченного множества и другими), которая сохраняется функциями переходов и выходными функциями этого автомата ([8], [16]). Так, многие известные задачи математического моделирования приводят к понятиям линейных [7], упорядоченных [10], булевозначных [20], вероятностью [6] автоматов. Исследованиям таких автоматов посвящены, например, работы Скорнякова Л. А. 23], Сытника A.A. [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 M. K), которые в [59] предложили один из возможных вариантов минимизации нечеткого автомата, а в работе [58] предложили способ описания полугруппы преобразований нечеткого автомата, а также соединений нечетких автоматов (это требовалось при решении конкретных технических задач), однако в силу того, что ими не использовался алгебраический аппарат, построения получились избыточно сложными, громоздкими и не универсальными. В силу этого представляется необходимым привнести алгебраические методы в теорию моделей нечетких систем, что позволит использовать методы теории конечных детерминированных автоматов при решении задач синтеза и анализа автоматов нечетких.

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

Нечеткие матрицы является одним из языков для описания дискретных систем, не допускающих точного описания [13, 21]. Примером такой системы, как уже отмечалось выше, является нечеткий автомат. Функция переходов для каждого входного сигнала нечеткого автомата представляется нечеткой матрицей. Итерации входного сигнала соответствует возведение данной матрицы в степень. В связи с этим, при решении достаточно большого числа задач исследуют степени различных вещественнозначных матриц (нечетких как частный случай), исследуют их поведение относительно различных операций сложения и умножения, как, например, тах-гшп умножение [38, 76], максимум-сложения [29, 67] (линейные системы с синхронизацией).

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

Нечеткие матрицы являются обобщением булевых матриц, которые в свою очередь достаточно давно являются объектом исследования различных авторов. В частности, Поплавским В. Б. в [17, 18] исследовалась последовательность определителей степеней булевых матриц. В свою очередь, теория булевых матриц ведет своё начало от теории матриц с неотрицательными элементами, большинство наиболее известных результатов для которых были получены между 1906 и 1912 годами Перроном и Фробениусом.

Благодаря широким областям применения нечеткой логики, нечеткие матрицы, а так же нечеткие графы используются в области нейронных сетей [33, 52], например, в нечетких клеточных нейронных сетях [74, 75], которые разрабатывались и применялись при решении задач связанных с обработкой изображений. Задача нахождения степеней нечеткой матрицы также тесно связана с такими задачами как исследование функционирования нечеткой двунаправленной ассоциативной памяти, нахождение решений нечетких уравнений отношения (см., например, [66, 77, 39]).

Одними из наиболее важных характеристик нечетких матриц являются значения их индекса и периода. Изучением степеней нечетких матриц одним из первых начал заниматься Томасон (ТЬотазоп), который заметил, что степени нечетких матриц, либо сходятся, либо обладают конечным периодом [76]. Однако следует отметить, что данные характеристики свойственны не только матрицам, но также и всем конечным циклическим полугруппам, и для каждой циклической полугруппы определены две характеристики называемые индексом и периодом циклической полугруппы соответственно (см. [11]).

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

Так как общий состав элементов нечеткой матрицы при возведении её в степень не расширяется, циклическая полугруппа, порожденная нечеткой, матрицей, конечна и потому для каждой такой матрицы, А определены индекс тс1(А) и период р{А).

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

Ответы на эти вопросы позволят решать задачи управления поведением, задачи синхронизации и диагностирования нечетких автоматов. Некоторые из перечисленных выше задач успешно решались для частных случаев нечетких матриц, таких как булевы матрицы, стохастические матрицы. Так в первую очередь исследовались идемпотенты булевых матриц (матрицы имеющие индекс равный нулю и период равный единице), поскольку их характеризация в алгебраических системах важна как для построения структурной теории таких систем, так и в приложениях (см. [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)2, аналогичную оценку получил Розенблатт в [64]. Ли в работе [57] показал, что период нечеткой матрицы размерности п делит [nj, где пнаименьшее общее кратное чисел 1,2,.п. В [56] Ли (1л .1.Х.) показал, что для индекса нечеткой матрицы справедлива оценка 1пс}^А)<{п-)п. Гавалек в [42] показал, что задача вычисления периода нечеткой матрицы является КР-полной.

Таким образом, всё вышесказанное определило актуальность следующей цели.

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

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

— разработать методы структурной декомпозиции и моделирования нечетких систем (задача анализа);

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

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

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

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

— на основе полученных теоретических данных предложен новый алгоритм, строящий наибольшую конгруэнцию нечеткого автомата (также полуавтомата), содержащуюся в некотором отношении эквивалентности на множестве его состоянийна основе данного алгоритма предложен новый метод минимизации нечеткого автомата;

— проведен компьютерный эксперимент по подсчету индексов и периодов нечетких матриц фиксированных размерностей: до размерности 6×6 — нечеткие матрицы с числом порогов равным двум и до размерности 4×4 с числом порогов до четырех включительнопоказано, что не все индексы реализуются нечеткими матрицами фиксированной размерности;

— получены оценки для индексов и периодов нечетких графов определенных типоврешены задачи нахождения индексов и периодов некоторых видов графов (неориентированные, бесконтурные, функциональные и др.) — показано, что индекс нечеткой матрицы размерности пхп (индекс п — вершинного нечеткого графа) не превышает [п-1)2- данная оценка лучше оценки, полученной ранее Ли [56];

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

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

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

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

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

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

На защиту выносятся:

— понятийный и методологический аппарат для нечетких полуавтоматов и собственно нечетких автоматов;

— теоремы о гомоморфизмах, конгруэнциях и фактор-автоматах нечеткого полуавтомата и собственно нечеткого автомата;

— множество подавтоматов и множество конгруэнций нечеткого полуавтомата и собственно нечеткого автомата являются решетками;

— новый метод построения наибольшей конгруэнции для нечеткого полуавтомата и собственно нечеткого автоматановый метод минимизации нечеткого полуавтомата и собственно нечеткого автомата;

— оценки для индексов и периодов нечетких матриц и графов определенных типов;

— решение задач по нахождению индексов и периодов некоторых видов графов (неориентированных, бесконтурных, функциональных и др.);

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

— программный комплекс для исследования свойств нечетких моделей дискретных систем (нечетких автоматов, нечетких полуавтоматов).

Апробация работы. Основные результаты диссертационного исследования докладывались и обсуждались на XIV и XV Международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов» (МГУ, г. Москва, 2007, 2008 г.) — Международной научной конференции «Компьютерные науки и информационные технологии» (СГУ, г. Саратов, 2007 г.) — VIII Всероссийской научно-технической конференции. (ВСГТУ, г. Улан-Удэ, 2007 г.) — Ежегодной конференции по итогам научно-исследовательской работы Саратовского государственного социально-экономического университета «Социально-экономическое развитие России: Проблемы, поиски, решения» (Саратов, 2007, 2008 г.).

Публикации. Основные результаты опубликованы в работах [М1]-[М12]. Работа [МЗ] опубликована в издании, включенном в «Перечень ведущих рецензируемых научных журналов и изданий, в которых должны быть опубликованы основные научные результаты диссертации на соискание ученой степени доктора и кандидата наук». Разработанный автором программный комплекс для исследования свойств нечетких моделей дискретных систем зарегистрирован в Отраслевом фонде алгоритмов и программ [М8].

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

Работа состоит из введения, трех глав, заключения, библиографии, включающей 81 наименование, и трех приложений. Общий объем работы 130 стр.

Заключение

.

В данной работе разработан понятийный и методологический аппарат для нечетких полуавтоматов и собственно нечетких автоматов. Для данных видов автоматов введены понятия подавтомата, гомоморфизма, конгруэнции, фактор-автомата (определения 2.1.1−2.1.7, 2.2.1−2.2.7). Для введенных конструкций разработаны и доказаны теоремы о гомоморфизмах и конгруэнциях (теоремы 2.1.1−2.1.5, 2.2.1−2.2.5). Показано, что множество конгруэнций и множество подавтоматов нечеткого автомата (а также и нечеткого полуавтомата) являются решетками (теоремы 2.1.2, 2.1.6, 2.2.2, 2.2.6) .

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

Рассмотрены задачи связанные с нахождением индекса и периода нечетких матриц, а также двоичных булевых матрицпоказана пеминимальность алгоритма Клиффорда-Престона (пример 3.1.1).

Проведен компьютерный эксперимент по подсчету индексов и периодов нечетких матриц фиксированных размерностей: до размерности 6×6 -нечеткие матрицы с числом порогов равным двум и до размерности 4×4 с числом порогов до четырех включительно (таблицы 3.2.1−3.2.8), в результате чего был обнаружено то, что не все индексы реализуются нечеткими матрицами фиксированной размерности.

В работе получены новые оценки для значений индексов и периодов нечетких матриц определенных типов (теоремы 3.3.5−3.3.8), решены задачи (теоремы 3.3.9−3.3.14) нахождения индексов и периодов некоторых видов графов (неориентированные, бесконтурные, функциональные и др.).

Показано, что индекс нечеткой матрицы размерности п х п (индекс п-вершинного нечеткого графа) не превышает [п -1)2(теорема 3.3.3) данная оценка лучше оценки, полученной ранее Ли (теорема 3.3.1).

Разработан программный комплекс [М8] (зарегистрирован в Отраслевом Фонде Алгоритмов и Программ) для исследования свойств нечетких моделей дискретных систем (нечетких автоматов, нечетких полуавтоматов). Разработан программный комплекс, позволяющий использовать компьютеры локальной сети для нахождения индексов и периодов нечетких матриц больших размерностей;