Оптимизация обобщенных конечно-нестационарных минимаксных нечетких автоматов

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 519. 71
Вестник СПбГУ. Сер. 1. Т. 1 (59). 2014. Вып. 4
ОПТИМИЗАЦИЯ ОБОБЩЕННЫХ КОНЕЧНО-НЕСТАЦИОНАРНЫХ МИНИМАКСНЫХ НЕЧЕТКИХ АВТОМАТОВ*
А. Ю. Пономарева, М. К. Чирков
С. -Петербургский государственный университет,
Российская Федерация, 199 034, Санкт-Петербург, Университетская наб., 7−9
В работе теоретически обоснован и детально разработан специальный метод минимизации числа состояний и построения минимальных форм обобщенного конечно-нестационарного минимаксного нечеткого автомата, основанный на доказанной ранее теореме о связи максиминных и минимаксных произведений нечетких матриц и разработанной методике матричной оптимизации конечно-нестационарного максиминного нечеткого автомата. Доказано, что от заданного обобщенного конечно-нестационарного минимаксного нечеткого автомата можно перейти к максиминному нечеткому автомату того же типа, являющемуся дополнением для исходного минимаксного автомата. Также доказано, что если заданные обобщенные конечно-нестационарные минимаксный и максиминный нечеткие автоматы являются дополнениями друг друга, то их минимальные формы имеют одно и тоже число состояний, что позволяет сначала перейти от обобщенного конечно-нестационарного минимаксного нечеткого автомата к обобщенному конечно-нестационарному максиминному нечеткому автомату, затем минимизировать известным методом преобразующих матриц полученный обобщенный конечно-нестационарный максимин-ный нечеткий автомат и, перейдя обратно к его дополнению, получить минимальную форму исходного обобщенного конечно-нестационарного минимаксного нечеткого автомата. В результате разработаны процедура и соответствующий ей алгоритм минимизации числа состояний и построения минимальной формы обобщенного конечно-нестационарного минимаксного нечеткого автомата. В заключение дан пример применения предложенного специального метода минимизации к заданному обобщенному минимаксному конечно-нестационарному нечеткому автомату. Библиогр. 7 назв.
Ключевые слова: обобщенный конечно-нестационарный минимаксный («оптимистический») нечеткий автомат, обобщенный конечно-нестационарный максиминный («пессимистический») нечеткий автомат, дополнение конечно-нестационарного минимаксного нечеткого автомата, минимальная форма конечно-нестационарного минимаксного нечеткого автомата.
1. Введение. В работе [1] был предложен один метод оптимизации стационарного обобщенного минимаксного (иначе «оптимистического») нечеткого автомата, определенного в работах [2−4]. Кроме того, в работах [5, 6] решена проблема оптимизации абстрактной структуры обобщенного (имеющего выходной алфавит) конечно-нестационарного нечеткого максиминного (иначе «пессимистического») автомата, разработаны теоретически обоснованные алгоритмы минимизации такого автомата по числу состояний, основанные на построении семейств специальных преобразующих матриц. Поскольку в работе [4] установлена связь между обобщенными стационарными автоматами обоих видов — «пессимистическим» и «оптимистическим», основная цель данной работы состоит в установлении подобной связи между обобщенными конечно-нестационарными «оптимистическим» и «пессимистическим» автоматами и разработке метода оптимизации конечно-нестационарного «оптимистического» автомата, опираясь на результаты работ [4−6].
2. Нечеткие множества. Обозначим символом L полную дистрибутивную решетку
L = ([0,1], max, min,
* Работа выполнена при финансовой поддержке РФФИ (грант № 13−01−538).
т. е. замкнутый интервал [0,1] с операциями (где a, b G [0,1])
a + b = max (a, b), ab = min (a, b), (1)
условно называемыми «сложением» и «умножением», и обычным упорядочиванием. В дальнейшем в данной работе условимся использовать знаки, обозначающие «сложение» и «умножение», только для записи (тах-тш)-операций (1), а символ L также для обозначения интервала [0,1]. В отличие от четкого множества, нечеткое множество Z над универсальным множеством U определяется как множество упорядоченных пар Z = {z, mz (z)}, где мz (z) G [0,1] для всех z G U. Функция mz (z) в этом случае называется характеристической функцией степени принадлежности (или просто функцией степени принадлежности) элемента z нечеткому множеству Z. В частном случае при мz (z) G {0,1} для всех z G U нечеткое множество Z будет обычным четким множеством над универсальным множеством U. Будем также обозначать через Cm'-n множество всех (m х п)-матриц над L и называть матрицы из? m& gt-"- нечеткими.
3. Операции над нечеткими множествами и матрицами. Если Zi и Z2 суть нечеткие множества над U, то их объединением называют [7] нечеткое множество Z = Z1 U Z2 с функцией принадлежности mz (z) = MZlUZ2 (z) = max [^Zl (z), mz2 (z)], z G U. Пересечением Zi и Z2 называют нечеткое множество Z = Zi П Z2 с функцией принадлежности = Hz1nz2(z) = min [m^i (z), /-iz2 (z)], z € U. Дополнением нечеткого множества Z называют нечеткое множество Z с функцией принадлежности fJr^-(z) = 1 — yU, Z (z), z (Е U.
Дополнением нечеткой матрицы R = (/лд (а?, aj))mj" € ?т& lt-п называют нечеткую матрицу R? ?т, п с элементами
Мк (аг, aj) = 1 — №(ai& gt- aj) — (2)
Максиминное произведение нечетких матриц R (1) G Lm, n и R (2) G Ln, k определяется как нечеткая матрица R = R (1) о R (2) g Lm, k с элементами
Mr (ai, aj) = Mr (i)or (2) (aj, aj) = maxmin[Mr (i) (aj, as), Mr (2) (ag, aj)]. (3)
g
Минимаксное произведение нечетких матриц R (1) и R (2) определяется как нечеткая матрица R = R (1) * R (2) с элементами
Mr (aj, aj) = Mru)*r (2) (aj, aj) = minmax[^r (i) (aj, ag), Mr (2) (ag, aj)]. (4)
g
4. Типы конечно-нестационарных нечетких автоматов. Пусть X, A, Y — алфавиты соответственно входных символов, состояний и выходных символов. Будем называть нечеткой элементарной автоматной структурой, заданной над L, систему
Л® = (х (ij), Aj, Aj, Y (ij), {FA'-j)(M)}), (5)
где символ ф обозначает один из символов о или *, определяющих типы произведения матриц (3) и (4) соответственно, X (i'-j) С X, Ai, Aj С A, |Ai| = mi, |Aj| = mj, Y (ij) с Y, а {FA'-j) (s, l)} есть совокупность нечетких матриц переходов из состояний алфавита Ai в состояния алфавита Aj, где FA'-j)(s, 1) G Lmi, mj есть матрица, соответствующая паре (xs, y-), xs G X (i'-j), y- G Y (i'-j).
Пусть задано конечное упорядоченное множество элементарных автоматных структур Л® вида (5) и QA — конечное упорядоченное множество финальных распределений степеней принадлежности (вектор-столбцов с элементами из С) состояний множеству конечных состояний в алфавитах А® С А. Обобщенным нечетким конечно-нестационарным автоматом назовем систему
Л® = (X, Л®, У, ГА, ?а (С, С, Со,/а, Ы, Qл& gt-, (6)
где Я, а — структурный граф автомата (конечный, ориентированный, нагруженный граф), имеющий:
— конечное множество вершин С = {со, с,…, с^- 1}, каждой вершине с^, г = 0, й — 1, сопоставлен алфавит состояний г = 0, й — 1, У^ Л^ = Л, |Л^| = ш^-
— начальную вершину с0, для которой задано г, а — начальное распределение степеней принадлежности состояний из Ао множеству начальных состояний-
— конечное множество О направленных ребер, д® € О — ребро, соединяющее вершины е^ и с® —
— однозначную функцию /А: О -& gt- Л®, /(д®) = Л®-, Л® € Л®, причем
У X= X, У У= У-
я%о ее я%о ее
— однозначную функцию у а: С -& gt-• С^а, & lt-рл ((к) = г = 0, й — 1.
Пусть задан нечеткий конечно-нестационарный автомат (6). Выделим в структурном графе какую-либо вершину с® € С. Пусть ^& gt-а (с®) = qA). Рассмотрим один из путей П0®) длины ведущий из начальной вершины со в вершину с® графа, и выпишем последовательность элементарных автоматных структур, отмечающих ребра, образующие этот путь: Л®^, Л® ^,…, Л® —. Рассмотрим любую пару слов (ад,"), ад = х31×32. . хаь, € Х^-1'-^, V = у, лу12. . ук, у^ € V = М, одной
длины? в алфавитах X и У. Множество всех пар таких слов назовем множеством допустимых пар слов для пути По®) и обозначим ¦?доп (п0®)), при этом будем считать, что пустые слова (е, е) €доп (П00). Весом отображения слова ад в слово V, порождаемого путем по®) структурного графа Я, а автомата Л® при заданном г, а, назовем величину
Ф^ад,") = ГА® П® ГА& quot--1 •& lt-"-^Л)®чА'-), (7)
т (c)
где знак П обозначает произведение нечетких матриц одного из двух типов (3), (4),
определенных в п. 3, (ад,") €доп (п0^®)), |ад| = |"| & gt- 0. Если же |ад| = |"| = 0, то
(Д®) (о) ~
фо / (е, е) = га®чА). Обозначим символом По® множество всех путей в структурном
графе автомата, ведущих из начальной вершины со в вершину с® € С, и символом П (® — множество всех таких путей, имеющих длину и введем обозначение
доп (П о®) = идоп (По®)).
-& gt-МС о ('-)
Нечетким отображением, индуцируемым вершиной с® структурного графа автомата ___(Д®) _(?)
Л® при заданном гА, назовем отображение Ф® /:доп (П°®)) -& gt- С, определяемое
выражением
{(-4®)
шах& lt- еп? ф/ '- М при ^о/ = 0, (8)
0 при П 0/ = 0,
где = |V| = 4 = 0,1,…, и 0 — пустое множество. Будем говорить, что нечеткое отображение ф/^) является нулевым отображением, если для всех пар слов
з
'- I ТЭТ_ТТТГЛ TTTLrOU& quot-/"-" fp ¦& gt-
вать спектр взаимосвязанных нечетких отображений
(w, v) G? j-1) выполнено Фз f (w, v) = 0. В целом автомат 4l® будет индуциро-
Ф f =Ф 0^Ф^Ф
соответствующих различным вершинам Cj G C, j = 0, d — 1, его структурного графа.
При этом нулевые отображения в спектре Ф (-4® — можно не учитывать. В зависимости от того, какой тип произведения матриц используется в выражении (7), т. е. какой из знаков о, * должен подразумеваться под символом ф, можно определить следующие два различных типа обобщенных конечно-нестационарных нечетких автоматов 41® (6):
— максиминные (иначе, «пессимистические») обобщенные конечно-нестационарные нечеткие автоматы 4f-
— минимаксные (иначе, «оптимистические») обобщенные конечно-нестационарные нечеткие автоматы 4f.
5. Формулировка задачи. Пусть заданы два нечетких конечно-нестационарных автомата, имеющих одинаковый входной X и выходной Y алфавиты, одно и то же множество ребер G, одинаковые множества вершин C и одну и ту же начальную вершину с0 структурного графа, — автомат 41® (6) и автомат
B® = (X, B®, Y, гв, Gb (G, C, со,/?), QB& gt-, (9)
индуцирующий при заданном г в спектр взаимосвязанных отображений ФБудем называть автоматы (6) и (9) эквивалентными, если они индуцируют одни и те же спектры взаимосвязанных автоматных отображений, обозначим это 4l® ~ B®.
Будем говорить, что автомат 4® (6) находится в минимальной форме, если не существует такого эквивалентного ему автомата B® (9) того же типа, у которого найдется хоть одна вершина с G C, такая что |Aj | & lt- |Bj|. Минимальной формой нечеткого конечно-нестационарного автомата 4® (6) назовем любой эквивалентный ему автомат B® (9) того же типа, находящийся в минимальной форме (обозначим B® = min 4®).
В соответствии с введенными определениями может быть сформулирована следующая задача: задан обобщенный нечеткий конечно-нестационарный автомат 41® (6) и требуется построить его минимальную форму — автомат того же типа B® = min 4l®.
Данная задача решена в работах [5] и [6] путем последовательного применения преобразований с помощью специальных матриц для случая «пессимистических» автоматов 4f. Основная цель данной работы — разработка и обоснование методов минимизации «оптимистических» конечно-нестационарных нечетких автоматов 4f.
6. Связь между автоматами. В работе [4] доказано следующее утверждение относительно произведений нечетких матриц переходов стационарных нечетких обобщенных автоматов А°, В*, которые являются частным случаем конечно-нестационарных нечетких автоматов.
Теорема 1. Пусть (ад, V), ад = ж81 жЯ2 …, V = у-2 …, есть любая пара слов длины й & gt- 0 в алфавитах X, У, а для стационарных обобщенных нечетких автоматов А°, В* выполнено |А| = |В| = т, Еа (хя, у-) = Ев (ж8, у-) = Е (ж8,у-) € ?т, т для всех ж8 € X, у- € У. Тогда, если
а а
Е°(ад, V) = Е (ж84), Е*(ад, V) = П*^*, уи)
4=1 4=1
суть, соответственно, максиминное и минимаксное произведения нечетких матриц переходов, то справедливы следующие соотношения:

4=1 4=1
где согласно (2) ?(хВг, у1г) = (1 —
44®)
Введем следующее определение. Условимся говорить, что Ф есть дополнение нечеткого отображения автомата А® в вершине е®, г € {0, й — 1}, если для
~ - (4®) -(. 4®)
любых (ад, V) €доп (П0®), |ад| = |V|, Ф ® / (ад, V) = 1 — Ф® / (ад, V). Будем называть нечеткий конечно-нестационарный автомат А® дополнением нечеткого конечно-
нестационарного автомата А®, если он индуцирует спектр взаимосвязанных нечетких отображений
Ф (. ®)={1^, ф!4®'-,…, фЙ-
В таком случае оказывается справедливым следующее утверждение.
Теорема 2. Пусть заданы два конечно-нестационарных обобщенных нечетких автомата А° (6) и В* (9), для которых выполнено следующее:
1) г, а = тв, Аг = Вг, для всех С? € С-
2) если для каждой вершины е® € С выполняется) = qAA), то (е®) =
«-(?) ?г* «-(?)
= qА, и множество Цв включает в себя все различные векторы = qА, е® € С-
3) если для ребра д® € Я /л (дг®) = А°, то /в (д®) = В*, где
для всех € X, у- € У, и множество В* включает в себя все такие различные автоматные структуры В*®, д® € Я, е®, е® € С. Тогда для этих автоматов выполняется
А° «В*, А° «В*. (10)
Доказательство. Для того чтобы показать, что 4° «В?, необходимо установить, что автоматы 4° и В?, индуцируют одни и те же спектры взаимосвязанных нечетких отображений Ф () и Ф). Заметим при этом, что согласно определению дополнения автомата В? выполнено Ф) =ф (В/).
Зафиксируем вершину е^ € С. Рассмотрим любой путь О04-) € О04)), который проходит через последовательность вершин е0 = е0, е^,…, е^ = е^, пару слов (ад,») €доп (О04)), |т| = |V| = и пусть этот путь отмечен последовательностью элементарных автоматных структур 4°^, 4°^,…, 4°4−1 ^ в автомате 4°. Запишем вес отображения слова т в слово V (7), порождаемого путем О04) структурного графаА автомата 4°, тогда:
ТТ°Т1(«1−1,"1-)/ 7 (ч) — TT0T7г (i^'--1'-i^'-)/ 7 -(«*)
(и}, у)= гАо || Е^ {ви, 1и) ос?А = гво || ?в {зи, 1и) ос?в'- =
^=1
согласно теореме 1 и условиям теоремы 2.
В силу произвольности выбранного пути О04-) € О0^ можно утверждать, что
— (-4о) ~ (В*) — (4)
Ф4 / (т, V) =Ф 4 / (т, V) для всех пар слов (т, V) €доп (О0/), |т| = |V| = вершина е^ € С тоже была выбрана произвольно, значит можно утверждать, что
ф (-4/) =ф (В/) = ф (В/) и согласно определению эквивалентность автоматов 4° и В?.
Проведя аналогичные рассуждения можно установить, что 4° «В?. Теорема доказана.
Следствие. Если конечно-нестационарные нечеткие автоматы 4° и В? удовлетворяют условиям теоремы 2 и автомат 4° находится в минимальной форме, то автомат В? также находится в минимальной форме, обратно, если автомат
В? находится в минимальной форме, то и автомат 4° находится в минимальной форме.
Справедливость данного следствия очевидна, поскольку указанные конечно-нестационарные нечеткие автоматы согласно (10) эквивалентны, и возможность удаления любого состояния в какой-либо вершине одного из автоматов непосредственно приводит к возможности редукции соответствующего состояния в другом автомате с необходимым преобразованием элементов матриц переходов, начальных и финальных векторов.
7. Алгоритм минимизации автомата 4?. Опираясь на результаты п. 6, можно сформулировать следующую процедуру построения минимальной формы заданного «оптимистического» конечно-нестационарного нечеткого автомата 4? (6):
а) используя теорему 2, построить для автомата 4? его дополнение — автомат
4? = В)°, являющийся «пессимистическим» конечно-нестационарным нечетким автоматом-
б) используя методику минимизации конечно-нестационарных максиминных («пессимистических») нечетких автоматов, предложенную в работах [5, 6], найти минимальную форму автомата — автомат f = min —
в) перейти от полученного автомата f к автомату V?, который согласно теореме 2 и следствию из нее дает решение данной задачи, т. е. минимаксный («оптимистический») нечеткий конечно-нестационарный автомат D* =V} такой, что D* = min A*.
8. Пример. Пусть задан обобщенный «оптимистический» нечеткий конечно-нестационарный автомат A* = (X, A*, Y, rA, GA (G, C, c0, ?& gt-a), Qa), граф которого представлен на рисунке.
X (0,1) = {xq}, Y (0,1) = {yo, yi}, Aq = {ао, а1, а2,аэ}, Ai = jao, ai, 02, 03},
fAq, 1)(O, 0) =
X (1'-1) = {X1},
F
(1,1)
(1, 0)
0, 8 0, 6 1 0, 6
0, 3 0, 9 0, 7 0, 9
0,4 0, 8 0, 7 0, 8
0, 5 0, 9 0, 9 0, 8
Y (1,1) = {У0,У1}
0, 9 1 0, 5 1
0, 7 0, 8 0, 7 0, 3
0, 6 0, 7 0, 9 0, 7
0, 4 0, 3 0, 7 0, 2
fAm)(0, 1) =
F
(1,1)
(1,1)
0, 7 0, 6 0, 3 0,
0, 7 0, 5 0, 9 0,
0, 7 0, 5 0, 8 0,
1 0, 6 0, 8 0,
0, 4 0, 7 0, 8 0,
0, 5 1 0, 9 0,
0, 8 0, 6 0, 5 0,
0, 5 0, 8 0, 9 0,
X (1,2) = {xo, x1}, Y (1,2) = {yo, У1}, A2 = {00,01,02,03},
F
(1,2)
F
(1,2)
(0, 0) =
(1, 0) =
/0, 9 0,1 0, 8 0, 9
/0, 5 0, 8 1 0, 9
0, 9 0, 7 0, 2 0, 8
0, 9 0, 8 0, 6 0,4
0,7 0, 7^
0, 5 0, 6
0, 7 0, 7
0, 8 0, 8
0, 6 0, 6 0, 9 1
0, 7 0, 7
0, 9 0, 9
F
(1,2)
(0,1) =
fA1,2)(1, 1)
0, 7 0, 3 0, 6 0,
0, 1 0, 8 1 0,
1 0, 9 0, 7 0,
0, 5 0, 9 0, 8 0,
0, 6 0, 9 0, 7 0,
1 0, 7 0, 2 0,
0, 8 0, 8 1 0,
0, 5 0, 7 0, 4 0,
А
А
А
А
А
X (°. 2) = {хо}, У (°. 2) = {уо, у 1},
Е
(0,2)
(0, 0) =
/0,9 0,9 0,7 0,
0, 5 0, 6 0, 9 0, 7
0,7 0,5 0,9 0,7
0, 7 0, 7 0, 7 0, 9
X (2,0) = {хо}, У (2'-0) = {уо, У1},
Е
(о, 2)
(0,1) =
/0, 4 0, 8 0, 9 0, 8
0, 4 0, 9 0, 9 0, 8
0, 6 0, 8 0, 8 0, 9
0, 6 1 0, 9 0, 8
Е
(2,о)
(0, 0)
0, 9 0, 8 0, 7 0, 9
ЧА0)
(0,4 0, 7 0, 7 0, 7)
0, 8 0, 8 1
0, 9 0, 8 0, 8 1
0, 4 0, 4 0, 9 1
0, 1 0, 1 0, 5
т qA1) = (0, 6
Е
(2,0)
(0,1)
0, 2 0, 6 0, 8 0, 6
0, 4 0, 6 0, 7 0, 7 1
1 0, 7 0, 7 0, 81 ,
0, 8 0, 9 0, 9 0, 7
(2) qA = (0, 9 0, 9 0, 4 0, 7) т
0, 5 0, 7 0, 5) т,
Требуется построить его минимальную форму. В соответствии с первым шагом
алгоритма из п. 7 для заданного автомата строим автомат, А? = (9) согласно теореме 2, представляющий собой обобщенный «пессимистический» конечно-нестационарный нечеткий автомат с теми же структурным графом и алфавитами входов и выходов, где Во = {& amp-0, & amp-1, & amp-2, & amp-э}, В = {60, 61, 62, 63}, В = {60,61,62,63}, гВ = (0, 7 0, 3 0, 3 0, 3),
Е
(0,1)
Е
(1,1)
(0,0)
(1,0) =
ев1,2)(0, 0)
Е
(1,2)
Е
(0,2)
Е
(2,0)
(1,0)
(0,0)
(0,0) =
qB0) = (0, 6 0, 3
0, 2 0 4 0 0 4
0 7 0 1 0 3 0,11
0 6 0 2 0 3 0 2
0, 5 0 1 0 1 0 2
/0 1 0 0 5 0
0 6 0 2 0 3 0, 7 1
0 4 0 3 0 1 0 3
/0 6 0 7 0 3 0,8
/0 1 0 1 0 3 0, 3
0 0 3 0 5 0,4 1
0 2 0 8 0 3 0, 3
1 0 2 0 2 0, 2
/0 /0 5 0 1 0 4 0, 4
0 2 0 2 0 1 0 1
0 0 4 0 3 0, 3
1 0 6 0 1 0, 1
/0 /0 1 0 1 0 3 0, 3
0 5 0 4 0 1 0,3 1
0 3 0 5 0 1 0, 3
3 0 3 0 3 0, 1
/0 /0 1 0 2 0 2 0
0 2 0 1 0 2 0, 2 1
0 3 0 6 0 6 0, 1
0 1 0 0 0, 5
со 0, 3) т, qB1) = (0, 4
Е
(0,1)
(0,1)
еВм)(1, 1)
ев1,2)(0, 1)
Е
(1,2)
Е
(0,2)
Е
(2,0)
(1,1)
(0,1)
(0,1) =
/0, 3 0, 3
0, 3 0
0, 6 0, 5 0, 2 0, 5
0, 3 0, 9 0
0, 5
0, 4 0 0, 2 0, 5
0, 6
0, 2
0, 1
0, 2
0, 8 0, 6 0 0, 2
30 0
40 20
70 2
10 30 2
30
60
20
0, 5 0, 3 0, 5) т
qB2) = (0,10,10, 6 0, 3) т
А
А
А
А
В
В
0
В
4
В
В
6
0
4
0
В
В
В
В
Далее, в соответствии со вторым шагом алгоритма производим минимизацию автомата с помощью алгоритма, приведенного в работе [6]. Получаем конечно-нестационарный «пессимистический» нечеткий автомат = (X, V*, У, гу, Яу (С, С, с0, /у, уу), } с теми же структурным графом и алфавитами входов и выходов, где У0 = {"о, VI}, VI = {"о, VI,"2}, = {"0,^1}, гу = (0, 7 0, 3),
Е
(0,1)
(0, 0)
Е
(1,1)
(1,0) =
'-0, 2 V0'- 7
'-0,1
0, 6 уД 4
е[1'-2)(0, 0)
Е2)(1,0)
е[0'-2)(0, 0) =
0, 4 0, 2
0 0, 8 0, 3
0, 1 0, 3 0, 8
'-0, 5
0, 6 0, 4
0, 1 0, 5
0
0, 3
0, 5^ 0, 3 0, 1
0, 3^ 0, 5 0, 3
0,4^ 0, 1 0, 3
0, 3 0, 3
Е
(0,1)
(0,1
Еу, 1)(1,1
е[1,2)(0, 1
Е2)(1,1
е2)(0,1
Е
(2,0)/
0, 2
у -(0,0)=0,3 qV0) = (0, 6 0, 3) т
0, 2 0, 6
Е
(2,0)
0, 3 ч0,3
0, 6 0, 5 0, 2
0, 7 0, 9 0, 1
0, 4 0, 5 0, 2
0, 6 0, 2
0, 4 0, 5
0, 3 0, 2 0, 4
0, 4 0, 2 0, 3
0, 3 0, 8 0, 3
0, 4 0, 2
0, 7 0, 2
0, 2 0, 1 0, 5
0, 8 0, 2
0, 4 0, 3
у (0,1
qУ1) = (0,4 0, 5 0, 3) т, qV2) = (0,1 0, 6) т.
Выполняя преобразование V? =, получаем обобщенный конечно-нестационарный «оптимистический» нечеткий автомат = (X, 2*, У, гв, Яв (С, С, С0,/в, ув),^в}, эквивалентный автомату *4*, с теми же структурным графом и алфавитами, что и у автомата У полученного автомата гв = (0, 3 0, 7),
еД0,1)(0, 0) =
0, 8 0, 6 1 0, 3 0, 8 0, 7
Е
(0,1) в
(0,1) =
0, 7 0, 6 0, 3 0, 7 0, 5 0, 8
Е
(1,1) в
(1,0)
0, 9 1 0, 4 0, 2 0, 6 0, 7
0, 5 0, 7 0, 9
ЕД, 1)(1,1)
0, 4 0, 5 0, 8
0, 7 0, 8 0, 6
0, 8 0, 9 0, 5
ев1,2)(0, 0) =
0, 9 0, 7 0, 2
0, 7 0, 5 0, 7
ев1,2)(0, 1)
0, 3 0, 1 0, 9
0, 6 0, 8 0, 7
ев1,2)(1, 0)
0, 5 0, 4 0, 6
0, 6 0, 9 0, 7
ев1,2)(1, 1)
0, 6 0, 5 0, 8
0, 7 0, 2 0, 7
Е
(0,2)
(0,0)
0, 9 0, 5
0, 7 0, 7
еВ, 2)(0, 1)
0, 4 0, 8
0, 6 0, 8
в
Fg-& gt-, 0)=(0:? jj), F& lt-i?'-0,(0,1)=(0:2 0: ?).
q& lt-0) = (0, 4 0, 7) T, q& lt- = (0, 6 0, 5 0, 7) T, q& lt-2) = (0, 9 0, 4) T, и он является минимальной формой исходного автомата Af.
Литература
1. Пономарева А. Ю., Чирков М. К. Об одном методе минимизации обобщенных «оптимистических» нечетких автоматов // Вестн. С. -Петерб. ун-та. Вып. 3. Сер. 1. 2013. С. 75−81.
2. Santos E. S. Maximin, minimax and composite sequential machines //J. Math. Anal. Appl. Vol. 24. 1968. P. 246−259.
3. Kandel A., Lee S. C. Fuzzy Switching and Automata: Theory and Applications. New York: Crane, Russak & amp- Comp. Inc., 1979. 303 p.
4. Хохулина В. А., Чирков М. К. О разложении «оптимистических» нечетких автоматов // Математические модели. Теория и приложения. Вып. 11. СПб.: ВВМ, 2010. С. 134−147.
5. Пономарева А. Ю., Строилов Р. В. Приведенные формы конечно-нестационарных нечетких автоматов // Математические модели. Теория и приложения. Вып. 12. СПб.: ВВМ, 2011. С. 150−166.
6. Пономарева А. Ю., Строилов Р. В., Чирков М. К. Матричные методы построения минимальных форм конечно-нестационарных максиминных нечетких автоматов // Стохастическая оптимизация в информатике. Т. 10. Вып. 1. СПб.: Изд-во С. -Петерб. ун-та, 2014. С. 101−121.
7. Кофман А. Введение в теорию нечетких множеств. М.: Радио и связь, 1982. 432 с.
Статья поступила в редакцию 26 июня 2014 г.
Сведения об авторах
Пономарёва Александра Юрьевна — кандидат физико-математических наук, доцент- a_ponomareva@mail. ru
Чирков Михаил Константинович — доктор физико-математических наук, профессор- mkchirk@mail. ru
OPTIMIZATION OF GENERALIZED FINITE NON-STATIONARY MINIMAX FUZZY AUTOMATA
Aleksandra Yu. Ponomareva, Mikhail K. Chirkov
St. Petersburg State University, Universitetskaya nab., 7−9, St. Petersburg, 199 034, Russian Federation- a_ponomareva@mail. ru, mkchirk@mail. ru
In the paper it is theoretically ground and elaborated a special method for minimization of the states number and construct a minimal form of a generalized finite non-stationary minimax fuzzy automata which is based on the previously proven theorem about maximin and minimax fuzzy matrices product and elaborated matrix method for optimization of a generalized finite non-stationary maximin fuzzy automata. It is proved that from the given generalized finite non-stationary minimax fuzzy automaton may be turn to generalized finite non-stationary maximin fuzzy automata, which is an addition to the initial minimax automaton. It is also proved that if given the generalized finite non-stationary minimax and maximin fuzzy automata are addition of each other, their minimal forms have the same number of states, which allows first turn from the generalized finite non-stationary minimax fuzzy automaton to generalized finite non-stationary maximin fuzzy automaton, then to minimize this obtained generalized maxmin fuzzy automaton by known method of transform matrix and turn back to its addition, get a minimal form of initial generalized finite non-stationary minimax fuzzy automaton. As a result, the procedure and the corresponding algorithm of minimization of the number of states and construct a minimal form of a generalized finite non-stationary minimax fuzzy automaton worked out. Finally, an example of application of the proposed special method of minimization to the given generalized finite non-stationary minimax fuzzy automaton is given. Refs 7.
Keywords: generalized finite non-stationary minimax (& quot-optimistic"-) fuzzy automaton, generalized finite nonstationary maximin (& quot-pessimistic"-) fuzzy automaton, addition of a finite non-stationary minimax fuzzy automaton, a minimal form of a finite non-stationary minimax fuzzy automaton.

ПоказатьСвернуть
Заполнить форму текущей работой