preview
Алгоритм кодового замка (Сode Lock Algorithm, CLA)

Алгоритм кодового замка (Сode Lock Algorithm, CLA)

MetaTrader 5Примеры | 22 мая 2024, 14:44
761 4
Andrey Dik
Andrey Dik

Содержание:

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


1. Введение

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

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

Преимущества кодовых замков:

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

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

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

Например, можно представить себе алгоритм оптимизации, который использует аналогию с кодовым замком следующим образом:

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

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


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

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

1. Инициализация:
      Создать массив замков размером "popSize", каждый из которых имеет "coords" наборов дисков, каждый набор имеет "lockDiscs" дисков.
2. Подбор комбинации замков:
      Если это первый шаг, инициализировать каждый диск каждого набора каждого замка случайным числом от 0 до 9.
      Иначе, для каждого замка:
         - Если случайное число меньше "copyProb", скопировать набор дисков от случайно выбранного замка.
         - Иначе, для каждого набора дисков:
            - Если случайное число меньше "rotateProb", установить диск на случайном числе от 0 до 9.
            - Иначе, скопировать диск от случайно выбранного замка.
3. Оценка качества комбинаций замков:
      Обновить качество комбинации каждого замка.   
      Найти замок с наилучшим качеством комбинации и обновить глобальное наилучшее решение, если это необходимо.
      Скопировать все замки в общую корзину замков.
      Отсортировать корзину замков по приспособленности.
4. Повторять шаги 2 и 3 заданное количество эпох или до достижения критерия останова.

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

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

Если, например, параметр задачи имеет набор из 9 дисков, на каждом из которых цифры от 0 до 9, то комбинация может быть от 000000000 до 999999999. Полученное число в комбинации мы отмасштабируем в диапазон от "min" до "max" соответствующего параметра. Таким образом, если у нас, к примеру, три оптимизируемых параметра, то наш кодовый замок будет иметь 3 x 9 = 27 цифровых дисков. На рисунке 1 иллюстрируется механизм кодирования для одного параметра.

Code

Рисунок 1. Декодирование параметра задачи из цифрового кода в вещественное значение

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

1. Кроссовер (Crossover). Кроссовер в генетических алгоритмах предназначен для комбинирования генетического материала двух родителей для создания потомства.

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

2. Мутация (Mutation). Мутация в генетических алгоритмах представляет собой случайное изменение генетического материала для создания разнообразия в популяции.

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

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

Для решения задачи нам необходимо подобрать правильную комбинацию цифр на кодовом замке. Нужно вращать диски, чтобы найти верную кодовую комбинацию, которая позволит открыть замок. В отличие от генетических алгоритмов, где при "вращении" значения двоичного кода в генах вероятность выпадения значения 50/50 (либо 0, либо 1), в алгоритме кодового замка мы можем использовать распределения вероятностей в стратегии вращения дисков. Давайте рассмотрим несколько вариантов.

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

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

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

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

Мы можем попробовать использовать еще и третий вариант – равномерное распределение, при котором создается равная вероятность выбора любой цифры на диске замка.

Теперь можем перейти от теоретической части к написанию кода и практическим исследованиям.

В алгоритме CLA агента, представляющего решение задачи, опишем замок структурой "S_CLA_Agent". Вот его основные компоненты:

  • f - эта переменная хранит значение приспособленности агента. Она инициализируется как -DBL_MAX, что означает наименьшее возможное значение для типа double.
  • struct S_Lock - это вложенная структура, содержит массив "lock". Этот массив используется для хранения кодовой комбинации отдельного оптимизируемого параметра задачи.
  • S_Lock code [] - это массив структур "S_Lock". Весь этот массив представляет собой "замок".
  • void Init (int coords, int lockDiscs) - это функция инициализации. Она принимает два параметра: "coords" - определяет количество наборов параметров, и "lockDiscs" - определяет количество дисков в каждом наборе. Внутри этой функции происходит инициализация массива "code".

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

//——————————————————————————————————————————————————————————————————————————————
struct S_CLA_Agent
{
    double f;  //fitness

    struct S_Lock
    {
        int lock [];
    };

    S_Lock code [];


    void Init (int coords, int lockDiscs)
    {
      f = -DBL_MAX;

      ArrayResize (code, coords);

      for (int i = 0; i < coords; i++)
      {
        ArrayResize (code [i].lock, lockDiscs);
      }
    }
};
//——————————————————————————————————————————————————————————————————————————————

Теперь опишем класс "C_AO_CLA", который является производным от класса "C_AO". Основные компоненты класса:

  • C_AO_CLA () - конструктор класса, который инициализирует объект класса. Внутри этого конструктора инициализируются параметры, такие как "popSize", "lockDiscs", "copyProb", "rotateProb" и "params".
  • SetParams () - функция устанавливает параметры алгоритма на основе значений в массиве "params".
  • Init () - функция инициализации, принимает диапазоны поиска и количество эпох, как параметры.
  • Moving (), Revision () - это функции, которые используются для выполнения основной логики в алгоритме.
  • lockDiscs, copyProb, rotateProb - переменные, которые используются для хранения параметров алгоритма.
  • S_CLA_Agent agent [] - массив агентов, каждый из которых представляет собой объект структуры "S_CLA_Agent".
  • maxLockNumber, S_CLA_Agent parents [], S_CLA_Agent parTemp [] - приватные переменные и массивы, которые используются внутри класса.
  • ArrayToNumber (), LockToDouble () - приватные методы, которые используются для преобразования массива кодовой комбинации в число, и замка в число, с плавающей точкой соответственно.
//——————————————————————————————————————————————————————————————————————————————
class C_AO_CLA : public C_AO
{
  public: //--------------------------------------------------------------------
  ~C_AO_CLA () { }
  C_AO_CLA ()
  {
    ao_name = "CLA";
    ao_desc = "Code Lock Algorithm";
    ao_link = "https://www.mql5.com/ru/articles/14878";

    popSize     = 100;   //population size

    lockDiscs   = 8;     //lock discs
    copyProb    = 0.8;   //copying probability
    rotateProb  = 0.03;  //rotate disc probability

    ArrayResize (params, 4);

    params [0].name = "popSize";     params [0].val = popSize;

    params [1].name = "lockDiscs";   params [1].val = lockDiscs;
    params [2].name = "copyProb";    params [2].val = copyProb;
    params [3].name = "rotateProb";  params [3].val = rotateProb;
  }

  void SetParams ()
  {
    popSize    = (int)params [0].val;

    lockDiscs  = (int)params [1].val;
    copyProb   = params      [2].val;
    rotateProb = params      [3].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);

  //----------------------------------------------------------------------------
  int    lockDiscs;    //lock discs
  double copyProb;     //copying probability
  double rotateProb;   //rotate disc probability

  S_CLA_Agent agent [];

  private: //-------------------------------------------------------------------
  int maxLockNumber; //max lock number

  S_CLA_Agent parents [];
  S_CLA_Agent parTemp [];

  int    ArrayToNumber (int &arr []);
  double LockToDouble  (int lockNum, int coordPos);
};
//——————————————————————————————————————————————————————————————————————————————

Определим метод "Init" в классе "C_AO_CLA". Этот метод инициализирует алгоритм с заданными диапазонами поиска и количеством эпох. Описание каждого шага:

1. if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; - вызов функции StandardInit с заданными диапазонами поиска. Если инициализация не удалась, функция возвращает "false".

2. ArrayResize (agent, popSize); - строка изменяет размер массива agent до размера популяции "popSize".

3. for (int i = 0; i < popSize; i++) agent [i].Init (coords, lockDiscs); - цикл инициализирует каждого агента в популяции с заданным количеством координат "coords" и дисков замка "lockDiscs".

4. ArrayResize (parents, popSize * 2); ArrayResize (parTemp, popSize * 2); - строки изменяют размеры массивов "parents" и "parTemp" до двух размеров популяции.

5. for (int i = 0; i < popSize * 2; i++) { parents [i].Init (coords, lockDiscs); parTemp [i].Init (coords, lockDiscs); } - цикл инициализирует каждого родителя и временного родителя в массивах "parents" и "parTemp".

6. maxLockNumber = 0; for (int i = 0; i < lockDiscs; i++) { maxLockNumber += 9 * (int)pow (10, i); } - цикл вычисляет максимальное число в комбинации замка "maxLockNumber", используя количество дисков замка "lockDiscs".

7. return true; - если все предыдущие операции прошли успешно, функция возвращает "true".

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

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

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

  ArrayResize (parents, popSize * 2);
  ArrayResize (parTemp, popSize * 2);

  for (int i = 0; i < popSize * 2; i++)
  {
    parents [i].Init (coords, lockDiscs);
    parTemp [i].Init (coords, lockDiscs);
  }

  maxLockNumber = 0;
  for (int i = 0; i < lockDiscs; i++)
  {
    maxLockNumber += 9 * (int)pow (10, i);
  }

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

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

  • val  = 0.0; code = 0; pos  = 0; - инициализация переменных, которые будут использоваться в методе.
  • if (!revision) {...} - блок кода выполняется, если "revision" равно "false". Внутри этого блока кода происходит инициализация агентов и родителей с помощью случайных значений. 
  • Затем для каждого агента и каждого родителя вычисляются значения "code" и "val", и они используются для обновления координат агента. После этого "revision" устанавливается в "true", и функция завершается.
  • for (int i = 0; i < popSize; i++) {...} - блок кода выполняется, если "revision" равно "true". Внутри этого блока кода происходит обновление агентов. Если случайное число меньше "copyProb", то код замка одного из родителей копируется в агента. В противном случае, код замка агента обновляется либо случайным значением, либо кодом замка одного из родителей. 
  • Затем для каждого агента вычисляются значения "code" и "val", и они используются для обновления координат агента.

Функция используется для обновления агентов в алгоритме оптимизации CLA.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_CLA::Moving ()
{
  double val  = 0.0;
  int    code = 0;
  int    pos  = 0;

  //----------------------------------------------------------------------------
  if (!revision)
  {
    for (int i = 0; i < popSize; i++)
    {
      for (int c = 0; c < coords; c++)
      {
        for (int l = 0; l < lockDiscs; l++)
        {
          agent [i].code [c].lock [l] = u.RNDminusOne (10);
        }

        code = ArrayToNumber (agent [i].code [c].lock);
        val  = LockToDouble  (code, c);
        a [i].c [c] = u.SeInDiSp  (val, rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }

    for (int i = 0; i < popSize * 2; i++)
    {
      for (int c = 0; c < coords; c++)
      {
        for (int l = 0; l < lockDiscs; l++)
        {
          parents [i].code [c].lock [l] = u.RNDminusOne (10);
        }
      }
    }

    revision = true;
    return;
  }

  //----------------------------------------------------------------------------
  for (int i = 0; i < popSize; i++)
  {
    for (int c = 0; c < coords; c++)
    {
      if (u.RNDprobab () < copyProb)
      {
        int pos = u.RNDminusOne (popSize);
        ArrayCopy (agent [i].code [c].lock, parents [pos].code [c].lock, 0, 0, WHOLE_ARRAY);
      }
      else
      {
        for (int l = 0; l < lockDiscs; l++)
        {
          if (u.RNDprobab () < rotateProb)
          {
            //pos = u.RNDminusOne (popSize);
            //agent [i].code [c].lock [l] = (int)round (u.GaussDistribution (agent [i].codePrev [c].lock [l], 0, 9, 8));
            //agent [i].code [c].lock [l] = (int)round (u.PowerDistribution (agent [i].codePrev [c].lock [l], 0, 9, 20));
            agent [i].code [c].lock [l] = u.RNDminusOne (10);
          }
          else
          {
            pos = u.RNDminusOne (popSize);
            agent [i].code [c].lock [l] = parents [pos].code [c].lock [l];
          }
        }
      }

      code = ArrayToNumber (agent [i].code [c].lock);
      val  = LockToDouble  (code, c);
      a [i].c [c] = u.SeInDiSp  (val, rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————
Метод "Revision" в классе "C_AO_CLA" в общем, предназначен для обновления глобального решения. Метод выполняет следующие действия:
  • ind = -1; - инициализация переменной "ind", которая будет использоваться для отслеживания индекса агента с наилучшей приспособленностью.
  • for (int i = 0; i < popSize; i++) {...} - цикл проходит через каждого агента в популяции и проверяет, если приспособленность агента больше текущего наилучшего значения приспособленности "fB". Если это так, то "fB" обновляется, и "ind" устанавливается в текущий индекс.
  • if (ind != -1) ArrayCopy (cB, a [ind].c, 0, 0, WHOLE_ARRAY); - если был найден агент с лучшей приспособленностью, то его координаты копируются в "cB".
  • for (int i = 0; i < popSize; i++) { agent [i].f = a [i].f; } - цикл обновляет приспособленность каждого агента на основе текущих значений в массиве "a".
  • for (int i = 0; i < popSize; i++) { parents [i + popSize] = agent [i]; } - цикл копирует каждого агента в массив "parents", начиная с позиции "popSize", то есть во вторую половину родительской популяции.
  • u.Sorting (parents, parTemp, popSize * 2); - эта строка сортирует массив "parents" с использованием массива "parTemp" в качестве временного хранилища.
В целом, эта функция используется для обновления приспособленности агентов и "родительских" замков в алгоритме CLA. Это включает в себя обновление наилучшего значения приспособленности и сортировку родительской популяции по их приспособленности.
//——————————————————————————————————————————————————————————————————————————————
void C_AO_CLA::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++)
  {
    agent [i].f = a [i].f;
  }

  for (int i = 0; i < popSize; i++)
  {
    parents [i + popSize] = agent [i];
  }

  u.Sorting (parents, parTemp, popSize * 2);
}
//——————————————————————————————————————————————————————————————————————————————

Для перевода знаков кодовой комбинации в число предназначен метод "ArrayToNumber". Действия метода:

  • result = 0; - инициализация переменной, которая будет использоваться для хранения результата.
  • for (int i = 0; i < ArraySize (arr); i++) {...} - цикл проходит через каждый элемент массива "arr". Для каждого элемента "arr [i]" он умножает текущее значение "result" на 10 и добавляет значение "arr [i]".
  • return result; - строка возвращает итоговое значение "result".

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

Например, значения входного массива "arr" (кодовая комбинация): |0|3|1|5|7|0|. Нам необходимо отбросить все нули слева комбинации и начать формирование числа со значения 3. В итоге получим число 31570. Если в комбинации все ячейки массива содержат нули, то итоговое число получится 0.

//——————————————————————————————————————————————————————————————————————————————
int C_AO_CLA::ArrayToNumber (int &arr [])
{
  int result = 0;
  for (int i = 0; i < ArraySize (arr); i++)
  {
    result = result * 10 + arr [i];
  }
  return result;
}
//——————————————————————————————————————————————————————————————————————————————

Для перевода числа кодовой комбинации в масштаб оптимизируемого параметра служит метод "LockToDouble" в классе "C_AO_CLA". Вот что делает эта функция:

  • LockToDouble (int lockNum, int coordPos) - метод принимает два параметра: "lockNum", который представляет собой число замка "coordPos" и представляет собой позицию координаты в массиве координат (оптимизируемого параметра).
  • return u.Scale (lockNum, 0, maxLockNumber, rangeMin [coordPos], rangeMax [coordPos]); - строка возвращает значение, которое получается путем масштабирования "lockNum" от диапазона [0, maxLockNumber] к диапазону [rangeMin [coordPos], rangeMax [coordPos]].

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

//——————————————————————————————————————————————————————————————————————————————
double C_AO_CLA::LockToDouble (int lockNum, int coordPos)
{
  return u.Scale (lockNum, 0, maxLockNumber, rangeMin [coordPos], rangeMax [coordPos]);
}
//——————————————————————————————————————————————————————————————————————————————


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

Результаты работы алгоритма оптимизации CLA на тестовых функциях выглядят отлично. Достижение 67.86% от максимального возможного значения является превосходным результатом. Это свидетельствует о высокой производительности алгоритма CLA в оптимизации сложных функций.

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

CLA|Code Lock Algorithm|100.0|8.0|0.8|0.03|
=============================
5 Hilly's; Func runs: 10000; result: 0.9534490932631814
25 Hilly's; Func runs: 10000; result: 0.8710742215971827
500 Hilly's; Func runs: 10000; result: 0.375900385878165
=============================
5 Forest's; Func runs: 10000; result: 0.9894215656296362
25 Forest's; Func runs: 10000; result: 0.917091907561472
500 Forest's; Func runs: 10000; result: 0.3164221021938828
=============================
5 Megacity's; Func runs: 10000; result: 0.7969230769230768
25 Megacity's; Func runs: 10000; result: 0.693846153846154
500 Megacity's; Func runs: 10000; result: 0.19303076923077062
=============================
All score: 6.10716 (67.86%)

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

Hilly

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

Forest

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

Megacity

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


Алгоритм кодового замка занял второе место в рейтинговой таблице. На острой функции Forest c 10-ю параметрами CLA даже смог опередить лидера таблицы - BGA. Окраска ячеек результатов на всех тестовых функциях имеет зелёный цвет (сравнение со всеми присутствующими в таблице алгоритмами), что говорит об очень равномерной производительности на различных типах задач, без заметных провалов на отдельных тестах. 

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 BGA binary genetic algorithm 0,99989 0,99518 0,42835 2,42341 0,96153 0,96181 0,32027 2,24360 0,91385 0,95908 0,24220 2,11512 6,782 75,36
2 CLA code lock algorithm 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 (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
4 CTA comet tail algorithm 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
5 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
6 ESG evolution of social groups 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
7 SIA simulated isotropic annealing 0,95784 0,84264 0,41465 2,21513 0,98239 0,79586 0,20507 1,98332 0,68667 0,49300 0,09053 1,27020 5,469 60,76
8 TSEA turtle shell evolution algorithm 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
9 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
10 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
11 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
12 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
13 (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
14 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
15 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
16 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
17 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
18 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
19 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
20 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
21 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
22 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
23 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
24 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
25 GSA gravitational search algorithm 0,64757 0,49197 0,30062 1,44016 0,53962 0,36353 0,09945 1,00260 0,32667 0,12200 0,01917 0,46783 2,911 32,34
26 BFO bacterial foraging optimization 0,61171 0,43270 0,31318 1,35759 0,54410 0,21511 0,05676 0,81597 0,42167 0,13800 0,03195 0,59162 2,765 30,72
27 ABC artificial bee colony 0,63377 0,42402 0,30892 1,36671 0,55103 0,21874 0,05623 0,82600 0,34000 0,14200 0,03102 0,51302 2,706 30,06
28 BA bat algorithm 0,59761 0,45911 0,35242 1,40915 0,40321 0,19313 0,07175 0,66810 0,21000 0,10100 0,03517 0,34617 2,423 26,93
29 SA simulated annealing 0,55787 0,42177 0,31549 1,29513 0,34998 0,15259 0,05023 0,55280 0,31167 0,10033 0,02883 0,44083 2,289 25,43
30 IWDm intelligent water drops M 0,54501 0,37897 0,30124 1,22522 0,46104 0,14704 0,04369 0,65177 0,25833 0,09700 0,02308 0,37842 2,255 25,06
31 PSO particle swarm optimisation 0,59726 0,36923 0,29928 1,26577 0,37237 0,16324 0,07010 0,60572 0,25667 0,08000 0,02157 0,35823 2,230 24,77
32 Boids boids algorithm 0,43340 0,30581 0,25425 0,99346 0,35718 0,20160 0,15708 0,71586 0,27846 0,14277 0,09834 0,51957 2,229 24,77
33 MA monkey algorithm 0,59107 0,42681 0,31816 1,33604 0,31138 0,14069 0,06612 0,51819 0,22833 0,08567 0,02790 0,34190 2,196 24,40
34 SFL shuffled frog-leaping 0,53925 0,35816 0,29809 1,19551 0,37141 0,11427 0,04051 0,52618 0,27167 0,08667 0,02402 0,38235 2,104 23,38
35 FSS fish school search 0,55669 0,39992 0,31172 1,26833 0,31009 0,11889 0,04569 0,47467 0,21167 0,07633 0,02488 0,31288 2,056 22,84
36 RND random 0,52033 0,36068 0,30133 1,18234 0,31335 0,11787 0,04354 0,47476 0,25333 0,07933 0,02382 0,35648 2,014 22,37
37 GWO grey wolf optimizer 0,59169 0,36561 0,29595 1,25326 0,24499 0,09047 0,03612 0,37158 0,27667 0,08567 0,02170 0,38403 2,009 22,32
38 CSS charged system search 0,44252 0,35454 0,35201 1,14907 0,24140 0,11345 0,06814 0,42299 0,18333 0,06300 0,02322 0,26955 1,842 20,46
39 EM electroMagnetism-like algorithm 0,46250 0,34594 0,32285 1,13129 0,21245 0,09783 0,10057 0,41085 0,15667 0,06033 0,02712 0,24412 1,786 19,85


Выводы

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

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

Tab

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

chart

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

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


Плюсы и минусы алгоритма кодового замка (CLA):

Плюсы:

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

Минусы:

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

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

Прикрепленные файлы |
CLA.ZIP (24.57 KB)
Последние комментарии | Перейти к обсуждению на форуме трейдеров (4)
fxsaber
fxsaber | 22 мая 2024 в 15:33

Все АО делают одинаковое количество расчетов ФФ?

Наверное, было бы полезно сравнить АО по среднему количеству расчетов ФФ, когда упирается в оптимум.


Это количество - скорость оптимизации.

Andrey Dik
Andrey Dik | 22 мая 2024 в 15:59
fxsaber #:

Все АО делают одинаковое количество расчетов ФФ?

Наверное, было бы полезно сравнить АО по среднему количеству расчетов ФФ, когда упирается в оптимум.


Это количество - скорость оптимизации.

Да, все АО выполняют в тестах одинаковое количество расчетов ФФ - 10000. У разных АО популяции разнятся, но тут просто изменяется количество эпох: 10000 / размер_популяции = количество_эпох.

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

fxsaber
fxsaber | 22 мая 2024 в 21:35
Andrey Dik #:

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

Поэтому говорил про среднее значение. Или науихудшее.

Andrey Dik
Andrey Dik | 22 мая 2024 в 21:50
fxsaber #:

Поэтому говорил про среднее значение. Или науихудшее.

Да, я тоже имел в виду среднее значение. Тут может быть полезным указание зоны, например, за сколько запусков ФФ, в среднем, попадает в зону 90%, 70%, 50%. Т.е., это, по сути, показатель неслучайности стратегии поиска, так как результаты первой эпохи заведомо случайны, соответственно чем выше результаты на каждой последующей эпохе, тем выше поисковые способности алгоритма. Можно так же измерять средний прирост сходимости с каждой последующей эпохой за указанное количество эпох.
Разрабатываем мультивалютный советник (Часть 12): Риск-менеджер как для проп-трейдинговых компаний Разрабатываем мультивалютный советник (Часть 12): Риск-менеджер как для проп-трейдинговых компаний
В разрабатываемом советнике у нас уже заложен определённый механизм контроля просадки. Но он имеет вероятностную природу, так как основывается на результатах тестирования на исторических ценовых данных. Поэтому просадка, хотя и с небольшой вероятностью, может иногда превышать максимальные ожидаемые значения. Попробуем добавить механизм, обеспечивающий гарантированное соблюдение заданного уровня просадки.
Нейросети — это просто (Часть 91): Прогнозирование в частотной области (FreDF) Нейросети — это просто (Часть 91): Прогнозирование в частотной области (FreDF)
Мы продолжаем рассмотрение темы анализ и прогнозирования временных рядов в частотной области. И в данной статье мы познакомимся с новым методом прогнозирования в частотной области, который может быть добавлен к многим, изученным нами ранее, алгоритмам.
Возможности Мастера MQL5, которые вам нужно знать (Часть 11): Числовые стены Возможности Мастера MQL5, которые вам нужно знать (Часть 11): Числовые стены
Числовые стены (Number Walls) — это вариант регистра сдвига с линейной обратной связью (Linear Shift Back Registers), который предварительно оценивает последовательности на предмет предсказуемости путем проверки на сходимость. Мы посмотрим, как эти идеи могут быть использованы в MQL5.
Создаем простой мультивалютный советник с использованием MQL5 (Часть 6): Два индикатора RSI пересекают линии друг друга Создаем простой мультивалютный советник с использованием MQL5 (Часть 6): Два индикатора RSI пересекают линии друг друга
Под мультивалютным советником в этой статье понимается советник, или торговый робот, который использует два индикатора RSI с пересекающимися линиями - быстрый RSI, который пересекается с медленным.