Применение методов машинного обучения в стохастических системах управления запасами

УДК 519.62 А.А. ГРИШКО

ПРИМЕНЕНИЕ МЕТОДОВ МАШИННОГО ОБУЧЕНИЯ В СТОХАСТИЧЕСКИХ СИСТЕМАХ УПРАВЛЕНИЯ ЗАПАСАМИ

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

1. Введение

Регулирование уровня запасов в сложных технологических комплексах зачастую определяет динамику их структуры (при этом состояние определяется уровнем запасов), а неопределенность данных (запросы, поступления, стоимость, наличие средств производства) делает структуру стохастичной. Оптимальное управление такой системой требует разработки стратегии использования запасов, позволяющей минимизировать математическое ожидание стоимости (или максимизировать математическое ожидание выигрыша) на некоторой совокупности стратегий. Таким образом, речь идет о том, чтобы знать, в какой пропорции надо использовать запасы для удовлетворения запросов и в какой степени желательно консервировать эти запасы для последующего времени [1].

Классическое решение для оптимизации выбора стратегии по сепарабельному критерию (т. е. когда стратегия может строиться шаг за шагом во времени и изменяться) может основываться на динамическом программировании (в частности, математическое ожидание является сепарабельным). К сожалению, в большинстве случаев оптимизация математического ожидания чересчур рискованная. Таким образом, целесообразно: выбрать критерий оптимизации, отличный от математического ожидания и обеспечивающий робаст-ные решения; обеспечить возможность оптимизации такого критерия, даже если он не совместим с классической техникой динамического программирования. К классическим статистическим характеристикам случайной переменной величины С, представляющим интерес для рассматриваемой задачи, кроме математического ожидания E(C) и дисперсии var(C) = E(C - E(C))' следует отнести распространенные в системах управления рисками характеристик Risk-At-Value (Я^) и Value-At-Risk (VaR ). означает (для некоторого порога затрат С') вероятность того, что С > С', а VaR для заданного порога риска соответствует минимальному С', для которого Р(С > С') < г. Представления типа RaV и VaR являются наиболее полными в смысле отображения всего распределения затрат. Стохастическое динамическое программирование служит принципом классической декомпозиции для динамической оптимизации. Оно используется для оптимизации по всем сепарабельным критериям. В частности, одним из таких критериев является математическое ожидание. Однако, если принимать во внимание оценки риска VaR , то возникает проблема несепарабельности, при которой нельзя применить стандартное стохастическое динамическое программирование. Эта статья посвящена применению техники обучения с подкреплением, совместимой с несепарабельным критерием [2]. На примере обучения с подкреплением целесообразно определить стратегию, оптимизирующую компромисс «математическое ожидание/риск» несепарабельного типа (1 - а)Е + а'УзЯ .

Целью данной работы является решение задачи определения стратегии управления запасами в стохастических системах с применением методов машинного обучения с подкреплением и динамического программирования.

2. Общая схема управления запасами с применением стохастической

оптимизации

Общая схема стохастической динамической оптимизации и схема ее применения для управления запасами приведены на рис.1 (в левом и правом фрагментах соответственно). В самом общем ракурсе проблема стохастической динамической оптимизации может быть проиллюстрирована эволюционирующей во времени системой, которая характеризуется некоторым внутренним состоянием и пытается оптимизировать свою траекторию по заданному критерию.

Для описания такой проблемы используются:

- стохастический процесс р(1) (здесь рассмотрим дискретное время от 0 до Т): р(0),...,р(Т);

- уравнение эволюции системы: хг+1 = , и(р(1), 1, хг),р(1)) и стратегия (регулятор) и(-, •, •), которая пытается на нее повлиять так, чтобы минимизировать математическое ожидание С1(хьи1) + С2(х2,и2) +... + Ст(хт,ит) (и означает и(р(1)Д,хг)).

Таким образом, можно сказать, что и() является регулятором, минимизирующим математическое ожидание суммарных затрат.

Рис. 1. Общая схема стохастической динамической оптимизации для управления запасами

В основе принципа декомпозиции Беллмана лежит способ определения V(p(t),t,xt) и, соответственно, математического ожидания ct(xt,ut) + ct+i(xt+i,ut+i) +... + cT(xT,uT) с заданными p(t) и x(t) для нахождения оптимальной стратегии u(); т.е. определение такого V, чтобы для оптимального u выполнялось следующее равенство:

V

где xt = x и xt+i = f(xt,u(p(t),t,xt),p(t)).

Уравнение (1) определяет V как функцию величины, зависящей от стратегии u . Можно показать, что каждой оптимальной стратегии u() соответствует своя величина V(). Таким образом, достаточно определить для решения задачи в каждый момент времени u(p(t), t,xt) е arg minu ct (xt ,u) + V(p(t + 1),t +1, xt+i). Функция V(-, •, •) называется функцией Бел-лмана или функцией валоризации, или же, с позиций обучения с подкреплением, критической функцией или функцией стоимости. Здесь мы будем рассматривать V(-,-,-) с одной стороны как математическое ожидание, а с другой - как компромисс вида (1 - a)E + aVaR, позволяющий решать задачу оптимизации не только по матожиданию затрат, но и по риску.

Такая задача является актуальной для всех систем управления запасами, независимо от их технологического назначения. В частности, в работе [2] рассматривается управление гидравлическими запасами при использовании различных типов электростанций для удовлетворения стохастических запросов на поставку электроэнергии. При этом необходимо знать в каждый конкретный момент времени (в функции предварительно определенной модели и для текущих уровней запасов), какая часть запросов должна быть удовлетворена с помощью тепловых электростанций (ТЭЦ), а какая часть - с помощью гидроэлектрических станций (ГЭС).

Формально стохастический процесс соответствует заявкам на электроэнергию d(t); продукция ТЭЦ pc (t) выбирается в соответствии с принимаемой стратегией (из диапазона pmin (t) - pmax (t), определяемого эксплуатационными ограничениями теплоцентрали); продукция ГЭС ph (t) выбирается в соответствии с принимаемой стратегией (из диапазона 0-

pmax). уравнение эволюции запасов имеет следующий вид: stock(t +1) = stock(t) + a(t) - ph (t) - dev(t), где a(t) - приток воды. Стратегия должна удовлетворять следующим ограничениям: pc (t) + ph (t) = d(t), stock(t) > 0 и stock(t) < stockmax (t). Функция стоимости с определяется суммой c(t,pc(t)), где c(t, •) - функция стоимости, зависящая от t (возрастающая и выпуклая), а c(stock(t)) - функция штрафа за конечные запасы (убывающая). Стоимости ct(xt,ut) равны c(t,pc(t)) для t < T и c(stock(T)) для t = T. Состояние определяется парой (di(t),stock(t)) (т.е. внутренним состоянием stock(t) и состоянием стохастического процесса di (t) ). Стратегия u() определяет pc(t) и p^(t). Динамическое программирование, используемое для поиска стратегии, работает для внутреннего состояния xt и стохастического процесса di(t) (a(t) - детерминированная составляющая).

Рассмотрим возможность применения методов обучения с подкреплением для решения рассматриваемой задачи. Основная идея таких методов состоит в следующем: формируются модуль-актер и/или начальный модуль-критик; реализуется симуляция текущих действий модуля-актера; если используется текущий модуль-критик (алгоритмически участвующий в симуляции), модифицируются решения актера в целях оптимизации заданной функции; производится возврат к этапу симуляции.

В методах обучения с подкреплением (Q-обучение, алгоритм TD(X) ), в настоящее время широко используемых для оптимизации матожиданий, начинают применять понятия риска. В настоящей статье предлагается рассмотреть использование компромиссного критерия «матожидание»/« VaR ».

Сравнивая методы обучения с подкреплением с методами классического динамического программирования, можно отметить следующее:

- классические процедуры стохастической оптимизации на основе динамического программирования обладают свойствами робастности; они реализуются с помощью алгоритмов, время вычисления для которых может быть определено заранее, а результаты вычислений являются достаточно устойчивыми;

- обучение с подкреплением хорошо подходит для работы с предысторией и, в частности, не требует структурного определения стохастического процесса, тогда как методы, основанные на стохастической оптимизации цепной предыстории с помощью динамического программирования, предполагают наличие модели;

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

- методы с подкреплением более приспособлены для работы с недискретизированными данными или с большим числом переменных состояния, когда они связаны с методами экстраполяции. Следует отметить, что объединение динамического программирования и методов, использующих экстраполяцию, все-таки менее удобно, чем обучение с подкреплением.

3. Комбинированные алгоритмы

Рассмотрим вопросы выбора схемы и алгоритмов оценивания эффективности стратегий принятия решений в системах управления запасами с использованием комбинированного критерия.

Алгоритм TD(X) был уже успешно проверен на практике для решения широкого круга задач; если требуется симуляция, то он хорошо сочетается с комплексными ограничениями с малыми затратами на программирование и время вычислений. Алгоритм TD(X) основан на использовании функции оценивания (аналога оценок Беллмана) для симуляций.

В частности, он может базироваться на симуляции различных форм величины X (параметра, принимающего значения в диапазоне [0,1]). Мы используем алгоритм ТБ(1), который позволяет удобное введение понятия риска. В отличие от других алгоритмов ТБ(Х) он формирует реальное распределение будущих стоимостей, соответствующих рассматриваемым состояниям, а не будущих стоимостей, полученных по функции оценивания; оценива -ние « УаЯ » является, таким образом, прямым. Предлагаемая идея состоит в аппроксимации У(-, 1, •) с помощью регистрируемых стоимостей сг (хг) + сг+1 (хг+1) +... + Ст (хт). Используемая при этом стратегия является «неоптимистической», т. е. базирующейся на медленных процедурах (точнее, последовательно осуществляется некоторое количество симуляций перед началом использования функции оценивания). Такой метод является робастным по отношению к сходимости выбираемых стратегий, так как функция оценивания может сходиться без обязательной сходимости стратегии.

Введение понятия риска можно осуществить посредством использования представления типа « УаЯ ». Модуль, позволяющий экстраполировать « УаЯ » для непрерывных уровней запасов на основе конечного числа примеров, предполагает необходимость введения ограничений на функции оценивания, что приводит к задаче выпуклой квадратичной оптимизации с линейными ограничениями. Структура реализации предлагаемого подхода приведена на рис. 2.

Рис. 2. Комбинированная схема формирования функции оценивания Стохастическое динамическое программирование реализует первую функцию оценивания в случае без «УаЯ » и с немного упрощенным стохастическим процессом, чтобы реализовать первую функцию оценивания (т.е. начальный пункт итераций обучения с подкреплением). Комбинирование обучения с подкреплением и динамического программирования позволяет использовать гарантированную устойчивость динамического программирования и возможность методов обучения с подкреплением трансформировать оптимальное управление по матожиданию в стратегию, использующую понятие риска (после обучения с подкреплением во время фазы симуляции). Модуль экстраполяции реализует здесь экстраполяцию выпуклыми функциями, без критериев регуляризации (т.е. без штрафа на вторую производную или других штрафов этого типа). Динамическое программирование является реализуемым только для предварительных расчетов, не принимающих во внимание понятие риска; будучи теоретически факультативным, оно тем не менее обеспечивает прочную базу для операций пересчета, компенсируя, как правило, трудности параметризации обучения с подкреплением. Модуль «Критик», располагающий полной траекторией, позволяет учитывать более понятия ЯаУ и УаЯ . Можно рассмотреть, например, случайную переменную С, ассоциируемую со стоимостью управления; оптимизацию С1 = (1 -а)Е(С) + аР(С>К), где Е - символ матожидания, а Р - вероятность, т.е.

учет ЯаУ; или оптимизация С2 = (1 - а)Е(С) + аК, где значения К такие что Р(С > К) = 1 - п, т.е. учет УаЯ . В случае ЯаУ, строго говоря, надо было бы для оптимизации, например, риска превышения стоимости управления величины к , использовать функции, основанные не только на состоянии и времени, но также и на предыдущей стоимости управления. В случае УаЯ это не является необходимым: критерий С2 изменяет в функции предыдущей стоимости только одну константу и, соответственно, предыдущая стоимость не влияет на модуль «Актер».

Фиксированными являются следующие параметры: частота принятия решений (количество симуляций между каждым У() и п; в соответствии с общепринятой терминологией это «степень оптимизма» метода); шаг спуска и его эволюция во времени; порог доверия применительно к понятию риска (обычно 5%); параметр компромисса между матожидани-ем и УаЯ .

Модуль «Критик» должен иметь возможность осуществлять представления в виде ломаной кривой функции оценивания У(р, 1, х) для заданного актера. Такая линия позволяет реализовать оптимизацию для выбора решения, соответствующую квадратичной выпуклой оптимизации с линейными ограничениями. В нашем случае р - это величина, характеризующая стохастический процесс (заявка), 1 - дата, х - уровень запасов. Таким образом, для каждого этапа п = 1,2,3,... необходимо произвести следующие действия:

- провести симуляции (процедура симуляции и особенно дискретизации будет подробнее приведена далее);

- получить «примеры» (р, 1, х, с), где 1 - дата, р - состояние стохастического процесса, х - уровень запасов, С - стоимость (по результатам проведенной симуляции);

- аппроксимировать матожидание будущей стоимости ломаными линиями (для шага времени и для состояния процесса: ломаная линия соединяет таким образом пары (уровень запасов, средняя будущая стоимость));

- аппроксимировать УаЯ ломаными линиями (для шага времени и для состояния процесса: ломаная линия соединяет таким образом пары (уровень запасов, квантиль стоимости)) и определить итоговые величины, комбинируя УаЯ и матожидание.

Обе аппроксимации (УаЯ и матожидание) получаются итеративным путем: на каждой итерации определяются симуляции УаЯ и матожидания для полученной стратегии управления; затем стратегия управления адаптируется для полученной функции оценивания. Пусть УпЕ и уУ - функции оценивания УаЯ и матожидания соответственно, которые были получены на п -м этапе (в виде ломаных линий). На основании уЕ и уУ строятся уЕ+1 и

уу

Уп+1-

Пусть УпЕ+1(р,1, с) и УУ+1(р,1, •, с) - кусочно-линейные функции (с фиксированными точками изломов С81), которые минимизируют (с указанными ниже ограничениями) сумму термов Т1,Т2,Т3,Т4:

Т1 = а 2

(терм вызова квадроплета (р, 1, х, с), используемый в симуляции с применением матожидания);

т"!^ __/•^т'Е / + \ т'Е / + \\2

Т2 = а2 2 (УПЧрЛс^)-У^рЛс^))2

(рД^О

(терм вызова симуляции с предыдущего матожидания);

Т3 =аз 2

(рД,аЬ§рс) '

(терм вызова оцениваемого УаЯ , где величины absj - аппроксимации УаЯ , полученные по данным (р,1, х,с));

Т4 = а4 2

(терм вызова предыдущей функции УаЯ ).

Таким образом можно найти функцию, «не слишком отличную» от предыдущей функции и «не слишком далекую» от результатов симуляции. При этом принимаются во внимание следующие ограничения: V1E+1(p,t, •) и V1V+1(p,t, •) - убывающие выпуклые функции; неравенство v^+j > vE+i в каждой точке (это, строго говоря, не гарантируется, но вероятность этого высока); задача не очень сложна и использование «пар» не является, следовательно, проблематичным; Vn+j получают в виде линейной комбинации vE+j и vV+j.

Выбор параметров aj,a2,аз,а4 производится следующим образом: aj и аз равны 1, деленной на число термов в И и T3 соответственно; a 2 и a 4 равны числу игр в N уже прошедших симуляциях для рассматриваемого шага времени, деленному на число термов в T2 и T4 соответственно. Такой выбор аналогичен технике градиентного спуска; тем не менее следует понимать, что актер эволюционирует после каждого действия критика, а алгоритм градиентного спуска является разновидностью алгоритма с фиксированной точкой.

В базовом варианте предлагаемый алгоритм определяется такой последовательностью действий:

L Определение первой функции оценивания с помощью динамического программирования.

2. Симуляции с помощью стратегии оптимизации, основанной на функции оценивания (т. е. во время симуляций получается решение, которое оптимизирует предсказанную стоимость с помощью функции оценивания).

3. Определение новой функции оценивания, которая соединяется аппроксимативно по результатам симуляции.

4. Переход к 2, в случае исчерпания лимита времени.

Формализация алгоритма зависит от параметров ! < DR (DR - размер сигнала подкрепления), j < Д < DR и 0 < r < Ь где r - уровень рассматриваемого риска:

Опишем подробнее этапы алгоритма.

Для всех T (от начального T, равного !) с шагом, равным Д, выполнить следующие действия: симулировать N траекторий с заданным шагом, начиная с T : начальные уровни запасов для этих траекторий, начиная с T , распределяются не поровну, так как маленькие уровни запасов являются более критичными. Пусть L = (p¡,stock¡,pdt¡,c¡) - перечень квад-роплетов (уровень заявок, начальный запас, шаг времени, стоимость (по результатом симуляции между шагом времени pdt и шагом времени T )), полученных в результате симуляции; L содержит N х DR пар, так как каждая симуляция позволяет получить будущую стоимость для каждого значения pdt между началом (N0) и (N0 + DR - !).

Для всех k между 0 и DR - j и всех состояний p стохастического процесса между 0 и (DR - j) в момент (k + N0) выполнить следующие действия: сформировать список L' из таких элементов l , для которых p¡ = p и pdt¡ = debut + k . Пусть VaR j соответствует квантилю j - r из c¡ для stock¡ в интервале [aj,aj+j] среди элементов одного подмножества (abSj,VaRj) для рассматриваемых значений k и p. Поместить каждый (abSj,VaRj) в

определенный терм T3 . Сформировать термы Tj T2, T4. Оптимизировать T! + T2 + T3 + T4 для получения новой функции оценивания. Симулировать большое число траекторий и вычислить полученные индикаторы риска (матожидание, кривая VaR ).

4. Анализ сходимости комбинированного алгоритма

Покажем, что функция стоимости для достаточно большого N стремится к функции оценивания оптимальной стратегии, полученной по рассмотренному методу, для нормы L2 . Для этапа алгоритма, соответствующего debut = T - j, сходимость соответствующей рекуррентной процедуры является очевидной. Рассмотрим гипотезу такой сходимости для этапа debut +! (с точностью е). Проблема оптимизации с ограничениями по T! (ограничения по T3 и T4 можно не рассматривать, поскольку они имеют отношение лишь к минимизации математического ожидания, а влияние T2 является слабым для большого

числа симуляций) сводится к асимптотическому приближению функции оценивания F к кусочно-линейной функции, соответствующей оптимальной стратегии.

Если шаг дискретизации пространства поиска выбрать в соответствии с рекомендациями, приведенными в [2], то можно получить точность е ' +е для сколь угодно малого е ' при ограниченном N . При этом гарантируется, что функции оценивания после оптимизации T1 для k = 0 будут наилучшими (для нормы L2). Отметим необходимость выполнения условия А = 1 в случае учета рисков при реализации стратегий управления. При этом среднее значение RaV для x в интервалах [aj,аj+1 ] является в асимптотике однозначно определяемым, так как число соответствующих дискрет по определению пропорционально отношению N/K . Поскольку функция VaR в общем случае инверсна функции RaV, то и оценки также являются сходящимися. Таким образом, для достаточно большого к (K -число сегментов [aj,aj+1 ] ) выполняется условие min(K,l/max(cSj+1 - es,)) ^œ (при N ^œ), а следовательно, кривая значений VaR , полученная по рассмотренному алгоритму, сходится к реальной кривой VaR , построенной по результатам проведения и анализа большого числа стандартных симуляций.

5. Результаты моделирования

Моделирование рассмотренного метода проводилось для тестовой задачи управления запасами гидроресурсов электростанций с ограничениями, приведенными в [3]. Были получены кривые для комбинированного критерия (1 -a)E + aVaR при +а = 0; 0.1; 0.2; 0.4; 0.6; 0.8 с использованием 1800 сценариев. При этом наилучшие результаты соответствуют значению +а = 0.6. Анализ результатов показал существенное снижение уровня риска получения неудовлетворительных решений (в среднем на 55 %) при использовании комбинированного метода по сравнению с результатами, полученными с применением стандартной процедуры динамической оптимизации с сепарабельным критерием.

6. Выводы

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

Эффективность реализации предложенного подхода во многом зависит от правильного

выбора коэффициентов в несепарабельном критерии (1 - a)E + aVaR .

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

Перспективным представляется развитие предложенного подхода для фиксированных уровней риска и высокого уровня неконтролируемых возмущений.

Список литературы: 1. Dempster M. Intraday. FX trading: An evolutionary reinforcement learning approach. Intelligent data engineering and automated learning // Proceedings of the IDEAL 2002 International Conference. 2002. P. 347-358. 2. Гришко А.,Удовенко С., Чалая Л. Применение гибридных методов машинного обучения в компьютерных трейдинговых системах // Системные технологии. 2010. №3(68). С. 84-92. 3. Sarma M., Thomas S., Shah A. Performance Evaluation of Alternative VaR Models. Mumbai: Indira Gandhi Institute of Development Research, 2000. Р. 5-10.

Поступила в редколлегию 11.12.2011 Гришко Андрей Александрович, аспирант кафедры ЭВМ ХНУРЭ. Научные интересы: методы вычислительного интеллекта, машинное обучение в системах интеллектуальной обработки данных. Адрес: Украина, 61166, Харьков, пр. Ленина, 14.