preview
Алгоритм оптимизации леса — Forest Optimization Algorithm (FOA)

Алгоритм оптимизации леса — Forest Optimization Algorithm (FOA)

MetaTrader 5 — Трейдинг |
31 0
Andrey Dik
Andrey Dik

Содержание

  1. Введение
  2. Реализация алгоритма
  3. Результаты тестов
  4. Выводы


Введение

Алгоритм оптимизации леса Forest Optimization Algorithm, FOA относится к простым. В нем всего два способа получить новое решение: слегка сдвинуть один параметр у хорошего решения или заменить несколько параметров случайными значениями. Всё остальное сводится к учёту возраста решений и отбору лучших.

Задачи, в которых трейдеру нужен такой алгоритм:

• подбор параметров советника по пользовательскому критерию, когда прогонов в тестере мало;
• подбор параметров индикаторов и фильтров сигнала;
• подбор весов инструментов или стратегий в портфеле;

• повторная оптимизация на скользящем окне, где важна скорость получения приемлемого решения.

Алгоритм предложили Manizheh Ghaemi и Mohammad-Reza Feizi-Derakhshi в 2014 году. Идея взята из жизни леса. Большинство деревьев живёт ограниченный срок. Отдельные деревья стоят десятилетиями, потому что выросли в удачном месте. Семена распространяются двумя путями: падают под дерево или уносятся далеко ветром и животными. Алгоритм ищет долгожителей, то есть лучшие решения, и использует оба пути посева.

В статье мы пройдём следующий путь. Сначала разберём алгоритм на простых примерах. Затем перенесём его в класс C_AO_FOA и и объясним решения, принятые при адаптации к тестовому стенду. В конце проверим алгоритм на функциях Hilly, Forest и Megacity и выясним, для задач каких размерностей он годится.


Реализация алгоритма

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

Возраст нужен для одного правила. Сеять под собой может только дерево возраста 0, то есть появившееся на прошлом круге. Правило не даёт одним и тем же решениям топтаться на месте: посеяв один раз, дерево уступает очередь своим потомкам.

Один круг алгоритма состоит из пяти шагов.

  1. Локальный посев. Каждое дерево возраста 0 роняет под себя несколько семян. Семя является копией родителя, у которой сдвинута одна случайная координата.
  2. Старение. Возраст всех деревьев, кроме только что посеянных, увеличивается на единицу.
  3. Ограничение популяции. Деревья, дожившие до предельного возраста, удаляются из леса. Оставшиеся сортируются по приспособленности. Всё, что не помещается в лимит леса, тоже удаляется. Удалённые деревья не пропадают, а попадают в список кандидатов.
  4. Глобальный посев. Небольшая доля кандидатов возвращается в лес. У каждого такого дерева несколько координат заменяются случайными значениями из всего диапазона.
  5. Обновление лучшего. Возраст лучшего дерева сбрасывается в 0. Поэтому оно не стареет и сеет на каждом круге.

FOA_cycle

Рисунок 1. Один круг алгоритма FOA

Разберём оба посева на числах. Пусть у дерева четыре координаты, каждая в диапазоне от 0 до 10.

Локальный посев. Родитель: [3.0, 7.0, 1.5, 9.0]. Случайно выбрана вторая координата. К ней прибавляется случайное число r из отрезка [-dx, dx]. При r = -1.2 получаем потомка [3.0, 5.8, 1.5, 9.0]. Остальные три координаты не изменились. Если результат выходит за границу диапазона, он обрезается по границе.

Глобальный посев. Кандидат: [3.0, 7.0, 1.5, 9.0]. Случайно выбрана четвёртая координата. Она заменяется случайным числом из всего диапазона, например 0.6. Новое дерево: [3.0, 7.0, 1.5, 0.6]. Это уже не сдвиг, а прыжок: новое значение не связано со старым.

FOA_seeding

Рисунок 2. Локальный и глобальный посев на одном дереве

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

Теперь проследим возраст. Возьмём лес с лимитом в три дерева и по одному семени на дерево.

Момент

Деревья и возраст

Что произошло

Старт

A(0), B(0), C(0)

случайный лес

Круг 1, посев

A(1), B(1), C(1), a(0), b(0), c(0)

каждое дерево дало семя и постарело

Круг 1, отбор

a(0), A(1), c(0)

остались три лучших; B, C, b ушли в кандидаты

Круг 1, лучший

a(0), A(1), c(0)

лучшее дерево a получает возраст 0

Круг 2, посев

a(1), A(2), c(1), a'(0), c'(0)

сеют только a и c; дерево A больше не сеет

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

Параметры алгоритма:

Параметр

Смысл

Что происходит при увеличении

areaLimit

сколько деревьев помещается в лесу

больше разнообразия, медленнее уточнение

lifeTime

предельный возраст дерева

старые решения держатся дольше

transferRate

доля кандидатов для глобального посева

больше случайных прыжков

LSC

число семян, которые дерево роняет под себя

тщательнее поиск рядом, дороже круг

GSC

число координат, заменяемых при глобальном посеве

прыжок уходит дальше от исходного дерева

dx

наибольший сдвиг координаты при локальном посеве

шаг крупнее и грубее

Авторы рекомендуют задавать LSC как 20% от числа координат, а GSC как 10%.

Псевдокод записан для максимизации, как принято на нашем стенде. В оригинале задача решается на минимум, отличие только в направлении сортировки.

ПАРАМЕТРЫ: areaLimit, lifeTime, transferRate, LSC, GSC, dx
ДЕРЕВО:    x[D], f, age

ИНИЦИАЛИЗАЦИЯ
  лес = areaLimit деревьев: x[d] случайно в [min[d], max[d]], age = 0
  вычислить f для каждого дерева

ЦИКЛ, пока не исчерпан бюджет вычислений

  1. ЛОКАЛЬНЫЙ ПОСЕВ
     для каждого дерева t с age = 0:
        повторить LSC раз:
           s = копия t
           d = случайная координата
           s.x[d] = s.x[d] + случайное из [-dx[d], dx[d]]
           обрезать s.x[d] по границам [min[d], max[d]]
           вычислить s.f;  s.age = 0
           запомнить s как новое дерево

  2. СТАРЕНИЕ
     для каждого дерева леса: age = age + 1
     добавить новые деревья в лес

  3. ОГРАНИЧЕНИЕ ПОПУЛЯЦИИ
     кандидаты = деревья с age >= lifeTime (убрать из леса)
     отсортировать лес по убыванию f
     если в лесу больше areaLimit деревьев:
        лишние дописать в конец списка кандидатов и убрать из леса

  4. ГЛОБАЛЬНЫЙ ПОСЕВ
     n = целая часть (число кандидатов * transferRate)
     для первых n кандидатов:
        s = копия кандидата
        повторить GSC раз:
           d = случайная координата
           s.x[d] = случайное в [min[d], max[d]]
        вычислить s.f;  s.age = 0
        добавить s в лес

  5. ОБНОВЛЕНИЕ ЛУЧШЕГО
     лучшее дерево леса: age = 0

Формулы двух посевов в отдельной записи:

локальный посев:   x_new[d] = x[d] + r,   r равномерно в [-dx[d], dx[d]]
глобальный посев:  x_new[d] = min[d] + u * (max[d] - min[d]),   u равномерно в [0, 1]
число деревьев глобального посева:  n = floor(число кандидатов * transferRate)

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

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

Место

В авторском решении

В нашей реализации

Координаты глобального посева

один набор на все деревья круга

свой набор у каждого дерева

Число координат GSC

целая часть от 10% размерности, при 5–9 координатах получается 0

не меньше 1

Радиус dx

модуль верхней границы, делённый на 5

доля ширины диапазона по каждой координате

Первое исправление следует описанию оператора: координаты выбираются у конкретного дерева. Второе устраняет ошибку: при нуле заменяемых координат глобальный посев просто копирует кандидата. Третье делает шаг независимым от положения диапазона. При диапазоне от 0 до 10 авторская формула даёт шаг 2, а при диапазоне от -10 до 0 даёт 0. Для симметричного диапазона обе записи совпадают при доле 0.1.

Перенос на тестовый стенд. Стенд выдаёт алгоритму одинаковую порцию вычислений фитнес-функции на каждой эпохе. Круг FOA создаёт переменное число новых деревьев. Это расхождение потребовало четырёх решений.

1.  Параметр popSize означает размер порции, а не размер популяции. Круг алгоритма может занимать несколько эпох. Следующий круг начинается, когда оценены все деревья текущего.
2.  Деревья глобального посева и локальные потомки следующего круга оцениваются вместе. Координаты глобальных деревьев известны сразу, поэтому они могут сеять до оценки. Так на один круг приходится одна очередь на оценку вместо двух.
3.  Остаток последней порции круга заполняется дополнительными локальными потомками. Родители берутся по кругу, начиная с лучшего. Лишних потомков получается не больше popSize - 1 на круг.
4.  Начальный лес округляется вверх до целого числа порций. Лишние деревья уходят в кандидаты на первом же отборе.

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

Класс C_AO_FOA. Дерево удобно описать специальной структурой S_FOA_Tree, в которой присутсвтуют координаты, приспособленность и возраст. Структура S_FOA_Pop оборачивает массив деревьев, чтобы лес можно было держать в двух буферах. Класс C_AO_FOA наследуется от C_AO. В конструкторе заданы параметры, подобранные в тестах. Параметры LSC и GSC задаются долями размерности: lscRatio и gscRatio. Радиус локального посева задаётся долей диапазона dxRatio.

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

//+------------------------------------------------------------------+
//| дерево                                                           |
//+------------------------------------------------------------------+
struct S_FOA_Tree
  {
   double            c [];   // координаты
   double            f;      // приспособленность
   int               age;    // возраст
  };

//+------------------------------------------------------------------+
//| лес                                                              |
//+------------------------------------------------------------------+
struct S_FOA_Pop
  {
   S_FOA_Tree        t [];
  };

//+------------------------------------------------------------------+
//| FOA                                                              |
//+------------------------------------------------------------------+
class C_AO_FOA : public C_AO
  {
public:
                    ~C_AO_FOA() {}
                     C_AO_FOA()
     {
      ao_name = "FOA";
      ao_desc = "Forest Optimization Algorithm";
      ao_link = "https://www.mql5.com/ru/articles/25876"; // ссылка на статью

      popSize      = 10;     // порция вычислений ФФ за эпоху
      areaLimit    = 20;     // предел размера леса
      lifeTime     = 30;     // предельный возраст дерева
      transferRate = 0.15;   // доля кандидатов для глобального посева
      lscRatio     = 0.0;    // LSC как доля размерности
      gscRatio     = 0.01;   // GSC как доля размерности
      dxRatio      = 0.4;    // радиус локального посева как доля диапазона

      ArrayResize(params, 7);
      params [0].name = "popSize";
      params [0].val = popSize;
      params [1].name = "areaLimit";
      params [1].val = areaLimit;
      params [2].name = "lifeTime";
      params [2].val = lifeTime;
      params [3].name = "transferRate";
      params [3].val = transferRate;
      params [4].name = "lscRatio";
      params [4].val = lscRatio;
      params [5].name = "gscRatio";
      params [5].val = gscRatio;
      params [6].name = "dxRatio";
      params [6].val = dxRatio;
     }

   void               SetParams()
     {
      popSize      = (int)params [0].val;
      areaLimit    = (int)params [1].val;
      lifeTime     = (int)params [2].val;
      transferRate = params [3].val;
      lscRatio     = params [4].val;
      gscRatio     = params [5].val;
      dxRatio      = params [6].val;

      if(popSize < 1)
         popSize = 1;
      if(areaLimit < 1)
         areaLimit = 1;
      if(lifeTime < 1)
         lifeTime = 1;
      if(transferRate < 0.0)
         transferRate = 0.0;
      if(transferRate > 1.0)
         transferRate = 1.0;
      if(lscRatio < 0.0)
         lscRatio = 0.0;
      if(gscRatio < 0.0)
         gscRatio = 0.0;
      if(gscRatio > 1.0)
         gscRatio = 1.0;
      if(dxRatio < 0.0)
         dxRatio = 0.0;
      if(dxRatio > 1.0)
         dxRatio = 1.0;

      params [0].val = popSize;
      params [1].val = areaLimit;
      params [2].val = lifeTime;
      params [3].val = transferRate;
      params [4].val = lscRatio;
      params [5].val = gscRatio;
      params [6].val = dxRatio;
     }

   bool               Init(const double &rangeMinP  [],
                           const double &rangeMaxP  [],
                           const double &rangeStepP [],
                           const int     epochsP = 0);

   void               Moving();
   void               Revision();

   //----------------------------------------------------------------
   int                areaLimit;
   int                lifeTime;
   double             transferRate;
   double             lscRatio;
   double             gscRatio;
   double             dxRatio;

   int                iterations;   // число завершённых итераций FOA за прогон

private:
   S_FOA_Pop          buf [2];      // лес: текущий буфер и буфер для пересборки
   int                cur;
   int                fN;           // число оценённых деревьев леса в buf [cur]

   int                LSC;          // локальных потомков на дерево
   int                GSC;          // заменяемых координат при глобальном посеве
   double             dx [];        // радиус локального посева по координатам

   //--- текущая итерация: деревья лежат в buf [cur].t [fN + g]
   bool               batchOpen;
   int                bSeeds;       // готовые деревья в начале итерации (глобальный посев / начальный лес)
   int                bLocal;       // локальных потомков по канону: pN * LSC
   int                bTotal;       // всего вычислений в итерации, кратно popSize
   int                bDone;        // уже оценено
   int                par [];       // индексы родителей локального посева
   int                pN;

   double             srt [][2];    // сортировка: [f, индекс]
   int                cand [];      // кандидаты (индексы)

   void               Reserve(int b, int size);
   void               CopyTree(S_FOA_Tree &dst, const S_FOA_Tree &src);
   void               InitBatch();
   void               NextBatch();
  };

Метод Init переводит доли в числа. LSC и GSC не могут быть меньше 1, поэтому lscRatio = 0 означает одно семя на дерево. Радиус dx считается отдельно для каждой координаты. Затем создаётся начальный лес.

//+------------------------------------------------------------------+
//|                              Init                                |
//+------------------------------------------------------------------+
bool C_AO_FOA::Init(const double &rangeMinP  [],
                    const double &rangeMaxP  [],
                    const double &rangeStepP [],
                    const int     epochsP = 0)
  {
   if(!StandardInit(rangeMinP, rangeMaxP, rangeStepP))
      return false;

   LSC = (int)MathFloor(lscRatio * coords);
   if(LSC < 1)
      LSC = 1;
   GSC = (int)MathFloor(gscRatio * coords);
   if(GSC < 1)
      GSC = 1;

   ArrayResize(dx, coords);
   for(int k = 0; k < coords; k++)
      dx [k] = dxRatio * (rangeMax [k] - rangeMin [k]);

   cur        = 0;
   iterations = 0;

   InitBatch();
   batchOpen = true;
   return true;
  }

Вспомогательные методы Reserve и CopyTree. Размер леса заранее неизвестен. Внутри круга лес растёт: Revision дописывает в него каждого оценённого потомка. Поэтому массив деревьев нужно расширять по ходу работы.

Метод Reserve расширяет буфер b, только если в нём меньше size мест. Третий аргумент ArrayResize резервирует 256 дополнительных элементов, чтобы при каждом новом дереве память не перевыделялась. Массив никогда не уменьшается. Старые элементы используются повторно на следующих кругах.

//+------------------------------------------------------------------+
void C_AO_FOA::Reserve(int b, int size)
  {
   if(ArraySize(buf [b].t) < size)
      ArrayResize(buf [b].t, size, 256);
  }

Метод CopyTree копирует дерево в другой буфер. Он нужен при пересборке леса в NextBatch: выжившие и кандидаты переносятся из текущего буфера во второй. Массив координат приёмника изменяет размер только при первом использовании элемента. Дальше копируются лишь значения, без перевыделения памяти.

//+------------------------------------------------------------------+
void C_AO_FOA::CopyTree(S_FOA_Tree &dst, const S_FOA_Tree &src)
  {
   if(ArraySize(dst.c) != coords)
      ArrayResize(dst.c, coords);
   ArrayCopy(dst.c, src.c, 0, 0, coords);
   dst.f   = src.f;
   dst.age = src.age;
  }

Метод InitBatch создаёт случайные деревья возраста 0. Их число равно areaLimit, округлённому вверх до целого числа порций. Все они ставятся в очередь на оценку как готовые деревья.

//+------------------------------------------------------------------+
//| начальный лес: случайные деревья возраста 0,                     |
//| areaLimit с округлением вверх до целого числа порций             |
//+------------------------------------------------------------------+
void C_AO_FOA::InitBatch()
  {
   int n = ((areaLimit + popSize - 1) / popSize) * popSize;

   fN = 0;
   Reserve(cur, n);

   for(int i = 0; i < n; i++)
     {
      if(ArraySize(buf [cur].t [i].c) != coords)
         ArrayResize(buf [cur].t [i].c, coords);

      for(int k = 0; k < coords; k++)
         buf [cur].t [i].c [k] = u.SeInDiSp(u.RNDfromCI(rangeMin [k], rangeMax [k]),
                                            rangeMin [k], rangeMax [k], rangeStep [k]);
      buf [cur].t [i].f   = -DBL_MAX;
      buf [cur].t [i].age = 0;
     }

   bSeeds = n;
   bLocal = 0;
   bTotal = n;
   bDone  = 0;
   pN     = 0;
  }

Метод NextBatch. Это основной метод. Он вызывается, когда весь лес оценён, и выполняет шаги 3, 4 и 5 текущего круга и планирует шаг 1 следующего. Разберём его по частям.

Первая часть ограничивает популяцию. Деревья моложе lifeTime попадают в массив для сортировки, остальные сразу идут в кандидаты. После сортировки первые areaLimit деревьев остаются в лесу. Лишние дописываются в кандидаты после старых, лучшие из них идут раньше.

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

Третья часть обнуляет возраст лучшего дерева и составляет список родителей. Родителями становятся все деревья возраста 0 и все деревья глобального посева. После этого лес стареет. В конце рассчитывается длина очереди на оценку с округлением до целого числа порций.

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

//+------------------------------------------------------------------+
//| одна итерация FOA над полностью оценённым лесом:                 |
//| ограничение популяции -> глобальный посев -> лучшее дерево ->    |
//| план локального посева следующей итерации                        |
//+------------------------------------------------------------------+
void C_AO_FOA::NextBatch()
  {
   int nxt = cur ^ 1;
   int all = fN;

//--- 1. ограничение популяции -------------------------------------
   int keptN = 0;
   int candN = 0;

   ArrayResize(srt, all);
   if(ArraySize(cand) < all)
      ArrayResize(cand, all);

   for(int i = 0; i < all; i++)
     {
      if(buf [cur].t [i].age < lifeTime)
        {
         srt [keptN][0] = buf [cur].t [i].f;
         srt [keptN][1] = i;
         keptN++;
        }
      else
         cand [candN++] = i;         // старые — в кандидаты, в порядке следования
     }

   if(keptN == 0)                    // недостижимо при lifeTime >= 1; страховка
     {
      for(int i = 0; i < all; i++)
        {
         srt [i][0] = buf [cur].t [i].f;
         srt [i][1] = i;
        }
      keptN = all;
      candN = 0;
     }

   if(keptN == 0)                    // лес пуст — начать заново
     {
      InitBatch();
      return;
     }

   ArrayResize(srt, keptN);
   ArraySort(srt);                   // по возрастанию f; лучший — последний

   int K = keptN < areaLimit ? keptN : areaLimit;

   for(int r = K; r < keptN; r++)    // лишние — в кандидаты после старых, лучшие раньше
      cand [candN++] = (int)srt [keptN - 1 - r][1];

//--- 2. глобальный посев ------------------------------------------
   int n = (int)MathFloor(candN * transferRate);

   Reserve(nxt, K + n);

   for(int r = 0; r < K; r++)        // выжившие, отсортированы: лучший в [0]
      CopyTree(buf [nxt].t [r], buf [cur].t [(int)srt [keptN - 1 - r][1]]);

   for(int s = 0; s < n; s++)        // первые n кандидатов
     {
      CopyTree(buf [nxt].t [K + s], buf [cur].t [cand [s]]);

      for(int g = 0; g < GSC; g++)   // свой набор координат у каждого дерева
        {
         int k = u.RNDminusOne(coords);
         buf [nxt].t [K + s].c [k] = u.SeInDiSp(u.RNDfromCI(rangeMin [k], rangeMax [k]),
                                                rangeMin [k], rangeMax [k], rangeStep [k]);
        }
      buf [nxt].t [K + s].f   = -DBL_MAX;
      buf [nxt].t [K + s].age = 1;   // возраст 0 при посеве, +1 на шаге 4
     }

//--- 3. лучшее дерево не стареет ----------------------------------
   buf [nxt].t [0].age = 0;

//--- 4. локальный посев: родители — все деревья возраста 0 --------
   if(ArraySize(par) < K + n)
      ArrayResize(par, K + n);
   pN = 0;

   for(int r = 0; r < K; r++)
      if(buf [nxt].t [r].age == 0)
         par [pN++] = r;
   for(int s = 0; s < n; s++)
      par [pN++] = K + s;

   for(int r = 0; r < K; r++)        // стареют все, кроме новых потомков
      buf [nxt].t [r].age++;

//--- план итерации ------------------------------------------------
   cur    = nxt;
   fN     = K;
   bSeeds = n;
   bLocal = pN * LSC;
   bTotal = ((bSeeds + bLocal + popSize - 1) / popSize) * popSize;
   bDone  = 0;

   iterations++;
  }

Метод Moving выдаёт стенду очередную порцию из очереди. Готовые деревья копируются как есть. Локальный потомок создаётся на месте: копия родителя со сдвигом одной случайной координаты. Номер родителя вычисляется по позиции в очереди. Сначала каждый родитель получает LSC потомков. Позиции сверх этого раздаются родителям по кругу.

//+------------------------------------------------------------------+
//|                            Moving                                |
//| очередная порция итерации: сначала готовые деревья, затем        |
//| локальные потомки, создаваемые по мере выдачи                    |
//+------------------------------------------------------------------+
void C_AO_FOA::Moving()
  {
   if(!batchOpen)
     {
      NextBatch();
      batchOpen = true;
     }

   for(int i = 0; i < popSize; i++)
     {
      int g = bDone + i;

      if(g < bSeeds)
        {
         ArrayCopy(a [i].c, buf [cur].t [fN + g].c, 0, 0, coords);
         continue;
        }

      //--- локальный потомок: LSC на родителя, остаток порции — по кругу
      int h  = g - bSeeds;
      int pi = h < bLocal ? h / LSC : (h - bLocal) % pN;

      ArrayCopy(a [i].c, buf [cur].t [par [pi]].c, 0, 0, coords);

      int    k = u.RNDminusOne(coords);
      double x = a [i].c [k] + u.RNDfromCI(-dx [k], dx [k]);
      a [i].c [k] = u.SeInDiSp(x, rangeMin [k], rangeMax [k], rangeStep [k]);
     }
  }

Метод Revision принимает оценки. Координаты локальных потомков сохраняются в лес вместе с приспособленностью и возрастом 0. Для готовых деревьев записывается только приспособленность. Здесь же обновляется лучшее решение за прогон. Когда оценена вся очередь, круг закрывается, и следующий вызов Moving запустит NextBatch.

//+------------------------------------------------------------------+
//|                           Revision                               |
//| оценённые деревья дописываются в лес; итерация закрывается,      |
//| когда оценены все её деревья                                     |
//+------------------------------------------------------------------+
void C_AO_FOA::Revision()
  {
   Reserve(cur, fN + bDone + popSize);

   for(int i = 0; i < popSize; i++)
     {
      int g   = bDone + i;
      int idx = fN + g;

      if(g >= bSeeds)                // локальный потомок: сохранить координаты
        {
         if(ArraySize(buf [cur].t [idx].c) != coords)
            ArrayResize(buf [cur].t [idx].c, coords);
         ArrayCopy(buf [cur].t [idx].c, a [i].c, 0, 0, coords);
         buf [cur].t [idx].age = 0;
        }
      buf [cur].t [idx].f = a [i].f;

      if(a [i].f > fB)
        {
         fB = a [i].f;
         ArrayCopy(cB, a [i].c, 0, 0, coords);
        }
     }

   bDone += popSize;

   if(bDone >= bTotal)
     {
      fN       += bTotal;
      batchOpen = false;
     }

   if(!revision)
      revision = true;
  }

Результаты тестов

Тестирование шло по стандартному протоколу. Три функции: Hilly, Forest и Megacity. Три размерности: 10, 50 и 1000 координат. Бюджет каждого прогона составляет 10 000 вычислений фитнес-функции. Каждый результат усреднён по 10 прогонам. Параметры подбирались вручную на этом же стенде. Поэтому числа ниже показывают настроенный алгоритм, а не оценку на задачах, которые в подборе не участвовали. Печать стенда для лучших найденных параметров:

FOA|Forest Optimization Algorithm|10.0|20.0|30.0|0.15|0.0|0.01|0.4|
=============================
5 Hilly's; Func runs: 10000; result: 0.9276572310654156
25 Hilly's; Func runs: 10000; result: 0.6913054833862419
500 Hilly's; Func runs: 10000; result: 0.32706306020079473
=============================
5 Forest's; Func runs: 10000; result: 0.9575204000613603
25 Forest's; Func runs: 10000; result: 0.7530261684501524
500 Forest's; Func runs: 10000; result: 0.1314098316271554
=============================
5 Megacity's; Func runs: 10000; result: 0.76
25 Megacity's; Func runs: 10000; result: 0.6285333333333336
500 Megacity's; Func runs: 10000; result: 0.1712000000000004
=============================
All score: 5.34772 (59.42%)

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

Функция

10 координат

50 координат

1000 координат

Hilly

0.92766

0.69131

0.32706

Forest

0.95752

0.75303

0.13141

Megacity

0.76000

0.62853

0.17120

Сумма

2.64518 (88.2%)

2.07287 (69.1%)

0.62967 (21.0%)

Общий результат: 5.34772 из 9, или 59.42%.

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

Параметр

Рекомендация авторов

После подбора

areaLimit

20

20

lifeTime

15

30

transferRate

0.15

0.15

LSC

20% размерности: 2, 10 и 200 семян при 10, 50 и 1000 координатах

1 семя при любой размерности

GSC

10% размерности: 1, 5 и 100 координат

1% размерности: 1, 1 и 10 координат

dx

0.1 ширины диапазона

0.4 ширины диапазона

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

Самое сильное изменение касается LSC. Причина видна из арифметики. При 1000 координат и авторских 20% каждое дерево роняет 200 семян. Первый же круг для леса из 20 деревьев стоит 20 × 200 = 4000 вычислений, то есть 40% всего бюджета. При одном семени на дерево круг стоит не больше 40 вычислений. За тот же бюджет алгоритм успевает выполнить сотни кругов отбора вместо одного полного.

Выводы по результатам. Вывод первый: алгоритм силён при малом и среднем числе параметров. При 10 координатах он набирает 88.2% от максимума, при 50 координатах 69.1%. На синтетических функциях это высокий уровень. Отдельного опыта на советнике в статье нет, поэтому перенос на тестер стратегий остаётся ожиданием, а не измерением.

Вывод второй: при 1000 координат результат падает до 21.0%. Причина следует из устройства посева. Каждое новое дерево отличается от родителя одной координатой. Бюджет в 10 000 вычислений означает около 10 000 одиночных изменений. Распределение этих изменений по координатам показано в таблице.

Число координат

Изменений на одну координату за прогон

Сумма по трём функциям

10

около 1000

2.64518

50

около 200

2.07287

1000

около 10

0.62967

Десяти попыток на координату недостаточно, чтобы настроить её значение. Результат падает вместе с числом попыток. Впрочем, это общая проблема больших размерностей для всех известных алгоритмов оптимизации, и FOA твёрдо занимает средние позиции в таблице среди 45 самых сильных известных алгоритмов.

Вывод третий: функция с острыми пиками даётся алгоритму не хуже холмистой. Forest при 10 и 50 координатах даёт 0.958 и 0.753, Hilly даёт 0.928 и 0.691. Мы связываем это с крупным шагом: семя улетает на расстояние до 40% диапазона и может попасть на соседний пик. Это объяснение согласуется с тем, что подбор остановился на dx = 0.4, но отдельным опытом мы его не проверяли.

Вывод четвёртый: на ступенчатой функции Megacity результат ниже, чем на гладких, но остаётся рабочим: 0.760 и 0.629 при 10 и 50 координатах. Для трейдера это важный случай, потому что результат тестера тоже меняется ступеньками.

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

Проверка на составной функции. Пятый вывод опирается на устройство операторов. Чтобы проверить его измерением, мы запустили составной тест. В нём пары координат по очереди раздаются пяти функциям: Hilly, Forest, Megacity, Peaks и Skin. У каждой функции свой диапазон и своё положение оптимума. Приспособленность равна среднему по всем парам.

Логика проверки простая. Если алгоритм получает выгоду от центра диапазона или от диагонали, на составной функции эта выгода пропадёт, и результат упадёт ниже 10-координатной части основного стенда. Если выгоды нет, результаты окажутся близки.

Прогон анитичит-теста выполнен с теми же параметрами, что и основной тест, на 10 координатах (5 пар):

FOA|Forest Optimization Algorithm|10.0|20.0|30.0|0.15|0.0|0.01|0.4|   
=============================
Composite anti-cheat test: Hilly + Forest + Megacity + Peaks + Skin
Pairs: 5; Coordinates: 10; Epochs: 1000; Repeats: 10
=============================
Run 1/10: 0.8457783720344878
Run 2/10: 0.9162545983573436
Run 3/10: 0.9625312389565297
Run 4/10: 0.9759954891084142
Run 5/10: 0.8500462775802781
Run 6/10: 0.8491967630185414
Run 7/10: 0.9483640852971952
Run 8/10: 0.9822687479373468
Run 9/10: 0.8774806961860762
Run 10/10: 0.8890752279420138
=============================
Average result: 0.9096991496 (90.97%)

Ориентиром служит среднее по трём 10-координатным результатам основного стенда: (0.92766 + 0.95752 + 0.76000) / 3 = 0.88173.

Показатель

Значение

Ориентир (основной стенд, 10 координат)

0.88173 (88.17%)

Составной тест, среднее по 10 прогонам

0.90970 (90.97%)

Разброс прогонов

от 0.84578 до 0.98227

Стандартное отклонение прогона

0.0545

Стандартная ошибка среднего

0.0172

Составной тест дал на 2.8 процентного пункта больше ориентира. Это около 1.6 стандартной ошибки, то есть в пределах разброса. В этой составной проверке падения не обнаружено. Признаков того, что на основном стенде алгоритм получал выгоду от положения оптимума, нет. Одна оговорка: функций Peaks и Skin на основном стенде нет. Поэтому ориентир приблизительный, и небольшое превышение над ним не означает, что составная задача для FOA проще.

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

Hilly

FOA на тестовой функции Hilly

Forest

FOA на тестовой функции Forest

Megacity

FOA на тестовой функции Megacity

Ackley

FOA на функции Ackley

Peaks

FOA на функции Peaks

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

cc
AO
Description
Hilly
Hilly
Final
Forest
Forest
Final
Megacity (discrete)
Megacity
Final
Final
Result
% of
MAX
10 p (5 F) 50 p (25 F) 1000 p (500 F) 10 p (5 F) 50 p (25 F) 1000 p (500 F) 10 p (5 F) 50 p (25 F) 1000 p (500 F)
1 ANS across neighbourhood search 1,00000 0,88228 0,40138 2,28366 1,00000 0,95281 0,28092 2,23373 0,94667 0,85733 0,22389 2,02789 6,545 72,72
2 AMOm animal migration optimization M 0,91624 0,83603 0,46790 2,22017 0,98482 0,92010 0,36391 2,26883 0,91733 0,81707 0,25177 1,98617 6,475 71,94
3 CLA code lock algorithm (joo) 0,95139 0,86199 0,37879 2,19217 0,99349 0,93500 0,26497 2,19346 0,93600 0,84267 0,24060 2,01927 6,405 71,17
4 (P+O)ES (P+O) evolution strategies 0,86571 0,89539 0,39740 2,15850 0,97761 0,89820 0,26878 2,14459 0,92133 0,80240 0,23952 1,96325 6,266 69,62
5 SDSm stochastic diffusion search M 0,95195 0,84944 0,36249 2,16388 0,98061 0,88457 0,22112 2,08630 0,92267 0,79013 0,21380 1,92660 6,177 68,63
6 AAm archery algorithm M 0,84685 0,73320 0,42590 2,00595 0,96709 0,77837 0,27789 2,02335 0,86133 0,77707 0,28712 1,92552 5,955 66,17
7 SIA simulated isotropic annealing (joo) 0,93543 0,86504 0,38483 2,18530 0,94069 0,80609 0,23835 1,98513 0,86400 0,66160 0,19536 1,72096 5,891 65,46
8 TETA time evolution travel algorithm (joo) 0,91452 0,86369 0,25579 2,03400 0,99654 0,91291 0,14394 2,05339 0,85467 0,82213 0,10443 1,78123 5,869 65,21
9 ESG evolution of social groups (joo) 0,98111 0,79857 0,31167 2,09135 0,98954 0,82270 0,15032 1,96256 0,92133 0,73440 0,15315 1,80888 5,863 65,14
10 CTA comet tail algorithm (joo) 0,92435 0,86786 0,27838 2,07059 0,99039 0,84571 0,19448 2,03058 0,95467 0,69680 0,11008 1,76155 5,863 65,14
11 COA coyote_optimization_algorithm 0,88909 0,70681 0,32718 1,92308 0,99467 0,85358 0,15152 1,99977 0,88533 0,71040 0,18981 1,78554 5,708 63,43
12 CSBO circulatory_system_based_optimization 0,87793 0,79105 0,30025 1,96923 0,95026 0,88027 0,15364 1,98417 0,85813 0,71525 0,14777 1,72115 5,776 63,05
13 ECBO enhanced colliding bodies optimization 0,94024 0,72363 0,32356 1,98743 0,99477 0,80291 0,13056 1,92824 0,87600 0,70160 0,17433 1,75193 5,668 62,98
14 BCO(B) bezier_curve-based_optimization 0,99069 0,77836 0,30678 2,07583 0,98481 0,74554 0,13778 1,86813 0,96400 0,58773 0,14361 1,69534 5,639 62,66
15 DA dialectical algorithm 0,93117 0,75400 0,26205 1,94722 0,98925 0,81375 0,08662 1,88962 0,92667 0,68107 0,11315 1,72089 5,558 61,76
16 BBO biogeography based optimization 0,95876 0,70609 0,35752 2,02237 0,92981 0,70660 0,16970 1,80611 0,87467 0,63013 0,20813 1,71293 5,541 61,57
17 BHAm black hole algorithm M 0,79558 0,76207 0,34682 1,90447 0,99836 0,75798 0,13826 1,89460 0,85067 0,64427 0,17020 1,66514 5,464 60,71
18 HS harmony search 0,91420 0,69049 0,29924 1,90393 0,97627 0,73373 0,14193 1,85193 0,91733 0,62720 0,15364 1,69817 5,454 60,60
19 RFO royal flush optimization (joo) 0,80989 0,74481 0,34546 1,90016 0,95251 0,77926 0,15185 1,88362 0,80400 0,66427 0,19071 1,65898 5,443 60,48
20 BOAm billiards optimization algorithm M 0,76177 0,72421 0,25275 1,73873 0,90890 0,81960 0,28853 2,01703 0,83733 0,74613 0,09763 1,68109 5,437 60,41
21 ASO anarchy society optimization 0,73070 0,73713 0,31195 1,77978 0,99732 0,87700 0,17619 2,05051 0,72000 0,68773 0,18988 1,59761 5,428 60,31
22 OOAm osprey_optimization_algorithm 0,67372 0,68299 0,34866 1,70537 0,99999 0,86410 0,15774 2,02183 0,78933 0,70613 0,18442 1,67988 5,407 60,08
23 EOm extremal optimization_M 0,76527 0,75205 0,31908 1,83640 0,99999 0,76426 0,12437 1,88862 0,84133 0,64133 0,15247 1,63513 5,360 59,56
24 FOA forest_optimization_algorithm 0,92765 0,69130 0,32706 1,94601 0,95752 0,75302 0,13141 1,84195 0,76000 0,62853 0,17120 1,55973 5,348 59,42
25 ACS artificial cooperative search 0,75545 0,77162 0,31653 1,84360 1,00000 0,80488 0,10705 1,91193 0,76933 0,60800 0,14157 1,51890 5,274 58,60
26 SSG saplings sowing and growing 0,75436 0,63206 0,35935 1,74577 0,91907 0,69694 0,19755 1,81356 0,81867 0,60533 0,21347 1,63747 5,197 57,74
27 AOSm atomic orbital search M 0,76184 0,68435 0,31344 1,75963 0,90015 0,80044 0,11501 1,81560 0,82800 0,63280 0,15696 1,61776 5,193 57,70
28 TSEA turtle shell evolution algorithm (joo) 0,95809 0,64852 0,29571 1,90232 0,99522 0,58104 0,10542 1,68168 0,92133 0,52160 0,14567 1,58860 5,173 57,48
29 DE flow_direction_algorithm 0,96398 0,62346 0,26089 1,84833 0,98482 0,77018 0,11459 1,86959 0,93067 0,36213 0,11000 1,40280 5,121 56,90
30 BIO blood inheritance optimization (joo) 0,72580 0,66522 0,31228 1,70330 0,99995 0,68125 0,11540 1,79660 0,85467 0,59333 0,15364 1,60164 5,102 56,69
31 (PO)ES (PO) evolution strategies 0,73972 0,58190 0,38896 1,71058 0,91199 0,59975 0,21262 1,72436 0,82400 0,56240 0,23432 1,62072 5,056 56,18
32 BO bonobo optimizer 0,75555 0,64366 0,32657 1,72578 0,94332 0,70442 0,13999 1,78773 0,73467 0,61440 0,16728 1,51635 5,030 55,89
33 SRA successful restaurateur algorithm (joo) 0,89010 0,63359 0,29115 1,81484 0,96634 0,55285 0,08914 1,60833 0,89333 0,52800 0,13911 1,56044 4,984 55,38
34 FDAm flow_direction_algorithm_M 0,87573 0,58806 0,27135 1,73514 0,99997 0,64399 0,09633 1,74029 0,84267 0,48453 0,11888 1,44608 4,922 54,70
35 CRO chemical reaction optimisation 0,91281 0,65681 0,29866 1,86828 0,90513 0,56020 0,10939 1,57472 0,82800 0,50133 0,14149 1,47082 4,914 54,60
36 BCOm bacterial chemotaxis optimization M 0,82589 0,61733 0,31584 1,75906 0,95296 0,63718 0,11984 1,70998 0,76533 0,51653 0,15800 1,43986 4,909 54,54
37 DOA dream optimization algorithm 0,78522 0,78121 0,36036 1,92679 0,61584 0,42117 0,12254 1,15955 0,86667 0,72587 0,21127 1,80381 4,890 54,33
38 ABO african buffalo optimization 0,92295 0,62528 0,29885 1,84708 0,92992 0,57468 0,09372 1,59832 0,73333 0,51333 0,14324 1,38990 4,835 53,72
39 BSA bird swarm algorithm 0,94432 0,67941 0,26401 1,88774 0,91649 0,65619 0,12054 1,69322 0,80933 0,33547 0,10652 1,25132 4,832 53,69
40 TSm tabu search M 0,87806 0,61040 0,28993 1,77839 0,98116 0,52165 0,08544 1,58825 0,82667 0,49547 0,13552 1,45766 4,824 53,60
41 BSA backtracking search algorithm 0,87128 0,53190 0,28675 1,68993 0,92408 0,51602 0,09153 1,53163 0,96000 0,47253 0,13760 1,57013 4,792 53,24
42 BEA bacterial_evolutionary_algorithm 0,92170 0,59615 0,29340 1,81125 0,96906 0,44500 0,08233 1,49639 0,90533 0,43173 0,13676 1,47382 4,781 53,13
43 BWOm beluga_whale_optimization_M 0,78488 0,56872 0,29557 1,64917 0,91370 0,61760 0,12988 1,66118 0,81333 0,49946 0,15004 1,46283 4,773 53,04
44 WOAm whale optimization algorithm M 0,93893 0,59477 0,26695 1,80065 0,98036 0,53873 0,07112 1,59021 0,78667 0,47600 0,11892 1,38159 4,772 53,02
45 ACA andean_condor_algorithm 0,78444 0,53260 0,33108 1,64812 0,79071 0,44960 0,10685 1,34716 0,92266 0,67733 0,17613 1,77612 4,771 53,02
RW random walk 0,49970 0,32333 0,25791 1,08094 0,30754 0,11470 0,04400 0,46624 0,36133 0,17013 0,10244 0,63390 2,181 24,23


Выводы

Мы начали с вопроса: хватит ли простого и понятного алгоритма для подбора двух-трёх десятков параметров советника при ограниченном числе прогонов. На синтетических функциях тесты дают ответ: да, хватит. При 10 координатах FOA набирает 88.2% от максимума, при 50 координатах 69.1%. Общий результат на стенде составляет 59.42%.

Читатель получает три вещи. Первая: готовый класс C_AO_FOA, совместимый со всеми тестами серии. Вторая: параметры, подобранные на стенде и записанные в конструкторе. Третья: понимание границы применимости. Алгоритм хорошо подходит для задач до нескольких десятков параметров. При 50 параметрах результат рабочий, а на 1000 координат снижается до 21.0% при конечном числе итераций. Сотни параметров отдельно не проверялись.

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

Рекомендации по настройке под свою задачу:

  • если результат застревает на одном значении, увеличьте transferRate или gscRatio: станет больше дальних прыжков;
  • если решение найдено грубо и не уточняется, уменьшите dxRatio: семена будут падать ближе к родителю;
  • если прогонов в тестере совсем мало, уменьшите areaLimit: бюджет сосредоточится на меньшем числе решений.

tab

Рисунок 3. Цветовая градация алгоритмов по результатам соответствующих тестов

chart

Рисунок 4. Гистограмма результатов тестирования алгоритмов (по шкале от 0 до 100: чем больше, тем лучше, где 100 — максимально возможный теоретический результат). В архиве приведён скрипт для расчёта рейтинговой таблицы


Плюсы и минусы итоговой версии FOA

Плюсы:

  • всего два понятных способа получить новое решение, поведение легко объяснить и настроить;
  • высокие результаты на всех трёх функциях;
  • рабочий результат на ступенчатой функции Megacity;

Минусы:

  • много внешних параметров (шесть), причём рекомендованные авторами значения далеки от лучших;
  • переменное число вычислений на круг: для работы порциями фиксированного размера нужна очередь на оценку;
  • локальный посев меняет одну координату за раз, поэтому скорость поиска падает с ростом размерности

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


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

# Имя Тип Описание
1 #C_AO.mqh
Включаемый файл
Родительский класс популяционных алгоритмов оптимизации
2 #C_AO_enum.mqh
Включаемый файл
Перечисление популяционных алгоритмов оптимизации
3 TestFunctions.mqh
Включаемый файл
Библиотека тестовых функций
4
TestStandFunctions.mqh
Включаемый файл
Библиотека функций тестового стенда
5 TestStand3D.mqh Включаемый файл 3D-панель визуализации для тестового стенда 
6 Utilities.mqh
Включаемый файл
Библиотека вспомогательных функций
7 CalculationTestResults.mqh
Включаемый файл
Скрипт для расчёта результатов в сравнительную таблицу
8 Test_AO_All.mq5
Скрипт Единый испытательный стенд для всех популяционных алгоритмов оптимизации
9 Test_AO_AntiCheat Скрипт Тест на читерство алгоритмов оптимизации
10 Simple use of population optimization algorithms.mq5
Скрипт
Простой пример использования популяционных алгоритмов оптимизации без визуализации
11 Test_AO_FOA.mq5
Скрипт Испытательный стенд для FOA
Прикрепленные файлы |
FOA.zip (476.9 KB)
Особенности написания Пользовательских Индикаторов Особенности написания Пользовательских Индикаторов
Написание пользовательских индикаторов в торговой системе MetaTrader 4
Нейронные аддитивные модели в MQL5: Точное определение вклада признаков в торговый сигнал Нейронные аддитивные модели в MQL5: Точное определение вклада признаков в торговый сигнал
Создание и развертывание нейронной аддитивной модели непосредственно в MQL5: отдельная небольшая сеть для каждого признака, аддитивный выход без необходимости отдельно объяснять результаты после расчета. В статье представлены скрипт обучения на PyTorch, экспорт в ONNX с двумя выходами (сигнал и вклады), обертка в подключаемом файле с использованием OnnxCreateFromBuffer/OnnxRun и советник, который на каждом баре выводит фактический вклад каждого признака. В статье рассматриваются единые формулы расчета признаков для обучения и экспорта, определение пороговых значений, результаты тестера стратегий и граничные случаи, такие как значения NaN и входы вне обучающего распределения.
Особенности написания экспертов Особенности написания экспертов
Написание и тестирование экспертов в торговой системе MetaTrader 4.
Точность вычислений под прицелом: Сравнение MQL5, ONNX Runtime и ALGLIB Точность вычислений под прицелом: Сравнение MQL5, ONNX Runtime и ALGLIB
В этой статье проводится сравнительное тестирование прямого прохода многослойного перцептрона (MLP), реализованного в MQL5 тремя способами: средствами штатного MQL5, с использованием ALGLIB и ONNX Runtime. Мы количественно оцениваем точность вычислений относительно эталона float64 и время выполнения (среднее значение и процентили), а затем предлагаем практические критерии и готовый к использованию тестовый стенд, которые помогут выбрать подходящий вычислительный движок и интегрировать его в советник.