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

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

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

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

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

ЭФФЕКТИВНОСТИ РАБОТЫ ВЫЧИСЛИТЕЛЬНЫХ КОМПЛЕКСОВ И СЕТЕЙ

05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

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

Санкт-Петербург 2005

Работа выполнена на кафедре системного программирования математико-механического факультета Санкт-Петербургского Государственного Университета.

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

доцент Граничин Олег Николаевич

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

доктор физико-математических наук, профессор Мелас Вячеслав Борисович кандидат технических наук Кудинов Александр Михайлович

Ведущая организация: Санкт-Петербургский институт

информатики и автоматизации РАН

Защита диссертации состоится " " 2005 года в /У часов

на заседании диссертационного совета Д 212.232.51 по защите диссертаций на соискание ученой степени доктора наук при Санкт-Петербургском государственном университете по адресу 198504, Санкт-Петербург, Старый Петергоф, Университетский пр.,28, Математико-механический факультет.

С диссертацией можно ознакомиться в Научной библиотеке Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб. 7/9

Автореферат разослан "_"_2005 г.

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

диссертационного совета

доктор физико-математических наук

Б. К. Мартыненко

to 9

Общая характеристика работы

Актуальность темы. Задача поиска минимума (максимума) некоторой функции (функционала)

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

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

В 1952 году, в работе Кифера-Вольфовица (Ann. Math. Statist., vol. 23), была предложена процедура оптимизации функционала, градиент которого был неизвестен, и наблюдателю были доступны лишь зашум-ленныс измерения уп. В работе предполагалось, что помехи измерения взаимонезависимы, одинаково распределены и центрированы (в среднем равны нулю). Эти ограничения предоставляют возможность получать оценку функционала / в некоторой точке путем многократного измерения и усреднения результата.

f{x) min

Ранее в 1951 году вышла статья Роббинса и Монро (Ann. Math. Statist., vol. 22), в которой решалась задача поиска корня функции, измеряемой с помехами, на которые накладывались точно такие же ограничения. Роббинс и Монро воспользовались модификацией градиентного метода и отказались от усреднения на каждом шаге, предложив алгоритм

1 = 2-71 ®пУп'

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

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

К настоящему времени методика исследования свойств оценок, доставляемых рекуррентными алгоритмами оценивания и оптимизации при зашумленных наблюдениях, приобрела в целом достаточно законченный вид. Основой многих работ по оптимизации сходимости алгоритмов являются работы М.Вазана, М.Б.Невельсона и Р.З.Хасьминско-го, В.Я.Катковника, Я З.Цыпкина, Б Т.Поляка, А.С.Позняка и О.Н.Гра-ничина.

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

следуемой функции потерь неизвестны, а измерение значений самой функции доступны чаще всего с помехами. В русскоязычной литературе эти алгоритмы исследовались, например, в работах Л А Растригина, А.Жилинскаса, С.М.Ермакова, В.Б.Меласа и А.А.Жиглявского.

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

Появление этих алгоритмов было обусловлено требованиями задач реального времени к сокращению количества вычислений функционала потерь на каждой итерации и необходимостью расширить класс допустимых помех. Предполагалась, например, возможная взаимозависимость помех, обусловленная намеренными действиями противника (глушение сигнала, и т. д.). Первые исследования, учитывающие эти условия, начались на рубеже 80-90-х годов прошлого века. Основы этих исследований базируются на работах О.Н. Граничина, Б.Т. Поляка с А.Б.Цыбаковым и А.В.Гольденшлюгером, Дж.Спала.

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

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

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

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

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

терь при конечном числе итераций.

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

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

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

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

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

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

2005 г), а также на семинарах кафедры системного программирования математико-механического факультета Санкт-Петербургского государственного университета.

Публикации. Основные результаты диссертации опубликованы в работах [1] — [6].

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

Содержание работы

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

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

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

Уп = f(xn) + vn.

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

уп = F(xn,wn)+vn.

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

f(x) = Ew{F(x,w)} ->■ min,

где Ет — условное математическое ожидание При этом функционал / принято называть функционалом среднего риска

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

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

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

Пусть Р(х,и>) : I' х Кр К1 — дифференцируемая по первому аргументу функция, Х\,Х2 - ■ ■ — выбираемая экспериментатором последовательность точек измерения (план наблюдения), в которых в каждый момент времени п = 1,2,... доступно наблюдению с аддитивными помехами уп значение функции Г(-,и}п)•

Уп = ^(аг„,гу„) + ип,

где {«;„} — неконтролируемая последовательность случайных величин (тп £ Ер), имеющих одинаковое, вообще говоря, неизвестное распределение Рш(-) с конечным носителем.

Требуется по наблюдениям 2/1,2/2-■■ построить последовательность оценок {дп} неизвестного вектора в*, минимизирующего функцию

/(х) = Еи]{Р(х,ю)} = [ Г(х,и>)РШ(А|;) Jw

типа функционала среднего риска.

Далее мы будем использовать обозначения || • || и (•, •} для евклидовой нормы и скалярного произведения в К9. Пусть р £ (1,2] Введем функцию Ляпунова

У(х) = \\х-в*Г,

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

А.1 Функция /(х) имеет единственный минимум в точке 0* и (УУ(ж), У/(х)) > рУ{х), Ух е К« с некоторой постоянной ¡л > 0.

А.2 При любом ю градиенты функций удовлетворяют условию

Гельдера с показателем р — 1

\\ЧхР(х,п)-ЧхР{у,ю)\\ <М\\х-у\\г-\ У®,уе№ с некоторой постоянной М > 0.

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

Зафиксируем некоторый начальный вектор £ и выберем некоторые последовательности положительных чисел, стремящиеся к нулю: {<*«} и {/?„}.

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

хп = вп-1 + Рп&п, Уп = и>п) + уп ,

В этом алгоритме Теп(-), тг = 1,2,... —- операторы проектирования на некоторые выпуклые замкнутые ограниченные подмножества 0„ С содержащие, начиная с некоторого п > 0, точку в*. Если заранее

известно замкнутое ограниченное выпуклое множество ©, содержащее точку в*, то можно считать ©п = 0. В противном случае множества {<ЭП} могут расширяться до бесконечности

Обозначим W = зирр(Р,„(-)) С I' - конечный носитель распределения Р№(-); Тп сг-алгебру вероятностных событий, порождаемую случайными величинами в\,..., вп. формируемыми по предлагаемому алгоритму;

¿п = сНат(6п) — диаметр множества 6„;

сп - 2ГрЧР/2аРп№, 7п = апМ -

фп = 2МрйРп~1апрп + 2"-Ч пвд \Р{в\ Ш)\р + 2

Теорема 1. Пусть р € (1,2] и выполнены условия: (А.1) для функции /(х) — ги)};

(А.2) для функции Уго € W:

функции Р(х, ги) и ЧХР(х, ш) равномерно ограничены на Уп > 1 случайные величины ..., г>„ и вектора гУ],..., гуп_х не зависят от гип, Ап, а случайный вектор вдп не зависит от Д„;

Е{\ьп\"}<ар,п = 1,2,...; Уп, 0 < 7„ < 1, ЕпТп = оо, Цп ->• 0, при п оо, где

Фп + СпСГ? ( /х„+Л 1 А«п = -, 1---•

1п V Мп ) 7п+1

Тогда:

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

Е{\\вп - в*\\р} О при п ->• оо.

2). Если Ей,,.*» гп > г > 1, то Я{У(0П)} = О (Щ^1 " 7»))•

3). Если гп>г>1Чп, то Е{У(вп)} < (Е{У(в0)}+^т) 1^(1-7,)■

4). Если, более того,

Фп + СпСТрп < оо

п

тогда 9п —> 0* при п -> оо с вероятностью единица, и

P{\\èa - *Т < е Vn > no} > 1 - Б^-^У + Т^Фп^

Доказательство теоремы приведено в последнем разделе второй главы диссертации.

Далее во второй главе рассмотрена проблема выбора вычислительного устройства, наилучшим образом подходящего для выполнения рандомизированного алгоритма стохастической оптимизации с одним измерением функции штрафа на итерации. В работе О.Н.Граничина (АиТ, 2002, №2) был описан способ реализации алгоритма (1) на вычислительных устройствах нового типа — квантовых компьютерах. За прошедшее время терминология и аксиоматика моделей квантовых вычислений стали более четкими Описанный ранее способ реализации не был похож на типичный "квантовый" алгоритм, и сейчас можно сказать, что выбранный ранее способ представления не был удачным В разделе 2.6 описан новый способ представления алгоритма на квантовом компьютере, который в большей мере соответствует общей логике квантовых вычислительных алгоритмов.

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

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

Начинается третья глава с рассмотрения задачи балансировки загрузки. Рассмотрим систему, состоящую из двух серверов, способных параллельно обрабатывать NW и iV® заявок, и балансировщика загрузки — устройства, в реальном времени принимающего решение, к какому из серверов отправить пришедшую в текущий момент времени заявку. Значения N^ и N^ могут меняться со временем, и считаются

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

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

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

• zt = 1, если в момент времени t пришла заявка, балансировщик

загрузки направил ее к серверу г, (г = 1,2), и на нем не нашлось свободных каналов, в то время как на другом сервере свободные каналы были,

• Zt = 0 во всех остальных случаях.

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

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

f(x) - E...{zt{x, ...)}-> min.

х

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

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

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

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

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

1 N

f(x) = q(х) + L{x) = q(x) + lim — E{Zl{x)} min,

i=i

где Zj(x) — время, которое задание, законченное i-м по счету, ожидало ("простаивало") в сервере до момента своего завершения.

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

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

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

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

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

Пусть заданы функции С2к(Х,и)), к £ 1,2,... ,1 (I — число классов), определяющих качество классификации и зависящих от матричного параметра X — {т,\,.... х;}, хг € который удобно интерпретировать как набор центров классов. Функционал среднего риска в задаче самообучения имеет смысл математического ожидания общих потерь и может быть записан следующим образом:

Ы1 М*)

где {1^(Л')}г<.=1 — разбиение выборочного пространства на I непересекающихся подмножеств

= {и> : (Зк(Х,ю) < <23(Х,ю)Л < А;} П П {ш : Як{Х, и!)<Я3(Х,и>),1>к}, к,] £1,2,...,1. Проблема самообучения распознаванию образов формулируется как поиск некой оценки X, минимизирующей предлагаемый функционал среднего риска — иными словами, задача заключается в поиске центров классов, наилучших с точки зрения функций £2к(Х,т)

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

f

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

Работы автора по теме диссертации

[1] Granichin O.N., Sysoev S.S. About Some Characteristics of Computers of New Generation //In Proceedings of the Physics and Control Conference, Saint-Petersburg, 2003, vol. 3, pp. 804-807.

[2] Сысоев С. С. Адаптивное управление распределением загрузки в простейшей вычислительной сети // Труды III международной конференции "Идентификация систем и задачи управления", М., 2004. С. 1563-1571.

[3] Измакова О. А., Сысоев С. С. Алгоритм стохастической оптимизации с возмущением на входе в задаче самообучения. // Труды Международной школы-семинара "Адаптивные роботы — 2004". М.-СПб. 2004. С. 49-52.

[4] Сысоев С. С. Рандомизированные алгоритмы стохастической оптимизации, квантовые компьютеры, искусственный интеллект // В сб. "Стохастическая оптимизация в информатике" под ред. О. Н. Гра-ничина. Изд-во С.-Петерб. ун-та. 2005. С. 206-221.

[5] Граничим О. Н., Сысоев С. С., Чуйко Д. С. Проблемы тестирования сервера как задачи о моделировании редких событий // В сб. "Стохастическая оптимизация в информатике" под ред. О. Н. Гра-ничина. Изд-во С.-Петерб. ун-та. 2005. С. 48-72.

[6] Chuyko D., Granichin O.N., Sysoev S. S. Simulation of rare events and probability estimation // In: Proceedings of the 5-th St. Petersburg Workshop on Simulation. St. Petersburg, 2005, pp. 215-220.

РНБ Русский фонд

2006-4 10994

Подписано в печать 15.09 2005 г. Формат бумаги 60X90 1/16. Бумага офсетная. Печать ризографическая. Объем 1 уел п. я Тираж 100 экз. Заказ № 1800026. Отпечатано в ООО "Анонс" с оригинал макета заказчика. 198095, Санкт-Петербург, ул. Розенштейна, д. 21

Введение.

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 Имитационное моделирование 50 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] была предложена процедура оптимизации функционала, градиент которого был неизвестен, и наблюдателю были доступны лишь зашумленные измерения уп. В работе предполагалось, что помехи измерения взаимонезависимы, одинаково распределены и центрированы (в среднем равны нулю). Эти ограничения предоставляют возможность получать оценку функционала / в некоторой точке путем многократного измерения и усреднения результата.

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

1 = &пУп•

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

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

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

К настоящему времени методика исследования свойств оценок, доставляемых рекуррентными алгоритмами оценивания и оптимизации при зашумленных наблюдениях, приобрела в целом достаточно законченный вид. Основой многих работ по оптимизации сходимости алгоритмов являются работы М.Вазана [1], М.Б.Невельсона и Р.З.Хасьминского [33],

B.Я.Катковника [24, 25], Б.Т.Поляка [37], Я.З.Цыпкина и А.С.Позняка [53], В.Фабиана [60], Л.Льюнга [28, 68], Г.Кушнера [66, 67], Ю.М.Ермольева [20], А.М.Гупала [32], С.П.Урясьева [47], В.Г.Гапошкина и Т.П.Красулиной [5], Э.Валкейлы и А.В.Мельникова [2], В.Н.Фомина, А.Л.Фрадкова, В.А.Якубовича [49], А.Б.Куржанского [27], Ф.Л.Черно-усько [54].

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

C.М.Ермакова и А.А.Жиглявского [18] при условии центрированности и независимости помех наблюдения.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

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

1. Вазан М. Стохастическая аппроксимация. М.: Мир, 1972.

2. Валкейла Э., Мельников А.В. Мартингальные модели стохастической аппроксимации и их сходимость // Теория вероятностей и её применения, 1999, вып. 2, с. 278-311.

3. Владимирович А. Г., Граничин О. Н. Обобщение концепции машины Тьюринга // В сб. тр. конф. "УИТ-2005". С.-Петербург. 2005.

4. Волкович Я.В., Граничин О.Н. Адаптивная оптимизация сервера, обрабатывающего очередь заданий // В сб. "Стохастическая оптимизация в информатике" под ред. О. Н. Граничина. Изд-во С.-Петерб. ун-та. 2005. С. 17-28.

5. Гапошкин В.Г., Красулина Т.П. О законе повторного логарифма для процессов стохастической аппроксимации // Теория вероятностей и её применения, 1974, вып. 4, с. 879-886.

6. Граничин О.Н., Фомин В.Н. Адаптивное управление с использованием пробных сигналов // Автоматика и телемеханика, 1986, №. 2, с. 100-112.

7. Граничин О.Н. Об одной стохастической рекуррентной процедуре при зависимых помехах в наблюдении, использующей на входе пробные возмущения // Вестник Ленингр. ун-та, сер. 1, 1989, вып. 1, с. 19-21.

8. Граничин О.Н. Алгоритм стохастической аппроксимации с возмущением на входе для идентификации статического нестационарного дискретного объекта // Вестник Ленингр. ун-та, сер. 1, 1988, вып. 3, с. 92-93.

9. Граничин О.Н. Процедура стохастической аппроксимации с возмущением на входе // Автоматика и телемеханика, 1992, №. 2, с. 97104.

10. Граничин О.Н. Оценивание точки минимума неизвестной функции, наблюдаемой на фоне зависимых помех // Проблемы передачи информации, 1992, № 2, с. 16-20.

11. Граничин О. Н. Оценивание параметров линейной регрессии при произвольных помехах // АиТ. 2002. JVa 1. С. 30-41 .

12. Граничин О. Н. Рандомизированные алгоритмы стохастической аппроксимации при произвольных помехах // АиТ. 2002. № 2. С. 4455.

13. Граничин О. Н. Неминимаксная фильтрация при неизвестных ограниченных помехах в наблюдениях // АиТ. 2002. № 9. С. 125— 133.

14. Граничин О. Н. Оптимальная скорость сходимости рандомизированных алгоритмов стохастической аппроксимации при произвольных помехах // АиТ. 2003. №2. С. 88-99.

15. Граничин О. Н., Измакова О. А. Рандомизированный алгоритм стохастической аппроксимации в задаче самообучения // АиТ. 2005. № 8. С. 52-63.

16. Граничин О. Н., Поляк Б. Т. Рандомизированные алгоритмы оценивания и оптимизации при почти произвольных помехах. М.: Наука, 2003. 291 с.

17. Граничин О. Н., Сысоев С. С., Чуйко Д. С. Проблемы тестирования сервера как задачи о моделировании редких событий // В сб. "Стохастическая оптимизация в информатике" под ред. О. Н. Гра-ничина. Изд-во С.-Петерб. ун-та. 2005. С. 48-72.

18. Ермаков С.М., Жиглявский А.А. Математическая теория оптимального эксперимента. М.:Наука, 1987, 320 с.

19. Ермаков С.М. Метод Монте-Карло и смежные вопросы. М.-.Наука, 1975, 471 с.

20. Ермольев Ю.М. О методе обобщенных стохастических градиентов и стохастических квазифейеровских последовательностях // Кибернетика, 1969, №. 2, с. 73-83.

21. Жилинскас А. Глобальная оптимизация. Вильнюс: Мокслас, 1986, 165с.

22. Измакова О. А. Рандомизированные алгоритмы самообучения для настройки ассоциативных нейронных сетей. // В сб. "Стохастическая оптимизация в информатике" под ред. О. Н. Граничина. Изд-во С.-Петерб. ун-та. 2005. С. 81-102.

23. Измакова О. А., Сысоев С. С. Алгоритм стохастической оптимизации с возмущением на входе в задаче самообучения. // Труды Международной школы-семинара "Адаптивные роботы — 2004". М.-СПб. 2004. С. 49-52.

24. Катковник В.Я. Линейные оценки и стохастические задачи оптимизации. М.: Наука, 1976, 487 с.

25. Катковник В.Я. Непараметрическая идентификация и сглаживание данных. М.: Наука, 1985.

26. Комаров С. Н. Информационные и математические модели организации контроля учебного процесса // В сб. "Стохастическая оптимизация в информатике" под ред. О. Н. Граничина. Изд-во С.-Петерб. ун-та. 2005. С. 103-132.

27. Куржанский А.Б. Управление и наблюдения в условиях неопределенности. М.: Наука, 1977, 392 с.

28. Лъюнг Л., Сёдерстрём Т. Идентификация систем: теория для пользователя. М.: Наука, 1991, 431 с.

29. Мелас В.Б. Общая теория функционального подхода к оптимальному планированию эксперимента1999, СПб., Изд-во С.-Петерб. ун-та.

30. Мелас В.В., Пепелышев А.Н. Степенные разложения неявных функций и локально оптимальные планы эксперимента //1999, Статистические модели с приложениями в эконометрике. СПб.: Изд-во НИХИ СПбГУ. С. 108-117.

31. Мелас В.Б., Пепелышев А.Н. Планы для оценивания точки экстремума квадратичной функции регрессии на гипершаре // 2001, Проблемы оптимизации дискретных систем. СПб.: Изд-во НИХИ СПбГУ. С. 70-86.

32. Михалевич B.C., Гупал A.M., Норкин В.И. Методы невыпуклой оптимизации. М.: Наука, 1987, 279 с.

33. Невелъсон М.Б., Хасъминский Р.З. Стохастическая аппроксимация и рекуррентное оценивание. М.: Наука, 1972, 304 с.

34. Поляк Б.Т., Цытгкин Я.З. Псевдоградиентные алгоритмы адаптации и обучения // Автоматика и телемеханика, 1973, №. 3, с. 45-68.

35. Поляк Б.Т. Сходимость и скорость сходимости итеративных стохастических алгоритмов. 1. Общий случай // Автоматика и телемеханика, 1976, № 12, с. 83-94.

36. Поляк Б. Т. Сходимость и скорость сходимости итеративных стохастических алгоритмов. 2. Линейный случай // Автоматика и телемеханика, 1977, Ж 4, с. 101-107.

37. Поляк Б. Т. Введение в оптимизацию. М.: Наука, 1983.

38. Поляк Б. Т., Цыпкин Я.З. Градиентные методы стохастической оптимизации // Измерения, контроль, автоматизация, 1989, №. 3, с. 50-54.

39. Поляк Б. Т., Цыбаков А.Б. Оптимальные порядки точности поисковых алгоритмов стохастической аппроксимации // Проблемы передачи информации, 1990, № 2, с. 45-53.

40. Поляк Б. Т., Цыпкин Я.З. Адаптивные алгоритмы оценивания (сходимость, оптимальность, устойчивость) // Автоматика и телемеханика, 1979, № 3, с. 71-84.

41. Поляк Б.Т., Цыпкин Я.З. Оптимальные псевдоградиентные алгоритмы адаптации // Автоматика и телемеханика, 1981, № 8, с. 7484.

42. Поляк Б.Т., Цыпкин Я.З. Робастные псевдоградиентные алгоритмы адаптации // Автоматика и телемеханика, 1981, № 10, с. 91-97.

43. Растригин JI.A. Статистические методы поиска. М.: Наука, 1968, 376 с.

44. Растригин Л.А. Адаптация сложных систем. Рига: Зинатне, 1981, 386 е.

45. Сысоев С.С. Адаптивное управление распределением загрузки в простейшей вычислительной сети // Труды международной конференции SICPRO'2004.

46. Сысоев С. С. Рандомизированные алгоритмы стохастической оптимизации, квантовые компьютеры, искусственный интеллект // В сб. "Стохастическая оптимизация в информатике" под ред. О. Н. Граничина. Изд-во С.-Петерб. ун-та. 2005. С. 206-221.

47. Урясъев С.П. Адаптивные алгоритмы стохастической оптимизации и теории игр. М.:Наука, 1990, 182 с.

48. Фаддеев Л. Д., Якубовский О. А. Лекции по квантовой механике для студентов-математиков. Изд-во РХД. 2001.

49. Фомин В.Н., Фрадков А.Л., Якубович В.А. Адаптивное управление динамическими объектами. М.: Наука, 1981, 448 с.

50. Цыпкин Я.З. Адаптация и обучение в автоматических системах. М.: Наука, 1968, 400 с.

51. Цыпкин Я.З. Основы теории обучающихся систем. М.: Наука, 1970, 252 с.

52. Цыпкин Я.З., Позняк А.С. Оптимальные поисковые алгоритмы стохастической оптимизации // Доклады АН СССР, 1981, т. 260, №. 3, с. 550-553.

53. Цыпкин Я.З., Позняк А. С. Рекуррентные алгоритмы оптимизации при неопределённости // Итоги науки и техники, сер. Технич. кибернетики, т. 16, М.: ВИНИТИ, 1983, с. 3-70.

54. Черноусъко Ф.Л. Оценивание фазового состояния динамических систем: метод эллипсоидов. М.: Наука, 1988, 319 с.

55. Якушкин С. И. Программная и аппаратная оптимизация при генерации вычислительных устройств // В сб. "Стохастическая оптимизация в информатике" под ред. О. Н. Граничина. Изд-во С.-Петерб. ун-та. 2005. С. 281-293.

56. Chen H.F., Duncan Т.Е., Pasik-Duncan B. A Kiefer-Wolfowitz Algorithm with Randomized Differences // IEEE Transactions on Automatic Control, 1999, vol. 44, №. 3, pp. 442-453.

57. Chen H.F., Guo L. Convergence Rate of Least-squares Stochastic Systems // Int. Journal of Control, 1986, vol. 44, Ж 5, pp. 1459-1477.

58. Chuyko D., Granichin O.N., Sysoev S. S. Simulation of rare events and probability estimation // In: Proceedings of the 5-th St. Petersburg Workshop on Simulation. St. Petersburg, 2005, pp. 215-220.

59. Fabian V. Stochastic approximation of minima with improved asymptotic speed // Ann. Math. Statist., 19G7, vol. 38, pp. 191-200.

60. Granichin O. N. Linear regression and filtering under nonstandard assumptions (Arbitrary noise) // IEEE Trans, on Automatic Control. 2004. Vol. 49. № 10. P. 1830-1835.

61. Granichin O.N., Sysoev S.S. About Some Characteristics of Computers of New Generation //In Proceedings of the Physics and Control Conference, Saint-Petersburg, 2003, vol. 3, pp. 804-807.

62. Goldenshluger A. V., Polyak В. T. Estimation of Regression Parameters with aArbitrary Noise // Mathematical Methods of Statistics, 1993, vol. 2, №. 1, pp. 18-29.http://domino.research.ibm.com/ comm/pr.nsf/pages/ rsc.quantum.htmlTOpen&printable

63. Kiefer J., Wolfowitz J. Statistical Estimation on the Maximum of a Regression Function // Ann. Math. Statist., 1952, vol. 23, pp. 462466.

64. Kushner H.J., Clark D.S. Stochastic Approximation Methods for Constrained and Unconstrained Systems. Berlin-Germany: Springer-Verlag, 1978, 259 p.

65. Maeda Y., Kanata Y. Learning Rules for Reccurent Neural Networks Using Perturbation and their Application to Neuro-control // Transactions of IEE of Japan, 1993, vol. 113-C, pp. 402-408.

66. Polyak B.T., Tsybakov A.B. On Stochastic Approximation with Arbitrary Noise (the KW Case) // In: Topics in Nonparametric Estimation, Khasminskii R.Z. ed., Advances in Soviet Mathematics, Amer. Math. Soc. Providence, 1992, No. 12, pp. 107-113.

67. Robbins H., Monro S. A Stochastic Approximation Method // Ann. Math. Statist., 1951, vol. 22, pp. 400-407.

68. Shor P. W. Quantum computing // Proc. 9-th Int. Math. Congress. Berlin. 1998. www.math.nine.edu/documenta/xvol-icm/Fields/Fields.html

69. Spall J.C. A Stochastic Approximation Technique for Generating Maximum Likelihood Parameter Estimates // In: Proceedings of the American Control Conference. 1987, pp. 1161-1167.

70. Spall J.C. Multivariate Stochastic Approximation Using a Simultaneous Perturbation Gradient Approximation // IEEE Transactions on Automatic Control, 1992, vol. 37, pp. 332-341.

71. Spall J.C. A One-Measurement Form of Simultaneous Perturbation Stochastic Approximation // Automatica, 1997, vol. 33, pp. 109-112.

72. Kleinman N. L., Spall J. C., Naiman D. Q. Simulation-Based Optimization with Stochastic Approximation Using Common Random Numbers // Management Science, 1999, vol. 45, № 11, pp. 1570-1578.

73. Tang Q-Y., Chen H.F., Han Z-J. Convergence rates of Perturbation-Analysis-Robbins-Monro-Single-Run algorithms for single server queues // IEEE Trans, on Automatic Control. 1997. Vol. 42, № 10. P. 1442-1447.

74. Villen-Altamirano J., Villen-Altamirano M. Restart: a method for accelerating rare event simulations North-Holland. 1991. P. 71-76.