Методы обучения с подкреплением для класса задач теории расписания
В работе был представлен способ построения расписания из связанных между собой задач, с учетом наличия нескольких исполнителей, с применением методов обучения с подкреплением. Были рассмотрены несколько различных существующих подходов к решению данной задачи, такие как методы теории расписаний, методы обучения с подкреплением. Практическая часть представляет собой построение модели, способной к приоритезации задач и выбором исполнителия, основанная на алгоритмах обучения с подкреплением и проведение численного эксперимента для оценки её эффективности и сравнения с уже известными алгоритмами теории расписаний.
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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.7 (82 отзыва)
4.8 (40 отзывов)
4.8 (17 отзывов)
4.6 (30 отзывов)
4.9 (298 отзывов)
4.7 (96 отзывов)
4.1 (20 отзывов)
4.6 (30 отзывов)
4.2 (25 отзывов)
