MetaTrader 5 / Тестер
preview
Алгоритм стрельбы из лука — Archery Algorithm (AA)

Алгоритм стрельбы из лука — Archery Algorithm (AA)

MetaTrader 5 — Тестер | 12 сентября 2024, 10:28
143 1
Andrey Dik
Andrey Dik

Содержание

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


Введение

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

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

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

В данной статье мы представим новый подход к решению задач оптимизации — Алгоритм стрельбы из лука (Archery Algorithm, AA). Алгоритм был разработан Фатеме Ахмади Зейдабади с коллегами и был опубликован в феврале 2022 года. Этот метод, вдохновленный искусством стрельбы из лука, предлагает квази-оптимальные решения, обновляя положение членов популяции в пространстве поиска на основе случайно выбранного элемента. Мы протестируем эффективность AA на стандартных целевых функциях и сравним полученные результаты с уже известными нам алгоритмами. Погружаясь в детали, мы раскроем, как этот инновационный подход может изменить наше восприятие оптимизации и открыть новые горизонты для решения сложных задач.


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

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

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

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

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

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

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

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

1. Популяция агентов (лучников)
2. Вектор вероятностей и кумулятивных вероятностей
3. Механизм наследования (отсутствует в оригинальной версии)
4. Механизм обновления позиций
5. Параметр интенсивности обучения (I)

Для начала представим псевдокод алгоритма:

Инициализация:
    Создать популяцию из popSize агентов
    Для каждого агента:
        Инициализировать случайную позицию в пределах диапазона поиска
        Инициализировать предыдущую позицию и приспособленность

Главный цикл:
    Пока не достигнуто условие остановки:
        Для каждого агента i в популяции:
            Рассчитать вектор вероятностей P и кумулятивных вероятностей C
            
            Для каждой координаты c:
                Выбрать лучника k с использованием кумулятивной вероятности
                
                Если (случайное_число < вероятность_наследования):
                    новая_позиция [c] = позиция_лучника_k [c]
                Иначе:
                    I = округление (1 + случайное_число_от_0_до_1)  // Параметр интенсивности обучения
                    случайное_гауссово = сгенерировать_гауссово_число (среднее = 0, мин =-1, макс = 1)
                    
                    Если (приспособленность_лучника_k > приспособленность_агента_i):
                        новая_позиция [c] = предыдущая_позиция [c] + случайное_гауссово * (позиция_лучника_k [c] - I * предыдущая_позиция [c])
                    Иначе:
                        новая_позиция [c] = предыдущая_позиция [c] + случайное_гауссово * (предыдущая_позиция [c] - I * позиция_лучника_k [c])
                
                Ограничить новую_позицию [c] в пределах диапазона поиска
            
            Обновить позицию агента i
        
        Оценить приспособленность всех агентов
        Обновить лучшее глобальное решение
        Для каждого агента:
            Если новая приспособленность лучше предыдущей:
                Обновить предыдущую позицию и приспособленность

Вернуть лучшее найденное решение

Особенности реализации в коде:

1. Алгоритм использует вероятностный подход для выбора лучников, у которых нужно учиться.
2. Механизм наследования позволяет агентам напрямую копировать позиции успешных лучников с некоторой вероятностью.
3. При обновлении позиций используется гауссово распределение для внесения случайности в процесс обучения лучников.
4. Алгоритм сохраняет предыдущие лучшие позиции агентов, что позволяет ему иметь некоторую "память" о хороших решениях.
5. Реализация будет включать механизм ограничения новых позиций в пределах допустимого диапазона поиска.
6. Параметр интенсивности обучения (I), описанный авторами будет использоваться для регулирования степени влияния текущей позиции на новую.

Параметр I (интенсивность обучения) — это случайная величина, которая может принимать значение 1 или 2. Он определяется следующим образом: I = округление до целого числа (1 + случайно сгенерированное число от 0 до 1). Это означает, что I будет равно 1 с вероятностью 0.5 и 2 с той же вероятностью. Роль параметра I в алгоритме:

1. Когда I = 1, алгоритм производит более мелкие корректировки позиции.
2. Когда I = 2, алгоритм может сделать более резкие изменения в позиции.

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

  • cPrev [] - массив хранит предыдущие координаты агента.
  • fPrev -  переменная хранит предыдущее значение "фитнеса" (fitness) агента.   

Метод "Init" позволяет подготовить агента к работе, задав начальные значения для его координат и фитнеса. Далее устанавливается значение "fPrev" в минимально возможное значение для типа "double", потому что приспособленность еще не была рассчитана.

//——————————————————————————————————————————————————————————————————————————————
struct S_AA_Agent
{
    double cPrev []; // previous coordinates
    double fPrev;    // previous fitness

    void Init (int coords)
    {
      ArrayResize (cPrev, coords);
      fPrev = -DBL_MAX;
    }
};
//——————————————————————————————————————————————————————————————————————————————

Давайте разберем класс "C_AO_AAm", который реализует сам алгоритм и наследуется от класса "C_AO". 

  • popSize - указывает на размер популяции.
  • inhProbab - представляет собой значение вероятности наследования признака от другого лучника.

Затем происходит инициализация массива "params" размером 2, где сохраняются параметры алгоритма: размер популяции и вероятность наследования.

  • SetParams - метод устанавливает параметры алгоритма на основе значений, хранящихся в массиве "params". Он извлекает значения для "popSize" и "inhProbab", преобразуя их в соответствующие типы.
  • Init - метод инициализирует алгоритм, принимая минимальные и максимальные границы поиска, шаг поиска и количество эпох.
  • Moving и Revision - методы отвечают за логику перемещения агентов в пространстве решений и их ревизию (обновление). 

S_AA_Agent agent [] - массив агентов, которые будут использоваться для выполнения оптимизации.

Класс "C_AO_AAm" реализует алгоритм оптимизации, а методы "SetParams", "Init", "Moving" и "Revision" управляют настройкой и поведением алгоритма в процессе его работы. 

//——————————————————————————————————————————————————————————————————————————————
class C_AO_AAm : public C_AO
{
  public: //--------------------------------------------------------------------
  ~C_AO_AAm () { }
  C_AO_AAm ()
  {
    ao_name = "AAm";
    ao_desc = "Archery Algorithm M";
    ao_link = "https://www.mql5.com/ru/articles/15782";

    popSize   = 50;    // population size
    inhProbab = 0.3;

    ArrayResize (params, 2);

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

  void SetParams ()
  {
    popSize   = (int)params [0].val;
    inhProbab = 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 ();

  //----------------------------------------------------------------------------
  double  inhProbab; //probability of inheritance

  S_AA_Agent agent [];

  private: //-------------------------------------------------------------------
};
//——————————————————————————————————————————————————————————————————————————————

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

  • Если стандартная инициализация прошла успешно, метод затем изменяет размер массива "agent", чтобы он соответствовал установленному размеру популяции "popSize". Это позволяет создать необходимое количество агентов, которые будут использоваться в алгоритме.
  • В цикле "for" каждый агент из массива инициализируется с помощью метода "Init", который задает начальные координаты для каждого агента.

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

//——————————————————————————————————————————————————————————————————————————————
bool C_AO_AAm::Init (const double &rangeMinP  [],
                     const double &rangeMaxP  [],
                     const double &rangeStepP [],
                     const int     epochsP = 0)
{
  if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false;

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

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

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

  • Если метод вызывается впервые ("revision" равно "false"), то для каждого агента и каждой координаты инициализируется случайное значение в пределах заданных границ "rangeMin" и "rangeMax".
  • Затем, это значение корректируется с помощью метода "SeInDiSp", который обеспечивает соответствие значения заданному шагу.

После этого флаг "revision" устанавливается в "true", и метод завершает свою работу.

  • Далее создаются два массива: "P" для вероятностей и "C" для кумулятивных вероятностей.
  • Находится наихудшее значение функции "F_worst", чтобы нормализовать значения фитнес-функции для агентов.
  • Затем вычисляются вероятности для каждого агента, которые нормализуются так, чтобы их сумма равнялась 1.
  • Кумулятивные вероятности "C" рассчитываются на основе вероятностей "P".
  • Для каждого агента и каждой координаты происходит выбор стрелка-напарника, агента на основе кумулятивной вероятности.
  • Если случайное значение меньше заданной вероятности наследования "inhProbab", агент принимает координату выбранного агента (обеспечивая наследование признаков с заданной вероятностью).
  • В противном случае, агент обновляет свою позицию на основе формулы, которая учитывает текущее положение, случайное значение и позицию стрелка-напарника.
  • Наконец, новое значение координаты также корректируется с помощью метода "SeInDiSp".

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

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

  //-------------------------------------------------------------------------
  // Calculate probability vector P and cumulative probability C
  double P [], C [];
  ArrayResize (P, popSize);
  ArrayResize (C, popSize);
  double F_worst = DBL_MAX;
  double sum = 0;

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

  for (int i = 0; i < popSize; i++)
  {
    P [i] =  a [i].f - F_worst;
    sum += P [i];
  }

  for (int i = 0; i < popSize; i++)
  {
    P [i] /= sum;
    C [i] = (i == 0) ? P [i] : C [i - 1] + P [i];
  }

  double x;

  for (int i = 0; i < popSize; i++)
  {
    for (int c = 0; c < coords; c++)
    {
      // Select archer (k) using cumulative probability
      int k = 0;
      double r = u.RNDprobab ();
      while (k < popSize - 1 && C [k] < r) k++;

      if (u.RNDbool () < inhProbab)
      {
        x = a [k].c [c];
      }
      else
      {
        // Update position using Eq. (5) and (6)
        double I   = MathRound (1 + u.RNDprobab ());
        double rnd = u.GaussDistribution (0, -1, 1, 8);

        if (a [k].f > a [i].f)
        {
          x = agent [i].cPrev [c] + rnd * (a [k].c [c] - I * agent [i].cPrev [c]);
        }
        else
        {
          x = agent [i].cPrev [c] + rnd * (agent [i].cPrev [c] - I * a [k].c [c]);
        }
      }

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

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

  • Переменная "ind" инициализируется значением "-1". Она будет использоваться для хранения индекса агента с наилучшим значением функции.
  • Цикл "for" проходит по всем агентам в популяции "popSize" и если значение функции текущего агента "a [i].f" больше, чем текущее лучшее значение функции "fB":
    • обновляется "fB" на новое лучшее значение "a [i].f".
    • сохраняется индекс этого агента в переменной "ind".
После завершения цикла, если "ind" не равен "-1", вызывается функция "ArrayCopy", которая копирует координаты лучшего агента из массива "a" в массив "cB". Второй цикл "for" также проходит по всем агентам в популяции:

  • Если значение функции текущего агента "a [i].f" больше, чем его предыдущее значение фитнес-функции "agent [i].fPrev":
    • обновляется предыдущее значение "fPrev" для этого агента.
    • копируются текущие координаты агента в массив "cPrev" с помощью "ArrayCopy".

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

//——————————————————————————————————————————————————————————————————————————————
void C_AO_AAm::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++)
  {
    if (a [i].f > agent [i].fPrev)
    {
      agent [i].fPrev = a [i].f;
      ArrayCopy (agent [i].cPrev, a [i].c, 0, 0, WHOLE_ARRAY);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————


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

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

if (u.RNDbool () < inhProbab)
{
  x = a [k].c [c];
}

Результаты представленные ниже, соответствуют оригинальной версии алгоритма по замыслу авторов.

AA|Archery Algorithm|50.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.6699547926310098
25 Hilly's; Func runs: 10000; result: 0.37356238340164605
500 Hilly's; Func runs: 10000; result: 0.257542163368952
=============================
5 Forest's; Func runs: 10000; result: 0.38166669771790607
25 Forest's; Func runs: 10000; result: 0.199300365268835
500 Forest's; Func runs: 10000; result: 0.15337954055780398
=============================
5 Megacity's; Func runs: 10000; result: 0.4076923076923077
25 Megacity's; Func runs: 10000; result: 0.17907692307692308
500 Megacity's; Func runs: 10000; result: 0.10004615384615476
=============================
All score: 2.72222 (30.25%)

Алгоритм набирает по итогам тестирования 30.25%, однако с моей модификацией алгоритм улучшил свою работу больше, чем на 13%. Ниже представлены результаты работы модифицированной версии:

AAm|Archery Algorithm M|50.0|0.3|
=============================
5 Hilly's; Func runs: 10000; result: 0.9353194829441194
25 Hilly's; Func runs: 10000; result: 0.6798262991897616
500 Hilly's; Func runs: 10000; result: 0.2596620178276653
=============================
5 Forest's; Func runs: 10000; result: 0.5735062785421186
25 Forest's; Func runs: 10000; result: 0.22007188891556378
500 Forest's; Func runs: 10000; result: 0.1486980566819649
=============================
5 Megacity's; Func runs: 10000; result: 0.6307692307692309
25 Megacity's; Func runs: 10000; result: 0.344
500 Megacity's; Func runs: 10000; result: 0.10193846153846249
=============================
All score: 3.89379 (43.26%)

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

Hilly

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

Forest

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

Megacity

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

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

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



Выводы

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

Tab

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

chart

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


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

Goals

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

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

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

  //-------------------------------------------------------------------------
  // Calculate probability vector P and cumulative probability C
  double P [], C [];
  ArrayResize (P, popSize);
  ArrayResize (C, popSize);
  double F_worst = DBL_MAX; // a[ArrayMaximum(a, WHOLE_ARRAY, 0, popSize)].f;
  double sum = 0;

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

  for (int i = 0; i < popSize; i++)
  {
    P [i] =  a [i].f - F_worst; ////F_worst - a[i].f;
    sum += P [i];
  }

  for (int i = 0; i < popSize; i++)
  {
    P [i] /= sum;
    C [i] = (i == 0) ? P [i] : C [i - 1] + P [i];
  }

  double x;
  
  double maxFF = fB;
  double minFF = DBL_MAX;
  double prob1;
  double prob2;
  
  for (int i = 0; i < popSize; i++)
  {
    if (a [i].f < minFF) minFF = a [i].f;
  } 

  for (int i = 0; i < popSize; i++)
  {
    for (int c = 0; c < coords; c++)
    {
      // Select archer (k) using cumulative probability
      int k = 0;
      double r = u.RNDprobab ();
      while (k < popSize - 1 && C [k] < r) k++;

      if (u.RNDbool () < inhProbab)
      {
        x = a [k].c [c];
      }
      else
      {
        
        // Update position using Eq. (5) and (6)
        //double I   = MathRound (1 + u.RNDprobab ());
        double rnd = u.GaussDistribution (0, -1, 1, 8);
        /*
        if (a [k].f > a [i].f)
        {
          x = agent [i].cPrev [c] + rnd * (a [k].c [c] - I * agent [i].cPrev [c]);
        }
        else
        {
          x = agent [i].cPrev [c] + rnd * (agent [i].cPrev [c] - I * a [k].c [c]);
        }
        */
        
        prob1 = u.Scale (a [i].f, minFF, maxFF, 0, 1);
        prob2 = u.Scale (a [k].f, minFF, maxFF, 0, 1);
        
        x = agent [i].cPrev [c] + rnd * (a [k].c [c] - agent [i].cPrev [c]) * (1 - prob1 - prob2);  
        
      }

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

1. В закомментированной секции в первоначальной версии использовалась условная конструкция  "if-else" для определения способа обновления позиции агента. Эта логика была удалена и заменена новым расчетом.

2. Три новые строки кода:

prob1 = u.Scale(a[i].f, minFF, maxFF, 0, 1);
prob2 = u.Scale(a[k].f, minFF, maxFF, 0, 1);

x = agent[i].cPrev[c] + rnd * (a[k].c[c] - agent[i].cPrev[c]) * (1 - prob1 - prob2);

Эти строки вводят новый подход к расчету обновленной позиции:

а) Вычисляются две вероятностные величины, "prob1" и "prob2", с использованием функции "Scale", которая нормализует значения приспособленности агентов "i" и "k" в диапазоне от 0 до 1, основываясь на минимальном и максимальном значениях приспособленности, "minFF" и "maxFF".

б) Затем новая позиция "x" рассчитывается с использованием этих вероятностей. Она использует предыдущую позицию "i" агента  "agent [i].cPrev [c]", позицию "k" выбранного лучника "a [k].c [c]" и случайный фактор "rnd".

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

Теперь посмотрим на результаты:

AAm|Archery Algorithm M|50.0|0.3|
=============================
5 Hilly's; Func runs: 10000; result: 0.9174358826544864
25 Hilly's; Func runs: 10000; result: 0.7087620527831496
500 Hilly's; Func runs: 10000; result: 0.42160091427958263
=============================
5 Forest's; Func runs: 10000; result: 0.9252690259821034
25 Forest's; Func runs: 10000; result: 0.7580206359203926
500 Forest's; Func runs: 10000; result: 0.353277934084795
=============================
5 Megacity's; Func runs: 10000; result: 0.6738461538461538
25 Megacity's; Func runs: 10000; result: 0.552
500 Megacity's; Func runs: 10000; result: 0.23738461538461658
=============================
All score: 5.54760 (61.64%)

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

Hilly2

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

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

//x = agent [i].cPrev [c] + rnd * (a [k].c [c] - agent [i].cPrev [c]) * (1 - prob1 - prob2); 
 x = agent [i].cPrev [c] + rnd * (a [k].c [c] - agent [i].cPrev [c]) * (2 - prob1 - prob2);  

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

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

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

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

AAm|Archery Algorithm M|50.0|0.3|
=============================
5 Hilly's; Func runs: 10000; result: 0.9053229410164233
25 Hilly's; Func runs: 10000; result: 0.8259118221071665
500 Hilly's; Func runs: 10000; result: 0.2631661675236262
=============================
5 Forest's; Func runs: 10000; result: 0.9714247249319152
25 Forest's; Func runs: 10000; result: 0.9091052022399436
500 Forest's; Func runs: 10000; result: 0.2847632249786224
=============================
5 Megacity's; Func runs: 10000; result: 0.7169230769230768
25 Megacity's; Func runs: 10000; result: 0.6378461538461538
500 Megacity's; Func runs: 10000; result: 0.10473846153846252
=============================
All score: 5.61920 (62.44%)

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

Tab2

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

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

Плюсы:

  1. Достаточно быстрый.
  2. Самоадаптивный.
  3. Всего лишь один внешний параметр.
  4. Хорошая сходимость.
  5. Хорошая масштабируемость.
  6. Простая реализация (несмотря на сложное описание авторами).

Минусы:

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

Дальнейшее добавление новых алгоритмов в рейтинговую таблицу стало вызывать трудности — она стала плохо читаемой. Поэтому я решил ограничить количество участников сравнения до 45 алгоритмов, и теперь соревнование проходит в формате "на вылет". Чтобы читатели могли легко и наглядно получить доступ ко всем статьям, я подготовил HTML-файл со списком всех ранее рассмотренных алгоритмов, упорядоченных по их рейтингу в таблице. Этот файл присутствует в архиве к статьям уже некоторое время, а для тех, кто открывает его впервые, приготовлен небольшой сюрприз.

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

Прикрепленные файлы |
Загрузить ZIP
AAm.ZIP (34.86 KB)
Предупреждение: все права на данные материалы принадлежат MetaQuotes Ltd. Полная или частичная перепечатка запрещена.

Другие статьи автора

Последние комментарии | Перейти к обсуждению на форуме трейдеров (1)
Ilya Melamed
Ilya Melamed | 13 сент. 2024 в 18:11
Спасибо за исследование. Но у меня, как у простого програмиста советников на mql5 ),( я ни разу не математик),  есть очень простой вопрос. Возможно, он Вам покажется глупым, заранее извините. Но все же, как ваше исследование может помочь в оптимизации советников? Не могли бы Вы привести пример. Вот допустим, у нас есть новый советник, мы хотим его оптимизировать, и ....? Спасибо.
Простые решения для удобной работы с индикаторами Простые решения для удобной работы с индикаторами
В этой статье расскажу, как сделать простенькую панельку для изменения настроек индикатора прямо с графика, и какие изменения нужно внести в индикатор, чтобы подключить эту панель. Статья рассчитана исключительно на тех, кто только начал знакомиться с языком MQL5.
Возможности Мастера MQL5, которые вам нужно знать (Часть 17): Мультивалютная торговля Возможности Мастера MQL5, которые вам нужно знать (Часть 17): Мультивалютная торговля
По умолчанию торговля несколькими валютами недоступна при сборке советника с помощью Мастера. Мы рассмотрим два возможных приема, к которым могут прибегнуть трейдеры, желающие проверить свои идеи на нескольких символах одновременно.
Нейросети в трейдинге: Обнаружение объектов с учетом сцены (HyperDet3D) Нейросети в трейдинге: Обнаружение объектов с учетом сцены (HyperDet3D)
Предлагаем Вам познакомиться с новым подход обнаружения объектов при помощи гиперсетей. Гиперсеть генерирующих весовые коэффициенты для основной модели, что позволяет учитывать особенности текущего состояния рынка. Такой подход позволяет улучшить точность прогнозирования, адаптируя модель к различным торговым условиям.
Метод группового учета аргументов: реализация комбинаторного алгоритма на MQL5 Метод группового учета аргументов: реализация комбинаторного алгоритма на MQL5
В этой статье мы продолжаем изучение семейства алгоритмов группового учета аргументов. Реализуем средствами MQL5 комбинаторный алгоритм, а также его усовершенствованную версию — комбинаторный селективный алгоритм.