автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Оптимальное поведение периодически нестационарных автоматных моделей в нечетко заданных условиях

кандидата физико-математических наук
Мосягина, Елизавета Николаевна
город
Санкт-Петербург
год
2011
специальность ВАК РФ
05.13.18
цена
450 рублей
Диссертация по информатике, вычислительной технике и управлению на тему «Оптимальное поведение периодически нестационарных автоматных моделей в нечетко заданных условиях»

Автореферат диссертации по теме "Оптимальное поведение периодически нестационарных автоматных моделей в нечетко заданных условиях"

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

Мосягина Елизавета Николаевна

ОПТИМАЛЬНОЕ ПОВЕДЕНИЕ ПЕРИОДИЧЕСКИ НЕСТАЦИОНАРНЫХ АВТОМАТНЫХ МОДЕЛЕЙ В НЕЧЕТКО ЗАДАННЫХ УСЛОВИЯХ

05.13.18 — Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

1 5 и/АР Ш

Санкт-Петербург 2012

005014669

005014669

Работа выполнена на кафедре статистического моделирования математико - механического факультета Санкт-Петербургского государственного университета

Научный руководитель: доктор физико-математических наук,

профессор Чирков Михаил Константинович

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

профессор Фрадков Александр Львович (Учреждение Российской академии наук Институт проблем машиноведения РАН)

доктор физико-математических наук, профессор Демьянович Юрий Каземирович (Санкт-Петербургский государственный университет)

Ведущая организация: Учреждение Российской академии наук

Санкт-Петербургский институт информатики и автоматизации РАН

Защита состоится " " 2012 г. в ' часов на заседании совс

Д 212.232.51 по защите докторских и кандидатских диссертаций при Санкт-Петербур1 ском государственном университете по адресу: 198504, Санкт-Петербург, Петродворс Университетский пр., д. 28, математико-механический факультет, ауд.405.

С диссертацией можно ознакомиться в Научной библиотеке имени М. Горького Сан Петербургского государственного университета по адресу: 199034, Санкт-Петербур Университетская набережная, дом 7/9.

Автореферат разослан " £ " 2012 г.

Ученый секретарь диссертационного совета доктор физико-математических наук, доцент

■■ . _________ Н.К. Кривулин

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

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

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

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

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

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

Цель работы. Целью данной работы является комплексное исследование пpoблe^ синтеза оптимального управления нестационарными детерминированными, недетерми нированными и стохастическими автоматными моделями с периодически меняющийс структурой, обеспечивающего их оптимальное поведение при наложении на входпы управляющие символы различных нечетких ограничений с учетом взаимодействия м делей, если они объединены в систему.

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

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

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

2. Применительно к различным нестационарным автоматным моделям разработа! матричный вариант метода, предложенного Беллмапом-Заде для стационарных а страктных автоматов.

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

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

томатов; в) периодически нестационарных стохастических автоматов; г) периодически нестационарных стохастических автоматов в условиях наличия «тени»; д) систем взаимодействующих периодически нестационарных стохастических и недетерминированных автоматов.

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

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

Научная новизна. Все основные результаты, представленные в диссертации, являются новыми.

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

Апробация работы. Основные результаты работы докладывались на международной научной конференции «6th St. Petersburg Workshop on Simulation» (Санкт-Петербург, 28 июня-4июля 2009г.) и на всероссийской научно-практической конференции «Интегрированные модели, мягкие вычисления, вероятностные системы и комплексы программ в искусственном интеллекте» (Коломна, 26-27 мая 2009г.), а также обсуждались на семинаре кафедры статистического моделирования математико-механического фаг культета СПбГУ. Работа над диссертацией выполнялась в рамках плановой госбюджетной научной темы НИИММ СПбГУ (помер гос.регистрации: 0120. 0804162) и при частичной поддержке грантов РФФИ 07-01-00355 и 10-01-00310.

Публикации. По теме диссертации опубликованы: 1 монография [13] и 12 научных статей, включая 2 статьи [3, 8] в журналах, рекомендованных ВАК, 2 доклада в трудах международной и всероссийской научных конференций [10, 11] и 8 публикаций [1, 2, 4-7, 9, 12] в других изданиях. В публикациях [ 1, 2, 5-7, 13], выполненных в соавторстве, научному руководителю М.К.Чиркову принадлежит постановка задач, а соискательнице - разработка и обоснование методов и алгоритмов их решения и построение модельных примеров.

Структура и объем диссертации. Диссертация состоит из введения, пяти глав, заключения и списка литературы. Текст диссертации изложен на 190 страницах, список литературы содержит 51 наименование.

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

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

Глава 1 посвящена основным определениям, постановке задач и основам методики их решения. В качестве математической модели исследуется нестационарный конечный автомат с периодически меняющейся структурой(периодически нестационарный автомат), в общем случае представляющий собой систему

A = {X^,A^,Y^ir,{^(x,y)},t0,T,n,tp), (1)

где Х(Т\ Y(T\ А- алфавиты входов, выходов и состояний автомата, £0, Т, tp - чис ло структурных тактов в предпериодической, периодической и постпериодической частях автомата, п - число повторений периодической части, и в зависимости от типа исследуемого автомата (детерминированный, недетерминированный, стохастический, нечеткий) начальное условие г и совокупность условий реализации переходов и вы ходов в структурном такте г имеют вид, соответствующий данному тин

автомата:

• для детерминированного автомата Adet ~ начальное состояние а0 и однозначны функции переходов и выходов;

• для недетерминированного автомата And - вектор начальных состояний г = = (ПьП, • • • i), Ti € {0,1}, и совокупность матриц у)} переходов и выходо с элементами D^(x,y) G {0,1};

• для стохастического автомата Apr ~ вектор распределения вероятностей началь ных состояний г и совокупность матриц {Р(т'(ж,г/)} вероятностей переходов и выходо с элементами P^j\x,y) = Pr(ajy\aix)',

• для нечеткого автомата Aj - нечеткий начальный вектор г = (г0,Г\,...,rmo_i), r-j е [0,1], и совокупность нечетких матриц {R(T)(a:,f/)} переходов и выходов с элемен тамиД^т)(х,у)е[0,1].

Автомат А функционирует в некоторых нечетко заданных условиях, заключающихся в наложении в каждом текущем такте t на входные символы автомата xSt G А"'1"'1" нечетких ограничений С" = CT<t\ которые являются нечеткими множествами со значениями функции принадлежности fiT(xSt), как правило зависящими от т, x3t, а в более сложных случаях и от , yit_t.

Пусть VС) есть множество альтернатив (в нашем случае это может быть множество состояний А^ или выходных символов yW) периодически нестационарной автоматной модели А в структурном такте т = N. Нечеткой целью функционирования автоматной модели А в текущем такте t, r(t) = N, условимся называть нечеткое подмножество GN множества V^ с функцией принадлежности /zG« : V—♦ [0,1].

Пусть для периодически нестационарной автоматной модели А задана единственная нечеткая цель в структурном такте т = N и пусть w = x3lxS2... xst есть входная управ-

ляющая последоватслыюсть(входиос слово), воздействующая на периодически нестационарную автоматную модель и оканчивающаяся в структурном такте r(i) = N. Результатом такого воздействия с учетом заданных нечетких ограничений также будет некоторое нечеткое множество GN(w) в множестве альтернатив такое, что GN(w) Ç GN. Будем говорить, что входная управляющая последовательность w = xBlxS2... x3t обес^ печивает оптимальное, поведение периодически нестационарной автоматной модели А в структурном такте r(i) = N, если для любой входной последовательности той же длины w' = x9lXg2 ...Xgt, r{t) = N, GN(w') Ç Gn и для максимальных элементов векторов HçN(w') и HqN(w) выполняется

max[nçN(и/)] < max[^gN(u))], для всех w' S XN.

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

Av = (XÎT\A(j\Yf\rv,{J?V(x,y)},t0,T,n,tp), (2)

которые имеют одинаковые i0, Т, n, tp и функционируют одновременно в последовательных тактах £ = 0,1,2____При этом на их входные символы накладываются различные

нечеткие ограничения CJ, v = l,q, и в структурных тактах i0 < тц = N < io + Т и тм = M = to+T+t,, заданы нечеткие цели G„ и G™, зависящие от номера v автоматной модели, а также коэффициенты, учитывающие важность се текущих параметров.

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

На начальном этапе решения задачи исследуемый периодически нестационарный конечный автомат (система таких взаимосвязанных конечных автоматов) представляется в виде последовательности трех нестационарных автоматов (систем), для чего структурные такты исходного автомата (каждого из автоматов системы) разбиваются в соответствии со структурными тактами to < т = N < t0 + Т, т = M = tp, в которых заданы нечеткие цели GN и GM, и структурным тактом N < т = К < < N+T-1, в котором начинается постпериод tp, на структурные такты т = 0,1,..., N, t = N,N+1,...,N + T-1,Nh т = N,... ,К,... ,М. Таким образом каждый из трех полученных автоматов (систем автоматов) будет представлять собой нестационарный конечный автомат (систему нестационарных конечных автоматов), для которого необходимо найти оптимальное управление.

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

удобной для автоматных моделей матричной интерпретацией метода Беллмана-Заде и позволяет (например, в случае нестационарного детерминированного автомата при ограничениях Ст, зависящих лишь от г = т(£) и xst) найти функцию принадлежности заданной нечеткой цели, используя формулы:

ДоОС. ■■■<?) = max max^foj П .. .П nN(xafl) П MgH/^Kv-U^J)),

где Hi(xai),... ~ вектор-столбцы нечетких ограничений, накладываемые на

входные символы x3t в тактах t — 1,2... N, a ¡iGN(/^(а^.,,xSN)) - матрица степеней принадлежности множеству переходов в такте t = N с учетом нечеткой цели G";

где 0.iH_v+l = /^-"+1'(a«jv-i,>a;ejv-i,+ i)i

Оптимальное управление при этом находится последовательной максимизацией величин а ' оптимальные входные воздействия определяются как функция от a,iN_u, v = 1,... N, согласно формуле

xSt+l =7ri+i(ait), t = 0,1,2... ЛГ — 1,

где 7Г(+1 - принятая «стратегия», т. е. принятое правило выбора входного воздействия a;Jt+1 в зависимости от

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

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

При этом дальнейшее решение задачи разделено на два этапа: сначала находится максимально возможная степень достижения нечеткой цели GN = c£N\ затем определяется множество входных слов Zmax Cl'"', обеспечивающих такое достижение нечеткой цели. Выполнение первого этапа основано на справедливости следующего утверждения.

Теорема 1.1. Для заданного нечеткого нестационарного конечного автомата Af множество входных слов Zmax ф Л и существует wopt = xSixS2.. .x3N такое, что

N

выполняется условие Ф;(шор1) = = max (г0 П R^T)(s»r)qW)> в том и только

г= 1

том случае, если r0q^ > 0, где q'0' определяется рекуррентным соотношением

1) = и = О, N — 1, RM= (J RW(i). (3)

хеХМ

Второй этап - построение регулярного выражения для Zmax. Условимся говорить, что множество входных слов Z С X(N) (иначе, язык Z) представлено в автомате Ani= (*(T),A(T>,r0,{D(T>(xa)}.q(JV)). если слово w = х„хя,... x„N 6 2 в .том и только в том случае, когда

т=1

Определим также соотношением

х,Техм

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

Теорема 1.2. Если нечеткий автомат Aj удовлетворяет условиям теоремы 1.1, т. е. Zmax ф А и > 0, и недетерминированный нестационарный абстрактный

автомат And получен ш автомата А/ заменой элементов векторов r0, q(iv) и матриц {R(T'(x)}, которые больше или равны цУшх, на элементы с1» и остальных элементов на «0то множество входных слов Zmax представлено в автомате And, причем его регулярное выражение имеет вид

Zm*x=?0f[&T)$N), (4)

Т — 1

где под операциями «•сложения» и «умножения» понимаются операции объединения и произведения в алгебре регулярных языков.

На основании теорем 1.1 и 1.2 алгоритм, реализующий метод автоматпых-итераций, состоит из следующих шагов.

Нахождение максимальной степени достижения нечеткой цели GN:

1. Определим для каждого структурного такта г € {1... N}^« нечеткие» автоматные матрицы U(r) = (U^lir)mT_limT автомата А/ с элементами u£]_lir = Ц, Rf-iU (х')х

2. Из построенных «нечетких» автоматных матриц U(t), т = 1 ,N, найдем матрицы максимальных весов переходов R(t) = (я£11<т)тт_ьтТ, Для чсго

а) удалим из матриц

и«,

г = 1,7V, все элементы из алфавита Х^) _

б) из каждого полученного объединения весов переходов Ц, г = 1,7V, выберем максимальный элемент, а остальные элементы удалим, и в результате получим элементы матриц максимальных весов переходов R\lllir = max т = 1,N.

3. Последовательно применяя формулу (3), найдем вектор-столбец q(0), и значение = r0q(0), которое и будет являться искомой максимально возможной степенью

достижения нечеткой цели GN.

Определение множества, входных слов Zm!iX\

1. Из матриц удаляются входные символы, умноженные на числовые коэффициенты, значения которых меньше, чем а численные коэффициенты оставшихся входных символов заменяются на «1». В результате получаются матрицы т = 1, N.

2. В финальном векторе элементы > ¡¿¡^ заменяются на «1», а элементы

(N) (N) Л ______

< /¿max - на «О», что позволяет получить вектор конечных состоянии q1"'.

3. В начальном векторе Го = (го,гь... ,rmo_i) элементы и > /¿^ заменяются на «1», а остальные - на «О», и в результате получаем вектор г0.

4. Окончательно регулярное выражение Zmxx находится по формуле (4).

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

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

В п.2.1 главы 2 исследован синтез воздействий, оптимизирующих поведение абстрактного детерминированного автомата без постпериода Л^л = {Х^Т\ А^т\а0, }^T\t0,T). В каждом текущем такте t па входной символ этого автомата, наложено нечеткое огра^ пичснис С' = являющееся нечетким множеством в с функцией принадлежности /¿т (.т.,) G [0,1], X, £ А"(т), и в периодической части автомата для фиксированного структурного такта т = N > tQ задана нечеткая цель GN в А^ с функцией принадлежности fJ,aNiai)I ai £ Требуется найти оптимальное управление - множества входных последовательностей (слов в алфавите X = ПРИ воздействии которых

г

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

В п.2.2 аналогичная задача решается для периодически нестационарного детерминированного конечного автомата Ade.t общего вида без постпериода

Ди = ЛМ a0,/(TVT),io,r),

со значительно более сложным нечетким ограничением С1 = являющимся нечетким множеством в (Л(т-1) х у(т_1)) х Xс функцией принадлежности /хт{{ai,yi),xs) 6 € [0,1], a,j е А'т-1', yi е У'т-1', х, 6 XНечеткая цель в данном конкретном случае определяется функциями принадлежности HG"(ai) И I^GN(yi), ai £ У1 G и

коэффициентами Хц 6 [0,1] относительной важности Oi перед yi. В результате в п.2.2 разработаны варианты двух методов решения этой задачи и соответствующие два алгоритма, учитывающие более сложный вид автомата, ограничений и нечетких целей, эффективность работы которых проиллюстрирована двумя примерами.

В развитие полученных результатов, в главе 3 работы в качестве управляемой модели исследовал другой тли автомата - периодически нестационарный недетерминированный абстрактный конечный автомат And - (Х(т),Л(т),г0,{В(т)(а:а)},Я(т),«о,Г,п,^), у которого в структурных тактах т = t0 = N, т = t0 + T + tp = М заданы нечеткие цели, определяемые функциями принадлежности ¿¿Giv(aj) и Цдм(щ), а на входные управляющие символы наложены нечеткие ограничения С(т)(жаЮ, г = 1, М. Постановка задачи синтеза оптимального управления такой периодически нестационарной недетерминированной автоматной моделью в этих нечетких условиях, два метода и соответствующие им алгоритмы ее решения, представляющие собой дальнейшее развитие предыдущих, представлены в пн.3.1-3.2 и их эффективность проиллюстрирована примерами.

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

А,» = <*(т), А(т), а0, {Р(Т)(*»)Ь t0,T), (5)

в каждом текущем такте i па входной символ которого наложено нечеткое ограничение с' = CT(t), т = Mo + Т, являющееся нечетким множеством в л(т('_1)) х!(г(1)) с функцией принадлежности /1т(0К-, ■*».)> a,t_, 6 Л^1"1», х„, в X(T(f)) и для фиксированного структурного такта т = N автомата (5) задана нечеткая цель - нечеткое множество Gn в A(JV) с функцией принадлежности nG»(ai), ai *= Задача заключается в на-

хождении оптимального управления - множества входных последовательностей (слов в алфавите X = U^(t))> воздействие которых на автомат (5) последовательно мак-

т

симизировало бы в структурных тактах r(i) = N вероятность достижения заданной цели, т. е. обеспечивало бы его оптимальное поведение. Предложенные в работе способ и алгоритм решения поставленной задачи основаны на матричной интерпретации метода Беллмана-Заде и позволяют эффективно находить оптимальные управляющие последовательности. В заключение п.4.1 рассмотрен пример решения данной задачи.

В н.4.2 исследуется специальная задача получения оценок эффективности достижения нечеткой цели периодически нестационарным стохастическим автоматом общего вида Apr = P{T)(xs,Vi)},t0,T,n,tp }, который находится во взаимо-

действии с некоторой нечеткой средой С, описываемой матрицами CT(i) ограничений на входные символы. В каждом текущем такте t - 1 автомат выдает символ , воздействующий на среду С, которая в свою очередь накладывает нечеткие ограничения C[w (:0 в такте t на входные управляющие символы xSt € X(T(t)) автомата в зависимости от полученного в предыдущем такте выходного символа ylt_r Для фиксированных структурных тактов rN = N и тм = М автомата задаются нечеткие цели GN и GM, определяемые функциями принадлежности HGN{ai>Vi)> е Vi е

и fJ.GM{ai,yi), а, е AiM\ yt € Y(M), которые задаются матрицами hgn, цам. Такое задание нечетких целей является наиболее общим, включая в себя в качестве частных случаев те варианты, когда (a,, yi) не зависит от <ц или от yt. Задача заключается в

нахождении оптимальных входных воздействий в структурных тактах т = 1, t0 + Т + tp, позволяющих оценить сверху и снизу степень достижения заданных целей в тактах tN и tM. Предложенные в работе метод и алгоритм решения такой специальной, достаточно сложной задачи основаны на существенной модификации метода матричных итераций и позволяет находить оптимальные входные воздействия на модель и интервальные оценки их эффективности, что проиллюстрировано на примере.

В 11.4.3 исследован особый случай оптимального управления абстрактным периодически нестационарным стохастическим автоматом при наличии у него определенных «теневых» структурных тактов, в которых управление моделью не может осуществляться внешним «наблюдателем». При этом в каждом текущем такте t на входной символ автомата наложено нечеткое ограничение С' = Ст'(', г = 1, £0 + Т + tp, являющееся нечетким множеством в А{т{,-1]) х с функцией принадлежности fj,T^(ait_uxSt),

G х„, в и заданы нечеткие цели GN и GM соответственно в А^

и Л(м) с функциями принадлежности /iGw(o,), щ е цам(а{), a,i 6 Зада^

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

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

В п.5.1 рассматривается система, взаимосвязанных периодически нестационарных недетерминированных автоматов

Äid = (х!;\а\;\r0", (DirH^)},«о, т,n, t„), v = т^. (б)

функционирующая в нечеткой среде С — (СТ,т = l,t0 + Т + tp), где Ст = = )))<!,1 ссть блочпо-диагональная матрица из д блоков, являющихся

((mi(t-i) х ■•• х m'(t_i)) х п'^-матрицами, = |A[Tw)|, n?(t) = |Xi,T(i))|, нечетких ограничений, устанавливаемых средой на входные символы х" G v =

автоматов системы Л" в такте i, если в предыдущем такте средой была, получена информация о совокупности групп состояний 5,:т((1) = (а} ( ...öj ), о1/ =

= {*„,-,е А«'-2)\ € Л«'-1», Х){х.2») = 1Ь« = 1^!элв-

меиты блоков матриц тем самым представляют собой значения функций принадлежности /4Т(('_|)(-Х«Т(,,) е [0,1] множества управляющих символов х" в зависимости от

совокупности групп состояний air(t_iv х" € А-,'/''", т = 1,£0 + Т + tp, v = l,g.

В каждом текущем такте t среда. С получаст информацию о совокупности групп состояний Я!т(1_,) системы (6) и накладывает нечеткие ограничения на со-

вокупность входных управляющих символов х.,т(1) = (х£ . • ), х" G Xv^, по-

даваемых на систему внешним «наблюдателем» в зависимости от полученной в предыдущем такте Ь - 1 совокупности групп состояний а(т(,_1Г Для каждого из автоматов и = системы (6) задаются нечеткие цели и , определяемые значениями функций принадлежности < е А11 а< е в структурныхтак"

тах ти = N = г0 и тм = М = ¿о + Т + - 1. Трсбуетсянайти оптимальное управление системой (6) в виде совокупности <7 языков V = 1,9, заданных своими регулярными выражениями, позволяющее получить максимальную степень достижения заданных нечетких целей в структурных тактах тц и тм с учетом получения максимальных степеней их достижения на предыдущих этапах. Предложенные в работе способ и алгоритм решения поставленной общей задачи основаны на специальной блочно-диагоналыюй интерпретации разработанного в диссертации метода автоматных итераций и их эффективность проиллюстрирована па примере.

В развитие полученных в 11.4.2 результатов оценки оптимальности поведения периодически нестационарного стохастического автомата при его взаимодействии с нечетко заданной средой в п.5.2 исследуется система таких взаимосвязанных стохастических автоматов

л;г = >, « = м, (7)

где ау € функционирующих в нечеткой среде С = (СТ,т = 1 +Г+£,,), где

С7" = ССГ(е) (х" ))„„ есть блочно-диагоиальпая матрица из д блоков, являющихся х • ■ • х х <(0)-матрицами нечетких ограничений, устанавливаемых сре-

дой на входные символы х"Яь € х1тШ, V = ТТд, автоматов системы V = 1,д, в такте если в предыдущем такте система воздействовала на среду совокупностью выходных символов Уц,.,, = Ыг11_„'- ■ ■ >У1т1,.:,)> г«0 е " = 1>9- Элементы блоков матриц Ст тем самым представляют собой значения функций принадлежности /4т(()'«() € [0,1] множества управляющих символов х" в зависимости от

совокупности 5г,т(1_1)( х;, 6 х1т111>, У1_, е У«'-1», Г = 1, ¡о + Т + (р - 1, у = Тд. При этом в каждом текущем такте £ - 1 система (7) выдает совокупность выходных символов У1,_,, воздействующую на среду С, которая в свою очередь накладывает в такте Ь нечеткие ограничения на совокупность входных управляющих симво-

лов х5( = (х^,... £ х1т(']\ подаваемых на систему внешним «наблюдателем»

в зависимости от полученной в предыдущем < - 1-ом такте совокупности выходных символов у1(_,. Для каждого из автоматов Л^, V = ТТд, системы (7) задаются нечеткие цели - нечеткие множества иС" определяемые функциями принадлежности а? € уГ 6 и Мс-К.уГ), а? € Л[М\ уЦ £ в струк-

турных тактах тм = N и тм = М таких, что тлг = N = = + Т +

Поскольку «наблюдатель» может управлять только всей системой в целом, для каждого структурного такта задаются нормирующие коэффициенты: а) Ат(')(у/1', а"), и = - коэффициенты, учитывающие важность одних состояний перед другими в условиях данной задачи и позволяющие получать функции принадлежности нечетких целей

цст(1)(у\'), зависимыми только от выходного символа у\' для каждого из q автоматов системы; б) Хт<-'Цу1,ь), - коэффициенты, учитывающие важность полученных значений [у]') среди значений функций принадлежности нечетких целей всех автоматов системы (7) и позволяющие получать значения функций принадлежности нечетких целей Мс*«>(г/Г) Для всей системы в независимости от номера автомата и б {1, <у}.

При этом «наблюдателю» неизвестны реально получаемые состояния, в которых находятся автоматы системы в каждом текущем такте 4 > 0 (кроме тактов % и £м), поскольку он и среда воспринимают только реакцию системы автоматов в предыдущем такте. Поэтому задача заключается в нахождении векторов оптимальных входных воздействий в структурных тактах т = 1, + Т + позволяющих оценить сверху и снизу степень достижения заданных целей в тактах £/у Каждая последовательность векторов воздействий при этом строится для достижения максимально возможных оценок степени принадлежности результата, очередной заданной цели при условии получения оптимальных решений на предыдущих этапах. Предложенные в п.5.2 метод и алгоритм решения данной общей задачи основаны на специальной блочпо-диагопальной интерпретации метода, матричных итераций и их эффективность иллюстрируется примером. В заключении подводятся итоги диссертационного исследования. ,

Список публикаций автора

[1] Мосягина Е. Н., Чирков М. К. Анализ воздействий, оптимизирующих функционирование периодически нестационарного детерминированного автомата, в нечетко заданных условиях // Математические модели. Теория и приложения. Вып. 7. -СПб.: ВВМ, 2006. С. 133-140.

[2] Мосягина Е. Н., Чирков М. К. Оптимальные стратегии воздействия на периодически нестационарный стохастический автомат в нечетко заданных условиях// Стохастическая оптимизация в информатике. Вып. 2. - СПб.: Изд-во СПбГУ. 2006. С. 134-146.

[3] Мосягина Е. Н. Об оптимальном управлении периодически нестационарным обобщенным автоматом в нечетких условиях. // Вестник С.-Петерб. ун-та. Сер.1. 2007. Вып. 4. С. 128-132.

[4] Мосягина, Е. Н. Синтез оптимального управления в нечетко заданных условиях для недетерминированных автоматов с периодически меняющейся структурой // Математические модели. Теория и приложения. Вып. 8. -СПб. Изд-во «Золотое сечение», 2007. С. 125-135.

[5] Мосягина Е. Н., Чирков М. К. Оценки оптимальности поведения периодически нестационарного стохастического автомата, в нечеткой среде // Стохастическая оптимизация в информатике. Вып. 3. -СПб.: Изд-во СПбГУ. 2007. С. 37-50.

|6| Мосягина Е. Н., Чирков М. К. Оптимальное управление периодически нестационарным стохастическим автоматом в нечетко заданных условиях при наличии «теней» // Математические модели. Теория и приложения. Вып. 9. -СПб: ВВМ, 2008. С. 100-111.

[7] Мосягина Е. Н., Чирков М. К. Оптимальнее управление системой взаимосвязанных периодически нестационарных стохастических автоматов в нечетко заданных условиях // Стохастическая оптимизация в информатике. Выи. 4. -СПб.: Изд-во СПбГУ. 2008. С. 121-138.

[8] Мосягина Е. Н. Об оптимальном управлении периодически нестационарным недетерминированным автоматом в нечетко заданных условиях // Вестник С.-Петорб. ун-та. Сер.10. 2009. Вып. 4. С. 278-285.

[9] Мосягина Е. Н. Об одном методе анализа слов, оптимально представляемых нестационарными нечеткими автоматными моделями // Математические модели. Теория и приложения. Вып. 10. -СПб.: ВВМ, 2009. С. 111-116.

[10] Моьуадгпа Е. N. Oil estimations of periodically non-stationary stochastic automaton behavior under fuzzy conditions // Proceedings of the 6th St.Petersburg Workshop on Simulation. St.Petersburg, June 28 - July 4, 2009. Vol. II. St.Petersburg, VVM com. Ltd., 2009. P. 857-862.

[И] Мосягина E. H. Синтез последовательных воздействий, обеспечивающих оптимальное поведение, периодически нестационарных недетерминированных автоматов в нечетко заданных условиях // Научно-практическая конференция студентов, аспирантов, молодых ученых и специалистов «Интегрированные модели, мягкие вычисления, вероятностные системы и комплексы программ в искусственном интеллекте» (Коломна, 26-27 мая 2009г.). Научные доклады, Том 2. -М., Физматлит, 2009. С. 189-199.

[12] Мосягина Е. Я. Оптимальное поведение системы периодически нестационарных недетерминированных автоматов в нечеткой среде // Математические модели. Теория и приложения. Вып. 11. -СПб.: ВВМ, 2010. С. 53-71.

[ЩМосягина Е. Н,, Чирков М. К. Оптимальное поведение периодически нестационарных детерминированных и недетерминированных автоматов в нечеткой средс (Теория автоматных моделей).-СПб: ВВМ, 2011. 94 с.

Подписано к печати 22.02.12. Формат60x84 '/ю . Бумага офсетная. Гарнитура Тайме. Печать цифровая. Печ. л. 1,00.

Тираж 100 экз. Заказ 5378._

Отпечатано л Отделе оперативной полиграфии химического факультета СПбГУ 198504, Санет-Пстербург, Старый Петергоф, Университетский пр., 26 Тел.: (812) 428-4043, 4-28-6919

Текст работы Мосягина, Елизавета Николаевна, диссертация по теме Математическое моделирование, численные методы и комплексы программ

61 12-1/1016

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

МОСЯГИНА ЕЛИЗАВЕТА НИКОЛАЕВНА

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

Специальность 05.13.18 — Математическое моделирование, численные методы и комплексы программ

диссертация

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

Научный руководитель — доктор физико-математических наук, профессор Чирков М.К.

Санкт-Петербург 2011

Оглавление

Введение 6

1 Основные определения и постановка задач. 22

1.1 Некоторые понятия теории нечетких множеств..............................22

1.1.1 Нечеткие множества......................................................22

1.1.2 Операции над нечеткими множествами................................23

1.1.3 Нечеткие матрицы и операции над ними................................23

1.2 Исследуемые автоматные модели.....................................25

1.2.1 Общие определения........................................................25

1.2.2 Детерминированные периодически нестационарные автоматы. . . 29

1.2.3 Недетерминированные периодически нестационарные автоматы. . 30

1.2.4 Стохастические периодически нестационарные автоматы............31

1.2.5 Нечеткие нестационарные автоматы...............................32

1.3 Нечетко заданные условия.................................32

1.3.1 Понятие о нечетких ограничениях......................................32

1.3.2 Способы управления моделью............................................33

1.3.3 Нечеткая среда............................................................33

1.3.4 Случай наличия «тени»..................................................34

1.4 Формулировка задачи............................................................35

1.4.1 Понятие нечеткой цели.......................: . 35

1.4.2 Понятие оптимального поведения......................................35

1.4.3 Формулировка общей задачи............................................36

1.4.4 Исследуемые варианты общей задачи..................................37

1.5 Методика решения задач..........................................................38

1.5.1 Начальный этап..........................................................38

1.5.2 Матричный вариант метода Беллмана-Заде..........................38

1.5.3 Алгоритм реализации метода ..........................................41

1.5.4 Метод автоматных итераций............................................42

1.5.5 Алгоритм реализации метода ..........................................46

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

2.1 Синтез воздействий, оптимизирующих поведение детерминированного периодически нестационарного абстрактного автомата..........................48

2.1.1 Формулировка задачи....................................................48

2.1.2 Решение задачи методом матричных итераций . . .................49

2.1.3 Алгоритм решения задачи..............................................50

2.1.4 Пример....................................................................51

2.1.5 Решение задачи методом автоматных итераций ....................56

2.1.6 Пример....................................................................58

2.2 Оптимальное управление детерминированным периодически нестационарным автоматом общего вида..............................................62

2.2.1 Формулировка задачи....................................................62

2.2.2 Решение задачи методом матричных итераций......................63

2.2.3 Алгоритм решения задачи..............................................65

2.2.4 Пример....................................................................67

2.2.5 Решение задачи методом автоматных итераций......................72

2.2.6 Пример....................................................................73

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

3.1 Синтез оптимального управления периодически нестационарным неде-

терминированным автоматом методом матричных итераций................79

3.1.1 Формулировка задачи....................................................79

3.1.2 Метод решения задачи.....................................80

3.1.3 Алгоритм решения задачи..............................................84

3.1.4 Пример....................................................................86

3.2 Решение задачи методом автоматных итераций..............................93

3.2.1 Метод и алгоритм решения задачи....................................93

3.2.2 Пример....................................................................96

4 Оптимальное поведение стохастических периодически нестационарных

автоматов в нечетко заданных условиях. 101

4.1 Оптимальное воздействие на стохастический периодически нестационарный абстрактный автомат........................................................101

4.1.1 Формулировка задачи....................................................102

4.1.2 Метод решения..........................................................102

4.1.3 Пример....................................................................105

4.2 Оценки оптимальности поведения стохастического периодически нестационарного автомата в нечеткой среде........................................................113

4.2.1 Формулировка задачи ..................................................113

4.2.2 Метод решения..........................................................114

4.2.3 Алгоритм решения задачи..............................................118

4.2.4 Пример....................................................................119

4.3 Оптимальное управление стохастическим автоматом при наличии «теней» в нечетко заданных условиях..............................................126

4.3.1 Необходимые дополнительные определения..........................126

4.3.2 Формулировка задачи ..................................................127

4.3.3 Метод решения..........................................................128

4.3.4 Пример....................................................................133

5 Оптимальное поведение систем взаимосвязанных недетерминированных и стохастических периодически нестационарных автоматов в нечет-

кой среде. 144

5.1 Оптимальное управление системой взаимосвязанных недетерминированных периодически нестационарных автоматов в нечеткой среде......144

5.1.1 Исходные данные........................................................144

5.1.2 Постановка задачи........................................................145

5.1.3 Метод автоматных итераций для решения задачи....................146

5.1.4 Пример....................................................................15 О

5.2 Оптимальное управление системой взаимосвязанных стохастических периодически нестационарных автоматов в нечеткой среде....................165

5.2.1 Необходимые определения..............................................165

5.2.2 Формулировка задачи ..................................................166

5.2.3 Метод решения..........................................................167

5.2.4 Пример....................................................................171

Заключение 183

Литература 185

Введение

Актуальность исследования. В течение многих лет различные автоматные модели достаточно успешно используются для описания и изучения на абстрактном уровне структуры и поведения дискретных систем, устройств, процессов и явлений. При этом до недавних пор наиболее подробно и детально были изучены стационарные автоматные модели - стационарные конечные автоматы различного вида, абстрактная структура которых (алфавиты входов, состояний и выходов, начальные и финальные условия, правила функционирования) не меняется во времени(см., например [33, 34, 39, 42, 44, 45, 48]).

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

Одной из таких принципиально новых нестационарных автоматных моделей, уже более 10 лет подробно изучаемой профессором М.К. Чирковым и его учениками, является конечный автомат общего вида с периодически меняющейся структурой (периодически нестационарный автомат) [12-24, 28, 29, 40], все элементы которого сначала меняются от такта к такту в течение заданного конечного предпериода, затем многократно меняются периодически с заданным периодом повторения и, наконец, в определенных

случаях меняются от такта к такту в течение конечного постпериода. При этом помимо традиционных для теории автоматов задач их абстрактного анализа, синтеза и оптимизации, возникает и ряд интересных новых задач, также имеющих прямое отношение к проблемам использования этих периодически нестационарных автоматных моделей в задачах автоматного моделирования. В том числе существенный толчок к расширению проблематики анализа, синтеза, оптимизации, автоматного моделирования языков, оптимального управления автоматами и т. д. дало развитие многими американскими, японскими, российскими и европейскими учеными теории нечетких множеств, теории нечетких моделей и нечеткого управления [2-5, 8-11, 25-27, 30-32, 35-39, 41-51].

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

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

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

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

В основу данной диссертации легли результаты, опубликованные автором E.H. Мо-сягиной в одной монографии [23] и 12 других печатных работах [12-22, 40].

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

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

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

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

2. Применительно к различным нестационарным автоматным моделям разработан матричный вариант метода, предложенного Беллманом-Заде для стационарных абстрактных автоматов.

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

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

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

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

Апробация и публикация результатов. Основные результаты работы докладывались на международной научной конференции «6th St. Petersburg Workshop on Simulation» (Санкт-Петербург, 28 июня-4июля 2009г.) и на всероссийской научно-практической конференции «Интегрированные модели, мягкие вычисления, вероятностные системы и комплексы программ в искусственном интеллекте» (Коломна, 26-27 мая 2009г.),

а также обсуждались на семинаре кафедры статистического моделирования математико-механического факультета СПбГУРабота над диссертацией выполнялась в рамках плановой госбюджетной научной темы НИИММ СПбГУ (номер гос.регистрации: 0120. 0804162) и при частичной поддержке грантов РФФИ 07-01-00355 и 10-01-00310.

По результатам диссертации опубликованы: 1 монография [23] и 12 научных статей, включая 2 статьи [14, 19] в журналах, рекомендованных ВАК, 2 доклада в трудах всероссийской и международной научных конференций [20, 40] и 8 публикаций [12-13, 15-18, 21, 22] в других изданиях.

Структура диссертации. Диссертация состоит из введения, пяти глав, заключения и списка литературы.

Глава 1 посвящена основным определениям, постановке задач и основам методики их решения. В качестве математической модели исследуется нестационарный конечный автомат с периодически меняющейся структурой (периодически нестационарный автомат), в общем случае представляющий собой систему

А = {XV, Л«, УW, г, (х, y)},tQ,T, n,tp ), (1)

где А^ - алфавиты входов, выходов и состояний автомата, to, Т, tp - чис-

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

• для детерминированного автомата Adet ~ начальное состояние ао и однозначные функции {f(T\ip(T) переходов и выходов;

• для недетерминированного автомата And ~ вектор начальных состояний г = = (г0, П.,.. ., rmo_i), Ti G {0, 1}, и совокупность матриц у)} переходов и выходов с элементами D\j\x, у) G {0,1};

• для стохастического автомата Apr ~ вектор распределения вероятностей начальных состояний г и совокупность матриц {Р(т)(ж, у)} вероятностей переходов и выходов

с элементами Р^\х,у) = Рг{а^у\^х)\

• для нечеткого автомата Лf - нечеткий начальный вектор г = (г0,гх,..., гто_ 1), Гг 6 [0,1], и совокупность нечетких матриц {К^Нж, у)} переходов и выходов с элементами е М-

Автомат А функционирует в некоторых нечетко заданных условиях, заключающихся в наложении в каждом текущем такте £ на входные символы автомата хн 6 нечетких ограничений С* = Ст(-1\ которые являются нечеткими множествами со значениями функции принадлежности цт(х31), как правило зависящими от г, а в более сложных случаях и от

Пусть у(^) есть множество альтернатив (в нашем случае это может быть множество состояний А^ или выходных символов У^)) периодически нестационарной автоматной модели Л в структурном такте т = N. Нечеткой целью функционирования автоматной модели А в текущем такте т(£) = N, условимся называть нечеткое подмножество Сы множества У^) с функцией принадлежности цсм : у(^) —> [0,1].

Пусть для периодически нестационарной автоматной модели А задана един