Введение к работе
Актуальность темы.В течение многих лет различные автоматные модели достаточно успешно используются для описания и изучения на абстрактном уровне структуры и поведения дискретных систем, устройств, процессов и явлений. При этом до недавних пор наиболее подробно и детально были изучены стационарные автоматные модели, абстрактная структура которых (алфавиты входов, состояний и выходов, начальные и финальные условия, правила функционирования) не меняется во времени. Однако, дальнейшее существенное расширение класса дискретных систем, устройств, процессов и явлений, описываемых и изучаемых с помощью автоматного моделирования, уже невозможно без перехода к исследованию нестационарных конечно-автоматных моделей, абстрактная структура которых меняется во времени. При этом, однако, концепция конечности автоматной модели подразумевает и тот факт, что процесс изменения ее абстрактной структуры целесообразно ограничить конечным числом вариантов этого изменения и допускать конечное их задание.
Одной из таких принципиально новых нестационарных автоматных моделей является конечный автомат общего вида с периодически меняющейся структурой (периодически нестационарный автомат), все элементы которого сначала меняются от такта к такту в течение заданного конечного предпериода, затем многократно меняются периодически с заданным периодом повторения и, наконец, в определенных случаях меняются от такта к такту в течение конечного постпериода. При этом помимо традиционных для теории автоматов задач их абстрактного анализа, синтеза и оптимизации, возникает и ряд интересных новых задач, также имеющих прямое отношение к проблемам использования этих периодически нестационарных автоматных моделей в задачах автоматного моделирования. В том числе существенный толчок к расширению проблематики анализа, синтеза, оптимизации, автоматного моделирования языков, оптимального управления автоматами и т. д. дало развитие многими американскими, японскими, российскими и европейскими учеными теории нечетких множеств, теории нечетких моделей и нечеткого управления.
В частности в работе Р. Беллмана и Л. Заде «Принятие решений в расплывчатых условиях» впервые были сформулированы проблемы, связанные с принятием многошаговых решений по оптимальному управлению стационарными абстрактными автоматами для максимального достижения ими при заданном конечном числе тактов одной нечеткой цели при достаточно простых нечетких ограничениях на управляющие воздействия, и предложен способ решения сформулированных задач, основанный на методе обратных итераций динамического программирования. Естественно, что в связи с развитием теории нестационарных автоматных моделей различного типа, имеющих более сложную нестационарную структуру, стало весьма актуальным изучение поведения таких моделей в более сложных нечетко заданных условиях.
Развитию подобной проблематики и посвящена данная диссертация, в которой исследуются методы и алгоритмы решения значительно более сложных задач синтеза множества входных управляющих воздействий, обеспечивающих оптимальное поведение периодически нестационарной автоматной модели, заключающееся в последовательном максимально возможном достижении конечного числа заданных нечетких целей при достаточно сложных внешних нечетких условиях, в том числе разработка методики синтеза комплекса оптимальных управляющих воздействий на целую систему взаимосвязанных периодически нестационарных автоматных моделей, в которой при определении всего комплекса нечетких ограничений и нечетко заданных целей учитываются результаты функционирования всей системы в целом.
Цель работы. Целью данной работы является комплексное исследование проблем синтеза оптимального управления нестационарными детерминированными, недетерминированными и стохастическими автоматными моделями с периодически меняющийся структурой, обеспечивающего их оптимальное поведение при наложении на входные управляющие символы различных нечетких ограничений с учетом взаимодействия моделей, если они объединены в систему.
Общая методика работы. В работе используются методы теории детерминированных, недетерминированных, стохастических и нечетких нестационарных автоматных моделей, теории нечетких множеств и нечетких отношений, теории вероятностей и статистического моделирования, алгебраической теории матриц и теории принятия решений при нечеткой исходной информации.
Результаты выносимые на защиту. В соответствии с поставленной в диссертации общей задачей обеспечения оптимального поведения системы взаимодействующих периодически нестационарных автоматных моделей в нечетко заданных условиях получены следующие основные результаты:
-
Предложена общая методика решения подобных задач, заключающаяся в разбиении заданной периодически нестационарной автоматной модели (или системы таких моделей) на последовательность нестационарных автоматных моделей (систем таких моделей) в зависимости от последовательности заданных нечетких целей и применении к ним одного из предложенных в работе методов и алгоритмов синтеза оптимального управления.
-
Применительно к различным нестационарным автоматным моделям разработан матричный вариант метода, предложенного Беллманом-Заде для стационарных абстрактных автоматов.
-
Теоретически обоснован и разработан специальный метод автоматных итераций и реализующие его алгоритмы, позволяющие эффективно решить задачу синтеза оптимального управления для детерминированных и недетерминированных нестационарных автоматных моделей рассматриваемого типа.
-
На основе предложенных методов и алгоритмов разработаны их модификации, позволяющие решать задачу обеспечения оптимального поведения периодически нестационарных автоматных моделей конкретного вида, в зависимости от различных нечетко заданных условий и нечетких целей: а) периодически нестационарных детерминированных автоматов; б) периодически нестационарных недетерминированных автоматов; в) периодически нестационарных стохастических автоматов; г) периодически нестационарных стохастических автоматов в условиях наличия «тени»; д) систем взаимодействующих периодически нестационарных стохастических и недетерминированных автоматов.
В целом разработанная методика решения этих задач при различных способах задания нечетких ограничений и нечетких целей предоставляет возможность формулировки различных конкретных вариантов общей задачи и выбора подходящих методов их решения.
Достоверность результатов. Все полученные в диссертации теоретические результаты математически строго доказаны. Разработанные в диссертации алгоритмы теоретически обоснованы и их эффективность подтверждена решением конкретных модельных задач.
Научная новизна. Все основные результаты, представленные в диссертации, являются новыми.
Теоретическая и практическая ценность.Разработанные в диссертации математические методы и алгоритмы синтеза оптимального управления периодически нестационарными детерминированными, недетерминированными и стохастическими автоматными моделями, обеспечивающего их оптимальное поведение при различных способах задания нечетких ограничений и особенностей взаимодействия таких моделей в системе в целом, предоставляют возможность эффективного решения конкретных вариантов общей задачи и выбора подходящего метода и алгоритма для их решения.
Апробация работы. Основные результаты работы докладывались на международной научной конференции «6th St. Petersburg Workshop on 8іши1а^оп»(Санкт-Петербург, 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 наименование.
