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

• Мосягина, Елизавета Николаевна
• кандидат физико-математических наук
• 2011

Оглавление диссертации кандидат физико-математических наук Мосягина, Елизавета Николаевна

Оглавление

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1.4 Пример

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

2.1.6 Пример

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

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

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

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

2.2.4 Пример

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

2.2.6 Пример

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

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

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

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

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

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

3.1.4 Пример

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

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

3.2.2 Пример

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

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

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

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

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

4.1.3 Пример

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

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

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

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

4.2.4 Пример

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

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

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

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

4.3.4 Пример

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

кой среде

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

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

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

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

5.1.4 Пример

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

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

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

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

5.2.4 Пример

Заключение

Литература

Введение диссертации (часть автореферата) на тему «Оптимальное поведение периодически нестационарных автоматных моделей в нечетко заданных условиях»

Введение

Актуальность исследования. В течение многих лет различные автоматные модели достаточно успешно используются для описания и изучения на абстрактном уровне структуры и поведения дискретных систем, устройств, процессов и явлений. При этом до недавних пор наиболее подробно и детально были изучены стационарные автоматные модели - стационарные конечные автоматы различного вида, абстрактная структура которых (алфавиты входов, состояний и выходов, начальные и финальные условия, правила функционирования) не меняется во времени(см., например [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].

Пусть для периодически нестационарной автоматной модели А задана единственная нечеткая цель в структурном такте т = N и пусть ио = х31 х32... х3г есть входная управляющая последовательнос,ть(входное слово), воздействующая на периодически нестационарную автоматную модель и оканчивающаяся в структурном такте т(£) = N. Результатом такого воздействия с учетом заданных нечетких ограничений также будет некоторое нечеткое множество См(ги) в множестве альтернатив у(^) такое, что бг(ги) С См. Будем говорить, что входная управляющая последовательность ии = хб1х32 ... х3г обеспечивает оптимальное поведение периодически нестационарной автоматной модели А в структурном такте т{€) = N, если для любой входной последовательности той же длины из' = х31хд2 ... х91, т(í) = Ы, Сы{т') С и для максимальных элементов векторов /¿¿лг(ги') и /л^ы^ш) выполняется

тах[/л^м(и}')] ^ тах[/^^ («;)], для всех из' е Xм.

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

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

А" = (Х<Г\ Уг., у)}, ¿0, Т, п, гр ), v = (2)

которые имеют одинаковые to, Т, п, ¿р и функционируют одновременно в последователь-' ных тактах ¿ = 0,1,2.... При этом на их входные символы накладываются различные нечеткие ограничения v = 1, д, и в структурных тактах ¿о ^ Тлг = < ¿о + Т и тм = М = ¿озаданы нечеткие цели и зависящие от номера V автоматной модели, а также коэффициенты, учитывающие важность ее текущих параметров.

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

На начальном этапе решения задачи исследуемый периодически нестационарный конечный автомат (система таких взаимосвязанных конечных автоматов) представляется в виде последовательности трех нестационарных автоматов (систем), для чего структурные такты исходного автомата (каждого из автоматов системы) разбиваются в соответствии со структурными тактами ¿о ^ т = N < ¿о + Т, т = М = ¿р, в которых заданы нечеткие цели Сы и См, и структурным тактом N ^ т — К < < N-\-Т — 1, в котором начинается постпериод £р, на структурные такты г = 0,1,..., N, т = ./V, N + 1,..., N + Т — 1, N к т = /V,..., К,. .., М. Таким образом каждый из трех полученных автоматов (систем автоматов) будет представлять собой нестационарный конечный автомат (систему нестационарных конечных автоматов), для которого необходимо найти оптимальное управление.

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

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

■ = тах тах(/л1(хЯ1) П ... П 1Лы(х8м) П ^(/^(^аг-!.^))).

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

входные символы хн в тактах £ = 1, 2 ... N, а х3лг)) - матрица степеней

принадлежности множеству переходов в такте £ = N с учетом нечеткой цели

где = V = 1,... N.

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

= тгг+1(а^), Ь = 0,1, 2 ... N - 1,

где 7г4_|_1 - принятая «стратегия», т. е. принятое правило выбора входного воздействия в зависимости от а^.

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

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

При этом дальнейшее решение задачи разделено на два этапа: сначала находится максимально возможная степень достижения нечеткой цели См = q('ЛГ^. затем определя-

ется множество входных слов Zmax , обеспечивающих такое достижение нечеткой

цели. Выполнение первого этапа основано на справедливости следующего утверждения.

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

(N) N

выполняется условие Фf(wopt) = fj,max = шах (г0 П в том и только

™ex(N) T=i

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

q(iv-,-i) = R(iv-,)q(iv-,)) „ = 0,^-1, rW= (J RW(x). (3)

хехм

Второй этап - построение регулярного выражения для Zmax. Условимся говорить, что множество входных слов Z С Х^ (иначе, язык Z) представлено в автомате And = го, {D^(xs)}, q^), если слово w = x31xS2... xSN £ Z в том и только в

том случае, когда

n

Т—1

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

fj(r)= (J r = T7F,

iSrexM

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

Теорема 1.2. Если нечеткий автомат Af удовлетворяет условиям теоремы 1.1, т. е. Zmax ф Л и Цтах > 0, и недетерминированный нестационарный абстрактный автомат Апа получен из автомата Af заменой элементов векторов Го, q^ и матриц {R(T)(x)}; которые больше или равны ¡Лтах, на элементы «1» и остальных элементов на «0», то множество входных слов Zmax представлено в автомате And, причем его регулярное выражение имеет вид

n

^ma,=?0nU(T)q(JV), (4)

т=1

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

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

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

1. Определим для каждого структурного такта т £ {1... ТУ"} «нечеткие» автоматные матрицы и^ = ^т)тг_1,тт- автомата Л/ с элементами =

2. Из построенных «нечетких» автоматных матриц и^, г = найдем матрицы максимальных весов переходов = Для чего

а) удалим из матриц им, т = 1, N, все элементы из алфавита Х^;

б) из каждого полученного объединения весов переходов -^¿Г^гД3'«); т = выберем максимальный элемент, а остальные элементы удалим, и в результате получим элементы матриц максимальных весов переходов — тахй|Т' ; (х3), т = 1,-Л/".

т 1 т Хв т т

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

Определение множества входных слов ,£тах:

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

2. В финальном векторе q(iV•) элементы ^ /х&Йс заменяются на «1», а элементы < ~ на «О», что позволяет получить вектор конечных состояний с^).

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

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

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

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

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

В п. 2.1 главы 2 исследован синтез воздействий, оптимизирующих поведение абстрактного детерминированного автомата без постпериода Лаа = (Х^т\ ао, /(-'г-), ¿о, Т). В каждом текущем такте £ на входной символ этого автомата наложено нечеткое ограничение С4 = Ст(-Ь\ являющееся нечетким множеством в с функцией принадлежности цт(ха) € [0,1], х3 € и в периодической части автомата для фиксированного структурного такта т = N > ^ задана нечеткая цель Сг в

с функцией принадлежности а, е Требуется найти оптимальное управление - множества входных последовательностей (слов в алфавите X = УХ^), при воздействии которых

г

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

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

Лш =

со значительно более сложным нечетким ограничением С4 = Ст^>, являющимся нечетким множеством в х х Х^ с функцией принадлежности у{), х3) 6 € [0,1], щ 6 у\ € х3 € Х^. Нечеткая цель в данном конкретном случае определяется функциями принадлежности цам^) и Цсы{У1); аг £ А^. у1 € и коэффициентами \ц £ [0,1] относительной важности а$ перед у\. В результате в п.2.2 разработаны варианты двух методов решения этой задачи и соответствующие два алгоритма, учитывающие более сложный вид автомата, ограничений и нечетких целей, эффективность работы которых проиллюстрирована двумя примерами.

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

ванный абстрактный конечный автомат And = (Х^т\ А^т\ го, {D'r'(xs)},q (T\to,T,n,tp), у которого в структурных тактах т = to = N, т = to + T + tp = М заданы нечеткие цели, определяемые функциями принадлежности HGN(ai) и ^GM(ai), а на входные управляющие символы наложены нечеткие ограничения С^(х3\щ), т = 1, М. Постановка задачи синтеза оптимального управления такой периодически нестационарной недетерминированной автоматной моделью в этих нечетких условиях, два метода и соответствующие им алгоритмы ее решения, представляющие собой дальнейшее развитие предыдущих, представлены в пи. 3.1-3.2 и их эффективность проиллюстрирована примерами.

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

Арг = ¿(т),а0,{Р(т)(^)Ыо,Т}, (5)

в каждом текущем такте t на входной символ которого наложено нечеткое ограничение С4 = т = 1, ¿о + Т, являющееся нечетким множеством в хХ^^ с функци-

ей принадлежности ¡iT(t^ait_1,xSt), ciit_l е л«*-1», xSt G и для фиксированного

структурного такта т = N автомата (5) задана нечеткая цель - нечеткое множество GN в AW с функцией принадлежности /iGN(a;), щ G Задача заключается в на-

хождении оптимального управления — множества входных последовательностей (слов в алфавите X = [JX^1"'), воздействие которых на автомат (5) последовательно мак-

т

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

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

действии с некоторой нечеткой средой С, описываемой матрицами Ст^ ограничений

на входные символы. В каждом текущем такте t — 1 автомат выдает символ yit_i: воздействующий на среду С, которая в свою очередь накладывает нечеткие ограничения Cj^(xSt) в такте t на входные управляющие символы xSt £ Х^^ автомата в зависимости от полученного в предыдущем такте выходного символа yit_1. Для фиксированных структурных тактов tjv = N и тм = М автомата задаются нечеткие цели GN и GM, определяемые функциями принадлежности /Jiqn (ßj, yi), £ yi £

и {¿GM(ai>yi)> аг ^ А^м\ yi £ ум, которые задаются матрицами ßGN, цсм. Такое задание нечетких целей является наиболее общим, включая в себя в качестве частных случаев те варианты, когда ¡iGiv(a,, yi) не зависит от щ или от yi. Задача заключается в нахождении оптимальных входных воздействий в структурных тактах т = 1, i0 + Т + tp, позволяющих оценить сверху и снизу степень достижения заданных целей в тактах ¿дг и ¿м- Предложенные в работе метод и алгоритм решения такой специальной, достаточно сложной задачи основаны на существенной модификации метода матричных итераций и позволяет находить оптимальные входные воздействия на модель и интервальные оценки их эффективности, что проиллюстрировано на примере.

В п. 4.3 исследован особый случай оптимального управления абстрактным периодически нестационарным стохастическим автоматом при наличии у него определенных «теневых» структурных тактов, в которых управление моделью не может осуществляться внешним «наблюдателем». При этом в каждом текущем такте t на входной символ автомата наложено нечеткое ограничение С4 = т = 1, ¿о + Т + tp, являющееся нечетким множеством в Л^4-1^ х X^^ с функцией принадлежности xSt), CLj. , £ X4t и заданы нечеткие цели GN и GM соответственно в AW и AW с функциями принадлежности /xGjv(aj), а» 6 A^N\ /л<зм(сц), сц G А^м\ Задача заключается в нахождении множества оптимальных последовательностей, максимизирующих вероятности достижения нечетких целей GN и GM и построении, если по условиям это возможно, детерминированного автомата Bdet для управления «теневым» участком автомата Арг. Предложены методы и алгоритмы решения всех этапов данной задачи и приведен пример их применения.

В главе 5 исследуется основная общая задача обеспечения оптимального поведе-

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

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

л1, = ), v = м, (6)

функционирующая в нечеткой среде С = (СТ,т = 1, ¿о + Т + Ьр), где Ст = = 1) (хв (4)))?.9 есть блочно-диагональная матрица из д блоков, являю-

щихся ((тп^_1} х ... х х п^(4))-матрицами, тьт{€) = |Л[тМ)|, =

нечетких ограничении, устанавливаемых средой на входные символы х" £ Ху ", V = 1,<7, автоматов системы в такте если в предыдущем такте средой была получена информация о совокупности групп состояний = (й\т{±_1) ■ • •

а» - 1п \п- а л(т^-2)) А(т(1-1)) п(т(1-1)) ( ч_п _Т--

Элементы блоков матриц тем самым представляют собой значения функций принадлежности (4)) € [0,1] множества управляющих символов в зависимости от совокупности групп состояний Щг((_1), ж" £ т = 1, ¿о + Т + г; = 1, д.

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

вокупность входных управляющих символов х3т(1) = (х] ■ ■ -х^ ), е ХуТ^\ по-

даваемых на систему внешним «наблюдателем» в зависимости от полученной в предыдущем такте Ь — 1 совокупности групп состояний а»т(4_1}. Для каждого из автоматов Апл, V = 1, д, системы (6) задаются нечеткие цели и С^1, определяемые значениями функций принадлежности цсм(а\), ¡Е и /¿см(а"), а^ е в структурных тактах Тм = N = £о и Тм — М = ¿о + Г + £р — 1. Требуется найти оптимальное управление системой (6) в виде совокупности д языков {.£„}, у = 1, д, заданных своими регулярными выражениями, позволяющее получить максимальную степень достижения заданных нечетких целей в структурных тактах гдг и 7>/ с учетом получения максимальных степеней их достижения на предыдущих этапах. Предложенные в работе способ и алгоритм решения поставленной общей задачи основаны на специальной блочно-диагональной

интерпретации разработанного в диссертации метода автоматных итераций и их эффективность проиллюстрирована на примере.

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

где 6 функционирующих в нечеткой среде С = (СТ,т = 1, + 71 + где Ст = (С^ 0е" (4)))д,д есть блочно-диагональная матрица из д блоков, являющихся х • • • х Кц-1)) х пт(г))-матрицами нечетких ограничений, устанавливаемых средой на входные символы х^ £ у = 1, д, автоматов системы Архп V = 1, д, в такте если в предыдущем такте система воздействовала на среду совокупностью выходных символов У1т(4_1} = (%1Т(4_1), • ■ • ,2/^-1))' где е ^ = 1.9- Элементы блоков матриц Ст тем самым представляют собой значения функций принадлежности ¡1 £ [0,1] множества управляющих символов в зависимости от совокупности у1т(4_1}, хЪ е е У^-1», г = 1,г0 + Т + гр-1, V = М. При этом в каждом текущем такте t — 1 система (7) выдает совокупность выходных символов У1<_1, воздействующую на среду С, которая в свою очередь накладывает в такте £ нечеткие ограничения (х^) на совокупность входных управляющих символов х8( = (х^,..., ), х^ € подаваемых на систему внешним «наблюдателем» в зависимости от полученной в предыдущем £ — 1-ом такте совокупности выходных символов У14_г. Для каждого из автоматов Ару, V = 1, д. системы (7) задаются нечеткие цели - нечеткие множества С^ и определяемые функциями принадлежности < е у? е и цс*г(а?,уг), < е а[м\ у- е у„(м) в структурных тактах т^ = N и тм = М таких, что Тдт = X = ¿о, Тм = М = ¿о + Т + £р. Поскольку «наблюдатель» может управлять только всей системой в целом, для каждого структурного такта задаются нормирующие коэффициенты: а) А1-^'^, а"), v = 1,д - коэффициенты, учитывающие важность одних состояний перед другими в условиях данной задачи и позволяющие получать функции принадлежности нечетких целей

/¿ст(о (у"), зависимыми только от выходного символа у^ для каждого из д автоматов системы; б) Лт^(уиу), - коэффициенты, учитывающие важность полученных значений цпт(4) (у?) среди значений функций принадлежности нечетких целей всех автоматов системы (7) и позволяющие получать значения функций принадлежности нечетких целей /¿ст(о (у?) для всей системы в независимости от номера автомата у € {1, д}.

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

В заключении подводятся итоги диссертационного исследования.

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

Заключение

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

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Мосягина, Елизавета Николаевна, 2011 год

Литература

[1] Беллман Р. Динамическое программирование. -М.: ИЛ. 1960.

[2] Беллман Р., Заде Л. Принятие решений в расплывчатых условиях// Вопросы анализа и процедуры принятия решений. -М.: Мир. 1976. С. 172-215.

[3] Борисов А. Н., Алексеев А. В., Меркурьева Г. В. и др. Обработка нечеткой информации в системах принятия решений. -М.: Радио и связь, 1989. 304 с.

[4] Борисов А. Н., Крумберг O.A., Федоров И. П. Принятие решений на основе нечетких моделей. -Рига: Зинатне, 1990.

[5] Борисов В. В., Круглое В. В, Федулов А. С. Нечеткие модели и сети. М.: Горячая линия-Телеком, 2007. 284 с.

[6] Блюмин С. Л., Шуйкова И. А. Введение в математические методы принятия решений. -Липецк: Липецкий государственный педагогический институт, 1999. 100 с.

[7] Вагнер Г. Основы исследования операций, t.t.I-III. -М.: Мир. 1972-1973.

[8] Дюбуа Д., Прад А. Теория возможностей. Приложения к представлению знаний в информатике. -М.:Радио и связь, 1990.

[9] Заде Л. А Основы нового подхода к анализу сложных систем и процессов принятия решений // Математика сегодня. -М.: «Знание», 1974. С. 5-49.

[10] Кофман А. Введение в теорию нечетких множеств. -М.: Радио и связь, 1982. 432 с.

[11] Леоненков А. Нечеткое моделирование в среде MATLAB и fuzzy TECH. -СПб.: БХВ-Петербург, 2003. 719 с.

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

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

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

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

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

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

[18] Мосягина Е. Л., Чирков М. К. Оптимальное управление системой взаимосвязанных периодически нестационарных стохастических автоматов в нечетко заданных усло-

виях // Стохастическая оптимизация в информатике. Вып.4. СПб.: Изд-во СПбГУ. 2008. С. 121-138.

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

[20] Мосягина Е. Н. Синтез последовательных воздействий, обеспечивающих оптимальное поведение периодически нестационарных недетерминированных автоматов в нечетко заданных условиях // Интегрированные модели, мягкие вычисления, вероятностные системы и комплексы программ в искусственном интеллекте. М., Физ-матлит, 2009. С. 189-199.

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

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

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

[24] Недзвецкая К. А., Пономарева А. Ю. О построении приведенных и минимальных форм нестационарных недетерминированных автоматов с периодически меняющейся структурой // Математические модели. Теория и приложения. Вып. 7. -СПб.: ВВМ, 2006. С. 110-132.

[25] Нечеткие множества и теория возможностей. Последние достижения / Под ред. Р. Р. Ягера. М., Радио и связь, 1986. 408 с.

[26] Нечеткие множества в системах управления и искусственного интеллекта / Под ред. Д. А. Поспелова. -М.:Наука. Гл. ред. физ.-мат. лит., 1986. 312 с.

[27] Орловский С. А. Проблемы принятия решений при нечеткой исходной информации. -М.: Наука, 1981. 206 с.

[28] Пономарева А. Ю., Чирков М. К. Оптимизация обобщенных автоматов с периодически меняющейся структурой. -СПб.: Изд-во НИИХ СПбГУ. 2000. 92 с.

[29] Пономарева А. Ю. Оптимизация абстрактной структуры периодически нестационарного стохастического автомата // Вестник молодых ученых. 2'2003. Серия Прикладная математика и механика, Г2003. -СПб.: С. 77-91.

[30] Прикладные нечеткие системы / Под ред. Т. Тэрано, К. Асаи, М. Сугено. -М.:Мир, 1993. 368 с.

[31] Саати Т. Принятие решений. Метод анализа иерархий. -М.:Радио и связь, 1993. 320 с.

[32] Силов В. Б. Принятие стратегических решений в нечеткой обстановке. М.:ИНПРО-РЕС, 1995.

[33] Чирков М. К. Основы общей теории конечных автоматов. -Л.:Изд-во Ленингр. унта, 1975. 280 с.

[34] Чирков М. К., Пономарева А. Ю. Стационарные детерминированные и вероятностные автоматы (Теория автоматных моделей).-СПб.: Изд-во СПбГУ, 2008. 248 с.

[35] Asai К., Kitajima S. Optimizing Control Using Fuzzy Autómata // Automática, Vol. 8, 1972. Р. 101-104.

[36] Asai К., Kitajima S. A Method for Optimizing Control of Multimodal Systems using Fuzzy Autómata // Information Sciences, 3, 1971. P. 343-353.

[37] Chang S. S. L. Fuzzy Dynamic Programming and the Decisión Making Process // Proc. 3d Princeton Conf. of Information Sciences and Systems, 1969. P. 200-203.

[38] Fuzzy Sets and their Applications to Cognitive and Decision Theory / Ed. L. A. Zadeh et. al. - N. Y.: Academic Press. 1975. 496 p.

[39] Kandel A., Lee S. C. Fuzzy Switching and Automata: Theory and Applications. - N. Y.; London: Russak & Company. 1979. 303 p.

[40] Mosyagina E. N. On 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.

[41] Pedrycz W. Fuzzy Control and Fuzzy Systems. - N. Y.: John Wiley and Sons, 1993.

[42] Santos E. S. Fuzzy automata and languages. // US-Japan Seminar on Fuzzy Sets and their Applications, Berkeley, Calif., 1974.

[43] Tanaka H., Okuda T., Asai K. Fuzzy mathematical programming. Trans. SICE 9, 1973. P. 109-115.

[44] Tanaka K., Toyoda J., Mizumoto M., Tsuji H. Fuzzy automata theory and its application to automatic controls //J. JAACE 1970. P. 541-550.

[45] Thomason M. G. Finite Fuzzy Automata, Regular Fuzzy Languages, and Pattern Recognition. Dept. of Electrical Engineering, Duke University, Durham, N. C., 1974.

[46] Tsuji H., Mizumoto M., Toyoda J., Tanaka K. Linear fuzzy automation. Trans. IECE Japan, 56-A, 1973. P. 256-257.

[47] Vasantha Kandasamy W.B., Smarandache F., Ilanthenral K. Elementary Fuzzy Matrix Theory and Fuzzy Models for Social Scientists. - Los Angeles: Automaton, 2007. 352 p.

[48] Wechler W. The Concept of Fuzziness in the Theory of Automata. Technical University of Dresden, German Democratic Republic, 1975.

[49] Zadeh L. A. Fuzzy Sets // Inform, a. Control, 8, 1965. P. 338-353.

[50] Zadeh L. A. Fuzzy Sets as a Basis for a Theory of Possibility // Fuzzy Sets and Systems, 1, 1978. P. 3-28.

[51] Zimmermann H. J. Descricription and optimization of fuzzy systems // Int. J. Gen. Syst. 2, 1975. P. 209-215.