preview
Оптимизация бактериальным хемотаксисом — Bacterial Chemotaxis Optimization (BCO)

Оптимизация бактериальным хемотаксисом — Bacterial Chemotaxis Optimization (BCO)

MetaTrader 5Примеры | 6 сентября 2024, 16:35
711 0
Andrey Dik
Andrey Dik

Содержание

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


Введение

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

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

  1. Бактерии в новой модели используют информацию о значениях концентрации.
  2. Они не продолжают движение в одном направлении при увеличении концентраций хемоаттрактантов.

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

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

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

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


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

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

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

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

Инициализация.

1. Задать параметры:

  • popSize: размер популяции (количество бактерий)
  • hs: количество шагов для расчета среднего изменения
  • T0: начальная температура
  • b: параметр
  • tau_c: параметр
  • v: скорость

2. Создать массив бактерий размером popSize

3. Для каждой бактерии i от 0 до popSize-1:

  • Инициализировать fPrev значением -DBL_MAX
  • Создать массив fHistory размером hs и заполнить его нулями

Основной цикл оптимизации. Повторять до достижения условия остановки:

Этап движения для каждой бактерии i от 0 до popSize - 1:

1. Получить текущее значение целевой функции f_tr

2. Получить предыдущее значение целевой функции f_pr из bacterium [i].fPrev

3. Если f_tr <= f_pr: T = T0

    Иначе: вычислить b_corr = CalculateCorrectedB (f_tr, f_pr, i)

  • T = T0 * exp (b_corr * (f_tr - f_pr))

4. Сгенерировать tau из экспоненциального распределения с параметром T.

5. Вычислить новые углы new_angles [] для coords - 1 измерений: для каждого угла j от 0 до coords - 2:

  • theta = CalculateRotationAngle ()
  • mu = 62 * (1 - cos (theta)) * π / 180
  • sigma = 26 * (1 - cos (theta)) * π / 180
  • new_angles [j] = случайное число из гауссовского распределения с параметрами (mu, mu-π, mu+π)

6. Вычислить новую позицию:

  • l = v * tau
  • CalculateNewPosition (l, new_angles, new_position, current_position)

7. Обновить позицию бактерии, ограничивая значения в пределах rangeMin и rangeMax

8. Обновить bacterium [i].fPrev значением f_tr

Этап ревизии.

1. Обновить глобальное лучшее решение cB со значением приспособленности fB

2. Для каждой бактерии i от 0 до popSize - 1. Обновить историю значений целевой функции fHistory:

  • Сдвинуть все значения на одну позицию влево
  • Добавить текущее значение целевой функции в конец истории

Вспомогательные функции:

CalculateCorrectedB (f_tr, f_pr, bacteriumIndex)

1. Вычислить delta_f_tr = f_tr - f_pr

2. Вычислить delta_f_pr = среднее изменение за последние hs шагов

3. Если |delta_f_pr| < epsilon: Вернуть b

   Иначе: Вернуть b * (1 / (|delta_f_tr / delta_f_pr| + 1) + 1 / (|f_pr| + 1))

CalculateRotationAngle ()

1. Вычислить cos_theta = exp (-tau_c / T0)

2. Вернуть arccos (cos_theta)

CalculateNewPosition (l, angles, new_position, current_position)

1. Вычислить new_position [0] с учетом всех углов

2. Для каждой координаты i от 1 до coords - 1:

   Вычислить new_position [i] с учетом соответствующих углов

3. Применить случайное направление (1 или -1) к каждой координате

GenerateFromExponentialDistribution (T)

Вернуть -T * ln (случайное число от 0 до 1)

Переходим к написанию кода алгоритма. Для представления бактерии как решение задачи оптимизации опишем структуру "S_BCO_Bacterium".

1. Поля структуры:

  • fPrev - предыдущее значение целевой функции.
  • fHistory [] - массив истории значений целевой функции.

2. Init - метод инициализации выполняет действия:

  • изменяется размер массива "fHistory" до значения "historySize".
  • инициализируются все элементы массива "fHistory" значением "0.0".
  • fPrev - устанавливается предыдущее значение целевой функции в минимально возможное значение.

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

//——————————————————————————————————————————————————————————————————————————————
struct S_BCO_Bacterium
{
    double fPrev;        // previous value of the objective function
    double fHistory [];  // history of objective function values

    void Init (int coords, int historySize)
    {
      ArrayResize     (fHistory, historySize);
      ArrayInitialize (fHistory, 0.0);
      fPrev = -DBL_MAX;
    }
};
//——————————————————————————————————————————————————————————————————————————————

Опишем класс алгоритма "C_AO_BCO". Давайте разберем его по частям.

1. В конструкторе инициализируются внешние параметры алгоритма.

2. Метод "SetParams" - обновляет значения параметров из массива "params".

3. Методы "Moving" и "Revision"- отвечают за движение бактерий и пересмотр их позиций.

4. В классе определены несколько приватных методов, которые используются для различных расчетов, связанных с алгоритмом. "CalculateAverageDeltaFpr", "CalculateNewAngles", "CalculateNewPosition", "GenerateFromExponentialDistribution", "CalculateCorrectedB", "CalculateRotationAngle", "RNDdir", bacterium - массив бактерий (популяция). Параметры класса:

  • hs - количество шагов для расчета среднего изменения.
  • T0 - начальная температура.
  • b - параметр.
  • tau_c - параметр.
  • v - скорость.
//——————————————————————————————————————————————————————————————————————————————
class C_AO_BCO : public C_AO
{
  public: //--------------------------------------------------------------------
  ~C_AO_BCO () { }
  C_AO_BCO ()
  {
    ao_name = "BCO";
    ao_desc = "Bacterial Chemotaxis Optimization";
    ao_link = "https://www.mql5.com/ru/articles/15711";

    popSize = 50;     // population size (number of bacteria)
    hs      = 10;     // number of steps to calculate average change
    T0      = 1.0;    // initial temperature
    b       = 0.5;    // parameter b
    tau_c   = 1.0;    // parameter tau_c
    v       = 1.0;    // velocity

    ArrayResize (params, 6);

    params [0].name = "popSize"; params [0].val = popSize;
    params [1].name = "hs";      params [1].val = hs;
    params [2].name = "T0";      params [2].val = T0;
    params [3].name = "b";       params [3].val = b;
    params [4].name = "tau_c";   params [4].val = tau_c;
    params [5].name = "v";       params [5].val = v;
  }

  void SetParams ()
  {
    popSize = (int)params [0].val;
    hs      = (int)params [1].val;
    T0      = params      [2].val;
    b       = params      [3].val;
    tau_c   = params      [4].val;
    v       = params      [5].val;
  }

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

  void Moving ();
  void Revision ();

  //----------------------------------------------------------------------------
  int    hs;
  double T0;
  double b;
  double tau_c;
  double v;

  S_BCO_Bacterium bacterium [];

  private: //-------------------------------------------------------------------
  double CalculateAverageDeltaFpr            (int bacteriumIndex);
  void   CalculateNewAngles                  (double &angles []);
  void   CalculateNewPosition                (double l, const double &angles [], double &new_position [], const double &current_position []);
  double GenerateFromExponentialDistribution (double T);
  double CalculateCorrectedB                 (double f_tr, double f_pr, int bacteriumIndex);
  double CalculateRotationAngle              ();
  int    RNDdir                              ();
};

//——————————————————————————————————————————————————————————————————————————————
bool C_AO_BCO::Init (const double &rangeMinP  [], //minimum search range
                     const double &rangeMaxP  [], //maximum search range
                     const double &rangeStepP [], //step search
                     const int     epochsP = 0)   //number of epochs
{
  if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false;

  //----------------------------------------------------------------------------
  ArrayResize (bacterium, popSize);
  for (int i = 0; i < popSize; i++) bacterium [i].Init (coords, hs);

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

Метод "Moving" класса "C_AO_BCO" отвечает за перемещение бактерий в пространстве поиска. Давайте разберем как он работает:

1. Если "revision" равно "false", это означает, что бактерии имеют начальную позицию.

  • Для каждой бактерии "a [i]" генерируются случайные координаты в пределах заданного диапазона.
  • Функция "u.RNDfromCI" генерирует случайное значение, а "u.SeInDiSp" корректирует ее с учетом заданного шага.

2. Основной цикл перемещения, если "revision" равно "true". Метод выполняет основную логику перемещения бактерий. Определение температуры "T":

  • Если текущее значение функции "f_tr" лучше или равно предыдущему "f_pr", используется начальная температура "T0".
  • В противном случае температура корректируется с помощью функции "CalculateCorrectedB", которая учитывает разницу между текущим и предыдущим значением функции приспособленности. 
  • Генерация времени перемещения "tau": используется экспоненциальное распределение для генерации времени перемещения.
  • Вычисляются новые углы перемещения и новая позиция на основе длины перемещения "l" и новых углов.
  • Новая позиция корректируется с учетом заданного диапазона и шага.
  • В конце цикла обновляется предыдущее значение функции приспособленности для каждой бактерии.

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

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

    revision = true;
    return;
  }

  //----------------------------------------------------------------------------
  for (int i = 0; i < popSize; i++)
  {
    double f_tr = a [i].f;
    double f_pr = bacterium [i].fPrev;

    double T;
    
    if (f_tr <= f_pr)
    {
      T = T0;
    }
    else
    {
      double b_corr = CalculateCorrectedB (f_tr, f_pr, i);
      
      T = T0 * exp (b_corr * (f_tr - f_pr));
    }

    double tau = GenerateFromExponentialDistribution (T);

    double new_angles [];
    ArrayResize (new_angles, coords - 1);
    CalculateNewAngles (new_angles);

    double l = v * tau;
    double new_position [];
    ArrayResize (new_position, coords);
    CalculateNewPosition (l, new_angles, new_position, a [i].c);

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

    bacterium [i].fPrev = a [i].f;
  }
}
//——————————————————————————————————————————————————————————————————————————————

Метод "Revision" класса "C_AO_BCO" отвечает за обновление информации о лучших найденных решениях и истории значений функции приспособленности для каждой бактерии.

1. Переменная "ind" инициализируется значением "-1". Она будет использоваться для хранения индекса бактерии, у которой найдено лучшее значение функции.

2. Поиск лучшего значения функции:

  • Метод проходит через все бактерии в популяции "popSize" и ищет ту, у которой значение функции "f" больше текущего лучшего значения "fB".
  • Если находится бактерия с более высоким значением функции, то "fB" обновляется, и индекс этой бактерии сохраняется в "ind".

3. Если была найдена бактерия с индексом "ind" (т.е. "ind" не равен "-1"), то координаты этой бактерии копируются в массив "cB", который, представляет собой координаты текущего лучшего решения.

4. Для каждой бактерии обновляется история значений функции. Метод проходит по каждому элементу "fHistory", сдвигая значения на одну позицию влево, чтобы освободить место для нового значения. В конце каждой итерации в последний элемент массива "fHistory" записывается текущее значение приспособленности "a [i].f" для каждой бактерии.

Таким образом, метод "Revision" выполняет две основные функции:

  • Обновляет лучшее значение функции приспособленности и соответствующие координаты.
  • Обновляет историю значений функции приспособленности для каждой бактерии, что позволяет отслеживать изменения в их состоянии на протяжении истории их перемещений. 
//——————————————————————————————————————————————————————————————————————————————
void C_AO_BCO::Revision ()
{
  int ind = -1;

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

  if (ind != -1)
  {
    ArrayCopy (cB, a [ind].c, 0, 0, WHOLE_ARRAY);
  }

  for (int i = 0; i < popSize; i++)
  {
    for (int j = 1; j < hs; j++)
    {
      bacterium [i].fHistory [j - 1] = bacterium [i].fHistory [j];
    }

    bacterium [i].fHistory [hs - 1] = a [i].f;
  }
}
//——————————————————————————————————————————————————————————————————————————————

Метод "CalculateAverageDeltaFpr" класса "C_AO_BCO" предназначен для вычисления средних изменений значений фитнес-функции (дельты) для конкретной бактерии между двумя её соседними положениями, основываясь на истории значений приспособленности.

//——————————————————————————————————————————————————————————————————————————————
double C_AO_BCO::CalculateAverageDeltaFpr (int bacteriumIndex)
{
  double sum = 0;

  for (int i = 1; i < hs; i++)
  {
    sum += bacterium [bacteriumIndex].fHistory [i] - bacterium [bacteriumIndex].fHistory [i - 1];
  }

  return sum / (hs - 1);
}
//——————————————————————————————————————————————————————————————————————————————

Метод "CalculateNewAngles" класса "C_AO_BCO" предназначен для вычисления новых углов на основе логики, связанной с вращением и распределением, выполняет следующие действия:

  • Проходит по массиву для новых углов и для каждого угла вычисляет новое значение.
  • Использует параметры, зависящие от косинуса угла, для генерации значений, которые используют гауссовское распределение.
//——————————————————————————————————————————————————————————————————————————————
void C_AO_BCO::CalculateNewAngles (double &angles [])
{
  for (int i = 0; i < coords - 1; i++)
  {
    double theta = CalculateRotationAngle ();
    double mu    = 62 * (1 - MathCos (theta)) * M_PI / 180.0;
    double sigma = 26 * (1 - MathCos (theta)) * M_PI / 180.0;

    angles [i] = u.GaussDistribution (mu, mu - M_PI, mu + M_PI, 8);
  }
}
//——————————————————————————————————————————————————————————————————————————————

Метод "CalculateNewPosition" класса "C_AO_BCO" предназначен для вычисления новых координат позиции на основе текущих координат, углов и параметра "l". 

1. Входные параметры метода:

  • l - коэффициент, влияющий на изменение позиции.
  • angles [] - массив углов, которые используются для вычисления новой позиции.
  • new_position [] - массив, в который будут записаны новые координаты.
  • current_position [] - массив текущих координат.

2. Первая координата "new_position [0]" вычисляется как сумма текущей координаты "current_position [0]" и произведения "l" на разницу между "rangeMax [0]" и "rangeMin [0]".

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

4. Результат умножается на значение, возвращаемое функцией "RNDdir ()", которая генерирует случайное направление "-1" или "1".

5. Для каждой следующей координаты "new_position [i]", где "i" от "1" до "coords - 2" вычисляется новая позиция на основе текущей позиции и синуса соответствующего угла.

6. Каждая новая координата также умножается на косинусы углов, начиная с текущего индекса "i" до предпоследнего.

7. Случайное направление для остальных координат, результат также умножается на значение, возвращаемое "RNDdir ()".

8. Обработка последней координаты, если количество координат больше 1, для последней координаты "new_position [coords - 1]" вычисляется новая позиция на основе текущей позиции и синуса последнего угла.

Таким образом метод "CalculateNewPosition" выполняет следующие действия:

  • Вычисляет новые координаты на основе текущих координат и углов.
  • Учитывает влияние случайного направления на каждую координату.
  • Применяет тригонометрические функции (синус и косинус) для учета углов.

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

//——————————————————————————————————————————————————————————————————————————————
void C_AO_BCO::CalculateNewPosition (double l, const double &angles [], double &new_position [], const double &current_position [])
{
  new_position [0] = current_position [0] + l * (rangeMax [0] - rangeMin [0]);
 
  for (int k = 0; k < coords - 1; k++)
  {
    new_position [0] *= MathCos (angles [k]);
  }
 
  new_position [0] *= RNDdir ();

  for (int i = 1; i < coords - 1; i++)
  {
    new_position [i] = current_position [i] + l * MathSin (angles [i - 1]) * (rangeMax [0] - rangeMin [0]);
    
    for (int k = i; k < coords - 1; k++)
    {
      new_position [i] *= MathCos (angles [k]);
    }
    
    new_position [i] *= RNDdir ();
  }

  if (coords > 1)
  {
    new_position [coords - 1] = current_position [coords - 1] + l * MathSin (angles [coords - 2]);
  }
 
}
//——————————————————————————————————————————————————————————————————————————————

Далее кратко опишем метод "RNDdir" класса "C_AO_BCO", который предназначен для генерации случайного направления, которое может принимать одно из двух значений: -1 или 1.

//——————————————————————————————————————————————————————————————————————————————
int C_AO_BCO::RNDdir ()
{
  if (u.RNDbool () < 0.5) return -1;
 
  return 1;
}
//——————————————————————————————————————————————————————————————————————————————

Сделаем краткий обзор методов класса "C_AO_BCO".

Метод "GenerateFromExponentialDistribution" выполняет:

  • генерацию случайного числа по экспоненциальному распределению с параметром "T".
  • далее использует случайное число из диапазона (0, 1), вычисляет его логарифм и умножает на "-T".
  • получаем случайное число, распределенное по экспоненциальному закону.

 Метод "CalculateCorrectedB" выполняет:

  • расчет скорректированного значения "b" на основе разницы между "f_tr" и "f_pr" (текущей и предыдущей приспособленности).
  • вычисляет разницу между "f_tr" и "f_pr", получает среднее значение для бактерии, и в зависимости от этого возвращает скорректированное значение "b".
//——————————————————————————————————————————————————————————————————————————————
double C_AO_BCO::GenerateFromExponentialDistribution (double T)
{
  return -T * MathLog (u.RNDprobab ());
}

double C_AO_BCO::CalculateCorrectedB (double f_tr, double f_pr, int bacteriumIndex)
{
  double delta_f_tr = f_tr - f_pr;
  double delta_f_pr = CalculateAverageDeltaFpr (bacteriumIndex);

  if (MathAbs (delta_f_pr) < DBL_EPSILON)
  {
    return b;
  }
  else
  {
    return b * (1 / (MathAbs (delta_f_tr / delta_f_pr) + 1) + 1 / (MathAbs (f_pr) + 1));
  }
}
//——————————————————————————————————————————————————————————————————————————————

Последним следует метод "CalculateRotationAngle" класса "C_AO_BCO". Метод вычисляет угол вращения на основе заданных параметров и возвращает значение в радианах.

//——————————————————————————————————————————————————————————————————————————————
double C_AO_BCO::CalculateRotationAngle ()
{
  double cos_theta = MathExp (-tau_c / T0);
  return MathArccos (cos_theta);
}
//——————————————————————————————————————————————————————————————————————————————

Протестируем оригинальную версию алгоритма и смотрим результаты:

BCO|Bacterial Chemotaxis Optimization|50.0|10.0|1.0|0.5|1.0|1.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.42924491510564006
25 Hilly's; Func runs: 10000; result: 0.282259866768426
500 Hilly's; Func runs: 10000; result: 0.2515386629014219
=============================
5 Forest's; Func runs: 10000; result: 0.2476662231845009
25 Forest's; Func runs: 10000; result: 0.17824381036550777
500 Forest's; Func runs: 10000; result: 0.15324081202657283
=============================
5 Megacity's; Func runs: 10000; result: 0.2430769230769231
25 Megacity's; Func runs: 10000; result: 0.11415384615384619
500 Megacity's; Func runs: 10000; result: 0.09444615384615461
=============================
All score: 1.99387 (22.15%)

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

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

Итак, представляю псевдокод моей версии алгоритма:

Инициализация:
1. Создать популяцию из popSize бактерий
2. Для каждой бактерии i:
    Инициализировать нулём историю значений целевой функции f_history [i] размера hs
    Установить начальное значение f_prev [i] = -DBL_MAX

Основной цикл:
Пока не достигнуто условие остановки:

1. Если это первая итерация:
   Для каждой бактерии i:
     Случайно инициализировать позицию x [i] в пространстве поиска
     x [i].[j] ∈ [x_min [j], x_max [j]] для каждой координаты j

2. Иначе:
   Для каждой бактерии i:
     a. Вычислить среднее изменение целевой функции:
        delta_ave [i] = (1 / (hs - 1)) * sum (f_history [i].[k] - f_history [i].[k-1] for k in 1..hs-1) + epsilon
     
     b. Вычислить относительное изменение приспособленности:
        delta [i] = 1 - |f (x [i]) - f_prev [i]| / delta_ave [i]
        delta [i] = max (delta [i], 0.0001)
     
     c. Для каждой координаты j:
        С вероятностью 0.5:
          dist [j] = (x_max [j] - x_min [j]) * delta [i]
          x [i].[j] = N (x [i].[j], x [i].[j] - dist [j], x [i].[j] + dist [j])
          Ограничить x [i].[j] в пределах [x_min [j], x_max [j]]
        Иначе:
          x [i].[j] = x_best [j]
     
     d. Обновить f_prev [i] = f (x [i])

3. Оценить целевую функцию f (x [i]) для каждой бактерии

4. Обновить лучшее найденное решение:
   Если существует i: f (x [i]) > f (x_best), то x_best = x [i]

5. Обновить историю значений целевой функции для каждой бактерии:
   Сдвинуть значения в f_history [i]
   Добавить новое значение: f_history [i].[hs - 1] = f (x [i])

Завершение:
Вернуть лучшее найденное решение x_best

Где:

  • x [i] - позиция i-й бактерии
  • f (x) - целевая функция
  • hs - размер истории
  • epsilon - малая константа для предотвращения деления на ноль
  • N (μ, a, b) - усеченное нормальное распределение со средним μ и границами [a, b]

Таким образом, мой модифицированный псевдокод отражает основную структуру и логику алгоритма BCO. Заострим внимание на основных моментах:

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

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

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

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

Эти изменения в логике привели к созданию более простого и, предположительно (до получения результатов тестов), более производительного алгоритма. Переходим к написанию кода.

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

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

Таким образом, метод "Init" класса "C_AO_BCOm" отвечает за инициализацию параметров алгоритма оптимизации. Он проверяет стандартные условия инициализации, создает необходимые массивы и заполняет их значениями.

//——————————————————————————————————————————————————————————————————————————————
bool C_AO_BCOm::Init (const double &rangeMinP  [], //minimum search range
                      const double &rangeMaxP  [], //maximum search range
                      const double &rangeStepP [], //step search
                      const int     epochsP = 0)   //number of epochs
{
  if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false;

  //----------------------------------------------------------------------------
  ArrayResize (bacterium, popSize);
  for (int i = 0; i < popSize; i++) bacterium [i].Init (coords, hs);

  ArrayResize (allowedDispl, coords);
  for (int c = 0; c < coords; c++) allowedDispl [c] = rangeMax [c] - rangeMin [c];

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

Разберем метод "Moving" класса "C_AO_BCOm", который отвечает за перемещение бактерий в пространстве поиска. Давайте разберем его по частям.

1. На первой итерации действия метода не изменились: инициализация координат бактерий случайными значения в заданном диапазоне.

2. Основной алгоритм перемещения: объявляются переменные для хранения значений, таких, как "Δ", "ΔAve", и "dist" и для каждого индивидуума в популяции:

  • Вычисляется среднее значение "ΔAve" с использованием функции "CalculateAverageDeltaFpr (i)".
  • Вычисляется относительное изменение "Δ", которое используется для определения степени изменения положения бактерий.
  • Если "Δ" слишком мал, оно устанавливается в 0.0001.

3. Изменение координат:

  • Для каждой координаты проверяется случайная вероятность (50%).
  • Если условие выполняется, вычисляется расстояние "dist", которое зависит от "allowedDispl [c]" и "Δ".
  • Новое значение "x" вычисляется с помощью функции "GaussDistribution", с учетом границ "xMin" и "xMax".
  • Если "x" выходит за пределы диапазона, оно корректируется с использованием "RNDfromCI".
  • Наконец, новое значение координаты сохраняется с учетом шага "rangeStep".

4. Сохраняется предыдущее значение функции приспособленности "f" для каждого индивидуума в массиве "bacterium". Используются массивы "a" и "bacterium". Функции "RNDfromCI", "SeInDiSp", "GaussDistribution" отвечают за генерацию случайных чисел и распределений, а также за нормализацию значений координат.

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

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

    revision = true;
    return;
  }

  //----------------------------------------------------------------------------
  double x    = 0.0;
  double xMin = 0.0;
  double xMax = 0.0;
  double Δ    = 0.0;
  double ΔAve = 0.0;
  double dist = 0.0;

  for (int i = 0; i < popSize; i++)
  {
    ΔAve = CalculateAverageDeltaFpr (i) + DBL_EPSILON;

    Δ = fabs (a [i].f - bacterium [i].fPrev) / ΔAve;

    Δ = 1.0 - Δ;

    if (Δ < 0.0001) Δ = 0.0001;

    for (int c = 0; c < coords; c++)
    {
      if (u.RNDprobab () < 0.5)
      {
        dist = allowedDispl [c] * Δ;

        x    = a [i].c [c];
        xMin = x - dist;
        xMax = x + dist;

        x = u.GaussDistribution (x, xMin, xMax, 8);

        if (x > rangeMax [c]) x = u.RNDfromCI (xMin, rangeMax [c]);
        if (x < rangeMin [c]) x = u.RNDfromCI (rangeMin [c], xMax);

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

    bacterium [i].fPrev = a [i].f;
  }
}
//——————————————————————————————————————————————————————————————————————————————

Метод "Revision ()" в классе "C_AO_BCOm", который отвечает за обновление информации о популяции и истории значений целевой функции, не изменился.


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

Теперь посмотрим, как работает новая версия алгоритма BCOm:

BCO|Bacterial Chemotaxis Optimization|50.0|10.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.759526049526603
25 Hilly's; Func runs: 10000; result: 0.6226756163411526
500 Hilly's; Func runs: 10000; result: 0.31483373090540534
=============================
5 Forest's; Func runs: 10000; result: 0.8937814268120954
25 Forest's; Func runs: 10000; result: 0.6133909133246214
500 Forest's; Func runs: 10000; result: 0.22541842289630293
=============================
5 Megacity's; Func runs: 10000; result: 0.653846153846154
25 Megacity's; Func runs: 10000; result: 0.42092307692307684
500 Megacity's; Func runs: 10000; result: 0.14435384615384755
=============================
All score: 4.64875 (51.65%)

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

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

Hilly

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

Forest

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

Megacity

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

Алгоритм по итогам тестирования занял стабильное 17 место в общем рейтинге алгоритмов оптимизации.

AO Description HillyHilly final ForestForest 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)
1ANSacross neighbourhood search0,949480,847760,438572,235811,000000,923340,399882,323230,709230,634770,230911,574916,13468,15
2CLAcode lock algorithm0,953450,871070,375902,200420,989420,917090,316422,222940,796920,693850,193031,683806,10767,86
3AMOmanimal migration ptimization M0,903580,843170,462842,209590,990010,924360,465982,380340,567690,591320,237731,396755,98766,52
4(P+O)ES(P+O) evolution strategies0,922560,881010,400212,203790,977500,874900,319452,171850,673850,629850,186341,490035,86665,17
5CTAcomet tail algorithm0,953460,863190,277702,094350,997940,857400,339492,194840,887690,564310,105121,557125,84664,96
6SDSmstochastic diffusion search M0,930660,854450,394762,179880,999830,892440,196192,088460,723330,611000,106701,441035,70963,44
7ESGevolution of social groups0,999060,796540,350562,146161,000000,828630,131021,959650,823330,553000,047251,423585,52961,44
8SIAsimulated isotropic annealing0,957840,842640,414652,215130,982390,795860,205071,983320,686670,493000,090531,270205,46960,76
9ACSartificial cooperative search0,755470,747440,304071,806981,000000,888610,224132,112740,690770,481850,133221,305835,22658,06
10ASOanarchy society optimization0,848720,746460,314651,909830,961480,791500,238031,991010,570770,540620,166141,277525,17857,54
11TSEAturtle shell evolution algorithm0,967980,644800,296721,909490,994490,619810,227081,841390,690770,426460,135981,253225,00455,60
12DEdifferential evolution0,950440,616740,303081,870260,953170,788960,166521,908650,786670,360330,029531,176534,95555,06
13CROchemical reaction optimisation0,946290,661120,298531,905930,879060,584220,211461,674730,758460,426460,126861,311784,89254,36
14BSAbird swarm algorithm0,893060,649000,262501,804550,924200,711210,249391,884790,693850,326150,100121,120124,80953,44
15HSharmony search0,865090,687820,325271,878180,999990,680020,095901,775920,620000,422670,054581,097254,75152,79
16SSGsaplings sowing and growing0,778390,649250,395431,823080,859730,624670,174291,658690,646670,441330,105981,193984,67651,95
17BCOmbacterial chemotaxis optimization M0,759530,622680,314831,697040,893780,613390,225421,732590,653850,420920,144351,219124,64951,65
18(PO)ES(PO) evolution strategies0,790250,626470,429351,846060,876160,609430,195911,681510,590000,379330,113221,082554,61051,22
19TSmtabu search M0,877950,614310,291041,783300,928850,518440,190541,637830,610770,382150,121571,114494,53650,40
20BSObrain storm optimization0,937360,576160,296881,810410,931310,558660,235371,725340,552310,290770,119140,962224,49849,98
21WOAmwale optimization algorithm M0,845210,562980,262631,670810,931000,522780,163651,617430,663080,411380,113571,188034,47649,74
22AEFAartificial electric field algorithm0,877000,617530,252351,746880,927290,726980,180641,834900,666150,116310,095080,877544,45949,55
23ACOmant colony optimization M0,881900,661270,303771,846930,858730,586800,150511,596040,596670,373330,024720,994724,43849,31
24BFO-GAbacterial foraging optimization - ga0,891500,551110,315291,757900,969820,396120,063051,428990,726670,275000,035251,036924,22446,93
25ABHAartificial bee hive algorithm0,841310,542270,263041,646630,878580,477790,171811,528180,509230,338770,103970,951974,12745,85
26ASBOadaptive social behavior optimization0,763310,492530,326191,582020,795460,400350,260971,456770,264620,171690,182000,618313,65740,63
27MECmind evolutionary computation0,695330,533760,326611,555690,724640,330360,071981,126980,525000,220000,041980,786983,47038,55
28IWOinvasive weed optimization0,726790,522560,331231,580580,707560,339550,074841,121960,423330,230670,046170,700173,40337,81
29Micro-AISmicro artificial immune system0,795470,519220,308611,623300,729560,368790,093981,192330,376670,158670,028020,563353,37937,54
30COAmcuckoo optimization algorithm M0,758200,486520,313691,558410,740540,280510,055991,077040,505000,174670,033800,713473,34937,21
31SDOmspiral dynamics optimization M0,746010,446230,296871,489120,702040,346780,109441,158260,428330,167670,036630,632633,28036,44
32NMmNelder-Mead method M0,738070,505980,313421,557470,636740,283020,082211,001970,446670,186670,040280,673623,23335,92
33FAmfirefly algorithm M0,586340,472280,322761,381380,684670,374390,109081,168140,286670,164670,047220,498553,04833,87
34GSAgravitational search algorithm0,647570,491970,300621,440160,539620,363530,099451,002600,326670,122000,019170,467832,91132,34
35BFObacterial foraging optimization0,611710,432700,313181,357590,544100,215110,056760,815970,421670,138000,031950,591622,76530,72
36ABCartificial bee colony0,633770,424020,308921,366710,551030,218740,056230,826000,340000,142000,031020,513022,70630,06
37BAbat algorithm0,597610,459110,352421,409150,403210,193130,071750,668100,210000,101000,035170,346172,42326,93
38AAAalgae adaptive algorithm0,500070,320400,255251,075720,370210,222840,167850,760890,278460,148000,097550,524022,36126,23
39SAsimulated annealing0,557870,421770,315491,295130,349980,152590,050230,552800,311670,100330,028830,440832,28925,43
40IWDmintelligent water drops M0,545010,378970,301241,225220,461040,147040,043690,651770,258330,097000,023080,378422,25525,06
41PSOparticle swarm optimisation0,597260,369230,299281,265770,372370,163240,070100,605720,256670,080000,021570,358232,23024,77
42Boidsboids algorithm0,433400,305810,254250,993460,357180,201600,157080,715860,278460,142770,098340,519572,22924,77
43MAmonkey algorithm0,591070,426810,318161,336040,311380,140690,066120,518190,228330,085670,027900,341902,19624,40
44SFLshuffled frog-leaping0,539250,358160,298091,195510,371410,114270,040510,526180,271670,086670,024020,382352,10423,38
45FSSfish school search0,556690,399920,311721,268330,310090,118890,045690,474670,211670,076330,024880,312882,05622,84




Выводы

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

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


Tab

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

chart

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

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


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

Плюсы:

  1. Быстрый.
  2. Самоадаптируемый.
  3. Хорошая масштабируемость.
  4. Всего лишь один внешний параметр.

Минусы:

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

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

Прикрепленные файлы |
BCOm.ZIP (35.49 KB)
Разработка системы репликации (Часть 46): Проект Chart Trade (V) Разработка системы репликации (Часть 46): Проект Chart Trade (V)
Устали тратить время на поиск того самого файла, который необходим для работы вашего приложения? Как насчет того, чтобы включить все в исполняемый файл? Так вы больше не будете тратить время на поиск необходимого. Знаю, что многие пользуются именно такой формой распространения и хранения вещей, но есть гораздо более подходящий способ. По крайней мере, что касается распространения исполняемых файлов и их хранения. Метод, который будет здесь представлен, может оказаться очень полезным, так как в качестве отличного помощника вы сможете использовать сам MetaTrader 5, а также MQL5. И это не так уж трудно и сложно для понимания.
Нейросети в трейдинге: Иерархическое обучение признаков облака точек Нейросети в трейдинге: Иерархическое обучение признаков облака точек
Продолжаем изучение алгоритмов для извлечения признаков из облака точек. И в данной статье мы познакомимся с механизмами повышения эффективности метода PointNet.
Создаем и оптимизируем торговую систему на основе волатильности с индикатором Чайкина Создаем и оптимизируем торговую систему на основе волатильности с индикатором Чайкина
В этой статье мы поговорим об индикаторе волатильности Чайкина (Chaikin Volatility, CHV). Разберемся, что делает этот индикатор, как и в каких условиях его можно использовать и как создать пользовательский индикатор волатильности. Проанализируем несколько простых стратегий и протестируем их, чтобы понять, какая стратегия лучше.
Построение модели ограничения тренда свечей (Часть 1): Для советников и технических индикаторов Построение модели ограничения тренда свечей (Часть 1): Для советников и технических индикаторов
Статья рассчитана на начинающих и профессиональных разработчиков MQL5. Она предоставляет фрагмент кода для определения индикаторов, генерирующих сигналы, и их ограничения трендами на более старших таймфреймах. Таким образом, трейдеры могут улучшить свои стратегии, включив в них более широкую перспективу рынка, что приведет к получению потенциально более надежных торговых сигналов.