Популяционные алгоритмы оптимизации: Алгоритм поиска системой зарядов (Charged System Search, CSS)

Содержание:

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

1. Введение

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

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

Алгоритм поиска системой зарядов (Charged System Search, CSS) впервые представлен Кавехом (А. Kaveh) и Талатахари (S. Talatahari) в 2010 г.

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

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

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

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

С учетом вышесказанного запишем шаги псевдокода алгоритма:

1. Инициализируем частицы начальным случайным положением в пространстве поиска, так же задаём случайное положение в пространстве для предыдущей итерации (делаем допущение, что предыдущая итерация была).

2. Рассчитываем значение фитнес функции.

3. Производим расчет следующего положения частиц по формулам.

4. Определяем наилучшее и наихудшее значение фитнес функции среди всех частиц.

5. Повторяем шаги с п.2. до выполнения условия останова.

Разберём формулы для расчета взаимного движения частиц. Основной характеристикой заряженной частицы является её заряд:

q = (φp - φw) / (φb - φw)

где:

• q - текущий заряд частицы
• φp - значение фитнес функции частицы
• φb - самое лучшее значение фитнес функции среди всех частиц
• φw - самое худшее значение фитнес функции среди всех частиц

Для определения расстояния между частицами будем использовать формулу:

r(i,j) = (|Xi - Xj|) / (|(Xi - Xj) * 0.5 - Xb|)

где:

• || - евклидово расстояние
• r(i,j) - расстояние между частицами i и j
• Xi и Xj - соответствующие координаты частиц i и j
• Xb - соответствующая координата лучшего найденного за все итерации положения.

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

Так же как и в электромагнитном алгоритме EM силы взаимодействия могут быть как притягивающими, так и отталкивающими. Обозначим знак направления переменной c. Для учета направления сил будем применять следующее выражение условия:

c = -1, если φi < φj, иначе c = 1

где:

• c - знак направления сил взаимодействия
• φi и φj - значения фитнес функции частиц i и j

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

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

F = qi * Q * c * (Xj - Xi)

где:

• F - сила воздействия на частицу
• qi - частица, для которой считаем силу воздействия на неё
• Q - компонент, учитывающий взаимное положение двух рассматриваемых частиц в зависимости от проникновения их сфер друг в друга, формула для Q:

Q = ((qj * r(i,j) * b1) / a^3) + (qj * b2) / r(i,j)^2

где:

• qj - заряд частицы, воздействующей на рассматриваемую
• b1 и b2 для "включения/отключения" соответствующего члена выражения, при этом b1 = 0 и b2 = 1 при r >= радиуса частицы, и  b1 = 1 и b2 = 0 если меньше.

И, наконец, новую координату перемещения частиц можем рассчитать по формуле:

Xn = X + λ1 * U * V + λ2 * U * coordinatesNumber * (F / qi)

где:

• Xn - новая координата
• λ1 - весовой коэффициент (внешний параметр), определяет степень влияния второго слагаемого - скорость
• λ2 - весовой коэффициент (внешний параметр), определяет степень влияния третьего слагаемого - ускорение
• U - случайное число в диапазоне [0;1]
• V - разница между координатой на текущей итерации и на предыдущей
• coordinatesNumber - количество координат, в оригинальной формуле этого "коэффициента" нет, введено мной из-за того, что с увеличением размерности пространства поиска приходится увеличивать коэффициент λ2 (поэтому введено для избежания эффекта "заморозки" частиц)

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

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

Структура частицы включает следующие поля:

• -c: массив координат частицы. Этот массив содержит текущие координаты частицы в пространстве.
• -cPrev: массив предыдущих координат частицы. Этот массив содержит предыдущие координаты частицы в пространстве.
• -cNew: массив новых координат частицы. Этот массив содержит новые координаты частицы, которые будут использоваться в следующей итерации алгоритма.
• -q: заряд частицы. Это значение представляет собой заряд, присвоенный данной частице. Заряд может принимать только положительные значения отличные от 0.
• -f: значение функции приспособленности частицы.

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

//——————————————————————————————————————————————————————————————————————————————
struct S_Particle
{
  double c     [];  //coordinates
  double cPrev [];  //coordinates
  double cNew  [];  //coordinates
  double q;         //particle charge
  double f;         //fitness
};
//——————————————————————————————————————————————————————————————————————————————

Объявим класс C_AO_CSS, который включает в себя:

Свойства класса:

• - p: массив частиц
• - rangeMax: массив с максимальными значениями диапазона поиска для каждой координаты
• - rangeMin: массив с минимальными значениями диапазона поиска для каждой координаты
• - rangeStep: массив с размерами шагов поиска для каждой координаты
• - cB: массив с лучшими найденными координатами
• - fB: значение фитнес функции для лучших координат
• - fW: значение фитнес функции для худших координат

Методы класса:

• - Init: инициализирует параметры алгоритма (количество координат, количество частиц, размер радиуса, коэффициенты скорости и ускорения)
• - Moving: выполняет перемещение частиц
• - Revision: выполняет обновление лучших координат

Приватные свойства класса:

• - coordinatesNumber: количество координат
• - particlesNumber: количество частиц
• - radius: размер радиуса
• - speedCo: коэффициент скорости
• - accelCo: коэффициент ускорения
• - F: вектор сил
• - revision: флаг, указывающий на необходимость ревизии

Приватные методы класса:

• - SeInDiSp: вычисляет новое значение координаты в заданном диапазоне с заданным шагом
• - RNDfromCI: генерирует случайное число в заданном интервале

//——————————————————————————————————————————————————————————————————————————————
class C_AO_CSS
{
  //----------------------------------------------------------------------------
  public: S_Particle p     []; //particles
  public: double rangeMax  []; //maximum search range
  public: double rangeMin  []; //manimum search range
  public: double rangeStep []; //step search
  public: double cB        []; //best coordinates
  public: double fB;           //FF of the best coordinates
  public: double fW;           //FF of the worst coordinates

  public: void Init (const int    coordinatesNumberP, //coordinates number
                     const int    particlesNumberP,   //particles number
                     const double radiusSizeP,        //radius size
                     const double speedCoP,           //speed coefficient
                     const double accelCoP);          //acceleration coefficient

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

  //----------------------------------------------------------------------------
  private: int    coordinatesNumber; //coordinates number
  private: int    particlesNumber;   //particles number
  private: double radius;            //radius size
  private: double speedCo;           //speed coefficient
  private: double accelCo;           //acceleration coefficient
  private: double F       [];        //force vector
  private: bool   revision;

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

Метод C_AO_CSS инициализирует параметры объекта класса. Он принимает в качестве аргументов значения количества координат, количества частиц, размера радиуса, коэффициента скорости и коэффициента ускорения.

Внутри метода происходит сброс генератора случайных чисел, установка начальных значений для переменных fB и revision. Затем значения аргументов присваиваются соответствующим переменным объекта.
Далее происходит изменение размеров массивов rangeMax, rangeMin, rangeStep, F, p и cB в соответствии с количеством координат и частиц.
Затем в цикле происходит изменение размеров массивов для каждой частицы и установка начального значения переменной f для каждой частицы.
В конце метода происходит изменение размера массива cB в соответствии с количеством координат.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_CSS::Init (const int    coordinatesNumberP, //coordinates number
                     const int    particlesNumberP,   //particles number
                     const double radiusSizeP,        //radius size
                     const double speedCoP,           //speed coefficient
                     const double accelCoP)           //acceleration coefficient
{
  MathSrand ((int)GetMicrosecondCount ()); // reset of the generator
  fB       = -DBL_MAX;
  revision = false;

  coordinatesNumber = coordinatesNumberP;
  particlesNumber   = particlesNumberP;
  radius            = radiusSizeP;
  speedCo           = speedCoP;
  accelCo           = accelCoP;

  ArrayResize (rangeMax,  coordinatesNumber);
  ArrayResize (rangeMin,  coordinatesNumber);
  ArrayResize (rangeStep, coordinatesNumber);
  ArrayResize (F,         coordinatesNumber);

  ArrayResize (p,  particlesNumber);

  for (int i = 0; i < particlesNumber; i++)
  {
    ArrayResize (p [i].c,     coordinatesNumber);
    ArrayResize (p [i].cPrev, coordinatesNumber);
    ArrayResize (p [i].cNew,  coordinatesNumber);
    p [i].f  = -DBL_MAX;
  }

  ArrayResize (cB, coordinatesNumber);
}
//——————————————————————————————————————————————————————————————————————————————

Основная логика перемещения частиц (поисковых агентов) реализована в методе Moving ().

На самой первой итерации необходимо выполнить инициализацию начальных значений координат частиц случайным числом в диапазоне от rangeMin до rangeMax, а значение приспособленности частиц принимаем равными значению `-DBL_MAX`.

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

//----------------------------------------------------------------------------
if (!revision)
{
  fB = -DBL_MAX;

  for (int obj = 0; obj < particlesNumber; obj++)
  {
    for (int c = 0; c < coordinatesNumber; c++)
    {
      p [obj].c     [c] = RNDfromCI (rangeMin [c], rangeMax [c]);
      p [obj].cPrev [c] = RNDfromCI (rangeMin [c], rangeMax [c]);

      p [obj].c     [c] = SeInDiSp (p [obj].c     [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      p [obj].cPrev [c] = SeInDiSp (p [obj].cPrev [c], rangeMin [c], rangeMax [c], rangeStep [c]);

      p [obj].f         = -DBL_MAX;
    }
  }

  double r = 0.0;
  double t = 0.0;

  for (int c = 0; c < coordinatesNumber; c++)
  {
    t = rangeMax [c] - rangeMin [c];
    r += t * t;
  }

  radius *= sqrt (r);
  revision = true;
}

Оставшаяся часть кода метода Moving () выполняется на второй и последующих итерациях и отвечает за перемещение частиц в поисковом пространстве.

Сначала вычисляется разница между значениями фитнес функции fB и fW (для наилучших координат, найденных за все итерации и наихудшие координаты среди частиц на текущей итерации) и сохраняется в переменную difference. Если difference равна 0.0, то ей присваивается значение 1.0.

Затем следует цикл, в котором происходит вычисление нового значения для каждой частицы. Для каждой частицы i вычисляется новое значение заряда q.

Далее объявляются и инициализируются переменные summ1, summ2, q, e, c, b1, b2, X, Q, U, V, t1, t2 для использования в выше описанных формулах.

В цикле для каждой частицы происходит вычисление суммарной силы F, действующей со стороны всех остальных частиц в популяции. Для каждой частицы i происходит цикл, в котором вычисляется сумма summ1 и summ2. Затем вычисляется расстояние r между частицами i и j. Если r равно 0.0, то ему присваивается значение 0.01, что бы избежать деления на 0. Затем вычисляются значения b1 и b2 в зависимости от значения r и radius. Затем вычисляется значение направления силы c в зависимости от значений приспособленности двух рассматриваемых частиц. Далее вычисляется значение Q. Затем для каждой координаты k вычисляется значение силы F[k].

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

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

double difference = fB - fW;
if (difference == 0.0) difference = 1.0;

for (int i = 0; i < particlesNumber; i++)
{
  p [i].q = ((p [i].f - fW) / difference) + 0.1;
}

double summ1 = 0.0;
double summ2 = 0.0;
double q     = 0.1;
double e     = 0.001;
double c     = 0.0;
double b1    = 0.0;
double b2    = 0.0;
double X     = 0.0;
double Q     = 0.0;
double U     = 0.0;
double V     = 0.0;
double t1    = 0.0;
double t2    = 0.0;

for (int i = 0; i < particlesNumber && !IsStopped (); i++)
{
  ArrayInitialize (F, 0.0);

for (int j = 0; j < particlesNumber && !IsStopped (); j++)
{
  if (i == j) continue;

  summ1 = 0.0;
  summ2 = 0.0;

  for (int k = 0; k < coordinatesNumber && !IsStopped (); k++)
  {
    t1 = p [i].c [k] - p [j].c [k];
    summ1 += t1 * t1;

    //t2 = t1 * 0.5 - cB [k];
    //summ2 += t2 * t2;
  }

  //r = sqrt (summ1) / (sqrt (summ2) + e);
  r = sqrt (summ1);
        
  if (r == 0.0) r = 0.01;

  if (r >= radius)
  {
    b1 = 0.0;
    b2 = 1.0;
  }
  else
  {
    b1 = 1.0;
    b2 = 0.0;
  }

  c = p [i].f < p [j].f ? -1.0 : 1.0;

  q = p [j].q;

  Q = ((q * r * b1 / (radius * radius * radius)) + (q * b2 / (r * r))) * c;

  for (int k = 0; k < coordinatesNumber && !IsStopped (); k++)
  {
    F [k] += /*p [i].q */ Q * (p [j].c [k] - p [i].c [k]);
  }
}

  for (int k = 0; k < coordinatesNumber && !IsStopped (); k++)
  {
    V = p [i].c [k] - p [i].cPrev [k];
    U = RNDfromCI (0.0, 1.0);

    X = p [i].c [k] + speedCo * U * V + accelCo * U * coordinatesNumber * (F [k] / p [i].q);
        
    p [i].cNew [k] = SeInDiSp (X, rangeMin [k], rangeMax [k], rangeStep [k]);
  }
}

for (int i = 0; i < particlesNumber && !IsStopped (); i++)
{
  for (int k = 0; k < coordinatesNumber && !IsStopped (); k++)
  {
    p [i].cPrev [k] = p [i].c [k];
    p [i].c [k] = p [i].cNew [k];
  }
}

И в завершение следует метод Revision ().
В начале метода переменной fW присваивается максимальное значение типа double (DBL_MAX), что бы мы могли в последующем определить худшую частицу с минимальным значением фитнес функции.
Затем происходит цикл по всем частицам системы. Для каждой частицы выполняются следующие действия:
- Если значение f текущей частицы больше значения fB (лучшая функция приспособленности из всех частиц), то значение fB обновляется значением f текущей частицы, а массив cB (лучшая позиция) копируется из позиции текущей частицы.
- Если значение f текущей частицы меньше значения fW (наименьшая функция приспособленности из всех частиц), то значение fW обновляется значением f текущей частицы.

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

//——————————————————————————————————————————————————————————————————————————————
void C_AO_CSS::Revision ()
{
  fW  = DBL_MAX;

  for (int i = 0; i < particlesNumber; i++)
  {
    if (p [i].f > fB)
    {
      fB = p [i].f;
      ArrayCopy (cB, p [i].c, 0, 0, WHOLE_ARRAY);
    }

    if (p [i].f < fW)
    {
      fW = p [i].f;
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

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

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

C_AO_CSS:50;0.1;0.7;0.01
=============================
5 Rastrigin's; Func runs 10000 result: 70.43726076935499
Score: 0.87276
25 Rastrigin's; Func runs 10000 result: 68.88569793414477
Score: 0.85353
500 Rastrigin's; Func runs 10000 result: 66.01225385184436
Score: 0.81793
=============================
5 Forest's; Func runs 10000 result: 0.4891262437640296
Score: 0.27667
25 Forest's; Func runs 10000 result: 0.1494549763925046
Score: 0.08454
500 Forest's; Func runs 10000 result: 0.07829232143185726
Score: 0.04429
=============================
5 Megacity's; Func runs 10000 result: 2.04
Score: 0.17000
25 Megacity's; Func runs 10000 result: 0.744
Score: 0.06200
500 Megacity's; Func runs 10000 result: 0.26880000000000004
Score: 0.02240
=============================
All score: 3.20412

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

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

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

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

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

Тестирование алгоритма CSS определило нового лидера для оптимизации гладких функций, прошлым лидером на функции Rastrigin был так же алгоритм инспирированный неживой природой - электромагнитный поиск (EM), на этот раз новый рекорд превышает предыдущий почти на 10%. К сожалению, на функции Forest с острым глобальным экстремумом и на дискретной функции Megacity алгоритм демонстрирует одни из самых худших результатов. Благодаря впечатляющему результату на Rastrigin с 1000 переменных алгоритм по суммарным показателям смог попасть на 13-е место из 20-и. За отведённое регламентом тестирования количество 10000 запусков алгоритма CSS не смог приблизиться к глобальному экстремуму ближе чем на 90% (см. принты работы тестового стенда, приведённые выше).   

№	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	SDS	stochastic Diffusion Search	0,99737	1,00000	0,58904	2,58641	0,96893	1,00000	0,95092	2,91985	1,00000	1,00000	0,72149	2,72149	100,000
2	SSG	saplings sowing and growing	1,00000	0,95313	0,51630	2,46944	0,72740	0,69680	1,00000	2,42421	0,69612	0,65918	1,00000	2,35531	87,506
3	HS	harmony search	0,99676	0,90817	0,44686	2,35179	1,00000	0,72930	0,44806	2,17736	0,91159	0,76578	0,41537	2,09274	79,501
4	ACOm	ant colony optimization M	0,34611	0,17142	0,15808	0,67562	0,86888	0,73719	0,77362	2,37968	0,91159	0,68163	0,05606	1,64929	55,026
5	IWO	invasive weed optimization	0,95828	0,63939	0,27647	1,87415	0,70773	0,34168	0,31773	1,36714	0,72927	0,32539	0,33289	1,38756	54,060
6	MEC	mind evolutionary computation	0,99270	0,48648	0,21148	1,69066	0,60762	0,29973	0,25459	1,16194	0,85083	0,31978	0,26170	1,43231	49,669
7	COAm	cuckoo optimization algorithm M	0,92400	0,44601	0,24120	1,61121	0,58378	0,25090	0,16526	0,99994	0,66298	0,25666	0,17083	1,09047	42,223
8	FAm	firefly algorithm M	0,59825	0,32387	0,15893	1,08106	0,51073	0,31182	0,49790	1,32045	0,31491	0,21880	0,35258	0,88629	36,941
9	ABC	artificial bee colony	0,78170	0,31182	0,19313	1,28664	0,53837	0,15816	0,13344	0,82998	0,51381	0,20758	0,13926	0,86064	32,977
10	BA	bat algorithm	0,40526	0,60773	0,78330	1,79629	0,20841	0,12884	0,25989	0,59714	0,27073	0,08135	0,17371	0,52579	32,236
11	GSA	gravitational search algorithm	0,70167	0,43098	0,00000	1,13265	0,31660	0,26845	0,33204	0,91710	0,54144	0,27208	0,00000	0,81352	31,522
12	BFO	bacterial foraging optimization	0,67203	0,29511	0,10957	1,07671	0,39702	0,19626	0,20652	0,79980	0,47514	0,25807	0,18932	0,92253	30,702
13	CSS	charged system search	0,56605	0,70573	1,00000	2,27178	0,14081	0,01980	0,16282	0,32343	0,09393	0,00000	0,03481	0,12874	29,743
14	EM	electroMagnetism-like algorithm	0,12235	0,44109	0,92752	1,49096	0,00000	0,02578	0,34880	0,37458	0,00000	0,00562	0,10924	0,11486	20,252
15	SFL	shuffled frog-leaping	0,40072	0,22627	0,24624	0,87323	0,20153	0,03057	0,02652	0,25862	0,24862	0,04769	0,06639	0,36270	14,050
16	MA	monkey algorithm	0,33192	0,31883	0,13582	0,78658	0,10012	0,05817	0,08932	0,24762	0,19889	0,03787	0,10720	0,34396	12,564
17	FSS	fish school search	0,46812	0,24149	0,10483	0,81445	0,12840	0,03696	0,06516	0,23052	0,15471	0,04208	0,08283	0,27961	11,880
18	PSO	particle swarm optimisation	0,20449	0,07816	0,06641	0,34906	0,18895	0,07730	0,21738	0,48363	0,21547	0,05049	0,01957	0,28553	9,246
19	RND	random	0,16826	0,09287	0,07438	0,33551	0,13496	0,03546	0,04715	0,21757	0,15471	0,03507	0,04922	0,23900	5,083
20	GWO	grey wolf optimizer	0,00000	0,00000	0,02093	0,02093	0,06570	0,00000	0,00000	0,06570	0,29834	0,06170	0,02557	0,38561	1,000

Выводы

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

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

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

К примеру, если рассмотреть алгоритм в первой строчке рейтинга SDS, то он не самый лучший на отдельных тестовых задачах (гладкие функции со многими переменными для него даются средне по таблице). Если взять алгоритм ACOm, то его отдельные результаты далеко ниже средних по таблице (удивительно плохо решает гладкие функции), но с Forest и дискретной Megacity справляется очень хорошо (он изначально был спроектирован для решения дискретных задач - типа задачи Коммивояжера), хотя масштабируемость оставляет желать много лучшего.

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

Масштабное тестирование алгоритмов оптимизации с самыми различными стратегиями поиска выявило неожиданный факт - стратегия может оказаться даже хуже, чем если применять простой случайный поиск с выбором наилучшего результата - RND занимает второе с низу место вместо последнего ожидаемого, GWO оказался хуже случайного поиска за исключением дискретной Megacity с 10 параметрами.

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

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

Рисунок 2. Гистограмма итоговых результатов тестирования алгоритмов.

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

Плюсы:
1. Высокая масштабируемость на гладких функциях.
2. Небольшое количество внешних параметров.

Минусы:
1. Невысокие результаты на дискретных функциях.
2. Низкая сходимость.
3. Склонность к застреванию в локальных экстремумах.

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