Стронгин Р.Г (ред.) Высокопроизводительные параллельные вычисления на кластерных системах
Подождите немного. Документ загружается.
251
перемещений по кратчайшему пути между каждой парой вершин
(очевидно, что матрица
L
получается из матрицы
V
путем
применения алгоритма Флойда [4]).
Стратегия обслуживания определяется перестановкой
),...,,(
21 n
iii=
ρ
элементов множества
},....,2,1{ n
. Объект с номером
k
i
в стратегии
ρ
обслуживается
k
-м по очереди; момент завершения
обслуживания объекта с номером
k
i
обозначаем через
),(*
k
it
ρ
.
Считается, что реализация стратегии компактна, а перемещение от
каждого обслуженного объекта к очередному выполняется по
кратчайшему пути. Совокупный штраф при обслуживании объектов
согласно стратегии
ρ
есть
∑
=
=
n
i
itiQ
1
*
)),(,()(
ρϕρ
. Экстремальная
задача записывается как
)(min ρQ
ρ
. (1)
Задача (1) NP-трудна, поскольку к ней полиномиально сводима
задача коммивояжера; оценка продолжительности синтеза в
зависимости от размерности задачи имеет экспоненциальный
характер. Решение задачи (1) может быть получено путем пошаговой
реализации вычислительного процесса по приводимым ниже
рекуррентным соотношениям динамического программирования
)},())},({\,),,(),(*({
min
),,( tijjoSiijltiDSit
p
So
j
ϕ
+−Σ=Σ
∈
0),0,0( =∅Σ
. (2)
В системе (2) приняты следующие обозначения:
t
– произвольный
момент принятия решения;
S
– совокупность объектов из
n
O
,
которые были обслужены раньше, чем
)(io
;
),(* tiD
− требуемый
момент начала обслуживания объекта
)(io
, если оно должно
завершиться в момент времени
t
;
)],(*),,()))((,()([ tiDijljtjjtT
p
+
+=
τ
;
),,( Sit
Σ
– минимально
возможная величина суммарных затрат при переводе управляемой
системы обслуживания из начального состояния A
0
=
),0,0(
∅
в
состояние
),,( Sit
, определяемая по формуле
252
∑
∑
∑
⎪
⎩
⎪
⎨
⎧
=−
>−
=
∈
p
p
Tt
ittiDприjoSjijlt
ittiDприjoSjijltiD
jSit
pp
)(),(*)}),({\,),,((min
)(),(*)}),({\,),,(),(*(
),,,(
Описание параллельного алгоритма синтеза оптимальных
стратегий обслуживания
Формулы (2) – рекуррентные соотношения динамического
программирования для решения задачи (1), ориентированные на
организацию "прямого счета", т.е. в порядке роста значений аргумента
t функции Беллмана Σ(t, i, S). Описание соответствующей
вычислительной процедуры приведено в [5]. Ниже излагается
модификация указанной процедуры, использующая возможности
распараллеливания, а также идеи метода ветвей и границ.
Введем оператор R раскрытия
состояния: если Х = (t, i, S) –
произвольное, отличное от финального состояние системы (т.е.
S ⊂ O
n
\ {o(i)}), то R(t, i, S) – множество состояний, порождаемых
состоянием Х, т.е. непосредственно следующих за этим состоянием.
Раскрыв начальное состояние A
0
и последовательно раскрывая все
далее получаемые состояния, мы в конечном итоге дойдем до
совокупности финальных состояний системы вида (t, i, O
n
\ {o(i)}).
Определим также оператор R*, который, в отличие от оператора R,
раскрывает не состояния, а их расширения – записи. Записью будем
называть кортеж (t, i, S, z, z*, c, h, v), где (t, i, S) = Х – состояние
системы, z – получаемый номер этого состояния, z* – номер
непосредственно предшествующего состояния, c – стоимость
определяемой построенной совокупностью записей траектории от
начального состояния до состояния Х
, h и v – соответственно нижняя и
верхняя оценки стоимостей всех возможных полных траекторий из A
0
в финальные состояния, начальная часть которых совпадает с
траекторией из A
0
в X.
Нижняя оценка h есть сумма с + Σ
H
(t, i, O
n
\ S), где через
Σ
H
(t, i, O
n
\ S) обозначена сумма
∑
∈Sjo
jit
)(
min
),,(
ϕ
, в которой
ϕ
min
(t, i, j) =
ϕ
(i, t
min
*
(t, i, j)) – величина штрафа по объекту o(j) при
условии, что его обслуживание начинается вслед за объектом o(i), т.е.
в момент времени t
min
(t, i, j) = max(t + l(i, j), t(j)); при этом t
min
*
(t, i, j) –
момент завершения обслуживания o(j), т.е. t
min
(t, i, j) +
τ
(j, t
min
(t, i, j)).
Очевидно, что в силу монотонности функции штрафа, величина
253
Σ
H
(t, i, O
n
\ S) является неуменьшаемой нижней оценкой оптимального
штрафа по объектам множества O
n
\ S.
Верхняя оценка v есть сумма с + Σ
V
(t, i, O
n
\ S), где Σ
V
(t, i, O
n
\ S) –
верхняя оценка оптимального суммарного штрафа по объектам
множества O
n
\ S при их обслуживании вслед за o(i). Значение
последней предлагается вычислять согласно следующей пошаговой
процедуры, относящейся к классу жадных алгоритмов[6].
1. Производится инициализации первоначальных значений
переменных алгоритма:
S
= O
n
\ S, ii = , tt = , Σ
V
(t, i, O
n
\ S) = 0.
2.1. В качестве очередного объекта, принимаемого к
обслуживанию, выбирается тот объект o(k)∈
S
, который обеспечивает
минимум приращения нижней оценки суммарного штрафа по
объектам множества
)}({\ koS
:
)})}({\,,()})({\,),,,(({min
*
koSitkoSkkitt
HH
Sk
Σ−Σ
∈
.
2.2. С учетом номера выбранного объекта производится
обновление значений переменных алгоритма:
S
=
S
\{o(k)},
t = t
min
*
(t, i , k), Σ
V
(t, i, O
n
\ S) = Σ
V
(t, i, O
n
\ S) +
ϕ
min
( t , i , k), i = k.
2.3. Если
S
≠ ∅, то переход на шаг 2.1, в противном случае –
останов.
Будем говорить, что запись Z = (t, i, S, z, z*, c, h, v) доминируется
записью Z
1
= (t
1
, i, S
1
, z
1
, z
1
*
, с
1
, h
1
, v
1
), если t
1
≤ t, S ⊆ S
1
, c
1
≤ c, причем
по меньшей мере одно из записанных соотношений выполняется как
строгое (строгое включение или строгое неравенство). Очевидно, что в
случае, когда запись Z
1
доминирует запись Z, траектория,
заканчивающаяся в итоге расширением Z
1
, предпочтительнее
траектории, заканчивающейся расширением Z. Очевидно также, что
если существует траектория, заканчивающаяся расширением
Z
2
= (t
2
, i
2
, S
2
, z
2
, z
2
*
, с
2
, h
2
, v
2
), и такая, что v
2
≤ h, то в этом случае
состояние X (соответствующее расширению Z) является
бесперспективным направлением счета и может быть исключено из
дальнейшего рассмотрения.
Итак, предполагаем, что параллельная система (ПС) состоит из m
вычислительных узлов cl
1
, …, cl
m
и одного узла-координатора cl
0
,
соединенных локальной сетью.
254
0. В начальный момент времени все вычислительные узлы
находятся в режиме ожидания, т.е.:
массив записей, раскрываемых узлом cl
i
– пуст (M
i
= ∅);
массив всех сгенерированных параллельной системой записей,
о которых на данный момент времени известно узлу cl
i
, а
также массив номеров записей, помеченных как удаленные,
пусты: G
i
= ∅, D
i
= ∅ (i = m,1 ).
множество номеров свободных узлов на координаторе
содержит номера всех узлов ПС (J = {1, 2,…, m}), а массивы
всех сгенерированных системой нефинальных и финальных
записей, а также записей, помеченных как удаленные – пусты:
G = ∅, F = ∅, D = ∅.
1. Координатор отправляет на cl
1
начальную запись Z
0
=(0, 0, ∅, 0,
0, 0, h
0
, v
0
), отражая изменение состояния системы в массивах J и G:
J = {2, 3, ..., m}, G = {Z
0
}.
2. На каждом узле cl
i
:
если узел находится в режиме ожидания (W
i
= 0) и он получает
от координатора пакет записей T, подлежащих раскрытию, то
этот пакет переносится в массив M
i
(M
i
= T ) и узел
переводится в рабочий режим (W
i
= 1);
если узел находится в рабочем режиме (W
i
= 1):
если M
i
= ∅, то узел переводится в режим ожидания (W
i
= 0) и
об этом ообщается координатору (J = J ∪ {i});
если M
i
≠ ∅, начинает действовать основная часть алгоритма.
2.1. Узлом запрашиваются от координатора записи из массива G
начиная с (|G
i
|+1)-й и добавляются в конец G
i
; аналогичным образом
запрашиваются номера удаленных записей начиная с (|D
i
|+1)-го
элемента массива D и добавляются в конец D
i
.
2.2. Из M
i
изымаются все записи, к ним применяется оператор R
*
и
результат сохраняется в G
i
*
.
2.3. Из числа записей массива G
i
помечаются как удаленные те
записи, которые либо доминируются записями из G
i
*
, либо их нижняя
оценка превышает верхнюю для какой-либо записи множества G
i
*
.
Совокупность записей, помеченных к удалению, добавляется в конец
D
i
.
2.4. Если в G
i
*
есть финальные записи, то они перемещаются в F
i
.
255
2.5. Устанавливается соединение с координатором, в рамках
которого передается содержимое массивов D
i
, G
i
*
и F
i
и сообщается о
незанятости узла cl
i
(J = J ∪ {i}).
2.6. Узел переводится в режим ожидания, т.е.
G
i
*
= ∅, F
i
= ∅, W
i
= 0.
3. При установлении соединения по инициативе узла cl
i
координатор принимает результаты работы узла (массивы D
i
, G
i
*
и F
i
)
и добавляет их в конец соответствующих совокупных массивов
записей, сгенерированных всей ПС (D = D ∪ D
i
, G = G ∪ G
i
*
, F
= F ∪ F
i
). После этого в массиве F оставляются только записи с
минимальным значением суммарного штрафа, а остальные записи
удаляются. По завершении соединения принятая координатором
совокупность нефинальных записей G
i
*
распределяется между узлами
множества J, и соответствующие узлы изымаются из J. Заметим, что
соединения узлов с координатором осуществляются в монопольном
режиме c целью синхронизации процесса обновлений массивов D, G и
F.
4. Процесс завершается, когда J = {1, 2, ..., m} и G
i
*
= ∅ (i = m,1 ),
т.е. все узлы завершили вычисления и нераскрытые нефинальные
записи отсутствуют. В этом случае массив F содержит все финальные
записи с минимальным значением штрафа c. Определив траекторию
системы, ведущую из начального состояния в состояние, определяемое
некоторой записью массива F, очевидным образом можно построить
соответствующую оптимальную стратегию.
Литература
1. Коган, Д.И. Проблема синтеза оптимального расписания
обслуживания бинарного потока объектов mobile-процессором
/ Д.И. Коган, Ю.С. Федосенко, А.В. Шеянов // Труды III
Международной конференции «Дискретные модели в теории
управляющих систем». – Москва. – 1998. – С. 43 – 46.
2.
Коган, Д.И. Задача диспетчеризации: анализ вычислительной
сложности и полиномиально разрешимые подклассы / Д.И.
Коган, Ю.С. Федосенко // Дискретная математика. – 1996. – т.
8. – №3. – с. 135 – 147.
3.
Коган, Д.И. Математическая модель и алгоритм синтеза
субоптимальных расписаний однопроцессорного
обслуживания пространственно рассредоточенной группы
256
стационарных объектов / Д.И. Коган, Ю.С. Федосенко, А.Ю.
Шлюгаев // Труды VI Международной конференции
«Идентификация систем и задачи управления SICPRO’07». –
Москва. – 2007. – С. 1026 – 1038.
4.
Асанов, М.О. Дискретная математика. Графы, матроиды,
алгоритмы / М.О. Асанов, В.А. Баранский, В.В. Расин. –
Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001.
5.
Коган, Д.И. Задача оптимального управления обслуживанием
mobile-процессором группы пространственно
рассредоточенных стационарных объектов / Д.И. Коган,
Ю.С. Федосенко // Вестник ВГАВТ. Межвузовская серия:
Моделирование и оптимизация сложных систем. –
Н.Новгород: Изд-во ФГОУ ВПО ВГАВТ. – 2005. – Вып. 14. –
С. 95 – 98.
6.
Пападимитриу, Х. Комбинаторная оптимизация. Алгоритмы и
сложность / Х. Пападимитриу, К. Стайглиц. – М.: Мир. – 1985.
– 510 с.
ПАРАЛЛЕЛЬНАЯ РЕАЛИЗАЦИЯ ЭВОЛЮЦИОННОГО
АЛГОРИТМА ОПТИМИЗАЦИИ СТРАТЕГИЙ БИРЖЕВОЙ
ТОРГОВЛИ
О.Г. Монахов, Э.А. Монахова
Институт вычислительной математики и математической
геофизики СОРАН, Новосибирск
Введение
В практике биржевой торговли одним из основных направлений
при выработке торговых стратегий (торговых алгоритмов) является
технический анализ ценовых рядов с помощью множества
индикаторов [1-6]. В соответствии с принятой торговой стратегией,
выраженной в виде набора правил, с поведением ценового ряда и
значениями индикаторов инвестор принимает решение о
совершении/несовершении сделки купли-продажи
в данный момент
времени. При совершении сделки инвестор руководствуется
соображениями максимизации доходности и минимизации риска.
Принятый набор правил, составляющий торговую стратегию, и
используемые индикаторы имеют эмпирический характер, и значения
их параметров определяются в основном опытным путем (методом
257
проб и ошибок). Однако, как показывают эксперименты, такой подход
с использованием известных правил и статически задаваемых
параметров часто приводит к убыточным стратегиям.
Целью данной работы является описание подхода к оптимизации
торговых стратегий, основанного на эволюционных вычислениях, и
его распараллеливанию. Представлен генетический алгоритм (ГА),
который в процессе торговых сессий осуществляет автоматический
поиск оптимальных параметров торговых стратегий и индикаторов с
точки зрения максимизации показателей доходности.
Постановка задачи
В работе рассматривается проблема поиска параметров данной
торговой стратегии S с целью оптимизации заданной целевой
функции F, характеризующей ее качество. Будем считать, что цена на
акцию представлена в виде ценового ряда {
i
C
},
Ni
≤
≤
1
, с заданной
частотой (например, минутные или часовые цены), где
i
C
- цена
закрытия в момент i. Пусть
iii
CCr
−
=
++ 11
. Важными инструментами
технического анализа рынка акций являются скользящие средние,
индикаторы и осцилляторы, на основе которых формируются
множество торговых стратегий и которые помогают инвестору
принимать решения о купле-продаже акций [1-6].
Пусть мы имеем индикатор технического анализа:
).,...,,(
1
)(
niii
n
i
CCCfI
−−
=
Обобщенная торговая стратегия
)(
)(n
i
IS
,
основанная на индикаторе
)(n
i
I
, определяется следующими
соотношениями:
⎪
⎩
⎪
⎨
⎧
−<−
≤≤−
>
=
+
.,1
,,
,,1
2
)(
1
)(
2
1
)(
1
ε
εεϕ
ε
ϕ
n
i
n
ii
n
i
i
Iесли
Iесли
Iесли
где
0,
21
>
ε
ε
- уровни значимого изменения индикатора
)(n
i
I
.
Состояние покупки в данной торговой стратегии наступает при
1
1
=
+i
ϕ
, а состояние продажи наступает при
1
1
−
=
+i
ϕ
. Решение о
сделке (купле/продаже) принимается при смене состояний:
1
1
−
=
+ii
ϕ
ϕ
.
Эта стратегия
)(
)(n
i
IS
будет использована как темплейт (с
некоторыми модификациями) для определения торговых стратегий на
258
основе различных индикаторов технического анализа, и поиск
оптимальных значений свободных параметров
),,(
21
ε
ε
n
,
определяющих стратегию с наилучшими показателями доходности,
будет осуществляться с помощью ГА.
Например, одним из часто используемых индикаторов при анализе
ценовых рядов является экспоненциальное скользящее среднее
порядка k:
() () () ()
10
10
2
();,
1
kk kk
ii i
i
CC CCCC
k
+
+
=+ − =
+
Ni ≤≤1
.
Порядок скользящего среднего k определяет степень сглаживания
цены: чем больше k, тем сильнее сглаживание. Рассчитывается также
разность экспоненциальных скользящих средних порядков
21
kk
<
:
12 2
() () ()
()
kk k
i
ii i
rC C C=−
.
Приведем пример простейшей торговой стратегии на основе
экспоненциальных скользящих средних [2]. Задается уровень
значимого изменения сглаженных цен
0>
ε
. Состояние покупки в
данной торговой стратегии наступает при
ε
>
i
r
, а состояние продажи
наступает при
ε
−<
i
r
. Решение о сделке (купле/продаже) принимается
при смене состояний. Стратегия имеет три свободных параметра
ε
,,
21
kk
, изменение которых изменяет показатели доходности и риска
торговой стратегии.
Поиск оптимальных стратегий (с наилучшими показателями
доходности и/или риска) может осуществлятся для каждого типа акций
отдельно в динамике торговых сессий, с постоянной адаптацией к
рыночной ситуации, или в квазидинамическом режиме, когда расчет
оптимальных параметров происходит либо через заданные периоды
времени
либо по выполнению определенных условий (например, по
достижении заданного уровня потерь).
Пусть торговая стратегия S содержит параметры
0},{ >
=
npP
n
,
описывающие значения целочисленных и действительных
коэффициентов и переменных, значения индексов, параметры
структур данных, константы и некоторые примитивные операции
алгоритма (величины инкрементов и декрементов, знаки переменных,
логические операции и отношения, типы округления переменных).
259
Целевая функция F оценивает величину доходности стратегии S,
полученную при заданных значениях параметров
0},{ >
=
npP
n
и при
входных данных ценового ряда {
i
C
}:
,)),,(( ijCPSFF
jii
≤
=
Ni
≤
≤
1
.
Таким образом, проблема оптимизации торговой стратегии
состоит в следующем: для данной стратегии S и заданного набора
значений ценового ряда {
i
C
},
Ni
≤
≤
1
, необходимо найти такие
значения параметров P* стратегии S, что
≥)),((
*
iN
CPSF
)),,((
iN
CPSF
для
Ni ≤≤1
, при любых других значениях параметров
)(PDomP
∈
.
Для решения данной проблемы в работе предлагается подход,
основанный на применении генетических алгоритмов (ГА) [7, 8] с
использованием предварительного знания прикладной области
(множества индикаторов), выборе обобщенной схемы торговой
стратегии, задаваемой в виде темплейта с параметрами [9], и
ограничении пространства поиска оптимальных параметров.
Генетический алгоритм
Генетический алгоритм основан на моделировании процесса
естественного отбора в популяции особей, каждая из которых
представлена точкой в пространстве решений задачи оптимизации.
Особи представлены структурами данных Gen - хромосомами,
включающими свободные (неопределенные) параметры
k
p
торговой
стратегии S:
0},,...,,{}{
21
>
=
=
kpppPGen
k
. Эти параметры определяют
необходимую торговую стратегию S(Gen). Каждая популяция является
множеством структур данных Gen и определяет множество стратегии
S(Gen).
Основная идея алгоритма синтеза состоит в эволюционном
преобразовании множества хромосом (параметров стратегии) в
процессе естественного отбора с целью выживания "сильнейшего". В
нашем случае этими особями являются стратегии, имеющие
наибольшее значение целевой
функции. Алгоритм начинается с
генерации начальной популяции. Все особи в этой популяции
создаются случайно, затем отбираются наилучшие особи и
запоминаются. Для создания популяции следующего поколения
(следующей итерации) новые особи формируются с помощью
генетических операций селекции (отбора), мутации, кроссовера и
добавления новых элементов (для сохранения разнообразия
популяции).
260
Примем, что целевая функция (fitness function, функция качества,
функция пригодности) F вычисляет суммарную доходность
N
D
,
полученную в результате торговли в соответствии с данной стратегией
S за N шагов для заданного ценового ряда {
i
C
},
Ni
≤
≤
1
:
,)(
1
∑
=
−==
br
N
m
br
mN
CommdDF
buy
m
buy
m
sell
m
br
m
C
CC
d
−
=
,
где
buy
m
sell
m
CC ,
- цены продажи и покупки в m-той сделке,
br
N
- число
сделок за N шагов моделирования, Comm - размер постоянных
комиссионных за каждую сделку. Целью алгоритма является поиск
максимума F.
Экспериментальные результаты
Предложенный генетический алгоритм с использованием
темплейтов был успешно применен для адаптивной оптимизации
торговых стратегий, основанных на следующих, наиболее популярных
инструментах технического анализа: экспоненциальнных скользящих
средних (EMA - exponential moving average), индекса относительной
силы (RSI - relative strength index), темпа изменения цены (ROC - price
rate-of-change), момента (Momentum) , метода схождения-расхождения
скользящих средних (MACD - Moving Average
Convergence/Divergence) [1-6].
Для экспериметов были рассмотрены ценовые ряды с минутными
интервалами для акций ГАЗПРОМа (65535 точек
), РАО ЕС России
(65535 точек), NIKKEI (42620 точек), DJIA - Dow Jones Industrial
Average (65535 точек), для периода с 16.04.2006 по 16.04.2007. Мы
использовали первые 15000 точек для обучения и остальные точки –
для тестирования.
Число итераций и размер популяции выбирались
экспериментальным путем, основываясь на параметрах из [7, 8].
Значения основных параметров в экспериментах следующие: размер
популяции (для однопроцессорной системы) – 16000, число итераций –
200, частота мутации – 0.15, частота
кроссовера – 0.7, комиссионные –
0.001.
Генетический алгоритм оптимизации торговых стратегий был
реализован в системе эволюционного синтеза алгоритмов на основе