Алгоритм оптимизации на основе коронавируса — Corona Virus Optimization (CVO)
58
0
Содержание
Введение
Алгоритмов оптимизации, вдохновлённых природой, с каждым годом всё больше и почти каждая новая работа обещает быстрые и красивые графики сходимости. Трейдеру, который ищет, чем оптимизировать параметры своей торговой системы, всё труднее отделить действительно сильный инструмент от середняка, удачно поданного на лёгких низкоразмерных задачах. Corona Virus Optimization (CVO) построен на модели распространения коронавируса: заражённые особи передают симптомы восприимчивым, популяция инфицированных то разрастается, то обновляется при очередной удаче, а сила инфекции управляет масштабом шага поиска. Идея свежая, авторская статья показывает уверенные результаты — но как алгоритм поведёт себя на честном, едином для всех бенчмарке, без подбора удобных функций?
В этой статье я провожу CVO: от формул оригинала до рабочего кода в стандартном стенде C_AO. Поясняю устройство динамической популяции, смысл R0 и силы инфекции I/N, а также необходимые отступления от текста статьи. Главное из них — покоординатное возмущение, чтобы алгоритм не эксплуатировал диагональную симметрию тестовых функций. Затем — прогон по стандартному набору (Hilly, Forest, Megacity на 10, 50 и 1000 измерениях) и, что важнее результата, разбор: почему буквально точная реализация села на уровень случайного блуждания и что именно её оттуда вытаскивает.
К концу у вас будет не только готовая, совместимая с фреймворком реализация CVO и его честное место в общем рейтинге. Также более переносимая вещь — понимание, почему дословное следование опубликованной формуле порой даёт слабый результат, и как одно изменение возвращает алгоритму работоспособность.
Реализация алгоритма
CVO построен на эпидемиологической модели SIR (Susceptible–Infectious–Recovered). Популяция делится на восприимчивых, инфицированных и выздоровевших/умерших. Заражённый контактирует с восприимчивыми и передаёт им симптомы; если иммунитет восприимчивого слабее, чем у носителя, он заболевает и пополняет инфекционную популяцию. Со временем число заражённых растёт по базовому репродуктивному числу R0, а сила инфекции масштабирует интенсивность передачи. Носители с сильным иммунитетом выздоравливают или умирают и выбывают.
Перенос в оптимизацию у авторов такой: пациент — это решение, его симптомы — переменные задачи, а уровень иммунитета — значение функции приспособленности. Ключевой и поначалу контринтуитивный момент: слабый иммунитет = лучшее решение. Чем слабее иммунная система пациента, тем он ближе к оптимуму, поэтому GlobalBest хранит пациента с самым слабым иммунитетом за весь прогон, а LocalBest — самого слабого за текущую итерацию. Задача — минимизация: меньше значение иммунитета, лучше решение.
Остальные обозначения: basePop — стартовое число заражённых, nPop — потолок популяции, Iters — число итераций (повторений пандемии), R0 — сколько восприимчивых заражает один носитель, pop — вся инфекционная популяция, newPop — новые заражённые текущей итерации, ρ — контактность (принята равной 1).
Три формулы. Скорость передачи симптомов (Eq. 1):
τ = ρ · φ;
где ρ — контактность, φ — вероятность передачи симптома.
Сила инфекции (Eq. 2):
λ(I) = τ · (I / N);
где I — число инфицированных, N — общая популяция. То есть чем больше доля заражённых, тем сильнее инфекция и крупнее возмущение.
Для непрерывных задач φ берётся из стандартного нормального распределения через преобразование Бокса–Мюллера (Eq. 3):
Z = √(−2·ln U₁) · cos(2π·U₂), U₁, U₂ ~ U(0,1)
Подставив всё вместе, носитель x порождает восприимчивого, меняя каждый симптом независимо:
xₙₒв[j] = x[j] + ρ · Zⱼ · (I / N); с зажимом в [LB, UB]
Важно: Zⱼ своё на каждую координату — у автора прямо сказано, что каждый симптом изменяется случайно по отдельности, хотя передаются все одновременно.
Правило заражения (отбор). Для каждого восприимчивого считается иммунитет (фитнес). Если иммунитет восприимчивого слабее иммунитета носителя (f(xₙₒв) < f(x) — то есть лучше по задаче), он заражается и попадает в newPop. Восприимчивые с сильным иммунитетом "соблюдали протоколы" и в новую популяцию не идут. Заодно отслеживается LocalBest итерации.
Динамика популяции (конец итерации):
- если LocalBest < GlobalBest (нашли новое глобально лучшее) — GlobalBest обновляется, а вся pop заменяется на newPop;
- иначе newPop дописывается к pop (популяция растёт);
- если |pop| > nPop — pop сортируется по возрастанию иммунитета и оставляются лучшие nPop (остальные выздоровели/умерли).
Псевдокод алгоритма:
ρ = 1 pop ← basePop случайных решений в [LB, UB]; оценить GlobalBest ← лучший из pop для iter = 1..Iters: newPop ← ∅; LocalBest ← худшее для каждого носителя x из pop: повторить R0 раз: для каждой переменной j: Z ← BoxMuller() xₙₒв[j] ← зажим( x[j] + ρ·Z·(|newPop|/nPop), LB, UB ) f ← фитнес(xₙₒв) если f < фитнес(x): # слабее носителя → заражается newPop ← newPop ∪ {xₙₒв} если f < LocalBest: LocalBest ← xₙₒв если LocalBest < GlobalBest: GlobalBest ← LocalBest; pop ← newPop # замена иначе: pop ← pop ∪ newPop # рост если |pop| > nPop: сортировать pop по возрастанию фитнеса; оставить лучшие nPop вернуть GlobalBest
Простой пример (1 переменная). Носитель в x = 2.0, ρ = 1, на ранней итерации заражено мало, пусть I/N = 0.1. При R0 = 3 он порождает трёх восприимчивых с Z = {0.8, −1.5, 0.2}: шаги ρ·Z·(I/N) = {0.08, −0.15, 0.02}, новые точки {2.08, 1.85, 2.02}. Шаги крошечные — поиск локальный. По мере того как пандемия разрастается и I/N идёт к 1, тот же механизм даёт шаги порядка Z — поиск становится размашистым.
Отсюда два свойства канона, которые стоит держать в голове (разбирать будем позже): шаг растёт по мере заполнения популяции — противоположно классическому отжигу, где он затухает; а замена pop на newPop при улучшении сбрасывает популяцию и снова сжимает шаг. То есть застой расширяет поиск, удача — фокусирует.
От минимизации к максимизации. Всё описанное выше — в системе координат оригинала: слабейший иммунитет означает наименьшее значение функции, и оно же лучшее. Отбор оставляет более слабых иммунно, то есть пациентов с меньшим значением.
Фреймворк C_AO, в который мы переносим алгоритм, устроен наоборот — он максимизирует. Все тестовые функции серии нормированы так, что больший балл — лучше; глобально лучший fB — это максимум, а базовый класс и весь рейтинг исходят из "больше значит лучше". Чтобы CVO встроился в серию и честно сравнивался с остальными, он обязан работать в той же, конвенции максимизации.
Поэтому при переносе мы не меняем сам алгоритм — мы зеркалим направление всех сравнений, чтобы "лучше" везде значило "больше f". Соответствие такое:
- слабее иммунитет = лучше (min) → больше f = лучше (max);
- заражение: было f(восприимчивый) < f(носитель) → стало f(восприимчивый) >= f(носителя);
- обновление рекорда: было LocalBest < GlobalBest → стало LocalBest > GlobalBest;
- отсечение пула: была сортировка по возрастанию с отбором наименьших → стала по убыванию с отбором наибольших.
Механика при этом неизменна — динамический пул, R0-распространение, "заражается, если не хуже носителя", замена/рост/отсечение, рост шага по доле заражённых. Меняется только знак сравнения. Поэтому дальше в коде сравнения будут выглядеть зеркально формулировкам статьи, и это ожидаемо: мы считаем максимум там, где оригинал искал минимум.
Реализация в C_AO. Канонический CVO работает с динамической популяцией: pop то разрастается, то заменяется, и за одну итерацию порождается |pop| · R0 новых пациентов — число плавающее. А контракт тестового стенда C_AO жёсткий: за каждую эпоху стенд оценивает ровно ArraySize(a) = popSize агентов — вызывает Moving(), считает a[i].f через CalcFunc, вызывает Revision(), и так epochCount = NumbTestFuncRuns / popSize раз. Бюджет вычислений функции на эпоху фиксирован. Эти две модели — динамическая популяция и фиксированный бюджет — надо примирить.
Решение: popSize — это не популяция CVO, а бюджет восприимчивых на эпоху. За проход стенд оценивает popSize кандидатов — это восприимчивые, рождённые носителями. А сам инфекционный пул живёт отдельным внутренним состоянием inf[], переживает перезапись слотов a[] и растёт/сжимается по правилам CVO. Так суммарно FE = popSize · epochCount ≈ NumbTestFuncRuns, как у всех алгоритмов серии, и сравнение честное.
Особь пула — структура: симптомы (координаты) и иммунитет (фитнес) одной особи лежат вместе, в стиле S_AO_Agent.
//+------------------------------------------------------------------+ //| Structure | //+------------------------------------------------------------------+ struct S_CVO_Patient { double c []; double f; };
Сам класс объявляем целиком так — параметры с предохранителями и поля пула:
//+------------------------------------------------------------------+ //| Сlass | //+------------------------------------------------------------------+ class C_AO_CVO : public C_AO { public: ~C_AO_CVO() {} C_AO_CVO() { ao_name = "CVO"; ao_desc = "Corona Virus Optimization"; ao_link = "https://www.mql5.com/ru/articles/22887"; popSize = 50; // бюджет FE на эпоху (= кандидатов за проход) nPop = 200; // потолок инфекционной популяции basePop = 5; // стартовая инфекционная популяция R0 = 5; // потомков-восприимчивых на одного носителя rho = 0.1; // контактность: общий множитель масштаба λ ArrayResize(params, 5); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "nPop"; params [1].val = nPop; params [2].name = "basePop"; params [2].val = basePop; params [3].name = "R0"; params [3].val = R0; params [4].name = "rho"; params [4].val = rho; } void SetParams() { popSize = (int)params [0].val; nPop = (int)params [1].val; basePop = (int)params [2].val; R0 = (int)params [3].val; rho = params [4].val; //--- предохранители if(popSize < 1) popSize = 1; if(nPop < 1) nPop = 1; if(R0 < 1) R0 = 1; if(rho < 0.0) rho = 0.0; if(basePop < 1) basePop = 1; if(basePop > popSize) basePop = popSize; // пул засевается из 1-го батча if(basePop > nPop) basePop = nPop; } bool Init(const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0); void Moving(); void Revision(); //--- видимые параметры int nPop; // потолок инфекционной популяции int basePop; // стартовая инфекционная популяция int R0; // потомков на носителя double rho; // множитель масштаба λ private: //--- инфекционный пул (массив структур: координаты + фитнес вместе) S_CVO_Patient inf []; // [nPop] int infCount; // текущий размер пула (<= nPop) //--- привязка слота-кандидата к носителю int parentOf []; // [popSize] //--- временный пул пересборки S_CVO_Patient tmp []; // [nPop + popSize] //--- стандартное нормальное (Box-Muller), Eq.3 double Gauss(); //--- индексная сортировка по убыванию f void ArgSortDesc(const double &f [], int &idx [], const int count); };
Привязка слотов к носителям. В каноне каждый носитель заражает R0 восприимчивых. Под фиксированный бюджет это проецируется так: слот k рождается носителем p = (k / R0) % infCount, то есть R0 подряд идущих слотов делят одного носителя. Если пул больше, чем popSize/R0, размножаются только первые ceil(popSize/R0) носителей — а так как пул отсортирован по убыванию иммунитета, это лучшие. Если пул меньше — модуль заворачивает, носители переиспользуются. Получается элитарная проекция правила "каждый заражает R0" на фиксированный бюджет эпохи.
Init заполняет стартовые случайные координаты для каждого агента и один раз выделяет пул и буфер:
//+------------------------------------------------------------------+ //| Init | //+------------------------------------------------------------------+ bool C_AO_CVO::Init(const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0) { if(!StandardInit(rangeMinP, rangeMaxP, rangeStepP)) return false; //--- стартовый случайный батч в cP[] (оценится на первом проходе) for(int i = 0; i < popSize; i++) for(int c = 0; c < coords; c++) a [i].cP [c] = u.RNDfromCI(rangeMin [c], rangeMax [c]); //--- инфекционный пул и временный пул (массивы структур) ArrayResize(inf, nPop); for(int i = 0; i < nPop; i++) ArrayResize(inf [i].c, coords); ArrayResize(tmp, nPop + popSize); for(int i = 0; i < nPop + popSize; i++) ArrayResize(tmp [i].c, coords); ArrayResize(parentOf, popSize); infCount = 0; return true; }
Moving в рабочем проходе порождает popSize восприимчивых — каждый симптом по формуле статьи ( Eq.1·3 ), покоординатно. Шаг здесь абсолютный, буква в букву по статье — это версия для первого честного прогона; в разделе диагностики мы заменим ровно строку v:
//+------------------------------------------------------------------+ //| Moving | //+------------------------------------------------------------------+ void C_AO_CVO::Moving() { //--- первый прогон: cP -> c if(!revision) { for(int i = 0; i < popSize; i++) for(int c = 0; c < coords; c++) a [i].c [c] = u.SeInDiSp(a [i].cP [c], rangeMin [c], rangeMax [c], rangeStep [c]); return; } //--- генерация кандидатов-восприимчивых for(int k = 0; k < popSize; k++) { int denom = infCount > 0 ? infCount : 1; // защита от %0 int p = (k / R0) % denom; // носитель данного слота parentOf [k] = p; for(int c = 0; c < coords; c++) { double phi = Gauss(); // Eq.3, [D1] свой на координату double frac = (double)(infCount + k) / (double)nPop; // I/N, Eq.1*Eq.2, [D3] if(frac > 1.0) frac = 1.0; double lam = rho * phi * frac; // абсолютный шаг, ТОЧНО по статье (Eq.1*2*3) double v = inf [p].c [c] + lam; a [k].c [c] = u.SeInDiSp(v, rangeMin [c], rangeMax [c], rangeStep [c]); } } }
Revision берёт на себя весь конец итерации канона: обновление лучших, посев пула на первом проходе, отбор заражённых и пересборку популяции. Поскольку стенд максимизирует, все сравнения зеркальны статье — заражается тот, чей иммунитет не хуже носителя ( >= ), лучшие сортируются по убыванию:
//--- принятые восприимчивые: иммунитет не лучше носителя -> заразился // (читаем inf[p].f ДО перезаписи пула — наложения нет) for(int k = 0; k < popSize; k++) { int p = parentOf [k]; if(MathIsValidNumber(a [k].f) && a [k].f >= inf [p].f) { ArrayCopy(tmp [cnt].c, a [k].c, 0, 0, coords); tmp [cnt].f = a [k].f; cnt++; } }
Дальше — решение замена/рост и отсечение, ровно по канону, только в сторону максимума: при улучшении глобального рекорда пул заменяется новыми заражёнными, иначе к нему дописываются принятые восприимчивые, а при переполнении пул сортируется по убыванию приспособленности и отсекается до лучших nPop.
Gauss — нормальное по Бокс–Мюллеру (Eq. 3). Превращает два равномерных числа из (0,1) в стандартное нормальное; вызывается отдельно на каждую координату при генерации восприимчивого:
//+------------------------------------------------------------------+ //| Gauss — стандартное нормальное (Box-Muller) | //+------------------------------------------------------------------+ double C_AO_CVO::Gauss() { double u1 = u.RNDfromCI(0.0, 1.0); double u2 = u.RNDfromCI(0.0, 1.0); if(u1 < 1e-15) u1 = 1e-15; // защита от ln(0) return MathSqrt(-2.0 * MathLog(u1)) * MathCos(2.0 * M_PI * u2); }
ArgSortDesc — порядок индексов по убыванию f. Нужен в двух местах (посев и отсечение). Чтобы не таскать структуры, сортируем не сам пул, а плоский массив фитнесов, получая порядок индексов, по которому потом собираем:
//+------------------------------------------------------------------+ //| ArgSortDesc — порядок индексов по убыванию f | //+------------------------------------------------------------------+ void C_AO_CVO::ArgSortDesc(const double &f [], int &idx [], const int count) { for(int i = 0; i < count; i++) idx [i] = i; for(int i = 0; i < count - 1; i++) { int b = i; for(int j = i + 1; j < count; j++) if(f [idx [j]] > f [idx [b]]) b = j; if(b != i) { int t = idx [i]; idx [i] = idx [b]; idx [b] = t; } } }
Это сортировка выбором, O(count²), но count не превышает nPop + popSize и вызывается раз за эпоху — на фоне оценок функции накладные незаметны, зато код предельно прозрачен.
Результаты тестов
Прогоняем по стандартному набору серии: функции Hilly, Forest и Megacity на 10, 50 и 1000 переменных, бюджет 10000 обращений к функции, по 10 повторов, итоговый балл — нормированная доля от максимума. Шаг абсолютный, ровно по статье, контактность ρ = 1, как у авторов. Лучшая чистая конфигурация (popSize=50, nPop=100, basePop=20, R0=10):
CVO|Corona Virus Optimization|50.0|100.0|20.0|10.0|1.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.5811428685355893
25 Hilly's; Func runs: 10000; result: 0.3689998607642066
500 Hilly's; Func runs: 10000; result: 0.26725319445074575
=============================
5 Forest's; Func runs: 10000; result: 0.4021701300516501
25 Forest's; Func runs: 10000; result: 0.1679713459276718
500 Forest's; Func runs: 10000; result: 0.05216720027056517
=============================
5 Megacity's; Func runs: 10000; result: 0.4613333333333333
25 Megacity's; Func runs: 10000; result: 0.21520000000000006
500 Megacity's; Func runs: 10000; result: 0.11194666666666767
=============================
All score: 2.62818 (29.20%)
29.20%. Это уровень рядом со случайным блужданием — там, где сильные алгоритмы серии берут пятьдесят с лишним процентов. Видно и характерное: на 10 переменных результаты ещё приличные (0.58 на Hilly), но с ростом размерности всё быстро проседает — на 1000 переменных Forest падает до 0.05, фактически шум. Алгоритм почти не держит высокую размерность.
Прежде чем винить алгоритм, надо убедиться, что считает он корректно, а не сломан. Проверка — чувствительность к параметрам. При фиксированных basePop=10, R0=5 крутим контактность: ρ = 0.001 -> 18.40%; ρ = 0.1 -> 28.91%; ρ = 10 -> 24.93%.
Отклик гладкий и осмысленный: при крошечном ρ шаг почти нулевой, поиск замерзает (18%); при большом ρ шаг разболтан, скатывается к случайному (25%); оптимум — где-то в районе ρ ≈ 0.1…1. Аналогично реагирует на basePop и R0 (лучшее — basePop=20, R0=10 ). Будь логика порвана, был бы плоский мусор при любых параметрах. Раз есть внятный экстремум и отклик на настройку — механика жива и считает правильно. Потолок ~29% не баг реализации, а свойство самого метода в этой постановке.
Диагностика и правка. Вернёмся к формуле шага в её точном виде:
λ = ρ · φ · (I / N), xₙₒв[j] = x[j] + λ
Возмущение здесь — абсолютное, в сырых единицах координаты. При ρ = 1 и φ из стандартного нормального его величина порядка единицы (в хвостах — двойки-тройки), помноженная на долю заражённых от нуля до единицы. То есть типичный шаг — это смещение примерно на один-два по оси, независимо от того, что это за ось.
Вот тут и зарыта собака. Шаг не привязан к ширине области поиска, а функции бенчмарка живут на разных диапазонах. Грубо: если ось тянется, скажем, на двести единиц, то шаг порядка единицы — это полпроцента диапазона, алгоритм почти не двигается, ползёт на месте. Если ось всего пара единиц шириной — тот же шаг это половина всего диапазона, дикие прыжки, чистый случайный поиск. Один и тот же λ на одной функции — микрошаги, на другой — хаос. Отсюда и картина из прошлого раздела: на 10 переменных кое-как, а на 1000 — коллапс до уровня шума, потому что покрыть огромный объём фиксированным мелким абсолютным шагом невозможно.
Гипотезу легко проверить: если дело в масштабе, то привязка шага к ширине диапазона должна выправить ситуацию. Так и есть.
Правка от здравого смысла. Делаем шаг долей диапазона каждой координаты — одна строка в Moving :
// было (абсолют, буква статьи): double v = inf [p].c [c] + lam; // стало (доля диапазона координаты): double v = inf [p].c [c] + lam * (rangeMax [c] - rangeMin [c]);
Теперь λ — не единица по оси, а доля ширины оси, одинаковая по смыслу на всех функциях и на каждой координате. Масштабная инвариантность, которой не хватало.
Но за это надо переставить величину. С range-scaling прежний ρ = 1 даёт шаг во весь диапазон — ровно тот хаос, что мы только что описали (кстати, это объясняет, почему ранняя попытка масштабировать с ρ = 1 скатывалась в случайный поиск). Поэтому ρ = 0.1 : при полном пуле шаг ~0.1·φ·диапазон, то есть порядка 5–10% ширины оси — разумная величина для уточнения. Заодно подстроены пул и посев: nPop = 200 (больше потолок, и заодно меньше frac = (infCount+k)/nPop → мельче шаг → больше эксплуатации) и basePop = 5 (сфокусированный старт). Все три параметра тянут в одну сторону — к управляемому, привязанному к масштабу шагу.
CVO|Corona Virus Optimization|50.0|200.0|5.0|5.0|0.1|
=============================
5 Hilly's; Func runs: 10000; result: 0.5946817995500855
25 Hilly's; Func runs: 10000; result: 0.36906584070682485
500 Hilly's; Func runs: 10000; result: 0.26998944552451903
=============================
5 Forest's; Func runs: 10000; result: 0.5225857394828209
25 Forest's; Func runs: 10000; result: 0.19382751005851218
500 Forest's; Func runs: 10000; result: 0.053702157009133125
=============================
5 Megacity's; Func runs: 10000; result: 0.4413333333333334
25 Megacity's; Func runs: 10000; result: 0.2424
500 Megacity's; Func runs: 10000; result: 0.11301333333333437
=============================
All score: 2.80060 (31.12%)
Сильно ли мы отклонились. Формально — да, это отступление от буквы: статья прибавляет λ как есть, мы умножаем на ширину диапазона. Но отступление принципиальное, а не косметический чит, и вот почему. Во-первых, вся структура CVO нетронута — динамический пул, R0-распространение, заражение «если иммунитет не хуже носителя», замена/рост, отсечение, рост шага по доле заражённых. Поменялись только единицы возмущения: абсолют → доля диапазона. Во-вторых, если функции в статье были одного, умеренного масштаба, то абсолютный λ у авторов по факту и был разумной долей их диапазона — а в нашем ненормированном бенче эту долю приходится восстанавливать явно. То есть range-scaling ближе к замыслу (относительный шаг), чем дословная формула. И в-третьих, это стандартная конвенция всей твоей серии: все алгоритмы масштабируют шаг к диапазону, иначе сравнение между ними нечестное.
Честно про масштаб эффекта: +1.9% — это не превращение CVO в сильный алгоритм, а снятие масштабного штрафа, который держал его на дне рядом со случайным блужданием. Теперь он на своём честном потолке — низко-средний эшелон. И главный переносимый урок: реализуя любой опубликованный алгоритм, первым делом проверь, в каких единицах живёт его шаг. Абсолютное возмущение, выглядящее естественным на функциях одного масштаба, на разномасштабном бенче работает мимо — относительный шаг почти всегда то, что нужно.
Композитный тест на 10 переменных даёт 56.69%, но это другой, более лёгкий режим (только низкая размерность), и смешивать эти два числа нельзя — в рейтинг идут стандартные 31%.
CVO|Corona Virus Optimization|50.0|200.0|5.0|5.0|0.1|
=============================
Composite test: Hilly + Forest + Megacity + Peaks + Skin
Coordinates: 10; Epochs: 200; Repeats: 10
=============================
Run 1/10: 0.5598502390640241
Run 2/10: 0.46218834024270095
Run 3/10: 0.5472841349143641
Run 4/10: 0.6438002840259478
Run 5/10: 0.5363633183876485
Run 6/10: 0.6189199641420557
Run 7/10: 0.5775251324533818
Run 8/10: 0.5168167745601945
Run 9/10: 0.5741164838588073
Run 10/10: 0.6317059909142314
=============================
Average result: 0.5668570663 (56.69%)
=============================
Рисунок 1. Схема работы алгоритма CVO
На рисунке — одна итерация алгоритма в новой, масштабированной версии: пул носителей порождает восприимчивых (по R0 на носителя), те проходят отбор (заражается тот, чей иммунитет не хуже носителя), после чего пул обновляется — заменяется при улучшении, растёт при застое и отсекается до лучших nPop. На следующей итерации цикл повторяется.
Возмущение, которым носитель порождает восприимчивого, задаётся по формуле на иллюстрации. Величину шага определяет сила инфекции
λ = ρ · φ · (I / N);
здесь ρ — контактность, φ = Z_j — случайное число из стандартного нормального распределения (преобразование Бокса–Мюллера), своё на каждую координату j, а I / N — доля заражённых в популяции. Чем шире разрослась пандемия и больше I / N, тем крупнее шаг — возмущение нарастает по ходу заполнения пула.
Ключевое отличие от оригинала — последний множитель (UB_j − LB_j), выделенный на схеме оранжевым. В статье сила инфекции прибавляется к позиции напрямую, в абсолютных единицах координаты. Мы же домножаем её на ширину диапазона каждой координаты, и шаг из "стольких-то единиц по оси" превращается в долю поискового пространства. Это и есть правка от здравого смысла: один и тот же относительный шаг ведёт себя одинаково на функциях любого масштаба — не теряется в микронудж на широких диапазонах и не разносит поиск в случайный на узких. Структуру самого CVO это не трогает: меняются только единицы возмущения.
CVO на тестовой функции Hilly
CVO на тестовой функции Forest
CVO на тестовой функции Megacity
CVO на тестовой функции Ackley
CVO на тестовой функции Rosenbrock
В рейтинговую таблицу CVO не попадает и представлен только ознакомительно.
| 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 | 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 |
| 12 | 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 |
| 13 | 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 |
| 14 | 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 |
| 15 | 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 |
| 16 | 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 |
| 17 | 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 |
| 18 | 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 |
| 19 | 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 |
| 20 | 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 |
| 21 | 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 |
| 22 | 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 |
| 23 | 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 |
| 24 | DE | differential evolution | 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 |
| 25 | 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 |
| 26 | (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 |
| 27 | 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 |
| 28 | 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 |
| 29 | 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 |
| 30 | 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 |
| 31 | 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 |
| 32 | 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 |
| 33 | 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 |
| 34 | 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 |
| 35 | 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 |
| 38 | 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 |
| 36 | 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 |
| 37 | 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 |
| 39 | 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 |
| 40 | FBA | fractal-based algorithm | 0,69419 | 0,64267 | 0,28955 | 1,62641 | 0,99812 | 0,54905 | 0,08705 | 1,63422 | 0,76133 | 0,51253 | 0,13689 | 1,41075 | 4,671 | 51,90 |
| 41 | ECOi | eco-inspired evolutionary algorithm | 0,78817 | 0,54402 | 0,29360 | 1,62579 | 0,88996 | 0,46592 | 0,09747 | 1,45335 | 0,78533 | 0,45173 | 0,14295 | 1,38001 | 4,459 | 49,54 |
| 42 | BSO | brain storm optimization | 0,92207 | 0,57625 | 0,29732 | 1,79564 | 0,80764 | 0,42508 | 0,09448 | 1,32720 | 0,77200 | 0,36533 | 0,13065 | 1,26798 | 4,391 | 48,79 |
| 43 | CAm | camel algorithm M | 0,71534 | 0,56917 | 0,35985 | 1,64436 | 0,84094 | 0,47174 | 0,10850 | 1,42118 | 0,70400 | 0,41947 | 0,19563 | 1,31910 | 4,385 | 48,72 |
| 44 | ACOm | ant colony optimization_M | 0,71885 | 0,48410 | 0,30990 | 1,51285 | 0,75792 | 0,48639 | 0,11871 | 1,36302 | 0,83600 | 0,48667 | 0,16148 | 1,48415 | 4,360 | 48,44 |
| 45 | BSO | brain storm optimization | 0,91331 | 0,55813 | 0,29705 | 1,76849 | 0,85329 | 0,44038 | 0,09447 | 1,38814 | 0,72267 | 0,32880 | 0,13325 | 1,18472 | 4,341 | 48,23 |
| CVO | corona_virus_optimization | 0,59468 | 0,36906 | 0,26998 | 1,23372 | 0,52258 | 0,19382 | 0,05370 | 0,77010 | 0,44133 | 0,24240 | 0,11301 | 0,79674 | 2,801 | 31,12 | |
| 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 | |
Выводы
В общий рейтинг CVO входит со своим честным результатом — 31.12% на стандартном наборе после привязки шага к диапазону. Алгоритм заметно слабее лидеров серии.
Сильные стороны у CVO всё же есть. Он прост по идее и в реализации. В нём заложен любопытный адаптивный механизм: при застое популяция растёт, доля заражённых тянет шаг вверх — поиск расширяется; при удаче pop заменяется на свежих заражённых, сжимается, и шаг снова мельчает — поиск фокусируется. То есть неудача автоматически включает разведку, успех — уточнение. На низкой размерности это работает.
Слабости перевешивают и хорошо видны по числам. Главная — обвал на высокой размерности: на 1000 переменных результаты падают до уровня шума, и никакое масштабирование шага это не лечит, потому что причина глубже. У CVO нет прямого притяжения к глобально лучшему: возмущение идёт только вокруг носителей, а отбор "заражается, если не хуже носителя" — слабый элитизм. Глобально лучший хранится, но не тянет поиск к себе. Плюс шаг у канона растёт по мере заполнения популяции — противоположно классическому отжигу, где он затухает к концу; уточнение случается лишь через сброс популяции при улучшении, а не плавно. Для гладкой сходимости в большом пространстве этого не хватает.
Теперь к тому, ради чего всё затевалось — и это закрывает обещание из вступления. Исходный вопрос: появился ещё один природный алгоритм с громкими обещаниями — стоит ли он внимания и как отличить сильный от раздутого. Ответ получен на живом примере: дословная, буква в букву реализация CVO работает на уровне случайного блуждания и разваливается с размерностью. Одно изменение от здравого смысла — перевод шага из абсолютных единиц в долю диапазона координаты — вернуло алгоритму его честный потолок, прибавив пару процентов, и не сломав ни одной его части. Переносимый урок: реализуя любой алгоритм, первым делом необходимо смотреть, в каких единицах живёт его шаг возмущения; абсолютное смещение, естественное на функциях одного масштаба, на разномасштабном бенче бьёт мимо, а относительный шаг почти всегда то, что нужно.
Рисунок 2. Цветовая градация алгоритмов по соответствующим тестам
Рисунок 3. Гистограмма результатов тестирования алгоритмов (по шкале от 0 до 100, чем больше, тем лучше, где 100 — максимально возможный теоретический результат), в архиве скрипт для расчёта рейтинговой таблицы
Плюсы и минусы алгоритма CVO:
Плюсы:
- Не выявлено.
Минусы:
- Склонность к застреванию.
К статье прикреплён архив с актуальными версиями кодов алгоритмов. Автор статьи не несёт ответственности за абсолютную точность в описании канонических алгоритмов, во многие из них были внесены изменения для улучшения поисковых возможностей. Выводы и суждения, представленные в статьях, основываются на результатах проведённых экспериментов.
Программы, используемые в статье
| # | Имя | Тип | Описание |
|---|---|---|---|
| 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_CVO.mq5 | Скрипт | Испытательный стенд для CVO |
Предупреждение: все права на данные материалы принадлежат MetaQuotes Ltd. Полная или частичная перепечатка запрещена.
Данная статья написана пользователем сайта и отражает его личную точку зрения. Компания MetaQuotes Ltd не несет ответственности за достоверность представленной информации, а также за возможные последствия использования описанных решений, стратегий или рекомендаций.
Моделирование рынка: Первые шаги на SQL в MQL5 (II)
Архитектура машинного обучения для MetaTrader 5 (Часть 16): Вложенная кросс-валидация для несмещённой оценки
Торговые инструменты MQL5 (Часть 26): Интеграция частотного разбиения, энтропии и критерия хи-квадрат в визуальный анализатор
Моделирование рынка: Первые шаги на SQL в MQL5 (III)
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Вы принимаете политику сайта и условия использования