Алгоритм оптимизации на основе мозгового штурма — Brain Storm Optimization (Часть II): Многомодальность

MetaTrader 5 — Примеры | 19 апреля 2024, 09:18

244

Andrey Dik

Содержание:

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

1. Введение

В первой части статьи мы окунулись в мир оптимизации с алгоритмом BSO (Brain Storm Optimization), где раскрывали основные принципы этой инновационной методики, вдохновленной мозговым штурмом. Мы не только изучили его логическую структуру, но и погрузились в обсуждение методов кластеризации, K-Means и K-Means++. Алгоритм Brain Storm Optimization (BSO) представляет собой метод оптимизации, который включает в себя фазы генерации и оценки идей в групповой деятельности. Этот алгоритм внес вклад в область оптимизации в совокупности с методами кластеризации. Кластеризация позволяет выявить группы данных схожих элементов, что помогает BSO находить оптимальные решения. Применение метода мутации позволяет алгоритму обходить препятствия в пространстве поиска решений и искать более эффективные пути к оптимуму.

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

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

Кратко обозначим ключевые моменты в логике алгоритма BSO:

Кластеризация.
Смещение кластеров.
Выбор идей из кластеров: центроидов кластеров или идей из кластеров.
Слияние выбранных идей.
Мутация полученных на предыдущих этапов идей.
Отбор идей для этапов 2, 3, 4. Помещение новых идей в родительскую популяцию и сортировка.

Переходим к описанию кода алгоритма BSO.

Напишем структуру агента алгоритма "S_BSO_Agent", которая используется для описания каждого агента в алгоритме BSO.

1. Структура содержит следующие поля:

c[] - массив для хранения координат агента.
f - переменная для хранения оценки (фитнеса) агента.
label - переменная для хранения метки принадлежности к кластеру.

2. Init - метод структуры "S_BSO_Agent", который инициализирует поля структуры. Он принимает целочисленный аргумент "coords", который используется для изменения размера массива координат "c" с помощью функции "ArrayResize".
3. f = -DBL_MAX - устанавливает начальное значение переменной "f" равным минимально возможной величине числа типа double.
4. label = -1 - устанавливает начальное значение переменной "label" равным -1, что означает, что агент не принадлежит ни к одному кластеру.

Этот код представляет собой базовую структуру данных для агентов в алгоритме оптимизации BSO и инициализирует их поля при создании нового агента.

//——————————————————————————————————————————————————————————————————————————————
struct S_BSO_Agent
{
    double c     []; //coordinates
    double f;        //fitness
    int    label;    //cluster membership label

    void Init (int coords)
    {
      ArrayResize (c,     coords);
      f     = -DBL_MAX;
      label = -1;
    }
};
//——————————————————————————————————————————————————————————————————————————————

Алгоритм кластеризации K-Means и K-Means++ мы уже подробно разобрали в предыдущей статье и здесь на этом останавливаться не будем.

Переходим к описанию кода класса "C_AO_BSO", который является наследником базового класса популяционных алгоритмов "C_AO" и содержит следующие поля и методы:

1. Публичные поля:

ao_name - имя алгоритма оптимизации.
ao_desc - описание алгоритма оптимизации.
ao_link - ссылка на статью об алгоритме оптимизации.
popSize - размер популяции.
parentPopSize - размер родительской популяции.
clustersNumb - количество кластеров.
p_Replace - вероятность замены.
p_One - вероятность одиночного выбора.
p_One_center - вероятность выбора одного центра либо индивида в выбранном кластере.
p_Two_center - вероятность выбора двух центров либо двух индивидуумов в выбранном кластере.
k_Mutation - коэффициент мутации.
distribCoeff - коэффициент распределения.
agent - массив агентов.
parents - массив родителей.
clusters - массив кластеров.
km - объект класса KMeans.

2. Методы:

SetParams - метод для установки параметров алгоритма.
Init - метод для инициализации алгоритма. Принимает минимальный и максимальный диапазоны поиска, шаг поиска и количество эпох.
Moving - метод для перемещения агентов.
Revision - метод для ревизии агентов.

3. Приватные поля:

parentsTemp - временный массив родителей.
epochs - максимальное количество эпох.
epochsNow - текущая эпоха.

//——————————————————————————————————————————————————————————————————————————————
class C_AO_BSO : public C_AO
{
  public: //--------------------------------------------------------------------
  ~C_AO_BSO () { }
  C_AO_BSO ()
  {
    ao_name = "BSO";
    ao_desc = "Brain Storm Optimization";
    ao_link = "https://www.mql5.com/ru/articles/14622";

    popSize        = 25;   //population size

    parentPopSize  = 50;   //parent population size;
    clustersNumb   = 5;    //number of clusters
    p_Replace      = 0.1;  //replace probability
    p_One          = 0.5;  //probability of choosing one
    p_One_center   = 0.3;  //probability of choosing one center
    p_Two_center   = 0.2;  //probability of choosing two centers
    k_Mutation     = 20.0; //mutation coefficient
    distribCoeff   = 1.0;  //distribution coefficient

    ArrayResize (params, 9);

    params [0].name = "popSize";       params [0].val  = popSize;

    params [1].name = "parentPopSize"; params [1].val  = parentPopSize;
    params [2].name = "clustersNumb";  params [2].val  = clustersNumb;
    params [3].name = "p_Replace";     params [3].val  = p_Replace;
    params [4].name = "p_One";         params [4].val  = p_One;
    params [5].name = "p_One_center";  params [5].val  = p_One_center;
    params [6].name = "p_Two_center";  params [6].val  = p_Two_center;
    params [7].name = "k_Mutation";    params [7].val  = k_Mutation;
    params [8].name = "distribCoeff";  params [8].val  = distribCoeff;
  }

  void SetParams ()
  {
    popSize       = (int)params [0].val;

    parentPopSize = (int)params [1].val;
    clustersNumb  = (int)params [2].val;
    p_Replace     = params      [3].val;
    p_One         = params      [4].val;
    p_One_center  = params      [5].val;
    p_Two_center  = params      [6].val;
    k_Mutation    = params      [7].val;
    distribCoeff  = params      [8].val;
  }

  bool Init (const double &rangeMinP  [], //minimum search range
             const double &rangeMaxP  [], //maximum search range
             const double &rangeStepP [], //step search
             const int     epochsP = 0);  //number of epochs

  void Moving    ();
  void Revision  ();
  void Injection (const int popPos, const int coordPos, const double value);

  //----------------------------------------------------------------------------
  int    parentPopSize; //parent population size;
  int    clustersNumb;  //number of clusters
  double p_Replace;     //replace probability
  double p_One;         //probability of choosing one
  double p_One_center;  //probability of choosing one center
  double p_Two_center;  //probability of choosing two centers
  double k_Mutation;    //mutation coefficient
  double distribCoeff;  //distribution coefficient

  S_BSO_Agent  agent   [];
  S_BSO_Agent  parents [];

  S_Clusters   clusters [];
  S_BSO_KMeans km;

  private: //-------------------------------------------------------------------
  S_BSO_Agent  parentsTemp [];
  int          epochs;
  int          epochsNow;
};
//——————————————————————————————————————————————————————————————————————————————

Метод "Init" класса "C_AO_BSO" выполняет следующие действия для инициализации алгоритма оптимизации:

Проверка инициализации. Сначала вызывается метод "StandardInit" с параметрами диапазона поиска и шага. Если "StandardInit" возвращает "false", то инициализация прерывается, и метод "Init" возвращает "false".
Инициализация агентов. Размер массива "agent" изменяется до "popSize", и для каждого агента вызывается метод "Init" с параметром "coords", определяющим количество координат.
Инициализация кластеров. Размер массива "clusters" изменяется до "clustersNumb" (максимальное количество кластеров), и для каждого кластера вызывается метод "Init".
Инициализация родителей. Размеры массивов "parents" и "parentsTemp" изменяются до "parentPopSize + popSize", и для каждого родителя вызывается метод "Init". Массивы должны иметь такой размер, что бы в него поместились родительская и дочерняя популяции для последующей сортировки.
Установка эпох. Значения "epochs" и "epochsNow" устанавливаются в соответствии с переданным параметром "epochsP" и "0" соответственно.

Метод возвращает "true", если все шаги инициализации выполнены успешно. Это подготавливает алгоритм к выполнению оптимизации на заданное количество эпох.

//——————————————————————————————————————————————————————————————————————————————
bool C_AO_BSO::Init (const double &rangeMinP  [], //minimum search range
                     const double &rangeMaxP  [], //maximum search range
                     const double &rangeStepP [], //step search
                     const int     epochsP = 0)   //number of epochs
{
  if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false;

  //----------------------------------------------------------------------------
  ArrayResize (agent, popSize);
  for (int i = 0; i < popSize; i++) agent [i].Init (coords);

  ArrayResize (clusters, clustersNumb);
  for (int i = 0; i < clustersNumb; i++) clusters [i].Init (coords);

  ArrayResize (parents,     parentPopSize + popSize);
  ArrayResize (parentsTemp, parentPopSize + popSize);

  for (int i = 0; i < parentPopSize + popSize; i++)
  {
    parents     [i].Init (coords);
    parentsTemp [i].Init (coords);
  }

  epochs    = epochsP;
  epochsNow = 0;

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

Метод "Moving" класса "C_AO_BSO" используется для перемещения агентов в процессе оптимизации. Метод выполняет следующие действия:

Увеличивается значение текущей эпохи ("epochsNow++").
Если "revision" равно "false", происходит инициализация координат агентов с использованием случайных значений в заданных диапазонах. Затем метод завершает работу.
Если "revision" не равно "false", для каждого агента происходит вычисление новых координат с использованием формул и вероятностей.
Используются различные математические вычисления, случайные числа и вероятности для определения новых координат агентов.
Новые координаты вычисляются в соответствии с условиями и вероятностями.
Новые координаты устанавливаются с использованием метода "SeInDiSp" для коррекции значений в соответствии с диапазонами поиска и шагами.
Происходит генерация новой идеи, которая заменяет выбранный центр кластера (смещение центра кластера), если выполняется условие "u.RNDprobab () < p_Replace".
Выбирается идея из одного кластера, если выполняется условие "u.RNDprobab () < p_One".
Выбираются идеи из двух кластеров, если не выполняется условие "u.RNDprobab () < p_One".
Происходит мутация координат агентов.
Сохраняются новые координаты агентов.

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

Генерация новой идеи. С каждой новой эпохой агенты более тщательно исследуют окрестности найденного глобального решения согласно коэффициенту "p_Replace", стремясь приблизиться к глобальному оптимуму и смещая центроиды кластеров.
Исследование окрестностей одного кластера. С учётом коэффициента "p_One" агенты исследуют окрестности одного случайно выбранного кластера. Таким образом, продолжается исследование всех областей, где находятся агенты в популяции.
Выбор идей из двух кластеров. Если не выполняется условие "u.RNDprobab () < p_One", выбираются идеи из двух случайно выбранных кластеров.
Мутация. Координаты агентов подвергаются мутации, что обеспечивает разнообразие в популяции и помогает избегать преждевременной сходимости к локальным оптимумам.
Сохранение агентов. После всех операций новые координаты агентов сохраняются для следующей итерации.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_BSO::Moving ()
{
  epochsNow++;

  //----------------------------------------------------------------------------
  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]);

        agent [i].c [c] = a [i].c [c];
      }
    }

    return;
  }

  //----------------------------------------------------------------------------
  //----------------------------------------------------------------------------
  int    cIndx_1    = 0;  //индекс в списке непустых кластеров
  int    iIndx_1    = 0;  //индекс в списке идей в кластере
  int    cIndx_2    = 0;  //индекс в списке непустых кластеров
  int    iIndx_2    = 0;  //индекс в списке идей в кластере
  double min        = 0.0;
  double max        = 0.0;
  double dist       = 0.0;
  double val        = 0.0;
  double X1         = 0.0;
  double X2         = 0.0;
  int    clListSize = 0;
  int    clustList [];
  ArrayResize (clustList, 0, clustersNumb);

  //----------------------------------------------------------------------------
  //составим список непустых кластеров
  for (int cl = 0; cl < clustersNumb; cl++)
  {
    if (clusters [cl].count > 0)
    {
      clListSize++;
      ArrayResize (clustList, clListSize);
      clustList [clListSize - 1] = cl;
    }
  }

  for (int i = 0; i < popSize; i++)
  {
    //==========================================================================
    //генерация новой идеи, которая заменяет выбранный центр кластера (смещение центра кластера)
    if (u.RNDprobab () < p_Replace)
    {
      cIndx_1 = u.RNDminusOne (clListSize);

      for (int c = 0; c < coords; c++)
      {
        val = clusters [clustList [cIndx_1]].centroid [c];

        dist = (rangeMax [c] - rangeMin [c]) * 0.8;

        min = val - dist; if (min < rangeMin [c]) min = rangeMin [c];
        max = val + dist; if (max > rangeMax [c]) max = rangeMax [c];

        val = u.GaussDistribution (val, min, max, 3);
        val = u.SeInDiSp  (val, rangeMin [c], rangeMax [c], rangeStep [c]);

        clusters [clustList [cIndx_1]].centroid [c] = val;
      }
    }

    //==========================================================================
    //выбирается идея из одного кластера
    if (u.RNDprobab () < p_One)
    {
      cIndx_1 = u.RNDminusOne (clListSize);

      //------------------------------------------------------------------------
      if (u.RNDprobab () < p_One_center) //выбирается центр кластера
      {
        for (int c = 0; c < coords; c++)
        {
          a [i].c [c] = clusters [clustList [cIndx_1]].centroid [c];
        }
      }
      //------------------------------------------------------------------------
      else                               //случайная идея из этого кластера
      {
        iIndx_1 = u.RNDminusOne (clusters [clustList [cIndx_1]].count);

        for (int c = 0; c < coords; c++)
        {
          a [i].c [c] = parents [clusters [clustList [cIndx_1]].ideasList [iIndx_1]].c [c];
        }
      }
    }
    //==========================================================================
    //выбираются идеи из двух кластеров
    else
    {
      if (clListSize == 1)
      {
        cIndx_1 = 0;
        cIndx_2 = 0;
      }
      else
      {
        if (clListSize == 2)
        {
          cIndx_1 = 0;
          cIndx_2 = 1;
        }
        else
        {
          cIndx_1 = u.RNDminusOne (clListSize);

          do
          {
            cIndx_2 = u.RNDminusOne (clListSize);
          }
          while (cIndx_1 == cIndx_2);
        }
      }

      //------------------------------------------------------------------------
      if (u.RNDprobab () < p_Two_center) //выбрали два центра кластеров
      {
        for (int c = 0; c < coords; c++)
        {
          X1 = clusters [clustList [cIndx_1]].centroid [c];
          X2 = clusters [clustList [cIndx_2]].centroid [c];

          a [i].c [c] = u.RNDfromCI (X1, X2);
        }
      }
      //------------------------------------------------------------------------
      else //две идеи из двух выбранных кластеров
      {
        iIndx_1 = u.RNDminusOne (clusters [clustList [cIndx_1]].count);
        iIndx_2 = u.RNDminusOne (clusters [clustList [cIndx_2]].count);

        for (int c = 0; c < coords; c++)
        {
          X1 = parents [clusters [clustList [cIndx_1]].ideasList [iIndx_1]].c [c];
          X2 = parents [clusters [clustList [cIndx_2]].ideasList [iIndx_2]].c [c];

          a [i].c [c] = u.RNDfromCI (X1, X2);
        }
      }
    }

    //==========================================================================
    //Мутация
    for (int c = 0; c < coords; c++)
    {
      int x = (int)u.Scale (epochsNow, 1, epochs, 1, 200);

      double ξ = (1.0 / (1.0 + exp (-((100 - x) / k_Mutation))));// * u.RNDprobab ();

      double dist = (rangeMax [c] - rangeMin [c]) * distribCoeff * ξ;
      double min = a [i].c [c] - dist; if (min < rangeMin [c]) min = rangeMin [c];
      double max = a [i].c [c] + dist; if (max > rangeMax [c]) max = rangeMax [c];

      val = a [i].c [c];

      a [i].c [c] = u.GaussDistribution (val, min, max, 8);
    }

    //Сохраним агента-----------------------------------------------------------
    for (int c = 0; c < coords; c++)
    {
      val = u.SeInDiSp  (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);

      a     [i].c [c] = val;
      agent [i].c [c] = val;
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Основная задача метода "Revision" класса "C_AO_BSO" заключается в обновлении глобального решения и построении кластеров решений. Метод выполняет следующие действия:

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

//——————————————————————————————————————————————————————————————————————————————
void C_AO_BSO::Revision ()
{
  //получить приспособленность--------------------------------------------------
  for (int i = 0; i < popSize; i++)
  {
    agent [i].f = a [i].f;
  }

  //перенести новые идеи в популяцию--------------------------------------------
  for (int i = parentPopSize; i < parentPopSize + popSize; i++)
  {
    parents [i] = agent [i - parentPopSize];
  }

  //отсортировать родительскую популяцию----------------------------------------
  u.Sorting (parents, parentsTemp, parentPopSize + popSize);

  if (parents [0].f > fB)
  {
    fB = parents [0].f;
    ArrayCopy (cB, parents [0].c, 0, 0, WHOLE_ARRAY);
  }

  //выполнить кластеризацию-----------------------------------------------------
  if (!revision)
  {
    km.KMeansInit (parents, parentPopSize, clusters);
    revision = true;
  }

  km.KMeansInit (parents, parentPopSize, clusters);
  km.KMeans     (parents, parentPopSize, clusters);

  //Назначить лучшее решение кластера центром кластера--------------------------
  for (int cl = 0; cl < clustersNumb; cl++)
  {
    clusters [cl].f = -DBL_MAX;

    if (clusters [cl].count > 0)
    {
      for (int p = 0; p < parentPopSize; p++)
      {
        if (parents [p].label == cl)
        {
          if (parents [p].f > clusters [cl].f)
          {
            clusters [cl].f = parents [p].f;
            ArrayCopy (clusters [cl].centroid, parents [p].c, 0, 0, WHOLE_ARRAY);
          }
        }
      }
    }
  }
}//——————————————————————————————————————————————————————————————————————————————

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

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

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

Функция "FitnessDistance" вычисляет расстояние между агентом и центроидом кластера, учитывая как расстояние, так и разницу в фитнес-функции между ними. Это делается путем вычисления взвешенной суммы расстояния и абсолютного значения разницы между фитнес-функцией агента и центроида. Вес "alpha" определяет относительную важность расстояния по сравнению с разницей в фитнес-функции.

//——————————————————————————————————————————————————————————————————————————————
double FitnessDistance (S_BSO_Agent &data, S_Cluster &clust, double alpha)
{
  double distance = VectorDistance (data.c, clust.centroid);
  double fitness_diff = fabs (data.f - clust.f);
  return alpha * distance + (1 - alpha) * fitness_diff;
}
//——————————————————————————————————————————————————————————————————————————————

Метод "KMeans" дополним параметром "alpha":

void KMeans (S_BSO_Agent &data [], int dataSizeClust, S_Cluster &clust [], double alpha)

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

// Обновление центроидов
double sum_c [];
ArrayResize (sum_c, ArraySize (data [0].c));
double sum_f = 0.0;

for (int cl = 0; cl < nClusters; cl++)
{
  ArrayInitialize (sum_c, 0.0);

  clust [cl].count = 0;
  ArrayResize (clust [cl].ideasList, 0);
  sum_f = -DBL_MAX;

  for (int d = 0; d < dataSizeClust; d++)
  {
    if (data [d].label == cl)
    {
      for (int k = 0; k < ArraySize (data [d].c); k++)
      {
        sum_c [k] += data [d].c [k];
      }

      if (data [d].f > sum_f) sum_f = data [d].f;

      clust [cl].count++;
      ArrayResize (clust [cl].ideasList, clust [cl].count);
      clust [cl].ideasList [clust [cl].count - 1] = d;
    }
  }

  if (clust [cl].count > 0)
  {
    for (int k = 0; k < ArraySize (sum_c); k++)
    {
      clust [cl].centroid [k] = sum_c [k] / clust [cl].count;
    }
  }
}

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

Если методы K-Means и K-Means++ не дали желаемых результатов, можно попробовать рассмотреть другие методы кластеризации:

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

2. Иерархическая кластеризация (Hierarchical Clustering), метод строит иерархию кластеров, где каждый кластер связан с двумя ближайшими кластерами. Иерархическая кластеризация может быть агломеративной (снизу вверх) или дивизионной (сверху вниз).

3. Смесь Гауссовых моделей (GMM), эта статистическая модель предполагает, что все наблюдаемые данные генерируются из смеси нескольких Гауссовых распределений, параметры которых неизвестны. Каждый кластер соответствует одному из этих распределений.

4. Спектральная кластеризация (Spectral Clustering), метод использует собственные векторы матрицы сходства для уменьшения размерности данных перед кластеризацией в низкоразмерном пространстве.

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

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

Вывод в принт результатов работы алгоритма BSO:

BSO|Brain Storm Optimization|25.0|50.0|5.0|0.1|0.5|0.3|0.2|20.0|1.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.9301770731803266
25 Hilly's; Func runs: 10000; result: 0.5801719580773876
500 Hilly's; Func runs: 10000; result: 0.30916005647304245
=============================
5 Forest's; Func runs: 10000; result: 0.929981802038364
25 Forest's; Func runs: 10000; result: 0.5907047167619348
500 Forest's; Func runs: 10000; result: 0.2477599978259004
=============================
5 Megacity's; Func runs: 10000; result: 0.5246153846153847
25 Megacity's; Func runs: 10000; result: 0.2784615384615384
500 Megacity's; Func runs: 10000; result: 0.1253384615384627
=============================
All score: 4.51637 (50.18%)

Результаты тестирования алгоритма на тестовых функциях (общий результат (All score) 4.51637 соответствует 50,18% от максимального возможного значения) показывают, что при использовании параметров, указанных в первой строке принтов, получаются достаточно хорошие результаты. Значения результатов функций находятся в диапазоне от 0,125 для 1000 оптимизируемых параметров и до 0,93 для 10 соответственно, что говорит о достаточно успешной работе алгоритма при поиске оптимальных решений.

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

Hilly

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

Forest

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

Megacity

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

Возлагались большие надежды на этот алгоритм и я надеялся увидеть его на первой позиции рейтинговой таблицы. Ведь это первый раз, когда метод кластеризации был применен мной в сочетании с методом мутации, которые должны были показать уникальные результаты алгоритма. И я был несколько разочарован, увидев, что алгоритм занял место только в верхней части рейтинговой таблицы, но не в числе лидеров. Хотелось бы отметить, что BSO демонстрирует отличные результаты на функциях Forest и Megacity c 1000 параметров, которые вполне достойны лидеров таблицы.

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

№	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	BGA	binary genetic algorithm	0,99992	0,99484	0,50483	2,49959	1,00000	0,99975	0,32054	2,32029	0,90667	0,96400	0,23035	2,10102	6,921	76,90
2	(P+O)ES	(P+O) evolution strategies	0,99934	0,91895	0,56297	2,48127	1,00000	0,93522	0,39179	2,32701	0,83167	0,64433	0,21155	1,68755	6,496	72,18
3	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
4	ESG	evolution of social groups	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
5	SIA	simulated isotropic annealing	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
6	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
7	BSA	bird swarm algorithm	0,90857	0,73661	0,25767	1,90285	0,90437	0,81619	0,16401	1,88457	0,61692	0,54154	0,10951	1,26797	5,055	56,17
8	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
9	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
10	(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
11	BSO	brain storm optimization	0,91301	0,56222	0,30047	1,77570	0,97162	0,57162	0,23449	1,77772	0,60462	0,27138	0,12011	0,99611	4,550	50,55
12	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
13	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
14	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
15	MEC	mind evolutionary computation	0,69533	0,53376	0,32661	1,55569	0,72464	0,33036	0,07198	1,12698	0,52500	0,22000	0,04198	0,78698	3,470	38,55
16	IWO	invasive weed optimization	0,72679	0,52256	0,33123	1,58058	0,70756	0,33955	0,07484	1,12196	0,42333	0,23067	0,04617	0,70017	3,403	37,81
17	Micro-AIS	micro artificial immune system	0,79547	0,51922	0,30861	1,62330	0,72956	0,36879	0,09398	1,19233	0,37667	0,15867	0,02802	0,56335	3,379	37,54
18	COAm	cuckoo optimization algorithm M	0,75820	0,48652	0,31369	1,55841	0,74054	0,28051	0,05599	1,07704	0,50500	0,17467	0,03380	0,71347	3,349	37,21
19	SDOm	spiral dynamics optimization M	0,74601	0,44623	0,29687	1,48912	0,70204	0,34678	0,10944	1,15826	0,42833	0,16767	0,03663	0,63263	3,280	36,44
20	NMm	Nelder-Mead method M	0,73807	0,50598	0,31342	1,55747	0,63674	0,28302	0,08221	1,00197	0,44667	0,18667	0,04028	0,67362	3,233	35,92
21	FAm	firefly algorithm M	0,58634	0,47228	0,32276	1,38138	0,68467	0,37439	0,10908	1,16814	0,28667	0,16467	0,04722	0,49855	3,048	33,87
22	GSA	gravitational search algorithm	0,64757	0,49197	0,30062	1,44016	0,53962	0,36353	0,09945	1,00260	0,32667	0,12200	0,01917	0,46783	2,911	32,34
23	BFO	bacterial foraging optimization	0,61171	0,43270	0,31318	1,35759	0,54410	0,21511	0,05676	0,81597	0,42167	0,13800	0,03195	0,59162	2,765	30,72
24	ABC	artificial bee colony	0,63377	0,42402	0,30892	1,36671	0,55103	0,21874	0,05623	0,82600	0,34000	0,14200	0,03102	0,51302	2,706	30,06
25	BA	bat algorithm	0,59761	0,45911	0,35242	1,40915	0,40321	0,19313	0,07175	0,66810	0,21000	0,10100	0,03517	0,34617	2,423	26,93
26	SA	simulated annealing	0,55787	0,42177	0,31549	1,29513	0,34998	0,15259	0,05023	0,55280	0,31167	0,10033	0,02883	0,44083	2,289	25,43
27	IWDm	intelligent water drops M	0,54501	0,37897	0,30124	1,22522	0,46104	0,14704	0,04369	0,65177	0,25833	0,09700	0,02308	0,37842	2,255	25,06
28	PSO	particle swarm optimisation	0,59726	0,36923	0,29928	1,26577	0,37237	0,16324	0,07010	0,60572	0,25667	0,08000	0,02157	0,35823	2,230	24,77
29	Boids	boids algorithm	0,43340	0,30581	0,25425	0,99346	0,35718	0,20160	0,15708	0,71586	0,27846	0,14277	0,09834	0,51957	2,229	24,77
30	MA	monkey algorithm	0,59107	0,42681	0,31816	1,33604	0,31138	0,14069	0,06612	0,51819	0,22833	0,08567	0,02790	0,34190	2,196	24,40
31	SFL	shuffled frog-leaping	0,53925	0,35816	0,29809	1,19551	0,37141	0,11427	0,04051	0,52618	0,27167	0,08667	0,02402	0,38235	2,104	23,38
32	FSS	fish school search	0,55669	0,39992	0,31172	1,26833	0,31009	0,11889	0,04569	0,47467	0,21167	0,07633	0,02488	0,31288	2,056	22,84
33	RND	random	0,52033	0,36068	0,30133	1,18234	0,31335	0,11787	0,04354	0,47476	0,25333	0,07933	0,02382	0,35648	2,014	22,37
34	GWO	grey wolf optimizer	0,59169	0,36561	0,29595	1,25326	0,24499	0,09047	0,03612	0,37158	0,27667	0,08567	0,02170	0,38403	2,009	22,32
35	CSS	charged system search	0,44252	0,35454	0,35201	1,14907	0,24140	0,11345	0,06814	0,42299	0,18333	0,06300	0,02322	0,26955	1,842	20,46
36	EM	electroMagnetism-like algorithm	0,46250	0,34594	0,32285	1,13129	0,21245	0,09783	0,10057	0,41085	0,15667	0,06033	0,02712	0,24412	1,786	19,85

Выводы

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

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

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

Tab

Рисунок 1. Цветовая градация алгоритмов по соответствующим тестам. Белым цветом подсвечены результаты больше или равные 0.99.

chart

Рисунок 2. Гистограмма результатов тестирования алгоритмов (по шкале от 0 до 100, чем больше, тем лучше,

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

Плюсы и минусы алгоритма оптимизации на основе мозгового штурма (BSO):

Плюсы:

Хорошие результаты на острой функции Forest и дискретной Megacity с высокой размерностью.

Минусы:

Очень большое количество внешних параметров.
Сложная архитектура и реализация.
Требователен к вычислительным ресурсам.

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

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

Загрузить ZIP

BSO.ZIP (26.81 KB)

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

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

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

fxsaber | 19 апр. 2024 в 09:23

Если многомодальность работает, то должен показать много вершин синуса.

fxsaber | 19 апр. 2024 в 10:02

Пример, когда мономодальный АО не справляется.

Форум по трейдингу, автоматическим торговым системам и тестированию торговых стратегий

Обсуждение статьи "Роль качества генератора случайных чисел в эффективности алгоритмов оптимизации"

fxsaber, 2024.04.01 19:17

Взял такую функцию.

input double X = 0;

double OnTester() { return(MathTan(X)); }

Какой-то непонятный результат. Если реализовать итерационное выкалывание, то предполагаю, можно найти много "скал".

Тангенс - неудачная ФФ, ТС-ФФ гораздо проще для выкалывания.

Andrey Dik | 19 апр. 2024 в 10:09

fxsaber #:
Если многомодальность работает, то должен показать много вершин синуса.

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

Andrey Dik | 19 апр. 2024 в 17:15

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

Как разработать агент обучения с подкреплением на MQL5 с интеграцией RestAPI (Часть 1): Как использовать RestAPI в MQL5

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

Разрабатываем мультивалютный советник (Часть 8): Проводим нагрузочное тестирование и обрабатываем новый бар

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

Нейросети — это просто (Часть 86): U-образный Трансформер

Мы продолжаем рассмотрение алгоритмов прогнозирования временных рядов. И в данной статье я предлагаю Вам познакомиться с методов U-shaped Transformer.

Разработка системы репликации (Часть 33): Система ордеров (II)

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