Содержание к диссертации
Введение
ГЛАВА I. ПРОБЛЕМ АДАПТИВНОГО УПРАВЛЕНИЯ НА ДИСКРЕТНЫХ СИТУАЦИОННЫХ СЕТЯХ И АВТОМТНО-СИТУАЦИОННЬІ ПОДХОД К ЕЕ РЕШЕНИЮ 14
1.1. Дискретные ситуационные сети и вопросы адаптивного управления на них 14
1.2. Автоматы и их использование в системах управления.. 26
1.2.1. Вероятностные автоматы и их взаимодействие со случайной средой 26
1.2.2. Асимптотические последовательности автоматов 30
1.2.3. Автоматы с формируемой структурой 34
1.2.4. Опыт использования автоматов в системах управления 42
1.3. Ситуационное управление и проблема обобщения ситуаций 52
1.3.1. Принципы ситуационного управления 52
1.3.2. Проблема обобщения ситуаций 59
1.4. Управление на дискретных ситуационных сетях на базе автоматного и ситуационного подходов... 64
1.4.1. Автоматный подход к управлению на дискретных ситуационных сетях 65
1.4.2. Автоматно-ситуационный подход к управлению на дискретных ситуационных сетях 70
ВЫВОДЫ 73
ГЛАВА 2. МОДЕЛИ ФУНКЦИОНИРОВАНИЯ АВТОМТОВ В СЛОЖНЫХ СЛУЧАЙНЫХ СРЕДАХ 75
2.1. Общие положения и постановка задачи 75
2.2. Поведение автоматов с переменной структурой в случайное среде «? реагирующей на смену действий 84
2.3. Алгоритм обучения автомата в среде 92
2.4. Поведение простейших автоматов в среде 99
2.5. Асимптотически-оптимальные последовательности автоматов в среде ом 105
2.6. Асимптотически-оптимальные последовательности автоматов с произвольным числом действий 117
2.7. Поведение автоматов в управляемой переключаемой среде. 128
ВЫВОДЫ 133
ГЛАВА 3. АВТОМАТНЫЕ МОДЕЛИ УПРАВЛЕНИЯ НА ДИСКРЕТНЫХ СЕТЯХ ТИПА СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ 135
3.1. Постановка задачи управления в системах массового обслуживания 135
3.2. Исходные предпосылки для использования автоматных моделей в системах массового обслуживания 143
3.3. Автоматная модель управления разомкнутой системой массового обслуживания... 157
3.3.1. Определение параметров случайной среды, в которой функционирует управляющие автоматы 157
3.3.2. Описание автоматной модели 163
3.4. Учет в модели некоторых свойств управляемого процесса 172
3.5. Управление в замкнутой системе массового обслуживания 178
ВЫВОДЫ 188
ГЛАВА 4. АВТОМТНО-СИТУАЦИОННЫЕ МОДЕЛИ УПРАВЛЕНИЯ: ДИСКРЕТНЫМИ СЕТЯМ 191
4.1. Основные принципы построения автоматно-ситуационных моделей 191
4.2. Исследование условий разделимости ситуаций на классы управлений 196
4.3. Построение асимптотически-целенаправленной последовательности макросостояний 203
4.4. Автоматно-ситуационная модель формирования асимптотически-оптимальной последовательности макросостояний 215
4.4.1. Исследование решения задачи управления в неадаптивной постановке 218
4.4.2. Разработка автоматно-ситуационной модели 223
4.5. Формирование макросостояний в ситуационной модели 229
ВЫВОДЫ 241
ГЛАВА 5. ПРАКТИЧЕСКОЕ ИСПОЛЬЗОВАНИЕ АВТОМАШО-СИТУАВДОННЫХ МОДЕЛЕЙ УПРАВЛЕНИЯ 243
5.1. Разработка пакета прикладных программ для имитационного моделирования и управления на сети ЭВМ 243
5.1.1. Постановка задачи управления на сети ЭВМ 243
5.1.2. Общее описание структуры пакета и модели объекта управления 249
5.1.3. Описание модели управления и результаты экспериментов. 256
5.2. Разработка алгоритмов и комплекса программ для оперативного управления ресурсами на сетевых графиках 266
5.2.1. Задача распределения ресурсов на сетевых графиках 266
5.2.2. Основные принципы формирования модели оперативного управления ходом выполнения работ сетевого графика. 270
5.2.3. Общее описание структуры программного комплекса и его использование для решения практических задач
ВЫВОДЫ
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА
ПРИЛОЖЕНИЕ
- Дискретные ситуационные сети и вопросы адаптивного управления на них
- Поведение автоматов с переменной структурой в случайное среде «? реагирующей на смену действий
- Постановка задачи управления в системах массового обслуживания
- Основные принципы построения автоматно-ситуационных моделей
- Разработка пакета прикладных программ для имитационного моделирования и управления на сети ЭВМ
Введение к работе
Актуальность проблемы» Необходимость использования адап-тивного метода возникает при решении задач управления объектами с неполной начальной информацией о параметрах и законах их функционирования. Для теории адаптивных систем весьма актуально исследование различных ее методов применительно к конкретным классам объектов управления. В последние годы большое внимание уделялось адаптивным методам управления, основанным на использовании моделей вероятностных автоматов. Однако, несмотря на простоту, наглядность и легкореализуемость на ЭВМ (важное свойство с точки зрения практического использования) автоматных моделей, они не нашли широкого применения в практических задачах по следующим причинам, характеризующим недостатки существующей теории.
Во-первых, при использовании автоматных моделей управления предполагается, что объект управления выступает в качестве внешней случайной среды, в которой функционируют управляющие автоматы. Другими словами, случайная среда выступает в качестве модели объекта управления. Поэтому задача построения адаптивной системы для оптимального управления конкретным объектом сводится к задаче выбора такой конструкции автомата, функционирование которого в случайной среде, выступающей в роли модели объекта управления, является оптимальным. Но для пользователей возможности выбора автоматов небольшие, так как к настоящему времени поведение автоматов систематически изучено в ограниченном классе случайных сред и построены лишь конструкции автоматов, обладающих оптимальным поведением в этих средах.
Во-вторых, для выбора автоматов, способных оптимально уп- равлять конкретным объектом, необходимо формализованно описать его в виде некоторой случайной среды. Однако к настоящему времени не разработаны методы описания отдельных классов объектов управления в виде адекватных им классов случайных сред.
В-третьих, при автоматном управлении широким классом объектов, называемых дискретными сетями, каждому управляемому состоянию сети сопоставляется вероятностный автомат с числом действий, равным числу возможных управлений в данном состоянии. При росте же числа состояний сети и числа действий автоматов, сопоставляемых с ними, значительно ухудшаются показатели качества функционирования автоматной модели.
Всесторонний анализ перечисленных недостатков современного состояния теории автоматных моделей управления позволил выявить возможные направления дальнейшего ее развития. Если два первых недостатка могут быть устранены в рамках самой теории автоматных моделей, то третий требует принципиально нового подхода. Исходя из приведенных рассуждений, в данной работе исследованы вопросы, связанные с развитием теории и методов использования автоматных моделей адаптивного управления, а также с разработкой и изучением основ построения нового класса адаптивных моделей, названных автоматно-ситуационными.
Основные дели работы. Они состоят в разработке, исследовании и практическом применении нового класса адаптивных систем управления» основанных на двухуровневых автоматно-ситуа-ционных моделях. В соответствии с ними исследованы и решены следующие задачи: Выделен класс сложных систем, так называемых дискретных ситуационных сетей, и показана целесообразность использования для управления ими автоматных и ситуационных моделей; созданы специальные классы автоматных и автоматно-ситуа- ционных моделей для реализации функций адаптивного управления дискретными сетями; исследованы модели взаимодействия вероятностных автоматов со сложными составными средами, составляющие которых переключаются действиями самих автоматов, и построены автоматы, обладающие оптимальным поведением в подобных средах; разработаны и использованы для решения прикладных задач программы реализации автоматно-ситуационных систем управления дискретными сетями.
Методы исследования. Методологическую основу работы составляют методы теории поведения автоматов, ситуационного и адаптивного управлений. На отдельных этапах работы использовались методы теории вероятностей, в частности, теории цепей Маркова, методы имитационного моделирования, методы теории систем массового обслуживания и др.
Научная новизна. На основе обобщения существующих автоматных и ситуационных моделей, а также собственных разработок и исследований автора в этой области предложен и изучен класс автоматно-ситуационных адаптивных двухуровневых моделей управления сложными системами. Основные положения, выдвигаемые на защиту, связаны с изучением этого класса моделей управления и заключаются в следущих научных результатах, составляющих основы нового научного направления в рамках теории адаптивных систем.
Изучены модели функционирования автоматов в составных случайных средах, составляющие которой переключаются действиями самих автоматов. Разработаны алгоритмы обучения автоматов с формируемой структурой и конструкции последовательностей автоматов, функционирование которых в переключаемых средах целесообразно или асимптотически оптимально.
Создана методика описания функционирования некоторых классов дискретных сетей типа управляемых систем массового обслуживания (СМО) в виде специального класса сложных случайных сред. Они состоят из множества стационарных случайных сред, переключение которых осуществляется управляемой цепью Маркова. С их помощью показана возможность использования автоматно-ситуаци-онных моделей для организации оптимальных приоритетов в рассмотренных классах СМО. Обоснование основных утверждений проведено в следующей последовательности: функционирование управляемой системы массового обслуживания описано вложенной по моментам управления цепью Маркова; полуены формулы для вычисления вероятностей потерь в состояниях СМО, при помощи которых оказалось возможным выразить в явном виде функционал общих потерь в системе через параметры управления; доказана основная теорема о том, что распределения вероятностей на множествах действий автоматов, выполняющих функции оптимального управления в рассмотренных классах СМО, являются вырожденными; доказана, что задача организации адаптивной модели управления в системах массового обслуживания с конечной очередью эквивалентна задаче организации асимптотически оптимального поведения автоматов в переключаемой, в зависимости от действий автоматов, случайной среде.
Разработана автоматно-ситуационная модель управления в СМО, состоящая из множества автоматов, каждый из которых соответствует одному состоянию очереди СМО. Экспериментально показано, что в такой системе локально-оптимальное поведение каждого автомата в своей среде оптимально для всего коллектива в целом. Этот факт позволил высказать следующую гипотезу.Про- - ю - цесс решения задачи линейного программирования, эквивалентной задаче оптимального управления в СМО с конечной очередью в неадаптивной постановке, можно свести к поиску минимальных элементов среди вероятностей потерь, соответствующих различным управлениям в отдельных состояниях системы.
Введены понятия теории автоматно-ситуационных моделей управления дискретными сетями, такие как асимптотически-целенаправленная и асимптотически-оптимальная последовательности обобщенных описаний состояний дискретной сети. Предложены и теоретически исследованы методы построения определенных выше последовательностей.
Практическая Деннрсть д реализация результатов., работу Идеи и методы, разработанные в диссертационной работе, нашли практическое воплощение при создании пакета программ для имитационного моделирования и управления на сети ЭВМ и комплекса программ для распределения ресурсов на сетевых графиках, разработанных под руководством автора в соответствии с планом научно-исследовательских работ Ж с ВЦ УзНПО "Кибернетика" -АН УзССР по темам: "Разработка теории и схем применения логико-эвристических методов анализа и управления сложными системами" (1976-80 гг.); "Разработать и сдать в ГФАП ПШІ для ситуационного управления потоком заданий в экспериментальной сети взаимодействующих Щ" (1979-81 гг., выполнена в соответствии с Постановлением ІЖГ СССР № 254 от 7 июня 1979 г.); "Разработать и исследовать автоматные и ситуационные модели управления сложными системами в частности, вычислительными сетями" (выполняется с 1981 г. в рамках.Целевой комплексной научно-технической программы 0.Ц.25). - II -
Результаты диссертации использованы в виде: методических рекомендаций при создании эскизного проекта "Центра управления первой очереди вычислительной сети Академии Наук СССР и академий наук союзных республик"; алгоритмов и программ при разработке в ТАШПКБ-АСУ автоматизированной системы управления головным заводом НПО "Электротерм" Минэлектротехпрома СССР; комплекса программ и инструкций при создании комплекса задач оперативного календарного планирования "Кошшект-ЗМ", внедренных в подразделениях Минводхоза СССР и Минстроя УзССР.
Экономический эффект от внедрения результатов работы составляет свыше 400 тыс.руб.
Апробация работы. Результаты работы доложены: на семинаре "Децентрализованные методы управления" в Московском доме научно-технической пропаганды им. В.Дзержинского (Москва, 1972 г.); Всесоюзном симпозиуме по искусственному интеллекту (Тбилиси, 1974 г.); ІУ, У и УІ Всесоюзных симпозиумах по ситуационному управлению большими системами (Одесса, 1976,1978, 1981 гг.); Всесоюзной конференции "Семиотические модели при управлении большими системами" (Клайпеда, 1979 г.); Всесоюзном совещании по ситуационному управлению (Калининград, 1979 г.); Ш и ІУ симпозиумах "Логическое управление в промышленности" (Каунас, 1980 г., Орджоникидзе, 1981 г.); УШ Всесоюзном совещании по проблемам управления (Таллин, 1980 г.); Всесоюзной конференции "Основные направления развития программного обеспечения ЭВМ, комплексов и сетей ЭВМ" (Севастополь, 1981 г.); Советско-итальянском семинаре "Теория иерархических структур" (Ташкент, 1981 г.); УЇЇ Республиканской школе молодых ученых и специалистов по АСУ (Ташкент, 1982 г.); Ш Всесоюзном симпозиуме "Вероятностные автоматы и их приложения" (Казань, 1983 г.); ХП Всесоюзной школе-семинаре по адаптивным системам (Могилев, 1984 г.) и др.
Публикации. По результатам диссертации опубликованы 34 научные работы, в том числе одна монография.
Структура и краткое содержание работы. Диссертация состоит из введения, 5 глав, заключения, списка использованной литературы и приложения.
Дискретные ситуационные сети и вопросы адаптивного управления на них
В настоящее время общепризнано, что единого аппарата для формализованного описания всех классов больших систем не существует. Например, даже наиболее развитый и поэтому часто используемый для таких целей аппарат математики - язык уравнений (линейных, нелинейных, дифференциальных, интегродифферен-циальных и др.) - становится непригодным для описания систем с начальной неопределенностью, в которых отсутствует априорная информация, необходимая для связывания внутренних параметров системы и внешних, как управляемых, так и неуправляемых, воздействий с выходными переменными. В силу этого приходится ограничиться рассмотрением отдельных подклассов объектов управления, представляющих интерес с практической точки зрения, и описанием и исследованием их с единых позиций.
Для формализации описания и поиска методов решения задач управления в широком классе объектов, такие как транспортные системы, всевозможные сети и системы сбора, хранения и обработки информации, ряд производственных систем и др., оказываются эффективными специального вида дискретные ситуационные сети (ДСС). Используемое здесь понятие ДСС опирается на результаты работ [l,2j .
Поведение автоматов с переменной структурой в случайное среде «? реагирующей на смену действий
Пусть стохастический автомат с переменной структурой (его определение дано в 1.2) функционирует в среде SM, Рас смотрим его поведение при линейном способе обучения. Здесь ограничимся случаем fll=fl=2 . Если под влиянием входного сигнала X, ОС=0J , автомат в момент с / перешел из состояния Q. в состояние а. тв. ъ момент времени t получил сигнал "штраф", то элемент уЭ. (X) матрицы Рл изменяется на элемент сСр..(Х) , а в случае сигнала "не штраф" этот же элемент заменяется на элемент /-oC+oCflfaX в обоих случаях остальные элементы z -й строки пересчитьшаются для сохранения условия нормировки.
Определим математическое ожидание р.. (X) - 85 здесь =1,2, 7=1» если t-2 и У =2, если е =1;
Как и ранее будем говорить, что достигаются стационарные значения /У. (X) , если выполняются условия которые в рассматриваемом случае достигаются при.
Как видим, матрицы штрафов и поощрений оказались равными между собой, поскольку алгоритм обучения автомата устроен так, что при переходе автомата из состояния #г-в состояние й-соответствующая этому переходу вероятность Д. (X) пересчи-тывается в зависимости от сигнала среды, но при этом различается под действием какого сигнала (штрафа или поощрения), т.е. по какой матрице, был осуществлен этот переход.
Рассмотрим указанные случаи:
а) на всякое действие автомата среда реагирует сигналом "штраф", поэтому никогда не происходит обращение к матрице;
б) после совершения автоматом оптимальной последовательности действий »#,#,#,#,... на его вход поступает только сигнал "поощрение" и автомат обращается к матрице Ц ;
в), г) обученный автомат делает одно действие ( 1/ в случае в) и у в случае г) и обращение происходит только к матрице 1 ;
д) на выход автомата поступает только сигнал "поощрение", поэтому всегда происходит обращение только к матрице
Таким образом, стохастический автомат с переменной структурой, обучающейся в среде ом , может быть определен заданием одной единственной матрицы переходов. Отметим, что это утверждение справедливо только для алгоритмов обучения рассматриваемого нами вида, в которых пересчет переходных вероятностей осуществляется независимо от значения входного сигнала, под действием которого осуществлен переход.
Постановка задачи управления в системах массового обслуживания
Разнообразные системы массового обслуживания являются типичными примерами дискретных ситуационных сетей. В СМО, как будет показано ниже легко выделяются элементы, с помощью которых определяется структура ДСС - истоки, стоки, пассивные и активные преобразователи. Эта глава посвящена вопросам разработки и исследования автоматных моделей управления некоторыми классами дискретных сетей типа систем массового обслуживания.
Широкое распространение методов теории массового обслуживания связано с тем, что математической моделью многих объектов управления выступают системы массового обслуживания. Ставшая уже классической теория массового обслуживания первоначально развивалась в направлении изучения систем массового обслуживания с заранее заданными значениями ее параметров [97-102] . Последнее время центр тяжести исследований перемещается в сторону изучения управляемых систем массового обслуживания [іОЗ-105] . При рассмотрении управляемых СМО приходится непосредственно обращаться к задаче минимизации некоторой функции стой-, мости относительно задержки и/или потерь различных требований. Поэтому исследование управляемых СМО связано с необходимостью постановки и решения оптимизационных задач.
Понятие управляемой системы массового обслуживания определим используя результаты [юз] . Как объект математического исследования система массового обслуживания характеризуется еледующими элементами; входящими потоками требований, механизмом и длительностями обслуживания, структурой системы, дисциплиной обслуживания. Каждый из этих элементов задается определенными правилами и/или параметрами. Для входящего потока требований это - законы распределения интервалов между последовательными моментами поступления требований, для механизов обслуживания параметры законов распределения длительности обслуживания разных типов требований в различных приборах, для дисциплины обслуживания - правила, согласно которым выбираются требования для обслуживания или такие параметры как вероятность выбора того или иного требования из очереди в зависимости от состояния последней.
Система, в которой какие-либо из правил и/или параметров могут изменяться под воздействием управляющих сигналов, называется управляемой СМО.Хотя развиваемый в данной работе адаптивный подход можно использовать для всяких управляемых (МО, здесь будут рассматриваться такие управляемые (МО, в которых управлению подвергаются лишь правила и/или параметры дисциплины обслуживания. Это связано с тем, что в настоящее время именно СМО с управляемой дисциплиной обслуживания получили наибольшее развитие и практическое распространение [і06-ІІб] .
Основные принципы построения автоматно-ситуационных моделей
В главе I было показано целесообразность совместного использования автоматного и ситуационного подходов для построения двухуровневых моделей управления в тех случаях, когда число состояний объекта управления является бесконечным или достаточно большим. Напомним, что согласно описанной концепции, автоматная модель, являющаяся моделью нижнего уровня, используется для разбиения множества состояний объекта управления на классы, а ситуационная модель, являющаяся моделью верхнего уровня - для обобщенного описания состояний, входящих в один и тот же класс.
В этой главе будут изучены вопросы, связанные с разработкой и исследованием подобных моделей.
Прежде чем приступить к обсуждению вопросов, непосредственно относящихся к разработке автоматно-ситуационных моделей, рассмотрим основные принципы, на которых они основываются. Ими являются следующие принципы: дискретность, самообучаемость, иерархичность, макроструктурность, целенаправленность, преемственность.
I. Дискретность. В соответствии с этим принципом, модель управления, так же как и модель объекта управления, описывается при помощи конечного или счетного множества элементов. В качестве таких множеств выступают: множество состояний объекта управления (конечное или счетное); множество автоматов (конечное), сопоставляемых отдельным состояниям или подмножествам состояний объекта управления; множество возможных управлений в системе (конечное); последовательность (счетная) обобщенных описаний состояний и др. Конечность и счетность, например, множества состояний вытекает из того факта, что в данной работе в качестве объектов управления рассматриваются ДСС, а множество их состояний определяется конечным или счетным набором конечных значений случайных процессов (см. раздел I.I).
Этот принцип не предполагает дискретности времени в самом объекте управления, хотя такое ограничение кажется естественным для данной работы. Но с другой стороны, в связи с изучением разработанных моделей на ЭВМ, необходимо перейти к дискретному времени. Это противоречие, как видно из предыдущих глав, и как будет показано далее,снимается при помощи перехода к рассмотрению только интересующих нас, с точки зрения управления, моментов изменения параметров исследуемых процессов. Например, при рассмотрении марковских процессов, осуществляется переход к вложенным, по интересующим нас моментам, цепям Маркова.
Разработка пакета прикладных программ для имитационного моделирования и управления на сети ЭВМ
Современная технология сбора, хранения и обработки информации всецело базируется на использовании электронных вычислительных машин [і5б] . Ее совершенствование связано с необходимостью постоянного повышения быстродействия и производительности средств вычислительной техники. Этого можно достигнуть как за счет совершенствования программно-технической базы вычислительных машин, так и за счет совершенствования организации совместного функционирования совокупности вычислительных средств. В последние годы в обеих направлениях достигнуты большие успехи. С одной стороны были последовательно разработаны вычислительные машины первых трех накоплений, разрабатываются машины четвертого поколения [I57J и начаты работы по разработке машин пятого поколения [158, 159 ] , а с другой стороны успешно разрабатывалась концепция организации совместного использования ЭВМ посредством их объединения в вычислительные системы и сети [І60-І63]
Создание вычислительных систем и сетей, ориентированных на широкий крут пользователей привело к появлению конкуренции между пользователями на занятие программных и технических ресурсов. Такой множественный доступ к ограниченным ресурсам привело в свою очередь к необходимости организации очередей требований конкурирующих пользователей. Поэтому естественно, возникающие здесь задачи решаются в рамках теории массового обслуживания.
В вычислительных системах и сетях практически невозможно заранее точно определить их параметры, в первую очередь параметры входящих потоков, которые необходимы для принятия тех или иных управленческих решений в конкретных ситуациях, и поэтому приходится обратиться к использованию адаптивного подхода как инструменту построения оптимальных алгоритмов управления [164 -165] .
В данном разделе диссертации на примере решения некоторых классов задач, возникающих при организации функционирования вычислительных систем и сетей, покажем эффективность использования адаптивных систем управления, основанных на автоматно-ситу-ационных моделях [166-174].
