Доброго времени суток. В этой статье расскажу о создании системы в которой генетические алгоритмы пишут роботов. В теории эти роботы могли бы торговать на бирже.

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

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

Эта статья подразумевает что вы знакомы с понятием генетические алгоритмы или генетическое программирование. А также, что делают торговые роботы.

С чего бы начать?

Я начал с изучения платформы для создания роботов MetaTrader5. Язык MQL5 позиционируется как схожий с С++, с незначительными отличиями в синтаксисе. Если говорить простыми словами, в платформе имеются функции для доступа к данным рынка и функции для выполнения торговых операций. После изучения и проверки нескольких десятков простых роботов, началась работа над их выделением общей элементарной базы, на которой и строятся эти алгоритмы.

Для удобства работы с логикой внутри генетического алгоритма мне пришлось создать свой мета-язык над MQL, назовем его SadLobster. Без этого обобщения было бы ужасно сложно заставить машину писать код по правилам языка программирования созданного для человека. Весь проект был обозначен как прототип, чтобы было проще принять множество компромиссов и упрощений. Иначе эта фаза разработки никогда бы не закончилась.

Как работает один робот

Давайте сразу посмотрим как выглядит упрощенная версия робота, который будет создан.
(пришлось выбросить лишнее, чтобы статья имела законченный вид)


Функции boolA__3 и priceA__10 обрабатывают информацию, получаемую с графиков котировок.
Функция boolA__3 запускается чтобы проверить есть ли сигнал для выставления ордера. Первый раз мы проверяем есть ли сигнал на покупку. Второй раз запускаем еще со значением инверт=1 и проверяем есть ли сигнал на продажу.

Функция priceA__10 определяет по какой цене должен быть выставлен ордер.

SadLobster
Вторая фишка языка SadLobster в том, что его синтаксис совместим с С++. То есть, тот же код, что я использую для тестирования в MQL, можно запустить через С++ тестер, который был написан отдельно.

MQL tester vs C++ tester

• Этот тестер на два порядка быстрее MQL и имеет необходимое API чтобы им мог управлять генетический алгоритм.
• MQL же предоставляет отличные возможности для отладки и проверки правильной работы роботов.

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

Язык состоит из списка функций которые можно использовать. Простейшие — AND, OR, CREATE_LINE, IS_INSIDE,…

И функции доступа к данным котировок и технических индикаторов — HIGH, LOW, FRACTAL, MA, MACD_SIGNAL. Эти функции будут перечислены в списке 1.

Симуляция торговли на истории

Робот запускается на периоде истории, например с 2014 по 2016 год. Происходит моделирование торговли. Все его сделки записываются и по ним формируется отчет. Мой отчет выглядит примерно так:



или так

1.82  14.66   64.1%   1.02   -383[+0.99]    451 (30.8%)    +6613 :     179F  <736c> 

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

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

Фитнес функция

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

Первое решение — чем больше робот заработал, тем он лучше. Но тут возникает вопрос рисков. Такой робот совершенно нежизнеспособен. Меньше риск — меньше прибыль, больше риск больше прибыль.

У торговых роботов есть несколько различных характеристик. Самые простые из них — профит фактор(PF) и математическое ожидание прибыли на одну сделку(EP), максимальная просадка по средствам, LR correlation, Коэффициент Шарпа.

Вот так выглядит отчет MetaTrader о работе одного из созданных роботов:



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

self.KOEF = [2, 4, 1, 1, 1, 1, 0, 0, 2]
self.KEYS = ['PF', 'EP', 'win_persent', 'p_wiin_div_loss', 'max_dd', 'deals', 'profit', 'pfMonth', 'LR']

Динамика и результаты запуска Генетического Алгоритма

Графическое представление эволюции или график обучения



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

Справа гистограмма помесячной прибыльности лучшего из роботов в пунктах. На ней слева отображено три года обучения, а справа — один год кросс теста.

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

О сложности

Алгоритм робота для простоты не имеет внутренней памяти или состояний. Эта же особенность помогает кешировать результаты вычислений на каждом баре. Что сильно ускоряет вычисления. Стараясь использовать только функции со сложностью О(1) или O(n) в логике, я сильно ограничил функционал. Но этого требовали вычислительные ресурсы.

Генерация случайного дерева

Как получить функцию в том виде в котором она представлена в первом листинге?

1. Надо создать список возможных функций и описать их
2. Собрать случайное дерево-выражение которое и есть логика
3. Преобразовать в код

Вот часть интерфейсных функций которые используются в логике роботов. Каждое имя функции это некий макрос, доступный как с MQL так и с тестового фреймворка С++. Реализации отличаются, в силу различий в языках. Назовем его список 1.


Рассмотрим простую функцию MORE_I

{'name':'MORE_I', 'input':['DEF_PRICE','DEF_PRICE','invert'], 'result':'DEF_BOOL', 'price':4}

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

А вот здесь возникает неплохая олимпиадная задачка: необходимо из исходных функций собрать все возможные варианты логик с заданной сложностью и типом результата. Под логикой следует понимать выражение типа F(X)->Y.

Пример — мы хотим функцию принятия решения о входе в длинную позицию. Нам нужно булевое решение — DEF_BOOL, тогда возможные варианты следующие:

return MORE_I(_CLOSE(__value(1)), _HIGH(__value(1)), invert);//1
return MORE_I(_CLOSE_D1(1), _HIGH(__value(1)), invert);//2
//__value сообщает о типе “1” но его можно убрать.
//PS также желательно понимать могут ли в данной функции быть одинаковые параметры. 

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

Задача алгоритма — сгенерировать функцию, которая будет возвращать DEF_BOOL. Нотация выражения LISP-подобная: [Function Name, param1, param2...]. Параметры, которые начинаются с DEF, являются типом. Выражение в котором есть такой параметр не является окончательным, требует уточнения. В нотации не указывается тип возвращаемого значения за ненадобностью.

1. Давайте создадим пул таких выражений, где мы их и будем генерировать.
2. Проверяем нет ли в нашем пуле функции без параметров требующих уточнения. Если есть, выбираем его и возвращаем как результат. Если нет продолжаем.
   
3. Выбираем случайно одно из следующих возможных действий — добавить в пул еще одну функцию(4) или заполнить в существующей неуточненные параметры(5).
   
4. Добавить новое выражение. Поскольку нам нужны только функции которые будет возвращать тип DEF_BOOL, выбираем все такие функции из списка СП1. Теперь выбираем случайную функцию и записываем ее в пул в виде [‘IS_INSIDE’, ‘DEF_HPRICE_LEVEL’, ‘DEF_PRICE’].
   
5. Расширяем существующую функцию. В функции IS_INSIDE два параметра требуют уточнения. Ищем функцию которой можно заполнить параметр DEF_PRICE в СП1.
   Получаем ['IS_INSIDE', ‘DEF_HPRICE_LEVEL’, ['MA_HI_I_v2', '8', 'dsD1', '1', 'invert']].
6. Возвращаемся к пункту 2.

Результатом алгоритма будет подобное выражение

['IS_INSIDE',
 ['MAKE_HPRICE_LEVEL',
  ['MA_CLOSE_v2', '3', 'dsD1', '1'],
  ['STDDEV8_RANGE_MAX_END', '10']],
 ['MA_HI_I_v2', '8', 'dsD1', '1', 'invert']]

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

Это третья реализация алгоритма, первые два были не столь удачны. Весьма полезно было ознакомиться с 4-м томом Кнута, а именно главой 7.2.1.6 Генерация всех деревьев. Если нужна будет улучшенная версия, обязательно перечитаю ее снова. Недостатками этого алгоритма является:

1. Надо убедиться что СП1 способен порождать выражения в нужном количестве и многообразии. Для этого у меня просто существует тест, который показывает что из 10000 сгенерированных функций 90% являются уникальными.
   
2. Также не ясно какое распределение базовых функций в выражении.
   
3. Хотелось бы знать какое количество различных функций может порождать конкретный список базовых функций.
   
4. PS. Это, кстати, одно из тех мест системы, где мы заменили всю силу аналитического ума человека на простую функцию Random(). Человек который создает робота уже должен знать ответ на вопрос Как? этот робот будет работать и Почему. ГА здесь просто выполняет роль оптимизированного полного перебора.
   

Трансляция в конечную форму

Далее это LISP-подобное выражение превращается в листинг на языке SadLobster, где каждое неделимое выражение — это новая переменная. Логически выражение остается тем же.

DEF_BOOL boolA_001(bool invert) {
        DEF_PRICE var_2 = MA_HI_I(8, dsD1, 1, invert);
        DEF_PIPS_DOUBLE var_1 = STDDEV8_RANGE_MAX_END(10);
        DEF_PRICE var_0 = MA_CLOSE(3, dsD1, 1);
        DEF_HPRICE_LEVEL var_3 = MAKE_HPRICE_LEVEL(var_0, var_1);
        DEF_BOOL var_4 = IS_INSIDE(var_3, var_2);
        return var_4;
}

SadLobster это не Haskell c чистыми функциями

Хотя я к этому стремился. Одна из проблем которые стоят при создании языка — обработка ошибок. Сразу возникло желание применить механизм эксепшенов, но MQL их не поддерживает. Самая частовозникаемая проблема — неудачно созданный объект. Идеально было бы использовать nil значения, не будем усложнять раньше времени. Это можно улучшить в следующих версиях. А в текущей реализации просто проверяется валидный ли объект, если нет то функция немедленно завершается. Этим занимается макрос типа CHECK_LINE_OR_FALSE.

DEF_PERIOD var_1 = makePeriodSinceLastDay(ds);
DEF_POINTS var_0 = GetZZPoints(5, ds, 0);
DEF_LINE var_3 = MAKE_SUPPORT(var_0, var_1, 4, !invert); CHECK_LINE_OR_FALSE(var_3);

Оптимизация выражений

Рассмотрим вариант когда выражение выглядит так:

['IS_INSIDE',
 ['MAKE_HPRICE_LEVEL',
  ['GET_MEDIAN_CLOSE_PRICE', ['makePeriodToday', 'ds'], 'ds'], //1
  ['MA_RANGE_v2', '7', 'dsD1', '1']],
 ['GET_MEDIAN_CLOSE_PRICE', ['makePeriodToday', 'ds'], 'ds']] //2

Выражения 1 и 2 одинаковые. После транслирования и выделения переменных, var_2 используется в обоих местах и никакого дублирования кода.

 DEF_PIPS_DOUBLE var_1 = MA_RANGE(7, dsD1, 1);
 DEF_PERIOD var_0 = makePeriodToday(ds);
 DEF_PRICE var_2 = GET_MEDIAN_CLOSE_PRICE(var_0, ds);
 DEF_HPRICE_LEVEL var_3 = MAKE_HPRICE_LEVEL(var_2, var_1);
 DEF_BOOL var_4 = IS_INSIDE(var_3, var_2);

Разработка требует инфраструктуры

Я хотел создать очень робастную базу для конструирования роботов. Разбирая примеры заказов АТС на фриланс бирже, я встраивал новые возможности/требования из ТЗ в общую систему. Так я старался расширить разнообразие в поведении роботов, потому как разнообразие в кодовой базе могло вести к созданию одних и тех же алгоритмических паттернов.

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

1. Логировать данные в базу во время работы ГА
2. Достать из базы и обработать
3. Отобразить графически при помощи mathplotlib

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

Пару слов о производительности

Тестирование очень быстрое по нескольким причинам:

• Все роботы компилируются в машинный код.
• Тестирование запускаются многопоточно.
• Распараллелен даже процесс линковки.
• Из тестера стратегий урезано много проверок.
• Используется кеширование для тяжелых функций
• Тестирование роботов очень грубое, тут нет скальперов или HFT, анализ происходит на часовых графиках.
• Я использовал процессор на 12 потоков с разгоном до 4GHz Intel Core i7-5820K для тестирования.

Как это работает?

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

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

Хочу уточнить что в работах не используется Money Management и торговля ведется одним и тем же минимальным объемом.



158$ средняя прибыль в месяц при обучении, 21$ — средняя прибыль в течении следующих 12 месяцев. Результаты балансируют около нулевой прибыльности плюс погрешность. С другой стороны можно сравнить со случайным роботом, который просто будет терять на спреде. Не стоит забывать что игра на бирже — это игра с отрицательной суммой. На другом периоде обучения скорее всего результаты будут иные.

Хэпиэнда не будет

Получилось заставить ГА создавать роботов с определенной задачей. Этот проект расширил мое понимание и экспертизу в описанной выше теме. И тут случилось страшное — цель проекта достигнута. Проект для генерации роботов готов. Эта статья подводит черту по проделанной работе.

Вывод хочу разделить на два пункта

Субъективный — по ходу работы назрело множество вариантов того, что можно было бы проверить в рамках данной системы, для чего она и создавалась. Например:

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

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

И самое главное — я вижу будущее этого проекта в формате песочницы для развития ИИ в области написания алгоритмов.

С удовольствием отвечу на ваши вопросы, предложения и комментарии.

Спасибо за ваше время.