WWW.DISSERS.RU

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

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

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

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

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

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

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

АВТОРЕФЕРАТ

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

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

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

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

Официальные оппоненты: доктор технических наук, профессор Фрадков Александр Львович (Учреждение Российской академии наук Институт проблем машиноведения РАН) доктор физико-математических наук, профессор Демьянович Юрий Каземирович (Санкт-Петербургский государственный университет)

Ведущая организация: Учреждение Российской академии наук Санкт-Петербургский институт информатики и автоматизации РАН

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

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

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

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

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

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

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

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

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

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

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

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

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, r, {F (x, y)}, t0, T, n, tp, (1) () где X( ), Y, A() – алфавиты входов, выходов и состояний автомата, t0, T, tp – число структурных тактов в предпериодической, периодической и постпериодической частях автомата, n – число повторений периодической части, и в зависимости от типа исследуемого автомата (детерминированный, недетерминированный, стохастический, нечеткий) начальное условие r и совокупность условий реализации переходов и вы() ходов {F (x, y)} в структурном такте имеют вид, соответствующий данному типу автомата:

• для детерминированного автомата Adet – начальное состояние a0 и однозначные функции (f(), ( ) переходов и выходов;

• для недетерминированного автомата And – вектор начальных состояний r = = (r0, r1,..., rm ), ri {0, 1}, и совокупность матриц {D( )(x, y)} переходов и выходов 0-() с элементами Dij (x, y) {0, 1};

• для стохастического автомата Apr – вектор распределения вероятностей начальных состояний r и совокупность матриц {P()(x, y)} вероятностей переходов и выходов () с элементами Pij (x, y) = P r(ajy|aix);

• для нечеткого автомата Af – нечеткий начальный вектор r = (r0, r1,..., rm ), 0-ri [0, 1], и совокупность нечетких матриц {R( )(x, y)} переходов и выходов с элемен() тами Rij (x, y) [0, 1].

Автомат A функционирует в некоторых нечетко заданных условиях, заключающихся в наложении в каждом текущем такте t на входные символы автомата xs X( (t)) t нечетких ограничений Ct = C (t), которые являются нечеткими множествами со значениями функции принадлежности µ(xs ), как правило зависящими от , xs, а в более t t сложных случаях и от ai, yl.

t-1 t-(N) Пусть V есть множество альтернатив (в нашем случае это может быть множе(N) ство состояний A(N) или выходных символов Y ) периодически нестационарной автоматной модели A в структурном такте = N. Нечеткой целью функционирования автоматной модели A в текущем такте t, (t) = N, условимся называть нечеткое под(N) (N) множество GN множества V с функцией принадлежности µGN : V [0, 1].

Пусть для периодически нестационарной автоматной модели A задана единственная нечеткая цель в структурном такте = N и пусть w = xs xs... xs есть входная управ1 2 t ляющая последовательность(входное слово), воздействующая на периодически нестационарную автоматную модель и оканчивающаяся в структурном такте (t) = N. Результатом такого воздействия с учетом заданных нечетких ограничений также будет некото(N) рое нечеткое множество GN(w) в множестве альтернатив V такое, что GN(w) GN.

Будем говорить, что входная управляющая последовательность w = xs xs... xs обес1 2 t печивает оптимальное поведение периодически нестационарной автоматной модели A в структурном такте (t) = N, если для любой входной последовательности той же длины w = xg xg... xg, (t) = N, GN(w ) GN и для максимальных элементов векторов 1 2 t µG (w ) и µG (w) выполняется N N max[µG (w )] max[µG (w)], для всех w XN.

N N Исследуемая в работе задача в самом общем случае состоит в следующем. Задана система (иначе, совокупность, коалиция, группировка) из q взаимосвязанных периодически нестационарных конечных автоматных моделей одного типа () ( () A = X, A( ), Y ), r, {F (x, y)}, t0, T, n, tp, = 1, q, (2) которые имеют одинаковые t0, T, n, tp и функционируют одновременно в последовательных тактах t = 0, 1, 2.... При этом на их входные символы накладываются различные нечеткие ограничения C, = 1, q, и в структурных тактах t0 N = N < t0 + T и M = M = t0+T +tp заданы нечеткие цели GN и GM, зависящие от номера автоматной модели, а также коэффициенты, учитывающие важность ее текущих параметров.

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

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

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

µD(xopt,... xopt) = max max(µ1(xs ) ... µN(xs ) µG (f(N)(ai, xs ))), N s1 sN xs1,...xsN-1xsN 1 N N-1 N где µ1(xs ),..., µN(xs ) – вектор-столбцы нечетких ограничений, накладываемые на 1 N входные символы xs в тактах t = 1, 2... N, а µG (f(N)(ai, xs )) – матрица степеней N t N-1 N принадлежности множеству переходов в такте t = N с учетом нечеткой цели GN;

µG (ai ) = max(µN-+1(xs ) µG (ai )), N- N-+N- N-+1 N-+xsN-+где ai = f(N-+1)(ai, xs ), = 1,... N.

N-+1 N- N-+Оптимальное управление при этом находится последовательной максимизацией величин µG (ai ), а xopt - оптимальные входные воздействия определяются как N- N- sN-+функция от ai, = 1,... N, согласно формуле N- xs = t+1(ai ), t = 0, 1, 2... N - 1, t+1 t где t+1 - принятая стратегия, т. е. принятое правило выбора входного воздействия xs в зависимости от ai.

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

Наряду с данным методом в работе предложен второй принципиально новый метод автоматных итераций, который позволяет уменьшить число шагов алгоритма и упростить решение поставленной задачи за счет преобразования исходной автоматной модели к стандартному виду – нечеткому нестационарному автомату Af = X(), A( ), r0, {R()(x)}, q(N).

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

Теорема 1.1. Для заданного нечеткого нестационарного конечного автомата Af множество входных слов Zmax = и существует wopt = xs xs... xs такое, что 1 2 N N выполняется условие f(wopt) = µN = max (r0 R()(xs )q(N)), в том и только max wX(N) =том случае, если r0q(0) > 0, где q(0) определяется рекуррентным соотношением q(N--1) = R(N-)q(N-), = 0, N - 1, R() = R()(x). (3) xX( ) Второй этап – построение регулярного выражения для Zmax. Условимся говорить, что множество входных слов Z X(N) (иначе, язык Z) представлено в автомате And = X(), A( ), r0, {D()(xs)}, q(N), если слово w = xs xs... xs Z в том и только в 1 2 N том случае, когда N nd(w) = r0 D()(xs )q(N) = 1.

=Определим также соотношением U( ) = D()(xs )xs, = 1, N, xs X() автоматные матрицы автомата And. С учетом введенных определений и обозначений оказывается справедливым следующее утверждение.

Теорема 1.2. Если нечеткий автомат Af удовлетворяет условиям теоремы 1.1, т. е. Zmax = и µN > 0, и недетерминированный нестационарный абстрактный max автомат And получен из автомата Af заменой элементов векторов r0, q(N) и матриц {R( )(x)}, которые больше или равны µN, на элементы 1 и остальных элементов max на 0, то множество входных слов Zmax представлено в автомате And, причем его регулярное выражение имеет вид N Zmax = r0 U()q(N), (4) =где под операциями сложения и умножения понимаются операции объединения и произведения в алгебре регулярных языков.

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

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

1. Определим для каждого структурного такта {1... N} нечеткие автомат() ные матрицы U( ) = (Ui() )m,m автомата Af с элементами Ui() = Ri i (xs)xs.

i -1 -1 i s - -1 2. Из построенных нечетких автоматных матриц U(), = 1, N, найдем матрицы () максимальных весов переходов R() = (Ri i )m,m, для чего -1 -а) удалим из матриц U(), = 1, N, все элементы из алфавита X( );

( б) из каждого полученного объединения весов переходов Ri ) (xs), = 1, N, s i -выберем максимальный элемент, а остальные элементы удалим, и в результате получим ( ( элементы матриц максимальных весов переходов Ri ) = max Ri ) (xs), = 1, N.

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

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

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

(N) 2. В финальном векторе q(N) элементы qi µ(N) заменяются на 1, а элементы max (N) qi < µ(N) – на 0, что позволяет получить вектор конечных состояний q(N).

max 3. В начальном векторе r0 = (r0, r1,..., rm ) элементы ri µ(N) заменяются на max 0- 1, а остальные – на 0, и в результате получаем вектор r0.

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

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

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

В п.2.1 главы 2 исследован синтез воздействий, оптимизирующих поведение абстрактного детерминированного автомата без постпериода Adet = X(), A( ), a0, f(), t0, T.

В каждом текущем такте t на входной символ этого автомата наложено нечеткое ограничение Ct = C(t), являющееся нечетким множеством в X() с функцией принадлежности µ(xs) [0, 1], xs X(), и в периодической части автомата для фиксированного структурного такта = N > t0 задана нечеткая цель GN в A(N) с функцией принадлежности µGN (ai), ai A(N). Требуется найти оптимальное управление – множества входных последовательностей (слов в алфавите X = X( )), при воздействии которых на автомат в тактах t таких, что (t) = N, достигалась бы максимально возможная степень принадлежности заданной цели. В результате исследования предложены варианты метода матричных итераций и метода автоматных итераций, а также разработаны соответствующие им алгоритмы решения поставленной задачи, эффективность работы которых проиллюстрирована двумя примерами.

В п.2.2 аналогичная задача решается для периодически нестационарного детерминированного конечного автомата Adet общего вида без постпериода () Adet = X(), A(), Y, a0, f(), (), t0, T, со значительно более сложным нечетким ограничением Ct = C(t), являющимся нечет( -1) ким множеством в (A(-1) Y ) X() с функцией принадлежности µ((ai, yl), xs) ( -1) [0, 1], ai A(-1), yl Y, xs X( ). Нечеткая цель в данном конкретном случае (N) определяется функциями принадлежности µGN (ai) и µGN (yl), ai A(N), yl Y, и коэффициентами il [0, 1] относительной важности ai перед yl. В результате в п.2.разработаны варианты двух методов решения этой задачи и соответствующие два алгоритма, учитывающие более сложный вид автомата, ограничений и нечетких целей, эффективность работы которых проиллюстрирована двумя примерами.

В развитие полученных результатов, в главе 3 работы в качестве управляемой модели исследован другой тип автомата – периодически нестационарный недетерминированный абстрактный конечный автомат And = X( ), A(), r0, {D()(xs)}, q(), t0, T, n, tp, у которого в структурных тактах = t0 = N, = t0 +T +tp = M заданы нечеткие цели, определяемые функциями принадлежности µGN (ai) и µGM (ai), а на входные управляющие символы наложены нечеткие ограничения C()(xs|ai), = 1, M. Постановка задачи синтеза оптимального управления такой периодически нестационарной недетерминированной автоматной моделью в этих нечетких условиях, два метода и соответствующие им алгоритмы ее решения, представляющие собой дальнейшее развитие предыдущих, представлены в пп.3.1-3.2 и их эффективность проиллюстрирована примерами.

В главе 4 решается важная задача обеспечения оптимального поведения периодически нестационарных стохастических автоматов в нечетко заданных условиях. В п.4.синтезируется оптимальное воздействие на периодически нестационарный абстрактный стохастический автомат без постпериода Apr = X(), A(), a0, {P( )(xs)}, t0, T, (5) в каждом текущем такте t на входной символ которого наложено нечеткое ограничение Ct = C(t), = 1, t0 + T, являющееся нечетким множеством в A( (t-1))X( (t)) с функцией принадлежности µ (t)(ai, xs ), ai A((t-1)), xs X((t)) и для фиксированного t-1 t t-1 t структурного такта = N автомата (5) задана нечеткая цель – нечеткое множество GN в A(N) с функцией принадлежности µGN (ai), ai A(N). Задача заключается в нахождении оптимального управления – множества входных последовательностей (слов в алфавите X = X()), воздействие которых на автомат (5) последовательно мак симизировало бы в структурных тактах (t) = N вероятность достижения заданной цели, т. е. обеспечивало бы его оптимальное поведение. Предложенные в работе способ и алгоритм решения поставленной задачи основаны на матричной интерпретации метода Беллмана-Заде и позволяют эффективно находить оптимальные управляющие последовательности. В заключение п.4.1 рассмотрен пример решения данной задачи.

В п.4.2 исследуется специальная задача получения оценок эффективности достижения нечеткой цели периодически нестационарным стохастическим автоматом общего ( ) вида Apr = X(), A( ), Y, ai, {P( )(xs, yl)}, t0, T, n, tp, который находится во взаимодействии с некоторой нечеткой средой C, описываемой матрицами C(t) ограничений на входные символы. В каждом текущем такте t - 1 автомат выдает символ yl, возt-действующий на среду C, которая в свою очередь накладывает нечеткие ограничения C (t) (xs ) в такте t на входные управляющие символы xs X((t)) автомата в завиt t lt-симости от полученного в предыдущем такте выходного символа yl. Для фиксироt-ванных структурных тактов N = N и M = M автомата задаются нечеткие цели GN (N) и GM, определяемые функциями принадлежности µGN (ai, yl), ai A(N), yl Y, (M) и µGM (ai, yl), ai A(M), yl Y, которые задаются матрицами µG, µG. Такое N M задание нечетких целей является наиболее общим, включая в себя в качестве частных случаев те варианты, когда µGN (ai, yl) не зависит от ai или от yl. Задача заключается в нахождении оптимальных входных воздействий в структурных тактах = 1, t0 + T + tp, позволяющих оценить сверху и снизу степень достижения заданных целей в тактах tN и tM. Предложенные в работе метод и алгоритм решения такой специальной, достаточно сложной задачи основаны на существенной модификации метода матричных итераций и позволяет находить оптимальные входные воздействия на модель и интервальные оценки их эффективности, что проиллюстрировано на примере.

В п.4.3 исследован особый случай оптимального управления абстрактным периодически нестационарным стохастическим автоматом при наличии у него определенных теневых структурных тактов, в которых управление моделью не может осуществляться внешним наблюдателем. При этом в каждом текущем такте t на входной символ автомата наложено нечеткое ограничение Ct = C(t), = 1, t0 + T + tp, являющееся нечетким множеством в A( (t-1)) X((t)) с функцией принадлежности µ(t)(ai, xs ), t-1 t ai A((t-1)), xs X((t)), и заданы нечеткие цели GN и GM соответственно в A(N) t-1 t и A(M) с функциями принадлежности µG (ai), ai A(N), µG (ai), ai A(M). ЗадаN M ча заключается в нахождении множества оптимальных последовательностей, максимизирующих вероятности достижения нечетких целей GN и GM и построении, если по условиям это возможно, детерминированного автомата Bdet для управления теневым участком автомата Apr. Предложены методы и алгоритмы решения всех этапов данной задачи и приведен пример их применения.

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

В п.5.1 рассматривается система взаимосвязанных периодически нестационарных недетерминированных автоматов ( A = X ), A(), r0, {D()(x)}, t0, T, n, tp, = 1, q. (6) nd s функционирующая в нечеткой среде C = C, = 1, t0 + T + tp, где C = = (C (t) (x ))q,q есть блочно-диагональная матрица из q блоков, являющихся s i (t-1) (t) ((m1(t-1) ... mq ) n(t))-матрицами, m(t) = |A( (t))|, n(t) = |X( (t))|, нечетких (t-1) ограничений, устанавливаемых средой на входные символы x X( (t)), = 1, q, s (t) автоматов системы A в такте t, если в предыдущем такте средой была получена информация о совокупности групп состояний ai = (a1... aq ), a = i(t-1) i (t-1) i(t-1) (t-1) ((t-1)) = {ai |ai A((t-2)), ai A( (t-1)), Di i(t-1)(xs ) = 1}, = 1, q. Эле (t-1) (t-2) (t-1) (t-1) (t-2) менты блоков матриц тем самым представляют собой значения функций принадлежности µ (t) (x ) [0, 1] множества управляющих символов x в зависимости от s i (t-1) (t) s (t) совокупности групп состояний ai, x X((t)), = 1, t0 + T + tp, = 1, q.

s (t) (t-1) В каждом текущем такте t среда C получает информацию о совокупности групп состояний ai системы (6) и накладывает нечеткие ограничения C(t) (x ) на со(t-1) i(t-1) s(t) ((t)) вокупность входных управляющих символов xs = (x1... xq ), x X, поs (t) s (t) s (t) (t) даваемых на систему внешним наблюдателем в зависимости от полученной в предыдущем такте t - 1 совокупности групп состояний ai. Для каждого из автоматов (t-1) A, = 1, q, системы (6) задаются нечеткие цели GN и GM, определяемые значениями nd функций принадлежности µG (a), a A(N), и µG (a), a A(M) в структурных такN M i i i i тах N = N = t0 и M = M = t0 + T + tp - 1. Требуется найти оптимальное управление системой (6) в виде совокупности q языков {Z}, = 1, q, заданных своими регулярными выражениями, позволяющее получить максимальную степень достижения заданных нечетких целей в структурных тактах N и M с учетом получения максимальных степеней их достижения на предыдущих этапах. Предложенные в работе способ и алгоритм решения поставленной общей задачи основаны на специальной блочно-диагональной интерпретации разработанного в диссертации метода автоматных итераций и их эффективность проиллюстрирована на примере.

В развитие полученных в п.4.2 результатов оценки оптимальности поведения периодически нестационарного стохастического автомата при его взаимодействии с нечетко заданной средой в п.5.2 исследуется система таких взаимосвязанных стохастических автоматов () A = X, A(), Y(), a, {P()(x, yl )}, t0, T, n, tp, = 1, q, (7) pr i0 s где a A(0), функционирующих в нечеткой среде C = C, = 1, t0 + T + tp, где i0 C = (C(t) (x ))q,q есть блочно-диагональная матрица из q блоков, являющихся s l (t-1) (t) q ((k(t-1) ... k(t-1)) n(t))-матрицами нечетких ограничений, устанавливаемых сре ( дой на входные символы x X (t)), = 1, q, автоматов системы A, = 1, q, в такте st pv t, если в предыдущем такте система воздействовала на среду совокупностью выq ( 1 ходных символов yl = (yl,..., yl ), где yl Y (t-1)), = 1, q. Элементы (t-1) (t-1) (t-1) (t-1) блоков матриц C тем самым представляют собой значения функций принадлежности µ((t))(x ) [0, 1] множества управляющих символов x в зависимости от lt-1 st st ((t-1)) совокупности yl, x X((t)), yl Y, = 1, t0 + T + tp - 1, = 1, q.

st (t-1) t-При этом в каждом текущем такте t - 1 система (7) выдает совокупность выходных символов yl, воздействующую на среду C, которая в свою очередь накладывает в t-такте t нечеткие ограничения C (t) (x ) на совокупность входных управляющих симвоlt-1 st лов xs = (x1,..., xq ), x X( (t)), подаваемых на систему внешним наблюдателем t st st st в зависимости от полученной в предыдущем t - 1-ом такте совокупности выходных символов yl. Для каждого из автоматов A, = 1, q, системы (7) задаются нечетt-1 pv кие цели – нечеткие множества GN и GM, определяемые функциями принадлежности (N) µG (a, yl ), a A(N), yl Y, и µG (a, yl ), a A(M), yl Y(M) в струкN M i i i i турных тактах N = N и M = M таких, что N = N = t0, M = M = t0 + T + tp.

Поскольку наблюдатель может управлять только всей системой в целом, для каждо го структурного такта задаются нормирующие коэффициенты: а) (t)(yl, a), = 1, q i – коэффициенты, учитывающие важность одних состояний перед другими в условиях данной задачи и позволяющие получать функции принадлежности нечетких целей µG (yl ), зависимыми только от выходного символа yl для каждого из q автоматов (t) системы; б) (t)(yl, ), – коэффициенты, учитывающие важность полученных значений µG (yl ) среди значений функций принадлежности нечетких целей всех автоматов си (t) стемы (7) и позволяющие получать значения функций принадлежности нечетких целей µG (yl ) для всей системы в независимости от номера автомата {1, q}.

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

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

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

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

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

ун-та. Сер.1. 2007. Вып. 4. С. 128-132.

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

C. 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. C. 111-116.

[10] 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.

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

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

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




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

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