Методы оптимизации библиотеки ALGLIB (Часть I)

MetaTrader 5 — Тестер | 25 октября 2024, 15:35

864

Andrey Dik

Содержание

Введение
Методы оптимизации библиотеки ALGLIB:

Введение

В стандартной поставке терминала MetaTrader 5 имеется библиотека ALGLIB, представляющая собой мощный инструмент для численного анализа, который может быть полезен разработчикам торговых систем. Библиотека ALGLIB предлагает пользователю обширный арсенал методов численного анализа, включая:

Линейную алгебру — решение систем линейных уравнений, вычисление собственных значений и векторов, разложение матриц.
Оптимизацию — методы одномерной и многомерной оптимизации.
Интерполяцию и аппроксимацию — полиномиальная и сплайн-интерполяция, аппроксимация функций с использованием методов наименьших квадратов.
Численное интегрирование и дифференцирование — методы интегрирования (трапеции, Симпсона и др.), численное дифференцирование.
Численные методы решения дифференциальных уравнений — обыкновенные дифференциальные уравнения и численные методы.
Статистические методы — оценка параметров, регрессионный анализ, генерация случайных чисел.
Фурье-анализ: быстрое преобразование Фурье.

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

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

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

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

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

Целевая функция (Objective Function или Fitness Function). Это функция, которую необходимо максимизировать или минимизировать. Например, максимизация прибыли или минимизация затрат (прибыль или затраты — критерии оптимизации).
Переменные. Это параметры, которые могут быть изменены для достижения наилучшего результата.
Ограничения. Это условия, которые должны быть соблюдены при поиске оптимального решения.

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

Виды ограничений:

Граничные ограничения (Boundary Constraints или Box Constraints) — ограничения, накладываемые на значения переменных, например, переменная "x" может быть только в диапазоне от 1 до 3.
Линейные ограничения равенства (Linear Equality Constraints) — это условия, при которых выражение с переменными должно быть точно равно какому-то числу. Например, (x + y = 5) — это линейное равенство.
Линейные ограничения неравенства (Linear Inequality Constraints) — условия, при которых выражение с переменными должно быть меньше или равно (или больше или равно) какому-то числу. Например, (x - y >= 1).

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

В качестве примера задачи оптимизации будем использовать простую целевую функцию, которую необходимо максимизировать. Она представляет собой гладкую монотонную функцию с единственным максимумом — перевернутый параболоид. Значения этой функции находятся в диапазоне [0; 1], независимо от количества аргументов, которые принадлежат диапазону [-10; 10].

//——————————————————————————————————————————————————————————————————————————————
//Paraboloid, F(Xn) ∈ [0.0; 1.0], X ∈ [-10.0; 10.0], maximization
double ObjectiveFunction (double &x [])
{
  double sum = 0.0;

  for (int i = 0; i < ArraySize (x); i++)
  {
    if (x [i] < -10.0 || x [i] > 10.0) return 0.0;
    sum += (-x [i] * x [i] + 100.0) * 0.01;
  }
  
  return sum /= ArraySize (x);
}
//——————————————————————————————————————————————————————————————————————————————

BLEIC (Boundary, Linear Equality-Inequality Constraints)

BLEIC (Boundary, Linear Equality-Inequality Constraints), алгоритм активного множества — это название для семейства методов, используемых для решения задач оптимизации с равенствами и неравенствами. Название метода происходит от классификации ограничений, которая делит их на активные в текущей точке и неактивные. Метод сводит задачу с ограничениями в виде равенств и неравенств к последовательности подзадач, ограниченных только равенствами. Активные неравенства рассматриваются как равенства, а неактивные временно игнорируются (хотя мы продолжаем следить за ними). Неофициально говоря, текущая точка перемещается по допустимому множеству, "прилипая" или "отлипая" от границ.

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

Границы значений переменных (например, цена не может быть отрицательной)
Равенства (например, сумма весов в портфеле должна быть равна 100%)
Неравенства (например, риск не должен превышать определенный уровень)

2. Как он работает — использует "ограниченную память" (Limited memory) это значит, что он не хранит все промежуточные вычисления, а только самые важные. Движется к решению постепенно, шаг за шагом:

Оценивает текущее положение
Определяет направление движения
Делает шаг в этом направлении
Проверяет, не нарушаются ли ограничения
Если нужно, корректирует движение

3. Особенности:

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

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

Для использования метода BLEIC и остальных в библиотеке ALGLIB нам понадобится подключить файл (библиотека поставляется вместе с терминалом MetaTrader 5, ничего дополнительно устанавливать пользователю не требуется).

#include <Math\Alglib\alglib.mqh>

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

1. Определим граничные условия задачи, такие как количество запусков фитнес-функции (целевой функции), диапазоны оптимизируемых параметров и их шаг. Для методов ALGLIB необходимо назначить стартовые значения оптимизируемых параметров "x" (методы детерминированные и результаты полностью зависят от начальных значений, поэтому мы применим генерацию случайных чисел в диапазоне параметров задачи), а также масштаб "s" (методы чувствительны к масштабу параметров относительно друг друга, в данном случае устанавливаем масштаб "1").

2. Объявим объекты, необходимые для работы алгоритма.

3. Зададим внешние параметры алгоритма (настройки).

4. Выполним инициализацию алгоритма, передав в метод диапазоны и шаги оптимизируемых параметров, а также внешние параметры алгоритма.

5. Выполним оптимизацию.

6. Получим результаты оптимизации для дальнейшего использования.

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

//——————————————————————————————————————————————————————————————————————————————
void OnStart ()
{
  // Инициализация параметров оптимизации---------------------------------------
  int numbTestFuncRuns = 10000;
  int params           = 1000;

  // Создание и инициализация массивов для границ диапазона---------------------
  double rangeMin [], rangeMax [], rangeStep;
  ArrayResize (rangeMin,  params);
  ArrayResize (rangeMax,  params);

  for (int i = 0; i < params; i++)
  {
    rangeMin  [i] = -10;
    rangeMax  [i] =  10;
  }
  rangeStep =  DBL_EPSILON;

  double x [];
  double s [];
  ArrayResize (x, params);
  ArrayResize (s, params);
  ArrayInitialize (s, 1);

  // Генерация случайных начальных значений параметров в заданных диапазонах----
  for (int i = 0; i < params; i++)
  {
    x [i] = rangeMin [i] + ((rangeMax [i] - rangeMin [i]) * rand () / 32767.0);
  }

  // Создание объектов для оптимизации------------------------------------------
  C_OptimizedFunction  fFunc; fFunc.Init (params, numbTestFuncRuns);
  CObject              obj;
  CNDimensional_Rep    frep;
  CMinBLEICReportShell rep;

  // Установка параметров алгоритма оптимизации BLEIC---------------------------
  double diffStep = 0.00001;
  double epsg     = 1e-16;
  double epsf     = 1e-16;
  double epsi     = 0.00001;

  CAlglib::MinBLEICCreateF      (x, diffStep, fFunc.state);
  CAlglib::MinBLEICSetBC        (fFunc.state, rangeMin, rangeMax);
  CAlglib::MinBLEICSetInnerCond (fFunc.state, epsg, epsf, rangeStep);
  CAlglib::MinBLEICSetOuterCond (fFunc.state, rangeStep, epsi);
  CAlglib::MinBLEICOptimize     (fFunc.state, fFunc, frep, 0, obj);
  CAlglib::MinBLEICResults      (fFunc.state, x, rep);

  // Вывод результатов оптимизации-----------------------------------------------
  Print ("BLEIC, best result: ", fFunc.fB, ", number of function launches: ", fFunc.numberLaunches);
}
//——————————————————————————————————————————————————————————————————————————————

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

1. Func () — это виртуальный метод, который переопределяется в производных классах.
2. Init () — инициализирует параметры класса. Внутри метода:

Инициализируются переменные, связанные с количеством запусков и лучшим найденным значением функции.
Резервируются массивы "c" и "cB" для хранения координат.

Переменные:

state — объект типа CMinBLEICStateShell, характерный именно для метода BLEIC, используется при вызове статических методов алгоритма и вызова метода останова.
numberLaunches — текущее количество запусков (необходимо для предотвращения бесконтрольного или слишком долгого выполнения фитнес-функции).
maxNumbLaunchesAllowed — максимальное допустимое количество запусков.
fB — лучшее найденное значение фитнес-функции.
c [] — массив текущих координат.
cB [] — массив для хранения лучших координат поиска.

//——————————————————————————————————————————————————————————————————————————————
// Класс для оптимизации функции, наследуется от CNDimensional_Func
class C_OptimizedFunction : public CNDimensional_Func
{
  public:
  C_OptimizedFunction (void) { }
  ~C_OptimizedFunction (void) { }

  // Виртуальная функция, которая будет содержать оптимизируемую функцию--------
  virtual void Func (CRowDouble &x, double &func, CObject &obj);

  // Инициализация параметров оптимизации---------------------------------------
  void Init (int coords,
             int maxNumberLaunchesAllowed)
  {
    numberLaunches         = 0;
    maxNumbLaunchesAllowed = maxNumberLaunchesAllowed;
    fB = -DBL_MAX;

    ArrayResize (c,  coords);
    ArrayResize (cB, coords);
  }

  //----------------------------------------------------------------------------
  CMinBLEICStateShell state;          // Состояние 
  int                 numberLaunches; // Счетчик запусков 

  double fB;                          // Лучшее найденное значение целевой функции (максимум)
  double cB [];                       // Координаты точки с лучшим значением функции

  private: //-------------------------------------------------------------------
  double c  [];                       // Массив для хранения текущих координат
  int    maxNumbLaunchesAllowed;      // Максимально допустимое число вызовов функции
};
//——————————————————————————————————————————————————————————————————————————————

Метод "Func" класса "C_OptimizedFunction" предназначен для обращения к фитнес-функции пользователя. Он принимает в качестве аргументов вектор "x" (один из вариантов оптимизируемых параметров задачи, предлагаемых методом оптимизации), аргумент "func", в который необходимо вернуть вычисленное значение фитнес-функции, и объект "obj" (предназначение которого для меня неясно, возможно зарезервировано для возможности передачи дополнительной информации в/из метода). Основные этапы выполнения метода:

1. Увеличивается счетчик "numberLaunches", который отслеживает количество вызовов метода "Func".
2. Если количество запусков превышает допустимое значение "maxNumbLaunchesAllowed", функция устанавливает значение "func" в "DBL_MAX" (максимальное значение типа "double", методы ALGLIB предназначены для минимизации функций, это значение означает наихудшее возможное решение). Затем вызывается функция "MinBLEICRequestTermination", которая предназначена сигнализировать методу BLEIC о необходимости остановить процесс оптимизации.
3. Далее в цикле происходит копирование значений из вектора "x" в массив "c". Это необходимо, чтобы использовать эти значения для передачи в фитнес-функцию пользователя.
4. Вызывается функция "ObjectiveFunction", которая вычисляет значение целевой функции для текущих значений в массиве "c". Результат сохраняется в "ffVal", и значение "func" устанавливается в отрицательное значение "ffVal" (мы оптимизируем перевернутый параболоид, который необходимо максимизировать, а BLEIC минимизирует функцию, поэтому значение переворачиваем).
5. Если текущее значение "ffVal" больше, чем предыдущее лучшее значение "fB", то "fB" обновляется, и массив "cB" копирует текущее состояние "c". Это позволяет отслеживать лучшее найденное значение целевой функции с соответствующими параметрами и позволяет обращаться к ним позднее при необходимости.

Функция "Func" реализует вызов пользовательской фитнес-функции и отслеживает количество ее запусков, обновляет наилучшие результаты. Она также управляет условиями остановки, если количество запусков превышает установленный предел.

//——————————————————————————————————————————————————————————————————————————————
// Реализация оптимизируемой функции
void C_OptimizedFunction::Func (CRowDouble &x, double &func, CObject &obj)
{
  // Увеличение счетчика запусков функции и контроль ограничений----------------
  numberLaunches++;
  if (numberLaunches >= maxNumbLaunchesAllowed)
  {
    func = DBL_MAX;
    CAlglib::MinBLEICRequestTermination (state);
    return;
  }
  
  // Копирование входных координат во внутренний массив-------------------------
  for (int i = 0; i < x.Size (); i++) c [i] = x [i];

  // Вычисление значения целевой функции----------------------------------------
  double ffVal = ObjectiveFunction (c);
  func = -ffVal;

  // Обновление лучшего найденного решения--------------------------------------
  if (ffVal > fB)
  {
    fB = ffVal;
    ArrayCopy (cB, c);
  }
}
//——————————————————————————————————————————————————————————————————————————————

После запуска тестового скрипта с алгоритмом BLEIC для оптимизации функции параболоида, получим в принт такой результат:

BLEIC, best result: 0.6861786206145579, number of function launches: 84022

Стоит отметить, что, несмотря на запросы остановить оптимизацию с помощью метода "MinBLEICRequestTermination", алгоритм продолжал процесс и пытался обратиться к фитнес-функции еще 74 022 раза, превысив лимит в 10 000 запусков.

Теперь попробуем не сдерживать BLEIC и дадим ему возможность действовать по своему усмотрению. Результаты получились следующие:

BLEIC, best result: 1.0, number of function launches: 72017

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

В алгоритме важен шаг дифференцирования. Так, если использовать очень маленький шаг, например 1e-16 вместо 0.00001, то алгоритм преждевременно останавливается, по сути - застревает, с таким результатом:

BLEIC, best result: 0.6615878186651468, number of function launches: 4002

L-BFGS (Limited-memory Broyden–Fletcher–Goldfarb–Shanno)

Алгоритм L-BFGS (Limited-memory Broyden–Fletcher–Goldfarb–Shanno) представляет собой эффективный метод оптимизации, специально разработанный для решения задач большой размерности, где количество переменных превышает 1 000. Он относится к квазиньютоновским методам и использует ограниченную память для хранения информации о кривизне функции, что позволяет избежать необходимости явного хранения и вычисления полной матрицы Гессе.

Принцип работы алгоритма заключается в том, что он строит и уточняет квадратичную модель оптимизируемой функции, используя последние M пар значений и градиентов. Обычно M составляет умеренное число, от 3 до 10, что значительно снижает вычислительные затраты до O(N·M) операций. На каждой итерации алгоритм вычисляет градиент в текущей точке, определяет направление поиска с использованием сохраненных векторов и выполняет линейный поиск для определения длины шага. Если шаг квазиньютоновского метода не приводит к достаточному уменьшению значения функции или градиента, происходит повторная корректировка направления.

Основной особенностью L-BFGS является положительная определённость приближённого Гессиана, что гарантирует, что направление квазиньютоновского метода всегда будет направлением спуска, независимо от кривизны функции.

Простыми словами как работает LBFGS:

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

2. Как он это делает: запоминает последние M шагов (обычно 310 шагов) и на каждом шаге сохраняет две вещи:

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

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

3. Особенности: всегда движется "вниз" (в сторону уменьшения значения функции), экономно использует память (хранит только последние M шагов) и работает быстро (затраты пропорциональны размеру задачи × M).

4. Практический пример. Представьте, что вы спускаетесь с горы в тумане:

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

5. Ограничения:

для очень сложных "ландшафтов" может работать медленнее
может требовать дополнительной настройки для улучшения работы

В отличие от метода BLEIC, в L-BFGS есть возможность прямо указать методу ограничение на количество запусков целевой функции, но нет возможности указать граничные условия для оптимизируемых параметров. Значение M в примере ниже установлено "1", использование других значений не привело к заметным изменениям результативности и в поведении алгоритма.

//——————————————————————————————————————————————————————————————————————————————
void OnStart ()
{
  // Инициализация параметров оптимизации---------------------------------------
  int numbTestFuncRuns = 10000;
  int params           = 1000;

  // Создание и инициализация массивов для границ диапазона поиска--------------
  double rangeMin [], rangeMax [], rangeStep;
  ArrayResize (rangeMin,  params);
  ArrayResize (rangeMax,  params);

  for (int i = 0; i < params; i++)
  {
    rangeMin  [i] = -10;
    rangeMax  [i] =  10;
  }
  rangeStep =  DBL_EPSILON;

  double x [];
  double s [];
  ArrayResize (x, params);
  ArrayResize (s, params);
  ArrayInitialize (s, 1);

  // Генерация случайных начальных значений параметров в заданных диапазонах-----
  for (int i = 0; i < params; i++)
  {
    x [i] = rangeMin [i] + ((rangeMax [i] - rangeMin [i]) * rand () / 32767.0);
  }

  // Создание объектов для оптимизации-------------------------------------------
  C_OptimizedFunction  fFunc; fFunc.Init (params, numbTestFuncRuns);
  CObject              obj;
  CNDimensional_Rep    frep;
  CMinLBFGSReportShell rep;

  // Установка параметров алгоритма оптимизации L-BFGS---------------------------
  double diffStep = 0.00001;
  double epsg     = 1e-16;
  double epsf     = 1e-16;

  CAlglib::MinLBFGSCreateF  (1, x, diffStep, fFunc.state);
  CAlglib::MinLBFGSSetCond  (fFunc.state, epsg, epsf, rangeStep, numbTestFuncRuns);
  CAlglib::MinLBFGSSetScale (fFunc.state, s);
  CAlglib::MinLBFGSOptimize (fFunc.state, fFunc, frep, 0, obj);
  CAlglib::MinLBFGSResults  (fFunc.state, x, rep);

  //----------------------------------------------------------------------------
  Print ("L-BFGS, best result: ", fFunc.fB, ", number of function launches: ", fFunc.numberLaunches);
}
//——————————————————————————————————————————————————————————————————————————————

В L-BFGS тип переменной "state" задаём "CMinLBFGSStateShell".

//——————————————————————————————————————————————————————————————————————————————
// Класс для оптимизации функции, наследуется от CNDimensional_Func
class C_OptimizedFunction : public CNDimensional_Func
{
  public: //--------------------------------------------------------------------
  C_OptimizedFunction (void) { }
  ~C_OptimizedFunction (void) { }

  // Виртуальная функция, которая будет содержать оптимизируемую функцию---------
  virtual void Func (CRowDouble &x, double &func, CObject &obj);

  // Инициализация параметров оптимизации----------------------------------------
  void Init (int coords,
             int maxNumberLaunchesAllowed)
  {
    numberLaunches         = 0;
    maxNumbLaunchesAllowed = maxNumberLaunchesAllowed;
    fB = -DBL_MAX;

    ArrayResize (c,  coords);
    ArrayResize (cB, coords);
  }

  //----------------------------------------------------------------------------
  CMinLBFGSStateShell state;          // Состояние 
  int                 numberLaunches; // Счетчик запусков

  double fB;                          // Лучшее найденное значение целевой функции (максимум)
  double cB [];                       // Координаты точки с лучшим значением функции

  private: //-------------------------------------------------------------------
  double c  [];                       // Массив для хранения текущих координат
  int    maxNumbLaunchesAllowed;      // Максимально допустимое число вызовов функции
};
//——————————————————————————————————————————————————————————————————————————————

Остановку процесса оптимизации запрашиваем командой "MinLBFGSRequestTermination".

//——————————————————————————————————————————————————————————————————————————————
// Реализация оптимизируемой функции
void C_OptimizedFunction::Func (CRowDouble &x, double &func, CObject &obj)
{
  //Увеличение счетчика запусков функции контроль ограничений-------------------
  numberLaunches++;
  if (numberLaunches >= maxNumbLaunchesAllowed)
  {
    func = DBL_MAX;
    CAlglib::MinLBFGSRequestTermination (state);
    return;
  }

  // Копирование входных координат во внутренний массив-------------------------
  for (int i = 0; i < x.Size (); i++) c [i] = x [i];

  // Вычисление значения целевой функции----------------------------------------
  double ffVal = ObjectiveFunction (c);
  func = -ffVal;

  // Обновление лучшего найденного решения--------------------------------------
  if (ffVal > fB)
  {
    fB = ffVal;
    ArrayCopy (cB, c);
  }
}
//——————————————————————————————————————————————————————————————————————————————

После запуска тестового скрипта с алгоритмом L-BFGS для оптимизации функции параболоида, получим в принт такой результат:

L-BFGS, best result: 0.6743844728276278, number of function launches: 24006

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

Теперь попробуем не ограничивать L-BFGS и позволим ему выполнить оптимизацию без ограничений на количество запусков:

L-BFGS, best result: 1.0, number of function launches: 52013

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

Для L-BFGS так же важен шаг дифференцирования. Если использовать очень маленький шаг 1e-16, то алгоритм преждевременно останавливается — застревает, с таким результатом:

L-BFGS, best result: 0.6746423814003036, number of function launches: 4001

NS (Nonsmooth Nonconvex Optimization Subject to box / linear / nonlinear - Nonsmooth Constraints)

NS (Nonsmooth Nonconvex Optimization Subject to box/linear/nonlinear - Nonsmooth Constraints) — алгоритм не гладкой не выпуклой оптимизации предназначен для решения задач, где целевая функция не является гладкой и выпуклой. Это означает, что функция может иметь резкие изменения, углы или другие особенности. Основные характеристики таких задач заключаются в том, что целевая функция может содержать точки разрывов или резкие изменения, затрудняющие анализ с помощью методов, основанных на вычислении градиента.

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

Простым языком разберемся, что означает это описание оптимизации:

1. NONSMOOTH (Негладкая оптимизация):

Функция может иметь разрывы или "изломы"
Нет требования непрерывной дифференцируемости
Могут быть резкие переходы и скачки

2. NONCONVEX (Невыпуклая):

Функция может иметь несколько локальных минимумов и максимумов
"Ландшафт" функции может быть сложным, с "холмами" и "впадинами"

3. Типы ограничений (CONSTRAINTS): BOX (Коробочные), LINEAR (Линейные), NONLINEAR-NONSMOOTH (Нелинейные негладкие) мы описывали выше.

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

Самое важное ограничение решателя AGS заключается в том, что он не предназначен для задач высокой размерности. Один шаг AGS требует примерно 2·N оценок градиента в случайно выбранных точках (для сравнения — L-BFGS требует O(1) оценок за шаг). Обычно вам потребуется O(N) итераций для сходимости, что приводит к O(N²) оценкам градиента за сессию оптимизации.

В отличие от предыдущих методов, NS требует использования не типа "double" для переменных граничных условий и начальных значений оптимизируемых параметров задачи, а тип "CRowDouble". Дополнительно требуется задать параметры решателю AGS.

//——————————————————————————————————————————————————————————————————————————————
void OnStart ()
{
  // Инициализация параметров оптимизации---------------------------------------
  int numbTestFuncRuns = 10000;
  int params           = 1000;

  // Создание и инициализация массивов для границ диапазона поиска--------------
  CRowDouble rangeMin, rangeMax;
  rangeMin.Resize (params);
  rangeMax.Resize (params);
  double rangeStep;

  for (int i = 0; i < params; i++)
  {
    rangeMin.Set (i, -10);
    rangeMax.Set (i,  10);
  }
  rangeStep = DBL_EPSILON;

  CRowDouble x, s; 
  x.Resize (params);
  s.Resize (params);
  s.Fill (1);

  // Генерация случайных начальных значений параметров в заданных диапазонах----
  for (int i = 0; i < params; i++)
  {
    x.Set (i, rangeMin [i] + ((rangeMax [i] - rangeMin [i]) * rand () / 32767.0));
  }

  // Создание объектов для оптимизации------------------------------------------
  C_OptimizedFunction fFunc; fFunc.Init (params, numbTestFuncRuns);
  CObject             obj;
  CNDimensional_Rep   frep;
  CMinNSReport        rep;
  
  // Установка параметров алгоритма оптимизации NS------------------------------
  double diffStep = 0.00001;
  double radius   = 0.8;
  double rho      = 50.0;

  CAlglib::MinNSCreateF    (x, diffStep, fFunc.state);
  CAlglib::MinNSSetBC      (fFunc.state, rangeMin, rangeMax);
  CAlglib::MinNSSetScale   (fFunc.state, s);
  CAlglib::MinNSSetCond    (fFunc.state, rangeStep, numbTestFuncRuns);

  CAlglib::MinNSSetAlgoAGS (fFunc.state, radius, rho);

  CAlglib::MinNSOptimize   (fFunc.state, fFunc, frep, obj);
  CAlglib::MinNSResults    (fFunc.state, x, rep);

  // Вывод результатов оптимизации-----------------------------------------------
  Print ("NS, best result: ", fFunc.fB, ", number of function launches: ", fFunc.numberLaunches);
}
//——————————————————————————————————————————————————————————————————————————————

Для метода NS необходимо создать класс-обертку, теперь унаследованный от другого родительского класса — "CNDimensional_FVec". Также потребуется изменить виртуальный метод на "FVec". Особенностью метода оказался тот факт, что возвращать значение фитнес-функции равным "DBL_MAX" нельзя, так как в этом случае метод завершится с ошибкой, в отличие от предыдущих методов оптимизации. Поэтому мы добавим дополнительное поле в класс — "fW", чтобы отслеживать наихудшее решение в процессе оптимизации.

//——————————————————————————————————————————————————————————————————————————————
// Класс для оптимизации функции, наследуется от CNDimensional_FVec
class C_OptimizedFunction : public CNDimensional_FVec
{
  public: //--------------------------------------------------------------------
  C_OptimizedFunction (void) { }
  ~C_OptimizedFunction (void) { }

  // Виртуальная функция, которая будет содержать оптимизируемую функцию--------
  virtual void FVec (CRowDouble &x, CRowDouble &fi, CObject &obj);

  // Инициализация параметров оптимизации---------------------------------------
  void Init (int coords,
             int maxNumberLaunchesAllowed)
  {
    numberLaunches         = 0;
    maxNumbLaunchesAllowed = maxNumberLaunchesAllowed;
    fB = -DBL_MAX;
    fW =  DBL_MAX;

    ArrayResize (c,  coords);
    ArrayResize (cB, coords);
  }

  //----------------------------------------------------------------------------
  CMinNSState state;             // Состояние 
  int         numberLaunches;    // Счетчик запусков

  double fB;                     // Лучшее найденное значение целевой функции (максимум)
  double fW;                     // Худшее найденное значение целевой функции (максимум)
  double cB [];                  // Координаты точки с лучшим значением функции

  private: //-------------------------------------------------------------------
  double c  [];                  // Массив для хранения текущих координат
  int    maxNumbLaunchesAllowed; // Максимально допустимое число вызовов функции
};
//——————————————————————————————————————————————————————————————————————————————

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

//——————————————————————————————————————————————————————————————————————————————
void C_OptimizedFunction::FVec (CRowDouble &x, CRowDouble &fi, CObject &obj)
{
  // Увеличение счетчика запусков функции и контроль ограничений----------------
  numberLaunches++;
  if (numberLaunches >= maxNumbLaunchesAllowed)
  {
    //fi.Set (0, DBL_MAX);  //Нельзя возвращать значение DBL_MAX
    fi.Set (0, -fW);
    CAlglib::MinNSRequestTermination (state);
    return;
  }

  // Копирование входных координат во внутренний массив-------------------------
  for (int i = 0; i < x.Size (); i++) c [i] = x [i];

  // Вычисление значения целевой функции----------------------------------------
  double ffVal = ObjectiveFunction (c);
  fi.Set (0, -ffVal);

  // Обновление лучшего и худшего найденных решений-----------------------------
  if (ffVal < fW) fW = ffVal;
  if (ffVal > fB)
  {
    fB = ffVal;
    ArrayCopy (cB, c);
  }
}
//——————————————————————————————————————————————————————————————————————————————

После запуска тестового скрипта с алгоритмом NS для оптимизации функции параболоида, получим в принт такой результат:

NS, best result: 0.6605212238333136, number of function launches: 1006503

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

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

Нет результата

Для NS так же важен шаг дифференцирования. Если использовать очень маленький шаг 1e-16, то алгоритм преждевременно останавливается — застревает, не использовав выделенное для его работы количество запусков целевой функции, с таким результатом:

NS, best result: 0.6784901840822722, number of function launches: 96378

Заключение

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

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

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

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

Программы, используемые в статье

#	Имя	Тип	Описание
1	Simple test ALGLIB BLEIC.mq5	Скрипт	Тестовый скрипт для работы с BLEIC
2	Simple test ALGLIB LBFGS.mq5	Скрипт	Тестовый скрипт для работы с L-BFGS
3	Simple test ALGLIB NS.mq5	Скрипт	Тестовый скрипт для работы с NS

Прикрепленные файлы |

Загрузить ZIP

ALGLIB_optimization_methods.zip (4.36 KB)

Предупреждение: все права на данные материалы принадлежат MetaQuotes Ltd. Полная или частичная перепечатка запрещена.

Другие статьи автора

Последние комментарии | Перейти к обсуждению на форуме трейдеров (1)

Rorschach | 25 окт. 2024 в 18:03

Спасибо, интересно.

Разработка системы репликации (Часть 54): Появление первого модуля

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

Упрощаем торговлю на новостях (Часть 2): Управляем рисками

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

Нейросети в трейдинге: Адаптивное представление графов (NAFS)

Предлагаем познакомиться с методом NAFS (Node-Adaptive Feature Smoothing) — это непараметрический подход к созданию представлений узлов, который не требует обучения параметров. NAFS извлекает характеристики каждого узла, учитывая его соседей, и затем адаптивно комбинирует эти характеристики для формирования конечного представления.

Разрабатываем мультивалютный советник (Часть 19): Создаём этапы, реализованные на Python

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