научная статья по теме ЭКСПЕРИМЕНТЫ С НЕЧЕТКИМИ АВТОМАТАМИ Автоматика. Вычислительная техника

Текст научной статьи на тему «ЭКСПЕРИМЕНТЫ С НЕЧЕТКИМИ АВТОМАТАМИ»

Автоматика и телемеханика, № 2, 2015

Логическое управление

© 2015 г. Д.В. СПЕРАНСКИЙ, д-р техн. наук (Speranskiy.dv@gmail.com) (Московский государственный университет путей сообщения)

ЭКСПЕРИМЕНТЫ С НЕЧЕТКИМИ АВТОМАТАМИ

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

1. Введение

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

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

Очевидно, что для адекватного отражения нечеткости исходной информации требуется соответствующий математический инструментарий. Важным шагом на пути получения подходящего инструментария явилось создание Л. Заде теории нечетких множеств [2] и разработка на этой основе различных

теорий, включая теорию нечетких алгоритмов, нечетких отношений, нечеткой логики, нечетких графов и т.п.

Подтверждением полезности и эффективности концепции нечеткости (размытости) являются также многочисленные практические приложения таких теорий в различных предметных областях [3].

Сказанное выше в полной мере относится и к теории автоматов. Так, в последние годы значительный интерес проявляется к агрегированным системам, поскольку в них появляются новые качества, не сводящиеся к качествам их частей в отдельности. Это позволяет создавать более адекватные модели реальных сложных систем. Отдельные компоненты таких систем могут быть как детерминированными, так и нечеткими блоками. Что касается последних, то в них нечеткость может относиться и к алгоритмам функционирования и к исходным данным, и значениям на выходах системы. В статье формализуется понятие нечеткости в смысле первой из упомянутых ипостасей. Многие современные системы содержат блоки обеих упомянутых категорий. Для таких систем, как и вообще систем любого типа, всегда актуальны процедуры их контроля и диагностики. Известно, что реализация таких процедур требует проведения с ними специального вида экспериментов, которые исследуются ниже.

2. Описание объекта исследования

Различные разновидности нечетких автоматов (НА) начали рассматриваться в научной литературе сразу после появления основополагающей работы Л. Заде [2] по нечетким множествам. В монографии Д. Дюбуа и Г. Прайда [4] прослежена эволюция и приведена библиография работ в этом направлении. Не вдаваясь в детали, отметим, что появляющиеся разновидности НА отличались друг от друга варьированием требований к начальному состоянию (четкие и нечеткие), к функциям выходов (четкие и нечеткие), к функциям принадлежности реакций НА на различные входные сигналы.

Известно, что нечеткие отношения (п-арные), играющие важную роль при определении НА, можно задавать с помощью его функции принадлежности

^ : Х\ х Х2 х ... х Хп — Ь,

где Ь в случае НА чаще всего представляет собой отрезок [0,1] вещественной прямой. Вместе с тем в качестве Ь могут быть взяты и другие множества. В частности, Ь может быть каким-либо множеством неотрицательных вещественных чисел, отличных от [0,1], либо множеством лингвистических переменных, либо полной дистрибутивной решеткой, либо множеством т-мерных векторов и т.п.

Исходя из сказанного различные типы НА могут быть определены в зависимости от выбора множества Ь и операций, используемых при вычислении функции переходов НА. Так, если Ь - полная дистрибутивная решетка, то Ь - частично упорядоченное множество, в котором любое непустое подмножество имеет наибольшую нижнюю и верхнюю грани и операции пересечения Л и объединения V в Ь удовлетворяют законам дистрибутивности. Все операции над нечеткими отношениями определяются с помощью этих операций

из L. К примеру, если в качестве L выбирается ограниченное множество вещественных чисел, то операции взятия наибольшей и наименьшей верхней грани в L будут соответственно операции SUP и INF, операциями пересечения Л и объединения V будут операции MIN и MAX, и эти операции будут определять и операции над нечеткими отношениями.

Перейдем теперь к определению НА, которое будет использоваться в дальнейшем.

Нечетким конечным автоматом назовем пятерку

(2.1) A = (S,X,Y,5,A),

где S = {si,...,sn} - конечное множество состояний, X = {xi,...,xm} -конечное множество входов, Y = {yi,... , yp} - конечное множество выходов, 5 : S х X х [0,1] — S - функция переходов, A : S х X х [0,1] — Y - функция выходов. Функция 5 имеет следующую интерпретацию: НА, находящийся в состоянии s, под воздействием входа x переходит в состояние s', причем значение функции принадлежности элемента (s, x, s') нечеткому подмножеству S х X х S равно некоторой величине q € [0,1].

Функция 5, введенная выше, фактически порождает множество нечетких матриц T(x) для каждого входа x € X:

(2.2) T(x) = [ßx(si,sj)], 1 < i,j < n.

Каждая такая матрица является квадратной, ее строки и столбцы соответствуют состояниям множества S. На пересечении i-й строки и j-го столбца стоит величина ßx(si,sj) € [0,1], являющаяся оценкой степени возможности перехода НА из состояния si в состояние sj при воздействии входа x.

Некоторые классические определения различных типов автоматов являются частными случаями приведенного определения НА. Так, если из какого-либо состояния s при входе x возможен переход в несколько различных состояний (например, в si и s2), то такой автомат называется недетерминированным. В этом случае в строке матрицы T(x), соответствующей состоянию s, в столбцах si и s2 должны стоять единицы, а в остальных - нули. Если же в каждой строке матрицы T(x) для каждого входа x € X имеется ровно одна единица, то такой автомат называется детерминированным.

По аналогии с [4] введем функцию выхода A : S х X х [0,1] — Y, имеющую следующую интерпретацию: НА, перешедший в состоянии s под воздействием входа x, инициирует выход у, причем значение функции принадлежности элемента (s,x,y) нечеткому подмножеству S х X х Y равно некоторой величине q € [0,1].

Введенная функция A фактически порождает множество матриц Л^) для каждого входа x € X:

(2.3) Лф = [vx(si, yj)] , 1 < i < n, 1 < j < p.

Каждая такая матрица является прямоугольной, ее строки соответствуют состояниям множества S, а столбцы - выходам НА из множества Y. На пересечении i-й строки и j-го столбца стоит величина vx(si,yj) € [0,1], яв-

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

Рассмотрим пример НА, имеющего множество состояний 5 = {1, 2, 3, 4} и множество входов X = {0,1}. Предположим, что матрицы Т(х) для этого НА имеют следующий вид:

0 0,7 0 " 0 0 0 0 0 0 • 0 0,2 0 _

Как следует из содержимого этих матриц, например, при входе х = 0, НА переходит из состояния 1 в состояние 2 со значением ^о(1,2) = 0,5, а из состояния 1 в состояние 3 со значением ^о(1, 3) = 0,8. Аналогично, переход НА при входе х = 0 из состояния 4 в состояние 2 и ^0(4, 2) = 0,6, переход из состояния 4 в состояние 3 со значением ^о(4, 3) = 0,4.

Условимся далее указанные переходы ¿(в, х) записывать в следующем виде:

¿(1, 0) = {(210,5), (310,8)}, ¿(4, 0) = {(2|0,6), (3|0,4)}.

Введем также следующие обозначения:

а) ¿^(в, х) = {в^,.. •, вгк } - это подмножество состояний НА, в которые он переходит из состояния в под воздействием входа х. Так, для данного примера ¿5(1, 0) = {2, 3}, ¿^(4, 0) = {2, 3};

б) ¿Дв,х) = , • • •, } - степени возможности перехода НА из состояния в под воздействием входа х в соответствующие состояния из множества ¿5(в, х). Так, для примера ¿Д1, 0) = {0,5, 0,8)}, ¿^(4, 0) = {0,6, 0,4};

в) ¿^(в,х, в')= ^(в,в;) - степень возможности перехода из состояния в в состояние в' при входе х. Так, для данного примера ¿Д1,0,2) = {0,5}, ¿Д4, 0, 3) = {0,4}.

Условимся далее вместо слов "степень возможности перехода из состояния в в состояние в'" писать "степень перехода...".

Пусть Б' = {в,,..., вjv } есть некоторое подмножество множества 5 состояний НА. Переход НА из состояний подмножества Б' при входе х определим следующим образом:

¿(Б',х) = { У ¿(в, ,х) и=1

Пусть для рассматриваемого примера Б' = {в1,в2}, тогда ¿({в1,в2}, 0) = = {¿(в1, 0) и ¿(в20)} = {(210,5), (310,8), (4|0,3)}.

В соответствии с введенным выше обозначением для этого Б' имеем:

¿Д{1, 2}, 0) = {0,5, 0,8, 0,3} и ¿5({1, 2}, 0) = {2, 3, 4}.

Множество состояний, в которые НА переходит из состояния в под воздействием входной последовательности и = х^1,..., х^ определяется так:

¿5(в, и) = ¿5(. . .¿5(¿5(в , хг1), хг2 ) ... хЙ ).

Т(0) =

0 0,5 0,8 0

0 0 0 0,3

0 0 0 0,1

0 0,6 0,4 0

Т(1) =

0

0,4 0,7 0

Вернемся к приме

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком