Оптимизируем торгового робота: генетический алгоритм

в 16:19, , рубрики: Алгоритмы, генетические алгоритмы, минимизация функций

Оптимизируем торгового робота: генетический алгоритм - 1

В предыдущей статье я занялся сравнением методов параметрической оптимизации, т.е., подбора параметров, оценивая прибыльность торговли робота в ходе последующего бэктеста. Выяснилось, что банальный метод Монте-Карло — генерация случайных некоррелированных комбинаций параметров робота — работает вполне неплохо. Сейчас же я хочу протестировать популярный, в том числе, в сообществе программирующих трейдеров, алгоритм: генетический алгоритм оптимизации.

Генетический алгоритм оптимизации торговой стратегии

Этот алгоритм рассмотрим на примере оптимизации 2-х параметров. Оптимизируемые параметры нашего робота — период скользящей средней и TakeProfit. Для большего погружения в “генетику”, условимся называть период скользящей средней геном, отвечающим за “рост”, а TakeProfit — геном “цвета глаз”.

В пространстве допустимых значений параметров каждая точка, каждая пара координат — “рост / цвет глаз” теоретически описывает одну “особь”. Допустим, мы случайным образом сотворили 10 особей. Это и был первый шаг генетического алгоритма оптимизации — создать первое поколение:

Оптимизируем торгового робота: генетический алгоритм - 2

В пространстве координат M — T случайно выбраны точки. К примеру, две точки, отмеченные красной рамкой — “особи” с гендерно-нейтральными именами (это важный момент!) Женя и Саша. “Рост” Саши (в исходной постановке задачи — период скользящей средней) составляет 11 единиц, “цвет глаз” равен 0.6 (зелено-голубые глаза). Женя несколько отличается по параметрам. Те же характеристики описывают 8 оставшихся особей.

Второй шаг — размножение

Из всего первого поколения мы определяем какое-то количество наиболее “успешных” особей. Критерием, очевидно, является значение ЦФ. Эти особи будут размножаться, случайным образом формируя пары (вот по этой причине они получили гендерно-нейтральные имена). В общем случае, можно задать ряд правил для подбора пар. Например, подбирать близкие по характеристикам (т.е., буквально, ближайшие на координатном пространстве) особи — инбридинг. Можно, напротив, искать противоположности (аутбридинг). Я не мог найти аргументы в пользу одного из этих вариантов — в моей реализации пары формируются строго случайно… К примеру, Женя и Саша прошли ценз и решили породить потомка. Что это означает в нашем контексте:

Оптимизируем торгового робота: генетический алгоритм - 3

От двух “родительских” особей получаем третью особь, которая наследует часть признаков одного родителя, часть — другого. Например, у Жени с Сашей родилась особь Никита (НикИта, НикитА?):

  • Никита унаследовал признак “цвет глаз” (параметр TakeProfit робота) от одного из родителей — “Жени”,
  • “рост” (период скользящей средней робота) Никита унаследовал от “Саши”… но немного подкорректированный в сторону другого родителя, Жени.

Дело в том, что, чем меньше размерность пространства оптимизации (в нашем случае она равна 2), тем “теснее” будет потомству. Генетический алгоритм оптимизации не строго определяет правила “наследования” генов для дочерней особи. Поэтому, случайным образом, Никита позаимствовал цвет глаз без изменений, а вот ростом оказался посередине между обоими родителями, ближе к одному из них. В моей реализации с тем же успехом Никита мог бы позаимствовать оригинальные параметры от обоих родителей.

Третий шаг — селекция

Движитель эволюционного процесса, естественный отбор. 4 из 10 лучших особей дали еще 10 потомков. Теперь у нас 20 особей. Генетический алгоритм оптимизации предполагает поддержание постоянного размера популяции. 10 особей должны “умереть”. В данной реализации “умирают” большинство особей первого поколения, от 80% до 100%.
Соответственно, в нашем примере новое поколение будет составлено из 0… 2 родителей и 8 — 10 их отпрысков. Иначе говоря, если опустить лирику, новые вектора параметров торгового робота будут рассчитываться от векторов, полученных на предыдущем шаге, “размножении” (комбинации) 4-х лучших лучших тестов. Большинство «стариков» в новой итерации селекции участия не примут (возможны и другие варианты реализации селекции).

Завершение алгоритма

Размножение и селекция повторяются N раз. Конкретно в нашем примере, для сравнения с тремя испытанными ранее алгоритмами, тестируются 4 поколения по 10 особей, итого 40 тестов.
Но может так получиться, что очередная популяция сколлапсирует. Иначе говоря, все испытания будут в окрестностях нескольких точек. Чтобы избежать такой ситуации, применяют несколько механизмов, в частности:

  • вливание в популяцию “свежей крови”. К потомкам текущей популяции добавляется несколько новых особей, полученных случайно, таким же путем, которым формировалась начальная популяция,
  • механизм мутации: особь-потомок может иметь какую-то из характеристик (координат) несколько отличающийся от характеристик собственных родителей:

Оптимизируем торгового робота: генетический алгоритм - 4

в данном примере

  • характеристики потомка Джейн и Джосс — “рост” и “цвет глаз” заимствованы у каждого из родителей,
  • характеристики особи — потомка Сэм и Сири несколько отличаются от соответствующих характеристик обеих родительских особей.

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

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

Оптимизируем торгового робота: генетический алгоритм - 5

Как видно из анимации, поначалу расположение точек хаотичное, но, с последующими поколениями имеет тенденцию к области с более высокими значениями ЦФ.

Теперь сравним алгоритмы на все той же поверхности: P = f(M, T):

Оптимизируем торгового робота: генетический алгоритм - 6

Монте-Карло градиентный спуск “морской бой” генетический алгоритм
95.7% 92.1% 97.0% 96.8%

Среднее значение найденного экстремума ЦФ в процентах от глобального значения.

Конечно, по одному набору входных данных судить рано, но пока что ГА, применительно к нашему торговому роботу, уступает алгоритму “морской бой”:

  • совсем незначительно — по среднему от найденного квазиоптимального значения ЦФ,
  • дает худшую оценку параметрической устойчивости торгового алгоритма, так как не слишком подробно “исследует” окрестности найденных квазиоптимальных кортежей параметров.

Итоговый тест 4-х алгоритмов оптимизации

Итоговый тест проведен на 4-х наборах входных данных — результаты бэктеста торговой стратегии на 4-х разных отрезках истории цен (EURUSD: 2016 год, EURUSD: 2017, XAUUSD: 2016, XAUUSD: 2017).

Оптимизируем торгового робота: генетический алгоритм - 7

(примеры ЦФ как функций от двух параметров для 4-х временных рядов цен)

В этот раз оптимизация проводилась по 3-м параметрам:

  1. период “быстрой” скользящей средней
  2. период “медленной” скользящей средней
  3. TakeProfit (прибыль по сделке, в процентах, при достижении которой сделка завершалась).

Каждый из параметров принимал 20 различных значений. Итого, для построения таблицы
P = F(Mf, Ms, T)
где P — прибыль, Mf — период “быстрой” скользящей средней, Ms — период “медленной” скользящей средней, T — TakeProfit,
было проведено 20 * 20 * 20 = 8 000 итераций тестирования.

Оптимизация проводилась с ограничением в 160, 400 и 800 тестов (вычислений ЦФ в выбранных координатах). Каждый раз результаты усреднялись для 1 000 итераций оптимизации. Среднее значение ЦФ для найденного квазиоптимального вектора параметров составило:

Монте-Карло градиентный спуск “морской бой” генетический алгоритм
84.1% 83.9% 77.0% 92.6%

Отдельно стоит отметить, что ГА показывают неплохой результат даже при небольшом проценте испытаний от всего возможного количества вариантов:

тестов Монте-Карло градиентный спуск “морской бой” генетический алгоритм
160 из 8 000 79.1% 76.7% 73.1% 87.7%
400 из 8 000 84.7% 85.0% 77.4% 93.7%
800 из 8 000 88.6% 90.1% 80.4% 96.3%

Вместо заключения

Я был несколько удивлен результатом, который показал генетический алгоритм оптимизации. Не считаю, что конкретно “генетическая парадигма” метода обеспечила ему первое место в списке. В каком-то смысле, по логике выбора координат, он напоминал методы дихотомии / золотого сечения. Вероятно, стоит опробовать один из этих алгоритмов и сравнивать ГА именно с ним.

Возвращаясь к торговому роботу, стоит отметить, как меняется “рельеф” поверхности, образованной ЦФ (прибылью) от года к году. Т.е., “оптимизировав” робота на истории 2017 года нет смысла применять эти настройки в 2018 году (первом квартале, месяце, неделе … 2018 года).

Искусственные, догматические и беспомощные торговые стратегии, вроде нашей (покупать по пересечению скользящей средней), вероятно, не скоро выйдут из моды. Других стратегий, к сожалению, мне встречать не довелось. Соответственно, прибыль или убыток торговых роботов я отношу, скорее, к удаче, чем к достоинствам / недостаткам алгоритма. Потому задача параметрической оптимизации торгового робота представляет для меня лично исключительно академический интерес.

Автор: AndreySitaev

Источник

* - обязательные к заполнению поля