автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Модели и технологии адаптивной обработки информации для частично наблюдаемых систем



На правах рукописи УДК 519 218+519 857 3

ООЗ166402

Коновалов Михаил Григорьевич

МОДЕЛИ И ТЕХНОЛОГИИ АДАПТИВНОЙ ОБРАБОТКИ ИНФОРМАЦИИ ДЛЯ ЧАСТИЧНО НАБЛЮДАЕМЫХ СИСТЕМ

05.13.17 - теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора технических наук

О ° АПР 2008

Москва 2008

^Работа выполнена в Институте проблем информатики РАН

Официальные оппоненты:

член-корреспондент РАН, доктор физико-математических наук, профессор Флеров Юрий Арсениевич

заслуженный деятель науки РФ, доктор технических наук, профессор Оганян Герман Арташесович

заслуженный деятель науки РФ, доктор технических наук, профессор Синицин Игорь Николаевич

Ведущая организация:

Московский государственный технический университет им Н Э Баумана

Защита состоится «ЖЗ» 2008 года в iS часов на заседании

диссертационного совета Д 002 073 01 при Институте проблем информатики РАН по адресу 119333, Москва, ул Вавилова, 44, корп 2

С диссертацией можно ознакомиться в библиотеке Института проблем информатики РАН

Автореферат разослан « ¿^7» « 2008 года

Ученый секретарь

диссертационного совета Д002 073 01, доктор технических наук, профессор

' С Н Гринченко

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

Актуальность темы

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

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

Основополагающие идеи теории адаптации были заложены в 50-х годах прошлого века1'2, а становление теории и ее развитие до конца 80-х годов проходило во многом благодаря усилиям отечественных исследователей3 С начала 90-х годов и по настоящее время это направление переживает большой подъем, а число публикаций исчисляется многими сотнями В частности, выделилась и получила широкое распространение новая ветвь, тесно связанная с искусственным интеллектом и его разнообразными приложениями4

Центральное место в теории адаптации занимает проблематика частично наблюдаемого марковского процесса принятия решений Традиционный подход, основанный на динамическом программировании, дал результаты, применимые в адаптивном варианте5'6 «Марковские процессы являются в настоящее время

"H Robbins, S Monro A stochastic approximation method//Ann Math Stat -V 22 -1951 -P 400-407

2 H Robbins A sequential decision problem with a finite memory // Proc Nat Acad Sei USA -V 42, No 3 -1956 -P 920-923

3 V G Sragovich Mathematical Theory of Adaptive Control - Singapore World Scientific, 2006

4 R Sutton, A Barto Reinforcement learning - MIT Press, 2000

SD P Bertsekas Dynamic programming and optimal control, V 1,2 - Belmont Athena Scientific, 2001

математическим фундаментом для многих работ в области активного обучения (reinforcement learning), теории принятия решений, поиска информации, распознавания речи, активного зрительного восприятия, навигации роботов»7 В то же время «одна из основных проблем в приложении теории марковского процесса принятия решений заключается в необходимости рассматривать не слишком большое пространство состояний»8 Как подчеркивают многие авторы, и как свидетельствует большой поток публикаций, необходим дальнейший прогресс в этой области, имеющей неоспоримое прикладное значение

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

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

Цель и задачи исследования

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

проведении исследований были поставлены следующие основные задачи

1 Разработка теоретических основ синтеза адаптивных стратегий в общих моделях частично наблюдаемых стохастических объектов

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

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

4 Реализация комплекса действий, связанных с синтезом информационных технологий для моделирования, адаптивной обработки информации и принятия решений на примерах крупных прикладных проблем

6 Н S Chang, М С Fu, J Ни, S I Marcus Simulation-based algorithms for Markov decision Processes - London Springer, 2007

7 S Mahadevan. Spatiotemporal abstraction of stochastic sequential processes // Lecture Notes m Computer Science, 2371 - 2002

8 T Belker, M Beetz, А В Cremers Learning action models for the improved execution of navigation plans//Robotics and Autonomous Systems, 38 -2002 -P 137-148

9 В С Пугачев, И Н Синицын Теория стохастических систем - М Изд Логос 2004

10 Unsupervised adaptive filtering V 1,2 Edited by S Haykm -New York JohnWilley& Sons, Inc, 2000

Методы исследования

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

Основные положения, которые выносятся на защиту

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

2 Теоретические основы анализа и технология синтеза градиентных адаптивных стратегий обработки информации для частично наблюдаемого марковского процесса принятия решений

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

4 Синтез информационных технологий моделирования и адаптивного принятия решений для сети с коммутацией каналов и для распределенной вычислительной среды

Все заявленные результаты получены лично автором

Научная новизна

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

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

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

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

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

• осуществлен синтез и анализ эрланговской модели для сети с коммутацией каналов с адаптивной градиентной стратегией минимизации отказов.

В области применения адаптивных методов новой является методология моделирования и оперативной адаптивной обработки информации для широкого класса стохастических систем с неполным информационным описанием и неполным наблюдением на основе оригинальных адаптивных стратегий

Практическая ценность и реализация результатов

1) В широком плане практическая значимость результатов диссертации заключается

■ в анализе и обосновании областей и примеров приложения теории,

■ в технологии синтеза универсальных и эффективных адаптивных алгоритмов для частично наблюдаемых дискретных стохастических объектов,

■ в методологии синтеза информационных технологий моделирования и оперативной адаптивной обработки информации

2) В ходе выполнения НИР «Модель-Т» по разработке модели телефонной сети (совместно с ЗАО «Телесофт-Россия» по заказу ОАО Ростелеком) осуществлен синтез информационных технологий моделирования и адаптивного принятия решений для сети с коммутацией каналов, в том числе разработаны

■ модель и алгоритмы восстановления матрицы тяготения по результатам сетеметрии;

■ имитационная модель трафика и принятия оперативных решений на языке параллельных процессов;

■ блок адаптивной коррекции обобщенных маршрутных таблиц и оптимизации дополнительных управляющих воздействий

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

3) При разработке автоматизированных систем управления сетями связи в ходе ОКР «Система-ATM» и «Север» (ОАО «Интелтех») использованы

■ методология применения алгоритмов оптимизации управления сетевыми ресурсами на базе теории адаптивного управления частично наблюдаемыми марковскими процессами,

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

4) При разработке магистрального широкополосного аппаратного IP-шифратора «Заслон» (ЗАО «Голлард») для достижения оптимальных системотехнических и алгоритмических решений с целью максимальной совместимости с различными приложениями реального времени и различным сетевым оборудованием использованы

* методология синтеза информационных технологий для моделирования и оптимизации параметров сложных стохастических систем с помощью применения адаптивных алгоритмов в режиме off-line,

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

5) Осуществлен синтез информационной технологии моделирования системы распределенных вычислений, в том числе разработаны

■ имитационная модель коллективного взаимодействия взаимно удаленных

потребителей и распределенных вычислительных ресурсов,

■ алгоритмы адаптивной обработки информации для оперативного распределения ресурсов при неполной информации

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

Апробация

Результаты исследований и разработок, представленных в диссертации, докладывались на Всесоюзной конференции «Теория адаптивных систем и ее применение» (Ленинград, 1983), на 4-ой международной вильнюсской конференции по теории вероятностей и математической статистике (1985), на XLVII научной сессии, посвященной Дню радио (Москва, 1992), на Международной конференции по информационным сетям и системам ICINAS-98 (С-Петербург, 1998), на 3-м Всероссийском симпозиуме по прикладной и промышленной математике (Ростов-на-Дону, 2002), на 3-й Московской международной конференции по исследованию операций (ORM2001), на Международных научно-технических конференциях «Интеллектуальные системы» (IEEE AIS'03) и «Интеллектуальные САПР» (СФВ-2003), на семинаре «Seminar on Stability Problems for Stochastic Models» (Pamplona, 2003), на 8-ой международной конференции «Проблемы функционирования информационных сетей» (Иссык-Куль, 2004), на Международной научно-практической конференции «Информационные технологии и информационная безопасность в науке, технике и образовании ИНФОТЕХ-2004» (Севастополь), на семинаре «XXV International Seminar on Stability Problems for Stochastic Models» (Salerno, 2005), на 2-ой международной конференции «Распределенные вычисления и Грид-технологии в науке и образовании» (Дубна, 2006), на Международном симпозиуме «Информационные технологии и общество» (Тель-Авив, 2007), на семинарах в Вычислительном центре им А А Дородницына РАН, на семинарах в Институте проблем информатики РАН, на семинаре в Институте проблем управления РАН

Исследования по теме диссертации были поддержаны 7 грантами РФФИ

Публикации

По теме диссертации имеется 40 публикаций, из них 9 - в изданиях из перечня ВАК, 1 - монография, 4 — свидетельства о регистрации программ для ЭВМ, 17 - тезисы докладов Общий объем публикаций - более 25 п. л

Структура и объем работы

Диссертация состоит из введения, шести глав, заключения и приложения Основная часть работы изложена на 319 страницах, включая 46 рисунков, 13 таблиц и список литературы из 212 наименований Приложение занимает 26 страниц

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

Во Введении дана общая характеристика диссертации, ее предмета, цели и задач Сформулированы основные признаки, которыми отличается изучаемая проблема

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

• характеристики процесса и возможности наблюдения являются неполными,

• процесс взаимодействия сопровождается синхронной с основным процессом, наблюдаемой последовательностью «доходов»,

• цель взаимодействия - (условная) максимизация предельного среднего дохода,

• процесс чередования пар сигналов «действие - наблюдение» продолжается неограниченно долго (с практической точки зрения — «достаточно долго»). В этих условиях требуется определить для взаимодействующего субъекта

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

• адаптивность — не предполагается обязательное наличие априорной информации и зависимости от параметров объекта, может использоваться оперативная информация, полученная в ходе взаимодействия с объектом,

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

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

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

В главе 1 на основе анализа большого количества источников сделан обзор значительной части всей сферы приложений, которые классифицированы на рис 1 В качестве основных областей приложения выделены три инфоте-лекоммуникацирнные системы (раздел 1.1), производственные системы (раздел 1.2), а также приложения, связанные с моделированием поведения, искусственным интеллектом и робототехникой (раздел 1.3)

ОБЛАСТИ ПРИЛОЖЕНИЯ АДАПТИВНЫХ АЛГОРИТМОВ

Информационные и телекоммуникационные системы

Сети связи

Распределенные вычисления

Оптимальное -| использование ресурсов

Оперативное управление потоками заданий

Коррекция маршрутных таблиц

Управление потоками

Оптимизация доступа и поиск информации в Интернете

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

Оптимизация передачи голосового трафика (1Р-телефония)

Оптимизация

поддержки программного обеспечения

Оптимизация воспроизведения видеотрафика

Производственные системы

Теория расписаний и календарное планирование

Технологические процессы

■ .: \ ' ^'Ъл-

Техническое

обслуживание —————~

Управление запасами —--..1 ■ —

Искусственный интеллект

Интеллектуальные игровые системы

Роботы

Модели поведения

Управление производством и сбытом

Планирование и диспетчеризация

Оптимизация сборочного процесса

Балансировка технологи ческих линий

Гибкое автоматизированное производство

Производственные и хозяйственные роботы

Космические вездеходы

Другие приложения

я#

Управляемые системы массового обслуживания

Выбор наилучшего алгоритма

Стабилизация механических систем

Регулирование биологических ресурсов

Распознавание образов

3

Рис. 1. Примерная классификация областей приложения адаптивных методов.

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

Сравнительно новой областью приложения является проектирование систем распределенных вычислений Необходимость принятия решений возникает при распределении потоков заданий между вычислительными ресурсами, а применение адаптивных методов не нашло пока должного распространения (Данной проблеме также посвящена отдельная глава 6 ) Среди других приложений в области инфотелекоммуникаций указаны поиск информации и

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

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

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

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

В главе 2 приведены базовые определения и конструкции, необходимые для изучения теоретических основ адаптивной обработки информации при неполном наблюдении В разделе 2.1 дано общее определение объекта как дискретной частично наблюдаемой управляемой случайной последовательности Сформулировано общее понятие стратегии

В качестве общей модели рассмотрен процесс, имеющий три компоненты (х(,_уг+1,гг+|), t = О, 1, , которые называются соответственно состоянием,

действием и наблюдением Эволюция этих компонент определяется с помощью трех последовательностей условных распределений ц, = (ц0,|Л], ), V = (у,, ) и ст = (С], ), определяющих соответственно изменение состояний, появление наблюдений и выбор действий Пара (ц., у) называется объектом, последовательность ст называется стратегией, а элементы последовательности а называются правилами

Наглядно, процесс развивается следующим образом (рис 2) В начальный момент ( = 0 состояние х0 объекта определено согласно распределению ц0 В момент г - 1 субъект должен выбрать некоторое действие У] (он делает это с помощью правила а;); в результате субъект может произвести наблюдение гх, которое возникает по закону V! Если процесс достиг предыстории х'~х,у' , то состояние объекта х( возникает с помощью распределения Очередное действие у(+^ субъект выбирает, руководствуясь правилом ог+], а новое наблюдение появляется в силу распределения и т д

Рис 2 Процесс взаимодействия субъекта и объекта

Если в наблюдении можно выделить компоненту, полностью совпадающую с состоянием, то объект называется полностью наблюдаемым, а в иных случаях объект называется частично наблюдаемым Предполагается, что в любом случае наблюдение содержит компоненту, которая принимает числовые значения из интервала (0,1) и называется доходом

Выделяются некоторые типы стратегий, которые важны для анализа поведения субъекта Так, стратегия называется детерминированной, если все ее правила задаются с помощью вырожденных (сосредоточенных в одной точке) условных распределений. Стратегия имеет глубину с1>0, если все ее правила, начиная с момента с1 + \, существенно зависят только от предыстории глубины ¿/ до момента t включительно Если состояния объекта наблюдаемы, то стратегия, состоящая из правил, у которых выбор очередного действия зависит только от предыдущего состояния, называется марковской стратегией Стратегия глубины с1 называется однородной, если все ее правила, начиная с момента с1 + \, не зависят явно от времени Таким образом, в однородной стратегии глубины й, начиная с момента й + \, применяется одно и то же правило глубины с?

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

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

2 Если в управляемой однородной марковской цепи при заданном действии переход от одного состояния цепи к другому происходит детерминировано, то говорим об (управляемом) графе с доходами. Конечное множество состояний играет роль вершин графа, находясь в которых можно совершить действие из заданного конечного множества С переходом по дуге вида (г, г1, к), который осуществляется, если в вершине г выбрано действие к, связан доход — случайная величина, имеющая распределение, зависящее от г и к Изучается случай частично наблюдаемого связного графа

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

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

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

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

В разделах 3.1, 3.2 исходной позицией является некоторое заданное счетное множество стратегий Рассмотрен класс всех объектов, для которых любая стратегия из указанного счетного множества является допустимой, и при этом выполнены некоторые условия эргодичности Построена адаптивная стратегия перебора, и доказана теорема о том, что для любого объекта из обозначенного класса с помощью этой стратегии можно получить предельный средний доход, равный точной верхней грани доходов по заданному счетному множеству стратегий Этот результат можно более наглядно перефразировать так Задано счетное количество «алгоритмов поведения» и имеется объект, свойства которого заранее неизвестны, и к которому можно применить любой из этих алгоритмов Построена стратегия, которая достигает той же цели, что и наилучший из алгоритмов

При построении адаптивной стратегии метод перебора реализован сле-

2 1+п

дующим образом Обозначим ф/ и = — 'УJgs, где gt - последовательность

доходов, а п - натуральное число, и положим 0<и - м((1 - Ф,^)-"), где М( ) означает целую часть числа Зададим последовательность марковских моментов с помощью рекуррентных соотношений Тд = 0, х„ = ти_1 + п + 9Й, где 9Л = 0Т ь„ Зададим также последовательность случайных величин Рй,

принимающих целые положительные значения

Пусть Е - заданное счетное множество стратегий Стратегия перебора

00

ст* = Р) определяется формулой ст* = }> ст<^ Где

п=\

I - индикаторная функция Развернутое описание стратегии а* выглядит следующим образом Процесс управления разбивается на этапы Этап с номером п начинается в момент ти_| +1 и оканчивается в момент т„ В момент, предшествующий началу очередного этапа, определяется номер стратегии, принадлежащей множеству 2, из которой будут взяты правила для применения на данном этапе Этот номер равен значению случайной величины Р„ Продолжительность этапа равна п + 8И и зависит, следовательно, от номера этапа и от оценки качества применяемой стратегии, полученной в течение первых п тактов

Интересно отметить, что на каждом этапе стратегии перебора в течение 9„ тактов (с ростом значения п это будет подавляющая часть времени) текущая информация не обрабатывается

В разделе 3.3 с помощью метода перебора решена задача построения адаптивной стратегии для класса регенерируемых объектов (доказана соответствующая теорема) В разделе 3.4 доказана аналогичная теорема с более сильным результатом для класса однородных конечных связных частично наблюдаемых марковских цепей

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

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

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

Градиентный подход в марковском процессе принятия решений появился позже других методов. Первые из известных работ этого направления11 скорее «обозначали желание» двигаться по градиенту, чтобы оптимизировать целевую функцию, и не дали конструктивных алгоритмов. Основная формула для градиента была опубликована в 1989 г 12, и там же был указан путь ее использования, в том числе в условиях неполного наблюдения и распределенного характера взаимодействия Начиная примерно с середины 90-х годов, за рубежом появилось много публикаций, связанных с градиентным подходом13,14 Исследования, которые излагаются в диссертации, проводились независимо от этих работ и не имеют среди них аналогов

В разделе 4.1 рассматривается однородная управляемая связная марковская цепь со счетным множеством состояний X, и конечным множеством действий У Вероятность перехода в состояния г при условии, что цепь находится в состоянии 7 и выбрано действие к обозначается . Одношаговый доход в состоянии г при выборе действия к считается детерминированным и обозначается С^

Пусть 0 е ¥ Однородную марковскую стратегию можно отождествить с матрицей 5 с элементами , которые означают вероятность выбора действия к е У\{0} при условии, что в предыдущий момент система находилась в состоянии г Для любого 5 > 0 такого, что |У| 8 < 1, определим множество

стратегий Б5 = Ь <1-8, 5г(/)>8, геХ, / е Г \ {0} [ и положим

I к> 0 ]

8 = Если Хе Б, то матрица Р = Р(5') с элементами 8>0

к> О

\

?(к)п(к)

к> 0

Q^ является переходной матрицей

обычной (неуправляемой) марковской цепи с множеством состояний X Предполагается, что если Я е в, то цепь Р является апериодической эргоди-ческой с эргодическим классом X, и поэтому предельный средний доход за

11 Y M El-Fattah Gradient approach for recursive estimation and control m finite Markov chains//Adv Appl Probab,13 -1981 -C 778-803

12 Работа [8] в списке литературы, приведенном в конце автореферата

13 X -R Cao The Relations Among Potentials, Perturbation Analysis, and Markov Decision Processes//Discrete Event Dynamic Systems Theory and Applications, 8 -1998 -P 71-87

14 P Marbach, J N Tsitsiklis Approximate gradient methods in policy-space optimization of Markov reward processes // Discrete Event Dynamic Systems Theory and Applications, 13 -2003 -P 111-148

стратегию 5 равен = тсу, где л - вектор-строка предельных вероятностей состояний, а у — вектор-столбец с компонентами

к> О

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

Теорема Частные производные предельных вероятностей в,

Эк 00

конечны и имеют вид —щ- = ^Р*, где к® - вектор-строка с ком-

и$а 1=0

понентами к^ = -(У^, ае1, 6 е Г\{0}. Частные производные предельного среднего дохода задаются формулами

айь>

м=о

Выражение для частных производных целевой функции допускает ясную интерпретацию Пусть н\к\п) означает средний доход к моменту п, который получается, если начальное состояние цепи (в момент 0) было г и при этом было выбрано действие к. Тогда с точки зрения критерия максимизации предельного среднего дохода следует увеличить (уменьшить) вероятность выбора в состоянии г действия к за счет уменьшения (увеличения) вероятности выбора действия /, если Нк, = \ш{н^к)(п)-н^(п)) > 0 (Ны < 0) По-

и-»сю

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

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

В разделе 4.5 изучается способ отыскания максимума функции на замкнутом выпуклом множестве 88, который заключается в построении рекуррентных алгоритмов градиентного типа Пусть цепь имеет конечное множество состояний. Рассмотрим последовательность = + а,у,\, где Б, е 8 8, а^ - заданная числовая последовательность, V, - некоторая случайная последовательность той же размерности, что и 81, П5 [ ] — оператор проектирования на множество , 50 — фиксированная точка из множества Последовательность задает стратегию, которую обозначим через ст и назовем градиентной адаптивной стратегией Согласно стратегии сг, если цепь в момент I находится в состоянии г, то выбор управления осуществляется с помощью распределения, содержащегося в г-ой строке матрицы 5г Это распределение является, вообще говоря, разным в разные моменты времени, поэтому стратегия а неоднородная Если последовательность V, зависит не

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

Теорема. Пусть ст — градиентная стратегия и пусть числовая последовательность а, подчиняется условиям ^ а, = оо, ^Г af < оо, а последовательность случайных векторов v, с измеримыми относительно предыстории компонентами удовлетворяет неравенству ||v, - V^(,Si)j| < bt, почти наверное относительно меры, порожденной стратегией ст. Пусть числовая последовательность Ь, такова, что <00. Тогда почти наверное выполняются равенства lim fV(S,) = max W(S), lim d(S,,S*) = 0, где S* - множе-

t-><n .SeSg /-»00

ство точек максимума функции W(S) на множестве S5, а d - расстояние от точки до множества в евклидовой метрике.

В разделе 4.6 классическая модель процесса принятия решений обобщена на ситуацию, которая весьма распространена на практике. Обобщение касается двух направлений: 1) распределенного взаимодействия и 2) отсутствия полной наблюдаемости. Наглядное описание новой схемы в простейшем случае выглядит следующим образом (рис. 3). Предполагается, что в системе имеются две «подсистемы», каждая из которых выбирает свое действие — параметр. Результирующее действие системы, является функцией от этих параметров.

наблюдение z = (u, v)

Рис. 3. Распределенное взаимодействие при неполном наблюдении.

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

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

Градиентный подход к оптимизации на марковских цепях оказался возможным благодаря конструктивной формуле для частных производных целевой функции по компонентам стратегии управления, которая переносится также на случай неполного наблюдения состояний цепи Однако для реализации алгоритма необходимо знать переходные матрицы процесса Если такой информации нет, то возникает проблема оценивания градиента по результатам наблюдения за траекторией процесса, а алгоритм превращается в адаптивную стратегию В разделе 4.7 разработаны эффективные методы оценки градиента Рассмотрим градиентную стратегию, порождающую последовательность марковских правил Обозначим через % = г е X, семейство условно независимых случайных величин, принимающих значения из интервала (0, 1), и положим = Цх^, т1 = ^М^(г) 71,(5",), где я(5"() -

тХ

предельное распределение, соответствующее марковскому правилу Отметим, что если = gt, то речь идет об оценке предельного среднего дохода Щ ,*>/), соответствующего тому марковскому правилу, которое предписывает алгоритм в момент I Если же с;( = , то оценивается предельная вероятность состояния г, соответствующая марковскому правилу С учетом того, что величины , изменяются, вообще говоря, в каждый момент, а оценить надо величину, усредненную по предельному распределению, задача построения таких оценок оказывается нетривиальной Алгоритм оценивания величины тг строится следующим образом

Определим последовательности, а,, <;, и (3, следующими формулами а, =1-(? + 1)"а, 0<а<1, С/+1 = £о=£о>

В качестве оценки величины т( рассмотрим величину ¡Л/ = С?/Рг

Теорема Пусть а - градиентная стратегия, и пусть выполнено условие II II ^ С Г", где С > 0, шах(а, *Л) <а< 1 Тогда \]Х,-т(\ = 0(ГЬ) поч-

ти наверное относительно меры, порожденной стратегий а, где Ь е (0, тт{а,а - а})

В разделе 4.8 приведены результаты вычислительного эксперимента, демонстрирующих то свойство оценок градиента, которое делает адаптивную градиентную стратегию особенно эффективной В рассмотренном примере значение аргумента (марковского правила) изменяется с постоянной скоростью, что приводит к постоянному изменению значения градиента Результаты эксперимента показывают (рис 4), что оценка градиента достаточно хорошо «отслеживает» траекторию точного значения величины Мас-

штаб по оси времени зависит от размерности объекта, которая, однако, не влияет на качественную картину графиков.

0,6

0,4

0,8

0,2

О

такты

точное значение я оценка

* относительная погрешность

Рис. 4. Оценка градиента целевой функции.

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

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

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

3. Декомпозиция процесса взаимодействия, то есть разбиение системы на подсистемы с указанием множества действий и множества наблюдений, доступных для каждой подсистемы на одном такте, а также характера взаимодействия подсистем. На рис. 3 показан пример такой распределенной структуры, в которой отдельные части системы располагают различными компонентами наблюдения и имеют свои наборы параметров, значения которых должны устанавливаться на каждом шаге. «Фактическое» воздействие на объект является результатом решений, принимаемых отдельными подсистемами.

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

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

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

6. Построение имитационно-аналитической модели включает:

• анализ априорной информации об объекте с целью определения структуры и набора параметров взаимодействия;

• создание аналитических методов, позволяющих рассчитывать параметры взаимодействия с объектом;

• написание формальной имитационной модели на специализированном языке параллельных процессов;

• разработку методов идентификации параметров модели;

• построение компьютерной программной системы.

Рис. 5. Схема обработки информации в распределенной системе взаимодействия с частично наблюдаемым объектом при неполной априорной информации; * - информационные потоки.

При выполнении пунктов 1-6 используется максимально доступная априорная информация об объекте.

7. Применение адаптивных стратегий для обработки информации и оптимизации выбора параметров, ответственных за принятие одношаговых решений.

Разработанная методология предполагает два способа реализации: прямое взаимодействие с объектом (режим on-line) и использование имитационно-аналитической модели (режим off-line). Наличие имитационной модели не является обязательным в тех случаях, когда взаимодействие с объектом происходит «достаточно быстро» и «достаточно долго». Но и в этих случаях роль имитационной модели всегда положительна, поскольку появляется возможность исследовать различные сценарии, избегая рисков непоправимых ошибок.

Реализация адаптивных алгоритмов является однотипной для каждой из подсистем, образованных в результате выполнения пункта 3. При этом обработка информации имеет двухуровневую организацию (рис. 6). На верхнем уровне накопленная к моменту t оперативная информация (то есть доступная для данной подсистемы часть наблюдений за объектом) обрабатывается с целью определения сценария, которому удовлетворяет имеющаяся предыстория. Формально это означает отображение/предыстории наблюдений глубины d, z\-d+\ = {zt, ,.... zt _d v\) в конечное множество сценариев С = {1,...,С}. Количество сценариев, отображение /,' а также глубина учитываемой предыстории d определяются на предварительных этапах 3 и 4. Каждому сценарию сеС соответствует адаптивная стратегия Ас (например, стратегия перебора или градиентная стратегия), которая представляет собой последовательность правил, отображающих предысторию доходов в конечное множество значений параметров данной подсистемы. Если на /-:м такте

Рис. 6. Двухуровневая реализация адаптивной стратегии обработки информации и принятия решений в подсистеме.

реализовался сценарий с = с,, то решающим правилом, которое определяет значение параметров подсистемы на следующем (*+1)-м такте, является правило из стратегии Ас. Таким образом, нижний уровень обработки оперативной информации представляет собой совокупность алгоритмов {Ас,сеС}, которые работают, вообще говоря, в асинхронном режиме Принимаемое на каждом такте решение определяется ровно одним из этих алгоритмов

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

Все данные относятся к периоду проведения работ (1999-2001 гг) Материалы соответствуют существовавшей на этот период концепции единой интегрированной автоматизированной системы управления для существующей и перспективной цифровой сети связи АО «Ростелеком» АСУ ЦС Указанная концепция отвечала всем современным требованиям и учитывала опыт ведущих разработчиков систем управления сетями связи

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

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

• создание упрощенной математической модели, отражающей важнейшие особенности объекта (без учета ряда специфических деталей), постановку и решение задач оптимизации;

• разработка методов идентификации матрицы тяготения по результатам сетевых измерений;

• формальный синтез объемлющей имитационной модели, включающей такие черты объекта, которые не поддаются аналитическому изучению,

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

• компьютерная реализация комплекса моделей

15 Recommendation E 412(10/92) Telephone network and ISDN Quality of service, network management and traffic engineering Network management controls -ITU, 1993

В разделе 5.2 сконцентрировано описание основных аспектов организации трафика в исследуемой системе. Приведена общая характеристика АСУ ЦС ОАО «Ростелеком» и детально перечислены основные объекты сети. Дано описание подсистемы управления вторичной телефонной сетью с указанием ее управляемых объектов. Разобраны функции блока управления трафиком (рис. 7). Анализ показал, что специфика современных телефонных сетей, определяемая как рекомендацией Е.412 Международного союза электросвязи, так и реальными параметрами телефонных сетей РФ, не позволяет использовать «напрямую» ни одну из описанных в научной литературе моделей телефонных сетей. Эти модели, как правило, используют ограничительные предположения, далеко не всегда выполняющиеся на практике; в частности, эти предположения не выполняются и в сетях, удовлетворяющих рекомендации Е.412. В связи с этим была поставлена задача создания сложной многоуровневой модели, включающей имитационную модель собственно телефонной сети с учетом всей специфики ее деятельности и алгоритмы динамического управления сетью, использующие как имитационную, так и аналитическую модель сети.

Мониторинг состояния сети

Блок обнаружения аномалий

Вычисление параметров

данных

Контроль трафика

Блок корреляции

Измерения трафика

Статистические расчеты

Управление маршрутизацией

Сбор данных из сети

ЩЩЩДРЩД!

ШГ.ШИпг

ттт

Рис. 7. Основная функциональная архитектура блока управления трафиком.

На основании сделанного анализа были решены задачи, соответствующие выполнению пунктов 1-4 общей методологии, описанной в предыдущем разделе. В частности, основная последовательность моментов принятия оперативных решений (масштаб времени) была определена как последовательность моментов появления вызовов. Глобальное «действие» на одном такте заключается в указании маршрута соединения для поступившего вызова, ли-

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

новый узел

(достигнутый узел является узлом-адресатом)

Рис 8 Последовательное установление маршрута соединения

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

Модель базируется на предположениях об экспоненциальном характере распределений и названа эрлангоеской Сеть представляется в виде множества узлов, соединенных между собой пучками каналов (линиями) Пучок каналов 1,\<1<Ь, имеет емкость п1 На узлы поступают пуассоновские потоки вызовов с параметрами Хт, т = 1,. М При поступлении вызова в сети принимается одно из двух решений либо этот вызов блокируется (получает отказ), либо ему предоставляется маршрут для соединения, продолжительность занятия которого для вызовов т-го типа имеет экспоненциальное распределение с параметром \ат Для каждой тяготеющей пары определено множест-

во из Кт возможных маршрутов соединения. Состоянием сети в момент / > О является вектор х(7) = {хтк{1), 1 < к < Кт,\ < т < М}, компонента хтк(1.) которого означает число вызовов да-го типа, которые в момент I имеют соединение по маршруту к. Множество возможных состояний сети имеет вид

Г м Кт 1

Х-\х = {хтк): £ ^а^кхтк<щ,\<]<Цхтк>Ъ,\<к<КтЛ<т<м\,

[ т=\к=\

Рис. 9. Поиск пучка для продолжения соединения вызова данного типа.

где равно 1, если линия / встречается в к-м маршруте соединения для т-го типа потока, и 0 - в ином случае. Соединение вызовов осуществляется с помощью набора векторов и = {итк, 1 < к < Кт, 1 < т < М), где компонента итк означает вероятность выбора к-то маршрута для вызова т-то типа. Множество допустимых стратегий имеет вид

Г Кт 1

где 8 > 0 - заданное число Функция относительных предельных потерь для т-то типа потоков определена как Ф^ 1пп где 2(™] (г) оз-

начает математическое ожидание суммарного числа блокировок для вызовов »г-го типа за время от 0 до / по мере Ри, и может быть также выражена в виде ф^") = Х^Р^, где Р^ - предельная вероятность того, что вызов »г-го типа получит отказ.

Теорема А) Если маршрутизация осуществляется с помощью стратегии и е Щ, 8 > 0, то предельная вероятность нахождения процесса х(() в состоянии х = {х^""^} существует и равна

= = 1Ьп Ри (*(0 = Ж) =

/->» Сх>

(м кт М кт Л

гдеС= Е (ри)» =ПП(Р-»-»)1-4 > *1=ПГК*'. Р* = ~

хеХ х т=\к=1 т=1к=\ М-ю

М

Б) Каждая точка локального минимума функции Ф(и) = Ф^ на мно-

т=1

жестве является точкой глобального минимума Множество точек минимума функции Ф(и) связно

В) Частные производные функции Ф(и) задаются формулой

Эи» я» 1

Км

где хти)=^хтк(1), соу(хт{1),хпк(1)) = Ххтхпк^х(()~ Е Е*«Л(0

к=1 аеХ хеХ хе^Г

В разделе 5 3 получен также сходный результат для распределенных стратегий маршрутизации, которые используют прием, известный в телефонии, как «откат». Для отыскания минимума функции потерь Ф(и) на множестве стратегий II5 предложено использовать градиентную стратегию, для которой доказана теорема, устанавливающая ее оптимизационные свойства.

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

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

Основным и единственным "входом" имитационной модели (если не считать структуру сети) является матрица тяготения В настоящее время не предусмотрены и не проводятся прямые измерения интенсивностей входных потоков, поэтому необходимо их реконструировать по имеющимся измерениям Эта реконструкция должна занимать сравнительно небольшое время, для того чтобы в отведенный пятнадцатиминутный интервал успеть «запустить» имитационную модель и дать возможность отработать основным алгоритмам анализа и оптимизации Так возникает дополнительная (по отношению к основным «оптимизационным» проблемам) задача идентификации параметров входных потоков по результатам косвенных измерений В разделе 5.4 изложен алгоритм, разработанный для восстановления интенсивностей входных потоков по результатам измерений Формальная постановка задачи предполагает, что (1) отказы на пучках независимы, (2) потоки, поступающие на пучки, являются пуассоновскими При этих предположениях выведены рекуррентные процедуры расчета вероятностей отказа и потоков на пучках при заданных интенсивностях входных потоков Идентификация интенсивностей входных потоков осуществляется в результате выполнения итеративной процедуры, которая минимизирует функцию невязки между измеренными и рассчитанными значениями вероятностно-временных характеристик

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

• непуассоновские входные потоки и произвольные распределения времен ожидания,

• повторные вызовы в случае блокировки,

• ненадежность каналов,

• произвольное управление соединением, в т ч возможность отката и перенаправления, постановка в очередь,

• значимая затрата времени на соединение,

• сбор информации о сети и пр

16 Ч Хоар Взаимодействующие последовательные процессы -М Мир, 1989

На рис 10 приведены некоторые объекты имитационной модели, описанные на языке параллельных процессов

СЕТЬ = ¡1 т ТРАФИК II ¿КАНАЛ II СЧЕТЧИКИ II ВРЕМЯ

теМ keK

м ТРАФИК — v = v +1, ПАУЗАо(Д), (v ВЫЗОВ || ТРАФИК)

X ВЫЗОВ = в сеть -> УЗЕЛ

X СОСТОЯНИЕ_ВЫЗОВА =

(всетъ ц = <1>, к = 0 |

в_узел —> о = к.Е, ¡J. = <ст>лц |

откат = кВ,ц =(ц')',к = (ц')о), СОСТОЯНИЕ ВЫЗОВА

X УЗЕЛ = в_узел ->

(в канал -> УЗЕЛ | блокировка ->

ПОВТОРНЫЙ ВЫЗОВ | откат н> ОТКАТ | соединение

ЗАНЯТИЕ)

X ОЖИДАНИЕ = в узел (if <т с > о С then (такт ОЖИДАНИЕ)

else ПОПЫТКА_СОЕДИНЕНИЯ)

X ОБРАБОТКАВЫЗОВА = р = R(a), case р of

1 вканал

2 блокировка

3 откат

4 соединение

end; КОНЕЦ

X ПОВТОРНЫЙ_ВЫЗОВ = (т, т v) ВЫЗОВ Д КОНЕЦ

X ОТКАТ = if а = I then ПОВТОРНЫЙ_ВЫЗОВ else (ц = (и')'. а = к.В,

УЗЕЛ)

X ЗАНЯТИЕ = ПАУЗА0(Т), изсети ->■ КОНЕЦ

КАНАЛ® ~ ({х в канал, хеХ, ¿ = хк}-> КАНАДА)) П ОТКАЗ КАНАЛА^)

КАНАД А) = ({х из канат, к = х к}КАНАЛ(Л)) JL ОТКАЗ КАНАЛА^)

ОТКАЗ_КАНАЛА(£) = сбой(к) исправен(к) КАНАЩ)

X<JM ПАУЗА*(0 = такт ->(if k<t then ПАУЗА*н(<) else КОНЕЦ)

ВРЕМЯ, = такт ВРЕМЯ«

Рис 10. Фрагмент имитационной модели на языке параллельных процессов

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

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

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

Разработано понятие обобщенной маршрутной таблицы, описание которой сводится к набору стохастических векторов р = {рв, р\, рк\ Каждый вектор р, представляет собой вероятностное распределение на некотором конечном множестве и участвует определенным образом в «прокладывании» маршрута поступившего вызова (разным типам вызовов в различных узлах соответствуют разные обобщенные маршрутные таблицы) Фактическое «решение» - маршрут - появляется в результате выбора серии "вспомогательных" действий, выбираемых независимо друг от друга с помощью компонент набора р. Такая ситуация укладывается в разработанную схему распределенного принятия решений при неполном наблюдении. Для оптимизации параметров обобщенных маршрутных таблиц используются адаптивные стратегии, построенные на основании полученных теоретических результатов

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

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

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

В Приложении содержится описание варианта программной системы, который послужил прообразом промышленной версии, переданной заказчику (ОАО Ростелеком) Кроме того, приложенный вариант явился инструментом для экспериментального исследования разработанной методологии и технологии синтеза адаптивных стратегий На рис 12 изображены фрагменты интерфейса этой программы

Начальное приближение

I

Имитация без Оценка целевой

коррекции функции

Регуляризация дополнительных воздействий на объектах

X

Выбор объектов управления

Округление

Цикл коррекции

Коней

Рис. 11. Функциональная схема блока коррекции.

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

Рис. 12. Фрагменты интерфейса программной системы моделирования и оптимизации трафика междугородной телефонной сети

Представление о возможностях программы дает следующий пример. Входные данные примерно соответствуют параметрам телефонной сети России (на период 2000 г.). Сеть содержит 115 узлов, 2390 пучков и 6683 тяготеющие пары. Исходных маршрутных таблиц - 11140. Исходная маршрутизация также соответствует реальной (и, следовательно, была настроена на этапе проектирования и в ходе эксплуатации), поэтому можно считать ее близкой к оптимальной. В эксперименте проводилась коррекция 1110 управляемых маршрутных таблиц на управляемых стациях коммутации (без применения дополнительных управляющих воздействий), что соответствует на-

стройке более 10 ООО параметров Результаты эксперимента на ПК с тактовой частотой 2,4 ГГц

• время выхода на стационарный режим - 2 мин,

• количество имитированных вызовов - около 10 млн ,

• относительное уменьшение вероятности отказов в сети после коррекции

маршрутных таблиц — 6%

Глава 6 посвящена описанию приложения разработанной методологии для синтеза информационной технологии моделирования и оптимизации системы распределенных вычислений

В основе проблематики лежит идея обеспечить коллективный доступ к вычислительным ресурсам для более эффективного их использования Новые технологии в этой области выступают, главным (но отнюдь не единственным) образом, под общим названием «системы Грид» «Грид - это программно-аппаратная инфраструктура, которая обеспечивает надежный, устойчивый, повсеместный и недорогой доступ к высокопроизводительным компьютерным ресурсам»17

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

В разделе 6.1 приведено описание модели оперативного управления распределением ресурсов на стадии непосредственного выполнения заданий, поступающих от потребителей Основными объектами модели являются заданное число распределенных вычислительных ресурсов, фиксированное число удаленных от ресурсов потребителей и потоки заданий, которые возникают у потребителей и которые состоят из случайного количества задач, упорядоченных с точки зрения очередности их выполнения (рис 13) В модели учитывается сетевой аспект тем, что при передаче пакетов от потребителей к ресурсам и обратно происходят задержки, которые зависят от объема передаваемой информации и от «расстояний» между потребителями и ресурсами Описаны механизмы возникновения заданий, отправки их на ресурсы и получения обратно, выполнения заданий на вычислительных мощностях

17 Я Фостер Что такое Грид'Три критерия http //www gndclub ru/hbrary/publication 200411-29 5830756248/publJIle

Задание состоит из упорядоченного набора задач разного объема.

задача 1 задача 2 задача л

объем V,

объем V,

объем V.

Задание выполняется путем посылки одного игм более пакетов.

задание выполнено?

Формирование пакета

[ задание"

нет

Рис. 13. Выполнение задания в модели сети Грид.

Раздел 6.2 посвящен постановке задачи и описанию адаптивных алгоритмов обработки информации для оперативного распределения ресурсов при неполной информации. Оперативные решения заключаются, прежде всего, в назначении ресурсов для задач, поступающих от разных пользователей. Кроме того, особенности, процесса обслуживания, в частности, возможность непредвиденного возвращения невыполненных задач, требуют оптимизировать объемы посылаемых пакетов задач. Оба типа решений представляются как выбор из конечного множества вариантов, и задача сводится к нахождению оптимальных значений распределений на этих множествах для различных пользователей и разных значений наблюдаемой части системы. Формально задача укладывается в схему частично наблюдаемой марковской последовательности и адаптивного распределенного принятия решений, которая была изучена в главе 3. В качестве основного одношагового показателя качества функционирования системы (одношагового дохода) выступает объем выполненных задач, возвращенных пользователю на данном такте. Соответствующим критерием качества решений является производительность, то есть отношение количества выполненных заданий к промежутку времени функционирования системы. Дополнительно рассмотрены одношаговые финансовые затраты, а также количество задач, потерянных (не обслуженных) на одном шаге. В этом случае получаются целевые функции, обозначающие соответственно (предельные средние) затраты и (предельные средние) отказы. Рассмотрены два основных варианта принятия решений: централизованный, когда цель заключается в том, чтобы повысить среднюю производительность всей системы, и децентрализованный, когда каждый потребитель пытается увеличить собственную производительность. Адаптивные алгоритмы представляют собой рекуррентные последовательности, сконструированные в главе 3, в которых вероятностные распределения выбора тех или иных

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

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

0,64 -I-1-1-1-1-1-1-1-1-1-1-

1234567В9 10 11 время, 1=100000 тактов

-♦—производительность адаптивной стратегии с момента нэнала моделирования

---производительность адаптивной стратегииза последние

100000 тактов —«— максимально возможная производительность

Рис. 14. Производительность адаптивной стратегии в сравнении с оптимальной стратегией (стационарная среда).

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

производительность

Рис. 15. Производительность адаптивной стратегии (I) в сравнении с эмпирической стратегией (II) — периодическая среда.

В результате проведенных экспериментов установлено, что адаптивные алгоритмы

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

• действуют результативнее, чем эвристические стратегии, в примерах, когда нет способа заранее и точно указать оптимальную стратегию;

• оказывают существенное положительное влияние на показатели качества, если их использовать для управления объемом посылаемых на обслуживание пакетов задач;

• являются восприимчивыми к выбору критерия качества;

• эффективны в случаях централизованного и децентрализованного (игрового) поведения участников.

РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

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

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

1.1. Построена общая модель взаимодействия субъекта с частично наблюдаемым, априори неизвестным объектом в виде управляемой случайной последовательности общего вида. Формализованы понятия объекта и стратегия (субъекта).

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

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

1 3 Предложена конструкция адаптивной стратегии, основанной на идее «средних времен» и на переборе счетного множества вариантов (стратегия перебора) Стратегия перебора не использует априорную информацию об объекте.

1 4 Доказано, что стратегия перебора способна взаимодействовать с произвольным, априори неизвестным объектом не хуже, чем (неизвестная) наилучшая стратегия из произвольного заданного счетного множества стратегий

1 5 Доказано, что стратегия перебора (на счетном множестве детерминированных однородных правил конечной глубины) обеспечивает максимально возможный предельный средний доход 1) для произвольного регенерируемого объекта, 2) для произвольной однородной конечной управляемой связной марковской цепи

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

2 Разработаны методы адаптивной обработки информации для марковского процесса принятия решений

2 1 Получен ряд свойств функции предельного среднего дохода в марковском процессе принятия решений со счетным множеством состояний

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

2 3 Предложена градиентная адаптивная стратегия для марковского процесса принятия решений с конечным множеством состояний и доказаны ее оптимизационные свойства

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

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

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

4.1 Решена задача оперативного управления трафиком в телекоммуникационной сети с коммутацией каналов Разработана совокупность моделей и

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

4.1 1. Построена эрланговская модель управляемой сети с коммутацией каналов, в ее рамках поставлена и решена задача минимизации средних потерь в сети

4 12 Разработаны модель и технология восстановления матрицы тяготения по результатам сетеметрии 4 13 Построена имитационная модель трафика в сети связи с коммутацией каналов, написанная на языке параллельных процессов 4 14 Дана трактовка модели управляемой сети с коммутацией каналов как управляемой марковской цепи с доходами В этой трактовке введено и формализовано понятие обобщенных маршрутных таблиц, а также формализовано применяемое в практике телефонных сетей понятие «управляющих воздействий» Разработаны технологии адаптивной коррекции маршрутных таблиц и дополнительных решающих правил На базе полученных результатов создана программная система, реализованная в блоке управления трафиком междугородной телефонной сети

4 2 Методология синтеза информационных адаптивных технологий и их применения в режиме оГ£-1те использованы в ходе проведения ряда ОКР для нахождения оптимальных системотехнических и программно-аппаратных решений при разработке АСУ и аппаратуры для инфотелекоммуникацион-ных систем

4 3 Создана информационная технология моделирования системы распределенных вычислений

4 3 1 Построена информационная модель коллективного взаимодействия взаимно удаленных потребителей и распределенных вычислительных ресурсов.

4 3 2 Поставлена и решена задача адаптивного оперативного распределения ресурсов при неполной информации. 4 3 3. Экспериментально исследованы свойства адаптивных алгоритмов в модели системы распределенных вычислений

Содержание диссертации изложено в следующих публикациях

1. Коновалов М. Г. Об адаптивном управлении некоторыми классами марковских цепей // Доклады АН СССР. - Т. 233, № 5. -1977. - С. 780-783.

2 Коновалов М Г Адаптивное управление неоднородными марковскими цепями // В сб «Вопросы кибернетики Адаптивные системы управления» - М Наука -1977

3. Коновалов М. Г. Адаптивное управление периодическими процессами с независимыми значениями // Известия АН СССР. Техническая кибернетика, № 1. -1979. - С.138-144.

4 Гессель М, Срагович В Г, Коновалов М Г Методы адаптивного управления конечными марковскими цепями и функционалами на них // В сб «Вопросы кибернетики Адаптивное управление» -М Наука -1979

5. Коновалов М. Г. Об адаптивной маршрутизации в сети связи с коммутацией каналов // Известия АН СССР. Техническая кибернетика, № 3. - 1984. -С. 152-155.

6. Коновалов М. Г. Адаптивное управление конечными автоматами с ненаблюдаемыми состояниями // Доклады АН СССР. - Т. 291, № 1. -1986. - С. 59-62.

7 Коновалов М Г Метод перебора в адаптивном управлении случайными процессами с дискретным временем - М ВЦ АН СССР - 1989 - 25 с

8 Коновалов М Г Об управлении в сетях с коммутацией пакетов - М ВЦ АН СССР -1989 -40 с

9. Коновалов М. Г. Опыт моделирования сети передачи данных на языке параллельных процессов П Математическое моделирование. - Т. 5, № 2. -1993.-С. 82-93.

10 Коновалов М Г Адаптивная маршрутизация в сети связи с коммутацией каналов // В сб «Всесоюзная конференция «Теория адаптивных систем и ее применение» - 1983

11 Коновалов М Г Адаптивное управление конечными частично наблюдаемыми марковскими цепями // Четвертая международная вильнюсская конференция по теории вероятностей и математической статистике - 1985

12 Коновалов М Г Параллельные процессы и имитационное моделирование сетей связи // В сб XLVII научная сессия, посвященная Дню Радио - М 1992

13 Коновалов М Г Адаптивный алгоритм маршрутизации для сетей передачи данных с коммутацией пакетов // В сб XLVII научная сессия, посвященная дню Радио -М 1992

14 Антонов С В , Коновалов М Г, Соколов И А, Супрун А П, Шоргин С Я Программные средства моделирования работы сетей с ретрансляцией кадров Свидетельство об официальной регистрации программы для ЭВМ № 980363, РосАПО, 1998

15. Антонов С В , Коновалов М Г, Соколов И. А, Шоргин С Я Математические методы и программные средства для анализа и проектирования сетей, использующих технологию ретрансляции кадров // Международная конференция по информационным сетям и системам ICINAS-98 Труды - С -Петербург ЛОНИИС, ГУТ им Бонч-Бруевича,РНТОРЭС им Попова, 1998 -С 132-141

16 Антонов С В , Захаров В Н, Коновалов М Г , Шоргин С Я Комплексная модель цифровой телефонной сети и алгоритмы динамического управления // Системы и средства информатики Выл 11 -М Наука,2001 -С 68-77

17 Коновалов М Г Управляемые марковские последовательности и оптимизация маршрутных таблиц в сетях связи с коммутацией каналов // В сб «Системы и средства информатики», вып 11 -М Наука, 2001 -С 78-93

18 Konovalov М G Management controls m telephone networks // 3 Московская международная конференция по исследованию операций (ORM2001) - Москва, 4-6апреля2001 -С 57-58

19. Шоргин С. Я., Соколов И. А., Антонов С. В., Захаров В. Н., Коновалов М. Г. Проблемы разработки математических методов и программных средств адаптивной оптимизации распределения потоков в многоуровневой сети коммутации каналов // Обозрение прикладной и промышленной математики. - Т. 9, Вып. 1. - 2002. - С. 252-253. (Третий Всероссийский Симпозиум по прикладной и промышленной математике (весенняя сессия).

20. Соколов И. А., Антонов С. В., Захаров В. Н., Коновалов М. Г, Шоргин С. Я. Разработка математических методов оптимизации распределения потоков в многоуровневой сети коммутации каналов // Обозрение прикладной и промышленной математики. - Т. 9, Вып. 2. - 2002. - С. 452-453 . (Третий Всероссийский Симпозиум по прикладной и промышленной математике (осенняя сессия).

21 Коновалов М Г Восстановление матрицы тяготения по результатам измерений в сети // В сб «Системы и средства информатики Спец выпуск Математическое и алгоритмическое обеспечение информационно-телекоммуникационных систем» — М Изд-во ИЛИ РАН, 2002 - С 100-111

22 Соколов И А, Антонов С В , Захаров В Н, Коновалов М Г, Шоргин С Я Проблематика моделирования вторичных сетей телефонной связи // В сб Труды конференции «Информационные технологии в науке, образовании, телекоммуникации, бизнесе» - Ялта-Гурзуф, 2002 -С 125

23 Коновалов М Г Экспериментальное сравнение некоторых алгоритмов маршрутизации в сетях с коммутацией каналов на примере сети Клоза // Системы и средства информатики Вып 13 -2003 -С. 106-121

24. Антонов С. В., Захаров В. Н., Коновалов М. Г., Соколов И. А., Шоргин С. Я. Информационные технологии моделирования и динамического управления в многоуровневых сетях коммутации каналов // Наукоемкие технологии, №4.-2003.-С. 70-78.

25 Антонов С В, Захаров В Н, Коновалов М Г Имитационная модель в комплексной системе моделирования многоуровневой сети коммутации каналов // Труды Международных научно-технических конференций «Интеллектуальные системы» (IEEE AIS'03) и «Интеллектуальные САПР» (СФВ-2003) - М Изд-во физико-магематическойлитературы,2003,Т 1 -С 517-522.

26 Antonov S V , Zakharov V N , Konovalov М G, Sokolov I. A, Shorgm S Ya Algorithms of routing and control actions optimization in multilevel networks of circuit switching // Seminar on Stability Problems for Stochastic Models Universidad Pública de Navarra Pamplona 2003 P 81

27 Соколов И А, Антонов С В , Захаров В Н, Коновалов М Г, Печинкин А В , Шоргин С Я Программные средства моделирования многоуровневой сети с коммутацией каналов и оптимизации распределений потоков Свидетельство об официальной регистрации программы для ЭВМ № 2004611520, 21 июня 2004 г (Федеральная служба по интеллектуальной собственности, патентам и товарным знакам)

28 Соколов И А, Антонов С В , Захаров В Н, Коновалов М Г, Шоргин С Я Алгоритмическое обеспечение моделирования многоуровневой сети коммутации

каналов и оптимизации маршрутных таблиц // 8-я Международная конференция «Проблемы функционирования информационных сетей» Материалы конференции МНПК «Связь-2004», Иссык-Куль, 22-29 августа 2004 г - С 277-283

29 Соколов И А, Антонов С В, Захаров В H, Коновалов M Г, Печинкин А В , Шоргин С Я Алгоритмы и программы моделирования и функционирования и процессов управления в телефонных сетях // Материалы международной научно-практической конференции «Информационные технологии и информационная безопасность в науке, технике и образовании ИНФОТЕХ-2004» Севастополь, 2025 сентября 2004 г С 116-117

30. Коновалов М. Г. Некоторые свойства функции предельного среднего дохода в задаче управления марковскими цепями // Вестник РУДН, серия Прикладная и компьютерная математика. - Т. 3, № 1. - 2004. - С. 61-77.

31 Коновалов M Г Об оценках градиента функции предельного среднего дохода в марковском процессе принятия решений // В сб «Системы и средства информатики», вып 14 - M Наука, 2004 -С 68-85

32 Коновалов M Г Градиентный подход к управлению конечными марковскими цепями и его применение // В сб «Проблемы и методы информатики II Научная сессия Института проблем информатики Российской академии наук Москва, 18-22 апреля 2005 г » -М Наука, 2005 - С 99-101

33 Konovalov M, Shorgin S , Saveno S Problème of GRID systems modehng -Transactions of XXV International Seminar on Stability Problems for Stochastic Models Maion (Salerno), Italy, September 20-24,2005 -P 309

34 Коновалов M Г Адаптивное управление процессом размещения заданий в модели коллективного использования распределенных вычислительных ресурсов // В сб Тезисы докладов 2-й международной конференции «Распределенные вычисления и Грид-технологии в науке и образовании» - Дубна, 26-30 июня 2006 г -С 76-77

35 Антонов С В , Душин Ю А, Коновалов M Г, Шоргин С Я Разработка математических моделей и методов распределения заданий в системе распределенных вычислений // "Системы и средства информатики" Выпуск 16 Москва Наука 2006 г - С 32-46

36. Gaeta M, Konovalov M, Shorgin S. Development of mathematical models and methods of task distribution in distributed Computing system // Reliability Theory & Applications, Electronic Journal, ISSN 1932-2321 - Vol 1, No 4 - 2006 -http //www gnedenko-forum org/Journal/mdex htm

37 Коновалова И H, Коновалов M Г Модель и алгоритмы адаптивного управления для системы распределенных вычислительных ресурсов // Международный симпозиум «Информационные технологии и общество», 24 апреля - 01 мая 2007, Тель-Авив, Израиль Материалы симпозиума Москва, 2007 - С 76-78

38 Коновалов M Г Методы адаптивной обработки информации и их приложения - M ИЛИ РАН, 2007 - 212с - ISBN 978-5-902030-59-9

39 Коновалов M Г Моделирование системы коллективного использования распределенных вычислительных ресурсов Свидетельство о государственной регистрации программы для ЭВМ № 2008610082, 9 января 2008 г (Федеральная служба по интеллектуальной собственности, патентам и товарным знакам )

40 Коновалов M Г, Чаплыгин В В Расчет матрицы тяготения по результатам измерений в сети с коммутацией каналов Свидетельство о государственной регистрации программы для ЭВМ № 2008610083, 9 января 2008 г (Федеральная служба по интеллектуальной собственности, патентам и товарным знакам )

Подписано в печать 29 02 2008 г Печать трафаретная

Заказ № 129 Тираж 110экз

Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш, 36 (495) 975-78-56, (499) 788-78-56 www autoreferat га

ВВЕДЕНИЕ.

1. АНАЛИЗ ОБЛАСТЕЙ ПРИЛОЖЕНИЯ АДАПТИВНЫХ МЕТОДОВ ОБРАБОТКИ ИНФОРМАЦИИ.

1.1. инфотелекоммуниклционные системы.

1.1.1. Маршрутизация.

1.1.1.1. СЕТИ С КОММУТАЦИЕЙ КАНАЛОВ.

1.1.1.2. ШИРОКОПОЛОС11ЫЕ СЕТИ.

1.1.2. Управление потоками.

1.1.2.1. ШИРОКОПОЛОСНЫЕ ИНТЕГРИРОВАННЫЕ СЕТИ.

1.1.2.2. БЕСПРОВОДНЫЕ СОТОВЫЕ СЕТИ.

1.1.2.3. БЕСПРОВОДНЫЕ СПУТНИКОВЫЕ СЕТИ.

1.1.3. Разное.

1.1.3.1. РАСПРЕДЕЛЕННАЯ ВЫЧИСЛИТЕЛЬНАЯ СРЕДА.

1.1.3.2. ОПТИМИЗАЦИЯ СТРАТЕГИИ КЭШИРОВАНИЯ.

1.1.3.3. «АДАПТИВНЫЕ САЙТЫ».

1.1.3.4. КОНТРОЛЬ КАЧЕСТВА.

1.1.3.5. ОПТИМИЗАЦИЯ ВОСПРОИЗВЕДЕНИЯ ВИДЕОПАКЕТОВ.

1.1.3.6. АНАЛИЗ ПРОТОКОЛА IEEE 1394.

1.1.3.7. ПОДДЕРЖКА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ.

1.2. Производственные системы.

1.2.1. Технологические процессы.

1.2.1.1. ПРОИЗВОДСТВО И СБЫТ.

1.2.1.2. ПЛАНИРОВАНИЕ И ДИСПЕТЧЕРИЗАЦИЯ.

1.2.1.3. БАЛАНСИРОВКА ТЕХНОЛОГИЧЕСКИХ ЛИНИЙ.

1.2.1.4. СБОРОЧНЫЙ ПРОЦЕСС.

1.2.1.5. ГИБКОЕ АВТОМАТИЗИРОВАННОЕ ПРОИЗВОДСТВО.

1.2.1.6. ДРУГИЕ ПРИЛОЖЕНИЯ.

1.2.2. Техническое обслуживание.

1.2.3. Управление запасами.

1.3. Моделирование поведения, искусственный интеллект, роботы.

1.3.1. Искусственные модели.

1.3.2. Физические модели и прототипы реальных устройств.

1.3.2.1. ОБУЧЕНИЕ РОБОТА ХОДЬБЕ.

1.3.2.2. РОБОТЫ НА ПРОИЗВОДСТВЕ.

1.3.2.3. КОСМИЧЕСКИЙ ВЕЗДЕХОД.

1.3.2.4. ФУТБОЛ РОБОТОВ.

1.4. Разные приложения.

1.4.1. Теория расписаний и календарное планирование.

1.4.2. Системы массового обслуживания.

1.4.3. Другие приложения.

1.4.3.1. ПРОДАЖА БИЛЕТОВ АВИАКОМПАНИЯМИ. 1.4.3.2. РЕГУЛИРОВАНИЕ ПОПУЛЯЦИЙ.

1.4.3.3. ВЫБОР НАИЛУЧШЕГО АЛГОРИТМА.

1.4.3.4. ИГРЫ.

1.4.3.5. ДЕНЬГИ, ФИНАНСЫ.

1.4.3.6. СТАБИЛИЗАЦИЯ ЭНЕРГОСИСТЕМЫ.

1.4.3.7. ВОЕННЫЕ ПРИЛОЖЕНИЯ.

1.4.3.8. ПОИСК ЗАПИСЕЙ В ФАЙЛЕ.

1.4.3.9. РАСПОЗНАВАНИЕ ИЗОБРАЖЕНИЙ.

1.4.3.10. МЕХАНИЧЕСКИЕ СИСТЕМЫ.

2. ОСНОВНЫЕ МОДЕЛИ И СТРАТЕГИИ ОБРАБОТКИ ИНФОРМАЦИИ ДЛЯ ЧАСТИЧНО НАБЛЮДАЕМЫХ СИСТЕМ.

2.1. Основные определения.

2.1.1. Общая модель.

2.1.2. Стратегии.

2.1.3. Объекты.

2.1.4. Примеры.

2.2. Однородные стратегии конечной глубины.

3. АДАПТИВНАЯ СТРАТЕГИЯ ПЕРЕБОРА.

3.1. Основные определения.

3.2. Общая теорема.

3.3. Стратегия перебора для регенерируемых объектов.

3.4. Применение к частично наблюдаемым марковским цепям.

3.5. Применение к частично наблюдаемым графам.

4. ГРАДИЕНТНАЯ ОПТИМИЗАЦИЯ ПРЕДЕЛЬНОГО СРЕДНЕГО ДОХОДА НА МАРКОВСКИХ ЦЕПЯХ.

4.1. Определения, предположения и свойства.

4.2. Основная теорема.

4.3. Дополнительные свойства функции предельного дохода.

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

4.5. Градиентный алгоритм оптимизации функции предельного среднего дохода.

4.6. Распределенное принятие решений в условиях неполного наблюдения

4.7. Методы оценки градиента целевой функции.

4.7.1. Оценка по одному наблюдению.

4.7.2. Оценки «с остановками».

4.7.3. Оценки «сзабыванием».

4.7.4. Численный пример.

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

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

5.2. Основные аспекты организации трафика в цифровой сети с коммутацией каналов.

5.2.1. Общее описание проблемы.

5.2.2. Характеристика АСУ ЦС ОАО «Ростелеком».

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

5.2.4. Блок управления трафиком.

5.2.5. Объекты сети.

5.2.6. Требования к средствам управления качеством.

5.2.7. Команды управления трафиком.

5.2.8. Маршрутизация в блоке управления трафиком.

5.3. Эрланговская модель сети с коммутацией каналов.

5.3.1. Общие свойства модели.

5.3.2. Распределенный выбор маршрутов соединений.

5.3.3. Минимизация отказов.

5.4. Идентификация матрицы тяготения по результатам сетеметрии.

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

5.4.2. Общая схема алгоритма идентификации матрицы тяготения.

5.4.3. Расчет градиента целевой функции.

5.4.4. Численный пример.

5.5. Имитационная модель сети с коммутацией каналов.

5.5.1. Описание имитационной модели.

5.5.2. Основные понятия теории взаимодействующих процессов.

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

5.6.1. Параметризация маршрутных таблиц.

5.6.2. Параметризация дополнительных управляющих воздействий.

5.7. Компьютерная реализация комплекса моделей управляемой цифровой сети с коммутацией каналов.

5.7.1. Структура данных.

5.7.2. Начальные данные.

5.7.3. Управляющие воздействия.

5.7.4. Основные процедуры блока имитации.

5.7.4.1. ФУНКЦИОНАЛЬНАЯ АРХИТЕКТУРА И СЦЕНАРИЙ РАБОТЫ БЛОКА ИМИТАЦИИ.

5.7.5.2. МОДУЛ bINIT.

5.7.5.3. МОДУЛЬ CALi.

5.7.5.4. МОДУЛИ SEND(p) И WR.

6. АДАПТИВНОЕ ПРИНЯТИЕ РЕШЕНИЙ В МОДЕЛИ РАСПРЕДЕЛЕННОЙ ВЫЧИСЛИТЕЛЬНОЙ СРЕДЫ.

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

6.1.1. Общее описание модели.

6.1.2. Формализация модели распределения ресурсов.

6.1.2.1. ПАРАМЕТРЫ МОДЕЛИ.

6.1.2.2. СОСТОЯНИЯ СИСТЕМЫ.

6.1.2.3. ОСНОВНЫЕ ПРОЦЕДУРЫ.

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

6.2.1. Выбор размера пакетов заданий и назначение ресурсов.

6.2.2. Конструкция адаптивной стратегии.

6.3. Экспериментальное исследование свойств адаптивных алгоритмов в модели системы распределенных вычислений.

6.3.1. Пример: один ресурс, один потребитель.

6.3.2. Пример: 10 потребителей, 5ресурсов.

6.3.3. Пример: неоднородный случай.

Актуальность темы исследования

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

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

Основополагающие идеи теории адаптации были заложены в 50-х годах прошлого века [177, 176], а становление теории и ее развитие до конца 80-х годов проходило во многом благодаря усилиям отечественных исследователей [190]. С начала 90-х годов и по настоящее время адаптивное направление переживает большой подъем, а число публикаций исчисляется многими сотнями. Выделилась и получила широкое распространение ветвь этого направления, которая обозначается плохо переводимым на русский язык словосочетанием «reinforcement learning» - «активное обучение». Этот раздел теории в значительной мере ориентирован на приложения и тесно связан с такой областью науки, как искусственный интеллект [193].

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

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

Центральное место в теории адаптации занимает проблематика частично наблюдаемого марковского процесса принятия решений. Традиционный подход, основанный на динамическом программировании, дал результаты, применимые в адаптивном варианте [60, 81]. В то же время, как подчеркивают многие авторы и о чем свидетельствует большой поток публикаций, необходим дальнейший прогресс в этой области, имеющей неоспоримое прикладное значение. «Марковские процессы являются в настоящее время математическим фундаментом для многих работ в области активного обучения (reinforcement learning), теории принятия решений, поиска информации, распознавания речи, активного зрительного восприятия, навигации роботов» [159].

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

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

Исследования, излагаемые в диссертационной работе, направлены, в частности, на преодоление трудностей, связанных с практическим воплощением теории. Особое внимание в этой связи уделяется изучению градиентного подхода в марковском процессе принятия решений, который появился позже других методов. Первые из известных нам работ этого направления (например, [104]) скорее «обозначали желание» двигаться по градиенту, чтобы оптимизировать целевую функцию, и не дали конструктивных алгоритмов. Основная формула для градиента была, видимо, впервые, опубликована в [21], и там же был указан путь ее использования, в том числе в условиях неполного наблюдения и распределенного характера взаимодействия. Начиная примерно с середины 90-х годов, за рубежом появилось много публикаций и много глубоких результатов, связанных с градиентным подходом [73, 160]. Исследования, которые излагаются в диссертационной работе, проводились независимо.

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

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

Цель и задачи исследования

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

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

Построение стратегии базируется на априорной модели объекта, которая в свою очередь включает в себя априорную информацию об объекте. Легко можно представить ситуацию, когда такая информация не полна или даже вовсе отсутствует (пресловутый «черный ящик»).

Имеются еще обстоятельства, которые фактически могут быть приравнены к отсутствию априорной информации. В некоторых случаях субъект имеет достаточно сведений для составления адекватной модели объекта, но не может воспользоваться этим, потому что, попросту говоря, не знает, как это сделать. (Шахматная игра, как процесс чередования позиций и ходов, полностью определяется небольшим количеством правил, однако до сих пор не удалось создать беспроигрышную стратегию игры, хотя на этом пути многое сделано.) Кроме того, иногда, и даже 9 довольно часто, проблема использования модели связана не только с «неумением», а и с тем, что теоретический рецепт нельзя воплотить на практике, например, из-за большой размерности.

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

Умение субъекта пользоваться для достижения цели информацией, поступающей в процессе функционирования, связано с такими понятиями, как «самоорганизация», «приспособление», «адаптация». Поэтому мы говорим об адаптивных стратегиях обработки информации.

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

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

При проведении исследований были поставлены следующие основные задачи.

1. Разработка теоретических основ синтеза адаптивных стратегий в общих моделях частично наблюдаемых объектов.

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

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

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

Методика исследования.

Методика и средства исследования различны для перечисленных выше задач.

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

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

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

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

- имитационное моделирование на основе аппарата теории взаимодействующих процессов;

- параметризация маршрутных таблиц и дополнительных управляющих воздействий;

- адаптивные алгоритмы, разработанные при решении задач 1 и 2;

- компьютерная реализация моделей с использованием объектно-ориентированного языка Delphi.

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

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

Краткое содержание работы

ЗАКЛЮЧЕНИЕ. РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

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

1.1. Построена общая модель взаимодействия субъекта с частично наблюдаемым, априори неизвестным объектом в виде управляемой случайной последовательности общего вида. Формализованы понятия объекта и стратегии (субъекта).

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

1.3. Предложена конструкция адаптивной стратегии, основанной на идее «средних времен» и на переборе счетного множества вариантов (стратегия перебора). Стратегия перебора не использует априорную информацию об объекте.

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

1.5. Доказано, что стратегия перебора (на счетном множестве детерминированных однородных правил конечной глубины) обеспечивает максимально возможный предельный средний доход 1) для произвольного регенерируемого объекта, 2) для произвольной однородной конечной управляемой связной марковской цепи.

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

2. Результаты в области адаптивной обработки информации в марковском процессе принятия решений.

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

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

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

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

3. Результаты в области практических приложений

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

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

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

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

3.4.1. Построена эрланговская модель управляемой сети с коммутацией каналов, в ее рамках поставлена и решена задача минимизации средних потерь в сети.

3.4.2. Разработаны модель и технология восстановления матрицы тяготения по результатам сетеметрии.

3.4.3. Построена имитационная модель трафика в сети связи с коммутацией каналов, написанная на языке параллельных процессов.

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

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

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

3.5. Создана информационная технология моделирования системы распределенных вычислений.

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

3.5.2. Поставлена и решена задача адаптивного оперативного распределения ресурсов при неполной информации.

3.5.3. Экспериментально исследованы свойства адаптивных алгоритмов в модели системы распределенных вычислений.

1. Антонов С. В., Душин Ю. А., Коновалов М. Г., Шоргин С. Я. Разработка математических моделей и методов распределения заданий в системе распределённых вычислений // "Системы и средства информатики". Выпуск 16. Москва. Наука. 2006 г. С. 32-46.

2. Антонов С. В., Захаров В. Н., Коновалов М. Г., Соколов И. А., Шоргин С. Я. Информационные технологии моделирования и динамического управления в многоуровневых сетях коммутации каналов // Наукоемкие технологии, № 4. 2003. - С.70-78.

3. Антонов С. В., Захаров В. Н., Коновалов М. Г., Шоргин С. Я. Комплексная модель цифровой телефонной сети и алгоритмы динамического управления // Системы и средства информатики. Вып. 11. М.: Наука, 2001. - С. 68-77.

4. Антонов С. В., Коновалов М. Г., Соколов И. А., Супрун А. П., Шоргин С. Я. Программные средства моделирования работы сетей с ретрансляцией кадров. Свидетельство об официальной регистрации программы для ЭВМ № 980363, РосАПО, 1998.

5. Байхельт Ф., Франкен П. Надежность и техническое обслуживание. М.: Радио и связь, 1988.

6. Гихман И. И., Скороход А. В. Теория случайных процессов. Т. 1. -М.: Наука, 1971.

7. Душин Ю. А. Модель оценки стоимости гетерогенных ресурсов в Грид // Системы и средства информатики: Спец. вып. Математические модели в информационных технологиях. М.: ИПИ РАН. - 2006. - С. 163-172.

8. Карманов В. Г. Математическое программирование. М.: Наука, 1975.

9. Кемени Д., Снелл Дж., Кнепп А. Счетные цепи Маркова. М.: Наука, 1987.

10. Коваленко В., Коваленко Е., Корягин Д. и др. Управление заданиями в распределенной вычислительной среде // Открытые системы. 2001. № 5-6. С. 22-28.

11. Коваленко В., Корягин Д. Эволюция и проблемы Grid // Открытые системы. 2003. №1. С. 27-33.

12. Коновалов М. Г. Об адаптивном управлении некоторыми классами марковских цепей // Доклады АН СССР. Т. 233, № 5. - 1977. - С. 780-783.

13. Коновалов М.Г. Адаптивное управление периодическими процессами с независимыми значениями // Известия АН СССР. Техническая кибернетика, № 1. 1979. - С. 138-144.

14. Коновалов М. Г. Адаптивная маршрутизация в сети связи с коммутацией каналов // В сб. «Всесоюзная конференция «Теория адаптивных систем и ее применение». 1983.

15. Коновалов М. Г. Об адаптивной маршрутизации в сети связи с коммутацией каналов // Известия АН СССР. Техническая кибернетика, № 3. 1984. - С. 152-155.

16. Коновалов М.Г. Адаптивное управление конечными автоматами с ненаблюдаемыми состояниями // Доклады АН СССР. Т. 291, № 1. - 1986. - С. 59-62.

17. Коновалов М.Г. Метод перебора в адаптивном управлении случайными процессами с дискретным временем. М.: ВЦ АН СССР. — 1989. - 25 с.

18. Коновалов М. Г. Об управлении в сетях с коммутацией пакетов. М.: ВЦ АН СССР.- 1989.-40 с.

19. Коновалов М. Г. Параллельные процессы и имитационное моделирование сетей связи // В сб.: XLVII научная сессия, посвященная Дню Радио. М. 1992.

20. Коновалов М. Г. Адаптивный алгоритм маршрутизации для сетей передачи данных с коммутацией пакетов // В сб.: XLVII научная сессия, посвященная дню Радио. М. 1992.

21. Коновалов М. Г. Опыт моделирования сети передачи данных на языке параллельных процессов // Математическое моделирование. Т. 5, № 2. - 1993. - С. 82-93.

22. Коновалов М. Г. Управляемые марковские последовательности и оптимизация маршрутных таблиц в сетях связи с коммутацией каналов // В сб. «Системы и средства информатики», вып. 11. М.: Наука, 2001 - С. 78-93.

23. Коновалов М. Г. Экспериментальное сравнение некоторых алгоритмов маршрутизации в сетях с коммутацией каналов на примере сети Клоза // Системы и средства информатики. Вып. 13.-2003.-С. 106-121.

24. Коновалов М. Г. Некоторые свойства функции предельного среднего дохода в задаче управления марковскими цепями // Вестник РУДН, серия Прикладная и компьютерная математика. Т. 3, № 1. - 2004. - С. 61-77.

25. Коновалов М. Г. Об оценках градиента функции предельного среднего дохода в марковском процессе принятия решений // В сб. «Системы и средства информатики», вып. 14. М.: Наука, 2004. - С. 68-85.

26. Неве Ж. Математические основы теории вероятностей. М.: Мир, 1969.

27. Попов М. // СЮ, N 2. 2005.

28. Прохоров Ю. В., Розанов Ю. А. Теория вероятностей. -М.: Наука, 1973.

29. Пугачев В. С., Синицын И. Н. Теория стохастических систем. М.: Изд. Логос.2004.

30. Топорков В. В. Модели распределенных вычислений. М.: Физматлит, 2004.

31. Хоар Ч. Взаимодействующие последовательные процессы. М.: Мир, 1989.

32. Экспериментальный GRlD-сегмент МГУ им. М.В. Ломоносова: Руководство для пользователей, http://www.parallel.ru/info/education/msugrid-intro.doc.

33. Akar N., Sahin С. Reinforcement learning as a means of dynamic aggregate QoS provisioning // LNCS 2698. 2003. - P. 100-114.

34. Ash G. R., Cardwell R. H., Murray R. Design and optimization of networks with dynamic routing // Bell System Technical Journal, 60. -1981. P. 1787-1820.

35. Barto A. G., Mahadevan S. Recent advances in hierarchical reinforcement learning // Discrete event dynamic systems: theory and applications, 13. — 2003. — 13 — P. 343-379.

36. Bartolini N. Handoff and optimal channel assignment in wireless networks // Mobile Networks and Applications, 6. 2001. - P. 511-524.

37. Beetz M. Chapter 5: Learning structured reactive navigation plans // Lecture Notes in Computer Science, 2554. 2002. - P. 125-146.

38. Belker Т., Beetz M. Learning to execute navigation plans // Lecture Notes in Computer Science, 2174.-2001.

39. Belker Т., Beetz M., Cremers A. B. Learning action models for the improved execution of navigation plans // Robotics and Autonomous Systems, 38. 2002. - P. 137-148.

40. Berenguer C., Chu C., Grail A. Inspection and maintenance planning: an application of semi-Markov decision processes // Journal of Intelligent Manufacturing, 8. 1997. - P. 467— 476.

41. Berman F, High-performance scheduling // The Grid: blueprint for a new computing infrastructure. Eds. I. Foster, C. Kesselman. San Francisco: Morgan Kaufmann. 1999. - P. 279307.

42. Berman F., Wolski R. Scheduling from the perspective of the application // Proc. of Symposium on High Performance Computing. 1996. -http://grail.sdsc.edu.

43. Berman 0„ Kim E. Dynamic order replenishment policy in internet-based supply chains // Math Meth Oper Res, 53. 2001. - P. 371-390.

44. Berman O., Sapna K. P. Optimal control of service for facilities holding inventory // Computers & Operations Research, 28. 2001. - P. 429^141.

45. Bertsekas D. P. Dynamic programming and optimal control, V. 1,2. Belmont: Athena Scientific, 2001.

46. Bianchi, R. Costa A. Comparing distributed reinforcement learning approaches to learn agent coordination // LNAI, 2527. 2002. - P. 575-584.

47. Blair C., Monahan G. E. Optimal sequential file search: a reduced-state dynamic programming approach // European Journal of Operational Research, 86. 1995. - P. 358-365.

48. Braun T. D., Siegel H. J., Beck N. Comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems // Parallel and Distributed Computing. 2001.

49. Brouns G. A. J. F., Van der Wal J. Optimal threshold policies in a workload model with a variable number of service phases per job // Math. Meth. Oper. Res., 53. 2003. - P, 483-501.

50. Bruns P. Optimality of randomized strategies in a Markovian replacement model // Math Meth Oper Res, 56. 2002. - P. 481-499.

51. Cai K.-Y. Optimal software testing and adaptive software testing in the context of software cybernetics // Information and Software Technology, 44. 2002. - P. 841-855.

52. Cao X.-R. A unified approach to Markov decision problems and performance sensitivity analysis // Automatica 36. 2000. P. 771-774.

53. Cao X.-R. Basic ideas for event-based optimization of markov systems // Discrete Event Dynamic Systems: Theory and Applications, 15. 2005. - P. 169-197.

54. Cao X.-R. From perturbation analysis to Markov decision processes and reinforcement learning // Discrete Event Dynamic Systems: Theory and Applications, 13. 2003. - P. 9-39.

55. Cao X.-R. Introduction to the special issue on learning, optimization, and decision making in DEDS // Discrete Event Dynamic Systems: Theory and Applications, 13. 2003. - P. 7-8.

56. Cao X.-R. Perturbation analysis of discrete event systems: concepts, algorithms, and applications // European Journal of Operational Research, 91. 1996. - P. 1-13.

57. Cao X.-R. Single sample path-based optimization of Markov chains // Journal of optimization theory and applications. -V. 100, N. 3. 1999. - P. 527-548.

58. Cao X.-R. The Relations Among potentials, perturbation analysis, and markov decision processes // Discrete Event Dynamic Systems: Theory and Applications, 8. 1998. - P. 71-87.

59. Cao X.-R., Chen H. F. Perturbation realization, potentials and sensitivity analysis of-Markov processes, IEEE Trans. Automat. Control 42. 1997. - P. 1382-1393.

60. Cao X.-R., Fu M. C., Hu J.-Q. On performance potentials and conditional Monte Carlo for gradient estimation for Markov chains // Annals of Operations Research 87. 1999. - P. 263-272.

61. Cao X.-R., Ren Z., Bhatnagar S., Fu M., Marcus S. A time aggregation approach to Markov decision processes // Automatica, 38. -2002. P. 929-943.

62. Casanova H., Legrand A., Zagorodnov D. et al. Heuristics for scheduling parameter sweep applications in Grid environment // Proc. of the 9th Heterogeneous Computing Workshop. -2000.-P. 349-363.

63. Chang B.-J., Hwang R.-H. Efficient hierarchical QoS routing in ATM networks // Computer Communications, 24. -2001. P. 1648-1660.

64. Chang H., Givan R., Chong E. Parallel rollout for online solution of partially observable Markov decision process // Discrete Event Dynamic Systems: Theory and Applications, 14. -2004.-P. 309-341.

65. Chang H. S., Fu M. C., Hu J., Marcus S. I. Simulation-based algorithms for Markov decision Processes. London: Springer, 2007.

66. Chang X., Subramanian K. R. A cooperative game theory approach to resource allocation in wireless ATM networks. Lecture Notes in Computer Science, 1815. 2000.

67. Chang Y. W., Geraniotis E. Optimal policies for handoff and channel assignment in networks of LEO satellites using CDMA // Wireless Networks, 4. 1998. - P. 181-187.

68. Chen M., Feldman R. M. Optimal replacement policies with minimal repair and age-dependent costs // European Journal of Operational Research, 98 1997. - P. 75-84.

69. Cheng Y., Robertazzi T. Distributed computation for a tree network with communication delays // IEEE Trans. On Aerospace and Electronic Systems. 1988. - V. 24(6). - P. 700712.

70. Chung S.-P., Ross K. W. Reduced load approximations for multirate loss networks, IEEE Transactions on Communications, 41. 1993. - P. 1222-1231.

71. Daws C., Kwiatkowska M., Norman G. Automatic verification of the IEEE 1394 root contention protocol with KRONOS and PRISM // International Journal on Software Tools for Technology Transfer, 5. 2004. - P. 221-236.

72. De Nitto P. V., Grassi V. Optimal access control for integrated services wireless networks // Computer Communications, 21 1998. - P. 1559-1570.

73. Dean Т., Kaelbling L. P., Kirman J., Nicholson A. Planning under time constraints in stochastic domains // Artificial Intelligence, 76. 1995. - P. 35-74.

74. Dekker R., Roelvink I. F. K. Marginal cost criteria for preventive replacement of a group of components // European Journal of Operational Research, 84. 1995. - P. 467-480.

75. Dekker R., Wildeman R. E., Van Egmond R. Joint replacement in an operational planning phase // European Journal of Operational Research, 91. 1996. - P. 74-88.

76. Dellaert N. P., Melo M. T. Approximate solutions for a stochastic lot-sizing problem with partial customer-order information // European Journal of Operational Research, 150. -2003. P. 163-180.

77. Dellaert N.P., Melo M.T. Production strategies for a stochastic lot-sizing problem with constant capasity // European Journal of Operational Research, 92. 1996. - P. 281-301.

78. Dietz D.S., Rosenshine M. Optimal specialization of a maintenance workforce // IIEj

79. Transactions, 29. 1997. - P. 423^133.

80. Do Val J.B.R., Salles J.L.F. Optimal production with preemption to meet stochastic demand // Automatica, 35. 1999. - P. 1819-1828.

81. Draper B.A., Ahlrichs U., Paulus D. Adapting object recognition across domains: a demonstration // Lecture Notes in Computer Science, 2095. 2001.

82. Draper B.A., Bins J., Baek K. ADORE: Adaptive object recognition // Lecture Notes in Computer Science, 1542. 1999.

83. Drouin N., Gautier A., Lamond B. F., Lang P. Piecewise affine approximations for the control of a one-reservoir hydroelectric system // European Journal of Operational Research, 89. -1996.-P. 53-69.

84. Duenyas I., Patana-Anake P. Base-stock control for single-product tandem make-to-stock systems // HE Transactions, 30. 1998. - P. 31-39.

85. Duenyas I., Tsai C.-Y. Control of a manufacturing system with random product yield and downward substitutability // HE Transactions, 32. 2000. - P. 785-795.

86. Dziong Z., Mason L. G. Call admission and routing in multi-service loss networks, IEEE Transactions on Communications, 42. 1994. - P. 2011-2022.

87. Economou A. On the control of a compound immigration process through total catastrophes // European Journal of Operational Research, 147. 2003. - P. 522-529.

88. Eilam T. et al. A utility computing framework to develop utility systems // IBM System Journal. 2004. - V. 43(1). P. - 97-120.

89. El-Fattah Y. M. Gradient approach for recursive estimation and control in finite Markov chains // Adv. Appl. Probab., 13. 1981. - 778-803.

90. Esogbue A. O., Hearnes W. E. A learning algorithm for the control of continuous action Set-point regulator systems // Journal of Computational Analysis and Applications, V.l, N.2.-1999.

91. Ferch M., Zhang J. Learning cooperative grasping with the graph representation of a state-action space // Robotics and Autonomous Systems, 38. 2002. - P. 183-195.

92. Fleischmann M., Kuik R. On optimal inventory control with independent stochastic item returns // European Journal of Operational Research, 151 2003. - P. 1, 25-37.

93. Foster Я. What is the Grid? The three criteria. http://www.gridclub.ru/library/publication.2004-ll-29.5830756248/publfile.

94. Foster I., Kesselman C., Tuecke S. The anatomy of the Grid: enabling scalable virtual organizations // Int. Journal of High Performance Computing Applications. 2001. - V. 15. № 3. - P. 200-222.

95. Fujimoto N., Hagihara K. Near-optimal dynamic task scheduling of precedence constrained coarse-grained tasks onto a computational Grid // Proc. of ISPDC 2003, Ljubljana, Slovenia, October 2003.

96. Gallego G., Ни H. Optimal policies for production/inventory systems with finite capacity and Markov-modulated demand and supply processes // Annals of Operations Research, 126.-2004.-P. 21-41.

97. Gel E.S., Hopp W.J., Van Oyen M.P. Factors affecting opportunity of work sharing as a dynamic line balancing mechanism // HE Transactions, 34. 2002. - P. 847-863.

98. Givan R., Chong E. K. R. Parallel rollout for online solution of partially observable Markov decision processes // Discrete Event Dynamic Systems: Theory and Applications, 14. — 2004.-P. 309-341.

99. Givan R., Leach S., Dean T. Bounded-parameter Markov decision processes // Artificial Intelligence, 122. 2000. - P. 71-109.

100. Glazebrook K. D. Stochastic scheduling and forwards induction // Discrete Applied Mathematics, 57. 1995. - P. 145-165.

101. Goldman R. P., Musliner D. J., Krebsbach K. D. Managing online self-adaptation in real-time environments // Lecture Notes in Computer Science, 2614. 2003. - P. 6-23.

102. Gosavi A. A reinforcement learning algorithm based on policy iteration for average reward: empirical results with yield management and convergence analysis // Machine Learning, 55.-2004.-P. 5-29.

103. Gosavi A., Bandla N., Das Т. K. A reinforcement learning approach to a single leg airline revenue management problem with multiple fare classes and overbooking // HE Transactions, 34. 2002. - P. 729-742.

104. Grolknann A., Poli R. Learning a navigation task in changing environments by multitask reinforcement learning // LNAI, 1812. 2000. - P. 23-43.

105. Hamilton M. D., McKee P., Mitrani I. Optimal caching policies for Web objects // Lecture Notes in Computer Science, 2110. 2001.

106. Hamscher V., Schwiegelshohn U., Streit A., Yahyapour R. Evaluation of job-scheduling strategies for Grid computing // LNCS, 1971. 2000. - P. 191- 202.

107. Hariharan R., Moustafa M. S., Stidham Jr. S. Scheduling in a multi-class series of queues with deterministic service times // Queueing Systems, 24. 1996. - P. 83-99.

108. Hinderer К., Waldmann K.-H. Cash management in a randomly varying environment // European Journal of Operational Research, 130. 2001. - P. 468-485.

109. Hontelez J. A. M., Burger H. H., Wijnmalen D. J. D. Optimum condition-based maintenance policies for deteriorating systems with partial information // Reliability Engineering & System Safety, 51. 1996. - P. 267-274.

110. Howard R. A. Dynamic programming and Markov processes. NewYork: Wiley,1960.127. http://www-cse.ucsd.edu/users/berman/apples.html.128. http://www.globus.org/research/papers/.129. http://www.nas.nasa.gov/.

111. Hwang R.-H. Adaptive multicast routing in multirate loss networks // Telecommunication Systems, 12. 1999. - P. 283-313.

112. Iakovou E., Ip С. M., Koulamas C. Machining economics with phase-type distributed tool lives and periodic maintenance control // Computers & Operations Research, 23. 1996. -P. 53-62.

113. Iakovou E., Ip С. M., Koulamas C. Throughput-dependent periodic maintenance policies for general production units // Annals of Operations Research, 91.- 1999. P. 41-47.

114. Iravani S. M. R., Duenyas I. Integrated maintenance and production control of a deteriorating production system // HE Transactions, 34. 2002. - P. 423-435.

115. Ishii S., Yoshida W., Yoshimoto J. Control of exploitation-exploration meta-parameter in reinforcement learning // Neural Networks, 15. 2002. - P. 665-687.

116. Johansen S. G., Larsen C. Computation of a near-optimal service policy for a single-server queue with homogeneous jobs // European Journal of Operational Research, 134. — 2001. P. 648-663.

117. Keblis M. F., Duenyas I. Control of an assembly system with processing time and sub-assembly-type uncertainty // The International Journal of Flexible Manufacturing Systems, 11,-1999.-P. 353-370.

118. Kelly F. P. Routing in circuit switched networks: Optimization, shadow prices and decentralization // Advances in Applied Probability, 20. 1988. - P. 112-144.

119. Kim E. Stochastic vendor managed replenishment with demand dependent shipment // European Journal of Operational Research, 152. 2004. - P. 723-744.

120. Kim E., Van Oyen M. P. Finite-capacity multi-class production scheduling with set-up times // HE Transactions, 32. 2000. - P. 807-818.

121. Kirchner F., Hertzberg J. A prototype study of an autonomous robot platform for sewerage system maintenance // Autonomous Robots, 4. 1997. - P. 319-331.

122. Konovalov M. G. Management controls in telephone networks // 3 Московская международная конференция по исследованию операций (ORM2001). Москва, 4-6 апреля 2001.-С. 57-58.

123. Konovalov М., Shorgin S., Saverio S. Problems of GRID systems modeling. — Transactions of XXV International Seminar on Stability Problems for Stochastic Models. Maiori (Salerno), Italy, September 20-24,2005. P. 309.

124. Kristensen A. R., Jorgensen E. Multi-level hierarchic Markov processes as a framework for herd management support // Annals of Operations Research, 94. 2000. - P. 69-89.

125. Kuri J., Kumar A. On the optimal control of arrivals to a single queue with arbitrary feedback delay // Queueing Systems, 27. 1997. - P. 1-16.

126. Kyriakidis E. G. Optimal control of a simple immigration-birth-death process through total catastrophes // European Journal of Operational Research, 81. 1995. - P. 346-356.

127. Kyriakidis E. G. Optimal control of a simple immigration-emigration process through total catastrophes // European Journal of Operational Research, 155. 2004. - P. 198-208.

128. Kyriakidis E. G. Optimal pest control through the introduction of a predator // European Journal of Operational Research, 81. 1995. - P. 357-363.

129. Lagoudakis M. G., Parr R., Littman M. L. Least-squares methods in reinforcement learning for control // LNAI, 2308. 2002. - P. 249-260.

130. Lamond B. F., Lang P. Lower bounding aggregation and direct computation for an infinite horizon one-reservoir model // European Journal of Operational Research, 95. 1996. - P. 404-410.

131. Laoutaris N., Boukeas G., Stavrakakis I. Design of optimal playout schedulers for packet video receivers // Lecture Notes in Computer Science, 2156. 2001.

132. Laoutaris N., Stavrakakis I. An analytical design of optimal playout schedulers for packet video receivers // Computer Communications, 26. 2003. - P. 294-303.

133. Laroche P. GraphMDP: A new decomposition tool for solving Markov decision processes // International Journal on Artifical Intelligence Tools, 10, No. 3. 2001. - P. 325-343.

134. Lee Т. E., Lee J.-H. A two-phase approach for design of supervisory controllers for robot cells: Model checking and Markov decision models // Annals of Operations Research, 77. 1998.-157-182.

135. Li H., Baras J. S. A framework for supporting intelligent fault and performance management for communication networks // Lecture Notes in Computer Science, 2216. 2001.

136. Li H., Dagli С. H. Hybrid least-squares methods for reinforcement learning // LNAI 2718.-2003.-P. 471-480.

137. Love С. E., Zhang Z.G., Zitron M. A., Guo R. A discrete semi-Markov decision model to determine the optimal repair/replacement policy under general repairs // European Journal of Operational Research, 125. 2000. - P. 398^109.

138. Luh H., Rieder U. Optimal control of arrivals in tandem queues of constant service time //Math Meth Oper Res. 53. -2001. P. 481—491.

139. Mahadevan S. Average reward reinforcement learning foundations, algorithms, and empirical results // Machine Learning, 22. 1996. - P. 159-195.

140. Mahadevan S. Spatiotemporal abstraction of stochastic sequential processes // Lecture Notes in Computer Science, 2371. 2002.

141. Marbach P., Tsitsiklis J.N. Approximate gradient methods in policy-space optimization of markov reward processes // Discrete Event Dynamic Systems: Theory and Applications, 13.-2003.-P. 111-148.

142. Menache I., Shie Mannor S., Shimkin N. Q-Cut Dynamic discovery of sub-goals in reinforcement learning // LNAI, 2430. - 2002. - P. 295-306.

143. Merke A., Riedmiller M. Karlsruhe Brainstormers A reinforcement learning approach to robotic soccer // Lecture Notes in Computer Science, 2377. — 2002.

144. Morisset В., Ghallab M. Learning how to combine sensory-motor modalities for a robust behavior // Lecture Notes in Computer Science, 2466. 2002. - P. 157-178.

145. Munos R. A study of reinforcement learning in the continuous case by the means of viscosity solutions H Machine Learning, 40. 2000. - 265-299.

146. Munos R., Moore A. Variable resolution discretization in optimal control // Machine Learning, 49. 2002. - P. 291-323.

147. Nobel R. D., Tijms H. C. Optimal control for an Mx/G/1 queue with two service modes // European Journal of Operational Research, 113. 1999. P. 610-619.

148. Pendrith M. D. Reinforcement learning in situated agents: theoretical problems and practical solutions // LNAI 1812. 2000. - P. 84-102.

149. Price В., Boutilier C. Imitation and reinforcement learning in agents with heterogeneous actions // LNAI 2056. 2001. - P. 111 - 120.

150. Puliti P., Tascini G, Montesanto A. Reactive navigation using reinforcement learning in situations of POMDPs // LNCS 2085. 2001. - P. 444^150.

151. Ranganathan K., Foster I. Decoupling computation and data scheduling in distributed data-intensive applications //The 11th IEEE Int. Symposium on High Performance Distributed Computing: Proc. Edinburgh, Scotland. 2002.

152. Ravindran В., Barto A. G. Model minimization in hierarchical reinforcement learning // Lecture Notes in Computer Science, 2371. 2002.

153. Recommendation E.412 (10/92). Telephone network and ISDN. Quality of service, network management and traffic engineering. Network management controls. ITU, 1993.

154. Regan P. J., Pate-Cornell M. E. Normative engineering risk management systems // Reliability Engineering & System Safety, 57. 1997. - P. 159-169.

155. Reiman M.I., Shwartz A. Call admission: a new approach to quality of service // Queueing Systems 38. 2001. - P. 125-148.

156. Ribeiro C. Reinforcement learning agents // Artificial Intelligence Review, 17. 2002. -P. 223-250.

157. Robbins M. A sequential decision problem with a finite memory // Proc. Nat. Acad. Sci. USA. V. 42, N 3. - 1956.

158. Robbins H., Monro S. A stochastic approximation method // Ann. Math. Stat. V. 22. -1951.-P. 400^407.

159. Sahin I., Zahedi F. Control limit policies for warranty, maintenance and upgrade of software systems // HE Transactions, 33. 2001. - P. 729-745.

160. Sahin I., Zahedi F. Optimal policies under risk for changing software systems based on customer satisfaction // European Journal of Operational Research, 123. 2000. - P. 175— 194.

161. Schoknecht R., Riedmiller M. Reinforcement learning on explicitly specified time scales // Neural Comput & Applic, 12. 2003. - P. 61-80.

162. Schoknecht R., Riedmiller M. Speeding-up reinforcement learning with multi-step actions // LNCS 2415. 2002. - P. 813- 818.

163. Senkul S., Polat F. Learning intelligent behavior in a non-stationary and partially observable environment // Artificial Intelligence Review, 18. 2002. - P. 97-115.

164. Senouci S.-M., Beylot A.-L., Pujolle G. Call admission control for multimedia cellular networks using neuro-dynamic programming // Lecture Notes in Computer Science, 2345. -2002.

165. Shan H., Oliker L., Biswas R. Job superscheduler architecture and performance in computational Grid environments // Proc. of the 2003 ACM/IEEE conference on Supercomput-ing. -2003. P. 44.

166. Shao G., Wolski R., Berman F. Performance effects of scheduling strategies for master/slave distributed applications // UCSD CSE Technical Report CS98-598. University of California, San Diego. 1998.

167. Sloan T.W., Shanthikumar J.G. Using in-line equipment condition and yield information for maintenance scheduling and dispatching in semiconductor wafer fabs // IIE Transactions, 34.-2002.-P. 191-209.

168. Smith W., Foster I., Taylor V. Predicting application run times using historical information // Lecture Notes on Computer Science. 1998. - Vol. 1459. - P. 122-142.

169. Smith W., Wong P. Resource selection using execution and queue wait time predictions // NAS Technical Report. NAS-02-003. 2002. 7 p.

170. Sohn J., Robertazzi T. G., Luryi S. Optimizing computing costs using divisible load analysis // IEEE Trans. Parallel and Distributed Systems. 1998. - V. 9, N. 3, - P. 225-234.

171. Sragovich V. G. Mathematical theory of adaptive control. Singapore: World Scientific, 2006.

172. Sun R., Sessions C. Automatic segmentation of sequences through hierarchical reinforcement learning // LNAI 1828. 2000. - P. 241-263.

173. Sutton R., Barto A. Reinforcement learning. MIT Press, 2000.

174. Tadepalli P., Ok D. Model-based average reward reinforcement learning // Artifical Intelligence, 100. 1998. - P. 177-224.

175. Tannenbaum Т., Wright D., Miller K., Livny M. Condor A distributed job scheduler // Beowulf Cluster Computing with Linux, The MIT Press, MA, USA, 2002.

176. Tesauro G. J. TD-Gammon, a self-teaching backgammon program, achieves master-level play, Neural Computation, 6. 1994. - P. 215-219.

177. Thickins G. Utility Computing: The next new IT model // Darwin Magazine. April2003.

178. Tong H., Brown Т. X. Reinforcement learning for call admission control and routing under quality of service constraints in multimedia networks // Machine Learning, 49. 2002. — P. 111-139.

179. Unsupervised adaptive filtering. V. 1,2. Edited by S. Haykin. New York: John Willey & Sons, Inc, 2000.

180. Vadhiyar S., Dongarra J. A metascheduler for the Grid // Proc. of the 11th IEEE Symposium on High-Performance Distributed Computing. 2002. — P. 343-351.

181. Van der Schouten D., Vanneste S.G. Mainetance optimization of a production system with buffer capacity // European Journal of Operational Research, 82. 1995. - P. 323-338.

182. Wijnmalen D. J. D., Hontelez J. A. M. Coordinated condition-based repair strategies for components of a multi-component maintenance system with discounts // European Journal of Operational Research, 98. 1997. - P. 52-63.

183. Williams В. К. Adaptive optimization of renewable natural resources: Solution algorithms and a computer program // Ecological Modelling, 93. 1996. - P. 101-111.

184. Wuest С. C., Verhaegh W. F. J. Quality control for scalable media progressing applications // Journal of Scheduling, 7. 2004. - P. 105-117.

185. Xiaobo Z., Ohno K., Nakade K. An optimal cart moving policy for a flexible manufacturing system // IEE Transactions, 34. 2002. - P. 34, 41-50.

186. Xiaobo Z., Ohno K., Nakade K. Modeling for flexible manufacturing systems and structural properties of optimal work routing policy // Journal of Intelligent Manufacturing, 8. -1997.-P. 497-503.

187. Yao D. D., Zheng S. Sequential quality control in batch manufacturing // Annals of Operations Research, 87. 1999. - P. 3-30.

188. Yoshimoto J., Ishii S., Sato M. System identification based on online variational Bayes method and its application to reinforcement learning // LNCS, 2714. 2003. - P. 123— 131.

189. Yu J., Buyya R., Tham С. K. A cost-based scheduling of scientific workflow applications on utility Grids // In 1st IEEE International Conference on e-Science and Grid Computing, Melbourne, Australia, Dec. 5-8, 2005.

190. Zheng S. Dynamic release policies for software systems with a reliability constraint // HE Transactions, 34. 2002. - P. 253-262.

191. Zhu J., Hong J., Hughes J. G. Using Markov chains for link prediction in adaptive Web sites // Lecture Notes in Computer Science, 2311. 2002.

192. Zilberstein S., Washington R., Bernstein D. S., Mouaddib A.-I. Decision-theoretic control of planetary rovers // Lecture Notes in Computer Science, 2466. 2002. - P. 270-289.