preview
Алгоритм циклического партеногенеза — Cyclic Parthenogenesis Algorithm (CPA)

Алгоритм циклического партеногенеза — Cyclic Parthenogenesis Algorithm (CPA)

MetaTrader 5Тестер | 23 января 2025, 14:08
301 0
Andrey Dik
Andrey Dik

Содержание

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


Введение

Оптимизационные алгоритмы, инспирированные природными явлениями, продолжают играть важную роль в решении сложных задач оптимизации. Особый интерес представляют алгоритмы, основанные на поведении социальных насекомых, таких как муравьи, пчелы и тли. В предыдущих статьях мы уже рассматривали ряд из них ACOmABHA. В данной статье представлен новый метаэвристический алгоритм оптимизации — Алгоритм Циклического Партеногенеза (Cyclic Parthenogenesis Algorithm, CPA), который имитирует уникальную репродуктивную стратегию тлей (aphids).

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

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

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


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

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

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

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

    CPA

    Рисунок 1. Схема работы алгоритма CPA, основные формулы

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

    cpa algorithm diagram

    Рисунок 2. Колонии тлей и их взаимодействие в алгоритме CPA

    Когда мы немного разобрались с описанием алгоритма, перейдем к написанию псевдокода:

    Инициализация:
    Создать популяцию размером Na особей
    Разделить популяцию на Nc колоний

    В каждой колонии:
    Определить количество особей женского пола (Fr * Nm)
    Определить количество особей мужского пола (остальные)

    Задать начальные параметры:
    alpha1 (коэффициент партеногенеза)
    alpha2 (коэффициент спаривания)
    Pf (вероятность перелета)

    Основной цикл (для каждой эпохи):
    Для каждой колонии:
    Для особей женского пола:

    Обновить позицию используя партеногенез:
    новая_позиция = текущая_позиция + alpha1 * k * N(0,1) * (max_range - min_range)
    где k = (total_epochs - current_epoch) / total_epochs
    N(0,1) - нормальное распределение

    Для особей мужского пола:
    Выбрать случайную особь женского пола из той же колонии
    Обновить позицию через спаривание:
    новая_позиция = текущая_позиция + alpha2 * random[0,1] * (позиция_самки - текущая_позиция)

    Ревизия позиций:
    Обновить лучшее найденное решение
    Сохранить текущие позиции
    Отсортировать особей в каждой колонии по значению целевой функции

    Миграция (с вероятностью Pf):
    Выбрать две случайные колонии
    Сравнить их лучшие решения
    Переместить лучшее решение в худшую колонию
    Пересортировать особей в колонии

    Все подготовлено к написанию кода алгоритма, идем дальше. Напишем класс "C_AO_CPA", который наследуется от класса "C_AO". Этот класс реализует весь алгоритм, краткое описание его компонентов:

    Конструктор C_AO_CPA:

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

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

    Методы Init, Moving и Revision:

    • Init — предназначен для инициализации алгоритма с заданными диапазонами и количеством эпох.
    • Moving  и  Revision —  методы реализуют логику перемещения и пересмотра в рамках алгоритма.

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

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

    //——————————————————————————————————————————————————————————————————————————————
    // Класс реализующий Алгоритм Циклического Партеногенеза (CPA)
    // Наследуется от базового класса оптимизации
    class C_AO_CPA : public C_AO
    {
      public:
      C_AO_CPA (void)
      {
        ao_name = "CPA";
        ao_desc = "Cyclic Parthenogenesis Algorithm";
        ao_link = "https://www.mql5.com/ru/articles/16877";
    
        popSize = 50;       // общий размер популяции Na
    
        Nc      = 10;       // количество колоний
        Fr      = 0.2;      // соотношение особей женского пола
        Pf      = 0.9;      // вероятность перелета между колониями
        alpha1  = 0.3;      // коэффициент масштабирования для партеногенеза
        alpha2  = 0.9;      // коэффициент масштабирования для спаривания
    
        ArrayResize (params, 6);
    
        // Установка параметров алгоритма
        params [0].name = "popSize";     params [0].val = popSize;
        params [1].name = "Nc";          params [1].val = Nc;
        params [2].name = "Fr";          params [2].val = Fr;
        params [3].name = "Pf";          params [3].val = Pf;
        params [4].name = "alpha1_init"; params [4].val = alpha1;
        params [5].name = "alpha2_init"; params [5].val = alpha2;
      }
    
      void SetParams ()
      {
        popSize = (int)params [0].val;
    
        Nc      = (int)params [1].val;
        Fr      = params      [2].val;
        Pf      = params      [3].val;
        alpha1  = params      [4].val;
        alpha2  = params      [5].val;
      }
    
      bool Init (const double &rangeMinP  [], // минимальный диапазон поиска
                 const double &rangeMaxP  [], // максимальный диапазон поиска
                 const double &rangeStepP [], // шаг поиска
                 const int     epochsP = 0);  // количество эпох
    
      void Moving   ();         // функция перемещения особей
      void Revision ();         // функция пересмотра и обновления позиций
    
      //----------------------------------------------------------------------------
      int    Nc;                // количество колоний
      double Fr;                // соотношение особей женского пола
      double Pf;                // вероятность перелета между колониями
    
      private: //-------------------------------------------------------------------
      int    epochs;            // общее количество эпох
      int    epochNow;          // текущая эпоха
      int    Nm;                // количество особей в каждой колонии
      double alpha1;            // коэффициент масштабирования для партеногенеза
      double alpha2;            // коэффициент масштабирования для спаривания
      int    fNumber;           // количество особей женского пола в колонии
      int    mNumber;           // количество особей мужского пола в колонии
    
      S_AO_Agent aT [];         // временная колония для сортировки
      void SortFromTo (S_AO_Agent &p [], S_AO_Agent &pTemp [], int from, int count); // функция сортировки агентов
    };
    //——————————————————————————————————————————————————————————————————————————————

    Реализация метода "Init" класса "C_AO_CPA", его функциональность:

    Параметры метода:

    • rangeMinP, rangeMaxP, rangeStepP - массивы, определяющие минимальные и максимальные значения диапазона, а также шаг поиска.
    • epochsP — количество эпох (по умолчанию 0).
    Логика метода:
    • Метод сначала вызывает "StandardInit", чтобы выполнить стандартную инициализацию с переданными диапазонами. Если инициализация не удалась, метод возвращает "false".
    • Устанавливает количество эпох (epochs) и текущую эпоху (epochNow).
    • Вычисляет количество членов в колонии (Nm) на основе размера популяции и количества колоний.
    • Определяет количество самок (fNumber) в колонии, гарантируя, что оно не меньше 1. Количество самцов (mNumber) вычисляется как разница между общим количеством членов и количеством самок.
    • Резервирует массив "aT" для хранения временных агентов колонии.
    Возвращаемое значение:
    • Метод возвращает "true", если инициализация прошла успешно.

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

      //——————————————————————————————————————————————————————————————————————————————
      // Инициализация алгоритма с заданными параметрами поиска
      bool C_AO_CPA::Init (const double &rangeMinP  [],
                           const double &rangeMaxP  [],
                           const double &rangeStepP [],
                           const int     epochsP = 0)
      {
        if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false;
      
        //----------------------------------------------------------------------------
        epochs   = epochsP;
        epochNow = 0;
        // Вычисление размера колонии и количества особей каждого пола
        Nm       = popSize / Nc;
        fNumber  = int(Nm * Fr); if (fNumber < 1) fNumber = 1;
        mNumber  = Nm - fNumber;
      
        ArrayResize (aT, Nm);
      
        return true;
      }
      //——————————————————————————————————————————————————————————————————————————————

      Метод "Moving" класса "C_AO_CPA" осуществляет перемещение агентов в пространстве решений, адаптируя их координаты на основе определённых правил и случайных факторов. Давайте разберем поэтапно:

      Увеличение эпохи. Метод начинает с увеличения текущего показателя эпохи (epochNow), что говорит о том, что вызывался очередной шаг в процессе оптимизации или эволюции.

      Первый этап (если ревизия не требуется) - если поле "revision" установлено в "false", выполняется инициализация координат каждого агента в популяции (popSize):

      • Каждый агент (a[i]) получает новые координаты в каждом измерении (coords) с использованием функции "RNDfromCI", которая генерирует случайные значения в заданном диапазоне [rangeMin[c], rangeMax[c]].
      • Затем координация модифицируется с помощью функции "SeInDiSp", которая обеспечивает коррекцию значений в соответствии с шагом дискретизации (rangeStep[c]).
      • Устанавливается флаг "revision" в "true", и метод завершает выполнение.
        Второй этап (если ревизия требуется) — если revision установлено в "true", выполняется адаптация координат агентов на основе их предыдущих координат и некоторой случайной компоненты:
        • Переменная "k" рассчитывается как отношение оставшегося количества эпох к общему количеству эпох. Это позволяет постепенно сужать размах передвижения агентов по мере приближения завершения оптимизации.
        • Перебираются колонии (col) и функции (fNumber), чтобы обновить координаты каждого агента для первых "fNumber" агентов в колонии это обновление происходит на основе их предыдущих координат (cP), с добавлением случайного значения, сгенерированного с помощью нормального распределения (GaussDistribution). Это значение масштабируется в диапазоне между "rangeMin" и "rangeMax".
        • Для остальных агентов (m от fNumber до Nm) также обновляются координаты, но теперь используются случайно выбранные координаты одного из лучших агентов в той же колонии. Случайные значения добавляются к координатам каждого агента с учетом параметра "alpha2".
        Логика поведения:
        • Общая цель этого метода — переместить агентов в пространстве решений, основываясь на их предыдущем положении и вливая элемент случайности для изучения района, чтобы улучшить возможность нахождения глобального оптимума.
        • Параметры, такие как "alpha1" и "alpha2", помогают контролировать уровень адаптации и случайности.

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

          //——————————————————————————————————————————————————————————————————————————————
          // Основная функция перемещения особей в пространстве поиска
          void C_AO_CPA::Moving ()
          {
            epochNow++;
            //----------------------------------------------------------------------------
            // Начальная случайная инициализация позиций, если это первая итерация
            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 k    = (epochs - epochNow)/(double)epochs;
            int    ind  = 0;
            int    indF = 0;
          
            // Обработка каждой колонии
            for (int col = 0; col < Nc; col++)
            {
              // Обновление позиций особей женского пола (партеногенез)
              for (int f = 0; f < fNumber; f++)
              {
                ind = col * Nm + f;
          
                for (int c = 0; c < coords; c++)
                {
                  // Партеногенетическое обновление позиции с использованием нормального распределения
                  a [ind].c [c] = a [ind].cP [c] + alpha1 * k * u.GaussDistribution (0.0, -1.0, 1.0, 8) * (rangeMax [c] - rangeMin [c]);
                }
              }
          
              // Обновление позиций особей мужского пола (спаривание)
              for (int m = fNumber; m < Nm; m++)
              {
                ind = col * Nm + m;
          
                // Выбор случайной особи женского пола для спаривания
                indF = u.RNDintInRange (ind, col * Nm + fNumber - 1);
          
                for (int c = 0; c < coords; c++)
                {
                  // Обновление позиции на основе выбранной особи женского пола
                  a [ind].c [c] = a [ind].cP [c] + alpha2 * u.RNDprobab () * (a [indF].cP [c] - a [ind].cP [c]);
                }
              }
            }
          }
          //——————————————————————————————————————————————————————————————————————————————

          Метод "Revision" класса "C_AO_CPA" отвечает за обновление состояния агентов в популяции на основе их значений функции "f", рассмотрим подробнее:

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

          Поиск лучшего агента — в первом цикле "for" происходит перебор всех агентов в популяции (popSize) и если значение функции "f" текущего агента (a[i].f) больше, чем текущее лучшее значение "fB", то:

          • Обновляется "fB"  на значение "a[i].f".
          • Сохраняется индекс лучшего агента в переменной "ind".
          • После завершения цикла, если был найден агент с лучшим значением (ind != -1), его координаты (c) копируются в массив "cB".

          Копирование текущих координат. Во втором цикле "for" копируются текущие координат (c) каждого агента в их предыдущие координаты (cP). Это позволяет сохранить предыдущее состояние агентов для дальнейшего анализа.

          Сортировка агентов. Третий цикл "for" проходит по всем колониям (Nc), и для каждой колонии вызывается метод "SortFromTo", который сортирует агентов в пределах колонии по их значениям функции "f". Индекс для сортировки рассчитывается как (ind = col * Nm).

          Вероятностное обновление. Метод проверяет, если случайное значение, сгенерированное функцией "u.RNDprobab()", меньше порогового значения "Pf":

          • Если условие выполняется, выбираются два случайных индекса колоний (indCol_1  и  indCol_2), при этом гарантируется, что они не равны друг другу.
          • Сравниваются значения функции "f" агентов в этих колониях. Если значение функции в первой колонии меньше, чем во второй, индексы меняются местами.
          • Затем координаты первого агента в первой колонии копируются в координаты последнего агента во второй колонии.
          • После этого снова вызывается "SortFromTo" для обновления порядка агентов во второй колонии.

          Общая логика:

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

          //——————————————————————————————————————————————————————————————————————————————
          // Функция пересмотра позиций и обмена информацией между колониями
          void C_AO_CPA::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++)
            {
              ArrayCopy (a [i].cP, a [i].c, 0, 0, WHOLE_ARRAY);
            }
          
            // Сортировка особей в каждой колонии по значению целевой функции
            for (int col = 0; col < Nc; col++)
            {
              ind = col * Nm;
              SortFromTo (a, aT, ind, Nm);
            }
          
            // Механизм перелета (миграции) между колониями
            if (u.RNDprobab () < Pf)
            {
              int indCol_1 = 0;
              int indCol_2 = 0;
          
              // Выбор двух случайных различных колоний
              indCol_1 = u.RNDminusOne (Nc);
              do indCol_2 = u.RNDminusOne (Nc);
              while (indCol_1 == indCol_2);
          
              // Обеспечение, чтобы лучшее решение было в первой колонии
              if (a [indCol_1 * Nm].f < a [indCol_2 * Nm].f)
              {
                int temp = indCol_1;
                indCol_1 = indCol_2;
                indCol_2 = temp;
              }
          
              // Копирование лучшего решения в худшую колонию
              ArrayCopy (a [indCol_2 * Nm + Nm - 1].cP, a [indCol_1 * Nm].cP, 0, 0, WHOLE_ARRAY);
          
              // Пересортировка колонии после миграции
              SortFromTo (a, aT, indCol_2 * Nm, Nm);
            }
          }
          //——————————————————————————————————————————————————————————————————————————————

          Метод "SortFromTo" класса "C_AO_CPA" предназначен для сортировки массива агентов на основе их значений функции "f", разберем подробнее:

          Инициализация переменных:

          • Метод принимает три параметра — массив агентов "p", временный массив "pTemp", индекс начала сортировки "from"  и количество элементов для сортировки "count".
          • Переменные "cnt", "t0", и "t1" используются для отслеживания количества обменов и временного хранения значений.
          • Массивы "ind" и "val" создаются для хранения индексов и значений функции приспособленности "f"  соответственно.

          Заполнение массивов индексов и значений. В первом цикле "for" заполняются массивы  "ind" и "val":

          • ind[i] получает индекс агента в исходном массиве, начиная с "from".
          • val[i] получает значение функции "f" для соответствующего агента.

          Сортировка. Основной цикл "while" выполняется до тех пор, пока есть обмены (т.е.  cnt > 0). Внутренний цикл "for"  проходит по массиву "val" и сравнивает соседние значения:

          • Если текущее меньше следующего (val[i] < val[i + 1]), происходит обмен индексов в массиве "ind"  и значений в массиве "val" .
          • Увеличивается счетчик "cnt", чтобы показать, что произошел обмен.
          • Этот процесс продолжается до тех пор, пока не будет выполнена полная итерация без обменов.

          Копирование отсортированных значений:

          • После завершения сортировки, в первом цикле "for"  происходит копирование отсортированных агентов из временного массива "pTemp"  обратно в исходный массив "p", начиная с индекса "from".
          • Второй цикл "for" обновляет оригинальный массив "p", заменяя его отсортированными значениями.
          //——————————————————————————————————————————————————————————————————————————————
          // Вспомогательная функция сортировки агентов по значению целевой функции
          void C_AO_CPA::SortFromTo (S_AO_Agent &p [], S_AO_Agent &pTemp [], int from, int count)
          {
            int    cnt = 1;
            int    t0  = 0;
            double t1  = 0.0;
            int    ind [];
            double val [];
            ArrayResize (ind, count);
            ArrayResize (val, count);
          
            // Копирование значений для сортировки
            for (int i = 0; i < count; i++)
            {
              ind [i] = i + from;
              val [i] = p [i + from].f;
            }
          
            // Сортировка пузырьком по убыванию
            while (cnt > 0)
            {
              cnt = 0;
              for (int i = 0; i < count - 1; i++)
              {
                if (val [i] < val [i + 1])
                {
                  // Обмен индексов
                  t0 = ind [i + 1];
                  ind [i + 1] = ind [i];
                  ind [i] = t0;
          
                  // Обмен значений
                  t1 = val [i + 1];
                  val [i + 1] = val [i];
                  val [i] = t1;
          
                  cnt++;
                }
              }
            }
          
            // Применение результатов сортировки
            for (int i = 0;    i < count; i++)        pTemp [i] = p [ind [i]];
            for (int i = from; i < from + count; i++) p     [i] = pTemp  [i - from];
          }
          //——————————————————————————————————————————————————————————————————————————————

          После написания и подробного разбора кода алгоритма, перейдем к результатам тестирования алгоритма CPA.


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

          При реализации интересной и своеобразной логики алгоритма, я даже не допускал мысли, что он не попадет в первые строки рейтинговой таблицы, и было некоторое разочарование при детальном рассмотрении результатов тестирования алгоритма CPA. По итогам тестирования алгоритм набрал самое большее 34,76 % от максимально возможного результата.

          CPA|Cyclic Parthenogenesis Algorithm|50.0|10.0|0.2|0.9|0.3|0.9|
          =============================
          5 Hilly's; Func runs: 10000; result: 0.7166412833856777
          25 Hilly's; Func runs: 10000; result: 0.4001377868508138
          500 Hilly's; Func runs: 10000; result: 0.25502012607456315
          =============================
          5 Forest's; Func runs: 10000; result: 0.6217765628284961
          25 Forest's; Func runs: 10000; result: 0.3365148812759322
          500 Forest's; Func runs: 10000; result: 0.192638189788532
          =============================
          5 Megacity's; Func runs: 10000; result: 0.34307692307692306
          25 Megacity's; Func runs: 10000; result: 0.16769230769230772
          500 Megacity's; Func runs: 10000; result: 0.09455384615384692
          =============================
          All score: 3.12805 (34.76%)

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

          Hilly

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

          Forest

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

          Megacity

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

          Алгоритм CPA после тестирования расположился на 44-м месте в рейтинговой таблице и вошел в группу из 45 лучших популяционных алгоритмов оптимизации.

          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 ANS across neighbourhood search 0,94948 0,84776 0,43857 2,23581 1,00000 0,92334 0,39988 2,32323 0,70923 0,63477 0,23091 1,57491 6,134 68,15
          2 CLA code lock algorithm (joo) 0,95345 0,87107 0,37590 2,20042 0,98942 0,91709 0,31642 2,22294 0,79692 0,69385 0,19303 1,68380 6,107 67,86
          3 AMOm animal migration ptimization M 0,90358 0,84317 0,46284 2,20959 0,99001 0,92436 0,46598 2,38034 0,56769 0,59132 0,23773 1,39675 5,987 66,52
          4 (P+O)ES (P+O) evolution strategies 0,92256 0,88101 0,40021 2,20379 0,97750 0,87490 0,31945 2,17185 0,67385 0,62985 0,18634 1,49003 5,866 65,17
          5 CTA comet tail algorithm (joo) 0,95346 0,86319 0,27770 2,09435 0,99794 0,85740 0,33949 2,19484 0,88769 0,56431 0,10512 1,55712 5,846 64,96
          6 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
          7 AAm archery algorithm M 0,91744 0,70876 0,42160 2,04780 0,92527 0,75802 0,35328 2,03657 0,67385 0,55200 0,23738 1,46323 5,548 61,64
          8 ESG evolution of social groups (joo) 0,99906 0,79654 0,35056 2,14616 1,00000 0,82863 0,13102 1,95965 0,82333 0,55300 0,04725 1,42358 5,529 61,44
          9 SIA simulated isotropic annealing (joo) 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
          10 ACS artificial cooperative search 0,75547 0,74744 0,30407 1,80698 1,00000 0,88861 0,22413 2,11274 0,69077 0,48185 0,13322 1,30583 5,226 58,06
          11 BHAm black hole algorithm M 0,75236 0,76675 0,34583 1,86493 0,93593 0,80152 0,27177 2,00923 0,65077 0,51646 0,15472 1,32195 5,196 57,73
          12 ASO anarchy society optimization 0,84872 0,74646 0,31465 1,90983 0,96148 0,79150 0,23803 1,99101 0,57077 0,54062 0,16614 1,27752 5,178 57,54
          13 AOSm atomic orbital search M 0,80232 0,70449 0,31021 1,81702 0,85660 0,69451 0,21996 1,77107 0,74615 0,52862 0,14358 1,41835 5,006 55,63
          14 TSEA turtle shell evolution algorithm (joo) 0,96798 0,64480 0,29672 1,90949 0,99449 0,61981 0,22708 1,84139 0,69077 0,42646 0,13598 1,25322 5,004 55,60
          15 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
          16 CRO chemical reaction optimisation 0,94629 0,66112 0,29853 1,90593 0,87906 0,58422 0,21146 1,67473 0,75846 0,42646 0,12686 1,31178 4,892 54,36
          17 BSA bird swarm algorithm 0,89306 0,64900 0,26250 1,80455 0,92420 0,71121 0,24939 1,88479 0,69385 0,32615 0,10012 1,12012 4,809 53,44
          18 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
          19 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
          20 BCOm bacterial chemotaxis optimization M 0,75953 0,62268 0,31483 1,69704 0,89378 0,61339 0,22542 1,73259 0,65385 0,42092 0,14435 1,21912 4,649 51,65
          21 ABO african buffalo optimization 0,83337 0,62247 0,29964 1,75548 0,92170 0,58618 0,19723 1,70511 0,61000 0,43154 0,13225 1,17378 4,634 51,49
          22 (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
          23 TSm tabu search M 0,87795 0,61431 0,29104 1,78330 0,92885 0,51844 0,19054 1,63783 0,61077 0,38215 0,12157 1,11449 4,536 50,40
          24 BSO brain storm optimization 0,93736 0,57616 0,29688 1,81041 0,93131 0,55866 0,23537 1,72534 0,55231 0,29077 0,11914 0,96222 4,498 49,98
          25 WOAm wale optimization algorithm M 0,84521 0,56298 0,26263 1,67081 0,93100 0,52278 0,16365 1,61743 0,66308 0,41138 0,11357 1,18803 4,476 49,74
          26 AEFA artificial electric field algorithm 0,87700 0,61753 0,25235 1,74688 0,92729 0,72698 0,18064 1,83490 0,66615 0,11631 0,09508 0,87754 4,459 49,55
          27 AEO artificial ecosystem-based optimization algorithm 0,91380 0,46713 0,26470 1,64563 0,90223 0,43705 0,21400 1,55327 0,66154 0,30800 0,28563 1,25517 4,454 49,49
          28 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
          29 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
          30 SOA simple optimization algorithm 0,91520 0,46976 0,27089 1,65585 0,89675 0,37401 0,16984 1,44060 0,69538 0,28031 0,10852 1,08422 4,181 46,45
          31 ABHA artificial bee hive algorithm 0,84131 0,54227 0,26304 1,64663 0,87858 0,47779 0,17181 1,52818 0,50923 0,33877 0,10397 0,95197 4,127 45,85
          32 ACMO atmospheric cloud model optimization 0,90321 0,48546 0,30403 1,69270 0,80268 0,37857 0,19178 1,37303 0,62308 0,24400 0,10795 0,97503 4,041 44,90
          33 ADAMm adaptive moment estimation M 0,88635 0,44766 0,26613 1,60014 0,84497 0,38493 0,16889 1,39880 0,66154 0,27046 0,10594 1,03794 4,037 44,85
          34 ATAm artificial tribe algorithm M 0,71771 0,55304 0,25235 1,52310 0,82491 0,55904 0,20473 1,58867 0,44000 0,18615 0,09411 0,72026 3,832 42,58
          35 ASHA artificial showering algorithm 0,89686 0,40433 0,25617 1,55737 0,80360 0,35526 0,19160 1,35046 0,47692 0,18123 0,09774 0,75589 3,664 40,71
          36 ASBO adaptive social behavior optimization 0,76331 0,49253 0,32619 1,58202 0,79546 0,40035 0,26097 1,45677 0,26462 0,17169 0,18200 0,61831 3,657 40,63
          37 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
          38 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
          39 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
          40 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
          41 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
          42 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
          43 BBBC big bang-big crunch algorithm 0,60531 0,45250 0,31255 1,37036 0,52323 0,35426 0,20417 1,08166 0,39769 0,19431 0,11286 0,70486 3,157 35,08
          44 CPA cyclic parthenogenesis algorithm 0,71664 0,40014 0,25502 1,37180 0,62178 0,33651 0,19264 1,15093 0,34308 0,16769 0,09455 0,60532 3,128 34,76
          45 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
          RW random walk 0,48754 0,32159 0,25781 1,06694 0,37554 0,21944 0,15877 0,75375 0,27969 0,14917 0,09847 0,52734 2,348 26,09




          Выводы

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

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

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

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

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

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

          Tab

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

          Chart

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

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

          Плюсы:

          1. Интересная идея.
          2. Достаточно простая реализация.
          3. Неплохо работает на задачах больших размерностей.

          Минусы:

          1. Много внешних параметров.
          2. Низкая скорость и точность сходимости.

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

          Программы, используемые в статье

          # Имя Тип Описание
          1 #C_AO.mqh
          Включаемый файл
          Родительский класс популяционных алгоритмов оптимизации
          2 #C_AO_enum.mqh
          Включаемый файл
          Перечисление популяционных алгоритмов оптимизации
          3 TestFunctions.mqh
          Включаемый файл
          Библиотека тестовых функций
          4
          TestStandFunctions.mqh
          Включаемый файл
          Библиотека функций тестового стенда
          5
          Utilities.mqh
          Включаемый файл
          Библиотека вспомогательных функций
          6
          CalculationTestResults.mqh
          Включаемый файл
          Скрипт для расчета результатов в сравнительную таблицу
          7
          Testing AOs.mq5
          Скрипт Единый испытательный стенд для всех популяционных алгоритмов оптимизации
          8
          Simple use of population optimization algorithms.mq5
          Скрипт
          Простой пример использования популяционных алгоритмов оптимизации без визуализации
          9
          Test_AO_CPA.mq5
          Скрипт Испытательный стенд для CPA
          Прикрепленные файлы |
          CPA.ZIP (151.92 KB)
          От начального до среднего уровня: Операторы От начального до среднего уровня: Операторы
          В этой статье мы рассмотрим основных операторов. Хотя тема проста для понимания, есть определенные моменты, которые имеют большое значение, когда речь идет о включении математических выражений в формат кода. Без адекватного понимания этих деталей, программисты с небольшим опытом или вообще без него в итоге отказываются от попыток создать собственных решений.
          Разработка системы репликации (Часть 59): Новое будущее Разработка системы репликации (Часть 59): Новое будущее
          Правильное понимание разных идей позволяет нам делать больше с наименьшими усилиями. В этой статье мы рассмотрим, почему необходимо настроить применение шаблона до того, как сервис начнет взаимодействовать с графиком. И что, если мы улучшим указатель мыши, чтобы иметь возможность делать больше вещей с его помощью?
          Визуальная оценка и корректировка торговли в MetaTrader 5 Визуальная оценка и корректировка торговли в MetaTrader 5
          В тестере стратегий можно не только оптимизировать параметры торгового робота. Мы покажем, как оценить постфактум проторгованную историю своего счёта и внести корректировки в торговлю в тестере, изменяя размеры стоп-приказов открываемых позиций.
          Нейросети в трейдинге: Контекстно-зависимое обучение, дополненное памятью (MacroHFT) Нейросети в трейдинге: Контекстно-зависимое обучение, дополненное памятью (MacroHFT)
          Предлагаю познакомиться с фреймворком MacroHFT, который применяет контекстно зависимое обучение с подкреплением и память, для улучшения решений в высокочастотной торговле криптовалютами, используя макроэкономические данные и адаптивные агенты.