Скачать презентацию
Идет загрузка презентации. Пожалуйста, подождите
Презентация была опубликована 10 лет назад пользователемТамара Ерохина
1 А ДАПТИВНАЯ ОПТИМИЗАЦИЯ СЕРВЕРА, ОБРАБАТЫВАЮЩЕГО ОЧЕРЕДЬ ЗАДАНИЙ Дипломная работа студента 545 группы Ле Чунг Хьеу Научный руководитель : О. Н. Граничин Рецедент : А. С. Лопатин Санкт – Петербург 2007
2 В ВЕДЕНИЕ Проблема эффективного обслуживания сервером очереди заданий. Рандомизированный алгоритм стохастической аппроксимации. Обучение с подкреплением.
3 П ОСТАНОВКА ЗАДАЧИ Рассмотрим задачу повышения эффктивности сервера: L(x) – среднее время ожидания клиентами. q(x) – стоимость исползования параметра x. y(x) – время, которое задание ожидало в сервере до момента своего завершения. Требуется найти параметра θ : f(x) min по x ( Θ )
4 П ОСТАНОВКА ЗАДАЧИ Эту задачу оптимизации не решить традиционными средствами. 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.
5 О БУЧЕНИЕ С ПОДКРЕПЛЕНИЕМ o Обучение с подкреплением, представляет класс задач, в которых агент, действуя в определенной среде, должен найти оптимальную стратегию взаимодействия с ней. Цель агента – максимизировать суммарную награду.
6 О БУЧЕНИЕ С ПОДКРЕПЛЕНИЕМ Оценочная Функция : RL алгоритмы основано на оценке оценочной функцией. Оценка Стратегии. Усовершенствование Стратегии. Повторение Стратегии.
7 Р АНДОМИЗИРОВАННЫЕ АЛГОРИТМЫ СТОХАСТИЧЕСКОЙ АППРОКСИМАЦИИ Пусть - дифференцируемая по второму аргументу. Наблюдении. Требуется по наблюдениям : y 1, y 2,... построить последовательность оценок {θ n } вектора θ :
8 SPSA ДЛЯ РЕШЕНИЯ ЗАДАЧИ О СЕРВЕРЕ 1. Положим k = 0 и выберем некоторое начальное значение оценки θ В начале каждого k-го такта вычисляем 3. Запускаем сервер с значением параметра x = θ k. 4. После завершения k-го такта подсчитаем новую оценку по правилу 5. Увеличиваем номер такта k = k Переход к п.2 (повтор действий заново).
9 М ОДЕЛИРОВАНИЕ Интерфейс программы :
10 Р ЕЗУЛЬТАТЫ Результаты программы с фиксированным значением
11 Р ЕЗУЛЬТАТЫ Минимум функции = 51 достигается при значении θ = 0.84.
12 Р ЕЗУЛЬТАТЫ ПРОГРАММЫ С АЛГОРИТМОМ SPSA θ = θ = 1.
13 Р ЕЗУЛЬТАТЫ ПРОГРАММЫ С АЛГОРИТМОМ М ОНТЕ К АРЛО
14 З АКЛЮЧЕНИЕ Работа с алгоритмом SPSA. Работа с методом Монте Карло.
Еще похожие презентации в нашем архиве:
© 2024 MyShared Inc.
All rights reserved.