Популяционные алгоритмы оптимизации: Алгоритм оптимизации спиральной динамики (Spiral Dynamics Optimization, SDO)

Содержание:

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

1. Введение

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

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

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

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

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

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

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

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

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

• Архимедова спираль
• Циклоидная спираль
• Эпитрохоидная спираль
• Гипотрохоидная спираль
• Логарифмическая спираль
• Роза спиральная
• Фермацова спираль

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

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

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

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

Алгоритм SDO для поиска в многомерных пространствах, описанный авторами, имеет ограничения и недостатки:

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

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

В многомерном пространстве спирали могут быть построены для каждой пары координат, но для одной оставшейся координаты спираль не может быть определена. Например, в случае 13-мерного пространства можно построить спирали для 6 пар координат, но одна координата будет двигаться без спиральной компоненты.

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

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

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

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

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

x(t) = A*e^(-γt)*cos(ωt + φ)

где:

• A - амплитуда колебаний
• γ - коэффициент затухания
• ω - собственная частота осциллятора
• φ - начальная фаза колебаний

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

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

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

Рисунок 1. Влияние амплитуды на характер колебаний.

Рисунок 2. Влияние частоты на характер колебаний.

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

Рисунок 3. Гипотетическая спираль, с параметрами алгоритма по умолчанию, где 6 - значение амплитуды, 0.3 - коэффициент затухания, и 4 - частота.

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

Рисунок 4. Значение точки по координате Y находится ближе к известному значению и амплитуда колебаний у неё меньше, чем по оси X.

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

Переходим к описанию кода. Для начала определимся со структурой алгоритма и составим псевдокод:

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

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

Для описания агента (частица, точка) хорошо подойдет структура S_Particle, которая содержит следующие переменные:

• c  [] - массив координат частицы
  
• cD[] - массив скоростей частицы
• t - шаг итерации, играет роль "времени" в формуле
  
• f - значение функции приспособленности частицы
  

Также в структуре определена функция Init, которая используется для инициализации переменных структуры. Параметр coords задает количество координат частицы.

//——————————————————————————————————————————————————————————————————————————————
struct S_Particle
{
  void Init (int coords)
  {
    ArrayResize (c,    coords);
    ArrayResize (cD,   coords);
    t = 0;
    f = -DBL_MAX;
  }

  double c  []; //coordinates
  double cD []; //coordinates
  int    t;     //iteration (time)
  double f;     //fitness
};
//——————————————————————————————————————————————————————————————————————————————

Определим класс алгоритма SDOm, C_AO_SDOm. Класс содержит следующие переменные и методы:

• cB [] - массив лучших координат
• fB - значение функции приспособленности лучших координат
• p [] - массив частиц, тип данных - S_Particle
• rangeMax [] - массив максимальных значений диапазона поиска
  
• rangeMin [] - массив минимальных значений диапазона поиска
  
• rangeStep [] - массив шагов поиска
  
• Init - метод для инициализации параметров класса, принимает следующие параметры: "coordinatesNumberP" - количество координат, "populationSize" - размер популяции, "dampingFactorP" - коэффициент затухания, "frequencyP" - частота, "precisionP" - точность.
• Moving - метод для перемещения частиц в пространстве поиска
• Revision - метод для ревизии и обновления лучших координат
• coords - количество координат
• popSiz - размер популяции
• A, e, γ, ω, φ - компоненты формулы затухающего гармонического колебания
  
• precision, revision - приватные переменные, которые используются внутри класса
• SeInDiSp - метод вычисляет новое значение координаты в заданном диапазоне с заданным шагом
  
• RNDfromCI - метод генерирует случайное число в заданном диапазоне

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

Первые три переменные класса — это массив cB, который хранит лучшие координаты, переменная fB, которая хранит значение функции приспособленности лучших координат, и массив p, который хранит кандидатов (частицы) популяции.

Следующие три переменные класса  — это массивы rangeMax, rangeMin и rangeStep, которые хранят максимальные и минимальные значения диапазона поиска и шаги поиска соответственно.

Далее, класс содержит три публичных метода: Init, Moving и Revision. Метод Init используется для инициализации параметров класса и создания начальной популяции частиц. Метод Moving используется для перемещения частиц по пространству поиска. Метод Revision используется для ревизии лучших координат и обновления их значений.

Класс также содержит несколько приватных переменных, которые используются внутри класса. Это переменные coords и popSize, которые хранят количество координат и размер популяции соответственно, переменная A, которая используется в методе Moving, переменная precision, которая хранит значение точности, и переменная revision, которая отвечает за необходимость ревизии лучших координат.

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

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

//——————————————————————————————————————————————————————————————————————————————
class C_AO_SDOm
{
  //----------------------------------------------------------------------------
  public: double     cB []; //best coordinates
  public: double     fB;    //FF of the best coordinates
  public: S_Particle p  []; //particles

  public: double rangeMax  []; //maximum search range
  public: double rangeMin  []; //manimum search range
  public: double rangeStep []; //step search

  public: void Init (const int    coordinatesNumberP,   //coordinates number
                     const int    populationSizeP,      //population size
                     const double dampingFactorP,       //damping factor
                     const double frequencyP,           //frequency
                     const double precisionP);          //precision

  public: void Moving   ();
  public: void Revision ();

  //----------------------------------------------------------------------------
  private: int    coords;   //coordinates number
  private: int    popSize;  //population size

  private: double A;
  private: double e;
  private: double γ;
  private: double ω;
  private: double φ;
  private: double precision;

  private: bool   revision;

  private: double SeInDiSp  (double In, double InMin, double InMax, double Step);
  private: double RNDfromCI (double min, double max);
};
//——————————————————————————————————————————————————————————————————————————————

Метод Init класса C_AO_SDOm, используется для инициализации параметров класса и создания начальной популяции частиц.

Сначала используется "MathSrand" для сброса генератора случайных чисел и функцию "GetMicrosecondCount" для инициализации генератора.

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

//——————————————————————————————————————————————————————————————————————————————
void C_AO_SDOm::Init (const int    coordinatesNumberP,   //coordinates number
                      const int    populationSizeP,      //population size
                      const double dampingFactorP,       //damping factor
                      const double frequencyP,           //frequency
                      const double precisionP)           //precision
{
  MathSrand ((int)GetMicrosecondCount ()); // reset of the generator
  fB       = -DBL_MAX;
  revision = false;

  coords  = coordinatesNumberP;
  popSize = populationSizeP;

  e = M_E;
  γ = dampingFactorP;
  ω = frequencyP;
  φ = 0.0;
  precision = precisionP;

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

  ArrayResize (p, popSize);

  for (int i = 0; i < popSize; i++)
  {
    p [i].Init (coords);
  }
}
//——————————————————————————————————————————————————————————————————————————————

Для перемещения частиц в пространстве поиска будем использовать метод "Moving".

Первый блок кода (if (!revision)) выполняется только на первой итерации и предназначен для случайного размещения частиц в пространстве поиска. Затем метод устанавливает значение "revision" в "true", чтобы в следующий раз использовать обычный блок кода.

Следующая часть кода метода отвечает за перемещение частиц популяции. Если значение приспособленности текущей частицы равно значению приспособленности лучших координат (p[i].f == fB), то координаты частицы обновляются так же, как и в первом блоке кода. Это означает, что частица выбрасывается из своего положения в случайном направлении, чтобы предотвратить схождение всех частиц в одну единственную точку.

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

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

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

    revision = true;
    return;
  }

  //----------------------------------------------------------------------------
  int t = 0.0;

  for (int i = 0; i < popSize; i++)
  {
    if  (p [i].f == fB)
    {
      for (int c = 0; c < coords; c++)
      {
        p [i].c [c] = RNDfromCI (rangeMin [c], rangeMax [c]);
        p [i].c [c] = SeInDiSp (p [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      }

      continue;
    }

    p [i].t++;
    t = p [i].t;

    for (int c = 0; c < coords; c++)
    {
      A = p [i].cD [c];
      φ = RNDfromCI (0.0, 2.0);

      p [i].c [c] = p [i].c [c] + A * pow (e, -γ * t / precision) * cos (ω * t / (precision) + φ);// + RNDfromCI (-0.01, 0.01) * (rangeMax [c] - rangeMin [c]);
      p [i].c [c] = SeInDiSp (p [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

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

//——————————————————————————————————————————————————————————————————————————————
void C_AO_SDOm::Revision ()
{
  //----------------------------------------------------------------------------
  bool flag = false;
  for (int i = 0; i < popSize; i++)
  {
    if (p [i].f > fB)
    {
      flag = true;
      fB = p [i].f;
      ArrayCopy (cB, p [i].c, 0, 0, WHOLE_ARRAY);
    }
  }

  if (flag)
  {
    for (int i = 0; i < popSize; i++)
    {
      p [i].t = 0;

      for (int c = 0; c < coords; c++)
      {
        p [i].cD [c] = (cB [c] - p [i].c [c]);

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

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

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

C_AO_SDOm:100;0.3;4.0;10000.0
=============================
5 Rastrigin's; Func runs 10000 result: 76.22736727464056
Score: 0.94450
25 Rastrigin's; Func runs 10000 result: 64.5695106264092
Score: 0.80005
500 Rastrigin's; Func runs 10000 result: 47.607500083305425
Score: 0.58988
=============================
5 Forest's; Func runs 10000 result: 1.3265635010116805
Score: 0.75037
25 Forest's; Func runs 10000 result: 0.5448141810532924
Score: 0.30817
500 Forest's; Func runs 10000 result: 0.12178250603909949
Score: 0.06889
=============================
5 Megacity's; Func runs 10000 result: 5.359999999999999
Score: 0.44667
25 Megacity's; Func runs 10000 result: 1.552
Score: 0.12933
500 Megacity's; Func runs 10000 result: 0.38160000000000005
Score: 0.03180
=============================
All score: 4.06967

Визуализация алгоритма SDOm выявила некоторые отличительные особенности: график сходимости на всех тестовых функциях нестабилен, меняется характер кривой сходимости на протяжении всех итераций и это не повышает чувство уверенности в результатах. На визуализации работы с функцией Megacity я специально показал несколько повторных тестов (обычно на видео только один, что бы не получился GIF слишком объёмным), чтобы показать нестабильность результатов от теста к тесту, разброс в результатах очень велик.

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

  SDOm на тестовой функции Rastrigin.

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

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

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

Демонстрация бесполезного, но красивого эффекта "фейерверка".

Алгоритм SDOm показал достаточно хорошие результаты в целом и оказался на 8 месте из 23 участвующих в обзоре рейтинговой таблицы. SDOm демонстрирует заметно лучшие результаты на гладкой функции Rastrigin. Склонность к застреванию не способствует отличным результатам на сложных функциях Forest и Megacity.

№	AO	Description	Rastrigin			Rastrigin final	Forest			Forest final	Megacity (discrete)			Megacity final	Final result
			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	SDSm	stochastic diffusion search M	0,99809	1,00000	0,69149	2,68958	1,00000	1,00000	1,00000	3,00000	1,00000	1,00000	1,00000	3,00000	100,000
2	SDS	stochastic Diffusion Search	0,99737	0,97322	0,58904	2,55963	0,96778	0,93572	0,79649	2,69999	0,78696	0,93815	0,71804	2,44315	88,208
3	SSG	saplings sowing and growing	1,00000	0,92761	0,51630	2,44391	0,72654	0,65201	0,83760	2,21615	0,54782	0,61841	0,99522	2,16146	77,678
4	HS	harmony search	0,99676	0,88385	0,44686	2,32747	0,99882	0,68242	0,37529	2,05653	0,71739	0,71842	0,41338	1,84919	70,647
5	IWO	invasive weed optimization	0,95828	0,62227	0,27647	1,85703	0,70690	0,31972	0,26613	1,29275	0,57391	0,30527	0,33130	1,21048	48,267
6	ACOm	ant colony optimization M	0,34611	0,16683	0,15808	0,67103	0,86785	0,68980	0,64798	2,20563	0,71739	0,63947	0,05579	1,41265	47,419
7	MEC	mind evolutionary computation	0,99270	0,47345	0,21148	1,67763	0,60691	0,28046	0,21324	1,10061	0,66957	0,30000	0,26045	1,23002	44,061
8	SDOm	spiral dynamics optimization M	0,81076	0,56474	0,35334	1,72884	0,72333	0,30644	0,30985	1,33963	0,43479	0,13289	0,14695	0,71463	41,370
9	COAm	cuckoo optimization algorithm M	0,92400	0,43407	0,24120	1,59927	0,58309	0,23477	0,13842	0,95629	0,52174	0,24079	0,17001	0,93254	37,845
10	FAm	firefly algorithm M	0,59825	0,31520	0,15893	1,07239	0,51012	0,29178	0,41704	1,21894	0,24783	0,20526	0,35090	0,80398	33,152
11	ABC	artificial bee colony	0,78170	0,30347	0,19313	1,27829	0,53774	0,14799	0,11177	0,79750	0,40435	0,19474	0,13859	0,73768	29,784
12	BA	bat algorithm	0,40526	0,59145	0,78330	1,78002	0,20817	0,12056	0,21769	0,54641	0,21305	0,07632	0,17288	0,46225	29,488
13	CSS	charged system search	0,56605	0,68683	1,00000	2,25289	0,14065	0,01853	0,13638	0,29555	0,07392	0,00000	0,03465	0,10856	27,914
14	GSA	gravitational search algorithm	0,70167	0,41944	0,00000	1,12111	0,31623	0,25120	0,27812	0,84554	0,42609	0,25525	0,00000	0,68134	27,807
15	BFO	bacterial foraging optimization	0,67203	0,28721	0,10957	1,06881	0,39655	0,18364	0,17298	0,75317	0,37392	0,24211	0,18841	0,80444	27,549
16	EM	electroMagnetism-like algorithm	0,12235	0,42928	0,92752	1,47915	0,00000	0,02413	0,29215	0,31628	0,00000	0,00527	0,10872	0,11399	18,981
17	SFL	shuffled frog-leaping	0,40072	0,22021	0,24624	0,86717	0,20129	0,02861	0,02221	0,25211	0,19565	0,04474	0,06607	0,30646	13,201
18	MA	monkey algorithm	0,33192	0,31029	0,13582	0,77804	0,10000	0,05443	0,07482	0,22926	0,15652	0,03553	0,10669	0,29874	11,771
19	FSS	fish school search	0,46812	0,23502	0,10483	0,80798	0,12825	0,03458	0,05458	0,21741	0,12175	0,03947	0,08244	0,24366	11,329
20	IWDm	intelligent water drops M	0,26459	0,13013	0,07500	0,46972	0,28568	0,05445	0,05112	0,39126	0,22609	0,05659	0,05054	0,33322	10,434
21	PSO	particle swarm optimisation	0,20449	0,07607	0,06641	0,34696	0,18873	0,07233	0,18207	0,44313	0,16956	0,04737	0,01947	0,23641	8,431
22	RND	random	0,16826	0,09038	0,07438	0,33302	0,13480	0,03318	0,03949	0,20747	0,12175	0,03290	0,04898	0,20363	5,056
23	GWO	grey wolf optimizer	0,00000	0,00000	0,02093	0,02093	0,06562	0,00000	0,00000	0,06562	0,23478	0,05789	0,02545	0,31812	1,000

Выводы

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

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

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

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

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

в архиве скрипт для расчета рейтинговой таблицы по методике в этой статье).

Плюсы и минусы модифицированного алгоритма оптимизации спиральной динамики (SDOm):

Плюсы:
1. Небольшое количество внешних параметров.
2. Простая реализация.
3. Скорость работы.

Минусы:
1. Высокий разброс результатов.
2. Склонность к застреванию в локальных экстремумах.

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