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

ВВВДЕНИЕ.

ГЛАВА I. ПРОБЛЕМ АДАПТИВНОГО УПРАВЛЕНИЯ НА ДИСКРЕТНЫХ СИТУАЦИОННЫХ СЕТЯХ И АВТОМТНО-СИТУАЦИОННЬЙ ПОДХОД К ЕЕ РЕШЕНИЮ.

1.1. Дискретные ситуационные сети и вопросы адаптивного управления на них.

1.2. Автоматы и их использование в системах управления.

1.2.1. Вероятностные автоматы и их взаимодействие со случайной средой.

1.2.2. Асимптотические последовательности автоматов.

1.2.3. Автоматы с формируемой структурой.

1.2.4. Опыт использования автоматов в системах управления.

1.3. Ситуационное управление и проблема обобщения ситуаций.

1.3.1. Принципы ситуационного управления

1.3.2. Проблема обобщения ситуаций.

1.4. Управление на дискретных ситуационных сетях на базе автоматного и ситуационного подходов.

1.4.1. Автоматный подход к управлению на дискретных ситуационных сетях

1.4.2. Автоматно-ситуационный подход к управлению на дискретных ситуационных сетях.

ВЫВОДЫ.

ГЛАВА 2. МОДЕЛИ ФУШЩИОНИРОВАНИЯ АВТОМАТОВ В СЛОЖНЫХ СЛУЧАЙНЫХ СРВДАХ.

2.1. Общие положения и постановка задачи.

2.2. Поведение автоматов с переменной структурой в

- 3

Л Стр. случайное среде .реагирующей на смену действии.

ЛГ /|

2.3. Алгоритм обучения автомата в среде Í,.

2.4. Поведение простейших автоматов в среде S^.

2.5. Асимптотически-оптимальные последовательности автоматов в среде SM

2.6. Асимптотически-оптимальные последовательности автоматов с произвольным числом действий.

2.7. Поведение автоматов в управляемой переключаемой среде.

ВЫВОДЫ.

ГЛАВА 3. АВТОМАТНЫЕ МОДЕЛИ УПРАВЛЕНИЯ НА ДИСКРЕТНЫХ СЕТЯХ

ТИПА СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ.

3.1. Постановка задачи управления в системах массового обслуживания.

3.2. Исходные предпосылки для использования автоматных моделей в системах массового обслуживания.

3.3. Автоматная модель управления разомкнутой системой массового обслуживания.

3.3.1. Определение параметров случайной среды, в которой функционирует управляющие автоматы.

3.3.2. Описание автоматной модели.

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

3.5. Управление в замкнутой системе массового обслуживания.

ВЫВОДЫ.

ГЛАВА 4. АВТОМТНО-ШТУАЦИОННЫЕ МОДЕЛИ УПРАВЛЕНИЯ ДИСКРЕТНЫМИ СЕТЯМИ.

4.1. Основные принципы построения автоматно-ситуационных моделей. igj

4.2. Исследование условий разделимости ситуаций на классы управлений.

4.3. Построение асимптотически-целенаправленной последовательности макросостояний.

4.4. Автоматно-ситуационная модель формирования асимптотически-оптимальной последовательности макросостояний.

4.4.1. Исследование решения задачи управления в неадаптивной постановке.

4.4.2. Разработка автоматно-ситуационной модели.

4.5. Формирование макросостояний в ситуационной модели.

ВЫВОДЫ.

ГЛАВА 5. ПРАКТИЧЕСКОЕ ИСПОЛЬЗОВАНИЕ АВТОМАШО-СИТУАЦИОННЫХ

МОДЕЛЕЙ УПРАВЛЕНИЯ.

5.1. Разработка пакета прикладных программ для имитационного моделирования и управления на сети ЭВМ.

5.1.1. Постановка задачи управления на сети ЭВМ.

5.1.2. Общее описание структуры пакета и модели объекта управления.

5.1.3. Описание модели управления и результаты экспериментов.

5.2. Разработка алгоритмов и комплекса программ для оперативного управления ресурсами на сетевых графиках.

5.2.1. Задача распределения ресурсов на сетевых графиках.

5.2.2. Основные принципы формирования модели оперативного управления ходом выполнения работ сетевого графика.

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

ВЫВОДЫ.

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

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

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

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

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

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

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

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

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

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

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

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

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

Практическая ценность и реализация результатов работы. Идеи и методы, разработанные в диссертационной работе, нашли практическое воплощение при создании пакета программ для имитационного моделирования и управления на сети ЭВМ и комплекса программ для распределения ресурсов на сетевых графиках, разработанных под руководством автора в соответствии с планом научно-исследовательских работ Ж с ВЦ УзНПО "Кибернетика" Ж УзССР по темам:

Разработка теории и схем применения логико-эвристических методов анализа и управления сложными системами" (1976-80 гг.);

Разработать и сдать в ГФАП ППП для ситуационного управления потоком заданий в экспериментальной сети взаимодействующих ВЦ" (1979-81 гг., выполнена в соответствии с Постановлением ГКНТ СССР № 254 от 7 июня 1979 г.);

Разработать и исследовать автоматные и ситуационные модели управления сложными системами в частности, вычислительными сетями" (выполняется с 1981 г. в рамках.Целевой комплексной научно-технической программы 0.Ц.25).

Результаты диссертации использованы в виде: методических рекомендаций при создании эскизного проекта "Центра управления первой очереди вычислительной сети Академии Наук СССР и академий наук союзных республик"; алгоритмов и программ при разработке в ТАШПКБ-АСУ автоматизированной системы управления головным заводом НПО "Электротерм" Минэлектротехпрома СССР; комплекса программ и инструкций при создании комплекса задач оперативного календарного планирования "Комплект-ЗМ", внедренных в подразделениях Минводхоза СССР и Минстроя УзССР.

Экономический эффект от внедрения результатов работы составляет свыше 400 тыс.руб.

Апробация работы. Результаты работы доложены: на семинаре "Децентрализованные методы управления" в Московском доме научно-технической пропаганды им. В.Дзержинского (Москва, 1972 г.); Всесоюзном симпозиуме по искусственному интеллекту (Тбилиси, 1974 г.); 1У, У и У1 Всесоюзных симпозиумах по ситуационному управлению большими системами (Одесса, 1976,1978, 1981 гг.); Всесоюзной конференции "Семиотические модели при управлении большими системами" (Клайпеда, 1979 г.); Всесоюзном совещании по ситуационному управлению (Калининград, 1979 г.); Ш и 1У симпозиумах "Логическое управление в промышленности" (Каунас, 1980 г., Орджоникидзе, 1981 г.); УШ Всесоюзном совещании по проблемам управления (Таллин, 1980 г,); Всесоюзной конференции "Основные направления развития программного обеспечения ЭВМ, комплексов и сетей ЭВМ" (Севастополь, 1981 г.); Советско-итальянском семинаре "Теория иерархических структур" (Ташкент, 1981 г,); УП Республиканской школе молодых ученых и специалистов по АСУ (Ташкент, 1982 г.); Ш Всесоюзном симпозиуме

Вероятностные автоматы и их приложения" (Казань, 1983 г.); ХП Всесоюзной школе-семинаре по адаптивным системам (Могилев, 1984 г.) и др.

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

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

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

1. На основе обобщения результатов теорий автоматных и ситуационных моделей, а также собственных разработок и исследований автора в этой области, созданы основы теории автоматно--ситуационных двухуровневых адаптивных моделей управления сложными системами типа дискретных ситуационных сетей.

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

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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