А ДАПТИВНАЯ ОПТИМИЗАЦИЯ СЕРВЕРА, ОБРАБАТЫВАЮЩЕГО ОЧЕРЕДЬ ЗАДАНИЙ Дипломная работа студента 545 группы Ле Чунг Хьеу Научный руководитель : О. Н. Граничин Рецедент : А. С. Лопатин Санкт – Петербург 2007

В ВЕДЕНИЕ Проблема эффективного обслуживания сервером очереди заданий. Рандомизированный алгоритм стохастической аппроксимации. Обучение с подкреплением.

П ОСТАНОВКА ЗАДАЧИ Рассмотрим задачу повышения эффктивности сервера: L(x) – среднее время ожидания клиентами. q(x) – стоимость исползования параметра x. y(x) – время, которое задание ожидало в сервере до момента своего завершения. Требуется найти параметра θ : f(x) min по x ( Θ )

П ОСТАНОВКА ЗАДАЧИ Эту задачу оптимизации не решить традиционными средствами. F(x,ω) – эмпирическая функция. f(x) = E{F(x,ω)}. F t (x,ω) – случайная функция дескретного времени t = 1, 2,... f t (x) = E ω {F t (x,ω)}. θ t = argmin x f t (x). Требуется по наблюдениям F t (x,ω) {θ n } |θ n - θ t | min.

О БУЧЕНИЕ С ПОДКРЕПЛЕНИЕМ o Обучение с подкреплением, представляет класс задач, в которых агент, действуя в определенной среде, должен найти оптимальную стратегию взаимодействия с ней. Цель агента – максимизировать суммарную награду.

О БУЧЕНИЕ С ПОДКРЕПЛЕНИЕМ Оценочная Функция : RL алгоритмы основано на оценке оценочной функцией. Оценка Стратегии. Усовершенствование Стратегии. Повторение Стратегии.

Р АНДОМИЗИРОВАННЫЕ АЛГОРИТМЫ СТОХАСТИЧЕСКОЙ АППРОКСИМАЦИИ Пусть - дифференцируемая по второму аргументу. Наблюдении. Требуется по наблюдениям : y 1, y 2,... построить последовательность оценок {θ n } вектора θ :

SPSA ДЛЯ РЕШЕНИЯ ЗАДАЧИ О СЕРВЕРЕ 1. Положим k = 0 и выберем некоторое начальное значение оценки θ В начале каждого k-го такта вычисляем 3. Запускаем сервер с значением параметра x = θ k. 4. После завершения k-го такта подсчитаем новую оценку по правилу 5. Увеличиваем номер такта k = k Переход к п.2 (повтор действий заново).

М ОДЕЛИРОВАНИЕ Интерфейс программы :

Р ЕЗУЛЬТАТЫ Результаты программы с фиксированным значением

Р ЕЗУЛЬТАТЫ Минимум функции = 51 достигается при значении θ = 0.84.

Р ЕЗУЛЬТАТЫ ПРОГРАММЫ С АЛГОРИТМОМ SPSA θ = θ = 1.

Р ЕЗУЛЬТАТЫ ПРОГРАММЫ С АЛГОРИТМОМ М ОНТЕ К АРЛО

З АКЛЮЧЕНИЕ Работа с алгоритмом SPSA. Работа с методом Монте Карло.