Популяционные алгоритмы оптимизации: Алгоритм птичьего роя (Bird Swarm Algorithm, BSA)

Содержание:

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

1. Введение

Птицы — это удивительные создания, которые занимают важное место в природе и экосистеме. Считается, что птицы произошли от динозавров, их ближайшие родственники. Один из наиболее известных примеров - археоптерикс, древнейшая из известных птиц, жившая около 150 миллионов лет назад. Они часто выступают в роли индикаторов состояния окружающей среды, потому что изменения в численности и их поведении могут свидетельствовать о проблемах в экосистеме, таких как загрязнение, потеря мест обитания и изменение климата. На Земле известно более 10 000 видов птиц, и каждый из них обладает уникальной адаптацией к своему образу жизни.

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

Bird Swarm Algorithm (BSA) — это увлекательный биоинспирированный эволюционный алгоритм, с использованием роевого интеллекта, вдохновленный социальными взаимодействиями и поведением стай птиц. Разработанный Менгом и его коллегами в 2015 году, BSA является уникальным подходом к оптимизации, объединяющим три ключевых аспекта поведения птиц: полет, поиск пищи, бдительность. Среди электронных стай, где каждая "птица" обладает индивидуальными тактиками и стратегиями, зарождается уникальная система коллективного взаимодействия, наполненная алгоритмическим интеллектом и креативностью. Здесь важны не только личные усилия, но и способность к сотрудничеству, обмену и взаимной поддержке в стремлении к общей цели оптимизации.  

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

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

Алгоритм BSA, основанный на поведении птиц, вдохновлен коллективным стайным взаимодействием птиц в природе, поведение которых легло в основу этого алгоритма:

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

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

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

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

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

2. Описание алгоритма

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

Псевдокод для алгоритма Bird Swarm Algorithm (BSA), который представляет собой высокоуровневое описание алгоритма, моделирующее поведение стаи птиц:

1. Инициализация N решений и связанных с ними параметров
2. Генерация новых решений:
3. Если птица летит:
    4. Если птица - производитель:
        5. Поиск нового участка с пищей
    6. Иначе:
        7. Птица-попрошайка следует за производителем
8. Иначе:
    9. Если птица добывает пропитание:
        10. Птица питается
    11. Иначе:
        12. Птица остается настороже (бдительна)
13. Оценка пригодности новых решений
14. Обновление решений
15. Если достигнут критерий останова:
    16. Завершение работы алгоритма
17. Иначе:
    18. Возврат к шагу 2

Формула пункта 5, для птицы, ищущей новый участок с пищей:

 xn = RNDg (min, max, producerPower)

где:

• xn - новое значение координаты
• RNDg - случайное число с нормальным распределением с центром распределения в текущей координате
• min и max - границы распределения
• producerPower - показатель стандартного отклонения для производителя

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

Формула пункта 7 для птицы-попрошайки, следующей за производителем:

xn = x + (xK - x) * FL * RNDg (-1.0, 1.0, scroungerPower)

где:

• xn -  новое значение координаты
• x - лучшая координата попрошайки в истории
• xK - лучшая координата производителя в истории, где в качестве производителя выбрана случайная птица с позицией K в популяции
• RNDg - случайное число с нормальным распределением с центром распределения в 0 и границами "-1.0" и "1.0"
• scroungerPower - показатель стандартного отклонения для попрошайки

Формула показывает, что птица-попрошайка ориентируется на лучшие свои координаты и лучшие координаты лучшего индивидуума в стае (производитель ориентируется не на лучшие свои координаты, а на текущие). Это моделирует поведение следования за лидером в стае.

Формула пункта 10, применимая к птице в период питания вне полёта:

xn = x + (p - x) * C * r1 + (g - x) * S * r2

где:

• xn - новое значение координаты
• x - текущая координата
• p - лучшая координата в истории птицы, принимающей пищу
• g - лучшие координаты популяции в истории (лучшее глобальное решение)
• r1 - случайное равномерное число в диапазоне [0.0 ... 1.0]
• r2 - случайное равномерное число в диапазоне [0.0 ... 1.0]
• C - когнитивный коэффициент, внешний параметр
• S - социальный коэффициент, внешний параметр

Формула описывает момент приёма пищи, в котором поведение птицы основано на её собственном опыте (текущее положение и лучшее положение в прошлом) и опыте стаи.

Формула пункта 12 для птицы находящейся на страже:

xn = x + A1 * (mean [c] - x) * r1 + A2 * (xK - x) * r2

где:

• xn - новое значение координаты
• x - лучшая координата бдящей птицы в истории
• r1 - случайное равномерное число в диапазоне [0.0 ... 1.0]
• r2 - случайное равномерное число в диапазоне [-1.0 ... 1.0]
• mean [c] - среднее значение c-той координаты по лучшим координатам всех птиц в стае
  

A1 - корректирующий коэффициент влияния усреднённых координат центра стаи:

A1 = a1 * exp (-pFit * N / (sumFit + e)) 

где:

• a1 - коэффициент, внешний параметр
• e = DBL_MIN, для избегания деления на 0
• pFit - лучшая приспособленность птицы на страже
• sumFit - сумма лучших приспособленностей птиц в стае
• N - количество птиц в стае

A2 - это поправочный коэффициент, учитывающий влияние положения выбранной для наблюдения птицы (попавшей в поле зрения бдящей птицы) на поведение последней. Формула для A2:

A2 = a2 * exp (((pFit - pFitK) / (|pFitK - pFit| + e)) * (N * pFitK / (sumFit + e)))

где:

• a2 - коэффициент, внешний параметр
• e = DBL_MIN, для избегания деления на 0
• pFit - лучшая приспособленность птицы на страже
• pFitK - лучшая приспособленность случайно выбранной в популяции K-той птицы (птица, попавшая в поле зрения бдящей птице)
• sumFit - сумма лучших приспособленностей птиц в стае
• N - количество птиц в стае

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

Выделенный цветом текст в псевдокоде соответствует логическим элементам BSA, изображенным на схеме рисунка 1.

Рисунок 1. Логическая схема алгоритма BSA.

Схема на рисунке 1 представляет собой визуализацию алгоритма BSA и моделирует поведение стаи птиц. Ключевые особенности этого алгоритма:

1. Инициализация решений. Алгоритм начинается с инициализации набора решений и связанных с ними параметров. Это включает в себя начальное распределение птиц (или решений) в пространстве поиска.
2. Поведение полета. В процессе работы алгоритма каждая птица может "летать" или "не летать". Это состояние влияет на способность птицы обнаруживать новые решения. 
3. Поведение поиска пищи. Если птица "летает", она может стать "производителем" и начать поиск нового участка с пищей, или же стать "попрошайкой", следуя за производителем.
4. Поведение добычи пищи. Если птица "не летает", она либо питается, либо остается бдительной. Это может представлять собой состояние ожидания или наблюдения за окружающей средой.
5. Оценка и обновление решений. После генерации новых решений проводится оценка их приспособленности или качества.
6. Критерий остановки. Алгоритм продолжает цикл генерации и обновления решений до тех пор, пока не будет достигнут определенный критерий остановки. Это может быть определенное количество итераций, достижение заданного уровня качества решения или другой критерий.

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

Напишем код алгоритма BSA. Для каждого агента определим структуру "S_BSA_Agent", которая будет являться отдельным решением задачи оптимизации и описанием птицы в стае.

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

• cBest[] - массив для хранения лучших координат агента.
• fBest - переменная для хранения лучшей оценки приспособленности агента.
• Init - метод структуры "S_BSA_Agent", который инициализирует поля структуры. Он принимает целочисленный аргумент “coords” - количество координат, который используется для изменения размера массива “cBest” с помощью функции “ArrayResize”.

Переменной "fBest" устанавливаем начальное значение равным минимально возможной величине числа типа double, что означает наихудшую возможную приспособленность.

//——————————————————————————————————————————————————————————————————————————————
struct S_BSA_Agent
{
    double cBest []; //best coordinates
    double fBest;    //best fitness

    void Init (int coords)
    {
      ArrayResize (cBest, coords);
      fBest = -DBL_MAX;
    }
};
//——————————————————————————————————————————————————————————————————————————————

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

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

• ao_name - имя алгоритма оптимизации.
• ao_desc - описание алгоритма оптимизации.
• popSize - размер популяции.
• params - массив параметров алгоритма.
• flyingProb - вероятность полета.
• producerProb - вероятность производства.
• foragingProb - вероятность сбора.
• a1 - константа a1 [0...2].
• a2 - константа a2 [0...2].
• C - когнитивный коэффициент.
• S - социальный коэффициент.
• FL - константа FL [0...2].
• producerPower - стандартное отклонение в поведении производителя.
• scroungerPower - стандартное отклонение в поведении попрошайки.

2. Методы:

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

//——————————————————————————————————————————————————————————————————————————————
class C_AO_BSA : public C_AO
{
  public: //--------------------------------------------------------------------
  ~C_AO_BSA () { }
  C_AO_BSA ()
  {
    ao_name = "BSA";
    ao_desc = "Bird Swarm Algorithm";

    popSize        = 20;  //population size

    flyingProb     = 0.8;  //Flight probability
    producerProb   = 0.25; //Producer probability
    foragingProb   = 0.55; //Foraging probability
    a1             = 0.6;  //a1 constant [0...2]
    a2             = 0.05; //a2 constant [0...2]
    C              = 0.05; //Cognitive coefficient
    S              = 1.1;  //Social coefficient
    FL             = 1.75; //FL constant [0...2]
    producerPower  = 7.05; //Producer power
    scroungerPower = 2.60; //Scrounger power

    ArrayResize (params, 11);

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

    params [1].name  = "flyingProb";     params [1].val  = flyingProb;
    params [2].name  = "producerProb";   params [2].val  = producerProb;
    params [3].name  = "foragingProb";   params [3].val  = foragingProb;
    params [4].name  = "a1";             params [4].val  = a1;
    params [5].name  = "a2";             params [5].val  = a2;
    params [6].name  = "C";              params [6].val  = C;
    params [7].name  = "S";              params [7].val  = S;
    params [8].name  = "FL";             params [8].val  = FL;
    params [9].name  = "producerPower";  params [9].val  = producerPower;
    params [10].name = "scroungerPower"; params [10].val = scroungerPower;
  }

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

    flyingProb     = params [1].val;
    producerProb   = params [2].val;
    foragingProb   = params [3].val;
    a1             = params [4].val;
    a2             = params [5].val;
    C              = params [6].val;
    S              = params [7].val;
    FL             = params [8].val;
    producerPower  = params [9].val;
    scroungerPower = params [10].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);

  //----------------------------------------------------------------------------
  double flyingProb;      //Flight probability
  double producerProb;    //Producer probability
  double foragingProb;    //Foraging probability
  double a1;              //a1 constant [0...2]
  double a2;              //a2 constant [0...2]
  double C;               //Cognitive coefficient
  double S;               //Social coefficient
  double FL;              //FL constant [0...2]
  double producerPower;   //Producer power
  double scroungerPower;  //Scrounger power

  S_BSA_Agent agent [];


  private: //-------------------------------------------------------------------
  double mean [];  //represents the element of the average position of the whole bird’s swarm
  double N;
  double e;        //epsilon

  void BirdProducer  (int pos);
  void BirdScrounger (int pos);
  void BirdForaging  (int pos);
  void BirdVigilance (int pos);
};
//——————————————————————————————————————————————————————————————————————————————

Метод "Init" класса "C_AO_BSA" используется для инициализации переменных класса на основе переданных параметров. Этот метод выполняет стандартную инициализацию с использованием метода "StandardInit", который принимает минимальный и максимальный диапазоны поиска, а также шаг поиска.

Если стандартная инициализация прошла успешно, метод продолжает инициализацию переменных "N" и "e". Значение "N" устанавливается равным размеру популяции "popSize", а "e"-эпсилон, инициализируется минимальным значением числа типа double.

Затем метод изменяет размер массива "agent" до размера "popSize". Для каждого элемента в "agent" вызывается метод "Init" с параметром "coords". Также изменяется размер массива "mean" до размера "coords", этот массив используется для хранения усреднённых по популяции координат птиц.

Метод возвращает "true", если инициализация прошла успешно, и "false" в противном случае.

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

//——————————————————————————————————————————————————————————————————————————————
bool C_AO_BSA::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 (mean, coords);

  N = popSize;
  e = DBL_MIN;

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

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

• Если "revision" равно "false", то происходит инициализация координат агентов "a[i].c[c]" с использованием случайных значений в заданных диапазонах. Затем устанавливается флаг "revision" в "true" и метод завершает работу.
• Если "revision" не равно "false", то для каждого агента происходит вычисление новых координат с использованием формул и вероятностей.

На второй и последующих эпохах метод вызывает функции, определяющие поведение каждой птицы в стае в зависимости от выполненных вероятностей: 

• Если выполнена вероятность полёта - "flyingProb", то агент "летает". В этом случае возможны два варианта поведения:

1. Если вероятность меньше "producerProb", то агент является "производителем" и ищет новое место для еды.
   
2. В противном случае, агент является "попрошайкой" и следует за производителем.

• Если "не летает", то возможны следующие два варианта поведения:
  

1. Если вероятность меньше "foragingProb", то агент "собирает" еду. 
2. В противном случае, агент находится в состоянии "бдительности".

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

//——————————————————————————————————————————————————————————————————————————————
void C_AO_BSA::Moving ()
{
  //----------------------------------------------------------------------------
  if (!revision)
  {
    for (int i = 0; i < popSize; i++)
    {
      for (int c = 0; c < coords; c++)
      {
        a [i].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]);
        a [i].c [c] = u.SeInDiSp  (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }

    revision = true;
    return;
  }

  //----------------------------------------------------------------------------
  for (int i = 0; i < popSize; i++)
  {
    //bird is flying------------------------------------------------------------
    if (u.RNDprobab () < flyingProb)
    {
      //bird producer
      if (u.RNDprobab () < producerProb) BirdProducer  (i); //bird is looking for a new place to eat
      //bird is not a producer
      else                               BirdScrounger (i); //scrounger follows the  producer
    }
    //bird is not flying--------------------------------------------------------
    else
    {
      //bird foraging
      if (u.RNDprobab () < foragingProb) BirdForaging  (i); //bird feeds
      //bird is not foraging
      else                               BirdVigilance (i); //bird vigilance
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

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

• Инициализирует переменную "x", которая будет использоваться для хранения текущего положения птицы.
• Затем для каждой координаты агента выполняются следующие действия:
• Значение "x" устанавливается равным текущей координате агента.
• Значение "x" обновляется с использованием Гауссового распределения, где среднее значение равно текущей координате, а диапазон и стандартное отклонение определяются значениями "rangeMin", "rangeMax" и "producerPower".
• Новое значение координаты агента устанавливается с использованием метода "SeInDiSp", который корректирует значение "x" в соответствии с диапазоном поиска и шагом.

Этот метод моделирует поведение "производителя" в алгоритме BSA, который ищет новые места-источники пищи (т.е. новые потенциальные решения), используя Гауссово распределение для исследования пространства поиска.

//——————————————————————————————————————————————————————————————————————————————
void  C_AO_BSA::BirdProducer  (int pos)
{
  double x = 0.0; //bird position

  for (int c = 0; c < coords; c++)
  {
    x = a [pos].c [c];
    x = u.GaussDistribution (x, rangeMin [c], rangeMax [c], producerPower);

    a [pos].c [c] = u.SeInDiSp (x, rangeMin [c], rangeMax [c], rangeStep [c]);
  }
}
//——————————————————————————————————————————————————————————————————————————————

Метод, моделирующий поведение "попрошайки", представляет собой функцию "BirdScrounger" в классе "C_AO_BSA". Он выполняет следующие действия:

• 1. Инициализирует переменные "K", "x" и "xK". "K" — это позиция случайно выбранной птицы в стае, "x" - это лучшая позиция птицы, а "xK" - это текущая лучшая позиция случайно выбранной птицы в стае.
• 2. Запускает цикл по всем координатам.
• Выбирает случайную птицу, которая не является текущей птицей.
• Обновляет "x" и "xK" на основе лучших позиций текущей птицы и случайно выбранной птицы.
• Обновляет "x" с использованием гауссовского распределения.
• Наконец, обновляет текущую позицию птицы, используя метод "SeInDiSp", корректирует значение "x" в соответствии с диапазоном поиска и шагом.

Этот метод моделирует поведение "попрошайки" в алгоритме BSA, используя Гауссово распределение, который следует за "производителем" (т.е. уточняет собственное местоположение относительно положения производителя).

//——————————————————————————————————————————————————————————————————————————————
void  C_AO_BSA::BirdScrounger (int pos)
{
  int    K  = 0;   //position of a randomly selected bird in a swarm
  double x  = 0.0; //best bird position
  double xK = 0.0; //current best position of a randomly selected bird in a swarm

  for (int c = 0; c < coords; c++)
  {
    do K = u.RNDminusOne (popSize);
    while (K == pos);

    x  = agent [pos].cBest [c];
    xK = agent   [K].cBest [c];

    x = x + (xK - x) * FL * u.GaussDistribution (0, -1.0, 1.0, scroungerPower);

    a [pos].c [c] = u.SeInDiSp (x, rangeMin [c], rangeMax [c], rangeStep [c]);
  }
}
//——————————————————————————————————————————————————————————————————————————————

Для птицы, которая не летает в данный момент и которая занята приёмом пищи, предназначен метод BirdForaging" в классе "C_AO_BSA". Внутри цикла по всем координатам метод выполняет следующее:

• Обновляет "x", "p" и "g" на основе текущих и лучших позиций птицы, а также лучшей глобальной позиции.
• Генерирует два случайных числа "r1" и "r2".
• Обновляет "x" с использованием этих случайных чисел, а также констант "C" и "S".
• Корректирует полученную позицию птицы, используя функцию "SeInDiSp".

//——————————————————————————————————————————————————————————————————————————————
void  C_AO_BSA::BirdForaging  (int pos)
{
  double x  = 0.0; //current bird position
  double p  = 0.0; //best bird position
  double g  = 0.0; //best global position
  double r1 = 0.0; //uniform random number [0.0 ... 1.0]
  double r2 = 0.0; //uniform random number [0.0 ... 1.0]

  for (int c = 0; c < coords; c++)
  {
    x = a     [pos].c     [c];
    p = agent [pos].cBest [c];
    g = cB                [c];

    r1 = u.RNDprobab ();
    r2 = u.RNDprobab ();

    x = x + (p - x) * C * r1 + (g - x) * S * r2;

    a [pos].c [c] = u.SeInDiSp (x, rangeMin [c], rangeMax [c], rangeStep [c]);
  }
}
//——————————————————————————————————————————————————————————————————————————————

Последний и самый сложный метод, моделирующий поведение бдящей птицы - "BirdVigilance". Он выполняет следующие действия:

• Вычисляет сумму лучших значений приспособленности всех птиц в стае.
• Вычисляет среднее значение каждой координаты для всех птиц в стае.
• Выбирает случайную птицу, которая не является текущей птицей.
• Обновляет "pFit" и "pFitK" на основе лучших значений приспособленности текущей птицы и случайно выбранной птицы.
• Вычисляет "A1" и "A2" с использованием экспоненциальной функции, которая зависит от "pFit", "pFitK", "N", "sumFit" и "e".
• Запускает цикл по всем координатам: 
• Генерирует два случайных числа "r1" и "r2".
• Обновляет "x" и "xK" на основе лучших позиций текущей птицы и случайно выбранной птицы.
• Обновляет "x" с использованием "A1", "A2", "r1" и "r2".
• Корректирует текущую позицию птицы, используя функцию "SeInDiSp".

//——————————————————————————————————————————————————————————————————————————————
void  C_AO_BSA::BirdVigilance (int pos)
{
  int    K      = 0;   //position of a randomly selected bird in a swarm
  double sumFit = 0.0; //best birds fitness sum
  double pFitK  = 0.0; //best fitness of a randomly selected bird
  double pFit   = 0.0; //best bird fitness
  double A1     = 0.0;
  double A2     = 0.0;
  double r1     = 0.0; //uniform random number [ 0.0 ... 1.0]
  double r2     = 0.0; //uniform random number [-1.0 ... 1.0]
  double x      = 0.0; //best bird position
  double xK     = 0.0; //best position of a randomly selected bird in a swarm

  ArrayInitialize (mean, 0.0);

  for (int i = 0; i < popSize; i++) sumFit += agent [i].fBest;

  for (int c = 0; c < coords; c++)
  {
    for (int i = 0; i < popSize; i++) mean [c] += a [i].c [c];

    mean [c] /= popSize;
  }

  do K = u.RNDminusOne (popSize);
  while (K == pos);

  pFit  = agent [pos].fBest;
  pFitK = agent   [K].fBest;

  A1 = a1 * exp (-pFit * N / (sumFit + e));
  A2 = a2 * exp (((pFit - pFitK) / (fabs (pFitK - pFit) + e)) * (N * pFitK / (sumFit + e)));

  for (int c = 0; c < coords; c++)
  {
    r1 = u.RNDprobab ();
    r2 = u.RNDfromCI (-1, 1);

    x  = agent [pos].cBest [c];
    xK = agent   [K].cBest [c];

    x = x + A1 * (mean [c] - x) * r1 + A2 * (xK - x) * r2;

    a [pos].c [c] = u.SeInDiSp (x, rangeMin [c], rangeMax [c], rangeStep [c]);
  }
}
//——————————————————————————————————————————————————————————————————————————————

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

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

//——————————————————————————————————————————————————————————————————————————————
void C_AO_BSA::Revision ()
{
  //----------------------------------------------------------------------------
  int ind = -1;

  for (int i = 0; i < popSize; i++)
  {
    if (a [i].f > fB) ind = i;
  }

  if (ind != -1)
  {
    fB = a [ind].f;
    ArrayCopy (cB, a [ind].c, 0, 0, WHOLE_ARRAY);
  }

  //----------------------------------------------------------------------------
  for (int i = 0; i < popSize; i++)
  {
    if (a [i].f > agent [i].fBest)
    {
      agent [i].fBest = a [i].f;
      ArrayCopy (agent [i].cBest, a [i].c, 0, 0, WHOLE_ARRAY);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

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

Хотел бы подробнее остановиться на результатах алгоритма Bird Swarm Algorithm (BSA) на различных наборах функций. Общий балл BSA на всех тестовых функциях составил 4.80947, что соответствует 53.44% от максимально возможного результата. Этот результат указывает на общую эффективность алгоритма исходя из этого, можно сделать вывод, что алгоритм Bird Swarm Algorithm обладает потенциалом для успешного решения разнообразных задач оптимизации на различных функциях.

BSA|Bird Swarm Algorithm|20.0|0.8|0.25|0.55|0.6|0.05|0.05|1.1|1.75|7.05|2.6|
=============================
5 Hilly's; Func runs: 10000; result: 0.8930600046782612
25 Hilly's; Func runs: 10000; result: 0.6489975525320968
500 Hilly's; Func runs: 10000; result: 0.262496551797822
=============================
5 Forest's; Func runs: 10000; result: 0.9241962617798402
25 Forest's; Func runs: 10000; result: 0.7112057472851052
500 Forest's; Func runs: 10000; result: 0.24938963509983267
=============================
5 Megacity's; Func runs: 10000; result: 0.6938461538461538
25 Megacity's; Func runs: 10000; result: 0.3261538461538461
500 Megacity's; Func runs: 10000; result: 0.1001230769230778
=============================
All score: 4.80947 (53.44%)

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

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

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

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

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

BSA на тестовой функции Skin.

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

№	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	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
12	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
13	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
14	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
15	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
16	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
17	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
18	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
19	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
20	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
21	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
22	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
23	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
24	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
25	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
26	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
27	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
28	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
29	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
30	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
31	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
32	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
33	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
34	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

Выводы

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

Сложность BSA проявляется также в большом количестве параметров, требующих тщательной настройки для достижения оптимальных результатов. Для оптимизации параметров алгоритма мне пришлось написать эксперта для работы в режиме математических расчетов штатного тестераMetaTrader 5, который помог найти хорошие внешние параметры, обеспечившие для алгоритма 7-е место в рейтинге. Возможно, есть потенциал для дальнейшего улучшения результатов, и я призываю желающих поэкспериментировать с этим алгоритмом, уверенный в том, что в нем еще не полностью раскрыты все возможности для достижения лучших результатов, поскольку существует множество вариантов порядка выполнения и комбинирования последовательностей птичьего поведения (в статье раскрыты 4 типа поведения). 

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

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

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

Плюсы и минусы алгоритма птичьего роя (BSA):

Плюсы:

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

Минусы:

1. Сложная реализация.
2. Невысокая сходимость.
3. Низкая масштабируемость на гладких функциях, таких как Hilly (проблемы с задачами высокой размерности).

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