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

Andrey Dik | 19 апреля, 2024

Содержание:

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


1. Введение

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

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


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

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

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

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

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

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

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. Публичные поля:

2. Методы:

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

//——————————————————————————————————————————————————————————————————————————————
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" выполняет следующие действия для инициализации алгоритма оптимизации:

Метод возвращает "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" используется для перемещения агентов в процессе оптимизации. Метод выполняет следующие действия:

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

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

//——————————————————————————————————————————————————————————————————————————————
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" заключается в обновлении глобального решения и построении кластеров решений. Метод выполняет следующие действия:

  1. Получение приспособленности. Для каждого агента в популяции извлекается значение приспособленности и сохраняется в соответствующем поле структуры агента.
  2. Перенос новых идей в популяцию. Новые идеи (агенты), сгенерированные в процессе оптимизации, добавляются в популяцию родителей.
  3. Сортировка родительской популяции. Родительская популяция сортируется по значению приспособленности. Это позволяет участвовать в создании новых идей только лучшим решениям на следующей эпохе.
  4. Проверка на лучшее решение. Если приспособленность лучшего агента в родительской популяции превышает текущее лучшее решение, то обновляется лучшее решение и его координаты.
  5. Выполнение кластеризации. Если это первая итерация, выполняется инициализация алгоритма k-means с родительской популяцией и кластерами. Затем выполняется алгоритм k-means для кластеризации родительской популяции.
  6. Назначение лучшего решения кластера центром кластера. Для каждого кластера проверяется, есть ли в нем агенты (кластеры могут оказаться пустыми). Если есть, то для каждого агента в родительской популяции проверяется, принадлежит ли он данному кластеру. Если приспособленность агента превышает текущую приспособленность кластера, то обновляется приспособленность кластера и его центроид (центроид участвует в создании новых идей).
//——————————————————————————————————————————————————————————————————————————————
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
10 p (5 F) 50 p (25 F) 1000 p (500 F) 10 p (5 F) 50 p (25 F) 1000 p (500 F) 10 p (5 F) 50 p (25 F) 1000 p (500 F)
1 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):

Плюсы:

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

Минусы:

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

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