Методы обучения с подкреплением для класса задач теории расписания
В работе был представлен способ построения расписания из связанных между собой задач, с учетом наличия нескольких исполнителей, с применением методов обучения с подкреплением. Были рассмотрены несколько различных существующих подходов к решению данной задачи, такие как методы теории расписаний, методы обучения с подкреплением. Практическая часть представляет собой построение модели, способной к приоритезации задач и выбором исполнителия, основанная на алгоритмах обучения с подкреплением и проведение численного эксперимента для оценки её эффективности и сравнения с уже известными алгоритмами теории расписаний.
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Обзор литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Глава 1. Обучение с подкреплением . . . . . . . . . . . . . . . . 11
1.1. Мотивация . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2. Концепция . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.2.1 Марковский процесс принятия решений . . . . . . . . 15
1.2.2 Policy iteration и Value iteration . . . . . . . . . . . . . 20
1.2.3 Importance Sampling . . . . . . . . . . . . . . . . . . . 22
1.3. Temporal Difference Learning . . . . . . . . . . . . . . . . . 24
1.3.1 SARSA . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.3.2 Q-learning . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.4. Policy Gradient . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.4.1 REINFORCE . . . . . . . . . . . . . . . . . . . . . . . 29
1.4.2 Actor-Critic . . . . . . . . . . . . . . . . . . . . . . . . 30
1.5. DQN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.6. A3C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
Глава 2. Данные и распределенные вычисления . . . . . . . . 39
2.1. Генерация данных . . . . . . . . . . . . . . . . . . . . . . . 39
2.2. Алгоритм для сравнения . . . . . . . . . . . . . . . . . . . 41
2.3. Ray и RLlib . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
Глава 3. Реализация . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.1. Архитектура . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.2. Результаты . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . 52
Приложение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
Проблема распределения связанных между собой задач между ис-
полнителями присутствует во многих областях нашей жизни. В качестве
примера можно рассмотреть две такие области: облачные вычисления и
энергетика.
Потребность общества в вычислительных ресурсах растет из года в
год весьма стремительно, а появление новых технологий только подстеги-
вает взрывной рост. Как пример, рост популярности нейронных сетей при-
вел к появлению запроса на высокопроизводительные вычисления с тен-
зорами, что сильно увеличило спрос на видеокарты (GPU), которые ранее
использовались в основном в узкоспециализированных задачах (компью-
терная графика, симуляция физики). Нейронные сети внедряются повсе-
местно, что повлекло за собой внедрению специализированных вычисли-
тельных модулей в потребительской электронике, даже в мобильной тех-
нике.
Хоть рост вычислительной мощности индивидуальных устройств в
целом следует знаменитому закону Мура, приближение к физическим огра-
ничениям технического процесса производства процессоров и кремния как
материала, становится очевидно [1], что локальные вычисления далеко не
всегда смогут удовлетворять нужды пользователей.
Появление Apache Hadoop в 2006 году позволило популяризировать
распределенные вычисления, показав преимущества горизонтальной инте-
грации и параллельных вычислений. Сейчас рынок облачных (распреде-
ленных) вычислений оценивается в 760 миллиардов долларов, и только
продолжит расти [2].
При взаимодействии большого числа вычислительных узлов возни-
кает проблема управления: как оптимально распределять связанные меж-
ду собой вычислительные задачи? На эту проблему можно посмотреть с
различных точек зрения: оптимизация по числу единовременно задейство-
ванных ресурсов, энергоэффективности, длительности выполнения задачи,
затрачиваемым ресурсам, стоимости. Данную проблему в математике ре-
шает класс алгоритмов теории расписаний.
Алгоритмы теории расписаний долго применялись в данной области,
но развитие нейронных сетей и алгоритмов обучения с подкрепление поз-
волило превзойти классические эвристики [3].
Отдельно можно выделить проблему построения расписания на на-
правленных ациклических графах. Для некоторых вычислительных задач
уже заранее может быть известен набор подзадач, связи между ними и по-
следовательность их выполнения, представляющий собой вычислительных
граф. К таким задачам относится обучение нейронных сетей, декодирова-
ние генома.
Если же рассматривать энергетику, то рост так называемой зеленой
экономики способствует к всё более широкому использованию возобновля-
емых источников энергии. Два наиболее популярных – солнечная и ветря-
ная энергия имеют один существенный недостаток: непостоянство. Энер-
гия ветра, преобразуемая в электричество ветряными электрогенератора-
ми, может быть весьма непредсказуемой – в день с сильным ветром энергии
может быть переизбыток, в то время как в штиль энергии может не быть
совсем. Солнечная энергия же циклична, нам хорошо известен промежуток
времени, когда её возможно генерировать. Но здесь возникает известная в
энергетике проблема – что делать при резком скачке спроса на электри-
чество? Освещение и отопление в большей степени требуется ночью, когда
солнце уже не светит.
Хранение полученный из таких источников энергии может серьёзно
повысить их эффективность и привлекательность для потребителя, даже
на уровне отдельного домохозяйства [4]. Баланс между запасанием энергии
из нескольких непостоянных источников, продажей её обратно в электро-
сеть (популярно в Европе и США), и расходом сейчас может представлять
из себя комплексную оптимизационную задачу.
Как и в случае с распределенными вычислениями, мы можем оптими-
зировать по уровню использования, энергоэффективности, цене. Возника-
ет задача распределения нагрузки, получаемой из различных источников
между потребителями и устройствами хранения. Если же уровень потреб-
ления электроэнергии известен заранее или может быть достаточно точно
предсказан, можно выстроить граф подзадач потребления энергии и рас-
пределять каждую подзадачу на один из генераторов энергии.
Две приведенные выше области, на первый взгляд различные, имеют
один и тот же набор оптимизационных задач – распределение связанных
между собой задач между исполнителями. Для их решения возможно эф-
фективно применить Reinforcement Learning, который превосходит клас-
сические алгоритмы теории расписаний, что и будет показано в данной
работе.
Постановка задачи
Пусть задан направленный ациклических граф G = (V, E), где V =
v1 , …, vn – множество вершин графа, представляющих собой задачи, E –
множество ребер графа. Все вершины и ребра имеют веса: вес вершины Wvi
представляет собой трудозатраты на исполнение задачи, вес ребра Wi,j в
свою очередь представляет собой трудозатраты исполнителя при переклю-
чении на новую задачу. Каждое ребро (i, j) ∈ E представляет собой отно-
шение предшествования, задача не может начать своё выполнение, пока не
были выполнены все предшествующие задачи.
Вершина без предшественников называется входной вершиной, без
наследников – выходной. Если вершин без предшественников несколько,
то все они становятся наследниками псевдо-входной вершины с нулевым
весом как самой вершины, так и исходящих из неё рёбер. По аналогии,
если выходных вершин несколько, то они все получат единого наследника
с нулевым весом вершины и входящих в неё ребер. Данное требование не
несет в себе практической цели для данной работы, но было введено с
целью согласования с возможными требованиями алгоритмов для данного
класса задач, по аналогии с работами
Введем понятие исполнителя – агента, который выполняет задачи.
Пусть задано 3 типа исполнителя: small, medium, large. Каждый из ис-
полнителей принадлежит к определенному типу, единственное их отли-
чие будет заключаться в значении их мощности – параметра, характе-
ризующего эффективность исполнителя при выполнении задачи. Пусть
P = {Psmall , Pmedium , Plarge } – множество параметров мощности. Пусть за-
дано множество исполнителей M = {m1P∗ , …, mkP∗ }. Для исключения три-
виальных решений будем полагать, что k < n.
Введем pred(vi ), succ(vi ) - множества непосредственных предшествен-
ников и наследников соответственно. Пусть comp(mjP∗ ) - множество выпол-
ненных исполнителем mjP∗ . Тогда длительность выполнения задачи vi на
mjP∗ будет вычисляться как
Поставленная задача выполнена полностью. Были рассмотрены под-
ходы к решению проблемы построения расписания на графах, на основе
рассмотренных подходов сделан выбор в пользу методов обучения с под-
креплением. Была реализована модель обучения с подкреплением, решаю-
щая задачу минимизации относительной длительности расписания на гра-
фах. Был выбран алгоритм для сравнения из классических эвристик для
построения расписания на графах, сгенерированы данные для тестирова-
ния. Проведенное сравнение показало, что построенная в рамках работы
модель превосходит классические эвристики. Модель, основанная на обу-
чении с подкреплением выполняет свою задачу и обладает потенциалом к
масштабированию.
Хочешь уникальную работу?
Больше 3 000 экспертов уже готовы начать работу над твоим проектом!
4.8 (2878 отзывов)
4.5 (330 отзывов)
4.6 (92 отзыва)
4.6 (71 отзыв)
4.9 (20 отзывов)
5 (22 отзыва)
4.2 (6 отзывов)
4.9 (66 отзывов)
4.8 (13 отзывов)
