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

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

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

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

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

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

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

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

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

АВТОРЕФЕРАТ

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

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

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

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

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

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

Ведущая организация: Санкт-Петербургский институт информатики и автоматизации РАН

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

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

Автореферат разослан “ ” 2005 г.

Ученый секретарь диссертационного совета доктор физико-математических наук Б. К. Мартыненко

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

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

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

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

Ранее в 1951 году вышла статья Роббинса и Монро (Ann. Math.

Statist., vol. 22), в которой решалась задача поиска корня функции, измеряемой с помехами, на которые накладывались точно такие же ограничения. Роббинс и Монро воспользовались модификацией градиентного метода и отказались от усреднения на каждом шаге, предложив алгоритм xn+1 = xn n yn.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где {wn } неконтролируемая последовательность случайных величин (wn Rp ), имеющих одинаковое, вообще говоря, неизвестное распределение Pw (·) с конечным носителем.

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

Далее мы будем использовать обозначения · и ·, · для евклидовой нормы и скалярного произведения в 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), сходится к точке в следующем смысле:

3). Если zn z > 1 n, то E{V (n )} (E{V (0 )}+ µ0 ) n1 (1i ).

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

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

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

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

Начинается третья глава с рассмотрения задачи балансировки загрузки. Рассмотрим систему, состоящую из двух серверов, способных параллельно обрабатывать 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 рассмотрен многомерный вариант задачи.

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

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

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

Последней в третей главе в разделе 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] 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.

Подписано в печать 15.09.2005 г. Формат бумаги 60Х90 1/16. Бумага офсетная.

Печать ризографическая. Объем 1 усл. п. л. Тираж 100 экз. Заказ N 737.

Отпечатано в ПК “МИКРОМАТИКС” c оригинал-макета заказчика.

199178, Санкт-Петербург, Большой пр. В.О., д. 55.