Методы обучения с подкреплением для класса задач теории расписания

Введение 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) 2 E представляет собой отношение предшествования, задача не может начать своё выполнение, пока не были выполнены все предшествующие задачи.
Вершина без предшественников называется входной вершиной, без наследников - выходной. Если вершин без предшественников несколько, то все они становятся наследниками псевдо-входной вершины с нулевым весом как самой вершины, так и исходящих из неё рёбер. По аналогии, если выходных вершин несколько, то они все получат единого наследника с нулевым весом вершины и входящих в неё ребер. Данное требование не несет в себе практической цели для данной работы, но было введено с целью согласования с возможными требованиями алгоритмов для данного класса задач, по аналогии с работами
Введем понятие исполнителя - агента, который выполняет задачи. Пусть задано 3 типа исполнителя: small, medium, large.Каждый из исполнителей принадлежит к определенному типу, единственное их отличие будет заключаться в значении их мощности - параметра, характеризующего эффективность исполнителя при выполнении задачи. Пусть P = {Psmaii, Pmedium, Piargeg- множество параметров мощности. Пусть задано множество исполнителей M ={miP, ...,mkP g. Для исключения тривиальных решений будем полагать, что к < п.
Введем pred(vi), succ(vi) - множества непосредственных предшественников и наследников соответственно. Пусть comp(mjP) - множество выполненных исполнителем mjP*. - множество предшественников Vi , которые не были выполнены на машине mjp*. Это означает что, если предшественник задачи был выполнен на данной машине, то затраты на переключение с предшественника на текущую задачу не будет.
Введем понятие относительной длины расписания [5]:
makespan(solution)
Pv.2CPM,N minp.ep W„,
Знаменатель в SLRпредставляет собой нижнюю границу расписания, являясь минимумом вычислительных затрат задач, составляющего критический путь (наиболее длинный путь в смысле весов, т.е. “самый тяжелый” путь), и без учета веса ребер. В [5] показано, что это значение является нижней границей makespan,и, исходя из этого SLR > 1.
Целью работы является построение Reinforcement Learning модели, которая будет добиваться минимизация SLR при заданном графе Gи наборе исполнителей Р.

Купить