Популяционные алгоритмы оптимизации: Искуственная Пчелиная Колония (Artificial Bee Colony - ABC)

Andrey Dik | 23 ноября, 2022

Содержание:

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

1. Введение

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

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

В течение многих лет только учёные биологи исследовали пчелиные методы поиска, однако с ростом заинтересованности роевым поведением в природе для создания новых алгоритмов оптимизации в 2005 году результатами исследований заинтересовался профессор Дервис Карабога. Он опубликовал научную статью и первый описал в ней модель роевого интеллекта, на создание которой его и вдохновили пчелиные танцы. Модель получила название искусственной пчелиной колонии (Artificial Bee Colony).

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

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

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

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

Схематично распределение рабочих пчел по областям можно наглядно представить рисунком 1.

Рисунок 1. Количество пчел в областях в зависимости от их ранга.

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

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

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

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

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

Рисунок 2. Область с рангом ниже должна быть смещена.

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

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

Перейдем к самому алгоритму. Шаги выполнения перечислены ниже:

1. Все пчелы как разведчики летят по пространству поиска случайным образом.
2. Измеряем количество нектара полученного от каждой пчелы.
3. Сортировка пчел.
4. Назначаем области согласно информации от пчел о количестве нектара.
5. Отправляем рабочих пчел в области, чем больше нектара в области, тем больше пчел будет отправлено.
6. Посылаем пчел-разведчиков в окрестности случайно выбранной области.
   
7. Измеряем количество нектара полученного от каждой пчелы.
8. Ранжируем области по количеству нектара.
   
9. Повторить п.4 до выполнения критерия останова.

Для простоты визуального восприятия, составим блок-схему алгоритма на рисунке 3.

Рисунок 3. Блок-схема алгоритма.

Опишем более подробно код алгоритма Пчелиной колонии.

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

//——————————————————————————————————————————————————————————————————————————————
struct S_Bee
{
  double c []; //coordinates
  int    aInd; //area index
  double n;    //nectar
};
//——————————————————————————————————————————————————————————————————————————————

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

//——————————————————————————————————————————————————————————————————————————————
struct S_Area
{
  void Init (int coordinatesNumber)
  {
    n = -DBL_MAX;

    ArrayResize (cC, coordinatesNumber);
    ArrayResize (cB, coordinatesNumber);
  }

  double cC   []; //center coordinates
  double cB   []; //best coordinates
  double n;       //nectarAmount
};
//——————————————————————————————————————————————————————————————————————————————

Танец пчел опишем в виде структуры, массив которой будет соответствовать количеству областей.

//——————————————————————————————————————————————————————————————————————————————
struct S_BeeDance
{
  double start;
  double end;
};
//——————————————————————————————————————————————————————————————————————————————

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

//——————————————————————————————————————————————————————————————————————————————
class C_AO_ABC //Bees Hive
{
  //============================================================================
  public: S_Area areas     []; //nectar collection areas
  public: double rangeMax  []; //maximum search range
  public: double rangeMin  []; //manimum search range
  public: double rangeStep []; //step search
  public: S_Bee  bees      []; //all the bees of the hive
  public: double cB        []; //best coordinates
  public: double nB;           //nectar of the best coordinates

  public: void InitHive (const int    coordinatesP,      //number of opt. parameters
                         const int    beesNumberP,       //bees number
                         const int    workerBeesNumberP, //worker bees number
                         const int    areasNumberP,      //areas number
                         const double collectionRadiusP, //collection radius
                         const double scoutAreaRadiusP); //scout area radius

  public: void TasksForBees ();
  public: void CollectingNectar ();

  //============================================================================
  private: void   BeeFlight      (double &cC [] , S_Bee &bee);
  private: void   ScoutBeeFlight (double &cC [] , S_Bee &bee);
  private: void   MarkUpAreas    ();
  private: void   SortingBees    ();
  private: void   SortingAreas   ();
  private: double SeInDiSp       (double In, double InMin, double InMax, double Step);
  private: double RNDfromCI      (double Min, double Max);
  private: double Scale          (double In, double InMIN, double InMAX, double OutMIN, double OutMAX,  bool Revers);

  private: int    coordinates;      //coordinates number
  private: int    beesNumber;       //the number of all bees
  private: int    workerBeesNumber; //worker bees number
  private: int    areasNumber;      //areas number
  private: S_Bee  beesT       [];   //temporary, for sorting
  private: S_Area areasT      [];   //temporary, for sorting
  private: int    indA        [];   //array for indexes when sorting
  private: double valA        [];   //array for nectar values when sorting
  private: int    indB        [];   //array for indexes when sorting
  private: double valB        [];   //array for nectar values when sorting
  private: double areasRadius [];   //radius for each coordinate
  private: double scoutRadius [];   //scout radius for each coordinate

  private: double collectionRadius;   //collection radius
  private: double scoutAreaRadius;    //scout area radius
  private: double hypersphereRadius;  //hypersphere radius
  private: double distHyperspCenters; //distance hyperspheres centers
  private: double scoutHyperspRadius; //scout hypersphere radius
  private: bool   scouting;           //scouting flag

  private: S_BeeDance beeDance [];    //bee dance
};
//——————————————————————————————————————————————————————————————————————————————

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

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ABC::InitHive (const int    coordinatesP,      //number of opt. parameters
                         const int    beesNumberP,       //bees number
                         const int    workerBeesNumberP, //worker bees number
                         const int    areasNumberP,      //areas number
                         const double collectionRadiusP, //collection radius
                         const double scoutAreaRadiusP)  //scout area radius
{
  MathSrand (GetTickCount ());
  scouting = false;
  nB       = -DBL_MAX;

  coordinates      = coordinatesP;
  beesNumber       = beesNumberP;
  workerBeesNumber = workerBeesNumberP;
  areasNumber      = areasNumberP < 3 ? 3 : areasNumberP;

  collectionRadius = collectionRadiusP; //collection radius
  scoutAreaRadius  = scoutAreaRadiusP;  //scout area radius

  ArrayResize (areas,  areasNumber);
  ArrayResize (areasT, areasNumber);
  for (int i = 0; i < areasNumber; i++)
  {
    areas  [i].Init (coordinates);
    areasT [i].Init (coordinates);
  }

  ArrayResize (beeDance, areasNumber);

  ArrayResize (rangeMax,  coordinates);
  ArrayResize (rangeMin,  coordinates);
  ArrayResize (rangeStep, coordinates);
  ArrayResize (cB,        coordinates);

  ArrayResize (indA, areasNumber);
  ArrayResize (valA, areasNumber);

  ArrayResize (areasRadius, coordinates);
  ArrayResize (scoutRadius, coordinates);
  for (int i = 0; i < coordinates; i++)
  {
    areasRadius [i] = (rangeMax [i] - rangeMin [i]) * collectionRadius;
    scoutRadius [i] = (rangeMax [i] - rangeMin [i]) * scoutAreaRadius;
  }

  double sqr = 0.0;
  for (int i = 0; i < coordinates; i++) sqr += areasRadius [i] * areasRadius [i];
  hypersphereRadius  = MathSqrt (sqr) * collectionRadius;

  distHyperspCenters = hypersphereRadius * 2.0;

  sqr = 0.0;
  for (int i = 0; i < coordinates; i++) sqr += scoutRadius [i] * scoutRadius [i];
  scoutHyperspRadius = MathSqrt (sqr) * scoutAreaRadius;

  ArrayResize (indB, beesNumber);
  ArrayResize (valB, beesNumber);

  ArrayResize (bees,  beesNumber);
  ArrayResize (beesT, beesNumber);
  for (int i = 0; i < beesNumber; i++)
  {
    ArrayResize (bees  [i].c, coordinates);
    ArrayResize (beesT [i].c, coordinates);
    bees  [i].n = -DBL_MAX;
    beesT [i].n = -DBL_MAX;
  }
}
//——————————————————————————————————————————————————————————————————————————————

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

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ABC::TasksForBees ()
{
  if (!scouting)
  {
    nB = -DBL_MAX;
  }
  MarkUpAreas ();
}
//——————————————————————————————————————————————————————————————————————————————

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

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ABC::CollectingNectar ()
{
  if (!scouting)
  {
    SortingBees ();

    for (int a = 0; a <areasNumber; a++)
    {
      ArrayCopy (areas [a].cB, bees [a].c, 0, 0, WHOLE_ARRAY);
      areas [a].n = bees [a].n;
    }

    scouting = true;
  }
  else
  {
    //transfer the nectar to the hive---------------------------------------------
    for (int b = 0; b < beesNumber; b++)
    {
      if (bees [b].n > areas [bees [b].aInd].n)
      {
        ArrayCopy (areas [bees [b].aInd].cB, bees [b].c, 0, 0, WHOLE_ARRAY);
        areas [bees [b].aInd].n = bees [b].n;
      }

      if (bees [b].n > nB)
      {
        ArrayCopy (cB, bees [b].c, 0, 0, WHOLE_ARRAY);
        nB = bees [b].n;
      }
    }

    SortingAreas ();
  }
}
//——————————————————————————————————————————————————————————————————————————————

Метод MarkUpAreas () достоин того, чтобы его рассмотреть детально, разобьем код на части.

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

//if the areas is not scouting - send all the bees to scouting----------------
if (!scouting)
{
  for (int b = 0; b < beesNumber; b++)
  {
    for (int c = 0; c < coordinates; c++)
    {
      bees [b].c [c] = RNDfromCI (rangeMin [c], rangeMax [c]);
      bees [b].c [c] = SeInDiSp  (bees [b].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
}

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

for (int s = 0; s < areasNumber; s++)
{
  //move the center of the area to the best point in with more nectar-------
  ArrayCopy (areas [s].cC, areas [s].cB, 0, 0, WHOLE_ARRAY);

  //ordinary area-----------------------------------------------------------
  if (s != 0)
  {
    //check if there is no intersection of a region with a region of higher rank
    //measure the distance from the centers of the regions
    double centersDistance = 0.0;

    for (int c = 0; c < coordinates; c++) centersDistance += pow (areas [s].cC [c] - areas [s - 1].cC [c], 2.0);
    centersDistance = MathSqrt (centersDistance);

    //the areas intersect, then need to move the current area
    if (centersDistance < distHyperspCenters)
    {
      double incrementFactor = (distHyperspCenters - centersDistance) / centersDistance;
      double coordDistance   = 0.0;

      for (int c = 0; c < coordinates; c++)
      {
        coordDistance = areas [s].cC [c] - areas [s - 1].cC [c];
        areas [s].cC [c] = areas [s].cC [c] + (coordDistance * incrementFactor);

        areas [s].cC [c] = SeInDiSp (areas [s].cC [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }
  }
}

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

//send bees to the marked areas-----------------------------------------------
double r = 0.0;

beeDance [0].start = bees [0].n;
beeDance [0].end   = beeDance [0].start + (bees [0].n - bees [areasNumber - 1].n);

for (int a = 1; a < areasNumber; a++)
{
  if (a != areasNumber - 1)
  {
    beeDance [a].start = beeDance [a - 1].end;
    beeDance [a].end   = beeDance [a    ].start + (bees [a].n - bees [areasNumber - 1].n);
  }
  else
  {
    beeDance [a].start = beeDance [a - 1].end;
    beeDance [a].end   = beeDance [a    ].start + (bees [a - 1].n - bees [a].n) * 0.1;
  }
}

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

for (int b = 0; b < beesNumber; b++)
{
  if (b < workerBeesNumber)
  {
    r = RNDfromCI(beeDance [0].start, beeDance [areasNumber - 1].end);
        
    for (int a = 0; a < areasNumber; a++)
    {
      if (beeDance [a].start <= r && r < beeDance [a].end)
      {
        bees [b].aInd = a;
        break;
      }
    }

    BeeFlight (areas [bees [b].aInd].cC, bees [b]);
  }
  else
  {
    //choose the area to send the bees there
    r = RNDfromCI (0.0, areasNumber - 1);

    bees [b].aInd = (int)r; //area index

    ScoutBeeFlight (areas [bees [b].aInd].cC, bees [b]);
  }
}

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

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ABC::BeeFlight (double &cC [] , S_Bee &bee)
{
  double r = 0.0;

  for (int c = 0; c < coordinates; c++)
  {
    r  = RNDfromCI (0.0, 1.0);
    r  = r * r * r;
    r = Scale (r, 0.0, 1.0, 0.0, areasRadius [c], false);
    r *= RNDfromCI (0.0, 1.0) > 0.5 ? 1.0 : -1.0;

    bee.c [c] = SeInDiSp  (cC [c] + r, rangeMin [c], rangeMax [c], rangeStep [c]);
  }
}
//——————————————————————————————————————————————————————————————————————————————

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

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ABC::ScoutBeeFlight (double &cC [] , S_Bee &bee)
{
  double r = 0.0;

  for (int c = 0; c < coordinates; c++)
  {
    r  = RNDfromCI (areasRadius [c], areasRadius [c] + scoutRadius [c]);
    r *= RNDfromCI (0.0, 1.0) > 0.5 ? 1.0 : -1.0;

    bee.c [c] = SeInDiSp  (cC [c] + r, rangeMin [c], rangeMax [c], rangeStep [c]);
  }
}
//——————————————————————————————————————————————————————————————————————————————

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

//——————————————————————————————————————————————————————————————————————————————
//Sorting of bees
void C_AO_ABC::SortingBees ()
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
//Sorting of areas
void C_AO_ABC::SortingAreas ()
//——————————————————————————————————————————————————————————————————————————————

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

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

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

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

Вот и наши результаты работы алгоритма на тествовых функциях:

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

3. Модифицированная версия

Хотелось бы поговорить об одном интересном моменте. При разработке и проектировании любого алгоритма оптимизации всегда возникает вопрос: "Алгоритм работает так как задумывалось или есть где то в коде ошибка?". Дело в том, что процесс стохастического поиска случаен по самой своей природе, отсюда непонятно, полученные результаты оптимизации были в результате работы алгоритма, либо где то закралась ошибка, и действительно ли полученный результат неслучаен. Так и при написании алгоритма пчелиной колонии я столкнулся с подобным явлением. При первом тесте из пяти в составе набора тестов алгоритм явно застревал в местах, с которых и начинал поиск, совершенно не пытаясь сходиться. Что интересно, но этот баг удалось решить совершенно невероятным с точки зрения логики способом. Оказалось достаточно инициализировать класс улья дополнительно второй раз на первой эпохе, и это при том, что класс уже был предварительно инициализирован перед началом старта эпох (стр. 142 в файле Test_AO_ABC.mq5). Если кому то удастся разгадать эту тайну, то я буду рад услышать решение в комментариях к статье.

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

Теперь вместо структуры области будет такая структура:

//——————————————————————————————————————————————————————————————————————————————
struct S_BeesSwarm
{
  void Init (int coordinatesNumber, int beesNumber)
  {
    ArrayResize (bees, beesNumber);

    for (int i = 0; i < beesNumber; i++)
    {
      ArrayResize (bees [i].c, coordinatesNumber);
      bees [i].n = -DBL_MAX;
    }

    n = -DBL_MAX;

    ArrayResize     (cC, coordinatesNumber);
    ArrayInitialize (cC, -DBL_MAX);
  }

  S_Bee  bees []; //bees
  double cC   []; //center coordinates
  double cB   []; //best coordinates
  double n;       //nectarAmount
};
//——————————————————————————————————————————————————————————————————————————————

В этой структуре так же есть функция инициализации, но дополнительно присутствует массив пчел bees[].

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

1. Создать центр для первого роя и разместить пчел в окрестностях центра.
2. Создать центр для последующих роёв и проверить что бы расстояние от центра до предыдущих роёв было больше либо равно R*2 (два радиуса), разместить пчел в окрестностях центра.
3. Отправить пчел роя разведчиков так, что бы каждая из пчел была дальше остальных роёв на расстояние большее либо равное R (радиус).
4. Получить значение фитнес функции для всех пчел.
5. Сортировка роев.
6. Разместить пчел в окрестностях центра каждого роя.
7. Повторить с п.4. до выполнения критерия останова.

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

Принты результатов модифицированной версии:

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

Кстати. Баг с необходимостью повторной инициализации улья в модифицированной версии отсутсвует.

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

Подведём итоги. Удивительно, но алгоритм пчелиной колонии показал 100% сходимость во всех пяти тестах на двух тестовых функциях, гладкой Skin и дискретной Megacity, продемонстрировав тем самым феноменальную скорость и качество сходимости. Правда это касается только функций с двумя переменными. По показателю масштабируемости алгоритм уступает другим участникам рейтинговой таблицы, функции с многими переменными пчелиной колонии даются с трудом, это видно и на анимации тестового стенда и по результатам в таблице.

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