WWW.DISSERS.RU

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

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

Pages:     ||
|

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

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

Теорема 2.1.1 Пусть - гомоморфизм нечеткого автомата в нечеткий автомат. Тогда:

  1. если, то ;
  2. если, то.

Теорема 2.1.2 Совокупность всех подавтоматов нечеткого автомата вместе с пустым подавтоматом образует решетку.

Пусть - отношение эквивалентности на множестве, а и - два нечетких вектора над. Тогда (т.е. и находятся в отношении эквивалентности ) тогда и только тогда, когда.

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

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

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

Теорема 2.1.6 Множество всех конгруэнций нечеткого автомата образует полную решетку.

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

Теорема 2.1.7 Пусть - некоторое отношение эквивалентности на множестве состояний нечеткого автомата, - семейство отношений, определенных следующим образом:

,

; - наибольшая конгруэнция, содержащаяся в отношении эквивалентности. Тогда, если, то.

Теорема 2.1.7 предлагает способ построения наибольшей конгруэнции нечеткого автомата, содержащейся в некотором отношении эквивалентности на множестве его состояний.

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

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

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

,, - наибольшая конгруэнция, содержащаяся в отношении эквивалентности. Тогда, если, то.

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

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

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

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

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

  • сервера баз данных (использовался MS SQL Server),
  • диспетчера заданий,
  • клиентских частей.

Общая схема взаимодействия модулей программного комплекса

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

В таблице представлены результаты вычислительного эксперимента по подсчету индексов и периодов нечетких матриц с числом порогов, равным двум размерности. Из таблицы видно, что для данных матриц индексы 6 и 7 остаются нереализованными, хотя значения 8 и 9 для индекса допустимы.

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

Период

Индекс

1

2

3

4

Всего с фиксированным индексом

0

2360

1042

156

6

3564

1

25096

2616

48

0

27760

2

24036

480

48

0

24564

3

7164

72

0

0

7236

4

2004

0

0

0

2004

5

360

0

0

0

360

6

0

0

0

0

0

7

0

0

0

0

0

8

24

0

0

0

24

9

24

0

0

0

24

Всего с фиксированным периодом

61068

4210

252

6

Всего: 65536

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

В работе также решаются задачи нахождения индексов и периодов некоторых видов графов (неориентированные, ориентированные, нечеткие).

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

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

Центральное место в данном параграфе занимает следующая теорема.

Теорема 3.3.3 Для любой нечеткой матрицы размерности справедлива следующая оценка.

Данная оценка лучше оценки, полученной ранее Ли.

Графы и называются изоморфными, если существует биекция, сохраняющая отношение смежности: для любых.

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

Теорема 3.3.5 Подобные нечеткие матрицы имеют равные индексы и равные периоды.

Как следствие из этой теоремы устанавливается тот факт, что изоморфные графы имеют равные индексы и равные периоды.

Теорема 3.3.9 Пусть сильносвязный - вершинный орграф, тогда его период.

Теорема 3.3.10 Неориентированный граф имеет период, равный 1 или 2.

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

Теорема 3.3.14 Индекс функционального графа равен уменьшенной на единицу максимальной из высот его элементов, а период – наименьшему общему кратному длин его контуров.

Данные теоремы дают оценки индексов и периодов нечетких матриц и графов определенных типов. В практических целях значения индекса и периода используют для предсказания поведения моделей нечетких дискретных систем, а также для управления этим поведением. Задача нахождения индексов и периодов нечетких матриц и графов является NP-полной, это означает, что их нахождение в реальных системах достаточно затруднительно, например, в биомедицинских системах размерность таких матриц и графов может достигать чрезвычайно больших значений. Теоремы 3.3.7-3.3.14 позволяют оценивать индекс и период через классификацию графа. Алгоритмы классификации, как правило, имеют полиномиальную сложность, что позволяет значительно ускорить процесс отыскания индексов и периодов нечетких матриц и графов.

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

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

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

Pages:     ||
|



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

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