MetaTrader 5 / Примеры
preview
Популяционные алгоритмы оптимизации: Алгоритм боидов, или алгоритм стайного поведения (Boids Algorithm, Boids)

Популяционные алгоритмы оптимизации: Алгоритм боидов, или алгоритм стайного поведения (Boids Algorithm, Boids)

MetaTrader 5 — Примеры | 8 апреля 2024, 17:18
415 0
Andrey Dik
Andrey Dik

Содержание:

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


1. Введение

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

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

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

Алгоритм Boids (от англ. "boid" - сокращение от "bird-птица" и "оид" - подобие) представляет собой компьютерный алгоритм, созданный Крейгом Рейнольдсом (Craig Reynolds) в 1986 году, который моделирует поведение стай животных, в частности, птиц. Этот алгоритм был разработан с целью имитировать естественное поведение стай, где каждый индивидуум движется в соответствии с простыми правилами, что в итоге приводит к появлению коллективного поведения. В его основе лежат три следующих правила:

1. Сепарация (Separation). Каждый объект (или "boid") старается минимизировать возможность столкновения с ближайшими объектами.
2. Выравнивание (Alignment). Каждый объект стремится к тому, чтобы его направление движения было средним направлением движения объектов, находящихся поблизости.
3. Когезия (Cohesion). Каждый объект стремится к тому, чтобы его положение было близко к среднему положению объектов, находящихся поблизости.

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

Первоначально создание алгоритма Boids имело несколько целей и применений:

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

Интересным фактом является то, что алгоритм Boids послужил вдохновением для разработки других алгоритмов: например, роя частиц (PSO) и алгоритмов моделирования поведения толпы.

Алгоритм Boids остается популярным инструментом для моделирования коллективного поведения и продолжает быть объектом исследований и развития в различных областях науки и технологий.

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

Boids

Визуализация работы алгоритма Boids.

config

Окно настроек алгоритма Boids, вызываемое по клавише F3. Параметр "#reset" позволяет перезапустить алгоритм, применив значение "1".


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

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

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

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

Работа Крейга Рейнольдса над алгоритмом Boids, который моделирует стайное поведение, вдохновила на создание концепции роевого интеллекта. Роевый интеллект описывает коллективное поведение децентрализованной самоорганизующейся системы и к ним относится алгоритм PSO.

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

Алгоритм Boids имеет достаточно много внешних параметров, и каждый из них значительно влияет на характер движения боидов. Посмотрим на эти параметры:

  1. cohesionWeight - вес сцепления, определяет силу притягивания членов стаи друг к другу.
  2. cohesionDist - расстояние сцепления, определяет расстояние между членами стаи, при котором они начинают притягиваться друг к другу.
  3. separationWeight - вес разделения, определяет, насколько сильно члены стаи будут отталкиваться друг от друга.
  4. separationDist - расстояние разделения, определяет расстояние между членами стаи, при котором они начинают отталкиваться друг от друга.
  5. alignmentWeight - вес выравнивания, определяет, насколько сильно члены стаи будут выравниваться по направлению движения друг друга.
  6. alignmentDist - расстояние выравнивания, определяет расстояние между членами стаи, при котором они начинают выравниваться по направлению движения друг друга.
  7. minSpeed - минимальная скорость, параметр необходим для предотвращения остановки движения боидов.
  8. maxSpeed - максимальную скорость, с которой может двигаться боид.

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

Переходим к написанию кода алгоритма Boids. Для описания каждого агента определим структуру "S_Boids_Agent". Давайте разберем, что здесь происходит:


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

  • x[] - массив для хранения текущих координат агента.
  • dx[] - массив текущих скоростей агента.
  • m - масса агента.

2. Init - метод структуры "S_Boids_Agent", инициализирует поля структуры. Он принимает целочисленный аргумент "coords", используемый для изменения размера массивов "x" и "dx" с помощью функции "ArrayResize".

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

//——————————————————————————————————————————————————————————————————————————————
struct S_Boids_Agent
{
    double x  [];
    double dx [];
    double m;

    void Init (int coords)
    {
      ArrayResize (x,  coords);
      ArrayResize (dx, coords);
    }
};
//——————————————————————————————————————————————————————————————————————————————

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

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

  • ao_name - имя алгоритма оптимизации.
  • ao_desc - описание алгоритма оптимизации.
  • popSize - размер популяции.
  • params - массив параметров алгоритма.
  • cohesionWeight - вес сцепления.
  • cohesionDist - расстояние сцепления.
  • separationWeight - вес разделения.
  • separationDist - расстояние разделения.
  • alignmentWeight - вес выравнивания.
  • alignmentDist - расстояние выравнивания.
  • maxSpeed - максимальная скорость.
  • minSpeed - минимальная скорость.
  • agent - вектор агентов.

2. Методы:

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

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

  • distanceMax - максимально возможное евклидово расстояние в пространстве поиска.
  • speedMax - максимальная скорость.
//——————————————————————————————————————————————————————————————————————————————
class C_AO_Boids : public C_AO
{
  public: //--------------------------------------------------------------------
  ~C_AO_Boids () { }
  C_AO_Boids ()
  {
    ao_name = "Boids";
    ao_desc = "Boids Algorithm";
    ao_link = "https://www.mql5.com/ru/articles/14576";

    popSize          = 50;   //population size

    cohesionWeight   = 0.6;
    cohesionDist     = 0.001;

    separationWeight = 0.005;
    separationDist   = 0.03;

    alignmentWeight  = 0.1;
    alignmentDist    = 0.1;

    maxSpeed         = 0.001;
    minSpeed         = 0.0001;

    ArrayResize (params, 9);

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

    params [1].name = "cohesionWeight";   params [1].val = cohesionWeight;
    params [2].name = "cohesionDist";     params [2].val = cohesionDist;


    params [3].name = "separationWeight"; params [3].val = separationWeight;
    params [4].name = "separationDist";   params [4].val = separationDist;

    params [5].name = "alignmentWeight";  params [5].val = alignmentWeight;
    params [6].name = "alignmentDist";    params [6].val = alignmentDist;

    params [7].name = "maxSpeed";         params [7].val = maxSpeed;
    params [8].name = "minSpeed";         params [8].val = minSpeed;
  }

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

    cohesionWeight   = params [1].val;
    cohesionDist     = params [2].val;

    separationWeight = params [3].val;
    separationDist   = params [4].val;

    alignmentWeight  = params [5].val;
    alignmentDist    = params [6].val;

    maxSpeed         = params [7].val;
    minSpeed         = params [8].val;
  }

  bool Init (const double &rangeMinP  [], //minimum search range
             const double &rangeMaxP  [], //maximum search range
             const double &rangeStepP [], //step search
             const int     epochsP = 0);  //number of epochs

  void Moving   ();
  void Revision ();
  void Injection (const int popPos, const int coordPos, const double value);

  //----------------------------------------------------------------------------
  double cohesionWeight;   //cohesion weight
  double cohesionDist;     //cohesion distance

  double separationWeight; //separation weight
  double separationDist;   //separation distance

  double alignmentWeight;  //alignment weight
  double alignmentDist;    //alignment distance

  double minSpeed;         //minimum velocity
  double maxSpeed;         //maximum velocity

  S_Boids_Agent agent [];

  private: //-------------------------------------------------------------------
  double distanceMax;
  double speedMax [];

  void   CalculateMass    ();
  void   Cohesion         (S_Boids_Agent &boid, int pos);
  void   Separation       (S_Boids_Agent &boid, int pos);
  void   Alignment        (S_Boids_Agent &boid, int pos);
  void   LimitSpeed       (S_Boids_Agent &boid);
  void   KeepWithinBounds (S_Boids_Agent &boid);
  double Distance         (S_Boids_Agent &boid1, S_Boids_Agent &boid2);
};
//——————————————————————————————————————————————————————————————————————————————

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

Если стандартная инициализация прошла успешно, метод изменяет размер массива "agent" до размера "popSize". Для каждого элемента в "agent" вызывается метод "Init" с параметром "coords".

Затем метод вычисляет максимальное расстояние и максимальную скорость, которые используются в алгоритме Boids для определения движения агентов.

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

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

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

//——————————————————————————————————————————————————————————————————————————————
bool C_AO_Boids::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);

  distanceMax = 0;
  ArrayResize (speedMax, coords);

  for (int c = 0; c < coords; c++)
  {
    speedMax [c] = rangeMax [c] - rangeMin [c];
    distanceMax += pow (speedMax [c], 2);
  }

  distanceMax = sqrt (distanceMax);

  GlobalVariableSet ("#reset", 1.0);

  GlobalVariableSet ("1cohesionWeight",   params [1].val);
  GlobalVariableSet ("2cohesionDist",     params [2].val);

  GlobalVariableSet ("3separationWeight", params [3].val);
  GlobalVariableSet ("4separationDist",   params [4].val);

  GlobalVariableSet ("5alignmentWeight",  params [5].val);
  GlobalVariableSet ("6alignmentDist",    params [6].val);

  GlobalVariableSet ("7maxSpeed",         params [7].val);
  GlobalVariableSet ("8minSpeed",         params [8].val);


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

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

  1. Проверяется значение глобальной переменной "reset". Если оно равно 1.0, то флаг "revision" устанавливается в "false", значение глобальной переменной "reset" устанавливается в 0.0, и метод завершает работу.
  2. Значения параметров алгоритма извлекаются из глобальных переменных.
  3. Если флаг "revision" равен "false", то происходит инициализация координат и скоростей агентов случайными значениями в заданных диапазонах. Затем флаг "revision" устанавливается в "true", и метод завершает работу.
  4. Если флаг "revision" не равен "false", то для каждого агента выполняются следующие действия:
    • Вызываются методы "CalculateMass", "Cohesion", "Separation", "Alignment", "LimitSpeed" и "KeepWithinBounds" для обновления скоростей агента.
    • Координаты агента обновляются на основе его скоростей.
    • Координаты агента копируются в соответствующий элемент массива "a".
/——————————————————————————————————————————————————————————————————————————————
void C_AO_Boids::Moving ()
{
  double reset = GlobalVariableGet ("#reset");
  if (reset == 1.0)
  {
    revision = false;
    GlobalVariableSet ("#reset", 0.0);
  }

  cohesionWeight   = GlobalVariableGet ("1cohesionWeight");
  cohesionDist     = GlobalVariableGet ("2cohesionDist");

  separationWeight = GlobalVariableGet ("3separationWeight");
  separationDist   = GlobalVariableGet ("4separationDist");

  alignmentWeight  = GlobalVariableGet ("5alignmentWeight");
  alignmentDist    = GlobalVariableGet ("6alignmentDist");

  maxSpeed         = GlobalVariableGet ("7maxSpeed");
  minSpeed         = GlobalVariableGet ("8minSpeed");

  if (!revision)
  {
    for (int i = 0; i < popSize; i++)
    {
      for (int c = 0; c < coords; c++)
      {
        agent [i].x [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]);
        agent [i].dx [c] = (rangeMax [c] - rangeMin [c]) * u.RNDfromCI (-1.0, 1.0) * 0.001;

        a [i].c [c] = u.SeInDiSp  (agent [i].x [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }

    revision = true;
    return;
  }

  //----------------------------------------------------------------------------
  for (int i = 0; i < popSize; i++)
  {
    CalculateMass    ();
    Cohesion         (agent [i], i);
    Separation       (agent [i], i);
    Alignment        (agent [i], i);
    LimitSpeed       (agent [i]);
    KeepWithinBounds (agent [i]);

    for (int c = 0; c < coords; c++)
    {
      agent [i].x [c] += agent [i].dx [c];
      a [i].c [c] = u.SeInDiSp  (agent [i].x [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Метод "CalculateMass" класса "C_AO_Boids" используется для вычисления "массы" каждого агента в алгоритме Boids. Вот что происходит в этом методе:

  1. Инициализируются переменные "maxMass" и "minMass" для хранения максимального и минимального значений функции приспособленности среди всех агентов.
  2. Для каждого агента в популяции проверяется, превосходит ли его функция приспособленности "a[i].f" текущее максимальное значение "maxMass" и меньше ли она текущего минимального значения "minMass". Если это так, то соответствующие максимальные и минимальные значения обновляются.
  3. После того как все агенты были проверены, для каждого агента вычисляется его "масса" как масштабированное значение его функции приспособленности относительно минимального и максимального значений.

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

//——————————————————————————————————————————————————————————————————————————————
void C_AO_Boids::CalculateMass ()
{
  double maxMass = -DBL_MAX;
  double minMass =  DBL_MAX;

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

  for (int i = 0; i < popSize; i++)
  {
    agent [i].m = u.Scale (a [i].f, minMass, maxMass, 0.0, 1.0);
  }
}
//——————————————————————————————————————————————————————————————————————————————

Метод "Cohesion" класса "C_AO_Boids" используется для реализации поведения "сцепления" в алгоритме Boids. Это поведение заставляет агентов двигаться к "центру масс" своих соседей. Метод выполняет:

  1. Инициализируется массив "centerX" для хранения координат центра масс и переменная "numNeighbors" для подсчета количества соседей.
  2. Для каждого агента в популяции проверяется, не является ли он самим собой (поскольку агент не должен рассматривать себя как соседа) и находится ли он в пределах определенного расстояния (определяемого как "distanceMax * cohesionDist"). Если оба условия выполняются, координаты агента добавляются к "centerX", и "numNeighbors" увеличивается на 1.
  3. Если был найден хотя бы один сосед, координаты "centerX" делятся на количество соседей, чтобы получить координаты центра масс соседей. Затем скорость агента "boid.dx" корректируется в направлении центра масс с учетом веса сцепления "cohesionWeight".

Этот метод обеспечивает выполнение поведения "сцепления" в алгоритме Boids, что помогает агентам двигаться вместе как группа.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_Boids::Cohesion (S_Boids_Agent &boid, int pos)
{
  double centerX [];
  ArrayResize     (centerX, coords);
  ArrayInitialize (centerX, 0.0);

  int    numNeighbors = 0;

  for (int i = 0; i < popSize; i++)
  {
    if (pos != i)
    {
      if (Distance (boid, agent [i]) < distanceMax * cohesionDist)
      {
        for (int c = 0; c < coords; c++)
        {
          centerX [c] += agent [i].x [c];
        }

        numNeighbors++;
      }
    }
  }

  for (int c = 0; c < coords; c++)
  {
    centerX [c] /= numNeighbors;
    boid.dx [c] += (centerX [c] - boid.x [c]) * cohesionWeight;
  }
}
//——————————————————————————————————————————————————————————————————————————————

Метод "Separation" класса "C_AO_Boids" используется для реализации поведения "разделения" в алгоритме Boids. Это поведение заставляет агентов двигаться в противоположном направлении от соседей, которые находятся слишком близко, чтобы избежать столкновений. Вот что происходит в этом методе:

  1. Инициализируется массив "moveX" для хранения изменений в координатах агента.
  2. Для каждого агента в популяции проверяется, не является ли он самим собой (поскольку агент не должен рассматривать себя как соседа) и находится ли он в пределах определенного расстояния (определяемого как "distanceMax * separationDist"). Если оба условия выполняются, то разница между координатами текущего агента и соседа добавляется к "moveX".
  3. После того как все соседи были проверены, скорость агента "boid.dx" корректируется в направлении, противоположном "moveX", с учетом веса разделения "separationWeight".

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

//——————————————————————————————————————————————————————————————————————————————
void C_AO_Boids::Separation (S_Boids_Agent &boid, int pos)
{
  double moveX [];
  ArrayResize     (moveX, coords);
  ArrayInitialize (moveX, 0.0);

  for (int i = 0; i < popSize; i++)
  {
    if (pos != i)
    {
      if (Distance (boid, agent [i]) < distanceMax * separationDist)
      {
        for (int c = 0; c < coords; c++)
        {
          moveX [c] += boid.x [c] - agent [i].x [c];
        }
      }
    }
  }

  for (int c = 0; c < coords; c++)
  {
    boid.dx [c] += moveX [c] * separationWeight;
  }
}
//——————————————————————————————————————————————————————————————————————————————

Метод "Alignment" класса "C_AO_Boids" используется для реализации поведения "выравнивания" в алгоритме Boids. Это поведение заставляет агентов двигаться в том же направлении, что и их соседи. В этом методе:

  1. Инициализируется массив "avgDX" для хранения средней скорости соседей и переменная "numNeighbors" для подсчета количества соседей.
  2. Для каждого агента в популяции проверяется, не является ли он самим собой (поскольку агент не должен рассматривать себя как соседа) и находится ли он в пределах определенного расстояния (определяемого как "distanceMax * alignmentDist"). Если оба условия выполняются, то скорость соседа добавляется к "avgDX", и "numNeighbors" увеличивается на 1.
  3. Если был найден хотя бы один сосед, скорости "avgDX" делятся на количество соседей, чтобы получить среднюю скорость. Затем скорость агента "boid.dx" корректируется в направлении средней скорости с учетом веса выравнивания "alignmentWeight".

Этот метод обеспечивает выполнение поведения "выравнивания" в алгоритме Boids, что помогает агентам двигаться вместе в одном направлении.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_Boids::Alignment (S_Boids_Agent &boid, int pos)
{
  double avgDX [];
  ArrayResize     (avgDX, coords);
  ArrayInitialize (avgDX, 0.0);

  int numNeighbors = 0;

  for (int i = 0; i < popSize; i++)
  {
    if (pos != i)
    {
      if (Distance (boid, agent [i]) < distanceMax * alignmentDist)
      {
        for (int c = 0; c < coords; c++)
        {
          avgDX [c] += agent [i].dx [c];
        }

        numNeighbors++;
      }
    }
  }

    for (int c = 0; c < coords; c++)
    {
      avgDX   [c] /= numNeighbors;
      boid.dx [c] += (avgDX [c] - boid.dx [c]) * alignmentWeight;
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Метод "LimitSpeed" класса "C_AO_Boids" используется для ограничения скорости агентов в алгоритме Boids. Это поведение предотвращает бесконечное увеличение скорости агентов, что неестественно для реальных животных. В этом методе происходит следующее:

  1. Инициализируется переменная "speed" для хранения текущей скорости агента и переменная "d" для временного хранения данных.
  2. Вычисляется текущая скорость агента на основе его скоростей по каждой координате.
  3. Для каждой координаты агента выполняются следующие действия:
    • Вычисляется "d" как разница между максимальным и минимальным значениями диапазона, умноженная на коэффициент минимальной скорости. 
    • Скорость агента "boid.dx" корректируется в соответствии с максимально возможной скоростью "speedMax" и коэффициентом максимальной скорости "maxSpeed".
    • Если абсолютное значение скорости агента меньше "d", то скорость агента устанавливается равной "d" (с сохранением знака).

Этот метод обеспечивает выполнение поведения "ограничения скорости" в алгоритме Boids, что помогает контролировать скорость движения агентов и не позволяет боидам прекращать движение.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_Boids::LimitSpeed (S_Boids_Agent &boid)
{
  double speed = 0;

  for (int c = 0; c < coords; c++)
  {
    speed += boid.dx [c] * boid.dx [c];
  }

  speed = sqrt (speed);

  double d = 0;

  for (int c = 0; c < coords; c++)
  {
    d = (rangeMax [c] - rangeMin [c]) * minSpeed;

    boid.dx [c] = (boid.dx [c] / speed) * speedMax [c] * maxSpeed;

    if (fabs (boid.dx [c]) < d)
    {
      if (boid.dx [c] < 0.0) boid.dx [c] = -d;
      else                   boid.dx [c] =  d;
    }

  }
}
//——————————————————————————————————————————————————————————————————————————————

Метод "KeepWithinBounds" класса "C_AO_Boids" используется для ограничения движения агентов в пределах заданных границ в алгоритме Boids. Это поведение предотвращает выход агентов за пределы заданных границ.

  1. Для каждой координаты агента проверяется, не выходит ли она за пределы заданных границ (определяемых как "rangeMin" и "rangeMax").
  2. Если координата агента меньше "rangeMin", то она устанавливается равной "rangeMax", перемещая агента на противоположную сторону границы.
  3. Если координата агента больше "rangeMax", то она устанавливается равной "rangeMin", перемещая агента на противоположную сторону границы.

Этот метод обеспечивает выполнение "ограничения границ" в алгоритме Boids, что помогает агентам оставаться внутри заданных границ.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_Boids::KeepWithinBounds (S_Boids_Agent &boid)
{
  for (int c = 0; c < coords; c++)
  {
    double margin     = 0; //(rangeMax [c] - rangeMin [c])* 0.00001;
    double turnFactor = (rangeMax [c] - rangeMin [c]) * 0.0001;

    /*
    if (boid.x [c] < rangeMin [c] + margin)
    {
      boid.dx [c] += turnFactor;
    }
    if (boid.x [c] > rangeMax [c] - margin)
    {
      boid.dx [c] -= turnFactor;
    }
    */
    if (boid.x [c] < rangeMin [c]) 
    {
      //boid.x [c] = rangeMax [c];
      boid.dx [c] *= -1;
      
    }
    if (boid.x [c] > rangeMax [c])
    {
      //boid.x [c] = rangeMin [c];
      boid.dx [c] *= -1;
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Метод "Distance" класса "C_AO_Boids" используется для вычисления евклидова расстояния между двумя агентами в алгоритме Boids.

  1. Инициализируется переменная "dist" для хранения расстояния.
  2. Для каждой координаты агентов вычисляется квадрат разности их координат, который затем добавляется к "dist".
  3. В конце метод возвращает квадратный корень из "dist", что соответствует евклидову расстоянию между агентами.

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

//——————————————————————————————————————————————————————————————————————————————
double C_AO_Boids::Distance (S_Boids_Agent &boid1, S_Boids_Agent &boid2)
{
  double dist = 0;

  for (int c = 0; c < coords; c++)
  {
    dist += pow (boid1.x [c] - boid1.x [c], 2);
  }

  return sqrt (dist);
}
//——————————————————————————————————————————————————————————————————————————————

Метод "Revision" класса "C_AO_Boids" используется для обновления лучшего решения в алгоритме Boids.

  1. Инициализируется переменная "ind" значением -1. Эта переменная будет использоваться для хранения индекса агента с лучшим решением.
  2. Для каждого агента в популяции проверяется, превосходит ли его функцию приспособленности "a[i].f" текущее лучшее решение "fB". Если это так, то "ind" устанавливается равным индексу этого агента.
  3. Если был найден агент с лучшим решением (то есть "ind" не равно -1), то лучшее решение "fB" и лучшие координаты "cB" обновляются значениями этого агента.

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

//——————————————————————————————————————————————————————————————————————————————
void C_AO_Boids::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);
  }
}
//——————————————————————————————————————————————————————————————————————————————


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

Хотел бы подробнее остановиться на результатах алгоритма Boids на различных наборах функций. Общий балл Boids на всех тестовых функциях составил 2.22889, что соответствует 24.77% от максимально возможного результата. Этот результат указывает на низкую эффективность алгоритма. Исходя из этого, можно сделать вывод, что алгоритм Boids обладает небольшим потенциалом для решения задач оптимизации на различных функциях.

Boids|50.0|0.05|0.002|0.01|0.01|0.0001|0.01|0.001|0.0001|
=============================
5 Hilly's; Func runs: 100000; result: 0.43339505349362384
25 Hilly's; Func runs: 100000; result: 0.3058074706767012
500 Hilly's; Func runs: 100000; result: 0.2542539219446322
=============================
5 Forest's; Func runs: 100000; result: 0.35717696198531945
25 Forest's; Func runs: 100000; result: 0.20160005990319796
500 Forest's; Func runs: 100000; result: 0.15708435238635948
=============================
5 Megacity's; Func runs: 100000; result: 0.2784615384615384
25 Megacity's; Func runs: 100000; result: 0.14276923076923081
500 Megacity's; Func runs: 100000; result: 0.09833846153846236
=============================
All score: 2.22889 (24.77%)

Алгоритм Boids занял 28-е место в рейтинговой таблице, рядом со своим "собратом" по системам роевого интеллекта, алгоритмом PSO.

№ 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 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
29 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
30 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
31 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
32 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
33 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
34 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
35 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


Выводы

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

tab

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

chart

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

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

Плюсы и минусы алгоритма стайного поведения (Boids):

Плюсы:

  1. Реалистичное моделирование стайного поведения.

Минусы:

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

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

Прикрепленные файлы |
Загрузить ZIP
Boids.ZIP (27.73 KB)
Предупреждение: все права на данные материалы принадлежат MetaQuotes Ltd. Полная или частичная перепечатка запрещена.

Другие статьи автора

Перейти к обсуждению на форуме трейдеров
Машинное обучение и Data Science (Часть 16): Свежий взгляд на деревья решений Машинное обучение и Data Science (Часть 16): Свежий взгляд на деревья решений
В последней части нашей серии о машинном обучении и работе с большими данными мы снова возвращаемся к деревьям решений. Эта статья предназначена для трейдеров, которые хотят понять роль деревьев решений в анализе рыночных тенденций. В ней собрана вся основная информация о структуре, предназначении и использовании таких деревьев. Мы рассмотри корни и ветви алгоритмических деревьев и узнаем, в чем же заключается их потенциал применительно к принятию торговых решений. Давайте вместе по-новому взглянем на деревья решений и посмотри, как они могут помочь преодолевать сложности на финансовых рынках.
Парадигмы программирования (Часть 1): Процедурный подход к разработке советника на основе ценовой динамики Парадигмы программирования (Часть 1): Процедурный подход к разработке советника на основе ценовой динамики
Узнайте о парадигмах программирования и их применении в коде MQL5. В этой статье исследуются особенности процедурного программирования, а также предлагаются практические примеры. Вы узнаете, как разработать советник на основе ценовой динамики (Price Action), используя индикатор EMA и свечные данные. Кроме того, статья знакомит с парадигмой функционального программирования.
Модифицированный советник Grid-Hedge в MQL5 (Часть I): Создание простого хеджирующего советника Модифицированный советник Grid-Hedge в MQL5 (Часть I): Создание простого хеджирующего советника
Мы будем создавать простой хеджирующий советник в качестве основы для нашего более продвинутого советника Grid-Hedge, который будет представлять собой смесь классической сетки и классических стратегий хеджирования. К концу этой статьи вы узнаете, как создать простую стратегию хеджирования, а также что говорят люди о прибыльности этой стратегии.
Разрабатываем мультивалютный советник (Часть 7): Подбор группы с учётом форвард-периода Разрабатываем мультивалютный советник (Часть 7): Подбор группы с учётом форвард-периода
Подбор группы экземпляров торговых стратегий с целью улучшения результатов при их совместной работы мы прежде оценивали только на том же временном периоде, на котором проводилась оптимизация отдельных экземпляров. Давайте посмотрим, что получится на форвард-периоде.