Алгоритм искусственного кооперативного поиска (Artificial Cooperative Search, ACS)

Содержание:

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

1. Введение

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

1. Цветковые растения и опылители:

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

2. Грибы и корни растений (микориза):

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

3. Термиты и симбиотические бактерии:

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

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

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

1. Колонии муравьев:

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

2. Пчелиные семьи:

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

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

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

Алгоритм ACS был предложен Пинаром Чивичиоглу в 2013 году. Он начинает работать, используя две базовые популяции, содержащие кандидатные решения в пределах доверительной области. Затем алгоритм создает две новые популяции — хищников и жертв, путем отображения значений из начальных популяций α и β с использованием случайных шагов и двоичной матрицы. Кроме того, пятая популяция рассчитывается на основе значений в популяциях хищников и жертв. Процесс включает в себя обновление начальных популяций в течение указанного числа итераций, при этом лучшее решение берется из этих двух популяций.

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

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

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

Алгоритм искусственного кооперативного поиска (ACS) работает следующим образом:

1. Инициализация. Задается размер популяции "popSize", количество переменных "N", нижние "XLow" и верхние "XHi" границы для переменных, а также вероятность биологического взаимодействия в ACS "Probab". Затем генерируются начальные позиции популяций "A" и "B" и вычисляются их значения приспособленности "YA" и "YB".

2. Цикл по итерациям. На каждой итерации выполняются следующие шаги:

• Выбор. Определяется, какой набор агентов из популяций "A" или "B" будет использоваться в качестве "хищника" на текущей итерации.
• Перетасовка "добычи". Позиции агентов в выбранном наборе перемешиваются.
• Мутация. Позиции агентов обновляются с использованием случайно сгенерированного коэффициента масштаба "R". "Хищники" мутируют, используя информацию о векторах решений "добычи".
  
• Заполнение бинарной матрицы "M". Создается бинарная матрица "M", которая определяет, какие переменные будут обновлены на текущей итерации.
• Обновление позиций агентов. Позиции агентов обновляются с учетом значений в матрице "M". Если значение в "M" равно 1, то соответствующая переменная агента обновляется.
• Контроль границ. Если обновленная позиция агента выходит за пределы заданных границ, она корректируется.
• Обновление выбора. На этом этапе лучшие решения сохраняются для следующей итерации алгоритма.
• Обновление глобального лучшего решения. Если найдено лучшее решение, оно сохраняется.

3. Возврат результата. В конце работы алгоритма возвращаются глобальное лучшее решение и его значение приспособленности.

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

Матрица "M" представляет собой двумерный массив с "popSize" строками (количество кандидатов в популяции) и "N" столбцами (количество переменных в каждом кандидате). Каждый элемент матрицы может быть либо 0, либо 1. Матрица "M" используется для определения, какие кандидаты будут выбраны для дальнейшего обновления в популяции. Значения 0 и 1 в матрице указывают, будет ли соответствующий кандидат выбран для обновления на основе случайных значений "Rand" и вероятности взаимодействия "Probab".
Матрица "M" помогает регулировать процесс выбора кандидатов для обновления в популяции. Таким образом, матрица "M" играет ключевую роль в процессе эволюции популяции и поиске оптимального решения в ACS.

Давайте подробно рассмотрим каждый шаг алгоритма ACS в виде псевдокода:

1. Инициализация:
   - Задаются параметры:
       - popSize - размер популяции
       - N - количество переменных
       - MaxIter - максимальное число итераций
       - XLow - нижние пределы для переменных
       - XHi - верхние пределы для переменных
       - Probab - вероятность биологического взаимодействия
   - Rand - функция, возвращающая равномерно распределенные числа в диапазоне (0, 1)
   - GlobMax инициализируется отрицательной DBL_MAX

2. Основной цикл:
   - Для каждого элемента популяции (I = 1 до popSize):
      - Для каждой переменной (J = 1 до N):
        - Вычисляются начальные значения A(I,J) и B(I,J) в диапазоне [XLow(J), XHi(J)]
     - Вычисляются начальные значения целевой функции YA(I) = Fx(A(I,:)) и YB(I) = Fx(B(I,:))
   - Начинается основной цикл по итерациям (Iter = 1 до MaxIter)

3. Выбор:
   - Случайно выбирается, будет ли использоваться A или B в качестве хищника (Predator):
     - Если Rand < 0.5, то Predator= A, Ypred = YA, Key = 1
     - Иначе Predator = B, Ypred = YB, Key = 2
   - Случайно выбирается, будет ли использоваться A или B в качестве жертвы (Prey):
      - Если Rand < 0.5, то Prey = A
      - Иначе Prey = B
   - Prey перемешивается случайным образом
   - Вычисляется параметр R:
      - Если Rand < 0.5, то R = 4 * Rand * (Rand - Rand)
      - Иначе R = 1/exp(4 * Rand)
   - Создается двоичная матрица M размера popSize x N, заполненная единицами
   - Случайно устанавливаются некоторые элементы матрицы M в 0 с вероятностью Probab
   - Если Rand < Probab, то случайно устанавливаются некоторые элементы матрицы M в 0 или 1
   - Для каждой строки матрицы M, если сумма элементов равна N, то случайно выбирается один элемент и устанавливается в 0

4. Мутация:
   - Вычисляется новое значение X = Predator + R * (Prey - Predator)
   - Для каждого элемента популяции (I = 1 до popSize) и каждой переменной (J = 1 до N):
     - Если соответствующий элемент матрицы M больше 0, то X(I,J) = Predator(I,J)
     - Если X(I,J) выходит за пределы [XLow(J), XHi(J)], то X(I,J) устанавливается случайным значением в этом диапазоне

5. Обновление выбора:
   - Для каждого элемента популяции (I = 1 до popSize):
     - Если Fx(X(I,:)) < Ypred(i), то Predator(I,:) = X(I,:) и Ypred(I) = Fx(X(I,:))
   - Если Key = 1, то A = Predator и YA = Ypred, иначе B = Predator и YB = Ypred
   - Ybest = min(Ypred)
   - Ibest = индекс строки Predator, соответствующей Ybest
   - Если Ybest > GlobMax, то GlobMax = Ybest и GlobMax = Predator(Ibest,:)

6. Возврат результата:
   - Возвращаются GlobMax и вектор GlobMaxX

Переходим к описанию реализации алгоритма ACS. Для описания популяции (которых в алгоритме пять) будем использовать простейшую структуру "S_D ":

• c [] - это массив для хранения координат (оптимизируемые параметры задачи)
  
• Init (int coords) - метод изменяет размер массива "c" до размера, указанного в "coords" (количество координат), с помощью функции "ArrayResize"

В общем, эта структура используется для создания объекта, который содержит массив вещественных чисел. Метод "Init" используется для изменения размера этого массива.

//——————————————————————————————————————————————————————————————————————————————
struct S_D
{
    void Init (int coords)
    {
      ArrayResize (c, coords);
    }
    double c [];
};
//——————————————————————————————————————————————————————————————————————————————

Для описания матрицы "M" создадим структуру "S_C", которая отличается от структуры "S_D" типом поля:

• c[] - массив, хранит символы матрицы "0" и "1"
  
• Init (int coords) - метод изменяет размер массива "c" до размера, указанного в "coords", с помощью функции "ArrayResize"

//——————————————————————————————————————————————————————————————————————————————
struct S_C
{
    void Init (int coords)
    {
      ArrayResize (c, coords);
    }
    char c [];
};
//——————————————————————————————————————————————————————————————————————————————

Алгоритм опишем в виде класса "C_AO_ACS", который является производным от базового класса "C_AO" и содержит поля:

•  ~C_AO_ACS () { } - деструктор класса, вызывается при удалении объекта класса. В данном случае деструктор пустой.
• C_AO_ACS () - конструктор класса, который инициализирует члены данных класса и изменяет размер массива "params" и назначает значения параметров алгоритма по умолчанию.
• SetParams () - метод устанавливает значения "popSize" и "bioProbab" на основе значений в массиве "params".
• Init () - метод принимает несколько аргументов и возвращает булево значение. 
  
• Moving () и Revision () - это методы, в которых заключена основная логика работы алгоритма.
• bioProbab - член данных, хранит вероятность биологического взаимодействия.
• S_D A [], S_D B [], S_D Predator [], S_D Prey [], S_C M [], double YA [], double YB [], double Ypred [], int Key, int phase - приватные члены данных класса.
• ArrayShuffle () - приватный метод, перемешивает элементы массива.
  

//——————————————————————————————————————————————————————————————————————————————
class C_AO_ACS : public C_AO
{
  public: //--------------------------------------------------------------------
  ~C_AO_ACS () { }
  C_AO_ACS ()
  {
    ao_name = "ACS";
    ao_desc = "Artificial Cooperative Search";
    ao_link = "https://www.mql5.com/ru/articles/15004";

    popSize   = 1;   //population size
    bioProbab = 0.9; //biological interaction probability

    ArrayResize (params, 2);

    params [0].name = "popSize";   params [0].val = popSize;
    params [1].name = "bioProbab"; params [1].val = bioProbab;
  }

  void SetParams ()
  {
    popSize   = (int)params [0].val;
    bioProbab = params      [1].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 ();

  //----------------------------------------------------------------------------
  double bioProbab; //biological interaction probability

  private: //-------------------------------------------------------------------
  S_D A              [];
  S_D B              [];
  S_D Predator       [];
  S_D Prey           [];

  S_C M              [];

  double YA          [];
  double YB          [];
  double Ypred       [];

  int Key;
  int phase;

  void ArrayShuffle (double &arr []);
};
//——————————————————————————————————————————————————————————————————————————————

Далее представим метод "Init" класса "C_AO_ACS". Метод выполняет инициализацию объекта класса:

• Init () - объявление метода. Он принимает четыре аргумента: минимальный диапазон поиска "rangeMinP", максимальный диапазон поиска "rangeMaxP", шаг поиска "rangeStepP" и количество эпох "epochsP", которое по умолчанию равно 0.
• if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; - вызов функции "StandardInit", выполняющей стандартную инициализацию базового класса. Если "StandardInit" возвращает "false", то метод "Init" немедленно завершается и возвращает "false".
• В цикле for (int i = 0; i < popSize; i++) каждый элемент массивов "A", "B", "Predator", "Prey" и "M" инициализируется с помощью метода "Init".
• ArrayResize (YA, popSize) и подобные строки изменяют размер массивов "YA", "YB" и "Ypred" до размера "popSize".
• ArrayInitialize (YA, -DBL_MAX) и подобные строки инициализируют все элементы массивов "YA", "YB" и "Ypred" значением "-DBL_MAX".
• Во вложенном цикле "for" каждый элемент "c" каждого объекта в массивах "A" и "B" инициализируется случайным значением в заданном диапазоне.
• phase = 0 устанавливает значение phase равным 0.
  

Оригинальный алгоритм, описанный авторами, не имеет разделения логики на фазы. Для реализации алгоритма в стиле, принятом нами для всех популяционных алгоритмов, мне пришлось добавить фазы. Это было необходимо, поскольку в ACS используется предварительный расчет приспособленности агентов для двух популяций "А" и "B". Чтобы выполнить эти операции последовательно в методах, было добавлено разделение на фазы.

//——————————————————————————————————————————————————————————————————————————————
bool C_AO_ACS::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 (A,         popSize);
  ArrayResize (B,         popSize);
  ArrayResize (Predator,  popSize);
  ArrayResize (Prey,      popSize);

  ArrayResize (M,         popSize);

  for (int i = 0; i < popSize; i++)
  {
    A         [i].Init (coords);
    B         [i].Init (coords);
    Predator  [i].Init (coords);
    Prey      [i].Init (coords);

    M         [i].Init (coords);
  }

  ArrayResize (YA,    popSize);
  ArrayResize (YB,    popSize);
  ArrayResize (Ypred, popSize);

  ArrayInitialize (YA,    -DBL_MAX);
  ArrayInitialize (YB,    -DBL_MAX);
  ArrayInitialize (Ypred, -DBL_MAX);

  // Initialization
  for (int i = 0; i < popSize; i++)
  {
    for (int j = 0; j < coords; j++)
    {
      A [i].c [j] = rangeMin [j] + (rangeMax [j] - rangeMin [j]) * u.RNDprobab();
      B [i].c [j] = rangeMin [j] + (rangeMax [j] - rangeMin [j]) * u.RNDprobab();
    }
  }

  phase = 0;
 
  return true;
}
//——————————————————————————————————————————————————————————————————————————————

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

• if (phase == 0) - на этой фазе копируются особи из популяции "A".
  
• if (phase == 1) - на этой фазе возвращаем приспособленность особей популяции "А" и копируем особи из популяции "B".
• if (phase == 2) - на этой фазе возвращаем приспособленность особей популяции "B" и далее выполняется вся дальнейшая логика алгоритма. 
  
• Selection - блок выполняет операцию селекции. В зависимости от случайного числа копируются массивы "A" или "B" в массив "Predator", а соответствующие значения копируются в массив "Ypred".
• Permutation of Prey - в этом блоке выполняется операция перестановки элементов массива "Prey".
• R - объявляется переменная, которая затем инициализируется одним из двух возможных значений в зависимости от случайного числа.
• Fill binary matrix M with 1s - в этом блоке двоичная матрица "M" заполняется единицами.
• Additional operations with matrix M -  блок выполняет дополнительные операции с матрицей "M", включая изменение некоторых ее элементов на 0 или 1, в зависимости от случайного числа и вероятности биологического взаимодействия "bioProbab".
• Mutation - блок выполняет операцию мутации, в которой элементы массива "a" изменяются на основе элементов массивов "Predator" и "Prey", а также значения "R".
• Crossover - блок выполняет операцию скрещивания, в которой некоторые элементы массива "a" заменяются элементами массива "Predator".
• Boundary control - в этом блоке выполняется контроль выхода за границы, при котором элементы массива "a", выходящие за пределы заданного диапазона оптимизируемых параметров, заменяются случайными значениями в этом диапазоне.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ACS::Moving ()
{
  //----------------------------------------------------------------------------
  if (phase == 0)
  {
    for (int i = 0; i < popSize; i++) ArrayCopy (a [i].c, A [i].c);

    phase++;
    return;
  }

  //----------------------------------------------------------------------------
  if (phase == 1)
  {
    for (int i = 0; i < popSize; i++) YA [i] = a [i].f;
    for (int i = 0; i < popSize; i++) ArrayCopy (a [i].c, B [i].c);

    phase++;
    return;
  }

  //----------------------------------------------------------------------------
  if (phase == 2)
  {
    for (int i = 0; i < popSize; i++) YB [i] = a [i].f;

    phase++;
  }

  //----------------------------------------------------------------------------
  // Selection
  if (u.RNDprobab () < 0.5)
  {
    for (int i = 0; i < popSize; i++)
    {
      ArrayCopy (Predator [i].c, A [i].c);
    }

    ArrayCopy (Ypred, YA);
    Key = 1;
  }
  else
  {
    for (int i = 0; i < popSize; i++)
    {
      ArrayCopy (Predator [i].c, B [i].c);
    }

    ArrayCopy (Ypred, YB);
    Key = 2;
  }

  if (u.RNDprobab () < 0.5)
  {
    for (int i = 0; i < popSize; i++)
    {
      ArrayCopy (Prey [i].c, A [i].c);
    }
  }
  else
  {
    for (int i = 0; i < popSize; i++)
    {
      ArrayCopy (Prey [i].c, B [i].c);
    }
  }

  // Permutation of Prey
  for (int i = 0; i < popSize; i++)
  {
    ArrayShuffle (Prey [i].c);
  }

  double R;

  if (u.RNDprobab () < 0.5)
  {
    R = 4 * u.RNDprobab () * u.RNDfromCI (-1.0, 1.0);
  }
  else R = 1 / MathExp (4 * MathRand () / 32767.0);

  // Fill binary matrix M with 1s
  for (int i = 0; i < popSize; i++)
  {
    for (int j = 0; j < coords; j++)
    {
      M [i].c [j] = 1;
    }
  }

  // Additional operations with matrix M
  for (int i = 0; i < popSize; i++)
  {
    for (int j = 0; j < coords; j++)
    {
      if (u.RNDprobab () < bioProbab)
      {
        M [i].c [j] = 0;
      }
    }
  }

  for (int i = 0; i < popSize; i++)
  {
    for (int j = 0; j < coords; j++)
    {
      if (u.RNDprobab () < bioProbab)
      {
        M [i].c [j] = 1;
      }
      else
      {
        M [i].c [j] = 0;
      }
    }
  }

  for (int i = 0; i < popSize; i++)
  {
    int sum = 0;

    for (int c = 0; c < coords; c++) sum += M [i].c [c];

    if (sum == coords)
    {
      int j = MathRand () % coords;
      M [i].c [j] = 0;
    }
  }

  // Mutation
  for (int i = 0; i < popSize; i++)
  {
    for (int j = 0; j < coords; j++)
    {
      a [i].c [j] = Predator [i].c [j] + R * (Prey [i].c [j] - Predator [i].c [j]);

      // Crossover
      if (M [i].c [j] > 0)
      {
        a [i].c [j] = Predator [i].c [j];
      }

      // Boundary control
      if (a [i].c [j] < rangeMin [j] || a [i].c [j] > rangeMax [j])
      {
        a [i].c [j] = rangeMin [j] + (rangeMax [j] - rangeMin [j]) * u.RNDprobab ();
      }
    }
  }
 
  for (int i = 0; i < popSize; i++)
  {
    for (int j = 0; j < coords; j++)
    {
      a [i].c [j] = u.SeInDiSp (a [i].c [j], rangeMin [j], rangeMax [j], rangeStep [j]);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

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

• if (phase < 3) return - основная логика метода не выполняется, пока не будут выполнены все три фазы подготовки популяций для дальнейшего взаимодействия между ними.
• Selection update - блок выполняет обновление выбора особей. Для каждой особи массива "a" проверяется, превышает ли его значение приспособленности "f" соответствующее значение в массиве "Ypred".
• if (Key == 1) и else - в этих блоках, в зависимости от значения "Key", элементы массива "Predator" копируются из массива "A" или "B", а соответствующие значения "Ypred" копируются из массива "YA" или "YB".
• ArraySort (Ypred); ArrayReverse (Ypred, 0, WHOLE_ARRAY) - массив "Ypred", содержащий значения приспособленности, сортируется, а затем переворачивается, чтобы значения были упорядочены в порядке убывания.
• Ybest = Ypred [0]; int Ibest = ArrayMaximum (Ypred) - здесь определяются "Ybest", как максимальное значение в "Ypred", и "Ibest", как индекс этого максимального значения.
• if (Ybest > fB) - если "Ybest" превышает текущее лучшее значение "fB", то "fB" обновляется, а соответствующие элементы массивов "a" и "cB" копируются из массива "Predator".

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ACS::Revision ()
{
  if (phase < 3) return;

  // Selection update
  for (int i = 0; i < popSize; i++)
  {
    double d = a [i].f;

    if (d > Ypred [i])
    {
      ArrayCopy (Predator [i].c, a [i].c);
      Ypred [i] = d;
    }
  }

  if (Key == 1)
  {
    for (int i = 0; i < popSize; i++)
    {
      ArrayCopy (A [i].c, Predator [i].c);
    }

    ArrayCopy (YA, Ypred);
  }
  else
  {
    for (int i = 0; i < popSize; i++)
    {
      ArrayCopy (B [i].c, Predator [i].c);
    }

    ArrayCopy (YB, Ypred);
  }

  ArraySort (Ypred);
  ArrayReverse (Ypred, 0, WHOLE_ARRAY);
  double Ybest = Ypred [0];
  int Ibest = ArrayMaximum (Ypred);

  if (Ybest > fB)
  {
    fB = Ybest;
    ArrayCopy (a [Ibest].c, Predator [Ibest].c);
    ArrayCopy (cB, Predator [Ibest].c);
  }
}
//——————————————————————————————————————————————————————————————————————————————

Метод "ArrayShuffle" класса "C_AO_ACS" выполняет операцию случайной перетасовки элементов в массиве.

• for (int i = n - 1; i > 0; i--) - цикл проходит по массиву "arr" в обратном порядке, начиная с последнего элемента.
• j = MathRand () % (i + 1) - определяется переменная "j" как случайное число от "0" до "i".
• tmp = arr [i]; arr [i] = arr [j]; arr [j] = tmp - эти строки выполняют обмен местами элементов "arr[i]" и "arr[j]".

В результате этого метода элементы массива "arr" перемешиваются в случайном порядке.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ACS::ArrayShuffle (double &arr [])
{
  int n = ArraySize (arr);
  for (int i = n - 1; i > 0; i--)
  {
    int j = MathRand () % (i + 1);
    double tmp = arr [i];
    arr [i] = arr [j];
    arr [j] = tmp;
  }
}
//——————————————————————————————————————————————————————————————————————————————

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

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

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

На распечатке результатов работы алгоритма на тестовым стенде, при параметре в 10 особей в популяции, при неизменном количестве запусков фитнес-функции в 10 000, алгоритм достигает результата 49,97%.

ACS|Artificial Cooperative Search|10.0|0.9|
=============================
5 Hilly's; Func runs: 10000; result: 0.8213829114300768
25 Hilly's; Func runs: 10000; result: 0.5418951009344799
500 Hilly's; Func runs: 10000; result: 0.2811381329747021
=============================
5 Forest's; Func runs: 10000; result: 0.9750514085798038
25 Forest's; Func runs: 10000; result: 0.5078176955906151
500 Forest's; Func runs: 10000; result: 0.20112458337102135
=============================
5 Megacity's; Func runs: 10000; result: 0.736923076923077
25 Megacity's; Func runs: 10000; result: 0.31446153846153846
500 Megacity's; Func runs: 10000; result: 0.11721538461538572
=============================
All score: 4.49701 (49.97%)

На распечатке результатов работы алгоритма на тестовым стенде, при параметре 3 особи в популяции, при неизменном количестве запусков фитнес-функции в 10 000, алгоритм достигает результата 55,23%.

ACS|Artificial Cooperative Search|3.0|0.9|
=============================
5 Hilly's; Func runs: 10000; result: 0.8275253778390631
25 Hilly's; Func runs: 10000; result: 0.6349216357701294
500 Hilly's; Func runs: 10000; result: 0.29382093872076825
=============================
5 Forest's; Func runs: 10000; result: 0.9998874875962974
25 Forest's; Func runs: 10000; result: 0.6985911632646721
500 Forest's; Func runs: 10000; result: 0.2132502183011688
=============================
5 Megacity's; Func runs: 10000; result: 0.7507692307692307
25 Megacity's; Func runs: 10000; result: 0.4270769230769231
500 Megacity's; Func runs: 10000; result: 0.1252615384615397
=============================
All score: 4.97110 (55.23%)

На распечатке результатов работы алгоритма на тестовым стенде, при параметре 1 особь в популяции, при неизменном количестве запусков фитнес-функции в 10 000, алгоритм достигает результата 58,06%.

ACS|Artificial Cooperative Search|1.0|0.9|
=============================
5 Hilly's; Func runs: 10000; result: 0.7554725186591347
25 Hilly's; Func runs: 10000; result: 0.7474431551529281
500 Hilly's; Func runs: 10000; result: 0.3040669213089683
=============================
5 Forest's; Func runs: 10000; result: 0.9999999999993218
25 Forest's; Func runs: 10000; result: 0.888607840003743
500 Forest's; Func runs: 10000; result: 0.2241289484506152
=============================
5 Megacity's; Func runs: 10000; result: 0.6907692307692308
25 Megacity's; Func runs: 10000; result: 0.4818461538461539
500 Megacity's; Func runs: 10000; result: 0.1332153846153859
=============================
All score: 5.22555 (58.06%)

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

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

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

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

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

По итогам тестирования алгоритм занял 8 место. ACS особо отличился на функциях Forest и Megacity.

№	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,99989	0,99518	0,42835	2,42341	0,96153	0,96181	0,32027	2,24360	0,91385	0,95908	0,24220	2,11512	6,782	75,36
2	CLA	code lock algorithm	0,95345	0,87107	0,37590	2,20042	0,98942	0,91709	0,31642	2,22294	0,79692	0,69385	0,19303	1,68380	6,107	67,86
3	(P+O)ES	(P+O) evolution strategies	0,92256	0,88101	0,40021	2,20379	0,97750	0,87490	0,31945	2,17185	0,67385	0,62985	0,18634	1,49003	5,866	65,17
4	CTA	comet tail algorithm	0,95346	0,86319	0,27770	2,09435	0,99794	0,85740	0,33949	2,19484	0,88769	0,56431	0,10512	1,55712	5,846	64,96
5	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
6	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
7	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
8	ACS	artificial cooperative search	0,75547	0,74744	0,30407	1,80698	1,00000	0,88861	0,22413	2,11274	0,69077	0,48185	0,13322	1,30583	5,226	58,06
9	TSEA	turtle shell evolution algorithm	0,96798	0,64480	0,29672	1,90949	0,99449	0,61981	0,22708	1,84139	0,69077	0,42646	0,13598	1,25322	5,004	55,60
10	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
11	BSA	bird swarm algorithm	0,89306	0,64900	0,26250	1,80455	0,92420	0,71121	0,24939	1,88479	0,69385	0,32615	0,10012	1,12012	4,809	53,44
12	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
13	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
14	(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
15	BSO	brain storm optimization	0,93736	0,57616	0,29688	1,81041	0,93131	0,55866	0,23537	1,72534	0,55231	0,29077	0,11914	0,96222	4,498	49,98
16	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
17	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
18	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
19	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
20	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
21	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
22	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
23	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
24	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
25	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
26	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
27	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
28	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
29	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
30	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
31	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
32	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
33	Boids	boids algorithm	0,43340	0,30581	0,25425	0,99346	0,35718	0,20160	0,15708	0,71586	0,27846	0,14277	0,09834	0,51957	2,229	24,77
34	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
35	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
36	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
37	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
38	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
39	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
40	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

Выводы

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

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

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

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

Плюсы и минусы алгоритма искусственного кооперативного поиска (ACS):

Плюсы:

1. Малое количество внешних параметров (всего лишь 1).
   
2. Хорошая сходимость на различных типах функций.

Минусы:

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

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

• github: https://github.com/JQSakaJoo/Population-optimization-algorithms-MQL5
• CodeBase: https://www.mql5.com/ru/code/49355