Алгоритм на основе фракталов — Fractal-Based Algorithm (FBA)

MetaTrader 5 — Трейдинг | 7 мая 2025, 10:21

582

Andrey Dik

Содержание

Введение

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

В данной статье рассмотрим новый метаэвристический алгоритм для решения задач непрерывной оптимизации — Fractal-based Algorithm (FBA) Марджана Каеди от 2017 года. Этот подход основан на геометрических свойствах фракталов и использует концепцию самоподобия для адаптивного исследования пространства. В основе алгоритма лежит инновационная эвристика, которая оценивает перспективность различных областей поиска на основе плотности расположения в них качественных решений.

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

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

Представьте, что вы ищете клад в огромном поле. Как бы вы действовали? Вероятно, не стали бы перекапывать каждый сантиметр земли — это заняло бы слишком много времени. Именно такую проблему решает фрактальный алгоритм (FBA) — он помогает найти "сокровище" (оптимальное решение) в огромном пространстве возможностей, не проверяя каждую точку.

Как можно представить работу этого алгоритма? Сначала разбиваем всю территорию поиска на равные квадраты, как шахматную доску. Затем забрасываем "искателей" (случайные точки) по всему полю, чтобы получить первое представление о местности. Каждый искатель докладывает о качестве найденного им участка. Алгоритм отбирает самых успешных (60% лучших точек) и смотрит, в каких квадратах они сосредоточены. Эти квадраты помечаются как "перспективные зоны" (30% лучших квадратов).

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

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

fba-space-partitioning

Рисунок 1. Визуализация схемы работы алгоритма FBA

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

Инициализация:

Разделить все пространство поиска на равные подпространства
Сгенерировать начальную популяцию равномерно по всему пространству
Оценить пригодность каждой точки

Процесс итерации:

Определение перспективных точек: выберите P1% точек с наилучшей пригодностью.
Рассчет рангов подпространств: подсчитайте, сколько перспективных точек попадает в каждое подпространство.
Выбор перспективных подпространств: выберите P2% подпространств с наивысшими перспективными рангами.
Разделение перспективных подпространств: дальнейшее разделение перспективных областей на более мелкие подпространства.
Генерация нового населения: создание новых точек с более высокой плотностью в перспективных регионах.
Применение мутации: добавить гауссовский шум к P3% точек (механизм исследования).
Интеграция популяций: объединение текущей и новой популяции с сохранением лучших точек.

Критерий останова:

Продолжайте, пока не будет достигнут критерий остановки (максимальное количество итераций, порог пригодности и т.д.)
Верните лучшее найденное решение

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

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

В классе объявлено также внутреннее структурное представление "S_Subspace", которое используется для описания подпространства поиска. Каждое подпространство характеризуется минимальными и максимальными границами по каждому измерению, степенью его перспективности, уровнем в иерархии, а также связью с родительским подпространством.

Основные методы внутри класса включают функционал для:

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

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

//——————————————————————————————————————————————————————————————————————————————
class C_AO_FBA : public C_AO
{
  public: //--------------------------------------------------------------------
  ~C_AO_FBA () { }
  C_AO_FBA ()
  {
    ao_name = "FBA";
    ao_desc = "Fractal-Based Algorithm";
    ao_link = "https://www.mql5.com/ru/articles/17458";

    popSize = 50;  // размер популяции
    P1      = 60;  // процент перспективных точек
    P2      = 30;  // процент перспективных подпространств
    P3      = 0.8; // процент точек для случайной модификации
    m_value = 10;  // число интервалов для разделения каждого измерения

    ArrayResize (params, 5);

    params [0].name = "popSize"; params [0].val = popSize;
    params [1].name = "P1";      params [1].val = P1;
    params [2].name = "P2";      params [2].val = P2;
    params [3].name = "P3";      params [3].val = P3;
    params [4].name = "m_value"; params [4].val = m_value;
  }

  void SetParams ()
  {
    popSize = (int)params [0].val;
    P1      = (int)params [1].val;
    P2      = (int)params [2].val;
    P3      =      params [3].val;
    m_value = (int)params [4].val;
  }

  bool Init (const double &rangeMinP  [],  // минимальные значения
             const double &rangeMaxP  [],  // максимальные значения
             const double &rangeStepP [],  // шаг изменения
             const int     epochsP = 0);   // количество эпох

  void Moving   ();
  void Revision ();

  //----------------------------------------------------------------------------
  int    P1;           // процент перспективных точек
  int    P2;           // процент перспективных подпространств
  double P3;           // доля точек для случайной модификации
  int    m_value;      // число интервалов для разделения каждого измерения

  private: //-------------------------------------------------------------------

  // Структура для представления подпространства
  struct S_Subspace
  {
      double min [];        // минимальные границы подпространства
      double max [];        // максимальные границы подпространства
      double promisingRank; // ранг перспективности (нормализованное значение)
      bool   isPromising;   // флаг перспективности
      int    parentIndex;   // индекс родительского подпространства (-1 для корневых)
      int    level;         // уровень в иерархии (0 для исходного пространства)

      void Init (int coords)
      {
        ArrayResize (min, coords);
        ArrayResize (max, coords);
        promisingRank = 0.0;
        isPromising   = false;
        parentIndex   = -1;
        level         = 0;
      }
  };

  S_Subspace subspaces     []; // массив подпространств

  // Вспомогательные методы
  bool   IsPointInSubspace              (const double &point [], const S_Subspace &subspace);
  void   CreateInitialSpacePartitioning ();
  void   DivideSubspace                 (int subspaceIndex);
  void   IdentifyPromisingPoints        (int &promisingIndices []);
  void   CalculateSubspaceRanks         (const int &promisingIndices []);
  void   SelectPromisingSubspaces       ();
  void   DividePromisingSubspaces       ();
  void   GenerateNewPopulation          ();
  void   MutatePoints                   ();
  void   SortByFitness                  (double &values [], int &indices [], int size, bool ascending = false);
  void   QuickSort                      (double &values [], int &indices [], int low, int high, bool ascending);
  int    Partition                      (double &values [], int &indices [], int low, int high, bool ascending);
};
//——————————————————————————————————————————————————————————————————————————————

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

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

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

//——————————————————————————————————————————————————————————————————————————————
bool C_AO_FBA::Init (const double &rangeMinP  [],  // минимальные значения
                     const double &rangeMaxP  [],  // максимальные значения
                     const double &rangeStepP [],  // шаг изменения
                     const int     epochsP = 0)    // количество эпох
{
  if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false;

  //----------------------------------------------------------------------------
  // Создаем начальное разделение пространства поиска
  CreateInitialSpacePartitioning ();

  return true;
}
//——————————————————————————————————————————————————————————————————————————————

//+----------------------------------------------------------------------------+
//| Основной метод оптимизации                                                 |
//+----------------------------------------------------------------------------+
void C_AO_FBA::Moving ()
{
  // Первая итерация - инициализация начальной популяции
  if (!revision)
  {
    // Инициализация начальной популяции равномерно по всему пространству
    for (int i = 0; i < popSize; i++)
    {
      for (int c = 0; c < coords; c++)
      {
        a [i].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]);
        a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }

    revision = true;
    return;
  }

  // Основной процесс оптимизации

  // 1. Выявление перспективных точек (P1% точек с лучшими значениями функции)
  int promisingIndices [];
  IdentifyPromisingPoints (promisingIndices);

  // 2. Расчет рангов перспективности для каждого подпространства
  CalculateSubspaceRanks (promisingIndices);

  // 3. Выбор P2% самых перспективных подпространств
  SelectPromisingSubspaces ();

  // 4. Разделение перспективных подпространств на более мелкие
  DividePromisingSubspaces ();

  // 5. Генерация новых точек с учетом рангов перспективности
  GenerateNewPopulation ();

  // 6. Случайная модификация (мутация)
  MutatePoints ();
}
//——————————————————————————————————————————————————————————————————————————————

Метод "Revision" отвечает за обновление текущего лучшего найденного решения в процессе работы алгоритма. Он перебирает все элементы текущей популяции и сравнивает значение целевой функции каждого элемента с текущим лучшим значением. Если у какого-то элемента оно лучше, то переменная, хранящая лучший результат, обновляется, а также копируется связанный с ним массив переменных (координат) для фиксации этого оптимального решения. За счет этого, метод обеспечивает постоянное отслеживание и сохранение наилучшего найденного на данный момент результата.

//+----------------------------------------------------------------------------+
//| Обновление лучшего решения                                                 |
//+----------------------------------------------------------------------------+
void C_AO_FBA::Revision ()
{
  // Поиск лучшего решения
  for (int i = 0; i < popSize; i++)
  {
    // Обновление лучшего решения
    if (a [i].f > fB)
    {
      fB = a [i].f;
      ArrayCopy (cB, a [i].c, 0, 0, WHOLE_ARRAY);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

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

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

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

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

//+----------------------------------------------------------------------------+
//| Создание начального разделения пространства                                |
//+----------------------------------------------------------------------------+
void C_AO_FBA::CreateInitialSpacePartitioning ()
{
  // Создаем начальное разделение пространства
  int totalSubspaces = (int)MathPow (m_value, coords);

  // При очень большой размерности ограничиваем количество подпространств
  if (totalSubspaces > 10000) totalSubspaces = 10000;

  ArrayResize (subspaces, totalSubspaces);

  // Инициализируем все подпространства
  for (int i = 0; i < totalSubspaces; i++)
  {
    subspaces [i].Init (coords);
    subspaces [i].level = 0; // Начальный уровень
  }

  // Разделяем начальное пространство на равные подпространства
  int index = 0;

  // В зависимости от размерности пространства выбираем метод разделения
  if (coords == 1)
  {
    // Одномерный случай
    double intervalSize = (rangeMax [0] - rangeMin [0]) / m_value;

    for (int i = 0; i < m_value && index < totalSubspaces; i++)
    {
      subspaces [index].min [0] = rangeMin [0] + i * intervalSize;
      subspaces [index].max [0] = rangeMin [0] + (i + 1) * intervalSize;
      index++;
    }
  }
  else
    if (coords == 2)
    {
      // Двумерный случай
      double intervalSize0 = (rangeMax [0] - rangeMin [0]) / m_value;
      double intervalSize1 = (rangeMax [1] - rangeMin [1]) / m_value;

      for (int i = 0; i < m_value && index < totalSubspaces; i++)
      {
        for (int j = 0; j < m_value && index < totalSubspaces; j++)
        {
          subspaces [index].min [0] = rangeMin [0] + i * intervalSize0;
          subspaces [index].max [0] = rangeMin [0] + (i + 1) * intervalSize0;
          subspaces [index].min [1] = rangeMin [1] + j * intervalSize1;
          subspaces [index].max [1] = rangeMin [1] + (j + 1) * intervalSize1;
          index++;
        }
      }
    }
    else
    {
      // Многомерный случай - используем итеративный подход
      int indices [];
      ArrayResize (indices, coords);
      for (int i = 0; i < coords; i++) indices [i] = 0;

      while (index < totalSubspaces)
      {
        // Вычисляем границы текущего подпространства
        for (int c = 0; c < coords; c++)
        {
          double intervalSize = (rangeMax [c] - rangeMin [c]) / m_value;
          subspaces [index].min [c] = rangeMin [c] + indices [c] * intervalSize;
          subspaces [index].max [c] = rangeMin [c] + (indices [c] + 1) * intervalSize;
        }

        // Переходим к следующему подпространству
        int c = coords - 1;
        while (c >= 0)
        {
          indices [c]++;
          if (indices [c] < m_value) break;
          indices [c] = 0;
          c--;
        }

        // Если завершили полный цикл, выходим
        if (c < 0) break;

        index++;
      }
    }
}
//——————————————————————————————————————————————————————————————————————————————

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

//+----------------------------------------------------------------------------+
//| Определение принадлежности точки подпространству                           |
//+----------------------------------------------------------------------------+
bool C_AO_FBA::IsPointInSubspace (const double &point [], const S_Subspace &subspace)
{
  // Проверяем, находится ли точка в указанном подпространстве
  for (int c = 0; c < coords; c++)
  {
    if (point [c] < subspace.min [c] || point [c] >= subspace.max [c])
    {
      return false;
    }
  }

  return true;
}
//——————————————————————————————————————————————————————————————————————————————

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

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

//+----------------------------------------------------------------------------+
//| Выявление перспективных точек                                              |
//+----------------------------------------------------------------------------+
void C_AO_FBA::IdentifyPromisingPoints (int &promisingIndices [])
{
  // Выбираем P1% точек с лучшими значениями функции

  // Создаем массивы для сортировки
  double values  [];
  int    indices [];

  ArrayResize (values,  popSize);
  ArrayResize (indices, popSize);

  // Заполняем массивы
  for (int i = 0; i < popSize; i++)
  {
    values  [i] = a [i].f;
    indices [i] = i;
  }

  // Сортируем по убыванию (для задачи максимизации)
  SortByFitness (values, indices, popSize);

  // Выбираем P1% лучших точек
  int numPromisingPoints = (int)MathRound (popSize * P1 / 100.0);
  numPromisingPoints = MathMax (1, MathMin (numPromisingPoints, popSize));

  ArrayResize (promisingIndices, numPromisingPoints);

  for (int i = 0; i < numPromisingPoints; i++)
  {
    promisingIndices [i] = indices [i];
  }
}
//——————————————————————————————————————————————————————————————————————————————

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

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

//+----------------------------------------------------------------------------+
//| Расчет рангов перспективности подпространств                               |
//+----------------------------------------------------------------------------+
void C_AO_FBA::CalculateSubspaceRanks (const int &promisingIndices [])
{
  // Сбрасываем ранги подпространств
  for (int i = 0; i < ArraySize (subspaces); i++)
  {
    subspaces [i].promisingRank = 0.0;
  }

  // Подсчитываем перспективные точки в каждом подпространстве
  for (int i = 0; i < ArraySize (promisingIndices); i++)
  {
    int pointIndex = promisingIndices [i];

    for (int j = 0; j < ArraySize (subspaces); j++)
    {
      if (IsPointInSubspace (a [pointIndex].c, subspaces [j]))
      {
        subspaces [j].promisingRank++;
        break; // Точка может находиться только в одном подпространстве
      }
    }
  }

  // Нормализуем ранги перспективности согласно статье
  // PromisingRank = Number of promising points in s / Total promising points
  int totalPromisingPoints = ArraySize (promisingIndices);
  if (totalPromisingPoints > 0)
  {
    for (int i = 0; i < ArraySize (subspaces); i++)
    {
      subspaces [i].promisingRank = subspaces [i].promisingRank / totalPromisingPoints;
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Метод "SelectPromisingSubspaces" определяет, какие подпространства следует считать перспективными, основываясь на их рангах. Создаются временные массивы "ranks" и "indices" для хранения рейтингов подпространств и их соответствующих индексов. Значения рейтингов и индексы подпространств копируются во временные массивы. Для каждого подпространства устанавливается флаг "isPromising" в "false". Это необходимо, чтобы начать с чистого листа и не учитывать результаты предыдущих итераций. Массив "ranks" сортируется в порядке убывания, а параллельно с этим, массив "indices" перестраивается так, чтобы сохранять соответствие индексов рейтингам.

Таким образом, в "indices" после сортировки находятся индексы подпространств, отсортированные по убыванию их рейтингов. Вычисляется количество подпространств, которые будут считаться перспективными, исходя из параметра "P2" (процент лучших подпространств). Полученное значение ограничивается диапазоном от 1 до общего числа подпространств. Проходится по первым "numPromisingSubspaces" элементам массива "indices". Для каждого индекса в этом массиве устанавливается флаг "isPromising" в "true" для соответствующего подпространства. Это означает, что данное подпространство считается перспективным.

Также присутствует проверка индекса на нахождение в пределах допустимого диапазона, чтобы избежать ошибок при обращении к массиву "subspaces". В результате выполнения метода, флаг "isPromising" установлен в "true" для "P2%" подпространств с наивысшими рангами.

//+----------------------------------------------------------------------------+
//| Выбор перспективных подпространств                                         |
//+----------------------------------------------------------------------------+
void C_AO_FBA::SelectPromisingSubspaces ()
{
  // Выбираем P2% подпространств с наивысшими рангами как перспективные

  // Создаем массивы для сортировки
  double ranks [];
  int indices [];

  int numSubspaces = ArraySize (subspaces);
  ArrayResize (ranks, numSubspaces);
  ArrayResize (indices, numSubspaces);

  // Заполняем массивы
  for (int i = 0; i < numSubspaces; i++)
  {
    ranks [i] = subspaces [i].promisingRank;
    indices [i] = i;
    // Сбрасываем флаг перспективности
    subspaces [i].isPromising = false;
  }

  // Сортируем по убыванию рангов
  SortByFitness (ranks, indices, numSubspaces);

  // Выбираем P2% самых перспективных подпространств
  int numPromisingSubspaces = (int)MathRound (numSubspaces * P2 / 100.0);
  numPromisingSubspaces = MathMax (1, MathMin (numPromisingSubspaces, numSubspaces));

  // Отмечаем перспективные подпространства
  for (int i = 0; i < numPromisingSubspaces && i < ArraySize (indices); i++)
  {
    // Защита от выхода за пределы массива
    if (indices [i] >= 0 && indices [i] < ArraySize (subspaces))
    {
      subspaces [indices [i]].isPromising = true;
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Метод "DividePromisingSubspaces" предназначен для разделения перспективных подпространств на более мелкие части. Сначала он идентифицирует все подпространства, помеченные как перспективные, путем проверки флага "isPromising". Индексы этих подпространств собираются во временный массив "promisingIndices". Затем, для каждого подпространства, индекс которого находится в массиве "promisingIndices", вызывается функция "DivideSubspace" для передачи индекса этого подпространства.

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

//+----------------------------------------------------------------------------+
//| Разделение перспективных подпространств                                    |
//+----------------------------------------------------------------------------+
void C_AO_FBA::DividePromisingSubspaces ()
{
  // Собираем индексы перспективных подпространств
  int promisingIndices [];
  int numPromising = 0;

  for (int i = 0; i < ArraySize (subspaces); i++)
  {
    if (subspaces [i].isPromising)
    {
      numPromising++;
      ArrayResize (promisingIndices, numPromising);
      promisingIndices [numPromising - 1] = i;
    }
  }

  // Делим каждое перспективное подпространство
  for (int i = 0; i < numPromising; i++)
  {
    DivideSubspace (promisingIndices [i]);
  }
}
//——————————————————————————————————————————————————————————————————————————————

Метод "DivideSubspace" предназначен для разбиения конкретного подпространства на более мелкие части. Вначале выбирается родительское подпространство по переданному индексу. Проверяется, не превышает ли общее число подпространств установленный лимит (10 000). Определяется общее число новых подпространств, которое получится в результате деления по каждому измерению на "m_value частей" — это возведение "m_value" в степень, равную количеству измерений.

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

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

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

//+----------------------------------------------------------------------------+
//| Разделение конкретного подпространства                                     |
//+----------------------------------------------------------------------------+
void C_AO_FBA::DivideSubspace (int subspaceIndex)
{
  // Делим указанное подпространство на m_value^coords подпространств

  S_Subspace parent = subspaces [subspaceIndex];

  // Ограничение на максимальное количество подпространств
  if (ArraySize (subspaces) > 10000) return;

  // Для каждого измерения делим на m_value частей
  int totalNewSubspaces = (int)MathPow (m_value, coords);
  int currentSize = ArraySize (subspaces);
  ArrayResize (subspaces, currentSize + totalNewSubspaces);

  // Создаем новые подпространства
  int newIndex = currentSize;
  int indices [];
  ArrayResize (indices, coords);
  for (int i = 0; i < coords; i++) indices [i] = 0;

  for (int idx = 0; idx < totalNewSubspaces && newIndex < ArraySize (subspaces); idx++)
  {
    subspaces [newIndex].Init (coords);
    subspaces [newIndex].level = parent.level + 1;
    subspaces [newIndex].parentIndex = subspaceIndex;

    // Вычисляем границы текущего подпространства
    for (int c = 0; c < coords; c++)
    {
      double intervalSize = (parent.max [c] - parent.min [c]) / m_value;
      subspaces [newIndex].min [c] = parent.min [c] + indices [c] * intervalSize;
      subspaces [newIndex].max [c] = parent.min [c] + (indices [c] + 1) * intervalSize;
    }

    // Переходим к следующему подпространству
    int c = coords - 1;
    while (c >= 0)
    {
      indices [c]++;
      if (indices [c] < m_value) break;
      indices [c] = 0;
      c--;
    }

    // Если завершили полный цикл, выходим
    if (c < 0) break;

    newIndex++;
  }
}
//——————————————————————————————————————————————————————————————————————————————

Метод "GenerateNewPopulation" создает новую популяцию точек, распределяя их по подпространствам в соответствии с "перспективностью", определяемой параметром "promisingRank".

Сначала вычисляется общая сумма "promisingRank" для всех подпространств. Это значение будет использоваться для определения пропорционального количества точек, которое должно быть сгенерировано в каждом подпространстве. Если сумма рангов оказывается близкой к нулю (меньше 0.0001), что может произойти, когда все подпространства имеют нулевой ранг, то всем подпространствам присваивается минимальный положительный ранг (1.0), чтобы обеспечить равномерное распределение точек. Затем, для каждого подпространства вычисляется количество точек, которые нужно сгенерировать в нем, пропорционально его "promisingRank" относительно общей суммы рангов.

Используется формула (subspaces[i].promisingRank / totalRank) * popSize, где popSize - требуемый размер популяции. Результат округляется до ближайшего целого числа. Количество точек ограничивается сверху, чтобы не превысить "popSize". Внутри каждого подпространства генерируется вычисленное количество точек, и для каждой точки генерируются "coords" координат, используя равномерное распределение в пределах границ подпространства. Для каждого измерения значение координаты ограничивается заданными минимальным и максимальным значениями и приводится к сетке с шагом "rangeStep[c]".

Если после распределения точек по подпространствам, общее количество сгенерированных точек меньше "popSize", оставшиеся точки генерируются равномерно по всему пространству поиска, используя границы всего пространства "rangeMin[c]", "rangeMax[c]", ограничения и приводятся к сетке с шагом "rangeStep[c]". Это гарантирует, что популяция всегда будет иметь размер "popSize".

//+----------------------------------------------------------------------------+
//| Генерация новой популяции                                                  |
//+----------------------------------------------------------------------------+
void C_AO_FBA::GenerateNewPopulation ()
{
  // Вычисляем сумму рангов всех подпространств
  double totalRank = 0.0;
  for (int i = 0; i < ArraySize (subspaces); i++)
  {
    totalRank += subspaces [i].promisingRank;
  }

  // Если все ранги равны 0, установим равномерное распределение
  if (totalRank <= 0.0001) // Проверка на приближенное равенство к нулю
  {
    for (int i = 0; i < ArraySize (subspaces); i++)
    {
      subspaces [i].promisingRank = 1.0;
    }
    totalRank = ArraySize (subspaces);
  }

  int points = 0;

  for (int i = 0; i < ArraySize (subspaces) && points < popSize; i++)
  {
    // Вычисляем количество точек для этого подпространства согласно формуле
    int pointsToGenerate = (int)MathRound ((subspaces [i].promisingRank / totalRank) * popSize);

    // Ограничение, чтобы не выйти за пределы
    pointsToGenerate = MathMin (pointsToGenerate, popSize - points);

    // Генерируем точки в этом подпространстве
    for (int j = 0; j < pointsToGenerate; j++)
    {
      // Создаем новую точку равномерно в пределах подпространства
      for (int c = 0; c < coords; c++)
      {
        a [points].c [c] = u.RNDfromCI (subspaces [i].min [c], subspaces [i].max [c]);
        a [points].c [c] = u.SeInDiSp (a [points].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      }

      points++;
      if (points >= popSize) break;
    }
  }

  // Если не все точки были сгенерированы, заполняем оставшиеся равномерно по всему пространству
  while (points < popSize)
  {
    for (int c = 0; c < coords; c++)
    {
      a [points].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]);
      a [points].c [c] = u.SeInDiSp (a [points].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
    points++;
  }
}
//——————————————————————————————————————————————————————————————————————————————

Метод "MutatePoints" класса "C_AO_FBA " предназначен для осуществления мутации точек в популяции и является частью процедуры алгоритма для повышения варьируемости решений и предотвращения застревания в локальных ловушках.

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

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

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

//+----------------------------------------------------------------------------+
//| Мутация точек в популяции                                                  |
//+----------------------------------------------------------------------------+
void C_AO_FBA::MutatePoints ()
{
  // Добавляем гауссовский шум к P3% случайно выбранных точек из новой популяции
  /*
  int numToMutate = (int)MathRound (popSize * P3 / 100.0);
  numToMutate = MathMax (1, MathMin (numToMutate, popSize));

  for (int i = 0; i < numToMutate; i++)
  {
    int index = u.RNDminusOne (popSize);

    // Добавляем шум к каждой координате
    for (int c = 0; c < coords; c++)
    {
      // Стандартное отклонение 10% от диапазона
      //double stdDev = (rangeMax [c] - rangeMin [c]) * 0.1;

      // Гауссовский шум с использованием метода Бокса-Мюллера
      //double noise = NormalRandom (0.0, stdDev);

      // Добавляем шум и ограничиваем значение
      a [index].c [c] += noise;
      a [index].c [c] = u.SeInDiSp (a [index].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
  */

  for (int p = 0; p < popSize; p++)
  {
    for (int c = 0; c < coords; c++)
    {
      if (u.RNDprobab () < P3)
      {
        a [p].c [c] = u.PowerDistribution (cB [c], rangeMin [c], rangeMax [c], 20);
        a [p].c [c] = u.SeInDiSp (a [p].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

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

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

//+----------------------------------------------------------------------------+
//| Сортировка по значению фитнес-функции                                      |
//+----------------------------------------------------------------------------+
void C_AO_FBA::SortByFitness (double &values [], int &indices [], int size, bool ascending = false)
{
  if (size > 1) QuickSort (values, indices, 0, size - 1, ascending);
}
//——————————————————————————————————————————————————————————————————————————————

Метод "QuickSort" реализует алгоритм быстрой сортировки для двух связанных массивов: "values" (массив значений) и "indices" (массив индексов). Он рекурсивно разделяет и сортирует массивы таким образом, чтобы сохранялось соответствие между значением и его исходным индексом. Параметры: массивы для сортировки, границы сортируемой области (low и high) и флаг "ascending", определяющий порядок сортировки.

//+----------------------------------------------------------------------------+
//| Алгоритм быстрой сортировки                                                |
//+----------------------------------------------------------------------------+
void C_AO_FBA::QuickSort (double &values [], int &indices [], int low, int high, bool ascending)
{
  if (low < high)
  {
    int pi = Partition (values, indices, low, high, ascending);

    QuickSort (values, indices, low, pi - 1, ascending);
    QuickSort (values, indices, pi + 1, high, ascending);
  }
}
//——————————————————————————————————————————————————————————————————————————————

Метод "Partition" является ключевой частью алгоритма быстрой сортировки. Его задача — выбрать опорный элемент и перераспределить элементы массива "indices" таким образом, чтобы все элементы, "меньшие" опорного (или "большие", в зависимости от порядка сортировки), оказались слева от него, а "большие" ("меньшие") — справа. "Меньше" и "больше" определяются относительно значений в массиве "values", на которые указывают индексы из "indices".

//+----------------------------------------------------------------------------+
//| Функция разделения для QuickSort                                           |
//+----------------------------------------------------------------------------+
int C_AO_FBA::Partition (double &values [], int &indices [], int low, int high, bool ascending)
{
  double pivot = values [indices [high]];
  int i = low - 1;

  for (int j = low; j < high; j++)
  {
    bool condition = ascending ? (values [indices [j]] < pivot) : (values [indices [j]] > pivot);
    if (condition)
    {
      i++;
      // Обмен значениями
      int temp = indices [i];
      indices [i] = indices [j];
      indices [j] = temp;
    }
  }

  // Обмен значениями
  int temp = indices [i + 1];
  indices [i + 1] = indices [high];
  indices [high] = temp;

  return i + 1;
}
//——————————————————————————————————————————————————————————————————————————————

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

Результат алгоритм показывает хороший.

FBA|Fractal-Based Algorithm|50.0|60.0|30.0|0.8|10.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.7900044352090774
25 Hilly's; Func runs: 10000; result: 0.6513385092404853
500 Hilly's; Func runs: 10000; result: 0.2896548031738138
=============================
5 Forest's; Func runs: 10000; result: 0.8715768614282637
25 Forest's; Func runs: 10000; result: 0.5682316842631675
500 Forest's; Func runs: 10000; result: 0.18876552479611478
=============================
5 Megacity's; Func runs: 10000; result: 0.6107692307692306
25 Megacity's; Func runs: 10000; result: 0.46061538461538465
500 Megacity's; Func runs: 10000; result: 0.12398461538461655
=============================
All score: 4.55494 (50.61%)

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

Hilly

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

Forest

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

Megacity

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

По результатам тестирования алгоритм FBA занимает 29 место в нашей рейтинговой таблице.

№	AO	Description	Hilly			Hilly Final	Forest			Forest Final	Megacity (discrete)			Megacity Final	Final Result	% of MAX
№	AO	Description	10 p (5 F)	50 p (25 F)	1000 p (500 F)	Hilly Final	10 p (5 F)	50 p (25 F)	1000 p (500 F)	Forest Final	10 p (5 F)	50 p (25 F)	1000 p (500 F)	Megacity Final	Final Result	% of MAX
1	ANS	across neighbourhood search	0,94948	0,84776	0,43857	2,23581	1,00000	0,92334	0,39988	2,32323	0,70923	0,63477	0,23091	1,57491	6,134	68,15
2	CLA	code lock algorithm (joo)	0,95345	0,87107	0,37590	2,20042	0,98942	0,91709	0,31642	2,22294	0,79692	0,69385	0,19303	1,68380	6,107	67,86
3	AMOm	animal migration ptimization M	0,90358	0,84317	0,46284	2,20959	0,99001	0,92436	0,46598	2,38034	0,56769	0,59132	0,23773	1,39675	5,987	66,52
4	(P+O)ES	(P+O) evolution strategies	0,92256	0,88101	0,40021	2,20379	0,97750	0,87490	0,31945	2,17185	0,67385	0,62985	0,18634	1,49003	5,866	65,17
5	CTA	comet tail algorithm (joo)	0,95346	0,86319	0,27770	2,09435	0,99794	0,85740	0,33949	2,19484	0,88769	0,56431	0,10512	1,55712	5,846	64,96
6	TETA	time evolution travel algorithm (joo)	0,91362	0,82349	0,31990	2,05701	0,97096	0,89532	0,29324	2,15952	0,73462	0,68569	0,16021	1,58052	5,797	64,41
7	SDSm	stochastic diffusion search M	0,93066	0,85445	0,39476	2,17988	0,99983	0,89244	0,19619	2,08846	0,72333	0,61100	0,10670	1,44103	5,709	63,44
8	BOAm	billiards optimization algorithm M	0,95757	0,82599	0,25235	2,03590	1,00000	0,90036	0,30502	2,20538	0,73538	0,52523	0,09563	1,35625	5,598	62,19
9	AAm	archery algorithm M	0,91744	0,70876	0,42160	2,04780	0,92527	0,75802	0,35328	2,03657	0,67385	0,55200	0,23738	1,46323	5,548	61,64
10	ESG	evolution of social groups (joo)	0,99906	0,79654	0,35056	2,14616	1,00000	0,82863	0,13102	1,95965	0,82333	0,55300	0,04725	1,42358	5,529	61,44
11	SIA	simulated isotropic annealing (joo)	0,95784	0,84264	0,41465	2,21513	0,98239	0,79586	0,20507	1,98332	0,68667	0,49300	0,09053	1,27020	5,469	60,76
12	ACS	artificial cooperative search	0,75547	0,74744	0,30407	1,80698	1,00000	0,88861	0,22413	2,11274	0,69077	0,48185	0,13322	1,30583	5,226	58,06
13	DA	dialectical algorithm	0,86183	0,70033	0,33724	1,89940	0,98163	0,72772	0,28718	1,99653	0,70308	0,45292	0,16367	1,31967	5,216	57,95
14	BHAm	black hole algorithm M	0,75236	0,76675	0,34583	1,86493	0,93593	0,80152	0,27177	2,00923	0,65077	0,51646	0,15472	1,32195	5,196	57,73
15	ASO	anarchy society optimization	0,84872	0,74646	0,31465	1,90983	0,96148	0,79150	0,23803	1,99101	0,57077	0,54062	0,16614	1,27752	5,178	57,54
16	RFO	royal flush optimization (joo)	0,83361	0,73742	0,34629	1,91733	0,89424	0,73824	0,24098	1,87346	0,63154	0,50292	0,16421	1,29867	5,089	56,55
17	AOSm	atomic orbital search M	0,80232	0,70449	0,31021	1,81702	0,85660	0,69451	0,21996	1,77107	0,74615	0,52862	0,14358	1,41835	5,006	55,63
18	TSEA	turtle shell evolution algorithm (joo)	0,96798	0,64480	0,29672	1,90949	0,99449	0,61981	0,22708	1,84139	0,69077	0,42646	0,13598	1,25322	5,004	55,60
19	DE	differential evolution	0,95044	0,61674	0,30308	1,87026	0,95317	0,78896	0,16652	1,90865	0,78667	0,36033	0,02953	1,17653	4,955	55,06
20	SRA	successful restaurateur algorithm (joo)	0,96883	0,63455	0,29217	1,89555	0,94637	0,55506	0,19124	1,69267	0,74923	0,44031	0,12526	1,31480	4,903	54,48
21	CRO	chemical reaction optimisation	0,94629	0,66112	0,29853	1,90593	0,87906	0,58422	0,21146	1,67473	0,75846	0,42646	0,12686	1,31178	4,892	54,36
22	BIO	blood inheritance optimization (joo)	0,81568	0,65336	0,30877	1,77781	0,89937	0,65319	0,21760	1,77016	0,67846	0,47631	0,13902	1,29378	4,842	53,80
23	BSA	bird swarm algorithm	0,89306	0,64900	0,26250	1,80455	0,92420	0,71121	0,24939	1,88479	0,69385	0,32615	0,10012	1,12012	4,809	53,44
24	HS	harmony search	0,86509	0,68782	0,32527	1,87818	0,99999	0,68002	0,09590	1,77592	0,62000	0,42267	0,05458	1,09725	4,751	52,79
25	SSG	saplings sowing and growing	0,77839	0,64925	0,39543	1,82308	0,85973	0,62467	0,17429	1,65869	0,64667	0,44133	0,10598	1,19398	4,676	51,95
26	BCOm	bacterial chemotaxis optimization M	0,75953	0,62268	0,31483	1,69704	0,89378	0,61339	0,22542	1,73259	0,65385	0,42092	0,14435	1,21912	4,649	51,65
27	ABO	african buffalo optimization	0,83337	0,62247	0,29964	1,75548	0,92170	0,58618	0,19723	1,70511	0,61000	0,43154	0,13225	1,17378	4,634	51,49
28	(PO)ES	(PO) evolution strategies	0,79025	0,62647	0,42935	1,84606	0,87616	0,60943	0,19591	1,68151	0,59000	0,37933	0,11322	1,08255	4,610	51,22
29	FBA	fractal-based Algorithm	0,79000	0,65134	0,28965	1,73099	0,87158	0,56823	0,18877	1,62858	0,61077	0,46062	0,12398	1,19537	4,555	50,61
30	TSm	tabu search M	0,87795	0,61431	0,29104	1,78330	0,92885	0,51844	0,19054	1,63783	0,61077	0,38215	0,12157	1,11449	4,536	50,40
31	BSO	brain storm optimization	0,93736	0,57616	0,29688	1,81041	0,93131	0,55866	0,23537	1,72534	0,55231	0,29077	0,11914	0,96222	4,498	49,98
32	WOAm	wale optimization algorithm M	0,84521	0,56298	0,26263	1,67081	0,93100	0,52278	0,16365	1,61743	0,66308	0,41138	0,11357	1,18803	4,476	49,74
33	AEFA	artificial electric field algorithm	0,87700	0,61753	0,25235	1,74688	0,92729	0,72698	0,18064	1,83490	0,66615	0,11631	0,09508	0,87754	4,459	49,55
34	AEO	artificial ecosystem-based optimization algorithm	0,91380	0,46713	0,26470	1,64563	0,90223	0,43705	0,21400	1,55327	0,66154	0,30800	0,28563	1,25517	4,454	49,49
35	ACOm	ant colony optimization M	0,88190	0,66127	0,30377	1,84693	0,85873	0,58680	0,15051	1,59604	0,59667	0,37333	0,02472	0,99472	4,438	49,31
36	BFO-GA	bacterial foraging optimization - ga	0,89150	0,55111	0,31529	1,75790	0,96982	0,39612	0,06305	1,42899	0,72667	0,27500	0,03525	1,03692	4,224	46,93
37	SOA	simple optimization algorithm	0,91520	0,46976	0,27089	1,65585	0,89675	0,37401	0,16984	1,44060	0,69538	0,28031	0,10852	1,08422	4,181	46,45
38	ABHA	artificial bee hive algorithm	0,84131	0,54227	0,26304	1,64663	0,87858	0,47779	0,17181	1,52818	0,50923	0,33877	0,10397	0,95197	4,127	45,85
39	ACMO	atmospheric cloud model optimization	0,90321	0,48546	0,30403	1,69270	0,80268	0,37857	0,19178	1,37303	0,62308	0,24400	0,10795	0,97503	4,041	44,90
40	ADAMm	adaptive moment estimation M	0,88635	0,44766	0,26613	1,60014	0,84497	0,38493	0,16889	1,39880	0,66154	0,27046	0,10594	1,03794	4,037	44,85
41	CGO	chaos game optimization	0,57256	0,37158	0,32018	1,26432	0,61176	0,61931	0,62161	1,85267	0,37538	0,21923	0,19028	0,78490	3,902	43,35
42	ATAm	artificial tribe algorithm M	0,71771	0,55304	0,25235	1,52310	0,82491	0,55904	0,20473	1,58867	0,44000	0,18615	0,09411	0,72026	3,832	42,58
43	CROm	coral reefs optimization M	0,78512	0,46032	0,25958	1,50502	0,86688	0,35297	0,16267	1,38252	0,63231	0,26738	0,10734	1,00703	3,895	43,27
44	CFO	central force optimization	0,60961	0,54958	0,27831	1,43750	0,63418	0,46833	0,22541	1,32792	0,57231	0,23477	0,09586	0,90294	3,668	40,76
45	ASHA	artificial showering algorithm	0,89686	0,40433	0,25617	1,55737	0,80360	0,35526	0,19160	1,35046	0,47692	0,18123	0,09774	0,75589	3,664	40,71
	RW	neuroboids optimization algorithm 2(joo)	0,48754	0,32159	0,25781	1,06694	0,37554	0,21944	0,15877	0,75375	0,27969	0,14917	0,09847	0,52734	2,348	26,09

Выводы

Версия алгоритма FBA с модифицированной мутацией, с результатами 50.61%, демонстрирует двукратное улучшение эффективности по сравнению с результатами оригинальной версии.

FBA|Fractal-Based Algorithm|50.0|60.0|30.0|5.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.4780639253626462
25 Hilly's; Func runs: 10000; result: 0.3222029113692554
500 Hilly's; Func runs: 10000; result: 0.25720991988937014
=============================
5 Forest's; Func runs: 10000; result: 0.36567166223346415
25 Forest's; Func runs: 10000; result: 0.22043205527307377
500 Forest's; Func runs: 10000; result: 0.15869146061036057
=============================
5 Megacity's; Func runs: 10000; result: 0.2861538461538461
25 Megacity's; Func runs: 10000; result: 0.15015384615384622
500 Megacity's; Func runs: 10000; result: 0.09838461538461622
=============================
All score: 2.33696 (25.97%)

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

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

Tab

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

chart

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

Плюсы и минусы алгоритма FBA:

Плюсы:

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

Минусы:

Большой разброс результатов на функциях малой размерности.
Интересная, но достаточно "слабая" базовая идея алгоритма.

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

github: https://github.com/JQSakaJoo/Population-optimization-algorithms-MQL5

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

#	Имя	Тип	Описание
1	#C_AO.mqh	Включаемый файл	Родительский класс популяционных алгоритмов оптимизации
2	#C_AO_enum.mqh	Включаемый файл	Перечисление популяционных алгоритмов оптимизации
3	TestFunctions.mqh	Включаемый файл	Библиотека тестовых функций
4	TestStandFunctions.mqh	Включаемый файл	Библиотека функций тестового стенда
5	Utilities.mqh	Включаемый файл	Библиотека вспомогательных функций
6	CalculationTestResults.mqh	Включаемый файл	Скрипт для расчета результатов в сравнительную таблицу
7	Testing AOs.mq5	Скрипт	Единый испытательный стенд для всех популяционных алгоритмов оптимизации
8	Simple use of population optimization algorithms.mq5	Скрипт	Простой пример использования популяционных алгоритмов оптимизации без визуализации
9	Test_FBA.mq5	Скрипт	Испытательный стенд для FBA

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

Загрузить ZIP

FBA.ZIP (274.96 KB)

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

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

Перейти к обсуждению на форуме трейдеров

Скрытые марковские модели в торговых системах на машинном обучении

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

Возможности Мастера MQL5, которые вам нужно знать (Часть 41): Сети Deep-Q

Сеть Deep-Q (Deep-Q-Network) — это алгоритм обучения с подкреплением, который вовлекает нейронные сети в прогнозирование следующего значения Q и идеального действия в процессе обучения модуля машинного обучения. Мы уже рассматривали альтернативный алгоритм обучения с подкреплением — Q-обучение. Таким образом, в данной статье представлен еще один пример того, как многослойный перцептрон (multi-layer perceptron, MLP), обученный с помощью обучения с подкреплением, может использоваться в пользовательском классе сигналов.

Нейросети в трейдинге: Прогнозирование временных рядов при помощи адаптивного модального разложения (Окончание)

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

Арбитражный трейдинг Forex: Матричная торговая система на возврат к справедливой стоимости с ограничением риска

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