Алгоритм Бизона — Bison Algorithm (BIA)

Содержание

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

Введение

В поисках лучшего оптимизационного метода, в этой статье познакомимся с Алгоритмом Бизона (Bison Algorithm, BIA) — это популяционный алгоритм оптимизации, вдохновлённый поведением роя, предназначенный для непрерывных задач с одной целевой функцией. Ключевыми особенностями BIA являются два основополагающих принципа, заимствованных из поведения бизонов, это способность к динамичному перемещению и оборонительная стратегия. Алгоритм был разработан чешскими исследователями в 2017 году и был опубликован в сборнике Lecture Notes in Computer Science (Springer) в 2019 году. 

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

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

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

Вы наблюдаете за стадом бизонов в прерии. Им нужно найти самое лучшее пастбище с сочной травой и чистой водой. Но прерия огромна! Как же они это делают? Разделим стадо бизонов на две группы.

Основное стадо (80% бизонов) — это осторожные бизоны. Они держатся вместе, медленно передвигаются группой. "Безопасность в числах!" — их девиз.

Исследователи (20% бизонов) — это смелые молодые бизоны. Они бегут вперед в одном направлении, исследуя новые территории. "А что там, за холмом?" — думают они.

Сформированы две группы: 40 бизонов основного стада разбредаются по известной территории, а 10 бегунов собираются возле самого упитанного бизона (он явно знает, где хорошая трава!) и готовятся к забегу. Когда бизон из основного стада идет к новому месту, он сначала запоминает, где стоял. Делает несколько шагов (от 0 до 3.5 метров). Пробует траву. Если новая трава хуже, тогда возвращается обратно. "Лучше синица в руках..." Если бегун-исследователь нашел место лучше, чем у худшего в стаде бизона, то происходит их замена местами. Бегуны каждый день слегка меняют направление (на 10% влево или вправо). Так больше шансов найти что-то новое. Когда стадо собирается вокруг лучших бизонов, они не просто встают посередине. Вожак (самый упитанный) имеет "вес" 100, второй — 90, третий — 80... десятый — 10. 

Теперь представьте, что:

• Пастбище = пространство поиска решений
• Качество травы = значение целевой функции
• Позиция бизона = потенциальное решение
• Лучшее пастбище = оптимальное решение

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

Рисунок 1. Схема работы стратегии алгоритма BIA

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

Приступим к написанию псевдокода алгоритма DIA.

Теперь нам более понятно, как все работает, и мы можем приступить к написанию кода алгоритма. Класс реализует "Bison Algorithm" и указывает наследование от базового класса "C_AO".

• popSize — определяет общее число "индивидов" или "агентов" в популяции, участвующей в работе алгоритма.
• swarmGroupRate — задает долю (в процентах) от общего числа индивидов, которая будет составлять "роевую группу".
• eliteGroupSize — определяет количество самых лучших индивидов, которые формируют "элитную группу" для вычисления центра.
• overstep — устанавливает максимальный шаг, который может сделать "роевая группа" при своем движении.

В конструкторе устанавливаются значения по умолчанию для всех параметров. Метод "SetParams" позволяет обновить значения параметров алгоритма, используя данные из внешнего источника (представленного массивом "params").

Функциональность:

• Init — метод для начальной инициализации алгоритма, с использованием диапазонов значений для параметров.
• Moving — метод, отвечающий за движение или обновление состояния индивидов в популяции.
• Revision — метод используется для пересмотра и корректировки поведения индивидов или параметров.
• ComputeCenter — приватный метод для вычисления центра элитной группы.
• CheckIfRunnerBetter — приватный метод, проверяет, является ли какой-либо "бегущий" индивид лучше других.

• swarmGroupSize — рассчитывается на основе "popSize" и "swarmGroupRate", определяет фактическое количество особей в роевой группе.
• runningGroupSize — размер "бегущей" группы (подгруппа в общей популяции).
• runDirection — массив, хранящий направление движения для каждого индивида.
• center — массив, хранящий координаты центра элитной группы.

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

class C_AO_BisonAlgorithm : public C_AO
{
  public: //----------------------------------------------------------
  ~C_AO_BisonAlgorithm () { }
  C_AO_BisonAlgorithm ()
  {
    ao_name = "BIA";
    ao_desc = "Bison Algorithm";
    ao_link = "https://www.mql5.com/ru/articles/19444";

    popSize          = 50;    // размер популяции
    swarmGroupRate   = 0.8;   // доля роевой группы от популяции (80%)
    eliteGroupSize   = 10;    // размер элитной группы для вычисления центра (s параметр)
    overstep         = 3.5;   // максимальный шаг роевой группы

    ArrayResize (params, 4);

    params [0].name = "popSize";        params [0].val = popSize;
    params [1].name = "swarmGroupRate"; params [1].val = swarmGroupRate;
    params [2].name = "eliteGroupSize"; params [2].val = eliteGroupSize;
    params [3].name = "overstep";       params [3].val = overstep;
  }

  void SetParams ()
  {
    popSize        = (int)params [0].val;
    swarmGroupRate = params      [1].val;
    eliteGroupSize = (int)params [2].val;
    overstep       = params      [3].val;
  }

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

  void Moving   ();
  void Revision ();
  
  private:
  void ComputeCenter ();
  bool CheckIfRunnerBetter ();

  //------------------------------------------------------------------
  public:
  double swarmGroupRate;     // доля роевой группы
  int    eliteGroupSize;     // размер элитной группы (s параметр)
  double overstep;           // максимальный шаг роевой группы

  private: //---------------------------------------------------------
  int    swarmGroupSize;     // размер роевой группы
  int    runningGroupSize;   // размер бегущей группы
  double runDirection [];    // направление бега
  double center [];          // центр элитной группы
};
//————————————————————————————————————————————————————————————————————

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

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

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

//————————————————————————————————————————————————————————————————————
//--- Инициализация
bool C_AO_BisonAlgorithm::Init (const double &rangeMinP  [],
                                const double &rangeMaxP  [],
                                const double &rangeStepP [],
                                const int     epochsP = 0)
{
  if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false;

  //------------------------------------------------------------------
  // Вычисляем размеры групп
  swarmGroupSize   = (int)MathFloor (popSize * swarmGroupRate);
  runningGroupSize = popSize - swarmGroupSize;
  
  // Корректировка размеров групп
  if (swarmGroupSize < 1) swarmGroupSize = 1;
  if (swarmGroupSize >= popSize) swarmGroupSize = popSize - 1;
  if (eliteGroupSize < 1) eliteGroupSize = 1;
  if (eliteGroupSize > swarmGroupSize) eliteGroupSize = swarmGroupSize;
  
  // Инициализация вспомогательных массивов
  ArrayResize (runDirection, coords);
  ArrayResize (center, coords);

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

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

Фаза 1: Первоначальная инициализация (при первом запуске): если алгоритм запускается впервые (флаг "revision" установлен в "false"), выполняется следующая последовательность действий:

• Генерация роевой группы. Особи, входящие в роевую группу, инициализируются случайными значениями в пределах заданных для каждого параметра диапазонов. После генерации эти значения могут быть дополнительно скорректированы, чтобы соответствовать шагу изменения параметров.
• Поиск лучшего бизона. Среди всех особей роевой группы находится та, которая имеет наилучшую приспособленность (наибольшее значение целевой функции).
• Генерация бегущей группы. Остальные особи популяции (бегущая группа) инициализируются вокруг найденного лучшего бизона. Их позиции генерируются случайным образом в некоторой окрестности лучшего решения, а затем также корректируются, в соответствии с диапазонами и шагами параметров.
• Инициализация вектора направления движения. Для каждой размерности пространства поиска генерируется случайный вектор направления движения. Величина этого вектора зависит от общего диапазона значений параметра, и его знак (положительный или отрицательный) также выбирается случайно.
• Установка флага инициализации. Флаг "revision" устанавливается в "true", начальная инициализация завершена, и в дальнейшем будут выполняться только шаги обновления.

Фаза 2: Основной цикл итерации (последующие шаги): когда начальная инициализация уже проведена, метод выполняет следующие шаги для каждой итерации:

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

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

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

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

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

Таким образом, метод "Moving" моделирует поведение группы особей: часть группы (роевая) движется к общей цели, реагируя на лучшие решения, а другая часть (бегущая) следует за скорректированным вектором направления, который также может изменяться.

/————————————————————————————————————————————————————————————————————
//--- Основной шаг алгоритма
void C_AO_BisonAlgorithm::Moving ()
{
  // Начальная инициализация популяции
  if (!revision)
  {
    // Генерация роевой группы случайным образом
    for (int i = 0; i < swarmGroupSize; i++)
    {
      for (int j = 0; j < coords; j++)
      {
        a [i].c [j] = u.RNDfromCI (rangeMin [j], rangeMax [j]);
        a [i].c [j] = u.SeInDiSp (a [i].c [j], rangeMin [j], rangeMax [j], rangeStep [j]);
      }
    }
    
    // Находим лучшее решение среди роевой группы для инициализации бегунов
    int bestIdx = 0;
    double bestFit = a [0].f;
    for (int i = 1; i < swarmGroupSize; i++)
    {
      if (a [i].f > bestFit)
      {
        bestFit = a [i].f;
        bestIdx = i;
      }
    }
    
    // Генерация бегущей группы вокруг лучшего бизона
    double neighbourhood = (rangeMax [0] - rangeMin [0]) / 15.0;
    for (int i = swarmGroupSize; i < popSize; i++)
    {
      for (int j = 0; j < coords; j++)
      {
        a [i].c [j] = a [bestIdx].c [j] + u.RNDfromCI (-neighbourhood, neighbourhood);
        a [i].c [j] = u.SeInDiSp (a [i].c [j], rangeMin [j], rangeMax [j], rangeStep [j]);
      }
    }
    
    // Генерация run direction = random((ub-lb)/45, (ub-lb)/15)
    for (int j = 0; j < coords; j++)
    {
      double range = rangeMax [j] - rangeMin [j];
      runDirection [j] = u.RNDfromCI (range / 45.0, range / 15.0);
      if (u.RNDprobab () < 0.5) runDirection [j] = -runDirection [j];
    }
    
    revision = true;
    return;
  }

  //------------------------------------------------------------------
  // Основной цикл итерации
  
  // 1. Определяем цель роения (swarming target)
  if (CheckIfRunnerBetter ())
  {
    // Если runner лучше swarmer, center = runner
    // center уже установлен в CheckIfRunnerBetter
  }
  else
  {
    // Иначе вычисляем центр сильнейших решений
    ComputeCenter ();
  }
  
  // 2. Движение роевой группы
  for (int i = 0; i < swarmGroupSize; i++)
  {
    // Сохраняем старые позиции в cP и фитнес в fP
    ArrayCopy (a [i].cP, a [i].c, 0, 0, coords);
    a [i].fP = a [i].f;
    
    // Вычисляем нового кандидата позиции
    for (int c = 0; c < coords; c++)
    {
      double direction = center [c] - a [i].c [c];
      a [i].c [c] = a [i].c [c] + direction * u.RNDfromCI (0.0, overstep);
      a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
  
  // 3. Корректировка run direction вектора
  for (int j = 0; j < coords; j++)
  {
    runDirection [j] = runDirection [j] * u.RNDfromCI (0.9, 1.1);
  }
  
  // 4. Движение бегущей группы
  for (int i = swarmGroupSize; i < popSize; i++)
  {
    for (int c = 0; c < coords; c++)
    {
      a [i].c [c] = a [i].c [c] + runDirection [c];
      a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
}
//————————————————————————————————————————————————————————————————————

Метод "Revision" класса "C_AO_BisonAlgorithm" предназначен для обновления состояния популяции после выполнения одного шага движения и оценки приспособленности особей, а также для подведения итогов итерации.

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

Сравнение бегущей группы с роевой:

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

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

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

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

//————————————————————————————————————————————————————————————————————
//--- Обновление и проверка результатов
void C_AO_BisonAlgorithm::Revision ()
{
  // 1. Для роевой группы: обновляем позиции только если новая позиция лучше
  for (int i = 0; i < swarmGroupSize; i++)
  {
    // Если новая позиция хуже старой, возвращаем старую
    if (a [i].f < a [i].fP)
    {
      ArrayCopy (a [i].c, a [i].cP, 0, 0, coords);
      a [i].f = a [i].fP;
    }
  }
  
  // 2. Проверяем, не нашел ли runner лучшее решение чем swarmer
  double bestRunnerFitness = -DBL_MAX;
  int bestRunnerIdx = -1;
  double worstSwarmerFitness = DBL_MAX;
  int worstSwarmerIdx = -1;
  
  for (int i = swarmGroupSize; i < popSize; i++)
  {
    if (a[i].f > bestRunnerFitness)
    {
      bestRunnerFitness = a[i].f;
      bestRunnerIdx = i;
    }
  }
  
  for (int i = 0; i < swarmGroupSize; i++)
  {
    if (a[i].f < worstSwarmerFitness)
    {
      worstSwarmerFitness = a[i].f;
      worstSwarmerIdx = i;
    }
  }
  
  // Если runner лучше худшего swarmer, копируем runner в swarming group
  if (bestRunnerIdx >= 0 && worstSwarmerIdx >= 0 && bestRunnerFitness > worstSwarmerFitness)
  {
    ArrayCopy (a[worstSwarmerIdx].c, a[bestRunnerIdx].c, 0, 0, coords);
    a[worstSwarmerIdx].f = a[bestRunnerIdx].f;
  }
  
  // 3. Сортировка роевой группы
  // Создаем временный массив для сортировки только роевой группы
  S_AO_Agent swarmTemp [];
  ArrayResize (swarmTemp, swarmGroupSize);
  
  // Копируем роевую группу
  for (int i = 0; i < swarmGroupSize; i++)
  {
    swarmTemp[i].Init(coords);
    ArrayCopy (swarmTemp[i].c, a[i].c, 0, 0, coords);
    swarmTemp[i].f = a[i].f;
    ArrayCopy (swarmTemp[i].cP, a[i].cP, 0, 0, coords);
    swarmTemp[i].fP = a[i].fP;
  }
  
  // Сортируем
  S_AO_Agent tempSorted [];
  ArrayResize (tempSorted, swarmGroupSize);
  u.Sorting (swarmTemp, tempSorted, swarmGroupSize);
  
  // Копируем обратно отсортированную роевую группу
  for (int i = 0; i < swarmGroupSize; i++)
  {
    ArrayCopy (a[i].c, swarmTemp[i].c, 0, 0, coords);
    a[i].f = swarmTemp[i].f;
    ArrayCopy (a[i].cP, swarmTemp[i].cP, 0, 0, coords);
    a[i].fP = swarmTemp[i].fP;
  }
  
  // 4. Обновляем глобальное лучшее и худшее решение
  if (a[0].f > fB)
  {
    fB = a[0].f;
    ArrayCopy (cB, a[0].c, 0, 0, WHOLE_ARRAY);
  }
  
  // Находим худшее во всей популяции
  for (int i = 0; i < popSize; i++)
  {
    if (a[i].f < fW)
    {
      fW = a[i].f;
      ArrayCopy (cW, a[i].c, 0, 0, WHOLE_ARRAY);
    }
  }
}
//————————————————————————————————————————————————————————————————————

Метод "CheckIfRunnerBetter" служит для определения, содержит ли бегущая группа более перспективное решение, чем те, что присутствуют в роевой группе. Если такое решение найдено, оно становится новой "целью" для роения.

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

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

Сравнение и определение цели. После этого происходит сравнение:

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

Возврат результата:

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

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

//————————————————————————————————————————————————————————————————————
//--- Проверка, лучше ли runner чем swarmer
bool C_AO_BisonAlgorithm::CheckIfRunnerBetter ()
{
  // Находим лучшего runner
  double bestRunnerFitness = -DBL_MAX;
  int bestRunnerIdx = -1;
  
  for (int i = swarmGroupSize; i < popSize; i++)
  {
    if (a[i].f > bestRunnerFitness)
    {
      bestRunnerFitness = a[i].f;
      bestRunnerIdx = i;
    }
  }
  
  // Находим худшего swarmer 
  double worstSwarmerFitness = DBL_MAX;
  
  for (int i = 0; i < swarmGroupSize; i++)
  {
    if (a[i].f < worstSwarmerFitness)
    {
      worstSwarmerFitness = a[i].f;
    }
  }
  
  // Если runner лучше swarmer, устанавливаем его как центр
  if (bestRunnerIdx >= 0 && bestRunnerFitness > worstSwarmerFitness)
  {
    ArrayCopy (center, a[bestRunnerIdx].c, 0, 0, coords);
    return true;
  }
  
  return false;
}
//————————————————————————————————————————————————————————————————————

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

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

• eliteGroupSize — максимальное количество "элитных" решений, которые могут быть учтены;
• swarmGroupSize — размер текущей роевой группы;
• Это гарантирует, что мы используем либо все заданные элитные решения, либо столько, сколько есть в роевой группе, если элитных решений меньше.
• Назначение весов. Создается набор весов для каждого из выбранных лучших решений. Эти веса увеличиваются линейно: первое решение получает меньший вес, второе — больший, и так далее, до последнего. Конкретно, веса задаются как 10, 20, 30... до  s * 10, где  s  —количество учитываемых лучших решений. Эти веса показывают, насколько значимым является каждое решение при вычислении центра.
• Накопление общей суммы весов. Все рассчитанные веса суммируются. Эта общая сумма понадобится для нормализации.
• Взвешенное суммирование позиций. Теперь для каждой размерности (координаты) позиции:
• берется значение соответствующей координаты из каждого из  s  лучших решений;
• это значение координаты умножается на вес соответствующего лучшего решения. Важно отметить, что веса применяются в обратном порядке: самое лучшее решение (первое в отсортированном списке) получается самый большой вес, второе — следующий по величине, и так далее.
• результаты этих умножений для всех  s  лучших решений суммируются для данной координаты.
• Нормализация. Полученная сумма взвешенных координат для каждой размерности делится на общую сумму всех весов. Это делает расчет "средневзвешенным", гарантируя, что итоговая позиция центра находится в некоторой "средней" области лучших найденных решений, при этом более качественные решения имеют большее влияние.

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

//————————————————————————————————————————————————————————————————————
//--- Вычисление центра элитной группы
void C_AO_BisonAlgorithm::ComputeCenter ()
{
  // Обнуляем центр
  for (int j = 0; j < coords; j++)
  {
    center [j] = 0.0;
  }
  
  // Вычисляем взвешенный центр из s лучших решений
  double weights [];
  int s = MathMin(eliteGroupSize, swarmGroupSize);
  ArrayResize (weights, s);
  double totalWeight = 0.0;
  
  // weight = (10, 20, 30, ..., 10*s)
  for (int i = 0; i < s; i++)
  {
    weights[i] = (i + 1) * 10.0;
    totalWeight += weights[i];
  }
  
  // center = sum(weight[i] * position[i]) / sum(weights)
  for (int j = 0; j < coords; j++)
  {
    for (int i = 0; i < s; i++)
    {
      center[j] += (weights[s - 1 - i] * a[i].c[j]) / totalWeight;
    }
  }
}
//————————————————————————————————————————————————————————————————————

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

На визуализации работы алгоритма BIA заметен достаточно большой разброс результатов не только на функциях малой размерности (зеленые линии), но и на функциях средней размерности (голубые линии).

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

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

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

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

Выводы

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

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

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

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

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

Плюсы:

1. Простая реализация.
2. Быстрый.

Минусы:

1. Разброс значений на функциях малой и средней размерности.

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

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

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