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

Проблема распределения связанных между собой задач между исполнителями присутствует во многих областях нашей жизни. В качестве примера можно рассмотреть две такие области: облачные вычисления и энергетика.
Потребность общества в вычислительных ресурсах растет из года в год весьма стремительно, а появление новых технологий только подстегивает взрывной рост. Как пример, рост популярности нейронных сетей привел к появлению запроса на высокопроизводительные вычисления с тензорами, что сильно увеличило спрос на видеокарты (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и наборе исполнителей Р.

Купить

Поставленная задача выполнена полностью. Были рассмотрены подходы к решению проблемы построения расписания на графах, на основе рассмотренных подходов сделан выбор в пользу методов обучения с подкреплением. Была реализована модель обучения с подкреплением, решающая задачу минимизации относительной длительности расписания на графах. Был выбран алгоритм для сравнения из классических эвристик для построения расписания на графах, сгенерированы данные для тестирования. Проведенное сравнение показало, что построенная в рамках работы модель превосходит классические эвристики. Модель, основанная на обучении с подкреплением выполняет свою задачу и обладает потенциалом к масштабированию.
Купить