Модификация Алгоритма оптимизации динго — Dingo Optimization Algorithm M (DOAm)
53
0
Содержание
Введение
Зададимся вопросом, существуют ли такие метаэвристические популяционные алгоритмы, которые при ограниченном количестве итераций — 10 000, как в нашем случае, — способны показать 100% результат? Настолько мощная природа должна быть этого алгоритма, что иногда я сомневаюсь в возможности получить такой бриллиант для оптимизации. А что скажете вы?
Так вот, близкие алгоритмы для такой цели могут существовать, и сегодня мы познакомимся с одним из уникальных методов оптимизации, точнее модифицированной мной версии уже рассмотренного в предыдущей статье алгоритма оптимизации Dingo Optimization Algorithm, которая ставит нас ближе к выполнению такой трудной задачи.
Реализация алгоритма
При работе над алгоритмом оптимизации Dingo Optimization Algorithm, меня заинтересовал принцип моделирования охоты динго, который имеет несколько стратегий. Мы познакомились с этим алгоритмом и подробно разобрали принципы его работы. Тестирование алгоритма принесло среднее результаты, в рейтинговую таблицу он не попал, так как до порога входа ему не хватало набрать еще 20%. Казалось бы, можно отложить на полку и идти дальше. Однако, я решил попробовать поэкспериментировать с формулами, и вот что получилось в итоге:
Формула групповой атаки (Equation 2), версия авторов:
x⃗ᵢ(t+1) = β₁ · [Σₖ₌₁ⁿᵃ φ⃗ₖ(t)]/nₐ - x⃗*(t)
в новой, модифицированной версии будет:
a[agentIdx].c[c] = cB[c] + beta1 * sumAttack;
В формуле, как можно заметить, изменен знак — вместо вычитания лучшего решения используем сложение. Также метод вычисления sumAttack усложнен — делится на (na * coords), вместо простого "na".
Порог выживания в оригинальной версии: survival[r] <= 0.3, изменим его на survival[r] <= 0.01. Порог резко снижаем, это означает, что будем применять стратегии выживания только для самых "слабых" агентов.
Формула поиска падали (Equation 4), версия авторов алгоритма:
x⃗ᵢ(t+1) = ½ · e^β₂ · |x⃗ᵣ₁(t) - (-1)^σ · x⃗ᵢ(t)|
Новая версия:
a[agentIdx].c[c] = (MathExp(beta2) * a[r1].c[c] - sign * a[agentIdx].c[c]) / 2.0;
Теперь будет убран модуль (абсолютное значение), это позволит давать отрицательные координаты. Новая версия алгоритма также еще будет усреднять разницу позиций по всем координатам одновременно, а не покоординатно, как подразумевается у разработчиков.
Почему эти изменения могут улучшить работу алгоритма? Изменение знака в групповой атаке может создавать движение "к лучшему решению с учетом позиций других", а не "от лучшего", как у авторов. Снижение порога выживания позволяет большинству агентов использовать основные стратегии охоты, применяя выживание только в крайних случаях. Отсутствие модуля в формуле падали позволяет более свободное движение в пространстве поиска.
Рисунок 1. Модификации стратегий DOAm_dingo
Иллюстрация выше показывает ключевые отличия модифицированной версии от оригинальной, описанной авторами алгоритма: в групповой атаке движение осуществляется к лидеру, вместо движения от него, изменен порог выживания, снижен до 0.01, теперь поиск падали без модуля в формуле и усреднение производится по (na × coords), вместо просто (na). Модификации выделены красным цветом для наглядности.
Теперь приступим к описанию кода алгоритма и посмотрим, что у нас получилось. Класс "C_AO_DOAm_dingo" является специализированной версией базового класса "C_AO". Он представляет собой оптимизационный алгоритм, основанный на модификации поведении динго, поэтому "Dingo Optimization Algorithm M" класс наследует от" C_AO", что предполагает наличие у него базовой функциональности. Устанавливаем значения по умолчанию для ключевых параметров:
- popSize — (размер популяции, то есть количество динго): 50.
- P — (вероятность выбора между охотой и поиском падали): 0.5.
- Q — (вероятность выбора между групповой атакой и преследованием): 0.7.
- Init — отвечает за начальный запуск алгоритма, включая инициализацию агентов (динго) и их параметров, с использованием предоставленных диапазонов и шагов изменения.
- Moving — отвечает за основную фазу работы алгоритма, где агенты перемещаются и взаимодействуют в соответствии с правилами алгоритма.
- Revision — отвечает за пересмотр или оценку состояния алгоритма после определенного этапа или эпохи.
- P — вероятность, будет динго охотиться или искать падаль.
- Q — вероятность, будет динго участвовать в групповой атаке или преследовании.
- beta1, beta2 — используются для генерации случайных векторов или шагов в процессе оптимизации, с заданными диапазонами значений;
- naIni, naEnd — определяют минимальное и максимальное количество динго, участвующих в атаке, что может варьироваться;
- survival — массив, хранящий показатели "выживаемости" или приспособленности каждого динго.
- UpdateSurvivalRates — обновляет показатели выживаемости агентов;
- GroupAttack — реализует поведение групповой атаки;
- Persecution — реализует поведение преследования;
- Scavenger — реализует поведение поиска падали;
- SurvivalProcedure — процедура, связанная с выживанием агентов;
- GetAttackVector — получает вектор, определяющий направление атаки;
- CalculateAttackSum — вычисляет суммарный "эффект" атаки.
//———————————————————————————————————————————————————————————————————— class C_AO_DOAm_dingo : public C_AO { public: //---------------------------------------------------------- ~C_AO_DOAm_dingo () { } C_AO_DOAm_dingo () { ao_name = "DOAm"; ao_desc = "Dingo Optimization Algorithm M"; ao_link = "https://www.mql5.com/ru/articles/19187"; popSize = 50; // размер популяции (количество динго) P = 0.5; // вероятность охоты или поиска падали (Hunting or Scavenger rate) Q = 0.7; // вероятность групповой атаки или преследования (Group attack or persecution) ArrayResize (params, 3); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "P"; params [1].val = P; params [2].name = "Q"; params [2].val = Q; } void SetParams () { popSize = (int)params [0].val; P = params [1].val; Q = params [2].val; } bool Init (const double &rangeMinP [], // минимальные значения const double &rangeMaxP [], // максимальные значения const double &rangeStepP [], // шаг изменения const int epochsP = 0); // количество эпох void Moving (); void Revision (); //------------------------------------------------------------------ double P; // вероятность охоты или поиска падали double Q; // вероятность групповой атаки или преследования private: //--------------------------------------------------------- double beta1; // -2 < beta1 < 2 double beta2; // -1 < beta2 < 1 int naIni; // минимальное количество атакующих динго int naEnd; // максимальное количество атакующих динго double survival []; // массив показателей выживания // Вспомогательные методы void UpdateSurvivalRates (); void GroupAttack (int agentIdx, int na); void Persecution (int agentIdx); void Scavenger (int agentIdx); void SurvivalProcedure (int agentIdx); void GetAttackVector (int na, int &attackVector []); double CalculateAttackSum (int agentIdx, int na); }; //————————————————————————————————————————————————————————————————————
Этот метод предназначен для инициализации алгоритма "Dingo Optimization Algorithm M", он подготавливает алгоритм к работе, устанавливая начальные условия для процесса оптимизации, определяя, как динго будут формировать атакующие группы, и задавая начальное состояние их "выживаемости".
//———————————————————————————————————————————————————————————————————— //--- Инициализация bool C_AO_DOAm_dingo::Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0) { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //------------------------------------------------------------------ // Инициализация параметров алгоритма naIni = 2; // минимальное количество атакующих naEnd = popSize / naIni; // максимальное количество атакующих ArrayResize (survival, popSize); ArrayInitialize (survival, 1.0); return true; } //————————————————————————————————————————————————————————————————————
Метод "Moving" является основной функцией, отвечающей за выполнение одного шага (или итерации) алгоритма, он симулирует поведение стаи динго в процессе поиска оптимального решения. Метод динамически управляет поведением популяции динго, позволяя им исследовать пространство решений, используя различные стратегии, основанные на их "выживаемости" и вероятностных решениях. Более детальное описание основных методов было приведено в предыдущей статье. Здесь остановимся подробнее на специфических методах.
//———————————————————————————————————————————————————————————————————— //--- Основной шаг алгоритма void C_AO_DOAm_dingo::Moving () { // Начальная инициализация популяции if (!revision) { for (int i = 0; i < popSize; i++) { for (int j = 0; j < coords; j++) { a [i].c [j] = u.RNDfromCI (rangeMin [j], rangeMax [j]); a [i].c [j] = u.SeInDiSp (a [i].c [j], rangeMin [j], rangeMax [j], rangeStep [j]); } } revision = true; return; } //------------------------------------------------------------------ // Обновляем показатели выживания UpdateSurvivalRates (); // Обновляем параметры beta для текущей итерации //beta1 = -2.0 + 4.0 * u.RNDprobab (); //beta2 = -1.0 + 2.0 * u.RNDprobab (); beta1 = u.RNDfromCI (-2.0, 2.0); beta2 = u.RNDfromCI (-1.0, 1.0); // Основной цикл по всем динго for (int r = 0; r < popSize; r++) { // Проверяем показатель выживания (Section 2.2.4) //if (survival[r] <= 0.3) if (survival [r] <= 0.01) { // Стратегия 4: Процедура выживания (Eq. 6) SurvivalProcedure (r); } else { // Выбор между охотой и поиском падали if (u.RNDprobab () < P) // Если охота { if (u.RNDprobab () < Q) // Если групповая атака { // Стратегия 1: Групповая атака (Eq. 2) int na = naIni + (int)((naEnd - naIni) * u.RNDprobab ()); GroupAttack (r, na); } else // Преследование { // Стратегия 2: Преследование (Eq. 3) Persecution (r); } } else // Поиск падали { // Стратегия 3: Поиск падали (Eq. 4) Scavenger (r); } } } } //————————————————————————————————————————————————————————————————————
Метод "GroupAttack" реализует "Стратегию 1: Групповая атака". Эта стратегия применяется, когда динго решает атаковать добычу в составе группы. Первым делом вызывается вспомогательный метод "CalculateAttackSum". Он берет индекс текущего динго (agentIdx) и количество динго, участвующих в атаке (na), и вычисляет общую силу или направление атаки, суммируя вклады от всех участников. Результат этой сложной операции сохраняется в переменной "sumAttack".
Далее метод обновляет позицию (координаты) текущего динго. Метод итерирует по каждой координате "c" пространства поиска и вычисляет новое значение позиции динго. Обновленная формула выглядит следующим образом:
Новая координата = Координата лучшего решения + beta1 * суммарный вектор атаки
где:
- "cB [c]" представляет собой "c" -тую координату текущего лучшего решения, найденного в оптимизации,
- beta1 — коэффициент, регулирующий интенсивность или направление воздействия групповой атаки,
- sumAttack — результат, полученный на предыдущем шаге.
Полученное новое значение координаты затем "укладывается" в допустимые границы. Метод "u.SeInDiSp" гарантирует, что новое значение остается в пределах заданных минимальных (rangeMin) и максимальных (rangeMax) границ, учитывая при этом шаг (rangeStep) изменения.
В итоге, метод "GroupAttack" моделирует скоординированный поиск оптимального решения группой динго. Он агрегирует информацию от нескольких особей через "sumAttack", учитывает лучшее найденное решение "cB" и использует случайный коэффициент "beta1" для определения нового, потенциально более выгодного, положения динго в пространстве поиска.
//———————————————————————————————————————————————————————————————————— //--- Стратегия 1: Групповая атака (Eq. 2) void C_AO_DOAm_dingo::GroupAttack (int agentIdx, int na) { // Вычисляем суммарный вектор атаки double sumAttack = CalculateAttackSum (agentIdx, na); // Применяем формулу групповой атаки (Eq. 2) for (int c = 0; c < coords; c++) { // v = beta1 * sumatory - theBestVct a [agentIdx].c [c] = cB [c] + beta1 * sumAttack; a [agentIdx].c [c] = u.SeInDiSp (a [agentIdx].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } //————————————————————————————————————————————————————————————————————
Метод "CalculateAttackSum" предназначен для вычисления суммарного вектора атаки, который используется в "Стратегии 1: Групповая атака". Он определяет, как конкретный динго (agentIdx) будет взаимодействовать с другими динго, участвующими в групповой атаке (na).
Сначала метод создает временный список (attackVector), который будет содержать индексы динго, непосредственно участвующих в атаке. Размер этого списка определяется параметром "na" (число атакующих). Затем вызывается вспомогательный метод "GetAttackVector". Этот метод, полагаясь на текущее состояние популяции, выбирает "na" динго, которые будут участвовать в атаке, и записывает их индексы в "attackVector". Инициализируется некоторая переменная "sumatory" (сумматор) нулевым значением. Далее следует основной цикл, он итерирует по всем динго, участвующим в атаке: для каждого атакующего динго, чей индекс (attackerIdx) берется из "attackVector".
Внутри этого цикла идет еще один цикл, который проходится по всем координатам (c) пространства поиска (цикл: от "0" до "coords - 1"). В каждой координате вычисляется разница между позицией атакующего динго и позицией динго, для которого вычисляется суммарная атака. Эта разница затем делится на общее количество возможных участников атаки (na) и общее количество координат (coords), и добавляется к "sumatory".
Наконец, метод возвращает значение "sumatory". Это значение представляет собой усредненную разницу позиций между атакующими динго и целевым динго, скорректированную на количество участников и измерений. Это значение потом будет использовано для обновления позиции целевого динго в рамках групповой атаки.
Таким образом, "CalculateAttackSum" собирает информацию о текущих положениях динго, участвующих в совместной атаке, и выводит комплексную величину, которая отражает их общее смещение относительно атакуемого динго. Эта величина затем направляет движение атакуемого динго.
//———————————————————————————————————————————————————————————————————— //--- Вычисление суммы для групповой атаки double C_AO_DOAm_dingo::CalculateAttackSum (int agentIdx, int na) { // Создаем вектор атакующих динго int attackVector []; ArrayResize (attackVector, na); GetAttackVector (na, attackVector); // Вычисляем среднюю разницу позиций double sumatory = 0.0; for (int j = 0; j < na; j++) { int attackerIdx = attackVector [j]; // Вычисляем среднее по всем координатам for (int c = 0; c < coords; c++) { sumatory += (a [attackerIdx].c [c] - a [agentIdx].c [c]) / (na * coords); } } return sumatory; } //————————————————————————————————————————————————————————————————————
Метод "GetAttackVector" отвечает за формирование списка динго, которые будут непосредственно участвовать в групповой атаке. Он создает набор случайных, уникальных индексов, каждый из которых соответствует одному динго из всей популяции. Метод сначала устанавливает размер выходного массива "attackVector" равным заданному числу "na" (количество атакующих). Также инициализируется счетчик "c" равный нулю, который будет отслеживать, сколько динго уже было выбрано для атаки.
Метод входит в цикл, который будет продолжаться до тех пор, пока не будут выбраны "na" динго. В каждой итерации цикла генерируется случайный индекс (idx) динго из всей доступной популяции (от "0" до "popSize - 1"). Перед тем, как добавить сгенерированный индекс в список атакующих, происходит проверка. Методом перебираются уже выбранные индексы (от "0" до "c - 1") массива "attackVector". Если случайно сгенерированный индекс (idx) совпадает с каким-либо из ранее выбранных (т.е. attackVector [i] == idx), устанавливается флаг "found" в значение "истина". Если флаг остался "ложью" (то-есть, данный индекс еще не был выбран), то этот новый, уникальный индекс (idx) добавляется в массив "attackVector" под текущим индексом "c". После этого счетчик c увеличивается на единицу.
По сути, "GetAttackVector" отвечает за случайный выбор "na" уникальных динго из всей популяции, чтобы они могли сформировать атакующий отряд. Этот процесс гарантирует, что каждый динго в группе будет отличаться от других, что предотвращает дублирование и обеспечивает разнообразие в атакующей группе.
//———————————————————————————————————————————————————————————————————— //--- Формирование вектора атакующих динго void C_AO_DOAm_dingo::GetAttackVector (int na, int &attackVector []) { int c = 0; ArrayResize (attackVector, na); while (c < na) { int idx = u.RNDintInRange (0, popSize - 1); // Проверяем, что индекс не повторяется bool found = false; for (int i = 0; i < c; i++) { if (attackVector [i] == idx) { found = true; break; } } if (!found) { attackVector [c] = idx; c++; } } } //————————————————————————————————————————————————————————————————————
Метод "Persecution", реализует "Стратегию 2: Преследование". Цель этого метода — обновить позицию одного конкретного динго (agentIdx) таким образом, чтобы он начал преследование. Метод сначала выбирает случайного динго из всей популяции, индекс сохраняется в переменной "r1".
Далее следует цикл, который проходит по всем измерениям (c) пространства, в котором находятся динго. Для каждого измерения применяется следующая формула для расчета новой позиции динго (agentIdx): к базовой величине (cB [c]), которая представляет собой позицию лучшего динго, добавляется результат произведения трех величин: beta1 — коэффициента, контролирующего степень влияния преследования на MathExp, (beta2) — экспоненциальной функции от коэффициента beta2 и разницы между позицией выбранного случайного динго (a [r1].c [c]), и текущей позицией атакующего динго (a [agentIdx].c [c]) в данном измерении.
Новая позиция сразу же корректируется с помощью вспомогательной функции нормализации "u.SeInDiSp", которая гарантирует, что новая позиция останется в допустимых пределах от "rangeMin [c]" до "rangeMax [c]" для каждого измерения с учетом шага "rangeStep [c]".
В итоге, метод "Persecution" заставляет указанный динго (agentIdx) начать движение в сторону случайно выбранного другого динго (r1), при этом учитывая базовую лучшую позицию и используя параметры "beta1" и "beta2" для регулирования силы и динамики этого преследования. При этом новое положение всегда остается в строгих границах пространства поиска.
//———————————————————————————————————————————————————————————————————— //--- Стратегия 2: Преследование (Eq. 3) void C_AO_DOAm_dingo::Persecution (int agentIdx) { // Выбираем случайного динго int r1 = u.RNDintInRange (0, popSize - 1); // Применяем формулу преследования (Eq. 3) for (int c = 0; c < coords; c++) { // v = theBestVct + beta1 * exp(beta2) * (Positions[r1] - Positions[r]) a [agentIdx].c [c] = cB [c] + beta1 * MathExp (beta2) * (a [r1].c [c] - a [agentIdx].c [c]); a [agentIdx].c [c] = u.SeInDiSp (a [agentIdx].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } //————————————————————————————————————————————————————————————————————
Метод "Scavenger" реализует "Стратегию 3: Поиск падали". Задача этого метода — обновить позицию одного конкретного динго (agentIdx), чтобы он переместился в новой позиции, которая является своего рода "компромиссом" или "медианным" значением между его текущим положением и позицией случайно выбранного другого динго.
Метод сначала выбирает случайного динго из всей популяции, и его индекс сохраняется в переменной "r1". Этот динго будет выступать в качестве некоторой точки отсчета. Также генерируется случайное бинарное значение (sign). Это значение будет либо "1.0", либо "-1.0". Это определяет, будет ли использоваться "прямое" вычитание разницы или "обратное".
Далее следует цикл, он проходит по всем измерениям пространства, в котором находятся динго. Для каждого измерения новая позиция динго (agentIdx) вычисляется следующим образом: берется позиция случайно выбранного динго (a [r1].c [c]) и умножается на экспоненту от коэффициента "beta2", из этого значения вычитается (или прибавляется, в зависимости от sign) текущая позиция атакующего динго, и полученный результат делится на 2.0.
Это фактически означает, что новая позиция будет находиться где-то между текущей позицией динго и новой "привлекательной" позицией, зависящей от "beta2" и выбранного соперника. Как и в других методах, после вычисления новой позиции, она сразу же корректируется с помощью вспомогательной функции "u.SeInDiSp". Эта функция гарантирует, что новая позиция остается в допустимых пределах (от "rangeMin [c]" до "rangeMax [c]") для каждого измерения.
Таким образом, метод "Scavenger" обновляет позицию динго, перемещая его в точку, которая является средней между его текущим положением и позицией, определяемой с помощью экспоненциальной трансформации положения другого динго и случайного знака. Это имитирует поведение животного, ищущего добычу, которая может находиться "по пути" или "где-то между" известными точками.
//———————————————————————————————————————————————————————————————————— //--- Стратегия 3: Поиск падали (Eq. 4) void C_AO_DOAm_dingo::Scavenger (int agentIdx) { // Выбираем случайного динго int r1 = u.RNDintInRange (0, popSize - 1); double sign = u.RNDbool() ? 1.0 : -1.0; // Применяем формулу поиска падали (Eq. 4) for (int c = 0; c < coords; c++) { // v = (exp(beta2) * Positions[r1] - (-1)^binary * Positions[r]) / 2 a [agentIdx].c [c] = (MathExp (beta2) * a [r1].c [c] - sign * a [agentIdx].c [c]) / 2.0; a [agentIdx].c [c] = u.SeInDiSp (a [agentIdx].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } //————————————————————————————————————————————————————————————————————
Метод "SurvivalProcedure" реализует "Стратегию 4: Процедура выживания". Основная цель этого метода — обновить позицию одного конкретного динго (agentIdx), используя информацию от двух других динго для нахождения новой, более выгодной позиции. Метод сначала выбирает двух различных случайных динго из всей популяции. Их индексы сохраняются в переменные "r1" и "r2". Гарантируется, что "r1" и "r2" не совпадают.
Также генерируется случайное бинарное значение (sign), которое может быть равно "1.0" или "-1.0". Оно определяет, будет ли вычитаться позиция второго динго с прямым знаком или с инвертированным. Далее следует цикл, проходящий по всем измерениям пространства, и для каждого измерения новая позиция динго вычисляется следующим образом: к лучшей найденной позиции (cB [c]), добавляется половина разницы между позицией первого случайного динго (a [r1].c [c]) и позицией второго случайного динго (a[r2]. c[c]), при этом знак позиции второго динго может быть инвертирован в зависимости от "sign". После вычисления новой позиции, она обязательно корректируется с помощью вспомогательной функции "SeInDiSp".
В целом, метод "SurvivalProcedure" демонстрирует стратегию, когда динго обновляет свою позицию, вычисляя ее как вариацию от лучшей найденной позиции, добавляя к ней половину разницы между позициями двух других случайно выбранных динго. Случайный знак добавляет элемент непредсказуемости в выбор направления для этой разницы, а ограничение позиции гарантирует, что динго остается в своей рабочей области. Это можно интерпретировать, как попытку найти "среднее" между двумя другими потенциальными "выгодными" точками, учитывая при этом лучшую известную позицию.
//———————————————————————————————————————————————————————————————————— //--- Стратегия 4: Процедура выживания (Eq. 6) void C_AO_DOAm_dingo::SurvivalProcedure (int agentIdx) { // Выбираем два разных случайных динго int r1, r2; do { r1 = u.RNDintInRange (0, popSize - 1); r2 = u.RNDintInRange (0, popSize - 1); } while (r1 == r2); double sign = u.RNDbool() ? 1.0 : -1.0; // Применяем формулу выживания (Eq. 6) for (int c = 0; c < coords; c++) { // v = theBestVct + (Positions[r1] - (-1)^binary * Positions[r2]) / 2 a [agentIdx].c [c] = cB [c] + (a [r1].c [c] - sign * a [r2].c [c]) / 2.0; a [agentIdx].c [c] = u.SeInDiSp (a [agentIdx].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } //————————————————————————————————————————————————————————————————————
Метод "UpdateSurvivalRates" отвечает за расчет и обновление "показателей выживания" для каждого динго в популяции. Эти показатели определяют вероятность того, что динго будет выбран для участия в следующей эволюционной итерации.
Сначала метод инициализирует две переменные: "minFitness" и "maxFitness". Затем он проходит в цикле по всем динго в популяции. Для каждого динго сравнивается его текущее значение приспособленности (a [i].f) с текущими "minFitness" и "maxFitness". Если текущая приспособленность меньше "minFitness", "minFitness" обновляется. Если текущая приспособленность больше "maxFitness", "maxFitness" обновляется. В результате этого цикла "minFitness" будет содержать наименьшее значение приспособленности во всей популяции, а "maxFitness" — наибольшее.
Если разница между "maxFitness" и "minFitness" очень мала (практически равна нулю, что означает, что все динго имеют одинаковую приспособленность), то всем динго присваивается показатель выживания, равный "0.5". Это предотвращает деление на ноль и устанавливает равные шансы для всех.
Если приспособленность динго различается, метод снова проходит в цикле по всем динго. Для каждого динго вычисляется его показатель выживания (survival [i]). Формула для этого показателя следующая: (maxFitness - a [i].f) / (maxFitness - minFitness). Эта формула нормирует значение приспособленности динго относительно диапазона всех значений приспособленности.
Динго с наименьшей приспособленностью, близкой к "minFitness" получит показатель выживания, близкий к 1.0 (поскольку maxFitness - a [i].f будет большим). Динго с наибольшей приспособленностью, близкой к "maxFitness" получит показатель выживания, близкий к 0.0 (поскольку maxFitness - a [i].f будет близко к нулю).
В итоге, метод UpdateSurvivalRates преобразует абсолютные значения приспособленности динго в относительные "оценки выживания", где более высокие значения приспособленности соответствуют более низким показателям выживания, и наоборот. Это может быть интерпретировано как стратегия, где те, кто "страдает" (имеет низкую приспособленность), имеют больший шанс "выжить" или измениться, в то время как наиболее "успешные" (с высокой приспособленностью) имеют меньше стимулов для изменения.
//———————————————————————————————————————————————————————————————————— //--- Обновление показателей выживания void C_AO_DOAm_dingo::UpdateSurvivalRates () { // Находим минимальный и максимальный fitness double minFitness = DBL_MAX; double maxFitness = -DBL_MAX; for (int i = 0; i < popSize; i++) { if (a [i].f < minFitness) minFitness = a [i].f; if (a [i].f > maxFitness) maxFitness = a [i].f; } // Вычисляем показатели выживания if (MathAbs (maxFitness - minFitness) < DBL_EPSILON) { ArrayInitialize (survival, 0.5); } else { for (int i = 0; i < popSize; i++) { // survival_rate = (max - fit) / (max - min) survival [i] = (maxFitness - a [i].f) / (maxFitness - minFitness); } } } //————————————————————————————————————————————————————————————————————
Метод "Revision" фокусируется на поиске наилучшего динго в текущей популяции после сортировки и, если этот динго превосходит ранее известные лучшие результаты, обновляет глобальные показатели лучшего решения. Это стандартная процедура для алгоритмов оптимизации, направленная на сохранение и отслеживание наилучшего найденного решения на протяжении всего процесса поиска.
//———————————————————————————————————————————————————————————————————— //--- Обновление лучшего и худшего решений void C_AO_DOAm_dingo::Revision () { // Сортируем популяцию для нахождения лучших и худших static S_AO_Agent aT []; ArrayResize (aT, popSize); u.Sorting (a, aT, popSize); // Обновляем глобальное лучшее решение if (a [0].f > fB) { fB = a [0].f; ArrayCopy (cB, a [0].c, 0, 0, WHOLE_ARRAY); } } //————————————————————————————————————————————————————————————————————
Результаты тестов
Результаты 50 запусков, вместо обычных 10 (чтобы нивелировать отличные, но случайные результаты)
DOA|Dingo Optimization Algorithm|50.0|0.5|0.7|
=============================
5 Hilly's; Func runs: 10000; result: 0.4796838225601811
25 Hilly's; Func runs: 10000; result: 0.4536754883347326
500 Hilly's; Func runs: 10000; result: 0.4636906699500103
=============================
5 Forest's; Func runs: 10000; result: 0.9414536230352631
25 Forest's; Func runs: 10000; result: 0.8790978288567921
500 Forest's; Func runs: 10000; result: 0.9145376343407303
=============================
5 Megacity's; Func runs: 10000; result: 0.7861538461538461
25 Megacity's; Func runs: 10000; result: 0.8606153846153848
500 Megacity's; Func runs: 10000; result: 0.8480461538461537
=============================
All score: 6.62695 (73.63%)
На визуализации заметен сложный меняющийся рисунок в поисковой области, связанный с применением различных стратегий охоты (прослеживаются "фамильные черты диагональности", унаследованные от своего прародителя). Однако при высоких общих показателях наблюдается очень большой разброс в результатах на всех тестовых функциях.
DOAm_dingo на тестовой функции Hilly
DOAm_dingo на тестовой функции Forest
DOAm_dingo на тестовой функции Megacity
По итогам тестирования алгоритм DOAm_dingo занимает первое место в нашей рейтинговой таблице популяционных методов оптимизации.
| № | 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 | DOAm_dingo | dingo_optimization_algorithm_M | 0,47968 | 0,45367 | 0,46369 | 1,39704 | 0,94145 | 0,87909 | 0,91454 | 2,73508 | 0,78615 | 0,86061 | 0,84805 | 2,49481 | 6,627 | 73,63 |
| 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 | TETA | time evolution travel algorithm (joo) | 0,91362 | 0,82349 | 0,31990 | 2,05701 | 0,97096 | 0,89532 | 0,29324 | 2,15952 | 0,73462 | 0,68569 | 0,16021 | 1,58052 | 5,797 | 64,41 |
| 7 | 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 |
| 8 | BOAm | billiards optimization algorithm M | 0,95757 | 0,82599 | 0,25235 | 2,03590 | 1,00000 | 0,90036 | 0,30502 | 2,20538 | 0,73538 | 0,52523 | 0,09563 | 1,35625 | 5,598 | 62,19 |
| 9 | 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 |
| 10 | 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 |
| 11 | 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 |
| 12 | EOm | extremal_optimization_M | 0,76166 | 0,77242 | 0,31747 | 1,85155 | 0,99999 | 0,76751 | 0,23527 | 2,00277 | 0,74769 | 0,53969 | 0,14249 | 1,42987 | 5,284 | 58,71 |
| 13 | BBO | biogeography based optimization | 0,94912 | 0,69456 | 0,35031 | 1,99399 | 0,93820 | 0,67365 | 0,25682 | 1,86867 | 0,74615 | 0,48277 | 0,17369 | 1,40261 | 5,265 | 58,50 |
| 14 | 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 |
| 15 | DA | dialectical algorithm | 0,86183 | 0,70033 | 0,33724 | 1,89940 | 0,98163 | 0,72772 | 0,28718 | 1,99653 | 0,70308 | 0,45292 | 0,16367 | 1,31967 | 5,216 | 57,95 |
| 16 | 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 |
| 17 | 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 |
| 18 | RFO | royal flush optimization (joo) | 0,83361 | 0,73742 | 0,34629 | 1,91733 | 0,89424 | 0,73824 | 0,24098 | 1,87346 | 0,63154 | 0,50292 | 0,16421 | 1,29867 | 5,089 | 56,55 |
| 19 | 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 |
| 20 | 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 |
| 21 | BSA | backtracking_search_algorithm | 0,97309 | 0,54534 | 0,29098 | 1,80941 | 0,99999 | 0,58543 | 0,21747 | 1,80289 | 0,84769 | 0,36953 | 0,12978 | 1,34700 | 4,959 | 55,10 |
| 22 | 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 |
| 23 | SRA | successful restaurateur algorithm (joo) | 0,96883 | 0,63455 | 0,29217 | 1,89555 | 0,94637 | 0,55506 | 0,19124 | 1,69267 | 0,74923 | 0,44031 | 0,12526 | 1,31480 | 4,903 | 54,48 |
| 24 | 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 |
| 25 | BIO | blood inheritance optimization (joo) | 0,81568 | 0,65336 | 0,30877 | 1,77781 | 0,89937 | 0,65319 | 0,21760 | 1,77016 | 0,67846 | 0,47631 | 0,13902 | 1,29378 | 4,842 | 53,80 |
| 26 | DOA | dream_optimization_algorithm | 0,85556 | 0,70085 | 0,37280 | 1,92921 | 0,73421 | 0,48905 | 0,24147 | 1,46473 | 0,77231 | 0,47354 | 0,18561 | 1,43146 | 4,825 | 53,62 |
| 27 | 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 |
| 28 | DEA | dolphin_echolocation_algorithm | 0,75995 | 0,67572 | 0,34171 | 1,77738 | 0,89582 | 0,64223 | 0,23941 | 1,77746 | 0,61538 | 0,44031 | 0,15115 | 1,20684 | 4,762 | 52,91 |
| 29 | 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 |
| 30 | 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 |
| 31 | 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 |
| 32 | 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 |
| 33 | (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 |
| 34 | FBA | fractal-based Algorithm | 0,79000 | 0,65134 | 0,28965 | 1,73099 | 0,87158 | 0,56823 | 0,18877 | 1,62858 | 0,61077 | 0,46062 | 0,12398 | 1,19537 | 4,555 | 50,61 |
| 35 | 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 |
| 36 | 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 |
| 37 | 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 |
| 38 | 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 |
| 39 | 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 |
| 40 | CAm | camel algorithm M | 0,78684 | 0,56042 | 0,35133 | 1,69859 | 0,82772 | 0,56041 | 0,24336 | 1,63149 | 0,64846 | 0,33092 | 0,13418 | 1,11356 | 4,444 | 49,37 |
| 41 | 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 |
| 42 | CMAES | covariance_matrix_adaptation_evolution_strategy | 0,76258 | 0,72089 | 0,00000 | 1,48347 | 0,82056 | 0,79616 | 0,00000 | 1,61672 | 0,75846 | 0,49077 | 0,00000 | 1,24923 | 4,349 | 48,33 |
| 43 | DA_duelist | duelist_algorithm | 0,92782 | 0,53778 | 0,27792 | 1,74352 | 0,86957 | 0,47536 | 0,18193 | 1,52686 | 0,62153 | 0,33569 | 0,11715 | 1,07437 | 4,345 | 48,28 |
| 44 | 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 |
| 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 | |
Выводы
Рассмотренная модификация алгоритма DOA_dingo выделяется своими высокими поисковыми возможностями. Однако, следует учесть, что эти впечатляющие результаты являются усредненными значениями, полученными в серии испытаний. Это означает, что для обеспечения достаточного исследования пространства поиска, пользователю придется выполнять оптимизацию многократно.
Компенсируя свои преимущества, алгоритм демонстрирует весьма скромную скорость сходимости на гладких функциях. Тем не менее DOA_dingo является весьма полезным и перспективным методом. Я бы рекомендовал его использование для начального этапа поиска, с последующим переходом к более точным алгоритмам. Также крайне важно предварительно нормализовать все параметры к одному диапазону значений.
Рисунок 2. Цветовая градация алгоритмов по соответствующим тестам
Рисунок 3. Гистограмма результатов тестирования алгоритмов (по шкале от 0 до 100, чем больше, тем лучше, где 100 — максимально возможный теоретический результат, в архиве скрипт для расчета рейтинговой таблицы)
Плюсы и минусы алгоритма DOAm_dingo:
Плюсы:
- Быстрый.
- Очень высокие усреднённые результаты.
Минусы:
- Большой разброс результатов.
- Склонность к застреванию.
К статье прикреплён архив с актуальными версиями кодов алгоритмов. Автор статьи не несёт ответственности за абсолютную точность в описании канонических алгоритмов, во многие из них были внесены изменения для улучшения поисковых возможностей. Выводы и суждения, представленные в статьях, основываются на результатах проведённых экспериментов.
Программы, используемые в статье
| # | Имя | Тип | Описание |
|---|---|---|---|
| 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_DOAm_dingo.mq5 | Скрипт | Испытательный стенд для DOAm_dingo |
Предупреждение: все права на данные материалы принадлежат MetaQuotes Ltd. Полная или частичная перепечатка запрещена.
Данная статья написана пользователем сайта и отражает его личную точку зрения. Компания MetaQuotes Ltd не несет ответственности за достоверность представленной информации, а также за возможные последствия использования описанных решений, стратегий или рекомендаций.
Разработка инструментария для анализа движения цен (Часть 8): Панель метрик
Автоматизация торговых стратегий на MQL5 (Часть 3): система Zone Recovery RSI для динамического управления торговлей
Анализ стратегий внутридневной торговли на основе прорывов диапазона открытия
Нейросети в трейдинге: Устойчивые торговые сигналы в любых режимах рынка (Окончание)
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Вы принимаете политику сайта и условия использования