Главная >> Диссертации - все темы

Pages: |

| 2 |

«Сысоев Сергей Сергеевич РАНДОМИЗИРОВАННЫЕ АЛГОРИТМЫ СТОХАСТИЧЕСКОЙ ОПТИМИЗАЦИИ И ИХ ПРИМЕНЕНИЕ ДЛЯ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ РАБОТЫ ВЫЧИСЛИТЕЛЬНЫХ КОМПЛЕКСОВ И СЕТЕЙ 05.13.11 Математическое и программное обеспечение ...»

-- [ Страница 1 ] --

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ

УНИВЕРСИТЕТ

На правах рукописи

Сысоев Сергей Сергеевич

РАНДОМИЗИРОВАННЫЕ АЛГОРИТМЫ

СТОХАСТИЧЕСКОЙ ОПТИМИЗАЦИИ

И ИХ ПРИМЕНЕНИЕ ДЛЯ ПОВЫШЕНИЯ

ЭФФЕКТИВНОСТИ РАБОТЫ

ВЫЧИСЛИТЕЛЬНЫХ КОМПЛЕКСОВ И

СЕТЕЙ 05.13.11 Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель д. ф.-м. н. О.Н.Граничин Санкт-Петербург 2005 Оглавление Введение................................ 1 Оптимизация функционалов среднего риска 1.1 Понятие функционала среднего риска............ 1.2 Примеры задач.......................... 1.2.1 Обнаружение сигнала, наблюдаемого на фоне помехи 1.2.2 Задача балансировки загрузки............. 1.2.3 Задача оптимизации работы сервера......... 1.2.4 Оценка надежности серверного ПО.......... 1.2.5 Предварительная оптимизация устройств...... 1.2.6 Организация контроля учебного процесса...... 1.2.7 Задача самообучения.................. 1.3 Итеративные алгоритмы оценивания и оптимизации................... 2 Рандомизированные алгоритмы стохастической оптимизации, квантовые компьютеры, искусственный интеллект 2.1 Постановка задачи и основные предположения................... 2.2 Пробное возмущение и основной алгоритм.......... 2.3 Состоятельность оценок..................... 2.4 Пример.............................. 2.5 Алгоритмы с двумя измерениями функции потерь на итерации.................. 2.6 Квантовый компьютер и вычисление оценки вектора-градиента функции.............. 2.7 О некоторых характеристиках компьютеров нового поколения................ 2.8 Доказательство теоремы 1................... 3 Имитационное моделирование 3.1 Использование рандомизированных алгоритмов для задачи балансировки загрузки.............. 3.1.1 Правило маршрутизации................ 3.1.2 Выбор размера шага алгоритма............ 3.2 Оптимизация работы сервера................. 3.2.1 Одномерный случай................... 3.2.2 Многомерный случай.................. 3.3 Оценка надежности серверного ПО.............. 3.3.1 Разделение на два уровня............... 3.3.2 Описание модели..................... 3.3.3 Разделение на четыре уровня............. 3.3.4 Результаты моделирования............... 3.4 Задача самообучения...................... Заключение............................... Литература............................... Введение Актуальность темы. Задача поиска минимума (максимума) некоторой функции (функционала) f (x) min x известна уже давно. Ее актуальность обосновывается тем фактом, что довольно большой класс задач сводится к ее решению. Часто порядок полученных уравнений и число неизвестных таковы, что аналитический поиск решения становится практически невозможным. На самом деле, ценность аналитического решения не так уж высока оно все равно будет искажено при использовании (например, за счет ограниченной разрядности вычислительных машин, или неточности измерительных приборов).

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

В 1952 году в работе Кифера и Вольфовица [65] была предложена процедура оптимизации функционала, градиент которого был неизвестен, и наблюдателю были доступны лишь зашумленные измерения yn. В работе предполагалось, что помехи измерения взаимонезависимы, одинаково распределены и центрированы (в среднем равны нулю). Эти ограничения предоставляют возможность получать оценку функционала f в некоторой точке путем многократного измерения и усреднения результата.

Ранее в 1951 году вышла статья Роббинса и Монро [72], в которой решалась задача поиска корня функции, измеряемой с помехами, на которые накладывались точно такие же ограничения. Роббинс и Монро воспользовались модификацией градиентного метода и отказались от усреднения на каждом шаге, предложив алгоритм Усреднение в предложенном методе происходило неявным образом, за счет достаточно медленного стремления к нулю параметра алгоритма n.

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

Благодаря стремительному развитию вычислительной техники процедуры Роббинса-Монро и Кифера-Вольфовица получили широкое распространение. Большую роль в пропаганде подобных методов сыграл Я.З.Цыпкин. В своих книгах “Адаптация и обучение в автоматических системах” [50] и “Основы теории обучающихся систем” [51] он показал широкую применимость рекуррентных стохастических алгоритмов в задачах оценивания, идентификации, распознавания образов, оптимизации и управления. Позже была оценена эффективность таких алгоритмов и найдены их оптимальные и робастные варианты.

Рассматриваемый в этой диссертации тип алгоритмов, основанных на использовании статистической информации о включаемом в рассмотрение пробном одновременном возмущении, относится к более широкому классу алгоритмов случайного поиска. Значительное использование на практике алгоритмов случайного поиска вызвано потребностью в решении задач оптимизации в условиях, когда свойства исследуемой функции потерь неизвестны, а измерение значений самой функции доступны чаще всего с помехами. В русскоязычной литературе эти алгоритмы исследовались, например, в работах Л.А.Растригина [43, 44], А.Жилинскаса [21], С.М.Ермакова и А.А.Жиглявского [18] при условии центрированности и независимости помех наблюдения.

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

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

Первые исследования, учитывающие эти условия, начались на рубеже 80–90-х годов прошлого века. Основы этих исследований базируются на работах О.Н. Граничина, Б.Т. Поляка с А.Б.Цыбаковым и А.В.Гольденшлюгером [6, 7, 8, 9, 10, 39, 63, 71], Дж.Спала [74, 75].

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

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

Основные результаты. В работе получены следующие основные результаты:

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

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

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

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

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

Научная новизна. Все основные научные результаты диссертации являются новыми.

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

Апробация работы. По материалам диссертации были сделаны доклады на международных конференциях “Physics and Control 2003” (Санкт-Петербург), “System Identication and Control Problems 2004” (Москва), на заседании международной школы-семинара “Адаптивные роботы – 2004” (Санкт-Петербург), на Пятом международном семинаре “5-th St. Petersburg Workshop on Simulation” (Санкт-Петербург, 2005 г.), а также на семинарах кафедры системного программирования математикомеханического факультета Санкт-Петербургского государственного университета.

Публикации. Основные результаты диссертации опубликованы в работах [17, 23, 45, 46, 59, 62].

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения и списка литературы, содержащего 79 наименований. Включает 18 рисунков. Общий объем работы 80 страниц.

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

В первой главе определяется понятие функционала среднего риска и ставится общая задача о его минимизации. Рассмотрим стандартную формулировку задачи оптимизации некоторого функционала f (x). Параметр x обычно представляет собой вектор сравнительно большой размерности, а вид функционала f часто неизвестен, но доступны его зашумленные измерения yn в выбранных экпериментатором точках xn :

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

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

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

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

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

Далее, в разделе 1.3, приводится библиографический обзор, касающийся алгоритмов стохастической оптимизации.

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

Пусть F (x, w) : Rq Rp R1 дифференцируемая по первому аргументу функция, x1, x2... выбираемая экспериментатором последовательность точек измерения (план наблюдения), в которых в каждый момент времени n = 1, 2,... доступно наблюдению с аддитивными помехами vn значение функции F (·, wn ) где {wn } неконтролируемая последовательность случайных величин (wn R ), имеющих одинаковое, вообще говоря, неизвестное распределение Pw (·) с конечным носителем.

Требуется по наблюдениям y1, y2... построить последовательность оценок {n } неизвестного вектора, минимизирующего функцию типа функционала среднего риска.

Обычно рассматривается задача минимизации функции f (·) при более простой модели наблюдений которая легко укладывается в общую схему. Сделанное обобщение в постановке задачи диктуется стремлением учесть случай мультипликативных помех в наблюдениях который входит в общую схему с функцией F (x, w) = wf (x).

Далее мы будем использовать обозначения · и ·, · для евклидовой нормы и скалярного произведения в Rq. Пусть (1, 2]. Введем функцию Ляпунова где - искомый вектор из пространства параметров, и сформулируем основные предположения.

A.1 Функция f (x) имеет единственный минимум в точке и с некоторой постоянной µ > 0.

A.2 При любом w градиенты функций F (·, w) удовлетворяют условию Гельдера с показателем с некоторой постоянной M > 0.

Пусть n, n = 1, 2,... наблюдаемая последовательность независимых друг от друга случайных векторов в Rq, называемая в дальнейшем пробным одновременным возмущением, компоненты которых независимы между собой принимают значения ±1 с вероятностью 2.

Зафиксируем некоторый начальный вектор 0 Rq и выберем некоторые последовательности положительных чисел {n } и {n }.

Для построения последовательностей точек измерения {xn } и оценок n } предлагается следующий алгоритм, использующий на каждом шаге (итерации) одно наблюдение:

В этом алгоритме Pn (·), n = 1, 2,... операторы проектирования на некоторые выпуклые замкнутые ограниченные подмножества n Rq, содержащие, начиная с некоторого n 0, точку. Если заранее известно замкнутое ограниченное выпуклое множество, содержащее точку, то можно считать n =. В противном случае множества {n } могут расширяться до бесконечности.

Обозначим W = supp(Pw (·)) Rp конечный носитель распределения Pw (·); Fn -алгебру вероятностных событий, порождаемую случайными величинами 0, 1,..., n, формируемыми по предлагаемому алгоритму;

dn = diam(n ) диаметр множества n ;

Теорема 1. Пусть (1, 2] и выполнены условия:

(A.1) для функции f (x) = Ew {F (x, w)};

(A.2) для функции F (·, w) w W;

функции F (x, w) и x F (x, w) равномерно ограничены на W;

n 1 случайные величины v1,..., vn и вектора w1,..., wn1 не зависят от wn, n, а случайный вектор wn не зависит от n ;

Тогда:

1). последовательность оценок {n }, доставляемых алгоритмом (1), сходится к точке в следующем смысле:

4). Если, более того, тогда n при n с вероятностью единица, и Доказательство теоремы приведено в последнем разделе второй главы.

Далее во второй главе рассмотрена проблема выбора вычислительного устройства, наилучшим образом подходящего для выполнения рандомизированного алгоритма стохастической оптимизации с одним измерением функции штрафа на итерации. В работе О.Н.Граничина 2002 года [12] был описан способ реализации алгоритма (1) на вычислительных устройствах нового типа квантовых компьютерах. За прошедшее время терминология и аксиоматика моделей квантовых вычислений стали более четкими. Описанный ранее способ реализации не был похож на типичный “квантовый” алгоритм, и сейчас можно сказать, что выбранный ранее способ представления не был удачным. В разделе 2.6 описан новый способ представления алгоритма на квантовом компьютере, который в большей мере соответствует общей логике квантовых вычислительных алгоритмов.

Заканчивается вторая глава описанием возможной схемы реализации интеллектуальной системы на базе квантовых компьютеров и рандомизированных алгоритмов. В разделе 2.7 предложен один из возможных подходов к созданию интеллектуальной системы. Термин “интеллектуальная” подразумевает способность системы адаптироваться к меняющемуся окружению посредством выбора задачи, которую необходимо решить в текущий момент. Предлагаемое решение задачи создания искусственного интеллекта базируется на предположении, что в ближайшем будущем станет возможно организовывать тысячи устройств для параллельной работы. Это предположение обосновывается последними серьезными продвижениями в создании квантового и ДНК компьютеров.

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

Начинается третья глава с задачи балансировки загрузки. Рассмотрим систему, состоящую из двух серверов, способных параллельно обрабатывать N (1) и N (2) заявок, и балансировщика загрузки устройства, в реальном времени принимающего решение, к какому из серверов отправить пришедшую в текущий момент времени заявку. Значения N (1) и N (2) могут меняться со временем, и считаются неизвестными балансировщику. Кроме того, неизвестным предполагается время обслуживания серверами каждой из заявок. При невозможности немедленной обработки запроса на серверах заявка системой отвергается.

Обозначим через ut 0 функцию прихода заявки в момент времени t. Если заявки нет, то ut = 0, если заявка фактически поступила, то ut время, которое будет затрачено на ее обработку (об этих величинах нам известна только некоторая индикаторная функция, показывающая есть ли новая заявка на входе балансировщика или нет).

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

• zt = 1, если в момент времени t пришла заявка, балансировщик загрузки направил ее к серверу i, (i = 1, 2), и на нем не нашлось свободных каналов, в то время как на другом сервере свободные • zt = 0 во всех остальных случаях.

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

Ясно, что функция штрафа в каждый момент зависит от большого количества случайных параметров (величин ut, Nt ) и от выбранного алгоритма маршрутизации. В случае когда выбран класс алгоритмов x, можно сформулировать задачу оптимизации:

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

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

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

Пусть вероятностное распределение времени обслуживания задания сервером зависит от параметра x, который требуется выбрать с целью минимизации среднего времени ожидания клиентами L(x) вместе с некоторой стоимостью использования q(x) параметра x где zi (x) время, которое задание, законченное i-м по счету, ожидало (“простаивало”) в сервере до момента своего завершения.

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

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

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

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

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

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

Система состоит из следующих компонент:

• База данных, • Сервер доступа к базе данных, • Генератор запросов к серверу, • Супервизор процесса тестирования.

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

Все компоненты модели разработаны на языке C++, в стандарте POSIX, что делает возможным их использование на всех платформах, поддерживающих этот стандарт. Генератор запросов к серверу, имитирующий действия клиентов, является полностью самостоятельным приложением и может быть реализован на любом языке и запущен на любой платформе, при условии осуществимости посылки запросов серверу. Результаты моделирования приведены в разделе 3.3.

Последней в третей главе в разделе 3.4 рассматривается самообучающаяся опознающая система, на вход которой поступают сигналы w принадлежащие одному из l классов (число классов конечно и известно заранее). Сигналы w представляют собой вектора из p компонент, называемых признаками, а последовательность векторов w1, w2,... является реализацией некоторой последовательности независимых, одинаково распределенных случайных величин.

Пусть заданы функции Qk (X, w), k 1, 2,..., l (l число классов), определяющих качество классификации и зависящих от матричного параметра X = {x1,..., xl }, xi Rq, который удобно интерпретировать как набор центров классов. Функционал среднего риска в задаче самообучения имеет смысл математического ожидания общих потерь и может быть записан следующим образом:

где {Wk (X )}l разбиение выборочного пространства на l непересекаk= ющихся подмножеств Проблема самообучения распознаванию образов формулируется как поиск некой оценки X, минимизирующей предлагаемый функционал среднего риска иными словами, задача заключается в поиске центров классов, наилучших с точки зрения функций Qk (X, w).

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

В заключении формулируются основные результаты работы.

Глава Оптимизация функционалов среднего риска 1.1 Понятие функционала среднего риска Известно, что многие практические задачи сводятся к поиску минимума (или максимума) некоторого функционала:

Параметр x обычно представляет собой вектор сравнительно большой размерности, а вид функционала f часто неизвестен, но доступны его зашумленные измерения yn в выбранных экпериментатором точках xn :

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

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

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

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

1.2.1 Обнаружение сигнала, наблюдаемого на фоне В качестве простейшего примера рассмотрим задачу об обнаружении сигнала n, наблюдаемого на фоне помехи v. Наблюдателю доступны значения:

Параметр может принимать значения 1 или 0, что соответствует наличию или отсутствию сигнала в канале наблюдения. Значение сигнала n предполагается известным наблюдателю в любой момент времени. Требуется по набору величин y1... yN построить оценку N параметра. Эта задача очевидным образом сводится к задаче минимизации функционала среднего риска:

Здесь помеха vn интерпретируется как одна из состовляющих вектора неконтролируемых параметров.

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

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

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

Такая ситуация возможна, если, например, используется тактика поиска первого свободного ресурса в некотором множестве.

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

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

Рассмотрим систему, состоящую из двух серверов, способных параллельно обрабатывать N (1) и N (2) заявок, и балансировщика загрузки - устройства, в реальном времени принимающего решение, к какому из серверов отправить пришедшую в текущий момент времени заявку [45, 67]. Значения N (1) и N (2) могут меняться со временем, и считаются неизвестными балансировщику. Кроме того, неизвестным предполагается время обслуживания серверами каждой из заявок. При невозможности немедленной обработки запроса на серверах будем считать, что заявка системой отвергается. Введем дискретное время t, и обозначим через ut 0 функцию прихода заявки в момент времени t. Если заявки нет, то ut = 0, если заявка фактически поступила, то ut - время, которое будет затрачено на ее обработку (об этих величинах нам известна только некоторая индикаторная функция, показывающая есть ли новая заявка на входе балансировщика или нет).

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

Далее, в главе 3 мы вернемся к поставленной здесь задаче, для того чтобы обозначить класс алгоритмов и предложить решение.

1.2.3 Задача оптимизации работы сервера В [4, 67, 78] рассматривалась задача повышения эффективности работы сервера, который используется для обслуживания очереди заданий, поступающих случайным образом. В работе предполагается, что вероятностное распределение времени обслуживания задания сервером зависит от вещественного параметра x, который требуется выбрать с целью минимизации среднего времени ожидания клиентами L(x) вместе с некоторой стоимостью использования q(x) параметра x где zi (x) время, которое задание, законченное i-м по счету, ожидало (“простаивало”) в сервере до момента своего завершения. Требуется найти параметр, минимизирующий f (x) по x из некоторого компактного множества R (области определения).

Вообще говоря, функцию L(x) очень трудно вычислить. Пусть x фиксировано. Можно, наблюдая за очередью длительное время (фиксируя время поступления заказа, время обслуживания и время отправки для каждого клиента), использовать полученные данные для оценки G производной функционала качества f (x) для текущего значения x =, получающегося в результате подсчета по некоторому градиентному алгоритму. Здесь термин оценка производной понимается в широком смысле, так как она может получаться смещенной. Фактически, мы обязаны предполагать, что получающаяся оценка производной зависит не только от выбранной точки x, но и от некоторого набора w неконтролируемых возмущений (помех) определяющихся конкретными условиями функционирования сервера на выбранном для исследований интервале времени, включая фактически реализовавшуюся последовательность запросов.

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

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

Более точно, пусть Ft (x, w) случайная функция дискретного времени t = 1, 2,..., векторного параметра x и вектора неконтролируемых возмущений w. Обозначим через ft “текущий” функционал среднего риска:

Точку минимума функционала ft обозначим Как и ранее будем считать, что, выбрав x на определенных интервалах времени, мы можем измерить значения соответствующего “текущего” эмпирического функционала Ft (x, w). При этом мы естественно предполагаем, что скорость “дрейфа” оптимального параметра настолько низкая, что мы в состоянии получить целую серию значений Ft (xn, wn ), n = 1, 2,....

Требуется по наблюдениям (может быть с дополнительными помехами) за случайными величинами Ft (xn, wn ), n = 1, 2,... построить последовательность оценок {n }, отслеживающих изменения параметра t, для которой В [77] формулируется более общая задача. Представим себе сервер, имеющий q входных каналов для поступления заявок. Время обработки заявок на данном сервере распределено экспоненциально, причем параметр экспоненциального распределения свой для каждого из каналов.

Значения данных параметров предполагаются неизвестными.

На сервере запущено q потоков исполнения (по одному на каждый канал). Требуется назначить каждому потоку исполнения свой timeslice промежуток времени, на который поток получает процессор, таким образом, чтобы минимизировать вероятность события, при котором на полном цикле (последовательном получении процессорного времени всеми потоками) не будет обработано ни одного задания. При этом вводится ограничение на рост длины цикла (в противном случае очевидным решением является назначить каждому потоку максимальный возможный промежуток).

Математически задачу можно формализовать как оптимизацию следующего функционала:

Здесь вектор x представляет собой набор соответствующих каждому из потоков исполнения временных промежутков, а w(i) случайные величины, обратнопропорциональные времени, требуемом на обработку приходящих заданий. Их распределение зависит от номера канала i.

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

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

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

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

В работе [17] рассмотрены характеристики стресс-теста, которые влияют на зависимость между временем работы при тестировании и временем “нормальной” работы. Изменяя эти характеристики (такие как интенсивность отсылки запросов или объем доступной памяти), можно сократить время тестирования, однако связь общего результата этого тестирования с понятием качества продукта остается весьма условной.

В [17] предлагается следующий критерий качества ПО. Сервер рассматривается как детерминированный автомат где S = {s} конечное или бесконечное счетное множество состояний сервера; s0 начальное состояние сервера, которое воспроизводится при выполнении тестирования; Lz = {z} конечное, но большое множество различных запросов к серверу; P : (s1, z) (s2, r) функция перехода (программа), которая позволяет серверу, находясь в состоянии s1, выдать результат r выполнения запроса z (при этом происходит смена состояния); E S множество терминальных состояний.

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

В качестве множества различных запросов к серверу можно выбрать, например, множество предложений языка SQL ограниченной длины на конечных данных с параметрами заданной разрядности. То, насколько велико при этом множество Lz, можно увидеть на простом примере.

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

Будем рассматривать случай, когда текущее состояние сервера определяется только начальным состоянием и цепочкой запросов. Более точно, пусть на некотором отрезке времени сервер выполняет цепочку запросов = z1... zl Ll. Эта цепочка приводит к цепочке переходов s0 s1... sl и наблюдениям y0,..., yl. Обозначим множество всех цепочек (любой длины) L = Ll.

Задача сервера состоит в генерации ответов ri на последовательные запросы zi, i = 1, 2,....

Будем считать, что на множестве всех наблюдений Y задана некоторая функция ошибок err : Y {0, 1}. Те состояния e S, для которых err(y(e)) = 1, будем называть ошибочными. Можно рассматривать и более общую постановку, когда функция ошибки err : Y [0, 1], т. е.

принимает значения от 0 до 1, что соответствует степени ошибочности состояния. В одном из простейших случаев, когда m = 1, y процент используемой памяти, а объем всей доступной памяти равен M, можно считать err(y) = y/M.

Поскольку при заданном начальном состоянии каждой цепочке Ll длины l соответствует один вектор измерений y, то можно переопреz делить функцию err : Ll [0, 1], считая err() = err(y). Будем считать, что работа сервера останавливается только в тех случаях, когда функция ошибок на наблюдаемых величинах равна 1. Задачу тестирования определим как исследование множества входных цепочек, приводящих к ошибочным состояниям сервера:

Конкретизация задачи может включать исследования • элементов E, • структуры E, • мощности |E| (по мере |L | = 1).

Мера множества E предлагается в [17] как критерий качества реализации сервера.

В общем случае исследовать множество E невозможно. Для упрощения задачи выберем достаточно большое натуральное число l и рассмотрим другое множество аналог множества E для конечных цепочек длины не более l, Для оценки мощности |A| можно использовать метод Монте-Карло (см. например [19]). Однако, на практике это множество часто оказывается настолько мало, что для оценки его мощности с некоторой заданной погрешностью (обычно сравнимой с оцениваемой мощностью) требуется провести невыполнимое количество испытаний.

В работе [17] предлагается эффективный алгоритм оценки мощности |A| (по мере |Ll | = 1), основанный на методах, предложенных в [79].

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

Пусть M > 0 и множество Y наблюдений за состояниями сервера разбито на M + 2 непересекающихся подмножеств Y0, Y1,..., YM +1, последнее из которых Y0 поглощающее множество, соответствует выполнению условия err(y) = 1 (при попадании в YM +1 процесс обрывается).

Состояние сервера в начальный момент соответствует множеству Y0.

Основное предположение: если последовательность из запросов Lz приводит в какой-то момент к множеству Yi, i = 1,..., M + 1, то до этого момента траектория пересекла все множества Y0, Y1,..., Yi1.

Набор множеств Y0, Y1,..., YM +1 естественным образом порождает семейство подмножеств всех цепочек запросов длины l причем BM +1 = A, B0 = Ll. Более точно, для i = 0, 1,..., M будем считать, что последовательность запросов Ll попадает в какое-то подмножество Bi, если при ее выполнении на сервере в какой-то момент времени ti () в первый раз наблюдается состояние из Yi. Дополнительно предположим, что Рассмотрим следующий алгоритм моделирования:

2. Сгенерировать по равномерному распределению и запустить N > последовательностей запросов {k }N.

4. Оборвать все траектории, которые Bj.

5. Каждая из оставшихся траекторий t пересекает множество Bj после выполнения некоторой начальной подцепочки t,i. “Разделить” цепочку t на Rj новых по правилу: первая t, начальные участки остальных равны t,i, а оставшиеся “хвосты” сгенерировать по равномерному распределению.

Каждый раз, когда траектория попадает в множество Bj, j = 1,..., M, она разделяется на Rj траекторий с началом на уровне j. Рис. 1 поясняет смысл алгоритма.

В [17] данный алгоритм обосновывается с точки зрения качества оценки мощности A, однако его можно использовать и как эффективный метод достижения A, что на практике дает возможность быстро выявлять ошибки в программном обеспечении.

Настройка параметров алгоритма (величин Ri ) с целью максимизации вероятности попадания в множество A представляет самостоятельную задачу, которую можно сформулировать в терминах оптимизации функционала среднего риска:

Компонентами вектора x здесь являются величины Ri, а вектор w несет в себе случайную составляющую процесса моделирования. Функционал F удобно определить как количество траекторий, достигнувших множества A за ограниченное время N (число запросов к серверу).

Более детальное исследование данной задачи и результаты моделирования описаны в главе 3, разделе 3.3.

1.2.5 Предварительная оптимизация устройств В настоящее время в информатике бурно развивается область кодизайна совместной программно-аппаратной разработки (Hardware / Software Codesign, HSC). Ее появление относят к началу 90-х годов, когда термин “кодизайн” был введен в обиход для описания совокупности проблем проектирования интегральных схем. Методы кодизайна позволяют решать не только задачи программной или аппаратной оптимизации, но и более глобально задачи программно-аппаратной оптимизации.

В Санкт-Петербургском Государственном Университете ведутся разработки по технологии прототипирования устройств (Processor Architecture Denition LAnguage, PADLA), предложен способ автоматизированного получения прототипа, основанный на извлечении макроархитектуры аппаратной платформы из реализации на языке высокого уровня (например, языка C), см. [55].

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

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

Пусть заданы:

• программа S, • множество входных данных D = (di ), • максимальное время T на обработку одного пакета di.

Вычислитель имеет следующий вид:

где z > 0 тактовая частота устройства, а каждое mi представляет собой количество ресурсов типа i (памяти, регистров и т.д.).

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

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

Обозначим за F энергию системы, затрачиваемую на обработку одного пакета входных данных. Она зависит от количества ресурсов устройства M, частоты устройства z, перечня исполняемых в процессе работы команд. Выполняемые команды определяются целевой программой S и входными данными d, поэтому F также зависит от S и d Естественно рассмотреть оптимизационную задачу: выбрать такое значение M Nl и z > 0, при которых энергопотребление F будет минимально в среднем для входных пакетов d D Пусть программа S задана изначально как требование к системе. Предположим, что в моменты времени n = 1, 2,... извне неконтролируемо поступают входные данные d1, d2,... D, они имеют одинаковое, но, вообще говоря, неизвестное распределение вероятностей PD (·). Мы можем проводить эксперименты, контролируя число ресурсов Mn и тактовую частоту zn вычислителя и измеряя на симуляторе (либо на прототипе устройства) энергопотребление yn для входных данных dn D, возможно с помехами vn.

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

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

1.2.6 Организация контроля учебного процесса Задача организации контроля учебного процесса, описанная в [26], представляется очень актуальной с практической точки зрения, так как именно эту задачу приходится решать на разных административных уровнях при планировании учебного процесса на кафедре, в ВУЗе, городе или стране в целом.

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

В работе [26] сделана попытка формализовать понятия состояния учебного процесса, измерения этого состояния, управления учебным процессом и результата этого управления.

Будем считать, что текущее состояние учебного процесса определяется вектором w в p-мерном вещественном пространстве:

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

Многие компоненты вектора текущего состояния w трудно (а иногда и невозможно) определить в конкретный момент времени. Например, не всегда легко количественно выразить качественный уровень подготовки того или иного студента.

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

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

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

Здесь q размерность вектора управлений, X некоторое (обычно ограниченное) множество возможных значений управлений.

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

Можно считать, что оценка качества принятия управленческих решений представляется некоторым функционалом F (x, w). Задание функционала качества позволяет нам перейти к формализации понятия о цели принятия решения и определить функционал среднего риска:

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

1.2.7 Задача самообучения В работах [15], [22] и [23] рассмотрена следующая задача: на вход самообучающейся опознающей системы поступают сигналы w принадлежащие одному из l классов (число классов конечно и известно заранее).

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

Рассмотрим несколько примеров, имеющих простой геометрический смысл:

1. Функционал среднего риска для классификатора минимальных расстояний. Пусть функции потерь представляют собой квадраты евклидовых расстояний:

В этом случае центр класса совпадает с его центром тяжести, а минимизация функционала состоит в выделении компактных подмножеств Wk (X ) с минимальным среднеквадратичным рассеянием.

2. Функционал среднего риска для классификатора корреляционной группировки. Выберем следующий вид функции потерь:

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

1.3 Итеративные алгоритмы оценивания и оптимизации Даже классическая задача оптимизации не содержащая помех и не зависящая от случайных процессов, требует наложения некоторых ограничений на функцию f. Например, довольно часто ее считают дифференцируемой, так как поиск минимума в этом случае сводится к поиску точек, в которых дифференциал обращается в ноль. Большинство известных на данный момент итеративных алгоритмов оптимизации являются градиентными [38] или псевдоградиентными [34] то есть являются алгоритмами поиска нулей градиента оптимизируемой функции.

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

а градиентный метод поиска минимума:

представляет собой градиентный метод поиска корня:

В обоих этих методах значения градиента оптимизируемой функции предполагаются незашумленными и известными в любой точке. В году, в работе Кифера-Вольфовитца [65] была предложена процедура оптимизации функционала, градиент которого был неизвестен, и наблюдателю были доступны лишь зашумленные измерения yn :

В работе предполагалось, что помехи vn • взаимонезависимы, • одинаково распределены, • центрированы (в среднем равны нулю).

Эти ограничения предоставляют возможность получать оценку функционала f в точке xn путем многократного измерения и усреднения результата:

Усреднение в предложенном методе происходило неявным образом, за счет достаточно медленного стремления к нулю параметра алгоритма n.

Кифер и Вольфовитц также отказались от явного усреднения и применили процедуру Роббинса-Монро к конечноразностной оценке градиента (здесь ei единичные базисные вектора в Rq ):

Благодаря стремительному развитию вычислительной техники процедуры Роббинса-Монро и Кифера-Вольфовица получили широкое распространение. Большую роль в пропаганде подобных методов сыграл Я.З.Цыпкин. В своих книгах “Адаптация и обучение в автоматических системах” [50] и “Основы теории обучающихся систем” [51] он показал широкую применимость рекуррентных стохастических алгоритмов в задачах оценивания, идентификации, распознавания образов, оптимизации и управления. Позже, в работах [34, 38, 40, 41, 42, 52, 53] была оценена эффективность таких алгоритмов и найдены их оптимальные и робастные варианты.

К настоящему времени методика исследования свойств оценок, доставляемых рекуррентными алгоритмами оценивания и оптимизации при зашумленных наблюдениях, приобрела в целом достаточно законченный вид. Основой многих работ по оптимизации сходимости алгоритмов являются работы М.Вазана [1], М.Б.Невельсона и Р.З.Хасьминского [33], В.Я.Катковника [24, 25], Б.Т.Поляка [37], Я.З.Цыпкина и А.С.Позняка [53], в которых при предположении о центрированности и независимости помех для анализа свойств сходимости оценок и определения оптимальных способов выбора параметров алгоритмов использовались методы, основывающиеся на стохастическом методе Ляпунова или непосредственно оценивающие наихудшие значения статистических моментов ошибок оценивания. При коррелированных статистических помехах в работах Л.Льюнга [28, 68] и Г.Кушнера с соавторами [66, 67] на основе исследования характеристик слабой сходимости разработана методика анализа асимптотических свойств оценок рекуррентных алгоритмов, опирающаяся на изучение устойчивости решений соответствующих обыкновенных дифференциальных уравнений (ОДУ). Асимптотические характеристики предельных распределений ошибок оценивания алгоритмов стохастической аппроксимации часто исследуются, основываясь на работе В.Фабиана [60]. Стохастические квазиградиентные алгоритмы для решения задач невыпуклой оптимизации рассматривались Ю.М.Ермольевым [20], В.С.Михалевичем, А.М.Гупалом, В.И.Норкиным [32], С.П.Урясьевым [47] и др. В.Г.Гапошкин и Т.П.Красулина в [5] предложили способ изучения асимптотического поведения траекторий, базирующийся на законе повторного логарифма. В работе Э.Валкейлы и А.В.Мельникова [2] асимптотические свойства диффузионных и дискретных моделей стохастической аппроксимации изучаются на единой основе.

Первые исследования, учитывающие эти условия, начались на рубеже 80–90-х годов прошлого века. Основы этих исследований базируются на работах О.Н. Граничина [6, 7, 8, 9, 10], Б.Т. Поляка с А.Б.Цыбаковым и А.В.Гольденшлюгером [39, 63, 71], предложивших самые эффективные в широком классе алгоритмы, состоятельность которых обоснована при почти произвольных помехах, и Дж.Спала [74, 75, 76], показавшего существенное сокращение необходимого для оптимизации количества измерений исследуемой функции по сравнению с классическими схемами. Новый алгоритм в англоязычной литературе получил название oдновременно возмущаемая стохастическая аппроксимация (Simultaneous Perturbation Stochastic Approximation, SPSA), в русскоязычной рандомизированный алгоритм стохастической оптимизации, алгоритм стохастической аппроксимации с возмущением на входе или поисковый алгоритм стохастической аппроксимации. В 1993 году при разработке способов настройки параметров нейронных сетей похожие алгоритмы были предложены в работах Дж.Алспектора [56] и Ю.Маеды [70] с соавторами. Состоятельность рандомизированных алгоритмов при почти произвольных помехах позже исследовалась в работах Л.Льюнга с Л.Гао [69] и Х.-Ф.Чена, Т.Дункана, Б.Пассик-Дункан [57]. Стоит дополнительно отметить, что обоснованное включение пробного возмущения в канал управления при синтезе адаптивного оптимального управления впервые было одновременно предложено в 1986 году в работе О.Н.Граничина с В.Н.Фоминым [6], базирующейся на методе стохастической аппроксимации, и Х.-Ф.Ченом с Л.Гао [58], использовавшими для оценивания модифицированный МНК.

Особый интерес с точки зрения методов доказательства сходимости, состоятельности оценок и т. д. представляет цикл работ Б.Т.Поляка [35, 36] 1976 и 1977 годов, в котором исследованы общие свойства оценок достаточно широкого класса алгоритмов:

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

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

Среди последних исследований по данной теме, предшествовавших данной работе, необходимо упомянуть статьи О.Н.Граничина [11, 12, 13, 14, 61], и его книгу “Рандомизированные алгоритмы оценивания и оптимизации при почти произвольных помехах” [16], написанную в соавторстве с Б.Т.Поляком, в которых представлены четкая формулировка задачи, основные виды рандомизированных алгоритмов и условия состоятельности их оценок. Некоторые из этих условий удалось ослабить в рамках представленной диссертации. Одним из недостатков указанных работ является отсутствие формулировки критерия, по которому итерации алгоритма имеет смысл прекратить. Подобный критерий (оценка результата работы после конечного числа итераций) сформулирован в следующей главе и опубликован в работе [46].

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

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

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

Большинство псевдоградиентных методов оптимизации, типа процедуры Кифера-Вольфовитца [65], требуют нескольких измерений функции потерь на итерации. Эти ограничения подразумевают необходимость на каждой итерации измерять минимизируемую функцию в нескольких разных точках. Если же вид самой функции меняется со временем, или каждое ее измерение зависит от реализации некоторой случайной величины, и требуется минимизировать ее в среднем то многократное измерение функции в одной точке становится невозможным. Подобная ситуация возникает, например, в задачах оптимизации систем реального времени.

Алгоритмы, вписывающиеся в такие ограничения, были предложены в конце 80-х, начале 90-х годов в работах [6, 7, 8, 9, 10, 39, 63, 71, 74, 75, 76]. Они получили название рандомизированных алгоритмов стохастической оптимизации, в силу того, что входные данные в этих алгоритмах подвергаются искусственной рандомизации на каждом шаге.

Среди основных достоинств этих алгоритмов можно назвать сходимость при “почти произвольных” помехах [16] и малое (одно - два) количество измерений функции потерь на итерации.

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

2.1 Постановка задачи и основные предположения Пусть F (x, w) : Rq Rp R1 дифференцируемая по первому аргументу функция, x1, x2.. . выбираемая экспериментатором последовательность точек измерения (план наблюдения), в которых в каждый момент времени n = 1, 2,... доступно наблюдению с аддитивными помехами vn значение функции F (·, wn ) где {wn } неконтролируемая последовательность случайных величин (wn R ), имеющих одинаковое, вообще говоря, неизвестное распределение Pw (·) с конечным носителем.

Постановка задачи. Требуется по наблюдениям y1, y2... построить последовательность оценок {n } неизвестного вектора, минимизирующего функцию типа функционала среднего риска.

Пусть (1, 2]. Введем функцию Ляпунова где - искомый вектор из пространства параметров, и сформулируем основные предположения.

A.1 Функция f (x) имеет единственный минимум и с некоторой постоянной µ > 0.

2.2 Пробное возмущение и основной алгоритм Пусть n, n = 1, 2,... наблюдаемая последовательность независимых друг от друга случайных векторов в Rq, называемая в дальнейшем пробным одновременным возмущением, компоненты которых независимы между собой принимают значения ±1 с вероятностью 1. Зафиксируем некоторый начальный вектор 0 Rq и выберем некоторые последовательности положительных чисел {n } и {n }. В [7, 12] для построения последовательностей точек измерения {xn } и оценок {n } был предложен следующий алгоритм, использующий на каждом шаге (итерации) одно наблюдение:

2.3 Состоятельность оценок Обозначим W = supp(Pw (·)) Rp конечный носитель распределения Pw (·);

Fn -алгебру вероятностных событий, порождаемую случайными величинами 0, 1,..., n, формируемыми по алгоритму (1);

dn = diam(n ) диаметр множества n ;

Теорема 1 Пусть (1, 2] и выполнены условия:

(A.1) для функции f (x) = E{F (x, w)};

(A.2) для функции F (·, w) w W;

функции F (x, w) и x F (x, w) равномерно ограничены на W;

n 1 случайные величины v1,..., vn и вектора w1,..., wn1 не зависят от wn, n, а случайный вектор wn не зависит от n ;

Тогда:

1). последовательность оценок {n }, доставляемых алгоритмом (1), сходится к точке в следующем смысле:

4). Если, более того, тогда n при n с вероятностью единица, и Доказательство теоремы 1 приведено в последнем разделе этой главы.

Замечания: 1. Для функции F (x, w) = wf (x) условия теоремы 1 выполняются, если функция f (x) удовлетворяет условиям (A.1,2).

2. В теореме 1 помехи наблюдения vn можно условно назвать “почти произвольными”, так как они могут быть неслучайными, но неизвестными и ограниченными, или представлять из себя реализацию некоторого стохастического процесса с произвольной структурой зависимостей. В частности, для доказательства утверждений теоремы 1 нет необходимости предполагать что-либо о зависимости между vn и Fn1.

3. Для справедливости утверждения теоремы 1 совсем не обязательно предполагать, что компоненты векторов пробного одновременного возмущения n принимают значения только ±1. Достаточно предположить симметричность и конечность носителя их распределения.

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

Задача состоит в том, чтобы определить местоположение цели.

В качестве помехи выбирались случайные или детерминированные последовательности: |vn | 1, а числовые последовательности {n }, {n } были выбраны следующим образом:

Проектирование не использовалось. На рис. 1 показан типичный пример результата работы алгоритма после тысячи итераций. Координаты цели были выбраны: = (9.31, 8.98). В качестве помехи была задана постоянная величина vn = 0.5. Координаты получившейся оценки 1000 = (9.3, 9.01).

Заметим, что условия теоремы 1 являются только достаточными. В рассмотренном примере выполнены основные ограничения на минимизируемую функцию. Несмотря на то, что не выполнены все условия на числовые последовательности {n }, {n } и носитель W не является конечным, свойства получающихся последователностей оценок достаточно хорошие.

2.5 Алгоритмы с двумя измерениями функции потерь на итерации Помимо алгоритма с одним измерением функционала потерь на итерации, в литературе (см. например [12, 16, 57, 66, 75]) часто рассматриваются рандомизированные алгоритмы с двумя измерениями:

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

Условия состоятельности оценок алгоритмов с двумя измерениями в несколько более общем случае можно найти, например, в [16].

2.6 Квантовый компьютер и вычисление оценки вектора-градиента функции Рассмотрим проблему выбора вычислительного устройства, наилучшим образом подходящего для выполнения рандомизированного алгоритма стохастической оптимизации с одним измерением функции штрафа на итерации. В [12, 16] был описан способ реализации алгоритма (1) на вычислительных устройствах нового типа квантовых компьютерах. За прошедшее время терминология и аксиоматика моделей квантовых вычислений стали более четкими. Описанный в [12, 16] способ реализации не был похож на типичный “квантовый” алгоритм, и сейчас можно сказать, что выбранный ранее способ представления не был удачным. Здесь мы опишем новый способ представления алгоритма на квантовом компьютере, который в большей мере соответствует общей логике квантовых вычислительных алгоритмов.

До недавнего времени квантовый компьютер рассматривался исключительно как умозрительная математическая модель. Однако в последнее время, благодаря успехам компании IBM в построении квантового вычислителя на базе ядерно-магнитного резонанса, эта модель перестает быть только умозрительной (см. [64]). Конечно, на данный момент существуют серьезные сомнения в том, что проблема построения практически полезного квантового компьютера имеет решение, однако работы в этом направлении ведутся с высокой интенсивностью.

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

Состояние квантового компьютера это состояние некоторой квантовой системы. Состояние простейшей квантовой системы единичный вектор в двумерном комплексном пространстве. Базис этого пространства обычно обозначается как |0 и |1, по аналогии с {0, 1} в классической теорией информации. Такая система может принимать не только базисные значения, и, следовательно, способна хранить больше информации нежели соответствующая классическая. Тем не менее, при измерении такой системы, она перейдет в одно из базисных значений (в случае правильно выбранной наблюдаемой), и информация, хранимая в ней будет соответствовать некоторой классической информации. Описанная квантовая система называется “кубит” (“квантовый бит”), по аналогии с классическим “битом”. Квантовая система из нескольких кубитов представляется как их тензорное произведение. Таким образом, размерность пространства, с которым оперирует квантовый компьютер, растет экспоненциально с ростом числа кубитов. Это свойство лежит в основе феномена “квантового параллелизма”. Достаточно строгое обоснование математической модели квантовых вычислений можно найти, например, в [73].

Еще одним важным свойством квантовых состояний является то, что их эволюция унитарна. Иными словами, любое преобразование кубитов в квантовом компьютере является унитарным оператором в соответствующем комплексном пространстве. Отсюда следует, что все преобразования информации (кроме измерения) в квантовом компьютере должны быть обратимы. Пусть f : Rq R некоторая функция, удовлетворяющая условиям теоремы 1. Предположим, что разрядность используемого квантового вычислителя равна l. Унитарный оператор, реализующий на квантовом компьютере функцию f (x), можно задать на всех классических двоичных цепочках x длины l q, определяющих аргумент функции, так:

где y произвольная двоичная цепочка длины l, побитовоя операция “логического или”. Это способ задания оператора на базисных векторах. На все остальные вектора оператор продолжается линейно. Легко видеть, что построенный оператор обратим и действует в комплексном пространстве размерности 2ql+l.

Рассмотрим задачу: получить следующую оценку точки минимума функции по алгоритму (1). Для подачи на вход вычислителя подготовим суперпозицию 2q возмущенных значений текущего вектора оценки:

где ±1 рассматриваются как l-разрядные числа. После применения унитарного оператора Uf к |xn |0 получаем Из общих свойств модели квантовых вычислений [73] следует, что после измерения полученного состояния, с вероятностью 21q будет получен один из векторов вида Из первых l q разрядов этого вектора легко получить реализацию вектора случайного возмущения i. По алгоритму (1) координаты вектора i надо умножить на соответствующее значение функции потерь в возмущенной точке, которое записано в последних l разрядах полученного после измерения результата.

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

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

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

Сегодня наилучший способ построения быстрых вычислительных устройств заключается в организации параллельных вычислений для переработки больших объемов информации. Наиболее перспективны здесь два направления. Первое связано с созданием классических электронных устройств, таких как VLSIC (Very Large Scale Integrated Circuits).

На данный момент доступна технология “0.1 микрон”, и анонсируется технология “0.06 микрон”. Процессоры, построенные по этим технологиям способны одновременно выполнять сотни тысяч операций. Компания IBM объявила, что в течении нескольких лет будет создано устройство, выполняющее одновременно миллион вычислительных операций. Такие вычислительные мощности позволят быстро обращать матрицы больших размеров, что необходимо в задачах, связанных с распознаванием.

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

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

В [62] был предложен один из возможных подходов к созданию интеллектуальной системы. Термин “интеллектуальная” подразумевает способность системы адаптироваться к меняющемуся окружению посредством выбора задачи, которую необходимо решить в текущий момент.

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

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

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

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

Здесь m натуральное число (1, 2, 3 или 100000, 1000000). Представим, что наши устройства реализованы в виде молекул (квантовых компьютеров), взаимодействующих друг с другом и “свернутых”, например, в спираль или шар Подобная пространственная форма может облегчить одновременность для всех устройств некоторого биологического или физического воздействия. Положим, что поведение каждого из устройств определяется его внутренней структурой, потоком данных из внешнего мира и некоторым конечным набором параметров (i) из множества i Все параметры системы в этом случае могут быть перечислены следующим образом:

Пусть эта схема удовлетворяет обоим перечисленным выше условием.

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

Приведем для примера задачу, для решения которой подобная схема представляется подходящей. Предположим, что у нас есть набор устройств, способных распознавать определенные виды изображений (каждое из устройств настроено на какой-либо конкретный объект). Все эти устройства получают в реальном времени изображение с некоторой цифровой камеры. В каждый момент времени только одно из устройств, объявившее себя главным, может управлять камерой. Существует также одно устройство, управляющее камерой в случаях, когда никто не объявил себя главным. Оно может действовать по какому-нибудь простому алгоритму - например осматриваться или сканировать некоторый важный участок, в котором ожидается появление объектов. Картинка с камеры постоянно подается на входы всех распознавателей, и те в свою очередь пытаются распознать в ней свой объект. Результатом их работы является степень совпадения в процентах (например, объект является кошкой с вероятностью 75%). Если у какого-то из устройств степень достоверности превысила некий заранее установленный порог (например, 90%), то это устройство объявляет себя главным и берет на себя управление камерой для более детального изучения объекта или слежения за ним.

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

• в резонанс вошло только одно устройство, • в резонанс вошли несколько устройств, • ни одно из устройств не вошло в резонанс.

Первый случай уже был описан ранее. Во втором можно выбрать главное устройство по каким-либо показателям силы (качества) резонанса (в последнем примере - по величине показателя достоверности распознавания). Третий случай наиболее интересен. Он может например означать, что параметры устройств надо настроить для получения резонанса, что ставит перед нами задачу многомерной оптимизации:

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

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

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

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

2.8 Доказательство теоремы Рассмотрим алгоритм (1). Используя свойства выбранной функции Ляпунова и теорему Лагранжа о среднем, нетрудно получить Здесь mid - средняя точка из теоремы Лагранжа. Применив к полученному выражению операцию условного математического ожидания относительно -алгебры Fn1, имеем Здесь [0, n ] множитель из теоремы Лагранжа. Воспользовавшись условием (A.1), получаем Применив условие (A.2) и неравенство (x + y) 21 (x + y ) к последнему члену в правой части неравенства, выводим Взяв безусловное математическое ожидание от левой и правой частей исходного неравенства и, обозначив ln = E{V (n )}, получаем неравенства из выполнения которых и конкретных условий теоремы 1 все ее утверждения непосредственно выводятся из соответствующих утверждений [35].

Доказательство теоремы 1 закончено.

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

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

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

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

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

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

Одним из способов приближения такого значения t на основе имеющейся информации является предлагающийся в литературе (см., например, [67]) алгоритм где Jt,i индикаторная функция того, что заявка была послана в i-тый сервер и принята там, а некоторый малый параметр алгоритма.

P[a,b] проектор на отрезок [a, b], лежащий в отрезке [0, 1]. Значения a и b следует выбирать близкими к 0 и 1 соответственно, но не равными им, так как в случае попадания t на границу отрезка, алгоритм оказывается в “мертвой” точке. Начальное значение можно выбрать любым из отрезка [a, b]. Параметр влияет на скорость изменения, о его правильном выборе будет написано ниже. Обозначим математические ожидания величин Jt,1 и Jt,2 :

где i загруженность i-того канала. Введем функцию g(, ):

Исходя из введенных обозначений, перепишем алгоритм (4) следующим образом:

Учитывая, что Mn являются мартингальными разностями [67], и, следовательно, стремятся к нулю на бесконечности, можно увидеть, что алгоритм (4) есть ни что иное, как итеративное вычисление корня функции g(, ) методом Роббинса-Монро. В то же время, равенство функции g(, ) нулю означает равенство математических ожиданий величин Jn,i, что гарантирует в среднем равномерную загруженность каналов.

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

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

На рис. 3 показано, как предлагаемый алгоритм позволяет снизить значения штрафной функции при изначально неправильно угаданном соотношении каналов. Количество каналов в серверах 4 для первого и 8 для второго. Соответственно, оптимальное = 4 / (4 + 8) = 1/3. В начале выбирается неоптимальное = 0.9, и на 45-той секунде запускается адаптивный алгоритм, существенно снижающий значения штрафной функции. На рис. 4 отражена ситуация, при которой адаптивный алгоритм запускается после теоретически оптимального. Все то же самое, только с самого начала берется оптимальным, а на 45-той секунде включается адаптивный алгоритм. Видно, что адаптивный выбор фактически не хуже оптимального. Следует отметить, что теоретически оптимальный алгоритм зависит от параметров каналов (N (1) и N (2) ), которые в реальной ситуации могут меняться со временем. Адаптивный алгоритм напрямую не зависит от этих параметров, что позволяет ему отслеживать их изменения. На рис. 5 и 6 показаны ситуации, в которых адаптивный алгоритм выигрывает у алгоритма с жестко прописанным Рис. 3:

Рис. 4:

, когда оптимальное значение изменяется.

Pages: |

| 2 |

Главная >> Диссертации - все темы

[ СКАЧАТЬ ОРИГИНАЛ ДОКУМЕНТА .pdf ]

Похожие работы:

«БАРАКИН Николай Сергеевич ПАРАМЕТРЫ ОБМОТКИ СТАТОРА И РЕЖИМЫ АСИНХРОННОГО ГЕНЕРАТОРА, ПОВЫШАЮЩИЕ КАЧЕСТВО ЭЛЕКТРОЭНЕРГИИ ДЛЯ ПИТАНИЯ ЭЛЕКТРООБОРУДОВАНИЯ ПОЧВЕННОЭКОЛОГИЧЕСКОЙ ЛАБОРАТОРИИ Специальность: 05.20.02. - Электротехнологии и электрооборудование в сельском хозяйстве Диссертация на соискание...»

«Анкудинова Полина Михайловна ЭВОЛЮЦИОННОЕ СТАНОВЛЕНИЕ ЧЕЛОВЕКА В ФИЛОСОФСКО-АНТРОПОЛОГИЧЕСКИХ КОНЦЕПЦИЯХ ХХ ВЕКА: МИРОВОЗЗРЕНЧЕСКИЙ АСПЕКТ Специальность 09.00.13 – философская антропология, философия культуры Диссертация на соискание ученой степени кандидата философских наук Научный руководитель : доктор философских наук,...»

«БРИЧКИН АНДРЕЙ СЕРГЕЕВИЧ ВЛИЯНИЕ SP-D ОБМЕННОГО ВЗАИМОДЕЙСТВИЯ НА ЭКСИТОННЫЕ СОСТОЯНИЯ В ПОЛУМАГНИТНЫХ ПОЛУПРОВОДНИКОВЫХ КВАНТОВЫХ ЯМАХ И ТОЧКАХ 01.04.07 – физика конденсированного состояния ДИССЕРТАЦИЯ на соискание учёной степени кандидата физико-математических наук Научный руководитель : Доктор физико-математических наук, профессор Кулаковский Владимир Дмитриевич Черноголовка Оглавление: Введение 1. Литературный обзор....»

«ИЗ ФОНДОВ РОССИЙСКОЙ ГОСУДАРСТВЕННОЙ БИБЛИОТЕКИ Марьянчик, Виктория Анатольевна Аксиологическая функция неологизмов медиаполитического дискурса Москва Российская государственная библиотека diss.rsl.ru 2006 Марьянчик, Виктория Анатольевна Аксиологическая функция неологизмов медиаполитического дискурса : [Электронный ресурс] : На материале газетных публикаций начала XXI века : Дис.. канд. филол. наук : 10.02.01. Архангельск: РГБ, 2006 (Из фондов Российской Государственной Библиотеки)...»

«Обущенко Сергей Владимирович АГРОЭКОЛОГИЧЕСКОЕ ОБОСНОВАНИЕ СИСТЕМ ВОСПРОИЗВОДСТВА ПОЧВЕННОГО ПЛОДОРОДИЯ В ПОЛЕВЫХ СЕВООБОРОТАХ СРЕДНЕГО ЗАВОЛЖЬЯ 06.01.01 – общее земледелие Диссертация на соискание ученой степени доктора сельскохозяйственных наук Научный консультант д. с.-х. н., профессор, академик РАСХН...»

«МИХАЙЛОВА ОЛЕСЯ СЕРГЕЕВНА БИБЛЕЙСКОЕ ПОВЕСТВОВАНИЕ В ИТАЛЬЯНСКОЙ ОПЕРЕ ПЕРВОЙ ПОЛОВИНЫ XIX ВЕКА (МОИСЕЙ ДЖ. РОССИНИ, НАВУХОДОНОСОР ДЖ. ВЕРДИ) 17.00.02 – музыкальное искусство Диссертация на соискание учёной степени кандидата искусствоведения Научный руководитель доцент, кандидат искусствоведения ДЁМИНА И.К. Ростов-на-Дону – ОГЛАВЛЕНИЕ...»

«Шепелева Лариса Петровна КОМПЬЮТЕРНАЯ ТОМОГРАФИЯ В ДИАГНОСТИКЕ ПЕРВИЧНОГО ТУБЕРКУЛЕЗА ОРГАНОВ ДЫХАНИЯ У ДЕТЕЙ И ПОДРОСТКОВ 14.01.16. – фтизиатрия 14.01.13. - лучевая диагностика и лучевая терапия ДИССЕРТАЦИЯ на соискание ученой степени доктора медицинских наук Научные консультанты: доктор медицинских наук, профессор АКСЕНОВА...»

«ИЗ ФОНДОВ РОССИЙСКОЙ ГОСУДАРСТВЕННОЙ БИБЛИОТЕКИ Заблоцкий, Петр Николаевич Совершенствование деятельности по использованию криминалистических учетов в раскрытии и расследовании преступлений Москва Российская государственная библиотека diss.rsl.ru 2006 Заблоцкий, Петр Николаевич Совершенствование деятельности по использованию криминалистических учетов в раскрытии и расследовании преступлений : [Электронный ресурс] : Дис. . канд. юрид. наук : 12.00.09. Волгоград: РГБ, 2006 (Из фондов...»

«Сайдумов Джамбулат Хамидович СУД, ПРАВО И ПРАВОСУДИЕ У ЧЕЧЕНЦЕВ И ИНГУШЕЙ (ХVIII–ХХ вв.) Диссертация на соискание ученой степени доктора юридических наук Специальность – 12.00.01-теория и история права и государства; история учений о праве и государстве Грозный – 2014 1 СОДЕРЖАНИЕ: ВВЕДЕНИЕ ГЛАВА I. ИСТОРИЧЕСКИЙ ГЕНЕЗИС И ЭВОЛЮЦИЯ ТРАДИЦИЙ ПРАВА И ПРАВОСУДИЯ У ЧЕЧЕНЦЕВ И ИНГУШЕЙ §1....»

«УДК 519.21 Демичев Вадим Петрович ПРЕДЕЛЬНЫЕ ТЕОРЕМЫ ДЛЯ НЕЛИНЕЙНЫХ ФУНКЦИЙ ОТ СЛАБО ЗАВИСИМЫХ СЛУЧАЙНЫХ ПОЛЕЙ 01.01.05 теория вероятностей и математическая статистика Диссертация на соискание ученой степени кандидата физико-математических наук Научный руководитель доктор физико-математических наук, профессор А. В. Булинский Москва 2013 2 Оглавление Введение Глава 1. Ковариационные и моментные оценки для слабо...»

«Селиверстов Владимир Валерьевич Проблема статуса несуществующих вещей в майнонгианской философской традиции 09.00.01 – Онтология и теория познания Диссертация на соискание ученой степени кандидата философских наук Научный руководитель доктор философских наук, профессор Порус Владимир Натанович. Москва – 2013 год 1 Содержание Введение..4 Проблема беспредметных представлений в I. брентановской философской...»

«Шагин Иван Анатольевич Специальность: 07.00.02 – Отечественная история Диссертация на соискание учёной степени кандидата исторических наук Становление судебных учреждений советского государства в 1917 – 1927 гг. (по материалам Псковской губернии) Научный руководитель : кандидат исторических наук, профессор А.В. Филимонов Псков 2014 2 Содержание Введение ГЛАВА I. Создание советского суда в Псковской...»

«ПОСТОВАЛОВ СЕРГЕЙ НИКОЛАЕВИЧ СТАТИСТИЧЕСКИЙ АНАЛИЗ ИНТЕРВАЛЬНЫХ НАБЛЮДЕНИЙ ОДНОМЕРНЫХ НЕПРЕРЫВНЫХ СЛУЧАЙНЫХ ВЕЛИЧИН Специальность 05.13.16 — применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (в области технических наук ) Диссертация на соискание ученой степени кандидата технических наук...»

«Сологуб Глеб Борисович РАЗРАБОТКА МАТЕМАТИЧЕСКИХ МЕТОДОВ И КОМПЛЕКСА ПРОГРАММНЫХ СРЕДСТВ ИМИТАЦИОННОГО ТЕСТИРОВАНИЯ ЗНАНИЙ НА ОСНОВЕ СЕМАНТИЧЕСКИХ МОДЕЛЕЙ 05.13.18 — математическое моделирование, численные методы и комплексы программ 05.13.11 —...»

«ЦЗЮЙ Чжаочунь ПРОЦЕСС ОБУЧЕНИЯ ИЗОБРАЗИТЕЛЬНОМУ ИСКУССТВУ В СИСТЕМЕ ВЫСШЕГО ХУДОЖЕСТВЕННО-ПЕДАГОГИЧЕСКОГО ОБРАЗОВАНИЯ РОССИИ И КИТАЯ 13.00.01 — общая педагогика, история педагогики и образования ДИССЕРТАЦИЯ на соискание ученой степени кандидата педагогических наук Научный руководитель : доктор педагогических...»

«Махалин Александр Николаевич ОБОСНОВАНИЕ СТРУКТУРЫ И ПАРАМЕТРОВ ЭЛЕКТРОТЕХНИЧЕСКИХ КОМПЛЕКСОВ ОБЪЕКТОВ ГАЗОТРАНСПОРТНЫХ СИСТЕМ Специальность 05.09.03 – Электротехнические комплексы и системы ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук НАУЧНЫЙ...»

«Жидкова Юнна Юрьевна РАЗРАБОТКА СОСТАВА И ФАРМАКОТЕХНОЛОГИЧЕСКИЕ ИССЛЕДОВАНИЯ КОМПОЗИТНЫХ ГЕЛЕЙ ДЛЯ ПРОФИЛАКТИКИ ГИПЕРТРОФИЧЕСКИХ И КЕЛОИДНЫХ РУБЦОВ 14.04.01. – технология получения лекарств ДИССЕРТАЦИЯ на соискание ученой степени кандидата фармацевтических наук Научный руководитель :...»

«ПАРИЖСКИЙ СЕМЕН ГЕОРГИЕВИЧ СООТНОШЕНИЕ ПОЭЗИИ И ПРОЗЫ В МАКАМАХ НА ИВРИТЕ XII-XIII ВВ. Специальность 10.01.03 – литература народов стран зарубежья (литературы стран Азии и Африки) ДИССЕРТАЦИЯ на соискание ученой степени кандидата филологических наук Научный руководитель – доктор исторических наук Якерсон С. М. Санкт-Петербург ОГЛАВЛЕНИЕ Введение... Глава 1 Историко-литературные предпосылки появления художественной прозы...»

«АЛЕКСАНДРОВ НИКОЛАЙ ВАСИЛЬЕВИЧ ИССЛЕДОВАНИЕ ВЛИЯНИЯ СВЕРХПРОВОДНИКОВЫХ ТРАНСФОРМАТОРОВ НА РЕЖИМЫ ЭЛЕКТРОЭНЕРГЕТИЧЕСКИХ СИСТЕМ Специальность 05.14.02 – Электрические станции и электроэнергетические системы Диссертация на соискание ученой степени кандидата технических наук Научный руководитель доктор технических наук,...»

«Дмитрий Сергеевич Ганенков КОНТАКТНЫЕ ЛОКАЛИЗАЦИИ В НАХСКО-ДАГЕСТАНСКИХ ЯЗЫКАХ И ИХ ТИПОЛОГИЧЕСКИЕ ПАРАЛЛЕЛИ Специальность 10.02.20 Сравнительно-историческое, типологическое и сопоставительное языкознание Диссертация на соискание ученой степени кандидата филологических наук Научный руководитель доктор филологических наук, профессор Владимир Александрович Плунгян Оглавление ОГЛАВЛЕНИЕ ОБЩАЯ...»

наверх

<< ГЛАВНАЯ | КОНТАКТЫ

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА (Авторефераты, диссертации, методички, учебные программы, монографии)