Детерминированный осциллирующий поиск — Deterministic Oscillatory Search (DOS)

Содержание

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

Введение

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

В данной статье будет представлен детерминированный осциллирующий поиск (Deterministic Oscillatory Search, DOS) — новый метаэвристический алгоритм, объединяющий преимущества традиционных градиентных методов с эффективностью роевых алгоритмов, но при этом, полностью избегающий использования случайных чисел.

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

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

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

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

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

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

Теперь начинается самое интересное. Когда исследователь обнаруживает, что перестал подниматься и начал спускаться (фитнес ухудшился), он не просто останавливается или поворачивает назад. Вместо этого, он делает "отскок" — разворачивается и продолжает двигаться в противоположном направлении, но с меньшей скоростью (в половину от предыдущей). Это похоже на теннисный мяч, который отскакивает от стены, но с меньшей энергией.

Этот процесс отскока создает колебательное (осциллирующее) движение — отсюда и название алгоритма. С каждым отскоком исследователь всё точнее локализует точку экстремума. Но что, если исследователь попал в ловушку — небольшой холм, вокруг которого всё ниже, и данный экстремум не является самой высокой точкой в регионе? Здесь DOS применяет другой прием. Если исследователь пытался двигаться в разных направлениях, но везде встречает спуск, он переключается на другой режим — "роение". В этом режиме он начинает двигаться в направлении лучшей точки, найденной всеми исследователями до сих пор.

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

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

• начальное детерминированное положение частицы,
• осциллирующее (зигзагообразное) движение при исследовании пространства,
• адаптивное движение в направлении глобального оптимума.

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

• положительным (+1) - текущее движение улучшает фитнес,
• отрицательным (-1) - текущее движение ухудшает фитнес,
• неизвестным (0) - состояние при инициализации или после смены стратегии.

Рисунок 1. Иллюстрация работы алгоритма

Иллюстрация наглядно показывает, как DOS объединяет характеристики классических градиентных методов (локальный поиск через осцилляции) с возможностями роевых алгоритмов, сохраняя при этом полностью детерминированное поведение. Выяснив принципы работы алгоритма, перейдем к написанию псевдокода алгоритма.

Шаг 1: Начальная подготовка

• Создать массивы для хранения позиций, скоростей, предыдущих значений фитнеса и наклонов для каждой частицы
• Инициализировать лучшее найденное решение с минимально возможным значением фитнеса

Шаг 2: Детерминистическая инициализация частиц

• Для каждой частицы:
  • расположить в пространстве поиска по детерминистической формуле, обеспечивающей равномерное покрытие
  • установить начальную скорость в ноль
  • установить начальный наклон как "неизвестный" (0)
  • установить предыдущее значение фитнеса в минимально возможное значение

Шаг 3: Основной цикл оптимизации

• Повторять до достижения максимального числа итераций: Часть 1: Движение частиц
  • Для каждой частицы:
    • сохранить текущее значение фитнеса как предыдущее
    • обновить позицию, прибавив текущую скорость
    • если новая позиция выходит за границы поиска, ограничить её разрешёнными пределами
  Часть 2: Оценка и корректировка движения
  • Для каждой частицы:
    • вычислить новое значение фитнеса
    • если фитнес лучше, чем лучшее найденное решение, обновить лучшее решение
    • если наклон "неизвестный" (0):
      • если новый фитнес лучше предыдущего, установить наклон "положительный" (1)
      • если новый фитнес хуже предыдущего, установить наклон "отрицательный" (-1)
      • если фитнес не изменился, оставить наклон "неизвестным"
    • если наклон "положительный" (1):
      • если новый фитнес хуже предыдущего:
        • изменить направление движения на противоположное
        • уменьшить скорость в два раза
        • установить наклон "отрицательный" (-1)
    • если наклон "отрицательный" (-1):
      • если новый фитнес хуже предыдущего:
        • применить механизм роения: добавить к текущей скорости вектор, направленный к лучшему решению, умноженный на фактор движения
        • установить наклон "неизвестный" (0)
    • проверить, не является ли скорость нулевой или близкой к нулю:
      • если скорость почти нулевая:
        • установить скорость в направлении лучшего найденного решения, умноженную на фактор движения
        • установить наклон "неизвестный" (0)

Шаг 4: Завершение

• Вернуть лучшее найденное решение и его значение фитнеса

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

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

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

// Структура для хранения скорости частицы
struct S_DOS_Velocity
{
    int    slope; // Наклон частицы (-1: отрицательный, 0: неизвестный, 1: положительный)
    double v [];  // Компоненты скорости по каждому измерению


    void Init (int dims)
    {
      slope = 0;
      ArrayResize     (v, dims);
      ArrayInitialize (v, 0.0); // Быстрая инициализация нулями всего массива
    }

    // Проверка на нулевую скорость
    bool IsZero (double epsilon = 1e-10)
    {
      for (int i = 0; i < ArraySize (v); i++) if (MathAbs (v [i]) > epsilon) return false;
      return true;
    }
};

//——————————————————————————————————————————————————————————————————————————————

Класс "C_AO_DOS" будет представлять собой реализацию алгоритма. Он будет наследовать функциональность от базового класса "C_AO", добавляя специфическую логику для метода DOS. Основные характеристики класса: в конструкторе инициализируются параметры по умолчанию, включая размер популяции и фактор движения к лучшему решению, создается массив параметров. Метод "SetParams ()" обеспечивает возможность задания и проверки параметров, таких как размер популяции "popSize" и коэффициент движения "movementFactor", с учетом ограничений. Метод "Init ()" отвечает за подготовку начальных условий: диапазонов поиска, шагов изменения и количества итераций.

Логика движения частиц, методы:

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

Внутри класса определена структура "S_DOS_Velocity velocities", которая хранит компоненты скорости каждой частицы по всем измерениям и содержит методы инициализации и проверки нулевой скорости.

Внутренние методы:

• InitializeParticles () и ProcessParticleMovement () - вспомогательные функции для инициализации и обновления положения частиц, обеспечивают алгоритмическую логику.

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

//——————————————————————————————————————————————————————————————————————————————
class C_AO_DOS : public C_AO
{
  public: //--------------------------------------------------------------------
  ~C_AO_DOS () { }
  C_AO_DOS ()
  {
    ao_name = "DOS";
    ao_desc = "Deterministic Oscillatory Search";
    ao_link = "https://www.mql5.com/ru/articles/18154";

    // Установка параметров по умолчанию
    popSize        = 30;   // размер популяции
    movementFactor = 0.95; // фактор движения к лучшему решению

    // Создание и инициализация массива параметров
    ArrayResize (params, 2);
    params [0].name = "Population Size"; params [0].val = popSize;
    params [1].name = "Movement Factor"; params [1].val = movementFactor;
  }

  void SetParams ()
  {
    // Установка значений параметров с проверкой
    popSize        = (int)MathMax (5, params [0].val);             // Минимально 5 частиц для эффективности
    movementFactor = MathMax (0.1, MathMin (1.0, params [1].val)); // Ограничение от 0.1 до 1.0
  }

  bool Init (const double &rangeMinP  [],  // минимальные значения
             const double &rangeMaxP  [],  // максимальные значения
             const double &rangeStepP [],  // шаг изменения
             const int     epochsP = 0);

  void Moving   ();
  void Revision ();

  //----------------------------------------------------------------------------
  double movementFactor;          // фактор движения к лучшему решению

  S_DOS_Velocity velocities [];  // Массив структур скоростей частиц

  private: //-------------------------------------------------------------------
  void InitializeParticles     ();
  void ProcessParticleMovement (int particleIndex);
};
//——————————————————————————————————————————————————————————————————————————————

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

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

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

//——————————————————————————————————————————————————————————————————————————————
bool C_AO_DOS::Init (const double &rangeMinP  [],  // минимальные значения
                     const double &rangeMaxP  [],  // максимальные значения
                     const double &rangeStepP [],  // шаг изменения
                     const int     epochsP = 0)    // количество эпох
{
  // Стандартная инициализация C_AO
  if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false;

  //----------------------------------------------------------------------------
  // Выделение памяти под массивы
  ArrayResize (velocities, popSize);

  // Инициализация скоростей для каждого измерения
  for (int i = 0; i < popSize; i++) velocities [i].Init (coords);

  // Инициализация позиций частиц детерминистическим способом
  InitializeParticles ();

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

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

Для каждой координаты (измерения) частицы вычисляется новое значение, путем добавления соответствующей компоненты скорости к текущей координате. Новые координаты ограничиваются заданными диапазонами "rangeMin [d]" и "rangeMax [d]" согласно шага, чтобы частицы не выходили за пределы допустимой области поиска. 

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

//+----------------------------------------------------------------------------+
//| Основной метод движения частиц                                             |
//+----------------------------------------------------------------------------+
void C_AO_DOS::Moving ()
{
  // Обработка всех частиц
  for (int i = 0; i < popSize; i++)
  {
    // Сохранение значения фитнеса
    a [i].fP = a [i].f;

    // Вычисление новых координат на основе скорости
    for (int d = 0; d < coords; d++)
    {
      // Обновление позиции
      a [i].c [d] += velocities [i].v [d];

      // Округление до ближайшего допустимого шага
      a [i].c [d] = u.SeInDiSp (a [i].c [d], rangeMin [d], rangeMax [d], rangeStep [d]);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

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

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

//+----------------------------------------------------------------------------+
//| Метод обновления фитнес-функций                                            |
//+----------------------------------------------------------------------------+
void C_AO_DOS::Revision ()
{
  // Обработка каждой частицы
  for (int i = 0; i < popSize; i++)
  {
    // Обновление лучшего решения, если текущее решение лучше
    if (a [i].f > fB)
    {
      fB = a [i].f;
      ArrayCopy (cB, a [i].c, 0, 0, WHOLE_ARRAY);
    }

    // Обработка движения частицы на основе изменения фитнеса
    ProcessParticleMovement (i);
  }
}
//——————————————————————————————————————————————————————————————————————————————

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

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

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

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

//+----------------------------------------------------------------------------+
//| Обработка движения частицы после обновления фитнеса                        |
//+----------------------------------------------------------------------------+
void C_AO_DOS::ProcessParticleMovement (int particleIndex)
{
  // Локальные переменные для оптимизации доступа
  double currentFitness  = a [particleIndex].f;
  double previousFitness = a [particleIndex].fP;
  int    currentSlope    = velocities [particleIndex].slope;

  // Сравнение фитнесов для определения направления движения
  double fitnessDiff = currentFitness - previousFitness;

  // Обработка наклона в соответствии с текущим состоянием
  if (currentSlope == 0) // Неизвестный наклон
  {
    // Определяем наклон на основе изменения фитнеса
    velocities [particleIndex].slope = (fitnessDiff > 0) ? 1 : (fitnessDiff < 0) ? -1 : 0;
  }
  else
    if (currentSlope == 1 && fitnessDiff < 0) // Положительный наклон и ухудшение фитнеса
    {
      // Меняем направление и уменьшаем скорость
      for (int d = 0; d < coords; d++) velocities [particleIndex].v [d] *= -0.5; // Оптимизированная форма деления на 2

      velocities [particleIndex].slope  = -1; // Меняем наклон на отрицательный
    }
    else
      if (currentSlope == -1 && fitnessDiff < 0) // Отрицательный наклон и ухудшение фитнеса
      {
        // Применяем механизм роения - движение к глобальному оптимуму
        for (int d = 0; d < coords; d++) velocities [particleIndex].v [d] += (cB [d] - a [particleIndex].c [d]) * movementFactor;

        velocities [particleIndex].slope = 0; // Сбрасываем наклон как неизвестный
      }

  // Проверка на нулевую скорость с использованием метода структуры
  if (velocities [particleIndex].IsZero ())
  {
    // Инициализируем скорость движением к глобальному оптимуму
    for (int d = 0; d < coords; d++) velocities [particleIndex].v [d] = (cB [d] - a [particleIndex].c [d]) * movementFactor;

    // Сбрасываем наклон
    velocities [particleIndex].slope  = 0;
  }
}
//——————————————————————————————————————————————————————————————————————————————

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

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

DOS|Deterministic Oscillatory Search Algorithm|50.0|0.95|
=============================
5 Hilly's; Func runs: 10000; result: 0.3422040822277234
25 Hilly's; Func runs: 10000; result: 0.3421751631202356
500 Hilly's; Func runs: 10000; result: 0.3421605659711745
=============================
5 Forest's; Func runs: 10000; result: 0.5708601371368296
25 Forest's; Func runs: 10000; result: 0.34628707444514434
500 Forest's; Func runs: 10000; result: 0.32879379664917996
=============================
5 Megacity's; Func runs: 10000; result: 0.19999999999999998
25 Megacity's; Func runs: 10000; result: 0.20923076923076928
500 Megacity's; Func runs: 10000; result: 0.23076923076922945
=============================
All score: 2.91248 (32.36%)

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

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

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

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

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

№	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	ANS	across neighbourhood search	0,94948	0,84776	0,43857	2,23581	1,00000	0,92334	0,39988	2,32323	0,70923	0,63477	0,23091	1,57491	6,134	68,15
2	CLA	code lock algorithm (joo)	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	AMOm	animal migration ptimization M	0,90358	0,84317	0,46284	2,20959	0,99001	0,92436	0,46598	2,38034	0,56769	0,59132	0,23773	1,39675	5,987	66,52
4	(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
5	CTA	comet tail algorithm (joo)	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
6	TETA	time evolution travel algorithm (joo)	0,91362	0,82349	0,31990	2,05701	0,97096	0,89532	0,29324	2,15952	0,73462	0,68569	0,16021	1,58052	5,797	64,41
7	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
8	BOAm	billiards optimization algorithm M	0,95757	0,82599	0,25235	2,03590	1,00000	0,90036	0,30502	2,20538	0,73538	0,52523	0,09563	1,35625	5,598	62,19
9	AAm	archery algorithm M	0,91744	0,70876	0,42160	2,04780	0,92527	0,75802	0,35328	2,03657	0,67385	0,55200	0,23738	1,46323	5,548	61,64
10	ESG	evolution of social groups (joo)	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
11	SIA	simulated isotropic annealing (joo)	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
12	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
13	DA	dialectical algorithm	0,86183	0,70033	0,33724	1,89940	0,98163	0,72772	0,28718	1,99653	0,70308	0,45292	0,16367	1,31967	5,216	57,95
14	BHAm	black hole algorithm M	0,75236	0,76675	0,34583	1,86493	0,93593	0,80152	0,27177	2,00923	0,65077	0,51646	0,15472	1,32195	5,196	57,73
15	ASO	anarchy society optimization	0,84872	0,74646	0,31465	1,90983	0,96148	0,79150	0,23803	1,99101	0,57077	0,54062	0,16614	1,27752	5,178	57,54
16	RFO	royal flush optimization (joo)	0,83361	0,73742	0,34629	1,91733	0,89424	0,73824	0,24098	1,87346	0,63154	0,50292	0,16421	1,29867	5,089	56,55
17	AOSm	atomic orbital search M	0,80232	0,70449	0,31021	1,81702	0,85660	0,69451	0,21996	1,77107	0,74615	0,52862	0,14358	1,41835	5,006	55,63
18	TSEA	turtle shell evolution algorithm (joo)	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
19	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
20	SRA	successful restaurateur algorithm (joo)	0,96883	0,63455	0,29217	1,89555	0,94637	0,55506	0,19124	1,69267	0,74923	0,44031	0,12526	1,31480	4,903	54,48
21	CRO	chemical reaction optimisation	0,94629	0,66112	0,29853	1,90593	0,87906	0,58422	0,21146	1,67473	0,75846	0,42646	0,12686	1,31178	4,892	54,36
22	BIO	blood inheritance optimization (joo)	0,81568	0,65336	0,30877	1,77781	0,89937	0,65319	0,21760	1,77016	0,67846	0,47631	0,13902	1,29378	4,842	53,80
23	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
24	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
25	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
26	BCOm	bacterial chemotaxis optimization M	0,75953	0,62268	0,31483	1,69704	0,89378	0,61339	0,22542	1,73259	0,65385	0,42092	0,14435	1,21912	4,649	51,65
27	ABO	african buffalo optimization	0,83337	0,62247	0,29964	1,75548	0,92170	0,58618	0,19723	1,70511	0,61000	0,43154	0,13225	1,17378	4,634	51,49
28	(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
29	FBA	fractal-based Algorithm	0,79000	0,65134	0,28965	1,73099	0,87158	0,56823	0,18877	1,62858	0,61077	0,46062	0,12398	1,19537	4,555	50,61
30	TSm	tabu search M	0,87795	0,61431	0,29104	1,78330	0,92885	0,51844	0,19054	1,63783	0,61077	0,38215	0,12157	1,11449	4,536	50,40
31	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
32	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
33	AEFA	artificial electric field algorithm	0,87700	0,61753	0,25235	1,74688	0,92729	0,72698	0,18064	1,83490	0,66615	0,11631	0,09508	0,87754	4,459	49,55
34	AEO	artificial ecosystem-based optimization algorithm	0,91380	0,46713	0,26470	1,64563	0,90223	0,43705	0,21400	1,55327	0,66154	0,30800	0,28563	1,25517	4,454	49,49
35	CAm	camel algorithm M	0,78684	0,56042	0,35133	1,69859	0,82772	0,56041	0,24336	1,63149	0,64846	0,33092	0,13418	1,11356	4,444	49,37
36	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
37	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
38	SOA	simple optimization algorithm	0,91520	0,46976	0,27089	1,65585	0,89675	0,37401	0,16984	1,44060	0,69538	0,28031	0,10852	1,08422	4,181	46,45
39	ABHA	artificial bee hive algorithm	0,84131	0,54227	0,26304	1,64663	0,87858	0,47779	0,17181	1,52818	0,50923	0,33877	0,10397	0,95197	4,127	45,85
40	ACMO	atmospheric cloud model optimization	0,90321	0,48546	0,30403	1,69270	0,80268	0,37857	0,19178	1,37303	0,62308	0,24400	0,10795	0,97503	4,041	44,90
41	ADAMm	adaptive moment estimation M	0,88635	0,44766	0,26613	1,60014	0,84497	0,38493	0,16889	1,39880	0,66154	0,27046	0,10594	1,03794	4,037	44,85
42	CGO	chaos game optimization	0,57256	0,37158	0,32018	1,26432	0,61176	0,61931	0,62161	1,85267	0,37538	0,21923	0,19028	0,78490	3,902	43,35
43	ATAm	artificial tribe algorithm M	0,71771	0,55304	0,25235	1,52310	0,82491	0,55904	0,20473	1,58867	0,44000	0,18615	0,09411	0,72026	3,832	42,58
44	CROm	coral reefs optimization M	0,78512	0,46032	0,25958	1,50502	0,86688	0,35297	0,16267	1,38252	0,63231	0,26738	0,10734	1,00703	3,895	43,27
45	CFO	central force optimization	0,60961	0,54958	0,27831	1,43750	0,63418	0,46833	0,22541	1,32792	0,57231	0,23477	0,09586	0,90294	3,668	40,76
	DOS	deterministic oscillatory search	0,34220	0,34218	0,34216	1,02654	0,57086	0,34629	0,32879	1,24594	0,20000	0,20923	0,23077	0,64000	2,912	32,36
	RW	neuroboids optimization algorithm 2(joo)	0,48754	0,32159	0,25781	1,06694	0,37554	0,21944	0,15877	0,75375	0,27969	0,14917	0,09847	0,52734	2,348	26,09

Выводы

Алгоритм имеет минимальное количество параметров для настройки (размер популяции и фактор движения), что упрощает его применение и снижает риск неправильной конфигурации.

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

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

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

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

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

Плюсы:

1. Быстрый.
2. Очень простая реализация.

Минусы:

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

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

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

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

#	Имя	Тип	Описание
1	#C_AO.mqh	Включаемый файл	Родительский класс популяционных алгоритмов оптимизации
2	#C_AO_enum.mqh	Включаемый файл	Перечисление популяционных алгоритмов оптимизации
3	TestFunctions.mqh	Включаемый файл	Библиотека тестовых функций
4	TestStandFunctions.mqh	Включаемый файл	Библиотека функций тестового стенда
5	Utilities.mqh	Включаемый файл	Библиотека вспомогательных функций
6	CalculationTestResults.mqh	Включаемый файл	Скрипт для расчета результатов в сравнительную таблицу
7	Testing AOs.mq5	Скрипт	Единый испытательный стенд для всех популяционных алгоритмов оптимизации
8	Simple use of population optimization algorithms.mq5	Скрипт	Простой пример использования популяционных алгоритмов оптимизации без визуализации
9	Test_AO_DOS.mq5	Скрипт	Испытательный стенд для DOS