Гибридизация популяционных алгоритмов. Последовательная и параллельная схема

Andrey Dik | 14 марта, 2024

Содержание:

1. Введение
2. Эксперимент с GWO и COA
3. Эксперимент с ESG и SDSm
4. Выводы

1. Введение

Рассмотрим три основные варианта гибридизации алгоритмов оптимизации:

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

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

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

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

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

2. Эксперимент с GWO и COA

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

Алгоритм оптимизации "Серых волков" (Grey Wolf Optimizer - GWO) - это метаэвристический стохастический алгоритм, основанный на имитации загонной охоты стаи серых волков.
Основные особенности алгоритма GWO:

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

Алгоритм оптимизации поиска с кукушкой (Cuckoo Optimization Algorithm — COAm) - это один из новейших эвристических алгоритмов, вдохновленных природой. Он основан на паразитизме некоторых видов кукушек.
Основные особенности алгоритма COAm:

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

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

Рисунок 1. Гибридный алгоритм, GWO+COA

Давайте взглянем на предположительный ход событий:

1. Начало:
   - Начинаем с 10 000 итераций, что является ограниченным ресурсом, поэтому каждая итерация критически важна для достижения оптимального решения.
2. Шаг 1 (0—5000 итераций):
   - Делим общее количество итераций пополам и начинаем с алгоритма GWO.
   - Благодаря быстрому распространению волков по пространству поиска, они быстро сходятся к потенциальному глобальному экстремуму к середине периода.
3. Шаг 2 (5000 — 10000 итераций):
   - После первых 5000 итераций, перенимаем положение волков на положение в этих точках кукушек.
   - Поиск кукушки с полетом Леви получает эстафетную палочку для дальнейшего уточнения экстремума.
4. Результат:
   - Ожидается, что в результате данной комбинации алгоритмов GWO и поиска кукушки с полетом Леви, мы сможем достичь более точного и устойчивого глобального экстремума в ограниченном количестве итераций. 

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

Объявим класс "C_AO_GWO_COAm", который является наследником класса "C_AO". В конструкторе класса устанавливаются значения по умолчанию для параметров оптимизации, таких как размер популяции "popSize" и соотношение "ratio" между алгоритмами GWO и COAm. Этот класс позволит использовать последовательную работу двух алгоритмов, при этом обращение с ним останется таким же, как обычно и позволит использовать наш стенд без изменений.

В классе также определены методы для установки параметров "SetParams", инициализации оптимизации "Init", перемещения "Moving" и обновления глобального решения "Revision", и вставки значений координат в агенты "Injection".

Важные переменные в классе включают "ratio" (соотношение между GWO и COAm), а также объекты классов "C_AO_GWO" и "C_AO_COAm" для реализации алгоритмов Grey Wolf Optimizer и Cuckoo Optimization Algorithm соответственно.

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

//——————————————————————————————————————————————————————————————————————————————
class C_AO_GWO_COAm : public C_AO
{
  public: //--------------------------------------------------------------------
  ~C_AO_GWO_COAm () { }
  C_AO_GWO_COAm ()
  {
    ao_name = "GWO_COAm";
    ao_desc = "Grey Wolf Optimizer and Cuckoo Optimization Algorithm M";

    popSize = 50;    //population size
    ratio   = 0.5;   //the ratio of GWO and COAm

    ArrayResize (params, 2);

    params [0].name = "popSize"; params [0].val = popSize;
    params [1].name = "ratio";   params [1].val = ratio;
  }

  void SetParams ()
  {
    popSize = (int)params [0].val;
    ratio   = params      [1].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  ();
  void Injection (const int popPos, const int coordPos, const double value);

  //----------------------------------------------------------------------------
  double ratio;  //the ratio of GWO and COAm

  private: //-------------------------------------------------------------------
  C_AO_GWO  AO1;
  C_AO_COAm AO2;

  int epochCount;
  int epochNow;

  int epochGWO;
  int epochCOAm;
};
//——————————————————————————————————————————————————————————————————————————————

Метод "Init" в классе "C_AO_GWO_COAm" используется для инициализации процесса оптимизации. Здесь происходит установка начальных значений, создание агентов, установка параметров инициализации для алгоритмов GWO и COAm.

1. Проверяется успешность стандартной инициализации с помощью метода "StandardInit", который использует переданные параметры для установки минимального и максимального диапазона поиска.
2. Вычисляются количество эпох для каждого из алгоритмов GWO и COAm на основе соотношения "ratio" и общего числа эпох "epochCount".
3. Устанавливаются параметры для алгоритмов GWO и COAm, инициализируются с помощью методов "SetParams" и "Init".
4. Метод возвращает "true", если инициализация прошла успешно.

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

//——————————————————————————————————————————————————————————————————————————————
bool C_AO_GWO_COAm::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;

  //----------------------------------------------------------------------------
  epochCount   = epochsP;
  epochNow     = 0;

  epochGWO  = int(epochCount *ratio);
  epochCOAm = epochCount - epochGWO;

  AO1.params [0].val = popSize;
  AO2.params [0].val = popSize;

  AO1.SetParams ();
  AO2.SetParams ();

  AO1.Init (rangeMinP, rangeMaxP, rangeStepP, epochGWO);
  AO2.Init (rangeMinP, rangeMaxP, rangeStepP, epochCOAm);

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

В коде метода "Moving" класса "C_AO_GWO_COAm" происходит увеличение значения переменной "epochNow" на единицу. Счетчик "epochNow" используется для определения этапов, на которых соответственно работает сначала GWO, а затем COAm.

Если "epochNow" меньше "epochGWO", то вызывается метод "Moving" для объекта "AO1" (GWO), после чего происходит копирование элементов массива агентов "AO1.a" в массив агентов "a".

В случае, если "epochNow" равно "epochGWO", вызывается метод "Moving" для объекта "AO2" (COAm), а затем происходит внедрение значений из массива "AO1.a" в соответствующие элементы массива "AO2.a", то-есть, то самое превращение волков в кукушки. Наконец, все элементы массива "AO2.a" копируются в массив "a", чтобы обращаться к агентам "а" в исполняемой программе.

Этот метод обеспечивает последовательное перемещение агентов на каждой эпохе оптимизации в соответствии с выбранными алгоритмами GWO и COAm.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_GWO_COAm::Moving ()
{
  epochNow++;

  if (epochNow < epochGWO)
  {
    AO1.Moving ();
    for (int i = 0; i < popSize; i++)
    {
      a [i] = AO1.a [i];
    }
    return;
  }

  AO2.Moving ();

  if (epochNow == epochGWO)
  {
    for (int i = 0; i < popSize; i++)
    {
      for (int c = 0; c < coords; c++)
      {
        AO2.Injection (i, c, AO1.a [i].c [c]);
      }
    }
  }

  for (int i = 0; i < popSize; i++)
  {
    a [i] = AO2.a [i];
  }
}
//——————————————————————————————————————————————————————————————————————————————

Метод "Revision" выполняет передачу рассчитанного значения приспособленности агентов соответствующим агентам алгоритмов.

В зависимости от значения переменных "epochNow" и "epochGWO" выполняются действия для алгоритмов GWO или COAm:

1. Копирование значения приспособленности агентам.
2. Выполнение метода "Revision".
3. Выполнение обновления глобального решения.
   

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

//——————————————————————————————————————————————————————————————————————————————
void C_AO_GWO_COAm::Revision ()
{
  if (epochNow < epochGWO)
  {
    for (int i = 0; i < popSize; i++) AO1.a [i].f = a [i].f;

    AO1.Revision ();

    if (AO1.fB > fB)
    {
      fB = AO1.fB;
      ArrayCopy (cB, AO1.cB, 0, 0, WHOLE_ARRAY);
    }
  }
  else
  {
    for (int i = 0; i < popSize; i++) AO2.a [i].f = a [i].f;

    AO2.Revision ();

    if (AO2.fB > fB)
    {
      fB = AO2.fB;
      ArrayCopy (cB, AO2.cB, 0, 0, WHOLE_ARRAY);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

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

GWO-COAm на тестовой функции Hilly

GWO-COAm на тестовой функции Forest

GWO-COAm на тестовой функции Megacity

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

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

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

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

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

В отличие от последовательной схемы работы в параллельной схеме мы запускаем методы "Moving" сразу у обоих алгоритмов. После этого копируем агентов этих алгоритмов в агенты объединённого класса для последующей отправки на расчет фитнес-функции. Таким образом, данный метод объединяет данные из двух объектов "AO1" и "AO2" в массив текущего объекта "a".

//——————————————————————————————————————————————————————————————————————————————
void C_AO_GWO_COAm::Moving ()
{
  AO1.Moving ();
  AO2.Moving ();

  int cnt = 0;
  for (int i = 0; i < popSize / 2; i++)
  {
    a [cnt] = AO1.a [i];
    cnt++;
  }

  for (int i = 0; i < popSize / 2; i++)
  {
    a [cnt] = AO2.a [i];
    cnt++;
  }
}
//——————————————————————————————————————————————————————————————————————————————

Отличия метода "Moving" для параллельной схемы работы от последовательной заключаются в следующем: после передачи значений приспособленности агентам объектов "AO1" и "AO2", выполнении их методов "Revision" и обновлении глобального решения, происходит копирование по два агента из одного алгоритма в другой. Это означает, что происходит обмен двумя лучшими агентами между алгоритмами, что способствует обогащению обоих алгоритмов лучшими характеристиками друг друга и может улучшить их эффективность в решении задач. Такой подход позволяет совместно использовать лучшие решения, достигнутые каждым из алгоритмов.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_GWO_COAm::Revision ()
{
  int cnt = 0;

  for (int i = 0; i < popSize / 2; i++)
  {
    AO1.a [i].f = a [cnt].f;
    cnt++;

    if (AO1.a [i].f > fB)
    {
      fB = AO1.a [i].f;
      ArrayCopy (cB, AO1.a [i].c, 0, 0, WHOLE_ARRAY);
    }
  }

  for (int i = 0; i < popSize / 2; i++)
  {
    AO2.a [i].f = a [cnt].f;
    cnt++;

    if (AO2.a [i].f > fB)
    {
      fB = AO2.a [i].f;
      ArrayCopy (cB, AO2.a [i].c, 0, 0, WHOLE_ARRAY);
    }
  }

  AO1.Revision ();
  AO2.Revision ();
  
  S_AO_Agent temp [];
  ArrayResize (temp, popSize / 2);
  
  for (int i = 0; i < 2; i++) temp [i] = AO1.a [i]; 

  for (int i = 0; i < 2; i++)
  {
    for (int c = 0; c < coords; c++)
    {
      AO1.Injection (i, coords - 1, AO2.a [i].c [c]);
      AO2.Injection (i, coords - 1, temp  [i].c [c]);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

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

К сожалению, улучшения показателей работы не наблюдаются.

3. Эксперимент с ESG и SDSm

В рассмотренных выше вариантах гибридизации GWO и COAm использовались алгоритмы из разных "весовых категорий". Возможно для этих целей необходимо использовать близкие по возможностям алгоритмы, что бы они действительно друг друга дополняли. Поэтому проведём ещё два эксперимента по последовательной и параллельной схемам. Для этого будем использовать алгоритмы ESG и SDSm.

Объединение этих двух алгоритмов в гибрид, может создать уникальное сочетание случайности и социальной динамики.

Алгоритм стохастического диффузионного поиска (Stochastic Diffusion Search, SDSm) — это популяционный алгоритм оптимизации.

Основные особенности алгоритма:

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

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

Алгоритм эволюции социальных групп (ESG) — это многопопуляционный алгоритм оптимизации.

Основные особенности алгоритма:

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

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

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

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

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

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

4. Выводы

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

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

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

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

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

Рейтинговая таблица популяционных алгоритмов.

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

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

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

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

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