WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     |
|

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

Максимов Алексей Алексеевич

МЕТОДЫ АНАЛИЗА И СИНТЕЗА МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ НЕЧЕТКИХ ДИСКРЕТНЫХ СИСТЕМ

05.13.18 – математическое моделирование,

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

Автореферат

диссертации на соискание ученой степени

кандидата физико-математических наук

Саратов – 2008

Работа выполнена в ГОУ ВПО «Саратовский государственный социально-экономический университет» и ГОУ ВПО «Саратовский государственный технический университет»

Научный руководитель: Заслуженный деятель науки

Российской Федерации,

лауреат премии Президента РФ,

доктор технических наук, профессор

Сытник Александр Александрович

Официальные оппоненты: доктор технических наук, доцент

Глазков Виктор Петрович

кандидат физико-математических наук,

доцент Богомолов Сергей Анатольевич

Ведущая организация: Институт проблем точной механики

и управления Российской академии наук

(г. Саратов)

Защита диссертации состоится “28” января 2009 г. в 13 часов на заседании диссертационного совета Д 212.242.08 при ГОУ ВПО «Саратовский государственный технический университет» (410054, г. Саратов, ул. Политехническая, 77, Саратовский государственный технический университет, корп. 1, ауд. 319).

С диссертацией можно ознакомиться в научно-технической библиотеке ГОУ ВПО «Саратовский государственный технический университет».

Автореферат разослан “ 24 ” декабря 2008 г.

Ученый секретарь

диссертационного совета А. А. Терентьев

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

Актуальность темы. Развитие науки и техники ведет к всё большему усложнению, как объектов исследования, так и систем, их моделирующих.

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

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

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

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

Впервые модели такого рода ввел в обиход Лотфи Заде. Несколько позже Бартоломеем Коско было показано, что любая математическая система может быть аппроксимирована некоторой нечеткой моделью. Ви и Фу предложили конструкцию нечеткой автоматной модели, являющейся обобщением конструкции детерминированных автоматов, в которой неопределенность выражалась в том, что изменения состояний определялись не однозначно, а также имели некоторую оценку, например из отрезка [0,1]. Данная модель активно использовалась различными авторами для описания поведения систем с неоднозначно определенными состояниями.

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

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

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

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

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

Для достижения данной цели необходимо решить следующие задачи:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Подмножество множества называется устойчивым в нечетком автомате, если, где - носитель нечеткого вектора,.

Pages:     |
|



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.