Алгоритм оптимизации, вдохновлённый охотой лисы — Fox-inspired Optimization Algorithm (FOX)
67
0
Содержание
Введение
В 2022 году был опубликован новый алгоритм Fox-inspired Optimization Algorithm (Mohammed, Rashid). Его авторы утверждают, что лиса, ныряющая в снег за мышью, обгоняет PSO, серых волков, китов и шимпанзе. Подобные заявления типичны: почти в каждой публикации новый алгоритм побеждает конкурентов, с которыми его сравнивают. Трейдеру при выборе оптимизатора трудно понять, какому из таких результатов доверять. Проверить их по формулам в логике алгоритма почти невозможно — за легендой о звуке, расстоянии и северо-восточном прыжке не видно, что алгоритм делает на самом деле.
От выбора оптимизатора зависит многое. Слабый алгоритм находит не лучшие параметры советника, а первую попавшуюся приличную точку, и трейдер принимает её за потолок стратегии. Алгоритм может хорошо выглядеть только на тех тестовых задачах, на которых его проверяли авторы.
Три из пяти классических функций — сфера, Растригин и Гриванк — имеют оптимум ровно в нуле, и именно на них FOX показывает свои самые впечатляющие результаты. Диапазоны торговых параметров устроены иначе: период от 5 до 200, уровень цены от 1.08 до 1.09, и ноль в них либо недостижим, либо бессмыслен.
Далее алгоритм переносится в C_AO без изменений и тестируется на стенде. Затем каждый механизм проверяется по отдельности: сначала ищется, что из легенды реально участвует в поиске, а что только занимает бюджет вычислений, и уже после этого меняется по одной вещи за раз.
Ключевой вопрос статьи прост: почему алгоритм, выигравший все сравнения в публикации авторов, на нашем стенде даёт 33% (у случайного поиска 24%), и что нужно поменять, чтобы он заработал.
Реализация алгоритма
Легенда. Рыжая лиса зимой не видит добычу под снегом. Она бродит наугад, пока не услышит мышь, затем по задержке звука оценивает расстояние и прыгает сверху. Биологи заметили, что прыжок на северо-восток удаётся примерно в 82% случаев, а в обратную сторону — в 18%. Из этого авторы собрали две фазы: случайное блуждание (исследование) и прыжок (эксплуатация), с вероятностью 50% каждая.
Что делает алгоритм на самом деле. В стае 30 лис. Алгоритм помнит одну лучшую точку, своей памяти у лис нет, и отбора тоже нет: новое положение принимается всегда, даже если оно хуже прежнего.
Каждую эпоху каждая лиса бросает монету. Если выпало блуждание, лиса встаёт в лучшую точку и делает от неё гауссов шаг, размер которого линейно уменьшается к концу поиска:
X = BestX + randn · MinT · a, a = 2 · (1 − it / MaxIt)
Если выпал прыжок, лиса берёт случайный вектор времён T из [0; 1], проецирует на него лучшую точку и умножает результат на маленькое число:
sps = <BestX, T> / <T, T> Dist = 0.5 · sps · T t = mean(T) / 2 Jump = 0.5 · 9.81 · t² X = Dist · Jump · c, c = 0.18 при p > 0.18, иначе 0.82
Вся физика — скорость звука, половина пути, ускорение свободного падения — сворачивается в один множитель около 0.03 или 0.13. Новая точка оказывается возле нуля координат, где бы ни находились лиса и лучшая точка. MinT — это минимальное за весь прогон среднее значение T, и обновляется он только в ветке прыжка.
Рисунок 1. Работа FOX по замыслу авторов
На иллюстрации серая рамка — область поиска, пунктирные оси проходят через начало координат (0, 0), зелёная звезда — оптимум, чёрная точка — лучшее найденное решение BestX. Синие точки — блуждание с вероятностью 0.5: гауссово облако вокруг BestX. Его радиус (синий пунктирный круг) задан в абсолютных единицах и одинаков для любого диапазона параметров. Синие кольца в углах — точки первой эпохи: пока MinT равен бесконечности, блуждание выбрасывает их на границы. Оранжевые точки — прыжок с вероятностью 0.5: лучшая точка проецируется и умножается на 0.03 или 0.13. Новые решения ложатся возле начала координат, на линии от (0, 0) к BestX, далеко от оптимума.
Псевдокод:
X[i] = U(lb, ub), BestScore = −inf, MinT = +inf для l = 0 .. MaxIt − 1: для каждой лисы i: отсечь X[i] по границам, оценить, обновить BestX a = 2 · (1 − l / MaxIt) для каждой лисы i: если U(0,1) ≥ 0.5: // прыжок T = U(0,1)^dim sps = <BestX, T> / <T, T> tt = mean(T), Jump = 0.5 · 9.81 · (tt / 2)² c = (U(0,1) > 0.18) ? c1 : c2 X[i] = 0.5 · sps · T · Jump · c MinT = min(MinT, tt) иначе: // блуждание X[i] = BestX + N(0,1)^dim · MinT · aГде код авторов расходится с их же статьёй. При переносе выяснилось, что опубликованные формулы и код авторов совпадают не везде. Реализация следует коду, потому что именно он давал результаты в публикации.
| Место | Статья | Код авторов |
|---|---|---|
| Параметр a, формула (8) | 2 · (it − 1/MaxIt) | 2 · (1 − l/MaxIt) |
| Блуждание, формула (9) | BestX · rand · MinT · a (произведение, равномерное) | BestX + randn · MinT · a (сумма, нормальное) |
| Скорость звука, формула (2) | поэлементное деление BestX / Time | матричное деление, результат — скаляр, проекция BestX на T |
| MinT, формула (7) | считается в фазе исследования | обновляется только при прыжке, стартует с бесконечности |
| Отбор | сравнение старого и нового решения | отбора нет, позиция заменяется всегда |
Отдельно стоит сказать о MinT. Пока ни одна лиса не прыгнула, он равен бесконечности, и блуждание выбрасывает координаты на границы. В обычном режиме это длится одну эпоху и на итог не влияет. Но из-за этой связи ветки нельзя отключить по отдельности: без прыжков MinT так и остаётся бесконечным.
Почему легенда скрывает слабость.Прыжок тянет точки к началу координат. Это подтверждают таблицы самих авторов: если разделить их тестовые функции по положению оптимума, картина получается очень показательной.
| Функция из публикации | Где оптимум | Результат FOX у авторов |
|---|---|---|
| Сфера | в нуле | 0 — точное решение, лучший среди всех |
| Растригин | в нуле | 0 — точное решение, лучший среди всех |
| Гриванк | в нуле | 0 — точное решение, лучший среди всех |
| Розенброк | в точке (1, …, 1) | 38.43 — худший среди шести алгоритмов |
| Швефель | около 420.97 по каждой координате | −6097.8 при глобальном минимуме около −12569.5 — лучше соперников, но вдвое хуже оптимума |
| CEC2019, функции 4–10 | сдвинуты и повёрнуты | лидер только в части функций, FDO лучше в 7 из 10 |
Три точных нуля приходятся ровно на те функции, где оптимум лежит в начале координат. Стоит оптимуму сместиться хотя бы в точку (1, …, 1), как у Розенброка, — и FOX оказывается последним. На сдвинутых функциях CEC2019 он уже не лидер. На функциях нашего стенда оптимум тоже не в нуле, и прыжок становится пустой тратой половины бюджета.
Авторская версия в нашем классе C_AO. Сначала алгоритм перенесён в C_AO без изменений, строго по коду авторов. Класс наследует C_AO и хранит позиции лис в массиве структур a[] базового класса.
Параметры: popSize — размер стаи (30, как у авторов); pExploit — вероятность прыжка (0.5); pDir — порог выбора направления (0.18); c1 и c2 — коэффициенты прыжка (0.18 и 0.82); fixMinT — стартовое значение MinT (0 — бесконечность, как у авторов; 1 — значение 0.5, его ожидаемое значение).
class C_AO_FOX : public C_AO { public: ~C_AO_FOX() {} C_AO_FOX() { ao_name = "FOX"; ao_desc = "Fox-inspired Optimization Algorithm"; ao_link = "https://www.mql5.com/ru/articles/"; popSize = 30; // размер популяции pExploit = 0.5; // вероятность ветки прыжка (r >= 0.5) pDir = 0.18; // порог направления прыжка (p > 0.18 -> c1) c1 = 0.18; // коэффициент прыжка на северо-восток c2 = 0.82; // коэффициент прыжка в обратную сторону fixMinT = false; // false — MinT = +inf на старте, как у авторов ArrayResize(params, 6); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "pExploit"; params [1].val = pExploit; params [2].name = "pDir"; params [2].val = pDir; params [3].name = "c1"; params [3].val = c1; params [4].name = "c2"; params [4].val = c2; params [5].name = "fixMinT"; params [5].val = fixMinT ? 1.0 : 0.0; } void SetParams() { popSize = (int)params [0].val; pExploit = params [1].val; pDir = params [2].val; c1 = params [3].val; c2 = params [4].val; fixMinT = params [5].val != 0.0; if(popSize < 1) popSize = 1; if(pExploit < 0.0) pExploit = 0.0; if(pExploit > 1.0) pExploit = 1.0; if(pDir < 0.0) pDir = 0.0; if(pDir > 1.0) pDir = 1.0; params [0].val = popSize; params [1].val = pExploit; params [2].val = pDir; params [3].val = c1; params [4].val = c2; params [5].val = fixMinT ? 1.0 : 0.0; } bool Init(const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0); void Moving(); void Revision(); //---------------------------------------------------------------- double pExploit; // доля шагов-прыжков double pDir; // порог выбора c1 / c2 double c1; double c2; bool fixMinT; // true — MinT стартует с 0.5 вместо +inf private: int epochs; // Max_iter int epochNow; // l double minT; // MinT, глобальный за весь прогон double tm []; // Time(i,:) — буфер текущего агента void Jump(int i, double c); void Walk(int i, double aCoef); double Gauss(); double RndOpen(); }; //+------------------------------------------------------------------+ //| Init | //+------------------------------------------------------------------+ bool C_AO_FOX::Init(const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0) { if(!StandardInit(rangeMinP, rangeMaxP, rangeStepP)) return false; epochs = epochsP > 0 ? epochsP : 1; epochNow = 0; minT = fixMinT ? 0.5 : DBL_MAX; // 0.5 = E[mean(U(0,1))] ArrayResize(tm, coords); return true; } //+------------------------------------------------------------------+ //| равномерное на (0; 1] | //+------------------------------------------------------------------+ double C_AO_FOX::RndOpen() { double r; do r = u.RNDprobab(); while(r <= 0.0); return r; } //+------------------------------------------------------------------+ //| N(0,1), Box-Muller | //+------------------------------------------------------------------+ double C_AO_FOX::Gauss() { return sqrt(-2.0 * log(RndOpen())) * cos(2.0 * M_PI * u.RNDprobab()); } //+------------------------------------------------------------------+ //| прыжок: X = 0.5 * proj_T(cB) * Jump * c | //+------------------------------------------------------------------+ void C_AO_FOX::Jump(int i, double c) { double dotBT = 0.0, dotTT = 0.0, sumT = 0.0; for(int k = 0; k < coords; k++) { tm [k] = u.RNDprobab(); dotBT += cB [k] * tm [k]; dotTT += tm [k] * tm [k]; sumT += tm [k]; } double sps = dotTT > 0.0 ? dotBT / dotTT : 0.0; double tt = sumT / coords; double t = tt / 2.0; double jump = 0.5 * 9.81 * t * t; double x; for(int k = 0; k < coords; k++) { x = 0.5 * sps * tm [k] * jump * c; // Distance_Fox_Rat * Jump * c a [i].c [k] = u.SeInDiSp(x, rangeMin [k], rangeMax [k], rangeStep [k]); } if(tt < minT) minT = tt; } //+------------------------------------------------------------------+ //| случайное блуждание: X = cB + randn * MinT * a | //| при MinT = +inf координата уходит на границу (как у авторов) | //+------------------------------------------------------------------+ void C_AO_FOX::Walk(int i, double aCoef) { double x; for(int k = 0; k < coords; k++) { x = cB [k] + Gauss() * minT * aCoef; a [i].c [k] = u.SeInDiSp(x, rangeMin [k], rangeMax [k], rangeStep [k]); } } //+------------------------------------------------------------------+ //| Moving | //+------------------------------------------------------------------+ void C_AO_FOX::Moving() { //--- первый прогон: стартовая популяция if(!revision) { for(int i = 0; i < popSize; i++) for(int c = 0; c < coords; c++) a [i].c [c] = u.SeInDiSp(u.RNDfromCI(rangeMin [c], rangeMax [c]), rangeMin [c], rangeMax [c], rangeStep [c]); return; } //--- одна итерация FOX = одна эпоха стенда double aCoef = 2.0 * (1.0 - (double)epochNow / epochs); for(int i = 0; i < popSize; i++) { if(u.RNDprobab() < pExploit) // r >= 0.5 Jump(i, u.RNDprobab() > pDir ? c1 : c2); else Walk(i, aCoef); } epochNow++; } //+------------------------------------------------------------------+ //| Revision | //| у FOX нет личной памяти и отбора: X перезаписывается целиком, | //| сохраняется только глобальный лучший | //+------------------------------------------------------------------+ void C_AO_FOX::Revision() { for(int i = 0; i < popSize; i++) { if(a [i].f > fB) { fB = a [i].f; ArrayCopy(cB, a [i].c, 0, 0, coords); } } if(!revision) revision = true; }
Результат авторской версии на стенде:
FOX|Fox-inspired Optimization Algorithm|30.0|0.5|0.18|0.18|0.82|0.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.5622864889901698
25 Hilly's; Func runs: 10000; result: 0.4286645591815209
500 Hilly's; Func runs: 10000; result: 0.2816065844212325
=============================
5 Forest's; Func runs: 10000; result: 0.5643415372578554
25 Forest's; Func runs: 10000; result: 0.25562416288808876
500 Forest's; Func runs: 10000; result: 0.06411584474910376
=============================
5 Megacity's; Func runs: 10000; result: 0.42800000000000005
25 Megacity's; Func runs: 10000; result: 0.2832
500 Megacity's; Func runs: 10000; result: 0.12313333333333439
=============================
All score: 2.99097 (33.23%)
Алгоритм, выигравший все сравнения в публикации, набирает 33% — заметно ниже FPA из прошлой статьи (49.16%).
Что мы улучшили. Чтобы понять, что в алгоритме работает, вклад каждой правки измерялся по отдельности: одна правка — один прогон, остальное без изменений. Все прогоны — 10 повторов, бюджет 10 000 вычислений функции, popSize 30.
Исправление MinT и вклад веток. Первым кандидатом был дефект MinT: он стартует с бесконечности, и первые блуждания выбрасывают координаты на границы. Затем проверялось, что даёт каждая ветка, если оставить её одну.| Вариант | pExploit | fixMinT | Итог |
|---|---|---|---|
| Авторский | 0.5 | 0 | 32.87% |
| MinT стартует с 0.5 | 0.5 | 1 | 32.92% |
| Мало прыжков | 0.1 | 0 | 33.14% |
| Только прыжки | 1.0 | 0 | 16.86% |
| Только блуждание | 0.0 | 0 | 16.54% |
Исправление MinT ничего не дало: бесконечность живёт одну эпоху, дальше MinT задаётся первыми же прыжками. Это отрицательный результат — дефект в коде есть, на итог он не влияет.
Прогон (только блуждание) оказался не тем, чем казался. Без прыжков MinT остаётся бесконечным навсегда, каждое блуждание выбрасывает координаты на границы, и поиск превращается в перебор углов гиперкуба. Поэтому эту строку нельзя читать как вклад прыжка: ветки связаны через MinT, и по отдельности их не отключить.
Остальное читается однозначно. Одни прыжки дают 17% — сами по себе они не ищут. Доля прыжков от 0.1 до 0.5 на итог почти не влияет: всю работу делает блуждание.
Шаг блуждания в долях диапазона. Раз работает только блуждание, его и нужно улучшать. Слабое место — сигма шага в абсолютных единицах: от 1 в начале до 0 в конце, одинаковая для любой функции. Для узкого диапазона такой шаг велик, для широкого мал.Гауссов шаг заменён на PowerDistribution со степенью 20 — готовую функцию из C_AO_Utilities. Шаг откладывается от лучшей точки в долях расстояния до границы: почти все шаги крошечные, но изредка случается шаг на весь диапазон. График сжатия при этом исчезает, форма шага одна на весь прогон. Результат поднялся с 33% до 50–52%.
Доля прыжков. После замены блуждание больше не зависит от MinT, и прогон без прыжков наконец стал корректным. Так как fixMinT теперь ни на что не влияет, прогоны с fixMinT = 0 и 1 — это повторы одной конфигурации; так они и сгруппированы.| pExploit | Прогоны | Среднее |
|---|---|---|
| 0.5 | 51.60, 50.44, 49.32, 50.48% | 50.46% |
| 0.0 | 51.65, 50.89% | 51.27% |
| 0.1 | 51.79, 52.54, 52.30% | 52.21% |
Разброс между одинаковыми прогонами доходит до 2 пунктов, и почти весь он приходится на тесты с 5 функциями: Megacity-5 гуляет от 0.67 до 0.81. Разница между долями 0.0 и 0.1 лежит внутри этого шума. Различие с авторской долей 0.5 устойчивее: на 25 функциях Forest поднимается с 0.48–0.51 до 0.54–0.57, Megacity — с 0.46 до 0.50, и так во всех прогонах. При доле 0.5 половина стаи тратит вычисления на точки возле нуля координат.
Рисунок 2. Работа FOX после изменений
Согласно иллюстрации блуждание (вероятность 0.9) использует степенное распределение по каждой координате отдельно. Большинство точек ложится вплотную к BestX, но изредка шаг уходит далеко вдоль одной из координат, вплоть до границы. Пунктирные линии min–max показывают, что дальность шага измеряется расстоянием до границ, то есть в масштабе самого диапазона. Прыжков стало впятеро меньше (вероятность 0.1), поэтому возле начала координат остаются лишь единичные точки.
Код итоговой реализации. Итоговый класс C_AO_FOX построен на той же основе, что и авторская версия, и отличается от неё одной строкой в методе Walk. Ниже класс разобран целиком, метод за методом.
Класс наследует C_AO. Позиции и пригодность лис хранятся в массиве структур a[] базового класса, лучшее решение — в cB и fB. Собственных структур алгоритму не понадобилось: у лис нет личной памяти, а промежуточные векторы прыжка нужны только на время перемещения одной лисы.
Открытые параметры: pExploit — вероятность прыжка; pDir — порог выбора направления прыжка; c1 и c2 — коэффициенты прыжка; fixMinT — стартовое значение MinT. Закрытые поля: epochs — общее число эпох (Max_iter у авторов); epochNow — номер текущей итерации (l); minT — минимальное среднее время за весь прогон; tm[] — буфер вектора времён текущей лисы.
SetParams. Метод переносит значения из params в поля класса и проверяет их. Размер стаи не может быть меньше единицы, вероятности pExploit и pDir ограничиваются отрезком [0; 1]. Исправленные значения записываются обратно в params, поэтому строка параметров в журнале теста всегда показывает то, с чем алгоритм реально работал.//+------------------------------------------------------------------+ //| | //+------------------------------------------------------------------+ class C_AO_FOX : public C_AO { public: ~C_AO_FOX() {} C_AO_FOX() { ao_name = "FOX"; ao_desc = "Fox-inspired Optimization Algorithm"; ao_link = "https://www.mql5.com/ru/articles/25488"; popSize = 30; // размер популяции pExploit = 0.5; // вероятность ветки прыжка (r >= 0.5) pDir = 0.18; // порог направления прыжка (p > 0.18 -> c1) c1 = 0.18; // коэффициент прыжка на северо-восток c2 = 0.82; // коэффициент прыжка в обратную сторону fixMinT = false; // false — MinT = +inf на старте, как у авторов ArrayResize(params, 6); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "pExploit"; params [1].val = pExploit; params [2].name = "pDir"; params [2].val = pDir; params [3].name = "c1"; params [3].val = c1; params [4].name = "c2"; params [4].val = c2; params [5].name = "fixMinT"; params [5].val = fixMinT ? 1.0 : 0.0; } void SetParams() { popSize = (int)params [0].val; pExploit = params [1].val; pDir = params [2].val; c1 = params [3].val; c2 = params [4].val; fixMinT = params [5].val != 0.0; if(popSize < 1) popSize = 1; if(pExploit < 0.0) pExploit = 0.0; if(pExploit > 1.0) pExploit = 1.0; if(pDir < 0.0) pDir = 0.0; if(pDir > 1.0) pDir = 1.0; params [0].val = popSize; params [1].val = pExploit; params [2].val = pDir; params [3].val = c1; params [4].val = c2; params [5].val = fixMinT ? 1.0 : 0.0; } bool Init(const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0); void Moving(); void Revision(); //---------------------------------------------------------------- double pExploit; // доля шагов-прыжков double pDir; // порог выбора c1 / c2 double c1; double c2; bool fixMinT; // true — MinT стартует с 0.5 вместо +inf private: int epochs; // Max_iter int epochNow; // l double minT; // MinT, глобальный за весь прогон double tm []; // Time(i,:) — буфер текущего агента void Jump(int i, double c); void Walk(int i, double aCoef); double Gauss(); double RndOpen(); };
Init вызывает стандартную инициализацию базового класса: она сохраняет диапазоны, создаёт массив лис и сбрасывает лучшее решение. Затем запоминается число эпох, обнуляется счётчик итераций и задаётся стартовое значение MinT: DBL_MAX вместо бесконечности, как у авторов, или 0.5, ожидаемое среднее равномерных чисел из [0; 1]. Буфер tm[] получает размер, равный числу координат.
//+------------------------------------------------------------------+ //| Init | //+------------------------------------------------------------------+ bool C_AO_FOX::Init(const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0) { if(!StandardInit(rangeMinP, rangeMaxP, rangeStepP)) return false; epochs = epochsP > 0 ? epochsP : 1; epochNow = 0; minT = fixMinT ? 0.5 : DBL_MAX; // 0.5 = E[mean(U(0,1))] ArrayResize(tm, coords); return true; }RndOpen и Gauss. Два вспомогательных генератора. RndOpen возвращает равномерное число из (0; 1], исключая ноль, потому что дальше от него берётся логарифм. Gauss строит нормальное число N(0, 1) по формуле Бокса — Мюллера. В итоговой версии Gauss больше не вызывается: он нужен только авторскому блужданию, которое оставлено в комментарии.
//+------------------------------------------------------------------+ //| равномерное на (0; 1] | //+------------------------------------------------------------------+ double C_AO_FOX::RndOpen() { double r; do r = u.RNDprobab(); while(r <= 0.0); return r; } //+------------------------------------------------------------------+ //| N(0,1), Box-Muller | //+------------------------------------------------------------------+ double C_AO_FOX::Gauss() { return sqrt(-2.0 * log(RndOpen())) * cos(2.0 * M_PI * u.RNDprobab()); }
Jump. Прыжок не изменился. Сначала заполняется случайный вектор времён tm[] из [0; 1] и одновременно считаются три суммы: скалярное произведение лучшей точки на tm, скалярный квадрат tm и сумма времён. Отношение первых двух — это sps. Затем по среднему времени считается высота прыжка 0.5 · 9.81 · t², и каждая координата новой позиции получается как половина проекции лучшей точки на tm, умноженная на высоту прыжка и коэффициент c. Позиция приводится к диапазону и шагу через SeInDiSp. В конце обновляется MinT.
//+------------------------------------------------------------------+ //| прыжок: X = 0.5 * proj_T(cB) * Jump * c | //+------------------------------------------------------------------+ void C_AO_FOX::Jump(int i, double c) { double dotBT = 0.0, dotTT = 0.0, sumT = 0.0; for(int k = 0; k < coords; k++) { tm [k] = u.RNDprobab(); dotBT += cB [k] * tm [k]; dotTT += tm [k] * tm [k]; sumT += tm [k]; } double sps = dotTT > 0.0 ? dotBT / dotTT : 0.0; double tt = sumT / coords; double t = tt / 2.0; double jump = 0.5 * 9.81 * t * t; double x; for(int k = 0; k < coords; k++) { x = 0.5 * sps * tm [k] * jump * c; // Distance_Fox_Rat * Jump * c a [i].c [k] = u.SeInDiSp(x, rangeMin [k], rangeMax [k], rangeStep [k]); } if(tt < minT) minT = tt; }Walk. Единственный изменённый метод. Авторский гауссов шаг с абсолютной сигмой оставлен в комментарии, вместо него каждая координата новой позиции берётся из степенного распределения вокруг лучшей точки. Аргумент aCoef и поле minT метод больше не читает, мы их сохранили, чтобы возврат к авторской версии занимал одну строку.
PowerDistribution — готовая функция из C_AO_Utilities. Она берёт случайное число r из [−1; 1], возводит |r| в степень 20 и откладывает результат от лучшей точки: при r > 0 — в долях расстояния до верхней границы, при r < 0 — до нижней. При степени 20 значение |r|^20 почти всегда близко к нулю и лишь изредка доходит до единицы. Получается мелкая доводка вокруг рекорда с редкими вылазками на весь диапазон, и всё в масштабе самого параметра.
//+------------------------------------------------------------------+ //| случайное блуждание: X = cB + randn * MinT * a | //| при MinT = +inf координата уходит на границу (как у авторов) | //+------------------------------------------------------------------+ void C_AO_FOX::Walk(int i, double aCoef) { double x; for(int k = 0; k < coords; k++) { //x = cB [k] + Gauss() * minT * aCoef; x = u.PowerDistribution (cB [k], rangeMin [k], rangeMax [k], 20); a [i].c [k] = u.SeInDiSp(x, rangeMin [k], rangeMax [k], rangeStep [k]); } }
Moving. При первом вызове флаг revision ещё не установлен, и метод создаёт стартовую популяцию: каждая координата каждой лисы выбирается равномерно в своём диапазоне. Дальше один вызов Moving — одна итерация FOX. Считается коэффициент a, который в итоговой версии используется только закомментированной авторской формулой, затем каждая лиса с вероятностью pExploit прыгает, а иначе блуждает. Направление прыжка выбирается вторым случайным числом: если оно больше pDir, берётся c1, иначе c2. В конце увеличивается счётчик итераций.
//+------------------------------------------------------------------+ //| Moving | //+------------------------------------------------------------------+ void C_AO_FOX::Moving() { //--- первый прогон: стартовая популяция if(!revision) { for(int i = 0; i < popSize; i++) for(int c = 0; c < coords; c++) a [i].c [c] = u.SeInDiSp(u.RNDfromCI(rangeMin [c], rangeMax [c]), rangeMin [c], rangeMax [c], rangeStep [c]); return; } //--- одна итерация FOX = одна эпоха стенда double aCoef = 2.0 * (1.0 - (double)epochNow / epochs); for(int i = 0; i < popSize; i++) { if(u.RNDprobab() < pExploit) // r >= 0.5 Jump(i, u.RNDprobab() > pDir ? c1 : c2); else Walk(i, aCoef); } epochNow++; }
Revision. После того как стенд посчитал пригодность всех лис, Revision ищет среди них решение лучше рекорда и копирует его в cB и fB. Отбора нет, как и у авторов: позиции лис не сравниваются со своими прежними, следующая итерация просто их перезаписывает. При первом вызове устанавливается флаг revision, и дальше Moving работает в обычном режиме.
//+------------------------------------------------------------------+ //| Revision | //| у FOX нет личной памяти и отбора: X перезаписывается целиком, | //| сохраняется только глобальный лучший | //+------------------------------------------------------------------+ void C_AO_FOX::Revision() { for(int i = 0; i < popSize; i++) { if(a [i].f > fB) { fB = a [i].f; ArrayCopy(cB, a [i].c, 0, 0, coords); } } if(!revision) revision = true; }
Итоговая конфигурация задаётся в тестовом скрипте: 30|0.1|0.18|0.18|0.82. После замены блуждания параметр fixMinT и коэффициент aCoef в поиске не участвуют: MinT по-прежнему обновляется в прыжке, но его никто не читает.
FOX|Fox-inspired Optimization Algorithm|30.0|0.1|0.18|0.18|0.82|1.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.7549337900579227
25 Hilly's; Func runs: 10000; result: 0.6234583123524393
500 Hilly's; Func runs: 10000; result: 0.288821766914745
=============================
5 Forest's; Func runs: 10000; result: 0.9986947688827552
25 Forest's; Func runs: 10000; result: 0.5468630490656631
500 Forest's; Func runs: 10000; result: 0.08518749849290573
=============================
5 Megacity's; Func runs: 10000; result: 0.7626666666666666
25 Megacity's; Func runs: 10000; result: 0.5095999999999998
500 Megacity's; Func runs: 10000; result: 0.1370533333333342
=============================
All score: 4.70728 (52.30%)
Проверка композитным тестом. На основном стенде каждая функция повторяется много раз: одна и та же пара координат с одним и тем же рельефом копируется 5, 25 или 500 раз. Алгоритм, который переносит значения между координатами, может этим воспользоваться: нашёл хорошее значение в одной паре — раздал его во все остальные, и на стенде это выглядит как сильный поиск. Для FOX такое подозрение обоснованно, потому что прыжок сворачивает все координаты лучшей точки в одно число sps и затем раздаёт его обратно по координатам.
Композитный тест убирает эти лазейки. Десять координат разбиты на пять пар, и каждая пара принадлежит своей функции — Hilly, Forest, Megacity, Peaks и Skin, со своими диапазонами и своим положением оптимума. Пригодность агента — среднее по всем пяти функциям. Общей диагонали и общего центра здесь нет, и алгоритм, который на них опирался, должен заметно потерять в результате.
FOX|Fox-inspired Optimization Algorithm|30.0|0.1|0.18|0.18|0.82|1.0|
=============================
Composite anti-cheat test: Hilly + Forest + Megacity + Peaks + Skin
Pairs: 5; Coordinates: 10; Epochs: 333; Repeats: 10
=============================
Run 1/10: 0.8533326243071251
Run 2/10: 0.7217738788895247
Run 3/10: 0.9845599120908016
Run 4/10: 0.7217738825280442
Run 5/10: 0.8936367453586047
Run 6/10: 0.8528223169207875
Run 7/10: 0.9866648653114923
Run 8/10: 0.9866526259274846
Run 9/10: 0.9865233793602057
Run 10/10: 0.8533305896088367
=============================
Average result: 0.8841070820 (88.41%)
=============================
Ориентиром служит 10-координатная часть основного стенда: среднее по Hilly 5, Forest 5 и Megacity 5 в итоговом прогоне составляет около 0.84. Композит дал 0.88 — не ниже, а немного выше, и разница лежит в пределах разброса: отдельные запуски дают от 0.72 до 0.99. Значит, итоговая версия не опирается на многократное повторение одной и той же функции, и при доле прыжков 0.1 смешивание координат через sps на результат заметно не влияет.
Но этот вывод касается только одного вида подмены. Композитный тест не выявляет притяжение к началу координат, потому что ни в стенде, ни в композите оптимум не находится в нуле. Здесь прыжок просто тратит бюджет впустую. На классических функциях, где оптимум находится в нуле, — сфере, Растригине, Гриванке и большинстве функций CEC2019 — тот же прыжок попадает прямо в цель, и алгоритм выглядит сильнее, чем он есть. Именно на таких функциях авторы и приводят свои сравнения. Было ли это сделано намеренно, сказать нельзя, но результат один: опубликованные победы FOX нельзя переносить на задачи, где оптимум лежит в другом месте.
В нашей итоговой версии изменено только блуждание, а прыжок остался авторским, без изменений. Поэтому называть FOX честным алгоритмом нельзя: он по-прежнему прыгает строго от начала координат. Это нужно помнить при его использовании. Если диапазоны параметров включают ноль и оптимум окажется рядом с ним, FOX найдёт его подозрительно легко. Если же сравнивать FOX с другими алгоритмами на функциях с оптимумом в нуле, сравнение будет обманчивым. На задачах трейдера, где ноль обычно вне диапазона или не имеет смысла, прыжок бесполезен, и его долю (во внешнем параметре) лучше держать малой.
Любопытна сама картина запусков. Значения собираются в три уровня — около 0.72, около 0.85 и около 0.99 — и почти точно повторяются. Это похоже на застревание в одних и тех же локальных экстремумах одной из пяти функций. Стая держится за единственную лучшую точку, и если та попала в ловушку, выбраться из неё алгоритму нечем: отбора и личной памяти у лис нет.
Как читать эти результаты. Правки в FOX подбирались на том же стенде, на котором потом измерялся итог, и у читателя может возникнуть закономерный вопрос: не подогнан ли алгоритм под конкретные функции? Здесь важно, что именно менялось. Ни одна правка не была перебором настроек в поисках лучшего числа. Каждая следовала из диагноза, поставленного на предыдущем шаге: прыжок не ищет — значит, работает только блуждание; шаг блуждания задан в абсолютных единицах — значит, его нужно привязать к диапазону параметра. Этот довод не зависит от того, какие функции стоят на стенде: шаг, не связанный с масштабом задачи, плох на любой задаче, где диапазоны параметров разные.Независимую проверку дал композитный тест. В нём участвуют функции Peaks и Skin, которые при выборе правок не использовались вовсе, а три знакомые функции стоят в других сочетаниях и с другими диапазонами. Итоговая версия набрала на нём 0.88 при ориентире 0.84 с основного стенда — переобучение под стенд дало бы обратную картину.
Кроме того, рейтинг серии устроен одинаково для всех алгоритмов: каждый настраивается и оценивается на одном и том же стенде по одному протоколу. Поэтому числа FOX сравнимы с числами остальных алгоритмов таблицы, но, как и для них, это результаты исследования на конкретном наборе задач, а не гарантия поведения на любой задаче.
Отдельно о степени 20 в PowerDistribution. Это значение выбрано эмпирически, и чувствительность к нему в этой статье не измерялась. Мы не утверждаем, что 20 — универсальный выбор. Утверждение статьи другое: шаг поиска должен измеряться в долях диапазона параметра и иметь тяжёлый хвост, то есть сочетать мелкую доводку с редкими дальними выходами. Степень распределения лишь задаёт, насколько редки эти выходы.
Теперь о разбросе. Стенд стохастический, и одна и та же конфигурация от прогона к прогону даёт немного разные числа. Ниже — средние и стандартные отклонения по всем прогонам, сделанным в ходе работы над статьёй.
| Конфигурация | Прогоны | Среднее | Стандартное отклонение |
|---|---|---|---|
| Авторская, pExploit 0.5 | 32.87, 32.92, 33.23% | 33.01% | 0.20 |
| Итоговая, pExploit 0.5 | 51.60, 50.44, 49.32, 50.48% | 50.46% | 0.93 |
| Итоговая, pExploit 0.0 | 51.65, 50.89% | 51.27% | 0.54 |
| Итоговая, pExploit 0.1 | 51.79, 52.54, 52.30% | 52.21% | 0.38 |
Разница между авторской и итоговой версией — около 19 пунктов при разбросе внутри групп меньше одного пункта. Такое различие не требует статистического теста, чтобы считать его реальным. Разница между долями прыжков 0.0 и 0.1 сопоставима с разбросом, и мы не утверждаем, что одна из них лучше другой. Итоговая версия выше FPA (49.16%) примерно на 3 пункта, что заметно больше разброса самого FOX; однако для FPA у нас есть только один прогон, поэтому точнее говорить, что итоговый FOX как минимум не уступает FPA.
Для воспроизведения важно знать, как считаются числа. Каждая строка журнала — среднее за 10 повторов лучшего найденного значения функции; функции стенда нормированы так, что глобальный максимум равен 1. All score — сумма девяти строк (три функции на три размерности), процент — та же сумма, делённая на 9 и умноженная на 100: например, 4.70728 / 9 · 100 = 52.30%. Генератор случайных чисел инициализируется в начале каждого прогона от счётчика микросекунд (MathSrand(GetMicrosecondCount()) в StandardInit), поэтому прогоны не повторяются бит в бит. Это сделано намеренно: стенд оценивает алгоритм на независимых запусках, и воспроизводимыми должны быть средние, а не отдельные траектории.
Визуализация работы алгоритма FOX.
FOX на тестовой функции Hilly
FOX на тестовой функции Forest
FOX на тестовой функции Megacity
FOX на функции Ackley
FOX на функции Peaks
По результатам тестирования алгоритм FOX представлен ознакомительно в нашей рейтинговой таблице лучших популяционных методов оптимизации.
| cc | AO | Description | Hilly | Hilly Final | Forest | Forest Final | Megacity (discrete) | Megacity Final | Final Result | % of MAX | ||||||
| 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | ||||||||
| 1 | ANS | across neighbourhood search | 1,00000 | 0,88228 | 0,40138 | 2,28366 | 1,00000 | 0,95281 | 0,28092 | 2,23373 | 0,94667 | 0,85733 | 0,22389 | 2,02789 | 6,545 | 72,72 |
| 2 | AMOm | animal migration optimization M | 0,91624 | 0,83603 | 0,46790 | 2,22017 | 0,98482 | 0,92010 | 0,36391 | 2,26883 | 0,91733 | 0,81707 | 0,25177 | 1,98617 | 6,475 | 71,94 |
| 3 | CLA | code lock algorithm (joo) | 0,95139 | 0,86199 | 0,37879 | 2,19217 | 0,99349 | 0,93500 | 0,26497 | 2,19346 | 0,93600 | 0,84267 | 0,24060 | 2,01927 | 6,405 | 71,17 |
| 4 | (P+O)ES | (P+O) evolution strategies | 0,86571 | 0,89539 | 0,39740 | 2,15850 | 0,97761 | 0,89820 | 0,26878 | 2,14459 | 0,92133 | 0,80240 | 0,23952 | 1,96325 | 6,266 | 69,62 |
| 5 | SDSm | stochastic diffusion search M | 0,95195 | 0,84944 | 0,36249 | 2,16388 | 0,98061 | 0,88457 | 0,22112 | 2,08630 | 0,92267 | 0,79013 | 0,21380 | 1,92660 | 6,177 | 68,63 |
| 6 | AAm | archery algorithm M | 0,84685 | 0,73320 | 0,42590 | 2,00595 | 0,96709 | 0,77837 | 0,27789 | 2,02335 | 0,86133 | 0,77707 | 0,28712 | 1,92552 | 5,955 | 66,17 |
| 7 | SIA | simulated isotropic annealing (joo) | 0,93543 | 0,86504 | 0,38483 | 2,18530 | 0,94069 | 0,80609 | 0,23835 | 1,98513 | 0,86400 | 0,66160 | 0,19536 | 1,72096 | 5,891 | 65,46 |
| 8 | TETA | time evolution travel algorithm (joo) | 0,91452 | 0,86369 | 0,25579 | 2,03400 | 0,99654 | 0,91291 | 0,14394 | 2,05339 | 0,85467 | 0,82213 | 0,10443 | 1,78123 | 5,869 | 65,21 |
| 9 | ESG | evolution of social groups (joo) | 0,98111 | 0,79857 | 0,31167 | 2,09135 | 0,98954 | 0,82270 | 0,15032 | 1,96256 | 0,92133 | 0,73440 | 0,15315 | 1,80888 | 5,863 | 65,14 |
| 10 | CTA | comet tail algorithm (joo) | 0,92435 | 0,86786 | 0,27838 | 2,07059 | 0,99039 | 0,84571 | 0,19448 | 2,03058 | 0,95467 | 0,69680 | 0,11008 | 1,76155 | 5,863 | 65,14 |
| 11 | COA | coyote_optimization_algorithm | 0,88909 | 0,70681 | 0,32718 | 1,92308 | 0,99467 | 0,85358 | 0,15152 | 1,99977 | 0,88533 | 0,71040 | 0,18981 | 1,78554 | 5,708 | 63,43 |
| 12 | CSBO | circulatory_system_based_optimization | 0,87793 | 0,79105 | 0,30025 | 1,96923 | 0,95026 | 0,88027 | 0,15364 | 1,98417 | 0,85813 | 0,71525 | 0,14777 | 1,72115 | 5,776 | 63,05 |
| 13 | ECBO | enhanced colliding bodies optimization | 0,94024 | 0,72363 | 0,32356 | 1,98743 | 0,99477 | 0,80291 | 0,13056 | 1,92824 | 0,87600 | 0,70160 | 0,17433 | 1,75193 | 5,668 | 62,98 |
| 14 | BCO(B) | bezier_curve-based_optimization | 0,99069 | 0,77836 | 0,30678 | 2,07583 | 0,98481 | 0,74554 | 0,13778 | 1,86813 | 0,96400 | 0,58773 | 0,14361 | 1,69534 | 5,639 | 62,66 |
| 15 | DA | dialectical algorithm | 0,93117 | 0,75400 | 0,26205 | 1,94722 | 0,98925 | 0,81375 | 0,08662 | 1,88962 | 0,92667 | 0,68107 | 0,11315 | 1,72089 | 5,558 | 61,76 |
| 16 | BBO | biogeography based optimization | 0,95876 | 0,70609 | 0,35752 | 2,02237 | 0,92981 | 0,70660 | 0,16970 | 1,80611 | 0,87467 | 0,63013 | 0,20813 | 1,71293 | 5,541 | 61,57 |
| 17 | BHAm | black hole algorithm M | 0,79558 | 0,76207 | 0,34682 | 1,90447 | 0,99836 | 0,75798 | 0,13826 | 1,89460 | 0,85067 | 0,64427 | 0,17020 | 1,66514 | 5,464 | 60,71 |
| 18 | HS | harmony search | 0,91420 | 0,69049 | 0,29924 | 1,90393 | 0,97627 | 0,73373 | 0,14193 | 1,85193 | 0,91733 | 0,62720 | 0,15364 | 1,69817 | 5,454 | 60,60 |
| 19 | RFO | royal flush optimization (joo) | 0,80989 | 0,74481 | 0,34546 | 1,90016 | 0,95251 | 0,77926 | 0,15185 | 1,88362 | 0,80400 | 0,66427 | 0,19071 | 1,65898 | 5,443 | 60,48 |
| 20 | BOAm | billiards optimization algorithm M | 0,76177 | 0,72421 | 0,25275 | 1,73873 | 0,90890 | 0,81960 | 0,28853 | 2,01703 | 0,83733 | 0,74613 | 0,09763 | 1,68109 | 5,437 | 60,41 |
| 21 | ASO | anarchy society optimization | 0,73070 | 0,73713 | 0,31195 | 1,77978 | 0,99732 | 0,87700 | 0,17619 | 2,05051 | 0,72000 | 0,68773 | 0,18988 | 1,59761 | 5,428 | 60,31 |
| 22 | OOAm | osprey_optimization_algorithm | 0,67372 | 0,68299 | 0,34866 | 1,70537 | 0,99999 | 0,86410 | 0,15774 | 2,02183 | 0,78933 | 0,70613 | 0,18442 | 1,67988 | 5,407 | 60,08 |
| 23 | EOm | extremal optimization_M | 0,76527 | 0,75205 | 0,31908 | 1,83640 | 0,99999 | 0,76426 | 0,12437 | 1,88862 | 0,84133 | 0,64133 | 0,15247 | 1,63513 | 5,360 | 59,56 |
| 24 | ACS | artificial cooperative search | 0,75545 | 0,77162 | 0,31653 | 1,84360 | 1,00000 | 0,80488 | 0,10705 | 1,91193 | 0,76933 | 0,60800 | 0,14157 | 1,51890 | 5,274 | 58,60 |
| 25 | SSG | saplings sowing and growing | 0,75436 | 0,63206 | 0,35935 | 1,74577 | 0,91907 | 0,69694 | 0,19755 | 1,81356 | 0,81867 | 0,60533 | 0,21347 | 1,63747 | 5,197 | 57,74 |
| 26 | AOSm | atomic orbital search M | 0,76184 | 0,68435 | 0,31344 | 1,75963 | 0,90015 | 0,80044 | 0,11501 | 1,81560 | 0,82800 | 0,63280 | 0,15696 | 1,61776 | 5,193 | 57,70 |
| 27 | TSEA | turtle shell evolution algorithm (joo) | 0,95809 | 0,64852 | 0,29571 | 1,90232 | 0,99522 | 0,58104 | 0,10542 | 1,68168 | 0,92133 | 0,52160 | 0,14567 | 1,58860 | 5,173 | 57,48 |
| 28 | DE | flow_direction_algorithm | 0,96398 | 0,62346 | 0,26089 | 1,84833 | 0,98482 | 0,77018 | 0,11459 | 1,86959 | 0,93067 | 0,36213 | 0,11000 | 1,40280 | 5,121 | 56,90 |
| 29 | BIO | blood inheritance optimization (joo) | 0,72580 | 0,66522 | 0,31228 | 1,70330 | 0,99995 | 0,68125 | 0,11540 | 1,79660 | 0,85467 | 0,59333 | 0,15364 | 1,60164 | 5,102 | 56,69 |
| 30 | (PO)ES | (PO) evolution strategies | 0,73972 | 0,58190 | 0,38896 | 1,71058 | 0,91199 | 0,59975 | 0,21262 | 1,72436 | 0,82400 | 0,56240 | 0,23432 | 1,62072 | 5,056 | 56,18 |
| 31 | BO | bonobo optimizer | 0,75555 | 0,64366 | 0,32657 | 1,72578 | 0,94332 | 0,70442 | 0,13999 | 1,78773 | 0,73467 | 0,61440 | 0,16728 | 1,51635 | 5,030 | 55,89 |
| 32 | SRA | successful restaurateur algorithm (joo) | 0,89010 | 0,63359 | 0,29115 | 1,81484 | 0,96634 | 0,55285 | 0,08914 | 1,60833 | 0,89333 | 0,52800 | 0,13911 | 1,56044 | 4,984 | 55,38 |
| 33 | FDAm | flow_direction_algorithm_M | 0,87573 | 0,58806 | 0,27135 | 1,73514 | 0,99997 | 0,64399 | 0,09633 | 1,74029 | 0,84267 | 0,48453 | 0,11888 | 1,44608 | 4,922 | 54,70 |
| 34 | CRO | chemical reaction optimisation | 0,91281 | 0,65681 | 0,29866 | 1,86828 | 0,90513 | 0,56020 | 0,10939 | 1,57472 | 0,82800 | 0,50133 | 0,14149 | 1,47082 | 4,914 | 54,60 |
| 35 | BCOm | bacterial chemotaxis optimization M | 0,82589 | 0,61733 | 0,31584 | 1,75906 | 0,95296 | 0,63718 | 0,11984 | 1,70998 | 0,76533 | 0,51653 | 0,15800 | 1,43986 | 4,909 | 54,54 |
| 36 | DOA | dream optimization algorithm | 0,78522 | 0,78121 | 0,36036 | 1,92679 | 0,61584 | 0,42117 | 0,12254 | 1,15955 | 0,86667 | 0,72587 | 0,21127 | 1,80381 | 4,890 | 54,33 |
| 37 | ABO | african buffalo optimization | 0,92295 | 0,62528 | 0,29885 | 1,84708 | 0,92992 | 0,57468 | 0,09372 | 1,59832 | 0,73333 | 0,51333 | 0,14324 | 1,38990 | 4,835 | 53,72 |
| 38 | BSA | bird swarm algorithm | 0,94432 | 0,67941 | 0,26401 | 1,88774 | 0,91649 | 0,65619 | 0,12054 | 1,69322 | 0,80933 | 0,33547 | 0,10652 | 1,25132 | 4,832 | 53,69 |
| 39 | TSm | tabu search M | 0,87806 | 0,61040 | 0,28993 | 1,77839 | 0,98116 | 0,52165 | 0,08544 | 1,58825 | 0,82667 | 0,49547 | 0,13552 | 1,45766 | 4,824 | 53,60 |
| 40 | BSA | backtracking search algorithm | 0,87128 | 0,53190 | 0,28675 | 1,68993 | 0,92408 | 0,51602 | 0,09153 | 1,53163 | 0,96000 | 0,47253 | 0,13760 | 1,57013 | 4,792 | 53,24 |
| 41 | BEA | bacterial_evolutionary_algorithm | 0,92170 | 0,59615 | 0,29340 | 1,81125 | 0,96906 | 0,44500 | 0,08233 | 1,49639 | 0,90533 | 0,43173 | 0,13676 | 1,47382 | 4,781 | 53,13 |
| 42 | BWOm | beluga_whale_optimization_M | 0,78488 | 0,56872 | 0,29557 | 1,64917 | 0,91370 | 0,61760 | 0,12988 | 1,66118 | 0,81333 | 0,49946 | 0,15004 | 1,46283 | 4,773 | 53,04 |
| 43 | WOAm | whale optimization algorithm M | 0,93893 | 0,59477 | 0,26695 | 1,80065 | 0,98036 | 0,53873 | 0,07112 | 1,59021 | 0,78667 | 0,47600 | 0,11892 | 1,38159 | 4,772 | 53,02 |
| 44 | ACA | andean_condor_algorithm | 0,78444 | 0,53260 | 0,33108 | 1,64812 | 0,79071 | 0,44960 | 0,10685 | 1,34716 | 0,92266 | 0,67733 | 0,17613 | 1,77612 | 4,771 | 53,02 |
| 45 | CSO | competitive swarm optimizer | 0,85151 | 0,60786 | 0,29896 | 1,75833 | 0,84085 | 0,58491 | 0,11974 | 1,54550 | 0,80000 | 0,48560 | 0,14184 | 1,42744 | 4,731 | 52,57 |
| FOX | fox-inspired_optimization_algorithm | 0,75493 | 0,62345 | 0,28882 | 1,66720 | 0,99869 | 0,54686 | 0,08518 | 1,63073 | 0,76266 | 0,50959 | 0,13705 | 1,40930 | 4,707 | 52,30 | |
| RW | random walk | 0,49970 | 0,32333 | 0,25791 | 1,08094 | 0,30754 | 0,11470 | 0,04400 | 0,46624 | 0,36133 | 0,17013 | 0,10244 | 0,63390 | 2,181 | 24,23 | |
Выводы
FOX в авторском виде — это гауссов поиск вокруг лучшей точки со сжимающимся шагом, к которому добавлена ветка, притягивающая решения к нулю координат. Легенда о звуке и прыжке сворачивается в один постоянный множитель.
Самые сильные результаты публикации — точные нули на сфере, Растригине и Гриванке — получены на функциях с оптимумом в начале координат; там, где оптимум смещён (Розенброк, сдвинутые функции CEC2019), FOX выглядит заметно скромнее. На нашем стенде, где оптимум в другом месте, алгоритм набирает 33%.
Что удалось выяснить проверкой каждого механизма по отдельности:
- прыжок сам по себе не ищет (17%), а при авторской доле 0.5 отнимает половину бюджета;
- исправление стартового MinT ничего не меняет — дефект реальный, но живёт одну эпоху;
- вся работа приходится на блуждание, и его слабость — шаг в абсолютных единицах, не связанный с диапазоном параметра;
- замена шага на степенное распределение в долях диапазона даёт +19 пунктов, снижение доли прыжков до 0.1 — ещё 1–2;
- на 1000 переменных ни одна правка ничего не дала: без отбора и памяти агентов алгоритму не за что держаться.
Итоговая версия набирает в среднем около 52% (52.30% в таблицу рейтинга) и как минимум не уступает FPA (49.16%). Но честнее сказать, что от лисы в ней остался каркас (вернись к лучшей точке и шагни случайно), а результат определяется распределением шага.
Для трейдера отсюда два практических правила. Первое: прежде чем доверять победам нового алгоритма, проверьте, где у тестовых функций автора оптимум — если в нуле, механизм, тянущий к нулю, будет выглядеть гениальным. Диапазоны торговых параметров (период 5–200, уровень цены 1.08–1.09) от нуля далеки. Второе: шаг поиска должен измеряться в долях диапазона параметра, а не в абсолютных единицах. Одна эта правка подняла FOX с 33% до 52%.
Однако этого было недостаточно, чтобы получить место в рейтинговой таблице. Для желающих остаётся открытое поле для дальнейших экспериментов.
Рисунок 3. Цветовая градация алгоритмов по результатам соответствующих тестов
Рисунок 4. Гистограмма результатов тестирования алгоритмов (по шкале от 0 до 100: чем больше, тем лучше, где 100 — максимально возможный теоретический результат). В архиве приведёнскрипт для расчёта рейтинговой таблицы
Плюсы и минусы итоговой версии FOX
Плюсы:
- простая реализация: два вида перемещения, никакой сортировки и личной памяти агентов;
- быстрая работа: одна итерация линейна по числу лис и координат;
- высокие результаты на задачах малой и средней размерности (Forest 5 — практически точное решение, на 25 переменных лучше FPA во всех трёх функциях);
- шаг поиска измеряется в долях диапазона параметра, поэтому алгоритм не зависит от масштаба и положения диапазона.
Минусы:
- на 1000 переменных результат остаётся на уровне случайного поиска;
- нет отбора и памяти: вся стая держится за одну лучшую точку, что грозит застреванием на многоэкстремальных функциях;
- заметный разброс результатов между запусками, до 2 пунктов на тестах с 5 функциями;
- ветка прыжка тянет решения к нулю координат и при любой ненулевой доле тратит часть бюджета впустую;
К статье прикреплён архив с актуальными версиями кода алгоритмов. Автор статьи не несёт ответственности за абсолютную точность в описании канонических алгоритмов, во многие из них внесены изменения для улучшения поисковых возможностей. Выводы и суждения, представленные в статьях, основываются на результатах проведённых экспериментов.
Программы, используемые в статье
| # | Имя | Тип | Описание |
|---|---|---|---|
| 1 | #C_AO.mqh | Включаемый файл | Родительский класс популяционных алгоритмов оптимизации |
| 2 | #C_AO_enum.mqh | Включаемый файл | Перечисление популяционных алгоритмов оптимизации |
| 3 | TestFunctions.mqh | Включаемый файл | Библиотека тестовых функций |
| 4 | TestStandFunctions.mqh | Включаемый файл | Библиотека функций тестового стенда |
| 5 | TestStand3D.mqh | Включаемый файл | 3D-панель визуализации для тестового стенда |
| 6 | Utilities.mqh | Включаемый файл | Библиотека вспомогательных функций |
| 7 | CalculationTestResults.mqh | Включаемый файл | Скрипт для расчёта результатов в сравнительную таблицу |
| 8 | Test_AO_All.mq5 | Скрипт | Единый испытательный стенд для всех популяционных алгоритмов оптимизации |
| 9 | Test_AO_AntiCheat | Скрипт | Тест на читерство алгоритмов оптимизации |
| 10 | Simple use of population optimization algorithms.mq5 | Скрипт | Простой пример использования популяционных алгоритмов оптимизации без визуализации |
| 11 | Test_AO_FOX.mq5 | Скрипт | Испытательный стенд для FOX |
Предупреждение: все права на данные материалы принадлежат MetaQuotes Ltd. Полная или частичная перепечатка запрещена.
Данная статья написана пользователем сайта и отражает его личную точку зрения. Компания MetaQuotes Ltd не несет ответственности за достоверность представленной информации, а также за возможные последствия использования описанных решений, стратегий или рекомендаций.
Создание системы торговой аналитики (Часть 1): Основы и архитектура системы
Торговые инструменты MQL5 (Часть 33): Создание системы документации с расширенным форматированием для программ на языке MQL5
Как выявлять ликвидность на круглых ценовых уровнях в MQL5
От новичка до эксперта: Адаптивное управление рисками в стратегиях на основе ликвидности
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Вы принимаете политику сайта и условия использования