Тестовые функции для оптимизации

Интересное

Введение

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

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

Создание начальной популяции

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

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

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

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

Долгая подготовка тестируемой системы

Вопросы, которые важно задать до внедрения оптимизаций:

  • Долгая относительно чего?
  • Кто занимается этой подготовкой (тестировщики, программисты…)?
  • Сколько раз при желании можно за рабочий день подготовить тестируемую систему? Соответствует ли это число потребностям тестирования?
  • Какой этап в подготовке самый долгий и почему?

Чтобы найти причину этой проблемы, важно задать правильный вопрос.Рассмотрим примеры:

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

Долгий ручной процесс обновления всей системы по разным «виртуалкам» на тестовом стендеПравильный вопрос: в какой момент обновления требуется участие человека, а в какой нет?Решение: автоматизировать процесс выкладки, использовать специальные инструменты деплоя и раскатки сервисов либо отлаженные механизмы релиза на «боевую», но применять их только для деплоя на тестовую.

Долгий процесс «разлития» исходников по «виртуалкам» на тестовом стенде для дальнейшей компиляции и раскаткиВероятная проблема: сетевое взаимодействие.Правильный вопрос: долгий относительно чего (сбора на локальной машине, сбора в локальной сети)?Решение: тестовый стенд и то место, где лежат исходники, должны находиться в одной сети, чтобы минимизировать сетевое взаимодействие.

С этой проблемой я сталкивалась в работе, когда решили сменить тестовую площадку в Екатеринбурге на московскую. И в процессе проб “выкладки” сайта мы быстро заметили, что обновление стенда стало занимать уже не 3 минуты, а почти 15 минут. Причина оказалась в том, что исходный код с большим количеством мелких файлов находился в Екатеринбурге, а стенд в Москве.

Долгий сбор и анализ результатов

Вопросы, которые важно задать до внедрения оптимизаций:

  • Долгий относительно чего?
  • Из каких этапов состоит процесс сбора и анализа результатов? Какой именно этап самый долгий и почему?
  • Кто анализирует результаты?
  • Кто принимает решение о релизе и на основании чего? Сколько тратит времени на принятие решения?

Например:Результаты тестирования оформляются по шаблону, оформление по шаблону отнимает большУю часть времени при тестировании.

Решение (спасибо, Кэп!): отказаться от заполнения результатов по шаблону либо создать более легкий для заполнения шаблон. Потребуется договориться с командой и узнать у тех, кто читает эти результаты (а читают ли их?), действительно ли есть потребность именно в таком шаблоне (риск – писать «в стол» результаты тестирования).

Optlib

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

Optlib — библиотека с открытым кодом, она распространяется под лицензией MIT.

Optlib::genetic

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

Модуль optlib::genetic создан таким образом, чтобы можно было собирать генетический алгоритм «из кубиков». При создании экземпляра структуры, внутри которой будет происходить работа генетического алгоритма, нужно указать, какие алгоритмы будут использоваться для создания популяции, выбора партнеров, скрещивания, мутации, отбора, а также какой критерий используется для прерывания алгоритма.

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

В библиотеке наиболее хорошо проработан случай, когда хромосомы — это вектор дробных чисел, т.е. когда минимизируется функция f(x), где x — это вектор чисел с плавающей точкой (f32 или f64).

Выбор особей для скрещивания

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

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

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

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

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

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

Идея

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

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

На мой взгляд, заставлять машину принимать стратегические решения – это “не самая хорошая мысль”. А выбор параметров (групп параметров) – это стратегия. Считает, торгует, жизнь облегчает – вот пусть этим и занимается, а по каким правилам “железу” работать, решать должен трейдер.

Каждый из этапов и переходы между ними максимально, насколько это представилось возможным, автоматизированы.

Этап 1. Оптимизация. Стандартный вариант, с настройками по желанию пользователя.

Опять-таки, не секрет, но упомянуть об этом необходимо. Генетика, безусловно, штука полезная, но в разумных пределах. Дело в том, что ее алгоритм может сыграть злую шутку – определится какой-то выигрышный, с её точки зрения, набор параметров, и вся дальнейшая оптимизация будет до самого окончания проходить “вокруг него”.

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

– провести оптимизацию не один раз, а два или больше. Первый раз, допустим, по “Balance”, следующий по “Maximal Drawdown” или чему-то еще. Окно “Оптимизируемый параметр” на вкладке “Тестирование” в свойствах эксперта позволяет сделать такой выбор. После этого объединить полученные таблицы результатов и работать уже с объединенной.

– максимально уменьшить количество комбинаций параметров.

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

В свойствах эксперта, на вкладке “Оптимизация” можно выставить различные ограничения, хочу сказать про одно из них: “Максимальная просадка”. При использовании этого параметра нужно помнить, что это просадка в процентах от текущего баланса. Что здесь нужно учесть. Если, к примеру, выставить ограничение 10% и взять начальный баланс 10000, то в процессе оптимизации, когда баланс вырастет хотя бы до 15000, первоначальная 1000 превратится в полторы – согласитесь, это разные цифры.

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

Этап 3. Тест. Выбирается участок истории для тестирования и “прогоняется” автоматический групповой тест “выживших” после отбраковки на предыдущем этапе наборов. Подчеркиваю: групповой. На этом этапе еще нет необходимости рассматривать каждый тест в отдельности, задача стоит в получении результатов тестирования всех оставшихся наборов разом. Фактически, терминал будет проводить ту же оптимизацию, только ему будут “скармливаться” параметры из предварительно записанного файла.

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

Этап 4. Анализ и Отбраковка.

Очевидно, что тесты с отрицательными результатом безжалостно отсекаются (строки удаляются). Вопрос в том, как оценить оставшиеся?

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

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

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

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

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

Завершением 3-го и 4-го этапов будет формирование set-файлов из оставшихся наборов, проведение индивидуальных тестов на любых участках истории, сравнение между собой, выбор и т.д.

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

Оптимизации, применимые ко всем видам тестов

Тестирование включает в себя этапы:

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

Считается, что больше всего времени у тестировщиков отнимает ручная регрессия. Однако, в большинстве случаев это не так. Как минимум, не стоит это утверждать, пока проблема не измерена и не доказана.

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

Отбор

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

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

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

Параллельность тестов

Если одной из проблем тестов является именно время их прохождения, при этом есть вычислительные ресурсы, можно распараллелить и выполнять их в одном из трех режимов параллельности:

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

Перенос существующих тестов и проверок на другой уровень

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

Правильная декомпозиция тестов по уровням “модульные — интеграционные — системные”

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

Правильным будет в данном случае разделить сначала тест на три подсценария: выбор товара, добавление товара в корзину, оформление заказа. Каждый сценарий разделим на более атомарные проверки.Например: “открытие магазина — отображение разных категорий товара для выбора” — один тест; “выбор категории из разных категорий товара” — другой тест.

Применение техник тест-дизайна для оптимизации наборов тест-кейсов

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

Удаление старых тестов

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

Условия окончания алгоритма

Так же как и в других этапах генетического алгоритма, существует несколько критериев окончания алгоритма.

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

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

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

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

Заключение

Изложенный материал не претендует на открытия в области, условно названной: “Теория оптимизации”…. Это чисто практическое руководство, не более того, но и не менее… Наверное, это понятно, но тем не менее, считаю нужным отметить это.Все, что здесь представлено, – это всего лишь инструмент, назначение которого – максимально облегчить труд трейдера. Никто и никогда не даст 100% гарантии того, что за правым краем графика кривая баланса будет такой же “симпатичной”, как и на видимом участке.

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

Есть идея и мысль, что у кого-нибудь возникнет идея и мысль о наиболее оптимальных окнах оптимизации и тестирования…. вдруг 🙂

Удачи и профитов.

P.S. Никогда не думал, что понадобится так много слов для того, чтобы описать пару десятков манипуляций “мышкой”. 🙂

Оцените статью
Obzorka24.ru