Популяционные алгоритмы оптимизации: Гибридный алгоритм оптимизации бактериального поиска с генетическим алгоритмом (Bacterial Foraging Optimization - Genetic Algorithm, BFO-GA)

Andrey Dik | 11 января, 2024

Содержание:

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


1. Введение

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

BFO (Bacterial Foraging Optimization) — это алгоритм оптимизации, вдохновленный поведением бактерий при поиске пищи. Он был предложен в 2002 году Рахулом К. Куджуром. BFO моделирует движение бактерий, используя три основных механизма: переходы, диффузию и обновление позиции. Каждая бактерия в алгоритме представляет решение оптимизационной задачи, а пища соответствует оптимальному решению. Бактерии перемещаются в пространстве поиска с целью найти наилучшую пищу.

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

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

Гибридный алгоритм BFO-GA (Bacterial Foraging Optimization - Genetic Algorithm) был предложен в 2007 году в работе Д. Н. Кима, А. Абрахама и Чоу. Этот алгоритм комбинирует принципы оптимизации, основанные на поведении роющихся бактерий, с генетическими операторами отбора, скрещивания и мутации.

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

В качестве оператора отбора BFO-GA использует алгоритм на основе метода рулетки. Этот метод выбирает родительские бактерии с вероятностями, пропорциональными их приспособленности. Таким образом, более приспособленные бактерии имеют большую вероятность быть выбранными для скрещивания.

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

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

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


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

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

В алгоритме BFO-GA используются следующие шаги:

  1. Инициализация: Создание начальной популяции бактерий, каждая из которых представляет собой потенциальное решение задачи. Каждая бактерия имеет свои параметры, которые могут быть изменены в процессе оптимизации.
  2. Оценка пищевого градиента: Вычисление значения функции приспособленности для каждой бактерии в популяции и дальнейшее сравнение двух последних значений, и эта разница значений определяет качество решения, представляемого каждой бактерией.
  3. Движение в направлении градиента: Каждая бактерия перемещается в направлении пищевого градиента, что позволяет ей двигаться в сторону более оптимальных решений с постоянным вектором изменения положения.
  4. Движение в случайном направлении: Часть бактерий также выполняет случайное движение, чтобы избежать застревания в локальных оптимумах. Это движение основано на случайном изменении параметров бактерии в случае предыдущего неудачного перемещения.
  5. Генетические операторы: Применение генетических операторов - отбор, скрещивание и мутация, к популяции бактерий. Это позволяет создавать новые комбинации параметров и улучшать качество решений.
  6. Повторение шагов 2-5: Повторение шагов движения в направлении градиента, движения в случайном направлении и применения генетических операторов до достижения критерия остановки, например, достижения максимального числа итераций или достижения определенного значения функции приспособленности.

Теоретически, гибридный алгоритм BFO-GA должен иметь ряд преимуществ перед BFO, которые стоит упомянуть:

  1. Эксплорация и эксплуатация: BFO-GA обладает способностью к эксплорации пространства параметров, благодаря случайному движению бактерий, и эксплуатация, благодаря движению в направлении пищевого градиента. Это позволяет алгоритму находить оптимальные решения, избегая локальные оптимумы и сходясь к глобальному.
  2. Адаптивность: BFO-GA обладает способностью адаптироваться к изменяющимся условиям оптимизации. В процессе работы алгоритма параметры бактерий могут изменяться, что позволяет адаптироваться к новым условиям и находить более оптимальные решения.
  3. Отcутсвие необходимости в тюнинге параметров: Как и у любого оптимизационного алгоритма, у BFO-GA есть набор параметров, которые могут быть настроены для достижения лучших результатов. Это включает параметры, связанные с размером популяции бактерий, шагами движения в направлении градиента и случайного движения, вероятностями генетических операторов и другими. Изменение параметров не оказывает существенного влияния на результат.

offspring

Рисунок 1. Наследование родительских "генов" дочерней бактерией.

    Переходим от теоретических основ к практической реализации.

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

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

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

    Для описания бактерии напишем структуру S_Bacteria, содержащая следующие поля:

    //——————————————————————————————————————————————————————————————————————————————
struct S_Bacteria
{
  double c     []; //coordinates
  double cLast []; //coordinates
  double v     []; //vector
  double f;        //current health
  double fLast;    //previous health
  double lifeCNT;  //life counter
};
//——————————————————————————————————————————————————————————————————————————————

    Объявим класс C_AO_BFO_GA, который реализует алгоритм BFO-GA (Bacterial Foraging Optimization - Genetic Algorithm). Давайте разберем каждое поле и метод класса:

    Поля класса:

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

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

    //——————————————————————————————————————————————————————————————————————————————
class C_AO_BFO_GA
{
  //----------------------------------------------------------------------------
  public: S_Bacteria b     []; //bacteria
  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: void Init (const int    paramsP,         //number of opt. parameters
                     const int    populationSizeP, //population size
                     const double lambdaP,         //lambda
                     const double reproductionP,   //probability of reproduction
                     const int    lifeCounterP,    //life counter
                     const double powerMutP);      //mutation power

  public: void Swimming   ();
  public: void Evaluation ();

  //----------------------------------------------------------------------------
  private: double NewVector (int paramInd);
  private: S_Bacteria bT []; //bacteria
  private: double v      [];
  private: int    ind    [];
  private: double val    [];

  private: int    populationSize; //population size
  private: int    parameters;     //number of optimized parameters
  private: double lambda;         //lambda
  private: double reproduction;   //probability of reproduction
  private: int    lifeCounter;    //life counter
  private: double powerMut;       //mutation power
  private: bool   evaluation;

  private: double PowerDistribution (const double In, const double outMin, const double outMax, const double power);
  private: void   Sorting           ();
  private: double SeInDiSp          (double In, double InMin, double InMax, double Step);
  private: double RNDfromCI         (double min, double max);
  private: double Scale             (double In, double InMIN, double InMAX, double OutMIN, double OutMAX,  bool revers);
};
//——————————————————————————————————————————————————————————————————————————————

    Для инициализации класса служит метод "Init", который инициализирует параметры алгоритма BFO-GA.

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

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

    //——————————————————————————————————————————————————————————————————————————————
void C_AO_BFO_GA::Init (const int    paramsP,         //number of opt. parameters
                        const int    populationSizeP, //population size
                        const double lambdaP,         //lambda
                        const double reproductionP,   //probability of reproduction
                        const int    lifeCounterP,    //life counter
                        const double powerMutP)       //mutation power
{
  fB = -DBL_MAX;
  evaluation = false;

  parameters      = paramsP;
  populationSize  = populationSizeP;
  lambda          = lambdaP;
  reproduction    = reproductionP;
  lifeCounter     = lifeCounterP;
  powerMut        = powerMutP;

  ArrayResize (rangeMax,  parameters);
  ArrayResize (rangeMin,  parameters);
  ArrayResize (rangeStep, parameters);
  ArrayResize (v,         parameters);

  ArrayResize (ind,       populationSize);
  ArrayResize (val,       populationSize);

  ArrayResize (b,  populationSize);
  ArrayResize (bT, populationSize);

  for (int i = 0; i < populationSize; i++)
  {
    ArrayResize (b [i].c,     parameters);
    ArrayResize (b [i].cLast, parameters);
    ArrayResize (b [i].v,     parameters);
    b [i].f     = -DBL_MAX;
    b [i].fLast = -DBL_MAX;

    ArrayResize (bT [i].c,     parameters);
    ArrayResize (bT [i].cLast, parameters);
    ArrayResize (bT [i].v,     parameters);
  }

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

    Для осуществления хемитаксиса бактерий, их репликации, отбора, наследования признаков и мутации напишем метод "Swimming":

    void Swimming ()
{
}

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

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

    if (!evaluation)
{
  fB = -DBL_MAX;

  for (int s = 0; s < populationSize; s++)
  {
    for (int k = 0; k < parameters; k++)
    {
      b [s].c [k] = RNDfromCI (rangeMin [k], rangeMax [k]);
      b [s].c [k] = SeInDiSp (b [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);

      v [k] = rangeMax [k] - rangeMin [k];

      b [s].v [k] = NewVector (k);

      b [s].f     = -DBL_MAX;
      b [s].fLast = -DBL_MAX;

      b [s].lifeCNT = 0;
    }
  }

  evaluation = true;
  return;
}

    На второй и последующих итерациях сначала выполняется проверка выполнения вероятности репродукции (репликации) бактерий. Если вероятность репродукции исполнена, то происходит следующее:

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

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

    Счетчик жизней бактерий в лучшей половине колонии увеличивается на единицу, а у клонированных - сбрасывается.

    double r = RNDfromCI (0.0, 1.0);

if (r < reproduction)
{
  int st = populationSize / 2;

  //bacterium original--------------------------------------------------------
  for (int s = 0; s < st; s++)
  {
    for (int k = 0; k < parameters; k++)
    {
      b [s].c [k] = b [s].cLast [k] + b [s].v [k];
      b [s].c [k] = SeInDiSp (b [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);
    }
    b [s].lifeCNT++;
  }

  //bacterium clone-----------------------------------------------------------
  for (int s = st; s < populationSize; s++)
  {
    for (int k = 0; k < parameters; k++)
    {
      int i = (int)RNDfromCI (0, st);
      if (i >= st) i = st - 1;

      b [s].c [k] = b [i].cLast [k];

      b [s].c [k] = PowerDistribution (b [s].c [k], rangeMin [k], rangeMax [k], powerMut);
      b [s].c [k] = SeInDiSp (b [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);
    }
    b [s].lifeCNT = 0;
  }
}

    Далее, если вероятность репродукции не выполнена, в цикле для всей популяции:

    for (int s = 0; s < populationSize; s++)

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

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

    if (b [s].lifeCNT >= lifeCounter)
{
  for (int k = 0; k < parameters; k++)
  {
    b [s].v [k] = NewVector (k);

    b [s].c [k] = PowerDistribution (b [s].cLast [k], rangeMin [k], rangeMax [k], powerMut);
    b [s].c [k] = SeInDiSp (b [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);
  }
  b [s].lifeCNT = 0;
}

    Если у бактерии ещё не исчерпан лимит жизней, мы проводим проверку наличия положительного хемотаксиса, то есть на то, движется ли бактерия в сторону увеличения пищевого градиента. Движение бактерии считается верным, если значения приспособленности на двух предыдущих итерациях равны. Почему именно равны? Потому что на следующем этапе, в методе "Evaluation", мы проводим проверку на положительное изменение здоровья бактерий. Если изменения оказываются положительными, то текущее состояние присваивается предыдущему состоянию. Именно поэтому, если состояния здоровья на двух последних итерациях одинаковы, это говорит о верности направления движения бактерии в поисках увеличения пищи. Таким образом, бактерия может двигаться только в сторону ещё большего количества пищи. В противном случае бактерия начинает кувыркаться на месте. Впрочем, это не является проблемой, поскольку рано или поздно застрявшая бактерия либо мутирует в новое состояние, либо унаследует гены более удачливых родителей и их вектор движения.

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

    if (b [s].f == b [s].fLast)
{
  for (int k = 0; k < parameters; k++)
  {
    b [s].c [k] = b [s].cLast [k] + b [s].v [k];
    b [s].c [k] = SeInDiSp (b [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);
  }
  b [s].lifeCNT++;
}

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

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

    for (int k = 0; k < parameters; k++)
{
  b [s].v [k] = NewVector (k);
  b [s].c [k] = b [s].cLast [k] + b [s].v [k];
  b [s].c [k] = SeInDiSp (b [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);
}
b [s].lifeCNT++;

    Для осуществления кувырка бактерий, то есть, изменения вектора движения, служит метод "NewVector", который выполняется для оптимизируемого параметра с индексом "paramInd":

    //——————————————————————————————————————————————————————————————————————————————
double C_AO_BFO_GA::NewVector (int paramInd)
{
  double r = RNDfromCI (-1.0, 1.0);
  return lambda * v [paramInd] * r;
}
//——————————————————————————————————————————————————————————————————————————————
    Для организации процесса конкуренции между бактериями и обновления глобального решения используется метод "Evaluation".

    В начале этого метода каждая бактерия в популяции проходит проверку на наличие положительного хемотаксиса: если текущее значение функции приспособленности "b[s].f" больше предыдущего значения "b[s].fLast", происходит обновление предыдущей приспособленности и обновление предыдущих координат, от которых бактерии будут двигаться в будущем.

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

    После этого происходит обновление глобального решения.

    //——————————————————————————————————————————————————————————————————————————————
void C_AO_BFO_GA::Evaluation ()
{
  for (int s = 0; s < populationSize; s++)
  {
    if (b [s].f > b [s].fLast)
    {
      b [s].fLast = b [s].f;
      ArrayCopy (b [s].cLast, b [s].c, 0, 0, WHOLE_ARRAY);
    }
  }

  Sorting ();

  if (b [0].fLast > fB)
  {
    fB = b [0].fLast;
    ArrayCopy (cB, b [0].cLast, 0, 0, WHOLE_ARRAY);
  }
}
//——————————————————————————————————————————————————————————————————————————————


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

    Распечатка работы гибридного алгоритма BFO-GA на тестовом стенде:

    C_AO_BFO_GA:50;0.01;0.8;50;10.0
    =============================
    5 Hilly's; Func runs: 10000; result: 0.8914957961234459
    25 Hilly's; Func runs: 10000; result: 0.5511088047221568
    500 Hilly's; Func runs: 10000; result: 0.31529201642392934
    =============================
    5 Forest's; Func runs: 10000; result: 0.9698155977381523
    25 Forest's; Func runs: 10000; result: 0.39612322805995287
    500 Forest's; Func runs: 10000; result: 0.06304955092899359
    =============================
    5 Megacity's; Func runs: 10000; result: 0.7266666666666667
    25 Megacity's; Func runs: 10000; result: 0.275
    500 Megacity's; Func runs: 10000; result: 0.035250000000000004
    =============================
    All score: 4.22380 (46.93%)

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

    Hilly

      BFO-GA на тестовой функции Hilly.

    Forest

      BFO-GA на тестовой функции Forest.

    Megacity

      BFO-GA на тестовой функции Megacity.

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

    №

    AO

    Description

    Hilly

    Hilly final

    Forest

    Forest final

    Megacity (discrete)

    Megacity final

    Final result

    % of MAX

    10 p (5 F)

    50 p (25 F)

    1000 p (500 F)

    10 p (5 F)

    50 p (25 F)

    1000 p (500 F)

    10 p (5 F)

    50 p (25 F)

    1000 p (500 F)

    1

    (P+O)ES

    (P+O) evolution strategies

    0,99934

    0,91895

    0,56297

    2,48127

    1,00000

    0,93522

    0,39179

    2,32701

    0,83167

    0,64433

    0,21155

    1,68755

    6,496

    72,18

    2

    SDSm

    stochastic diffusion search M

    0,93066

    0,85445

    0,39476

    2,17988

    0,99983

    0,89244

    0,19619

    2,08846

    0,72333

    0,61100

    0,10670

    1,44103

    5,709

    63,44

    3

    SIA

    simulated isotropic annealing

    0,95784

    0,84264

    0,41465

    2,21513

    0,98239

    0,79586

    0,20507

    1,98332

    0,68667

    0,49300

    0,09053

    1,27020

    5,469

    60,76

    4

    DE

    differential evolution

    0,95044

    0,61674

    0,30308

    1,87026

    0,95317

    0,78896

    0,16652

    1,90865

    0,78667

    0,36033

    0,02953

    1,17653

    4,955

    55,06

    5

    HS

    harmony search

    0,86509

    0,68782

    0,32527

    1,87818

    0,99999

    0,68002

    0,09590

    1,77592

    0,62000

    0,42267

    0,05458

    1,09725

    4,751

    52,79

    6

    SSG

    saplings sowing and growing

    0,77839

    0,64925

    0,39543

    1,82308

    0,85973

    0,62467

    0,17429

    1,65869

    0,64667

    0,44133

    0,10598

    1,19398

    4,676

    51,95

    7

    (PO)ES

    (PO) evolution strategies

    0,79025

    0,62647

    0,42935

    1,84606

    0,87616

    0,60943

    0,19591

    1,68151

    0,59000

    0,37933

    0,11322

    1,08255

    4,610

    51,22

    8

    ACOm

    ant colony optimization M

    0,88190

    0,66127

    0,30377

    1,84693

    0,85873

    0,58680

    0,15051

    1,59604

    0,59667

    0,37333

    0,02472

    0,99472

    4,438

    49,31

    9

    BFO-GA

    bacterial foraging optimization - ga

    0,89150

    0,55111

    0,31529

    1,75790

    0,96982

    0,39612

    0,06305

    1,42899

    0,72667

    0,27500

    0,03525

    1,03692

    4,224

    46,93

    10

    MEC

    mind evolutionary computation

    0,69533

    0,53376

    0,32661

    1,55569

    0,72464

    0,33036

    0,07198

    1,12698

    0,52500

    0,22000

    0,04198

    0,78698

    3,470

    38,55

    11

    IWO

    invasive weed optimization

    0,72679

    0,52256

    0,33123

    1,58058

    0,70756

    0,33955

    0,07484

    1,12196

    0,42333

    0,23067

    0,04617

    0,70017

    3,403

    37,81

    12

    Micro-AIS

    micro artificial immune system

    0,79547

    0,51922

    0,30861

    1,62330

    0,72956

    0,36879

    0,09398

    1,19233

    0,37667

    0,15867

    0,02802

    0,56335

    3,379

    37,54

    13

    COAm

    cuckoo optimization algorithm M

    0,75820

    0,48652

    0,31369

    1,55841

    0,74054

    0,28051

    0,05599

    1,07704

    0,50500

    0,17467

    0,03380

    0,71347

    3,349

    37,21

    14

    SDOm

    spiral dynamics optimization M

    0,74601

    0,44623

    0,29687

    1,48912

    0,70204

    0,34678

    0,10944

    1,15826

    0,42833

    0,16767

    0,03663

    0,63263

    3,280

    36,44

    15

    NMm

    Nelder-Mead method M

    0,73807

    0,50598

    0,31342

    1,55747

    0,63674

    0,28302

    0,08221

    1,00197

    0,44667

    0,18667

    0,04028

    0,67362

    3,233

    35,92

    16

    FAm

    firefly algorithm M

    0,58634

    0,47228

    0,32276

    1,38138

    0,68467

    0,37439

    0,10908

    1,16814

    0,28667

    0,16467

    0,04722

    0,49855

    3,048

    33,87

    17

    GSA

    gravitational search algorithm

    0,64757

    0,49197

    0,30062

    1,44016

    0,53962

    0,36353

    0,09945

    1,00260

    0,32667

    0,12200

    0,01917

    0,46783

    2,911

    32,34

    18

    BFO

    bacterial foraging optimization

    0,61171

    0,43270

    0,31318

    1,35759

    0,54410

    0,21511

    0,05676

    0,81597

    0,42167

    0,13800

    0,03195

    0,59162

    2,765

    30,72

    19

    ABC

    artificial bee colony

    0,63377

    0,42402

    0,30892

    1,36671

    0,55103

    0,21874

    0,05623

    0,82600

    0,34000

    0,14200

    0,03102

    0,51302

    2,706

    30,06

    20

    BA

    bat algorithm

    0,59761

    0,45911

    0,35242

    1,40915

    0,40321

    0,19313

    0,07175

    0,66810

    0,21000

    0,10100

    0,03517

    0,34617

    2,423

    26,93

    21

    SA

    simulated annealing

    0,55787

    0,42177

    0,31549

    1,29513

    0,34998

    0,15259

    0,05023

    0,55280

    0,31167

    0,10033

    0,02883

    0,44083

    2,289

    25,43

    22

    IWDm

    intelligent water drops M

    0,54501

    0,37897

    0,30124

    1,22522

    0,46104

    0,14704

    0,04369

    0,65177

    0,25833

    0,09700

    0,02308

    0,37842

    2,255

    25,06

    23

    PSO

    particle swarm optimisation

    0,59726

    0,36923

    0,29928

    1,26577

    0,37237

    0,16324

    0,07010

    0,60572

    0,25667

    0,08000

    0,02157

    0,35823

    2,230

    24,77

    24

    MA

    monkey algorithm

    0,59107

    0,42681

    0,31816

    1,33604

    0,31138

    0,14069

    0,06612

    0,51819

    0,22833

    0,08567

    0,02790

    0,34190

    2,196

    24,40

    25

    SFL

    shuffled frog-leaping

    0,53925

    0,35816

    0,29809

    1,19551

    0,37141

    0,11427

    0,04051

    0,52618

    0,27167

    0,08667

    0,02402

    0,38235

    2,104

    23,38

    26

    FSS

    fish school search

    0,55669

    0,39992

    0,31172

    1,26833

    0,31009

    0,11889

    0,04569

    0,47467

    0,21167

    0,07633

    0,02488

    0,31288

    2,056

    22,84

    27

    RND

    random

    0,52033

    0,36068

    0,30133

    1,18234

    0,31335

    0,11787

    0,04354

    0,47476

    0,25333

    0,07933

    0,02382

    0,35648

    2,014

    22,37

    28

    GWO

    grey wolf optimizer

    0,59169

    0,36561

    0,29595

    1,25326

    0,24499

    0,09047

    0,03612

    0,37158

    0,27667

    0,08567

    0,02170

    0,38403

    2,009

    22,32

    29

    CSS

    charged system search

    0,44252

    0,35454

    0,35201

    1,14907

    0,24140

    0,11345

    0,06814

    0,42299

    0,18333

    0,06300

    0,02322

    0,26955

    1,842

    20,46

    30

    EM

    electroMagnetism-like algorithm

    0,46250

    0,34594

    0,32285

    1,13129

    0,21245

    0,09783

    0,10057

    0,41085

    0,15667

    0,06033

    0,02712

    0,24412

    1,786

    19,85


    Выводы

    Мы видим явные улучшения в результатах BFO-GA по сравнению с оригинальным алгоритмом BFO, что обусловлено использованием операторов генетического алгоритма: селекции, мутации и наследования. BFO ранее не имел механизмов выхода из локальных экстремумов, и теперь эта проблема отсутствует. Алгоритм представляет огромные возможности для экспериментирования, комбинирования порядка компонентов стратегии бактериального поиска и операторов ГА, многие из которых я еще не испробовал.

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

    rating table

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

    chart

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

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


    Плюсы и минусы гибридного алгоритма оптимизации бактериального поиска с генетическим алгоритмом (BFO-GA):

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

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