Михаил григорьевич модели и технологии адаптивной обработки информации для частично наблюдаемых систем
На правах рукописи
УДК 519.218+519.857.3 Коновалов Михаил Григорьевич МОДЕЛИ И ТЕХНОЛОГИИ АДАПТИВНОЙ ОБРАБОТКИ ИНФОРМАЦИИ ДЛЯ ЧАСТИЧНО НАБЛЮДАЕМЫХ СИСТЕМ 05.13.17 – теоретические основы информатики
АВТОРЕФЕРАТ
диссертации на соискание ученой степени доктора технических наук
Москва 2008
Работа выполнена в Институте проблем информатики РАН
Официальные оппоненты:
член-корреспондент РАН, доктор физико-математических наук, профессор Флеров Юрий Арсениевич заслуженный деятель науки РФ, доктор технических наук, профессор Оганян Герман Арташесович заслуженный деятель науки РФ, доктор технических наук, профессор Синицин Игорь Николаевич
Ведущая организация:
Московский государственный технический университет им. Н. Э. Баумана
Защита состоится «_» 2008 года в часов на заседании диссертационного совета Д 002.073.01 при Институте проблем информатики РАН по адресу: 119333, Москва, ул. Вавилова, 44, корп. 2.
С диссертацией можно ознакомиться в библиотеке Института проблем информатики РАН Отзывы в двух экземплярах, заверенных печатью, просим направлять по адресу: 119333, Москва, ул. Вавилова, 44, корп. 2, диссертационный совет.
Автореферат разослан «» «_» 2008 года.
Ученый секретарь диссертационного совета Д002.073.01, доктор технических наук, профессор С. Н. Гринченко ОБЩАЯ ХАРАКТЕРИСТИКА ДИССЕРТАЦИИ Актуальность темы В различных областях науки и техники имеются многочисленные задачи, для решения которых необходимо анализировать, оптимизировать, реализо вывать взаимодействие субъекта с объектом в условиях недостаточной ин формации. Наибольшее количество подобного рода задач возникает в ин формационных и телекоммуникационных системах, автоматизированных производственных процессах, робототехнике, то есть в тех сферах, которые в наибольшей степени связаны с компьютерной обработкой информации.
Неполнота информации имеет двоякое качество. Во-первых, это (частич ное) отсутствие априорной информации, даже на уровне представления о структуре объекта, имеющего, как правило, стохастическую природу. Во вторых, ограниченная возможность наблюдения объекта и его идентифика ции. В предельном случае субъекту заранее известно лишь множество, из ко торого можно выбирать воздействия на объект, а неполнота наблюдений в неблагоприятных случаях означает, что субъект может лишь оценивать от клики объекта с точки зрения своего предпочтения. В подобных ситуациях первостепенное значение приобретает умение воспользоваться доступной информацией об объекте, в том числе, и главным образом, приобретенной в ходе взаимодействия с ним. Умение субъекта пользоваться для достижения цели информацией, поступающей в процессе функционирования, связано с такими понятиями, как «самоорганизация», «приспособление», «адаптация».
Диссертационная работа посвящена преимущественно синтезу, анализу и применению адаптивных стратегий обработки информации.
Основополагающие идеи теории адаптации были заложены в 50-х годах прошлого века1,2, а становление теории и ее развитие до конца 80-х годов проходило во многом благодаря усилиям отечественных исследователей3. С начала 90-х годов и по настоящее время это направление переживает боль шой подъем, а число публикаций исчисляется многими сотнями. В частно сти, выделилась и получила широкое распространение новая ветвь, тесно связанная с искусственным интеллектом и его разнообразными приложениями4.
Центральное место в теории адаптации занимает проблематика частично на блюдаемого марковского процесса принятия решений. Традиционный подход, основанный на динамическом программировании, дал результаты, применимые в адаптивном варианте5,6. «Марковские процессы являются в настоящее время H. Robbins, Monro S. A stochastic approximation method // Ann. Math. Stat. – V. 22. – 1951.
– P. 400– H. Robbins. A sequential decision problem with a finite memory // Proc. Nat. Acad. Sci. USA.
– V. 42, No. 3. – 1956. – P. 920–923.
V. G. Sragovich. Mathematical Theory of Adaptive Control. – Singapore: World Scientific, 2006.
R. Sutton, A. Barto. Reinforcement learning. – MIT Press, 2000.
D. P. Bertsekas. Dynamic programming and optimal control, V. 1, 2. – Belmont: Athena Scien tific, 2001.
математическим фундаментом для многих работ в области активного обучения (reinforcement learning), теории принятия решений, поиска информации, распо знавания речи, активного зрительного восприятия, навигации роботов»7. В то же время «одна из основных проблем в приложении теории марковского про цесса принятия решений заключается в необходимости рассматривать не слиш ком большое пространство состояний»8. Как подчеркивают многие авторы, и как свидетельствует большой поток публикаций, необходим дальнейший про гресс в этой области, имеющей неоспоримое прикладное значение.
Развиваемое в диссертационной работе адаптивное направление лежит в русле фундаментальных исследований, как адаптивного, так и не адаптивно го характера, в области стохастических систем и стохастических информаци онных технологий9,10. Стремительный прогресс в области информационных и телекоммуникационных технологий позволил поставить на гораздо более ре альную почву вопрос о практической реализации стохастических адаптивных алгоритмов, которые принципиально связаны с быстрой обработкой и пере дачей больших объемов оперативной информации.
Из вышесказанного следует, что тема диссертационной работы находится в одной из актуальных и плодотворных областей современной науки.
Цель и задачи исследования Целью диссертационной работы является разработка теоретических ос нов анализа, синтеза и применения стратегий адаптивной обработки информации и принятия решений в условиях неполного наблюдения. При проведении исследований были поставлены следующие основные задачи.
1. Разработка теоретических основ синтеза адаптивных стратегий в общих моделях частично наблюдаемых стохастических объектов.
2. Изучение класса частично наблюдаемых управляемых однородных мар ковских цепей. Разработка для этого класса простых, эффективных и универсальных адаптивных алгоритмов, позволяющих решать задачи боль шой размерности.
3. Изучение принципиальной возможности и оценка границ применения теории в различных областях приложений. Разработка общей методологии применения адаптивных методов обработки информации.
4. Реализация комплекса действий, связанных с синтезом информацион ных технологий для моделирования, адаптивной обработки информации и принятия решений на примерах крупных прикладных проблем.
H. S. Chang, M. C. Fu, J. Hu, S. I. Marcus. Simulation-based algorithms for Markov decision Processes. – London: Springer, 2007.
S. Mahadevan. Spatiotemporal abstraction of stochastic sequential processes // Lecture Notes in Computer Science, 2371. – 2002.
T. Belker, M. Beetz, A.B. Cremers. Learning action models for the improved execution of navigation plans // Robotics and Autonomous Systems, 38. – 2002. – P. 137–148.
В.С. Пугачев, И. Н. Синицын. Теория стохастических систем. – М.: Изд. Логос. 2004.
Unsupervised adaptive filtering. V. 1, 2. Edited by S. Haykin. – New York: John Willey & 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 таблиц.
ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ Во Введении дана общая характеристика диссертации, ее предмета, цели и задач. Сформулированы основные признаки, которыми отличается изучае мая проблема:
• имеется процесс взаимодействия с объектом произвольной (стохастиче ской) природы, в котором воздействия на объект чередуются с получе ниями откликов (наблюдений);
• характеристики процесса и возможности наблюдения являются неполными;
• процесс взаимодействия сопровождается синхронной с основным процес сом, наблюдаемой последовательностью «доходов»;
• цель взаимодействия – (условная) максимизация предельного среднего дохода;
• процесс чередования пар сигналов «действие – наблюдение» продолжается неограниченно долго (с практической точки зрения – «достаточно долго»).
В этих условиях требуется определить для взаимодействующего субъекта такую стратегию анализа и обработки поступающей информации, которая позволяла бы ему постепенно «обучаться» совершать «правильные» действия и достигать цели, максимально доступной в тех условиях неопределенности, в которых он находится. Разрабатываемые алгоритмы обучения, или страте гии адаптивной обработки информации должны быть устроены как рекур рентные процедуры, осуществляющие целенаправленный бесконечный поиск в конечномерном пространстве на основе статистических оценок. При этом должны выполняться следующие требования:
• а д а п т и в н о с т ь – не предполагается обязательное наличие априорной информации и зависимости от параметров объекта;
может использоваться оперативная информация, полученная в ходе взаимодействия с объектом;
• э ф ф е к т и в н о с т ь – время адаптации, то есть время до осуществления оптимизации по выбранному критерию качества должно быть небольшим;
• к о н с т р у к т и в н о с т ь – реализация алгоритма должна быть простой, сводиться к выполнению на каждом такте сравнительно небольшого числа арифметических операций и требовать сравнительно малой памяти;
• у н и в е р с а л ь н о с т ь – алгоритмы должны быть применимы к широкому классу объектов разнообразной физической природы, допускать локаль ное, распределенное и децентрализованное использование.
В главе 1 на основе анализа большого количества источников сделан об зор значительной части всей сферы приложений, которые классифицированы на рис. 1. В качестве основных областей приложения выделены три: инфоте лекоммуникационные системы (раздел 1.1), производственные системы (раздел 1.2), а также приложения, связанные с моделированием поведения, искусственным интеллектом и робототехникой (раздел 1.3).
ОБЛАСТИ ПРИЛОЖЕНИЯ АДАПТИВНЫХ АЛГОРИТМОВ Информационные и Сети телекоммуникационные связи системы Коррекция Оптимизация маршрутных доступа и поиск таблиц информации Распределенные в Интернете вычисления Управление потоками Оптимизация Оптимальное передачи использование Оптимизация до- голосового трафика ресурсов полнительных (IP-телефония) управляющих воздействий Оперативное управление Оптимизация потоками заданий воспроизведения Оптимизация видеотрафика поддержки программного обеспечения Управление производством и сбытом Производственные Технологические Планирование и системы процессы диспетчеризация Оптимизация Теория Техническое сборочного расписаний и обслуживание процесса календарное планирование Балансировка Управление технологических запасами линий Гибкое автоматизированное производство Искусственный Роботы интеллект Производственные и хозяйственные роботы Интеллектуальные Модели Космические игровые системы поведения вездеходы Управляемые Стабилизация системы массового механических систем обслуживания Другие приложения Регулирование Распознавание биологических образов Выбор ресурсов наилучшего алгоритма Рис. 1. Примерная классификация областей приложения адаптивных методов.
Системы компьютерной обработки и передачи информации являются наиболее очевидным направлением применения адаптивных методов. Во многих сферах телекоммуникации они уже с успехом применяются. Напри мер, давно применяется адаптивная маршрутизация. (Приложениям в облас ти маршрутизации для сетей с коммутацией каналов посвящена отдельная глава 5.) Плодотворным приложением является также близкий участок сете вой тематики, связанный с управлением потоками, в частности, важное для беспроводных технологий управление доступом.
Сравнительно новой областью приложения является проектирование сис тем распределенных вычислений. Необходимость принятия решений возни кает при распределении потоков заданий между вычислительными ресурса ми, а применение адаптивных методов не нашло пока должного распростра нения. (Данной проблеме также посвящена отдельная глава 6.) Среди других приложений в области инфотелекоммуникаций указаны поиск информации и организация сайтов в среде Интернет;
управление качеством сетевого серви са;
организация поддержки программного обеспечения и некоторые другие.
Следующей важной областью применения адаптивных алгоритмов явля ются производственные системы: технологические линии, сборочные кон вейеры, гибкие автоматизированные производства и пр. Эти системы требу ют настройки, балансировки, планирования, диспетчеризации и других оп тимизационных решений в области производства и сбыта. Как показывает анализ, такие процессы хорошо укладываются в основную схему, намечен ную во введении и изученную далее в главах 2–4. Очень большое количество постановок задач дают также направления, связанные с техническим обслу живанием и управлением запасами.
Первоначальный этап создания и исследования адаптивных алгоритмов в значительной степени проходил под эгидой «моделирования поведения и ин теллекта». Это направление вполне сохранилось и достаточно интенсивно развивается в настоящее время. В диссертационной работе приведен обзор моделей поведения, которые предназначены для отработки тех или иных ал горитмов обучения и являются широко разрабатываемой областью примене ния. К тому же данные исследования воплощаются во вполне осязательных изделиях, которые называются роботами. Приведено несколько иллюстра тивных примеров из робототехники.
Раздел 1.4 содержит примеры из самых разнообразных областей прило жений: управляемые системы массового обслуживания (за которыми также стоят всевозможные применения), примеры из механики, экологии и пр.
В главе 2 приведены базовые определения и конструкции, необходимые для изучения теоретических основ адаптивной обработки информации при неполном наблюдении. В разделе 2.1 дано общее определение объекта как дискретной частично наблюдаемой управляемой случайной последователь ности. Сформулировано общее понятие стратегии.
В качестве общей модели рассмотрен процесс, имеющий три компоненты:
( xt, yt +1, zt +1 ), t = 0, 1, …, которые называются соответственно состоянием, действием и наблюдением. Эволюция этих компонент определяется с помо щью трех последовательностей условных распределений: µ = (µ 0, µ1,...), = ( 1,...) и = ( 1,...), определяющих соответственно изменение состоя ний, появление наблюдений и выбор действий. Пара (µ, ) называется объ ектом, последовательность называется стратегией, а элементы последо вательности называются правилами.
Наглядно, процесс развивается следующим образом (рис. 2). В начальный момент t = 0 состояние x0 объекта определено согласно распределению µ 0. В момент t = 1 субъект должен выбрать некоторое действие y1 (он делает это с помощью правила 1 );
в результате субъект может произвести наблюдение z1, которое возникает по закону 1. Если процесс достиг предыстории x t 1, y t, z t, то состояние объекта xt возникает с помощью распределения µ t.
Очередное действие y t +1 субъект выбирает, руководствуясь правилом t +1, а новое наблюдение появляется в силу распределения t +1 и т. д.
предыстория xt-1, yt, zt действие yt+1=t+1(yt,zt) действие y µ0 1 1 µt t+1 t+1 ••• ••• начальное состояние xt наблюдение z1 наблюдение zt+ состояние x Рис. 2. Процесс взаимодействия субъекта и объекта.
Если в наблюдении можно выделить компоненту, полностью совпадаю щую с состоянием, то объект называется полностью наблюдаемым, а в иных случаях объект называется частично наблюдаемым. Предполагается, что в любом случае наблюдение содержит компоненту, которая принимает число вые значения из интервала (0, 1) и называется доходом.
Выделяются некоторые типы стратегий, которые важны для анализа пове дения субъекта. Так, стратегия называется детерминированной, если все ее правила задаются с помощью вырожденных (сосредоточенных в одной точ ке) условных распределений. Стратегия имеет глубину d 0, если все ее пра вила, начиная с момента d + 1, существенно зависят только от предыстории глубины d до момента t включительно. Если состояния объекта наблюдаемы, то стратегия, состоящая из правил, у которых выбор очередного действия за висит только от предыдущего состояния, называется марковской стратеги ей. Стратегия глубины d называется однородной, если все ее правила, начи ная с момента d + 1, не зависят явно от времени. Таким образом, по опреде лению, в однородной стратегии глубины d, начиная с момента d + 1, приме няется одно и то же правило глубины d.
В диссертационной работе изучаются следующие основные объекты (1–3).
1. Одно из центральных мест отведено изучению (управляемых) однород ных марковских цепей со счетным или конечным множеством состояний, ко нечным множеством действий и с доходами, причем доход определяется по следним состоянием процесса и выбранным в этом состоянии действием.
Принципиально различаются случаи полного и частичного наблюдения, каж дый из которых является предметом изучения.
2. Если в управляемой однородной марковской цепи при заданном дейст вии переход от одного состояния цепи к другому происходит детерминиро вано, то говорим об (управляемом) графе с доходами. Конечное множество состояний играет роль вершин графа, находясь в которых можно совершить действие из заданного конечного множества. С переходом по дуге вида (i, i1, k ), который осуществляется, если в вершине i выбрано действие k, свя зан доход – случайная величина, имеющая распределение, зависящее от i и k.
Изучается случай частично наблюдаемого связного графа.
3. Для теоретического анализа проблемы поведения в условиях недоста точной информации представляет интерес (частично наблюдаемый) регене рируемый объект, с конечными множествами состояний и действий, который обладает следующими свойствами. На любом этапе взаимодействия можно «организовать» с помощью выбора подходящих действий наступление мо мента регенерации. В этот момент объект переводится в состояние, «эквива лентное» начальному состоянию. Состояние объекта в текущий момент вре мени зависит от всей предыстории с момента предыдущей регенерации, при чем характер зависимости может быть произвольным, а промежутки между моментами регенерации могут быть сколь угодно длинными. В довершение состояния объекта не наблюдаемы (число их неизвестно), а наблюдаемы только доходы. Введенный объект обобщает понятие частично наблюдаемой связной марковской цепи. Появление его вызвано стремлением указать как можно более широкую конструкцию объекта, с которым можно целенаправ ленно взаимодействовать, «обучаясь» в процессе взаимодействия. При этом наличие моментов регенерации представляется совершенно необходимым, для того чтобы избежать «непоправимых» ошибок в процессе обучения.
В разделе 2.2 показана фундаментальная роль детерминированных одно родных стратегий конечной глубины. Рассмотрены регенерируемые объекты, для которых определено понятие предельного среднего дохода за стратегию.
Доказана теорема, которая устанавливает, что для любого указанного объек та существует детерминированная однородная равномерно -оптимальная относительно начального распределения стратегия конечной глубины. Это утверждение является аналогом ряда известных результатов, согласно кото рым структура зависимости правил стратегии от предыстории повторяет структуру зависимости переходных вероятностей объекта от предыстории. В связи с полученным результатом надо подчеркнуть, что на характер зависи мости переходных вероятностей для регенерируемых объектов не наклады ваются ограничения ни по однородности, ни по глубине предыстории, ни по каким-либо условиям эргодичности. Доказанная теорема имеет важные след ствия в двух отношениях. Во-первых, множество стратегий, среди которых следует искать равномерно -оптимальную стратегию для рассматриваемых объектов, является счетным. Во-вторых, данный класс объектов содержит как частный случай частично наблюдаемые связные марковские цепи.
Глава 3 посвящена изучению метода перебора в теории адаптации. Адап тивной стратегией принято называть стратегию, которая достигает цели для любого объекта из заданного множества объектов и не зависит при этом от переходных вероятностей, определяющих объект. Один из наиболее эффект ных приемов построения адаптивной стратегии основан на простой идее «пе ребора вариантов». В процессе взаимодействия с объектом перебираются возможные варианты поведения. Если какой-то вариант представляется «хо рошим», то его применяют достаточно долго, прежде чем перейти к испыта нию нового варианта. Поскольку качество различных вариантов можно оце нить лишь со случайными ошибками, то процесс перебора никогда не окан чивается, но среднее время применения «хорошего» варианта подавляюще превосходит среднее время использование менее выгодных вариантов. Пер вая реализация этой идеи – автомат Роббинса2, который предназначался для однородных процессов с независимыми значениями. В качестве множества «вариантов» на каждом такте взаимодействия в этом случае выступает (ко нечное) множество действий. В дальнейшем это направление широко разви валось, преимущественно применительно к процессам с независимыми зна чениями. В диссертации содержится широкое обобщение данного метода.
Более сложные объекты требуют перебора на все более разнообразных множествах. Например, в случае конечных марковских цепей необходимо перебирать конечное множество всех детерминированных однородных мар ковских правил. Еще сложнее обстоит дело в случае частично наблюдаемых конечных марковских цепей, для которых, как показано в разделе 2.2, пере бирать нужно счетное количество вариантов. Для организации такого пере бора необходимо преодолеть следующие принципиальные затруднения. Во первых, его надо осуществить на бесконечном множестве и, во-вторых, каче ство того или иного варианта определяется в терминах предельного вероят ностного распределения. Любое из этих обстоятельств означает, что поиск наилучшего варианта никогда не может окончиться, и что к любому варианту для его испытания необходимо возвращаться неограниченное число раз.
В разделах 3.1, 3.2 исходной позицией является некоторое заданное счет ное множество стратегий. Рассмотрен класс всех объектов, для которых лю бая стратегия из указанного счетного множества является допустимой, и при этом выполнены некоторые условия эргодичности. Построена адаптивная стратегия перебора, и доказана теорема о том, что для любого объекта из обозначенного класса с помощью этой стратегии можно получить предель ный средний доход, равный точной верхней грани доходов по заданному счетному множеству стратегий. Этот результат можно более наглядно пере фразировать так. Задано счетное количество «алгоритмов поведения» и име ется объект, свойства которого заранее неизвестны, и к которому можно применить любой из этих алгоритмов. Построена стратегия, которая достига ет той же цели, что и наилучший из алгоритмов.
При построении адаптивной стратегии метод перебора реализован сле 1 t+n дующим образом. Обозначим t, n = g s, где g t – последовательность n s = t + ( ) доходов, а n – натуральное число, и положим t, n = Int (1 t, n ) n, где Int() означает целую часть числа. Зададим последовательность марковских мо ментов с помощью рекуррентных соотношений 0 = 0, n = n 1 + n + n, где n = n 1, n. Зададим также последовательность случайных величин n, принимающих целые положительные значения.
Пусть – заданное счетное множество стратегий. Стратегия перебора (t n ) I{ n1 t n }, * = *(, ) определяется формулой * = (i ), где t n = I – индикаторная функция. Развернутое описание стратегии * выглядит сле дующим образом. Процесс управления разбивается на этапы. Этап с номе ром n начинается в момент n 1 + 1 и оканчивается в момент n. В момент, предшествующий началу очередного этапа, определяется номер стратегии, принадлежащей множеству, из которой будут взяты правила для примене ния на данном этапе. Этот номер равен значению случайной величины n.
Продолжительность этапа равна n + n и зависит, следовательно, от номера этапа и от оценки качества применяемой стратегии, полученной в течение первых n тактов.
Интересно отметить, что на каждом этапе стратегии перебора в течение n тактов (с ростом значения n это будет подавляющая часть времени) т е кущая информация не обрабатывается.
В разделе 3.3 с помощью метода перебора решена задача построения адаптивной стратегии для класса регенерируемых объектов (доказана соот ветствующая теорема). В разделе 3.4 доказана аналогичная теорема с более сильным результатом для класса однородных конечных связных частично наблюдаемых марковских цепей.
В разделе 3.5 рассмотрен еще более узкий класс графов с детерминиро ванными переходами между конечным множеством ненаблюдаемых вершин и доходами, связанными с пребыванием в вершинах. Количество вершин не известно. Доказана теорема о том, что с т р а т е г и я п е р е б о р а о б е с п е ч и в а е т для любого такого объекта п р е д е л ь н ы й с р е д н и й д о х о д, р а в ный тому, который можно было бы получить, располагая возможностью полного наблюдения.
Глава 4 посвящена изложению нового направления в развитии известной концепции марковского процесса принятия решений. Предложенный подход основан на анализе целевой функции предельного среднего дохода и на яв ном аналитическом выражении для градиента этой функции. Сформулирован базовый алгоритм градиентной оптимизации целевой функции. Сделаны важные с точки зрения приложений обобщения на случай неполного наблю дения и на ситуацию, когда взаимодействие с объектом осуществляется рас пределенным образом. Важнейшее значение для эффективного применения градиентных алгоритмов имеет способ оценки градиента целевой функции.
Если переходные матрицы процесса неизвестны, то градиент не может быть вычислен и необходимы его оценки по результатам наблюдений. В этом слу чае градиентный алгоритм превращается в адаптивную стратегию.
Градиентный подход в марковском процессе принятия решений появился позже других методов. Первые из известных работ этого направления11 ско рее «обозначали желание» двигаться по градиенту, чтобы оптимизировать целевую функцию, и не дали конструктивных алгоритмов. Основная форму ла для градиента была опубликована в 1989 г.12, и там же был указан путь ее использования, в том числе в условиях неполного наблюдения и распреде ленного характера взаимодействия. Начиная примерно с середины 90-х го дов, за рубежом появилось много публикаций, связанных с градиентным подходом13,14. Исследования, которые излагаются в диссертации, проводи лись независимо от этих работ и не имеют среди них аналогов.
В разделе 4.1 рассматривается однородная управляемая связная марков ская цепь со счетным множеством состояний X, и конечным множеством действий Y. Вероятность перехода в состояния i при условии, что цепь нахо дится в состоянии j и выбрано действие k обозначается Qij ). Одношаговый (k доход в состоянии i при выборе действия k считается детерминированным и обозначается Gi(k ).
Пусть 0 Y. Однородную марковскую стратегию можно отождествить с матрицей S с элементами Si(k ), которые означают вероятность выбора дейст вия k Y\{0} при условии, что в предыдущий момент система находилась в состоянии i. Для любого 0 такого, что |Y|· 1, определим множество стратегий S = S : Si( k ) 1, Si( l ), i X, l Y \ {0} и положим k 0 S = US. S S, Если то матрица Р = P(S) с элементами Si( k )Qijk ) + 1 Si(k )Qijk ) Qij0) ( ( ( Pij = является переходной матрицей k 0 k обычной (неуправляемой) марковской цепи с множеством состояний X.
Предполагается, что если S S, то цепь P является апериодической эргоди ческой с эргодическим классом X, и поэтому предельный средний доход за El-Fattah Y. M. Gradient approach for recursive estimation and control in finite Markov chains // Adv. Appl. Probab., 13. – 1981. – С. 778–803.
Работа [8] в списке литературы, приведенном в конце автореферата.
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.
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.
стратегию S равен W (S ) =, где – вектор-строка предельных вероятно стей состояний, а – вектор-столбец с компонентами i = Gi + Si (Gi Gi ).
( 0) (k ) (k ) ( 0) k Доказана теорема об унимодальности функции W(S) на множестве S.
При некоторых дополнительных предположениях доказан следующий ос новополагающий результат.
Теорема. Частные производные предельных вероятностей (S), S S, = a ( b ) P t, где (b) – вектор-строка с ком конечны и имеют вид a a S ab ) ( t = понентами ( b ) = Qaj ) Qaj ), a X, b Y\{0}. Частные производные пре (b ( aj дельного среднего дохода задаются формулами ( W ( S ) = a ( b ) P t + Gab ) Ga0).
( a S ab ) ( t =0 Выражение для частных производных целевой функции допускает ясную интерпретацию. Пусть H i( k ) ( n ) означает средний доход к моменту n, кото рый получается, если начальное состояние цепи (в момент 0) было i и при этом было выбрано действие k. Тогда с точки зрения критерия максимизации предельного среднего дохода следует увеличить (уменьшить) вероятность выбора в состоянии i действия k за счет уменьшения (увеличения) вероятно ( ) сти выбора действия l, если H kl = lim H i( k ) ( n ) H i( l ) ( n ) 0 ( H kl 0). По n добные соображения открывают путь для построения алгоритмов оптимиза ции марковского процесса принятия решений.
В разделе 4.3 установлены некоторые дополнительные свойства целевой функции W(S). В разделе 4.4 получено другое удобное для применения пред ставление частных производных предельного среднего дохода.
В разделе 4.5 изучается способ отыскания максимума функции W(S) на замкнутом выпуклом множестве S, который заключается в построении ре куррентных алгоритмов градиентного типа. Пусть цепь имеет конечное мно жество состояний. Рассмотрим последовательность S t +1 = [ S t + at vt ], где S t S, at – заданная числовая последовательность, vt – некоторая случай ная последовательность той же размерности, что и S t, [] – оператор про ектирования на множество S, S 0 – фиксированная точка из множества S.
Последовательность St задает стратегию, которую обозначим через и назо вем градиентной адаптивной стратегией. Согласно стратегии, если цепь в момент t находится в состоянии i, то выбор управления осуществляется с по мощью распределения, содержащегося в i-ой строке матрицы St. Это рас пределение является, вообще говоря, разным в разные моменты времени, по этому стратегия неоднородная. Если последовательность vt зависит не только от текущего состояния цепи, но и от предыдущих состояний и, воз можно, от предыдущих действий, то стратегия не является марковской. По следовательность vt играет роль оценки градиента. Доказан следующий ре зультат относительно свойств градиентной адаптивной стратегии.
Теорема. Пусть – градиентная стратегия и пусть числовая последо вательность at подчиняется условиям at =, at2, а последова тельность случайных векторов vt с измеримыми относительно предыстории компонентами удовлетворяет неравенству vt W ( St ) bt,почти навер ное относительно меры, порожденной стратегией. Пусть числовая по следовательность bt такова, что at bt. Тогда почти наверное выпол няются равенства lim W ( St ) = max W ( S ), lim d ( St, S*) = 0, где S* – множе t t S S ство точек максимума функции W(S) на множестве S, а d – расстояние от точки до множества в евклидовой метрике.
В разделе 4.6 классическая модель процесса принятия решений обобщена на ситуацию, которая весьма распространена на практике. Обобщение каса ется двух направлений: 1) распределенного взаимодействия и 2) отсутствия полной наблюдаемости. Наглядное описание новой схемы в простейшем случае выглядит следующим образом (рис. 3). Предполагается, что в системе имеются две «подсистемы», каждая из которых выбирает свое действие – па раметр. Результирующее действие системы, является функцией от этих пара метров.
наблюдение z = (u, v) СУБЪЕКТ u v подсистема 1 подсистема параметр параметр действие y = f(, ) ОБЪЕКТ Рис. 3. Распределенное взаимодействие при неполном наблюдении.
Выбор значения параметра внутри каждой подсистемы осуществляется в зависимости от собственных наблюдений c помощью собственных стратегий, которые опираются на эти наблюдения. Получена формула для частных про изводных целевой функции по компонентам стратегий подсистем, которая подобно приведенной выше основной формуле, удобна для практической реализации аналога градиентной стратегии Градиентный подход к оптимизации на марковских цепях оказался воз можным благодаря конструктивной формуле для частных производных целе вой функции по компонентам стратегии управления, которая переносится также на случай неполного наблюдения состояний цепи. Однако для реали зации алгоритма необходимо знать переходные матрицы процесса. Если та кой информации нет, то возникает проблема оценивания градиента по ре зультатам наблюдения за траекторией процесса, а алгоритм превращается в адаптивную стратегию. В разделе 4.7 разработаны эффективные методы оценки градиента. Рассмотрим градиентную стратегию, порождающую по следовательность марковских правил St. Обозначим через = (i), i X, се мейство условно независимых случайных величин, принимающих значения из интервала (0, 1), и положим t = ( xt ), mt = M(i ) i ( S t ), где ( St ) – i X предельное распределение, соответствующее марковскому правилу St. Отме тим, что если t = g t, то речь идет об оценке предельного среднего дохода W( St ), соответствующего тому марковскому правилу, которое предписывает алгоритм в момент t. Если же t = I{ xt = i}, то оценивается предельная вероят ность состояния i, соответствующая марковскому правилу St. С учетом того, что величины St, изменяются, вообще говоря, в каждый момент, а оценить надо величину, усредненную по предельному распределению, задача по строения таких оценок оказывается нетривиальной. Алгоритм оценивания величины mt строится следующим образом.
Определим последовательности, t, t и t следующими формулами:
t = 1 (t + 1), 0 1 ;
t +1 = t t t + t, 0 = 0 ;
t +1 = t t + 1, 0 = 1.
В качестве оценки величины mt рассмотрим величину µ t = t t.
Теорема. Пусть – градиентная стратегия, и пусть выполнено условие || S t +1 S t || C t a, где C 0, max(, ) a 1. Тогда | µ t mt | = O (t b ) поч ти наверное относительно меры, порожденной стратегий, где b (0, min{, a }).
В разделе 4.8 приведены результаты вычислительного эксперимента, де монстрирующих то свойство оценок градиента, которое делает адаптивную градиентную стратегию особенно эффективной. В рассмотренном примере значение аргумента St (марковского правила) изменяется с постоянной ско ростью, что приводит к постоянному изменению значения градиента. Резуль таты эксперимента показывают (рис. 4), что оценка градиента достаточно хо рошо «отслеживает» траекторию точного значения величины W ( St ). Мас штаб по оси времени зависит от размерности объекта, которая, однако, не влияет на качественную картину графиков.
Оценка градиента целевой функции 0, 0, 0, 0, такты точное значение оценка относительная погрешность Рис. 4. Оценка градиента целевой функции.
Глава 5 посвящена практическому применению разработанной теории. В ней описана общая методология обработки информации и принятия решений в распределенной системе взаимодействия с частично наблюдаемым объек том, о котором имеется неполная априорная информация. На основе этой ме тодологии осуществляется синтез информационных технологий для опера тивного управления трафиком в цифровой сети с коммутацией каналов. Ос новные положения, которые содержит предлагаемый подход, изложены в разделе 5.1. Они иллюстрируются рисунком 5 и заключаются в следующих пунктах.
1. Выбор подходящего масштаба времени и выделение тактов, то есть указа ние последовательности моментов, в которые будет происходить взаимо действие с объектом.
2. Определение информационного обмена с объектом. Этот пункт включает описание множества воздействий на объект, а также множества доступ ных на каждом такте наблюдений. Кроме того, необходимо установить, что будет являться одношаговым доходом.
3. Декомпозиция процесса взаимодействия, то есть разбиение системы на подсистемы с указанием множества действий и множества наблюдений, доступных для каждой подсистемы на одном такте, а также характера взаимодействия подсистем. На рис. 3 показан пример такой распределен ной структуры, в которой отдельные части системы располагают различ ными компонентами наблюдения и имеют свои наборы параметров, зна чения которых должны устанавливаться на каждом шаге. «Фактическое» воздействие на объект является результатом решений, принимаемых от дельными подсистемами.
4. Максимально возможное априорное сужение множества допустимых стратегий для каждой подсистемы. Эта процедура может осуществляться с помощью аналитических методов, экспертных оценок, учета технологи ческих особенностей и пр.
5. Параметризация множеств действий для каждой подсистемы с помощью конечных наборов конечнозначных параметров.
6. Построение имитационно-аналитической модели включает:
• анализ априорной информации об объекте с целью определения струк туры и набора параметров взаимодействия;
• создание аналитических методов, позволяющих рассчитывать параметры взаимодействия с объектом;
• написание формальной имитационной модели на специализированном языке параллельных процессов;
• разработку методов идентификации параметров модели;
• построение компьютерной программной системы.
1. Выбор масштаба времени Использование априорной ин- 2. Определение состава и объема формации информационного обмена 3. Декомпозиция системы 4. Сужение множества допусти Построение мых стратегий формальной модели 5. Параметризация воздействий Идентификация параметров 6. Построение имитационно Компьютерная аналитической модели реализация 7. Применение универсальных адаптивных стратегий Использование оперативной информации Рис. 5. Схема обработки информации в распределенной системе взаимодей ствия с частично наблюдаемым объектом при неполной априорной ин формации;
– информационные потоки.
При выполнении пунктов 1–6 используется максимально доступная апри орная информация об объекте.
7. Применение адаптивных стратегий для обработки информации и оптими зации выбора параметров, ответственных за принятие одношаговых решений.
Разработанная методология предполагает два способа реализации: прямое взаимодействие с объектом (режим on-line) и использование имитационно аналитической модели (режим off-line). Наличие имитационной модели не является обязательным в тех случаях, когда взаимодействие с объектом про исходит «достаточно быстро» и «достаточно долго». Но и в этих случаях роль имитационной модели всегда положительна, поскольку появляется воз можность исследовать различные сценарии, избегая рисков непоправимых ошибок.
Реализация адаптивных алгоритмов является однотипной для каждой из подсистем, образованных в результате выполнения пункта 3. При этом обра ботка информации имеет двухуровневую организацию (рис. 6). На верхнем уровне накопленная к моменту t оперативная информация (то есть доступная для данной подсистемы часть наблюдений за объектом) обрабатывается с це лью определения сценария, которому удовлетворяет имеющаяся предысто рия. Формально это означает отображение f предыстории наблюдений глуби ны d, ztt d +1 = ( zt, zt 1,..., zt d +1 ) в конечное множество сценариев C = {1,..., C}. Количество сценариев, отображение f, а также глубина учиты ваемой предыстории d определяются на предварительных этапах 3 и 4. Каж дому сценарию соответствует адаптивная стратегия Ac (например, стратегия перебора или градиентная стратегия), которая представляет собой последовательность правил, отображающих предысторию доходов в конеч ное множество значений параметров данной подсистемы. Если на t-м такте оперативная информация Выбор решающего z1, z2, …, zt правила c = f(zt, zt–1, …, zt–d+1) AC Ac A1 ••• ••• асинхронные новые значения параметров адаптивные подсистемы алгоритмы Рис. 6. Двухуровневая реализация адаптивной стратегии обработки инфор мации и принятия решений в подсистеме.
реализовался сценарий c = ct, то решающим правилом, которое определяет значение параметров подсистемы на следующем (t+1)-м такте, является пра вило из стратегии Ac. Таким образом, нижний уровень обработки оператив ной информации представляет собой совокупность алгоритмов { Ac, c C}, которые работают, вообще говоря, в асинхронном режиме. Принимаемое на каждом такте решение определяется ровно одним из этих алгоритмов.
В качестве примера реального приложения разработанной теории в дис сертации рассмотрена проблема оперативного управления вторичной теле фонной сетью в режиме, приближенном к реальному времени, в том числе при возникновении внештатных ситуаций. Рассмотрена многоуровневая сеть коммутации каналов, которая удовлетворяет рекомендациям Международно го союза электросвязи15 и аналогична по функциям и масштабам междуго родной сети РФ. На ее примере демонстрируются основные черты методоло гии и технологии моделирования большой системы и применения адаптив ных методов обработки информации и принятия решений.
Все данные относятся к периоду проведения работ (1999–2001 гг.). Мате риалы соответствуют существовавшей на этот период концепции единой ин тегрированной автоматизированной системы управления для существующей и перспективной цифровой сети связи АО «Ростелеком» АСУ ЦС. Указанная концепция отвечала всем современным требованиям и учитывала опыт ве дущих разработчиков систем управления сетями связи.
Ключевым моментом синтеза информационных технологий для оператив ного управления трафиком в цифровой сети с коммутацией каналов является применение разработанных адаптивных алгоритмов для коррекции маршрут ных таблиц и оптимизации дополнительных управляющих воздействий. В то же время процесс такого синтеза является многоплановым и включает не сколько этапов и составных частей:
• изучение реального объекта и анализ его основных технологических осо бенностей в контексте поддержки принятия решений по управлению тра фиком;
• создание упрощенной математической модели, отражающей важнейшие особенности объекта (без учета ряда специфических деталей), постановку и решение задач оптимизации;
• разработка методов идентификации матрицы тяготения по результатам сетевых измерений;
• формальный синтез объемлющей имитационной модели, включающей та кие черты объекта, которые не поддаются аналитическому изучению;
• анализ специфических средств управления трафиком с позиций общей теоретической модели адаптивной обработки информации и применение адаптивных алгоритмов;
• компьютерная реализация комплекса моделей.
Recommendation Е. 412 (10/92). Telephone network and ISDN. Quality of service, network management and traffic engineering. Network management controls. – ITU, 1993.
В разделе 5.2 сконцентрировано описание основных аспектов организа ции трафика в исследуемой системе. Приведена общая характеристика АСУ ЦС ОАО «Ростелеком» и детально перечислены основные объекты сети. Да но описание подсистемы управления вторичной телефонной сетью с указа нием ее управляемых объектов. Разобраны функции блока управления тра фиком (рис. 7). Анализ показал, что специфика современных телефонных се тей, определяемая как рекомендацией E.412 Международного союза электро связи, так и реальными параметрами телефонных сетей РФ, не позволяет ис пользовать «напрямую» ни одну из описанных в научной литературе моделей телефонных сетей. Эти модели, как правило, используют ограничительные предположения, далеко не всегда выполняющиеся на практике;
в частности, эти предположения не выполняются и в сетях, удовлетворяющих рекоменда ции E.412. В связи с этим была поставлена задача создания сложной много уровневой модели, включающей имитационную модель собственно телефон ной сети с учетом всей специфики ее деятельности и алгоритмы динамиче ского управления сетью, использующие как имитационную, так и аналитиче скую модель сети.
Мониторинг состояния сети Блок Контроль База обнаружения трафика данных аномалий Вычисление Блок Статистические параметров корреляции расчеты Измерения трафика Управление маршрутизацией Сбор данных из сети УПРАВЛЯЕМАЯ СЕТЬ Рис. 7. Основная функциональная архитектура блока управления трафиком.
На основании сделанного анализа были решены задачи, соответствующие выполнению пунктов 1–4 общей методологии, описанной в предыдущем раз деле. В частности, основная последовательность моментов принятия опера тивных решений (масштаб времени) была определена как последователь ность моментов появления вызовов. Глобальное «действие» на одном такте заключается в указании маршрута соединения для поступившего вызова, ли бо в отказе на соединение. Это действие сопряжено с рядом промежуточных решений, то есть имеет место декомпозиция процесса принятия решений, ко торая получается естественным образом и связана с технологией организа ции трафика в сети. На рис. 8 и 9 показана схема управления установлением соединений. Маршрут соединения отдельного вызова прокладывается посте пенно, от узла возникновения вызова к узлу назначения. Локальное решение в каждом узле заключается в выборе пучка продолжения маршрута. Это ре шение принимается на основании маршрутной таблицы, соответствующей данному вызову, а также в зависимости от дополнительных управляющих воздействий, которые могут быть осуществлены в данный момент. В свою очередь параметры маршрутных таблиц и дополнительных управляющих воздействий регулируются на более высоком уровне. Таким образом, приня тие решений в системе происходит распределенным многоуровневым обра зом в асинхронном режиме. Общее количество локальных подсистем, тре бующих последовательного оперативного изменения параметров (с учетом количества узлов в сети и типов вызовов) достигает порядка десятков тысяч.
новый узел да Выбор Пучок исходящего возникновение найден?
пучка в узле вызова нет соединение блокировка (достигнутый узел является узлом-адресатом) Рис. 8. Последовательное установление маршрута соединения.
В разделе 5.3 построена и проанализирована математическая модель управляемой сети с коммутацией каналов. Связанные с ней постановки задач обладают тем несомненным преимуществом, что допускают аналитическое решение. Модель дает возможность осуществить первоначальное исследова ние объекта, пренебрегая некоторыми реальными, но трудно формализуемы ми факторами.
Модель базируется на предположениях об экспоненциальном характере распределений и названа эрланговской. Сеть представляется в виде множест ва узлов, соединенных между собой пучками каналов (линиями). Пучок ка налов l, 1 l L, имеет емкость nl. На узлы поступают пуассоновские потоки вызовов с параметрами m, m = 1, … M. При поступлении вызова в сети при нимается одно из двух решений: либо этот вызов блокируется (получает от каз), либо ему предоставляется маршрут для соединения, продолжительность занятия которого для вызовов m-го типа имеет экспоненциальное распреде ление с параметром µ m. Для каждой тяготеющей пары определено множест во из Km возможных маршрутов соединения. Состоянием сети в момент t является вектор x (t ) = {xmk (t ), 1 k K m, 1 m M }, компонента xmk (t ) ко торого означает число вызовов m-го типа, которые в момент t имеют соеди нение по маршруту k. Множество возможных состояний сети имеет вид M Km X = x = ( x mk ) : a mk x mk nl, 1 l L;
x mk 0, 1 k K m, 1 m M, (l ) m =1 k = Управление параметрами Управление параметрами маршрутных таблиц дополнительных воздействий ТИП ВЫЗОВА ТИП ВЫЗОВА ТИП ВЫЗОВА ТИП ВЫЗОВА Поиск пучка в маршрутной таблице блокировка нет Пучок нет найден?
да Есть дополнительные воздействия?
да нет Есть в пучке сво- Применение дополнительных бодный канал? воздействий да соединение Рис. 9. Поиск пучка для продолжения соединения вызова данного типа.
(l ) где amk равно 1, если линия l встречается в k-м маршруте соединения для m го типа потока, и 0 – в ином случае. Соединение вызовов осуществляется с помощью набора векторов u = {umk, 1 k K m, 1 m M }, где компонента umk означает вероятность выбора k-го маршрута для вызова m-го типа. Мно жество допустимых стратегий имеет вид Km U = u : u mk = 1, u mk ;
1 m M, k =1 где 0 – заданное число. Функция относительных предельных потерь для m-го типа потоков определена как ( m ) = 1 lim t 1 Z um ) (t ), где Z u( m ) (t ) оз ( u m t начает математическое ожидание суммарного числа блокировок для вызовов m-го типа за время от 0 до t по мере Pu, и может быть также выражена в виде um ) = 1 Pu( m ), где Pu(m ) – предельная вероятность того, что вызов m-го ти ( m па получит отказ.
Теорема. А) Если маршрутизация осуществляется с помощью стратегии u U, 0, то предельная вероятность нахождения процесса x(t) в со стоянии x = {xijm ) } существует и равна ( (u ) x x = u, x = lim Pu ( x (t ) = x ) =, Cx!
t M Km M Km (x ) x, (u ) = ( m umk ), x! = xmk !, m = m.
x mk x где = µm x!
x X m =1 k =1 m =1 k = M (um) Б) Каждая точка локального минимума функции (u ) = на мно m = жестве U является точкой глобального минимума. Множество точек ми нимума функции Ф(u) связно.
В) Частные производные функции Ф(u) задаются формулой M (u ) = lim m cov ( xm (t ), xlk (t ) ), ulk t m = Km xmk (t ), cov( xm (t ), xnk (t )) = xm xnk x (t ) xm x xnk x (t ).
где xm (t ) = k =1 x X x X x X В разделе 5.3 получен также сходный результат для распределенных стра тегий маршрутизации, которые используют прием, известный в телефонии, как «откат». Для отыскания минимума функции потерь Ф(и) на множестве стратегий U предложено использовать градиентную стратегию, для которой доказана теорема, устанавливающая ее оптимизационные свойства.
Разрабатываемая комплексная модель вторичной телефонной сети предна значена для включения в общий блок управления трафиком. В ее задачу, в частности, входит анализ ситуации и выработка рекомендаций по управляю щим воздействиям в сети. Существенной особенностью является то, что мо дель рассчитана на работу в реальном времени. При этом информационный обмен между моделью и остальным блоком управления трафиком осуществ ляется каждые 15 минут. Иными словами, по истечении каждых 15 минут комплексная модель получает из основного блока новую информацию о сети и должна передать в основной блок подготовленные данные анализа и реко мендации по управлению.
Одним из существенных звеньев комплексной модели является компью терная модель, имитирующая процесс поступления и обслуживания вызовов.
Имитационная модель является тем промежуточным объектом, на котором осуществляется работа алгоритмов анализа и оптимизации перед тем, как пе редать результаты их работы в основной блок. При этом, естественно, особое значение имеет точность, с которой имитационная модель воспроизводит фактическую картину трафика в сети.
Основным и единственным "входом" имитационной модели (если не счи тать структуру сети) является матрица тяготения. В настоящее время не пре дусмотрены и не проводятся прямые измерения интенсивностей входных по токов, поэтому необходимо их реконструировать по имеющимся измерени ям. Эта реконструкция должна занимать сравнительно небольшое время, для того чтобы в отведенный пятнадцатиминутный интервал успеть «запустить» имитационную модель и дать возможность отработать основным алгоритмам анализа и оптимизации. Так возникает дополнительная (по отношению к ос новным «оптимизационным» проблемам) задача идентификации параметров входных потоков по результатам косвенных измерений. В разделе 5.4 изло жен алгоритм, разработанный для восстановления интенсивностей входных потоков по результатам измерений. Формальная постановка задачи предпо лагает, что (1) отказы на пучках независимы;
(2) потоки, поступающие на пучки, являются пуассоновскими. При этих предположениях выведены ре куррентные процедуры расчета вероятностей отказа и потоков на пучках при заданных интенсивностях входных потоков. Идентификация интенсивностей входных потоков осуществляется в результате выполнения итеративной про цедуры, которая минимизирует функцию невязки между измеренными и рас считанными значениями вероятностно-временных характеристик.
В разделе 5.5 изложена формальная имитационная модель сети с комму тацией каналов. В качестве инструмента моделирования выбран аппарат тео рии параллельных процессов16, к числу достоинств которого относятся лако ничность, удобная для программирования форма представления, возмож ность легко изменять, добавлять и удалять отдельные блоки, наличие мате матических средств для проверки логической правильности модели.
Были учтены следующие особенности, присущие реальной сети:
• непуассоновские входные потоки и произвольные распределения времен ожидания;
• повторные вызовы в случае блокировки;
• ненадежность каналов;
• произвольное управление соединением, в т. ч. возможность отката и перенаправления, постановка в очередь;
• значимая затрата времени на соединение;
• сбор информации о сети и пр.
Ч. Хоар. Взаимодействующие последовательные процессы. – М.: Мир, 1989.
На рис. 10 приведены некоторые объекты имитационной модели, описан ные на языке параллельных процессов.
СЕТЬ = || m.ТРАФИК || k.КАНАЛ || СЧЕТЧИКИ || ВРЕМЯ mM kK М : ТРАФИК = := +1;
ПАУЗА0();
(.ВЫЗОВ ТРАФИК) X : ВЫЗОВ = в_сеть УЗЕЛ X : СОСТОЯНИЕ_ВЫЗОВА = (в_сеть µ := I;
:= 0 | в_узел :=.E;
µ := ^µ | откат :=.B;
µ := (µ’)’;
:= (µ’)0);
СОСТОЯНИЕ_ВЫЗОВА X : УЗЕЛ = в_узел (в_канал УЗЕЛ | блокировка ПОВТОРНЫЙ_ВЫЗОВ | откат ОТКАТ | соединение ЗАНЯТИЕ) X : ОЖИДАНИЕ = в_узел (if.с.С then (такт ОЖИДАНИЕ) else ПОПЫТКА_СОЕДИНЕНИЯ) X : ОБРАБОТКА_ВЫЗОВА = := R();
case of 1: в_канал 2: блокировка 3: откат 4: соединение end;
КОНЕЦ X : ПОВТОРНЫЙ_ВЫЗОВ = (m, m.).ВЫЗОВ КОНЕЦ X : ОТКАТ = if = I then ПОВТОРНЫЙ_ВЫЗОВ else (µ := (µ) ;
:=.B;
УЗЕЛ) X : ЗАНЯТИЕ = ПАУЗА0(Т);
из_сети КОНЕЦ КАНАЛ(k) = ({х.в_канал, хХ, k = x.} КАНАЛх(k)) ОТКАЗ_КАНАЛА(k) КАНАЛх(k) = ({х.из_канала, k = x.} КАНАЛ(k)) ОТКАЗ_КАНАЛА(k) ОТКАЗ_КАНАЛА(k) = сбой(k) исправен(k) КАНАЛ(k) X М : ПАУЗАk(t) = такт (if k t then ПАУЗАk+1(t) else КОНЕЦ) ВРЕМЯt = такт ВРЕМЯt+ Рис 10. Фрагмент имитационной модели на языке параллельных процессов.
Раздел 5.6 посвящен детальному обсуждению механизмов принятия опе ративных решений в сети и их параметризации, то есть представлению в том виде, который позволяет применить разработанные адаптивные алгоритмы.
Под оперативным решением понимается, прежде всего, выбор маршрута соединения вызовов, который осуществляется с помощью маршрутных таб лиц. При существующем положении маршрутные таблицы являются объек тами, которые составляются на этапе проектирования, а их непосредственное изменение в процессе эксплуатации является технически трудно осуществи мой процедурой. Коррекция маршрутизации, необходимость в которой воз никает, например, в случае возникновения нештатной ситуации на сети, осу ществляется с помощью дополнительных управляющих воздействий. В то же время анализ этих воздействий показывает, что применение большинства из них фактически означает временное изменение маршрутной таблицы. По этому коррекцию маршрутизации удобно трактовать, прежде всего, как кор рекцию маршрутных таблиц, возможность которой была включена в модель.
Разработано понятие обобщенной маршрутной таблицы, описание кото рой сводится к набору стохастических векторов p = {p0, p1, …, pK}. Каждый вектор pi представляет собой вероятностное распределение на некотором ко нечном множестве и участвует определенным образом в «прокладывании» маршрута поступившего вызова (разным типам вызовов в различных узлах соответствуют разные обобщенные маршрутные таблицы). Фактическое «решение» – маршрут – появляется в результате выбора серии "вспомога тельных" действий, выбираемых независимо друг от друга с помощью ком понент набора p. Такая ситуация укладывается в разработанную схему рас пределенного принятия решений при неполном наблюдении. Для оптимиза ции параметров обобщенных маршрутных таблиц используются адаптивные стратегии, построенные на основании полученных теоретических результатов.
Коррекция маршрутных таблиц является инструментом практически дос таточным для того, чтобы реализовать функции регулирования трафика в случае возникновения внештатных ситуаций. Это положение подтверждается на многочисленных вычислительных экспериментах с компьютерной имита ционной моделью. Однако поскольку на существующих станциях реакция на изменения в сети технически допустима в виде дополнительных управляю щих воздействий, то при разработке комплексной модели решалась задача оптимизации этих воздействий.
Управляющими воздействиями в сети являются: блокировка кода, проре живание вызовов, пропуск, отмена направления, перенаправление каналов, временное перенаправление потоков по обходному пути, выборочное резер вирование каналов. Общая схема оптимизации имеет тот же вид, что и для обобщенных маршрутных таблиц, и сводится к коррекции одного или не скольких стохастических векторов, параметризирующих то или иное допол нительное управляющее воздействие.
Раздел 5.7 является интегрирующим в изложении комплексной модели управляемой цифровой сети с коммутацией каналов. В нем дается детальное описание структуры данных, входных параметров и основных блоков модели в том виде, который предшествует непосредственному написанию компью терных кодов. Приведены принципиальные схемы имитации работы сети в двух режимах: без коррекции и с коррекцией маршрутных таблиц и управ ляющих воздействий. Подробно изложены наиболее важные блок-схемы и процедуры, имеющие принципиальное значение для качества и быстродейст вия программной системы, в том числе: создание и обработка вызовов, уста новление соединения, работа блока коррекции (рис. 11).
В Приложении содержится описание варианта программной системы, ко торый послужил прообразом промышленной версии, переданной заказчику (ОАО Ростелеком). Кроме того, приложенный вариант явился инструментом для экспериментального исследования разработанной методологии и техно логии синтеза адаптивных стратегий. На рис. 12 изображены фрагменты ин терфейса этой программы.
Начальное приближение Имитация без Оценка целевой коррекции функции Регуляризация Выбор объектов дополнительных воздействий на объектах управления Округление Конец Цикл коррекции Рис. 11. Функциональная схема блока коррекции.
Компьютерная модель позволяет имитировать работу сети большого мас штаба в двух режимах: с коррекцией и без коррекции маршрутизации и до полнительных управляющих воздействий.
Рис. 12. Фрагменты интерфейса программной системы моделирования и оптимизации трафика междугородной телефонной сети Представление о возможностях программы дает следующий пример.
Входные данные примерно соответствуют параметрам телефонной сети Рос сии (на период 2000 г.). Сеть содержит 115 узлов, 2390 пучков и 6683 тяго теющие пары. Исходных маршрутных таблиц – 11140. Исходная маршрути зация также соответствует реальной (и, следовательно, была настроена на этапе проектирования и в ходе эксплуатации), поэтому можно считать ее близкой к оптимальной. В эксперименте проводилась коррекция 1110 управ ляемых маршрутных таблиц на управляемых стациях коммутации (без при менения дополнительных управляющих воздействий), что соответствует на стройке более 10 000 параметров. Результаты эксперимента на ПК с тактовой частотой 2,4 ГГц:
• время выхода на стационарный режим – 2 мин;
• количество имитированных вызовов – около 10 млн.;
• относительное уменьшение вероятности отказов в сети после коррекции маршрутных таблиц – 6%.
Глава 6 посвящена описанию приложения разработанной методологии для синтеза информационной технологии моделирования и оптимизации сис темы распределенных вычислений.
В основе проблематики лежит идея обеспечить коллективный доступ к вычислительным ресурсам для более эффективного их использования. Новые технологии в этой области выступают, главным (но отнюдь не единствен ным) образом, под общим названием «системы Грид». «Грид – это про граммно-аппаратная инфраструктура, которая обеспечивает надежный, ус тойчивый, повсеместный и недорогой доступ к высокопроизводительным компьютерным ресурсам»17.
Среди задач, возникающих в связи с проблематикой синтеза и эксплуа тации систем распределенных вычислений и, в частности, технологии Грид, имеется универсальная проблема, присущая всем оттенкам концептуальных подходов и всем примерам практических воплощений подобных систем. Эта проблема заключается в поиске ответа на вопрос, как следует распоряжаться вычислительными ресурсами, то есть куда, в какие моменты и сколько сле дует посылать заданий, чтобы добиться эффективного использования ресур сов с точки зрения различных потребителей, а также с точки зрения различ ных показателей производительности ресурсов. Решение этой проблемы, по крайней мере, в части оперативного управления ресурсами, видится в приме нении адаптивных методов.
В разделе 6.1 приведено описание модели оперативного управления рас пределением ресурсов на стадии непосредственного выполнения заданий, поступающих от потребителей. Основными объектами модели являются: за данное число распределенных вычислительных ресурсов, фиксированное число удаленных от ресурсов потребителей и потоки заданий, которые воз никают у потребителей и которые состоят из случайного количества задач, упорядоченных с точки зрения очередности их выполнения (рис. 13). В мо дели учитывается сетевой аспект тем, что при передаче пакетов от потреби телей к ресурсам и обратно происходят задержки, которые зависят от объема передаваемой информации и от «расстояний» между потребителями и ресур сами. Описаны механизмы возникновения заданий, отправки их на ресурсы и получения обратно, выполнения заданий на вычислительных мощностях.
Фостер Я. Что такое Грид? Три критерия. http://www.gridclub.ru/library/publication.2004 11-29.5830756248/publ_file.
Рис. 13. Выполнение задания в модели сети Грид.
Раздел 6.2 посвящен постановке задачи и описанию адаптивных алгорит мов обработки информации для оперативного распределения ресурсов при неполной информации. Оперативные решения заключаются, прежде всего, в назначении ресурсов для задач, поступающих от разных пользователей. Кро ме того, особенности, процесса обслуживания, в частности, возможность не предвиденного возвращения невыполненных задач, требуют оптимизировать объемы посылаемых пакетов задач. Оба типа решений представляются как выбор из конечного множества вариантов, и задача сводится к нахождению оптимальных значений распределений на этих множествах для различных пользователей и разных значений наблюдаемой части системы. Формально задача укладывается в схему частично наблюдаемой марковской последова тельности и адаптивного распределенного принятия решений, которая была изучена в главе 3. В качестве основного одношагового показателя качества функционирования системы (одношагового дохода) выступает объем выпол ненных задач, возвращенных пользователю на данном такте. Соответствую щим критерием качества решений является производительность, то есть от ношение количества выполненных заданий к промежутку времени функцио нирования системы. Дополнительно рассмотрены одношаговые финансовые затраты, а также количество задач, потерянных (не обслуженных) на одном шаге. В этом случае получаются целевые функции, обозначающие соответст венно (предельные средние) затраты и (предельные средние) отказы. Рас смотрены два основных варианта принятия решений: централизованный, ко гда цель заключается в том, чтобы повысить среднюю производительность всей системы, и децентрализованный, когда каждый потребитель пытается увеличить собственную производительность. Адаптивные алгоритмы пред ставляют собой рекуррентные последовательности, сконструированные в главе 3, в которых вероятностные распределения выбора тех или иных управлений корректируются на основании накопленной статистики. Рас смотрены модификации адаптивных стратегий при различных предположе ниях о доступной наблюдению информации.
В разделе 6.3 приведены результаты вычислительных экспериментов с программной системой, в которой реализована модель распределенной вы числительной среды. Эта программа позволяет в широком диапазоне на страивать параметры модели, включая стратегии поведения участников сис темы, и проводить вычислительные эксперименты. Она является полезным инструментом для экспериментального исследования свойств системы, в ча стности, для сравнения свойств различных стратегий. Были изучены различ ные аспекты общих свойств адаптивных алгоритмов и поведения конкретной моделируемой системы. Рис. 14 позволяет увидеть типичную картину, когда адаптивная стратегия, после некоторого периода обучения в стационарной среде, выводит поведение системы на уровень, близкий к оптимальному. На до подчеркнуть, что определение оптимальной стратегии иными, нежели чем адаптивными методами, возможно лишь в исключительных случаях. Причи на в отсутствии аналитических методов и в большой размерности. Если до бавить сюда принципиальную неполноту априорной информации и естест венную неоднородность, присущую реальной системе, то использование адаптивного подхода выглядит практически неизбежным.
0, 0, 0, 0, 0, 0, 0, 1 2 3 4 5 6 7 8 9 10 время, 1=100000 тактов производительность адаптивной стратегии с момента начала моделирования производительность адаптивной стратегии за последние 100000 тактов максимально возможная производительность Рис. 14. Производительность адаптивной стратегии в сравнении с оптималь ной стратегией (стационарная среда).
Ситуации с неоднородными во времени средами моделировались особо.
На рис. 15 показан типичный пример, в котором на примере периодической среды сравнивается адаптивная стратегия и стратегия, которая представляет ся выгодной из соображений «здравого смысла». На рисунке различаются че тыре зоны, которые соответствуют резко отличающимся свойствам системы.
Эмпирическая стратегия (нижний график) оказывается более или менее эф фективной на первых двух этапах, уступая немного адаптивной стратегии. На следующих двух этапах преимущество адаптивной стратегии становится бе зоговорочным. На рисунке видны также области, на которых происходит приспособление адаптивной стратегии к резко изменившимся условиям.
Рис. 15. Производительность адаптивной стратегии в сравнении с эмпириче ской стратегией (периодическая среда).
В результате проведенных экспериментов установлено, что адаптивные алгоритмы • достаточно быстро находят оптимальную (неизвестную для них) страте гию поведения в тех случаях, когда оптимальная стратегия может быть определена априори;
• действуют результативнее, чем эвристические стратегии, в примерах, ко гда нет способа заранее и точно указать оптимальную стратегию;
• оказывают существенное положительное влияние на показатели качества, если их использовать для управления объемом посылаемых на обслужи вание пакетов задач;
• являются восприимчивыми к выбору критерия качества;
• эффективны в случаях централизованного и децентрализованного (игро вого) поведения участников.
РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ В диссертации решена актуальная проблема анализа, синтеза и примене ния адаптивных алгоритмов оперативной обработки информации и принятия решений для широкого класса технических систем с неполным информаци онным описанием и неполным наблюдением. В том числе получены сле дующие результаты.
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. Изучены возможности практического использования теории и указаны объекты приложений в областях инфотелекоммуникаций, производственных систем, искусственного интеллекта и других. Разработана методология прак тического применения информационных технологий моделирования и адап тивной обработки информации для широкого класса систем с неполным на блюдением. Разработана технология синтеза и реализации эффективных ал горитмов адаптивного принятия решений.
4. Получены результаты в области реализации разработанной теории и методологии для крупных прикладных проблем.
4.1. Решена задача оперативного управления трафиком в телекоммуника ционной сети с коммутацией каналов. Разработана совокупность моделей и информационных технологий для оперативной адаптивной обработки ин формации в сети с коммутацией каналов.
4.1.1. Построена эрланговская модель управляемой сети с коммутацией каналов, в ее рамках поставлена и решена задача минимизации средних потерь в сети.
4.1.2. Разработаны модель и технология восстановления матрицы тяготе ния по результатам сетеметрии.