1 of 22

ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ СИСТЕМОЙ МАССОВОГО ОБСЛУЖИВАНИЯ С ПОМОЩЬЮ ОБУЧЕНИЯ С ПОДКРЕПЛЕНИЕМ

Выполнил аспирант

ФФ МГУ:

Лаптин В. А.

Научный руководитель:

Профессор, д. т. н.

Мандель А.С.

«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.В.ЛОМОНОСОВА»

Физический факультет

Кафедра физико-математических методов управления

2 of 22

УПРАВЛЯЕМАЯ СМО

Блок-схема управляемой СМО

3 of 22

ФОРМАЛИЗАЦИЯ ЗАДАЧИ

4 of 22

ВХОДЯЩИЙ ПОТОК

5 of 22

ОДНОШАГОВЫЕ ЗАТРАТЫ

6 of 22

ФУНКЦИОНАЛЫ ЗАТРАТ

7 of 22

ОБЩИЙ ФУНКЦИОНАЛ (2 ТИПА)

8 of 22

УРАВНЕНИЕ ДИСКРЕТНОГО ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

9 of 22

МАРКОВСКИЙ ПРОЦЕСС ПРИНЯТИЯ РЕШЕНИЙ

10 of 22

ОСОБЕННОСТИ ПОСТАНОВКИ ЗАДАЧИ

11 of 22

ПАРАМЕТРЫ ЗАДАЧИ

Обозначение	Значение	Определение
	1	Стоимость эксплуатации одного устройства
	0.2	Стоимость отключения одного рабочего устройства обслуживания
µ	6	Интенсивность обслуживания для одного устройства
	1	Стоимость принятия решения о включении/отключении
		Интенсивность входящего потока для каждого состояния (1-й, 2-й соответственно)
		Матрица переходных вероятностей однородной марковской цепи
	1	Расходы на содержание очереди
	10	Максимально допустимое число каналов обслуживания

12 of 22

МЕТОД ИТЕРАЦИЙ ЗНАЧЕНИЙ

13 of 22

МЕТОД ИТЕРАЦИЙ ЗНАЧЕНИЙ – СРАВНЕНИЕ

Интенсивность	Число каналов (m)	Мат. ожидание	Итерация значений, mean	Итерация значений, std
20	4	72.54	72.52	0.41
20	5	71.54	71.58	0.42
20	6	72.74	72.76	0.44
20	7	72.94	72.95	0.41
20	8	73.14	73.23	0.43
20	9	73.34	73.41	0.37
20	10	73.54	73.58	0.46
40	4	80.45	80.49	0.36
40	5	80.45	80.42	0.40
40	6	80.45	80.42	0.40
40	7	80.45	80.41	0.43
40	8	80.45	80.43	0.37
40	9	79.45	79.48	0.37
40	10	80.65	80.64	0.46

14 of 22

Q-ОБУЧЕНИЕ

15 of 22

ПОЛИТИКИ Q-ОБУЧЕНИЯ

16 of 22

СРАВНЕНИЕ СХОДИМОСТИ Q-ОБУЧЕНИЯ

17 of 22

СРАВНЕНИЕ КАЧЕСТВА Q-ОБУЧЕНИЯ

	Число каналов (m)	Мат. ожидание	Q-обучение	Exp. val. SARSA	Softmin SARSA
20	4	72.54	75.09 ± 2.73	74.28 ± 2.31	76.51 ± 3.86
20	5	71.54	74.7 ± 5.59	74.12 ± 3.38	74.87 ± 3.98
20	6	72.74	73.86 ± 1.38	74.31 ± 2.79	75.46 ± 3.55
20	7	72.94	75.92 ± 2.26	75.32 ± 3.61	75.55 ± 3.29
20	8	73.14	75.49 ± 2.46	75.16 ± 2.37	76.55 ± 3.88
20	9	73.34	75.4 ± 5.12	75.41 ± 3.35	76.49 ± 4.88
20	10	73.54	75.78 ± 3.03	75.16 ± 1.76	75.06 ± 2.46
40	4	80.45	82.05 ± 2.16	81.93 ± 2.81	82.06 ± 2.4
40	5	80.45	81.97 ± 2.44	81.48 ± 2.47	82.0 ± 2.21
40	6	80.45	82.79 ± 2.74	81.76 ± 1.84	83.66 ± 4.29
40	7	80.45	83.52 ± 4.27	81.74 ± 1.72	82.73 ± 2.88
40	8	80.45	82.28 ± 3.17	81.78 ± 1.79	84.37 ± 4.23
40	9	79.45	80.93 ± 1.9	80.87 ± 3.04	80.75 ± 2.35
40	10	80.65	82.2 ± 2.02	82.56 ± 3.62	83.47 ± 3.79

18 of 22

EXPERIENCE REPLAY

19 of 22

EXPERIENCE REPLAY

20 of 22

СТАТИСТИЧЕСКАЯ ОЦЕНКА МАТРИЦЫ МАРКОВА

	Число каналов (m)	Мат. ожидание	10 итераций	20 итераций	50 итераций
20	4	72.54	72,21	72,75	71,98
20	5	71.54	71,85	71,46	71,93
20	6	72.74	73,36	72,85	73,11
20	7	72.94	73,54	73,08	72,78
20	8	73.14	73,22	72,81	73,34
20	9	73.34	73,30	74,17	73,50
20	10	73.54	73,45	73,39	72,91
40	4	80.45	80,48	80,30	80,32
40	5	80.45	80,74	80,21	80,31
40	6	80.45	80,42	80,51	80,53
40	7	80.45	80,76	80,76	80,33
40	8	80.45	80,47	80,75	80,30
40	9	79.45	79,58	79,22	79,56
40	10	80.65	80,95	80,32	80,44

Число итераций	Оценка матрицы вероятностей
10	[[0.76 0.24] [0.46 0.54]]
20	[[0.79 0.21] [0.39 0.61]]
50	[[0.8 0.2 ] [0.41 0.59]]
100	[[0.79 0.21] [0.41 0.59]]

21 of 22

СИСТЕМЫ БОЛЬШИХ РАЗМЕРНОСТЕЙ

Все вышесказанное также справедливо и для систем большей размерности (5 состояний):

Метод итерации значений также дает отличное управление.
Q-обучению требуется порядка 2.5-3 тыс. итераций для сходимости.
При статистической оценки матрицы хватает 50-100 итераций для качественной оценки матрицы.

22 of 22

ВЫВОДЫ

В случае известной матрицы переходов алгоритм итерации значений показал хорошие результаты, соотносящиеся с значениями математического ожидания при оптимальной политике.
При отсутствии данных о модели среды алгоритмы на основе Q-обучения также способны дать около оптимальную политику управления. Но агенты на основе таких алгоритмов обладают 2-мя недостатками: нестабильность качества обучения и большое время сходимости.
Использование буфера ранее наблюдавшихся состояний для повторного обучения помогает в несколько раз ускорить обучение агента, однако еще более усложняется процесс подбора параметров.
Статистическая оценка матрицы для алгоритма итерации значений показала более лучшие качество и время сходимости, чем Q-обучение.