Содержание к диссертации
Введение
1 Рандомизированные алгоритмы стохастической аппроксимации 9
1.1 Оптимизация дифференцируемых функций 10
1.2 Оптимизация функционала среднего риска 12
1.3 Методы на основе аппроксимации градиента 19
1.4 Рандомизированные алгоритмы стохастической аппроксимации 22
1.5 Модели со случайными величинами с бесконечной дисперсией и задачи оптимизации 25
1.5.1 Модель высокооптимизированной толерантности . 26
1.5.2 Модель присоединения с предпочтением 28
2 Свойства последовательностей оценок РАСА 31
2.1 Условия состоятельности и стабилизации оценок 31
2.2 Примеры задач 36
2.3 Состоятельность оценок в стационарном случае 40
2.4 Скорость сходимости 44
2.5 Стабилизация оценок в нестационарном случае 49
2.6 Доказательства теорем 1-5 54
3 Система управления загрузкой узлов распределенной вычислительной сети 71
3.1 Задача загрузки узлов распределенной сети 71
3.2 Управление с обратной связью 76
3.3 Имитационное моделирование 83
3.4 Доказательства теорем 7,8 83
Заключение 89
Литература 91
- Оптимизация функционала среднего риска
- Модель высокооптимизированной толерантности
- Скорость сходимости
- Управление с обратной связью
Введение к работе
Актуальность темы. Проблема оптимизации того или иного функционала встает во многих практических приложениях. Иногда экстремальные значения можно найти аналитически, однако зачастую инженеры имеют дело с неизвестным функционалом, значение которого можно только вычислять в задаваемых точках. При этом возможно появление неконтролируемых неопределенностей различной природы, как статистических, так и нерегулярных (например, неизвестных, но ограниченных, для которых традиционные предположения о статистической природе, независимости и центрированности не выполнены). Для неопределенностей статистической природы в современных практически значимых задачах финансовой математики, теории игр, распознавания биологических видов, в Интернет-системах, при планировании электросетей, предотвращении эпидемий и лечении инфицированных все чаще обоснованно предполагают степенное распределение, при котором может отсутствовать второй статистический момент.
В 50-е годы XX века для решения задачи стохастической оптимизации начинают использоваться методы стохастической аппроксимации Роббинса-Монро и Кифера-Вольфовица. Они были развиты в работах B.C. Боркара, М. Вазана, Ю.М. Ермольева, Дж. Ина, В.Я. Катков-ника, Т.П. Красулиной, Г. Кушнера, М.Б. Невельсона, А.С. Немиров-ского, Ю.Е. Нестерова, А.С. Позняка, Б.Т. Поляка, Р.З. Хасьминского, Я.З. Цыпкина, В. Фабиана, В.Н. Фомина, А.Л. Фрадкова, Д.Б. Юдина, В.А. Якубовича и др.
В работах М. Вадьясагара, Д. Галафиори, Л. Гао, О.Н. Граничина, М. Кампи, Л. Льюнга, Б.Т. Поляка, П.С. Щербакова и др. показана целесообразность использования в задачах оценивания рандомизированных алгоритмов, которые позволяют ускорить процедуры решения задач и устранить эффекты смещения. Рандомизированные алгоритмы стохастической аппроксимации (РАСА, в англоязычной литературе — SPSA, Simultaneous Perturbation Stochastic Approximation), были предложены в работах О.Н. Граничина, Б.Т. Поляка и А.Б. Цыбако-ва, Дж. Спалла, Х.-Ф. Чена, Т. Дункан и Б. Пасик-Дункан в конце 80-х, 90-х гг. XX в., развивая идеи методов случайного поиска, детально исследованных в русскоязычной литературе СМ. Ермаковым и А.А. Жиглявским, А. Жилинскасом, Л.А. Растригиным и многими
другими. О.Н. Граничиным в 1989-1992 гг. было показано, что эти алгоритмы работоспособны в условиях неизвестных ограниченных помех наблюдения (unknown but bounded). В задачах стационарной оптимизации Б.Т. Поляк и А.Б. Цыбаков в 1990 г. обосновали минимаксную асимптотическую оптимальность скорости сходимости оценок этих алгоритмов, в том смысле, что порядок ее не может быть улучшен никаким другим итеративным алгоритмом. Дж. Спаллом в 1992-1997 гг. была установлена оптимальность использования в качестве пробного возмущения распределения Бернулли и уменьшение количества измерений для получения оценки заданного качества по сравнению с процедурой Кифера-Вольфовица.
Несмотря на большое количество публикаций по исследованию свойств оценок алгоритмов типа РАСА, теоретическая обоснованность их использования до последнего времени существенно ограничивалась пред-пол ожениями об ограниченности второго момента у неопределенностей. С.С. Сысоевым в 2005 г. была обоснована состоятельность рандомизированного алгоритма стохастической аппроксимации с одним измерением в частном случае при существовании у статистических неопределенностей конечного момента степени р Є (1; 2] в более строгих условиях, чем предложенные в диссертации.
В последнее десятилетие методы управления и оптимизации нашли важное приложение в теории распределенных и мультиагентных систем, а также систем массового обслуживания, в работах Ф. Булло, Г. Вайса, X. Кортес, Н.К. Кривулина, С. Мартинез, А.С. Матвеева, А.В. Савкина, Ж. Фербера и др.
Цель работы. Исследование свойств оценок рандомизированных алгоритмов стохастической аппроксимации в стационарном и нестационарном случае при наличии у неопределенностей конечного момента степени р, 1 < р < 2. Для достижения этой цели были поставлены и решены следующие задачи.
При оптимизации функционала типа среднего риска со статистическими неопределенностями с конечными моментами степени р Є (1,2] и почти произвольной ограниченной аддитивной помехе наблюдения
исследовать в стационарном случае свойства состоятельности оценок РАСА с уменьшающимися до нуля размерами шагов;
получить асимптотические оценки скорости сходимости РАСА;
исследовать в нестационарном случае свойства стабилизируемости последовательности оценок РАСА с постоянным размером шага.
Разработать модель системы управления загрузкой узлов распределенной вычислительной сети, в контур обратной связи которой включены РАСА, и исследовать ее поведение при неопределенностях, распределенных с бесконечным вторым моментом.
Методы исследования. В диссертации применяются методы теорий оценивания и оптимизации, вероятностей и математической статистики, массового обслуживания, имитационного моделирования. Основные результаты. В задачах оптимизации функционала типа среднего риска со статистическими неопределенностями с конечным моментом степени р Є (1,2] и почти произвольной ограниченной аддитивной помехой наблюдения установлены
необходимые условия состоятельности и сильной состоятельности оценок РАСА в стационарном случае (Теоремы 1,2);
асимптотические оценки скорости сходимости РАСА (Теоремы 3,4);
необходимые условия стабилизации последовательности оценок и получено выражение для границы стабилизации РАСА в нестационарном случае (Теорема 5).
Разработана динамическая модель системы управления загрузкой узлов распределенной вычислительной сети, в которой случайный дрейф производительности процессоров имеет бесконечную дисперсию, а в контур обратной связи включены РАСА. Применимость РАСА подтверждается полученными теоретическими границами на время обработки пакета заданий (Теоремы 6-8) и имитационным моделированием.
Научная новизна. Все основные научные результаты диссертации являются новыми.
Теоретическая ценность и практическая значимость. Теоретическая ценность диссертации состоит в ослаблении условий состоятельности и сильной состоятельности оценок рандомизированных алгоритмов стохастической аппроксимации с убывающим и фиксированным шагом в задачах стационарной и нестационарной стохастической оптимизации.
Практическая значимость работы заключается в том, что расширен круг задач, при решении которых обосновано применение РАСА. Разработанная модель распределения заданий в гетерогенной вычислительной сети может непосредственно использоваться при проектировании соответствующих систем. Полученные в диссертации условия состоятельности и границы стабилизации могут быть использованы при настройке инженерных систем, использующих РАСА, а также в педагогической практике.
Апробация работы. Результаты работы докладывались на научных семинарах кафедр системного программирования и теоретической кибернетики СПбГУ, на Балтийских олимпиадах по автоматическому управлению в 2006 и 2008 гг. (в 2008 г. доклад был удостоен награды первой степени за теоретическую значимость), на научных конференциях: 5th WSEAS Conference on Automatic Control, Modeling and Simulation в 2006 г. (Прага, Чехия, доклад был удостоен премии за лучший студенческий доклад), Всерос. научн. конф. "Научный сервис в сети Интернет" (2006,2007,2009), 9th IFAC Workshop "Adaptation and Learning in Control and Signal Processing" (ALCOSP'07, Санкт-Петербург, 2007), XI конф. молодых ученых "Навигация и управление движением" (Санкт-Петербург, 2009), Первая традиционная всероссийская молодежная летняя школа "Управление, информация и оптимизация" (Переславль-За-лесский, 2009), 3rd IEEE Multi-conference on Systems and Control (2009), Sixth Workshop on Simulation (Санкт-Петербург, 2009), VI Всероссийской межвузовской конференции молодых ученых в СПбГУ ИТМО (Санкт-Петербург, 2009, диплом "За лучший доклад аспиранта на секции"), 6th Int. Conf. on Informatics in Control, Automation and Robotics (Милан, Италия, 2009), 48th IEEE Conference on Decision and Control and 28th Chinese Control Conference (Шанхай, Китай, 2009).
Результаты диссертации были частично использованы в работах по грантам РФФИ 05-07-90179-в, 09-04-00789-а и проектам "Система видеонаблюдения на основе стереозрения" и "Разработка рандомизированного подхода к проблемам поиска схожих участков изображений в задачах стереозрения и отслеживания движения", которые победили в конкурсах СТАРТ-08 в 2008 г. и "УМ.Н.И.К." в 2009 году. Публикации. Основные результаты диссертации опубликованы в работах [1-32], среди которых [1-3] — в научных журналах перечня ВАК.
Работы [1-4, 6-10,14-21, 24-27, 30-32] написаны в соавторстве. Со-
искателю в них принадлежат формулировки и доказательства основных теорем, имитационное моделирование. В работах [1-4,8-10,30-32] О.Н. Граничину принадлежат общие постановки задач, в [1] С.С. Сысоеву — формулировка алгоритма для квантовых вычислений; в [2,19, 20,24,30,32] Л.С. Гуревичу — формулировки условий на нестационарность и теорема об оптимальном выборе размера шага, в [3,14,15, 28] М.А. Паныненскову — анализ и реализация алгоритмов распределения загрузки вычислительных узлов и оценивания пропускной способности каналов данных, в [6,7,16-18,21,25-27] соавторам — постановки задач и обзоры подходов к их решению.
Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения и списка литературы, содержащего 136 наименований. Включает 11 рисунков, 3 таблицы. Общий объем работы — 103 страницы.
Оптимизация функционала среднего риска
В инженерной практике зачастую возникают задачи, для которых из-за влияния неконтролируемых факторов невозможно предложить решение, оптимальное при всех возможных стечениях обстоятельств. Примером может быть серийный выпуск сложных механизмов, когда технические характеристики отдельных изделий могут существенно отличаться друг от друга, находясь при этом в рамках некоторого допустимого множества. Это происходит в силу неконтролируемых факторов, влияющих на производственный процесс. Факт непостоянства характеристик от изделия к изделию необходимо учитывать при настройке системы управления механизмом. Также, неконтролирусмость может возникать в силу необходимости принятия решения перед тем, как случится некоторое влияющее на качество решения событие. Так, инженеры электростанции в начале каждого отчетного периода должны настроить станцию на предполагаемый объем производства энергии, с тем, чтобы оптимально расходовать ресурсы, в то время как спрос на энергию определяется ее потребителями уже в течение этого периода. Оптимизация при условиях неопределенности появляется в задачах идентификации, регрессии, робастного и рекуррентного оценивания и анализа данных, оптимального управления и экстремального регулирования [47], связанных с моделированием по методу Монте-Карло, фильтрацией или распознаванием изображения, экономическим планированием или распределением ресурсов [24,47,66]. Неопределенность, возникающая в приведенных выше и других задачах, может трактоваться как зависимость функции качества от неизвестного параметра. Обозначим штрафную функцию F(x,w), первый аргумент - оптимизируемый (управляемый) х, второй - неизвестный w Є W С W. Критерий оптимизации может формулироваться по-разному в зависимости от задачи. Так, возвращаясь к примеру серийного производства механизмов, естественно требовать работоспособности системы управления в наихудшем из возможных сочетании характеристик, то есть ставить задачу оптимизации в минимаксной постановке [47,53,109]. Математически это можно записать как что выражает требование наименьшего значения функции стоимости при наихудшем возможном значении w. Эта постановка задачи является основной, когда нет никаких сведений о природе w, кроме принадлежности множеству W. Она может появиться в приложениях теории игр [31], где w генерируется соперником, в системах управления, от которых требуется робастпая устойчивость по параметру w [51] и пр. В диссертационном исследовании использована и другая трактовка неопределенности, а именно - предположение о случайности ее или какой-то ее составной части.
Исторически, случайные величины использовались именно для выражения равновозможности исходов из некоторого допустимого набора. Для случайной части неопределенностей, рассмотрим задачу Оптимизации функционала среднего риска — штрафной функции, усредненной по всем возможным значениям неопределенности. В приложениях задачи оптимизации такого типа решают при планировании деятельности на фоне непредсказуемых процессов, например - планировании загрузки вычислительного сервера при случайном характере размеров заданий, планировании вложений в ценные бумаги при случайном характере изменения их стоимости и др. Пусть задано вероятностное пространство (Q: Т, Р), функция F(x, w) : Ж9 х W — К, дифференцируемая по первому аргументу, хг, а,-2,... - выбираемая экспериментатором последовательность точек измерения (план наблюдения), в которых в каждый момент времени п = 1,2,... доступно наблюдению с аддитивными помехами vn значение функции F(-,wn) где wn - неконтролируемая последовательность независимых случайных векторов, wn Є W. имеющих одинаковое, вообще говоря, неизвестное распределение Pw( )- Требуется по наблюдениям у\, уч-, .. построить последовательность оценок {9п} неизвестного вектора в, минимизирующего функцию f(x) типа функционала среднего риска [24: Обычно исследуется случай F(w,x) = f(x). Сделанное обобщение позволяет, например, учесть случай мультипликативной неопределенности: F(x, w) = wf(x) и Ew — 1. В зависимости от конкретных условий задачи, свойств функции F и неопределенностей wn и vn сходимость последовательности оценок {вп} к в понимается в смысле одного из следующих определений. Определение! Последовательность оценок {9п} величины в называется состоятельной, если Ve О Р{0П — 0 е} —» 0 (п —» со). Определение 2. Последовательность оценок {вп} величины 9 называется сильно состоятельной, если сходимость оценок к в выполняется с вероятностью единица: Наряду с (1.8) будем рассматривать и нестационарную постановку задачи, которая актуальна в приложениях, где наблюдается постоянный незатухающий дрейф точки минимума, например — изменение оптимальных параметров двигателя вслед за износом отдельных деталей, изменением характера его использования или переменами в окружающей среде. Такого типа задачи возникают при построении адаптивных алгоритмов, когда необходимо не только идентифицировать систему, но и оценивать ее изменение во времени [66,86,93].
Типичным примером является отслеживание цели, когда измерению доступно только расстояние до цели [12], или отслеживание изображения движущегося объекта на видеосъемке [16,89]. Пусть задано семейство функций дифференцируемых по первому аргументу, х\. Х2,. — выбираемая экспериментатором последовательность точек измерения (план наблюдения), в которых в каждый момент времени п = 1,2,... доступно на блюдению с аддитивными помехами vn значение функции F(-,wn) где п — неконтролируемая последовательность, (п є Н. Требуется по наблюдениям уі,у2,--. построить последовательность оценок {9п} неизвестных векторов {9}, минимизирующих функции fn(x) типа функционала среднего риска [24]: Обозначим 9п = argminfn(x), р Є (1,2] показатель степени, используемый далее при определении статистических моментов случайных величин, который будет в основном использоваться в дальнейшем. Примером может служить нестационарный функционал со случайным дрейфом1 где Ew = w и п Є U(0, l)q — равномерно распределенная на (0, l)q случайная величина, или нестационарный функционал с детерминированным дрейфом В разделе 2.5 диссертации подробно рассматриваются задачи, где вводятся ограничения на дрейф минимума, включающие как затухающее, так и незатухающее изменение точки минимума со временем, как детерминированное, так и случайное. Рассматриваемые ограничения не позволяют доказать состоятельность или сильную состоятельность оценок, поэтому ставится задача построить стабилизирующуюся последователь
Модель высокооптимизированной толерантности
В [74] была предложена модель высокооптимизированной толерантности. Рассмотрим g-мсрное пространство X. Пусь в этом пространстве происходят некоторые явления ("пожары"), возникающие в определенной точке пространства X и потом распространяющиеся. Задана плотность вероятности явлений р(х) для всех х Є X. Предположим, что имеются некоторые ресурсы, которые могут остановить распространение явления, ресурсов ограниченное количество и они также распределены в пространстве, то есть для каждого х задано некоторое количество ресурсов R(x). Хорошей метафорой этой модели служат лесные пожары и барьеры в виде канав, прорываемых с целью предотвращения перекидывания огня между участками леса. Предположим, что размер явления, начавшегося из точки х, задается формулой Аа(х), тогда средний размер явления считается как Ограничение на ресурсы задается как Будем предполагать, что размер события обратно пропорционален количеству выделенных ресурсов: где (3 0. Если подставить такую закономерность в (1.16), то получится їх. Учитывая ограничение на количество ресурсов, получаем, что имеем где 7 = а + 1/(3. Обозначим Рситіу) = Р{У У} — 1 - (2/), гДе -случайная величина, a F(y) — ее функция распределения. Вероятность явления размером больше А может быть посчитана как JA(x) A Jp{x) A i что дает где р_1(-) - функция, обратная к плотности р{х).
Для гауссовского, экспоненциального и степенного распределений вероятности Рсит(А) приведены в табл. 1.1. Видно, что для этих распределений х распределение размеров явлений А удовлетворяет степенному закону. В работе [75] описаны три возможных применения модели, как обоснованные теоретически, так и подтвержденные собранными статистическими данными. Это лесные пожары, где q = 2 (лес распределен по плоскости), размеры веб-страниц (рассматривается модель "разрезания" большого текста на отдельные страницы), где q = 1, и эффективное кодирование информации по Шеннону, где q = 0. В случае лесных пожаров, у случайной величины присутствует конечное математическое ожидание, однако отсутствует дисперсия. Учитывая зависимость приведенной в табл. 1.1 плотности р(х) от размерности q пространства X, получаем, что в задачах минимизации размера возгорания или минимизации пересылаемых веб-сервером данных присутствуют случайные величины с бесконечной дисперсией. Модель высокооптимизированной толерантности была предложена как теоретическое обоснование эмпирического распределения размеров заданий в грид-системах [133], основанных на скоординированном разделении ресурсов и решении задач большим числом вычислительных процессоров [84]. В этом случае, х —- это пакет заданий, А(х) — число процессоров, задействованных при выполнении задания, R(x) — ограничения производительности процессоров. Модель присоединения с предпочтением (preferential attachment) основана на метафоре "богатый становится еще богаче" (rich get richer), справедливой в том или ином смысле для статистики населения городов, ци тирусмости научных статей, количества ссылок на страницах Интернет, численности биологических видов [112]. Впервые эта модель была предложена Дж. Юлсм в 1922 г. [136] для объяснения степенного закона эмпирического распределения у числа видов цветковых растений в составе одного рода, и итеративный процесс, лежащий в основе построения модели, с тех пор называют процессом Юля. Пусть существует некоторое множество объектов (биологических родов, городов, научных статей, веб-страниц и пр.) Время от времени в множество добавляется новый объект. Для каждого объекта определен целый неотрицательный параметр fc, — население города, число ссылок на статью, число ссылок с веб-страниц, число видов в рамках рода. Появляющиеся объекты имеют значение к = ко. Для новых видов ко = 1, для городов ко может равняться нескольким тысячам. Нельзя исключать ко — О, так как на только что вышедшую из печати статью обычно ни одна другая работа еще не ссылается. Между появлениями новых объектов, для уже присутствующих объектов увеличивается значение к: добавляется т новых видов, жителей или ссылок. Таким образом, в некоторых, но не обязательно во всех, городах или биологических родах увеличивается численность населения или количество видов. При этом вероятность увеличения параметра к прямо пропорциональна его значению (здесь и находит отражение принцип "богатый становится богаче"). Возникающая проблема с ко = 0 может быть преодолена, если положить вероятность увеличения к на единицу пропорциональной к + с для некоторого постоянного целого с 0. Пусть вероятность значения к для объекта на шаге п процесса обозначена как pk,n- Тогда из описания процесса получаются следующие уравнения [112]: Для разных примеров а;р Є (1,2]. Для эмпирического распределения числа ссылок на страницы в Интернет с использованием процесса Юля выбирают с = 0,2т [112]. В статье Дж. Юля [136] для объяснения эмпирического распределения числа видов в рамках биологического рода выбирается с = 0, &о = 1, т0 есть ар = 1 + 1/т.
Модель присоединения с предпочтением неоднократно использовалась для объяснения степенного закона у эмпирического распределения размеров страниц в Интернет [95,112,123] или файлов в компьютерном хранилище [108], где процессом Юля моделировалось создание и редактирование страницы или файла. Установлено, что число операторов в объектно-ориентированной программе также имеет степенной характер распределения, что связано с моделированием деятельности программиста с помощью процесса Юля [96,104,135]. Таким образом, степенным считают распределение размеров заданий, загружающих один процессор компьютера или паралллеьную многопроцессорную систему [95,123]. В этой главе сформулированы условия состоятельности или стабилизируемое последовательностей оценок РАСА в зависимости от конкретных условий задачи, свойств функции F и неопределенностей гип и vn, приведены удовлетворяющие им примеры задач в стационарном и нестационарном случаях, сформулированы и доказаны теоремы о состоятельности, сильной состоятельности, асимптотической скорости сходимости в стационарном случае и стабилизации в нестационарном случае последовательности оценок РАСА. При выполнении следующих условий будут доказаны требуемые факты об алгоритмах (1.13)-(1.15). Обозначим Тп сг-алгебру, порожденную случайными величинами Ai,..., Дп-і, 0о,..., 0п-1, u i,..., wmn. и fi,..., mnj если рассматривается нестационарная постановка задачи и дрейф случайный. (А) Сильная выпуклость f(x) в точке минимума.
Скорость сходимости
Теорема 3. Если выполнены условия Теоремы 1,а таксисе для всех п выполнено неравенство 0 vn 1, и Примеры 2. Для функции, описанной в разделе 2.2, пункт 1, проведем эксперимент с параметрами: р = 1,6; г = р; av — 1,8; E\v\ = 100; q = Ю; 0О = 104/p(l;...; 1)г; в = (0;...; 0)т, ап = 0, ОООООбп"1 и /? = 0, 5п 0,2917. В этом случае, уровень помехи совпадает со значением оптимизируемой функции в точке начального приближения: E\v\ /(#о)-Применим алгоритм (1.15). По Т. 1 оценки состоятельны, по 3 получаем, что р п р 1, и в то же время ип Є (0,1), что означает применимость пункта 4 Теоремы 3. Граница, полученная по данной в условии формуле, показана на рис. 2.2. Ее можно сравнить с также приведенной на рисунке усредненной по 10 запускам величиной отклонения 0П — 9\\р. Видно, что граница находится выше среднего отклонения. Пример показывает, что РАСА даст оценки при многомерной [q = 10) оптимизации в условиях, когда значение аддитивной помехи превышает уровень наблюдений штрафной функции. 3. Эксперимент аналогичен приведенному выше, однако используется функция, описанная в пункте 2 раздела 2.2, имеющая показатель степени р. Граница, полученная по данной в условии формуле, показана на рис. 2.3. Ее можно сравнить с также приведенной на рисунке усредненной по 10 запускам величине отклонения 0П Щрр- Сравнивая результат с предыдущим примером, можно заметить более пологий характер сходимости, что вызвано изменением степени с 2 на р. Из-за необходимости выполнения условия сильной выпуклости (А) требуется, чтобы для функций, убывающих к минимуму медленнее квадратичной, множество значений аргумента было бы выпуклым и компактным. Из таблицы 2.1 видно, что от размеров этого множества зависит постоянная сильной выпуклости р и другие параметры, при получении оценок выбиралось d = (——— ] . РАСА и при меньшей выпуклости функции дает при многомерной оптимизации оценки высокого качества. Пусть и обозначим к = тт{р(а — /д — ь \ р{а — dy), а + /Зру — /л(р — 1)} для алгоритма (1.13) или к — тт{р(а — /3 — г/), а + /Зру — Д(р — 1)} для (1.14),(1.15). Теорема 4. Пусть выполнены условия (А) для f{x), (В)-(Е) для F(x,w), (G) для аддитивных помех наблюдения, (Н) для рандомизированного возмущения и (2.3) для параметров. 1. Если а + р = 1, тогда -і 1 1 r Теоремы 3, 4 были опубликованы впервые в работе [14J для алгоритма (1.13) и затем обобщены на все три РАСА в [10]. Замечание. В случае, когда рп = р, 0, т)П = т 0, dn = d, можно получить оптимальный показатель степени (3 для размера шага Рп, в том смысле, что он будет наилучшим в рамках обоснованных в доказательстве Теоремы 1 оценок: В этом случае, к — сё-г Влияние показателя р.
При выборе разных р, как видно из приведенных теорем, скорость сходимости методов стохастической аппроксимации с пробным возмущением может изменяться довольно значительно. Ниже приведена табл. 2.2, показывающая показатель степени г) = р, п-о Пример 4. Параметры эксперимента: г = р = 1,6; q = 10; 9Q = (1, 5;...; 1,5)г; в = (0;...; 0)т; Ew = 1; aw = 1, 8; ап = 0, ООООбп"1, /3n = 0, Ьп Р, ft - (согласно Замечанию к Т. 4). Выполняется подпункт 3 п.1 Теоремы 4, так как 0, 00005д 0, 0001 р(1 - /3) - 1 = 0,13. Приводим график поведения \\вп — 0, усредненный по 50 опытам (рис. 2.4) и график пАіл\\вп — 9\\Р (рис. 2.5), подтверждающий утверждение Теоремы 4 о ЕпАР\\6п - в\\Р оо. Обозначим: С = 1 + J, J — число ненулевых функций и постоянных в наборе C/W , «;„_!), I7 («;n.iu„_i),D_i,VFn(0n,ion)Н,,, . Постоянная т принимает значения т = 1 для алгоритма (1.13) и т — 2 для алгоритмов (1.14)-(1.15); Х«,ь,с = t -i.n a.b.c + rp lD 1 Мр-фр-15а,ь,р-\+с Для а, 6, с принимаю-щих значения 1, р — 1, /?; Л 0 - произвольная постоянная; Примеры 5. Рассмотрим задачу из раздела 2.2, пункт 1, vn - распределено по Парето с показателем ар = 1, 8, среднее значение Evn = 1. Дрейф задается по правилу вп = 0n_i + f, f 1) = (2). Щ\р = 0,0001. Выберем шаги: а = 0,0005, Р — 0,5. Выберем начальные значения 6 о = (2,4224;2,4224)г, #0 = (0;0)т. Получается ситуация, когда оценка алгоритма „нагоняет" дрейфующую точку минимума. Граница из Теоремы 5 для алгоритма (1.15) представлена на рис. 2.6 прерывистой линией. Асимптотически при А = 0,1 получается граница стабилизации РИС. 2.6: Иллюстрация к примеру 5, сплошной линией показаны результаты среднего по 10 запускам алгоритма (1.15), прерывистой линией показано значение границы, приведенной в Теореме 5. РИС. 2.7: Иллюстрация к примеру 6, сплошной линией показаны результаты среднего по 10 запускам алгоритма (1.15), прерывистой линией показано значение границы, приведенной в Теореме 5. L = 1,1638. Сплошной линией показан результат усреднения по 10 экспериментам. 6. Рассмотрим задачу оптимизации с мультипликативной помехой fn(x) = \\х—0пМ, описанную в разделе 2.2, пункт 3, при этом Fn(x, wn) = wn\\x 9п\\р, Wn — распределено по Парето с показателем ар = 1, 8,среднее значение Ewn = 1. Дрейф задается по правилу 9п = 9n-i + п где ,г равномерно распределено на сфере \\п\\р — 1- Выберем шаги: а — 0,0005, р = 0,5. Выберем начальные значения в0 = (2, 4224; 2,4224)т, OQ = (0;0)г. Получается ситуация, когда оценка алгоритма „нагоняет" дрейфующую точку минимума. Граница из Теоремы 5 для алгоритма (1.15) представлена па рис. 2.7 прерывистой линией. Сплошной линией показан результат усреднения по 10 экспериментам.
Управление с обратной связью
Предположим, что процессоры загружены сторонними вычислениями, не относящимися к работе виртуальной организации. Будем считать, что размеры сторонних пакетов заданий являются случайными величинами. В разделе 1.4 диссертации показано, что для размеров пакетов вычислительных заданий для процессоров типично степенное распределение с бесконечной дисперсией. Будем считать, что справедливо одно из двух условий: (X) Производительность процессора і = 1,2, ...,q на всем временном интервале работы распределенной системы не изменяется и равна д Є К. Время вычисления заданий из пакета п выражается как (г) и (i) г tn — -г,—гтт—Ы) ГДС wn Є R - число сторонних обработанных заданий 0Ы+и -г — Wn за рассматриваемый временной интервал, являющееся случайной величиной, распределенной по степенному закону с некоторым показателем aw и математическим ожиданием Ewn = w \ (Y) Производительность процессора і = 1, 2,..., д на интервале между поступлением п-го и п + 1-го пакета заданий равна впг и изменяется как 9п = #„_i + Cn , где (п ЄІ- дрейф производительности процессора, вызванный загрузкой сторонними заданиями, случайная величина, распределенная по степенному закону с некоторым показателем az. В условиях случайной неопределенности согласно (X) переформулируем задачу (3.1). Пусть Ц?1 = minZn. Вместо (3.1) при условии (X) сформулируем задачу построения управления, обеспечивающего нера венство: В силу наличия неопределенности, при выполнении условия (X) достичь оптимального в среднем распределения заданий невозможно. Смысл задачи (3.4) сводится к поиску управления, обеспечивающего приближение к оптимальному значению показателя Zn при стремлении момента степени р неопределенности к нулю. В [69,113] рассматривается похожее на (X) условие, однако ставится задача минимизации простоя ресурсов, более актуальная для систем, работающих в потоковом режиме, а также не учитываются последние результаты о возможном отсутствии дисперсии у распределения размеров сторонних заданий. В случае (Y), при тех же, что и в (3.4), условиях на ип, сформулируем задачу построения управления, обеспечивающего наличие асимптотической границы для среднего значения Zn:
Вместо неизвестных параметров производительности процессоров при распределении заданий можно использовать их оценки, полученные с помощью РАСА (1.15) (или (1.13),(1.14)). Отклонение времени фактического выполнения заданий процессорами от предсказанного при этом используется как штрафная функция. РАСА используются в блоке адаптации, который включается в контур обратной связи для уточнения стратегии распределения заданий, как показано на рис. 3.2. Используемый подход является достаточно общим для систем управления [24]. Алгоритмы построения оптимального управления зачастую предполагают известными некоторые априорные параметры системы управления и помех, которые на практике могут быть неизвестны. В какой-то степени эту информацию удается восстановить, используя наблюдения системы. Таким образом, процессы управления и восполнения недостающей информации оказываются совмещены, что близко понятию дуального управления, введенному А.А. Фельдбаумом [55]. При достаточно эффективном восполнении информации система управления приобретает оптимальные или близкие к ним свойства, то есть является адаптивной, приспосабливающейся к заранее неизвестным помехо-сигнальным условиям [56,57]. В более простой формулировке, аналогичная проблема возникает в задачах экстремального регулирования [77,101].
В получившейся системе управления присутствует четыре модуля: объект управления - набор вычислительных устройств, характеризуемых вектором параметров Вп\ профилировщик - блок расчета показателя качества распределения заданий; блок адаптации, подстраивающий значение оценки 9п вектора параметров 0п ; регулятор, определяющий управление ип — стратегию распределения заданий в зависимости от оценки вп. В качестве стратегии распределения заданий выберем функцию ип(х) :
