Эволюция городских советов — City Councils Evolution (CCE)
171
0
Содержание
Введение
Социальная метафора этого алгоритма привлекла мое внимание для рассмотрения в задачах оптимизации для торговых роботов. В чем суть: город устроен иерархически: сначала есть мельчайшие кварталы, у каждого свой совет. Лучший член квартального совета становится его главой и входит в совет района. Лучший в районном совете идёт выше, и так до верховного совета города. Члены совета стараются улучшить свои показатели, чтобы быть избранными и подняться на уровень выше. Автор — Einollah Pira опубликовал алгоритм City Councils Evolution в 2022 году.
Заинтересовала меня в CCE больше не метафора, а иерархия с локальным обменом. Подавляющее большинство алгоритмов серии устроены по одной из двух схем: либо все агенты тянутся к одному глобальному лидеру, либо каждый общается со случайным соседом. Первая схема быстро схлопывает популяцию, вторая размывает найденное. Древовидная структура обещала третий вариант: агент подтягивается только к своему непосредственному начальнику, начальник — к своему, и хорошее решение распространяется по популяции постепенно, слой за слоем, не уничтожая разнообразие на нижних уровнях.
Такая топология в рейтинге серии встречается редко, и было любопытно, даёт ли она что-то на практике. Вторая приманка — экономная схема пробы: четыре кандидата на одно изменение и жадный приём лучшего. Это дёшево реализуется и хорошо ложится на дискретные пространства, которых в трейдинге большинство.
Далее по порядку: реализую каноническую версию в C AO, протестирую на стенде, проверю гипотезу о скрытых преимуществах и затем попробую устранить выявленные проблемы. Все промежуточные результаты по ходу работы будут приведены.
Реализация алгоритма
Итак, как работает каноническая версия. Прежде чем переходить к коду, соберём картину целиком — так, как алгоритм себя представляет.
Состояние. Есть совет из N решений, отсортированный по убыванию приспособленности. Первый элемент — верховный совет, он же является лучшим решением. Остальные разложены по уровням d-арного дерева, и родитель любого узла всегда стоит в массиве раньше него, то есть всегда лучше. Одна элементарная операция — это обработка одной координаты g у одного члена совета m. Происходит следующее.
Сначала выбирается напарник. Для корня напарником служит копия его самого, у которой координата g заменена равномерно случайным значением из диапазона — это единственное место во всём алгоритме, где рождается новый материал. Для остальных членов напарником становится их родитель по дереву. Дальше берётся случайное число alpha. Распределение у него необычное, двугорбое: с вероятностью одна вторая это малое положительное значение из [0; 0.5), иначе — большое отрицательное из [-1; -0.5]. Промежуточных значений оператор не выдаёт.
Затем строятся четыре кандидата. Все они — точные копии текущего решения, у которых изменена ровно одна координата g, и различаются только формулой этой координаты: две комбинации отталкиваются от значения потомка, две — от значения родителя, с множителями alpha и 1 - alpha соответственно. Все четыре обрезаются по границам диапазона. Наконец, все четыре кандидата оцениваются целевой функцией, лучший из них сравнивается с текущим решением, и если он лучше — заменяет его. Приём жадный: ухудшение не принимается никогда.
Один шаг алгоритма — это описанная операция, проделанная последовательно для всех членов совета сверху вниз, от корня к листьям. Порядок важен: потомок читает родителя уже обновлённым в этом же шаге. После обхода совет пересортировывается — это и есть перестройка дерева советов. Один полный цикл — это N таких шагов, по одному на каждую координату задачи. Затем цикл повторяется с первой координаты.
Отсюда следуют два ключевых ограничения, которые определят всё дальнейшее. Во-первых, за один шаг решение меняется ровно по одной координате из всех — это классический покоординатный спуск со всеми его свойствами, хорошими и плохими. Во-вторых, на одну координату одного агента требуется 4 вызова ЦФ. При бюджете 10000, совете из 30 членов и 1000 координат алгоритм не успевает пройти даже 10% координат хотя бы один раз.
Что в итоге, CCE — это покоординатный спуск с четырьмя пробами на координату, жадным приёмом и аддитивным оператором. Всё остальное — обёртка.
Псевдокод алгоритма:ВХОД: N (число членов совета), d (степень дерева), maxEva, dim, [lb, ub] h = floor(log(N*(d-1)) / log(d) + 1) maxIter = round(maxEva / (dim * N * 4)) // Инициализация M[1..N] = random_uniform(lb, ub) for i = 1..N: fit[i] = FF(M[i]) sort_ascending(M, fit) // Главный цикл for t = 2..maxIter: for g = 1..dim: // проход по координатам Mnew = M // обновления идут каскадом // 1. Корень: мутация одной координаты у лучшего Z = M[1]; Z[g] = lb[g] + rand * (ub[g] - lb[g]) Y = Improve(M[1], Z, g) // 4 вызова ЦФ if FF(Y) < fit[1]: fit[1] = FF(Y); Mnew[1] = Y // 2. Остальные узлы, сверху вниз for level = 2..h: sIndex = (d^(level-1) - 1)/(d-1) + 1 eIndex = min((d^level - 1)/(d-1), N) for i = sIndex..eIndex: j = floor(i/d); if (i mod d) > 1: j = j + 1 parent = Mnew[j] // уже обновлён на этом же g child = Mnew[i] (Y, Yfit) = Improve(parent, child, g) // 4 вызова ЦФ if Yfit < fit[i]: fit[i] = Yfit; Mnew[i] = Y M = Mnew sort_ascending(M, fit) // перестройка дерева best = M[1] function Improve(X1, X2, g): if X1 == X2: // поэлементно! X2 = copy(X1); X2[g] = U[lb[g], ub[g]] rnd = U[0,1) alpha = (rnd < 0.5) ? rnd : -rnd Y1 = X2; Y1[g] = X2[g] + alpha * X1[g] Y2 = X2; Y2[g] = X2[g] + (1 - alpha) * X1[g] Y3 = X2; Y3[g] = X1[g] + alpha * X2[g] Y4 = X2; Y4[g] = X1[g] + (1 - alpha) * X2[g] clamp(Y1..Y4, lb, ub) evaluate Y1..Y4 return argmin_fitness(Y1, Y2, Y3, Y4)
Теперь разберем работу алгоритма по схеме:
Рисунок 1. Схема работы CCE: обход дерева советов и построение четвёрки кандидатов
Слева — дерево советов. Тринадцать узлов при d = 3, в каждом стоит ранг в отсортированном массиве. Оранжевым выделена пара родитель 3 → потомок 9, подписанная как X1 и X2 — она и разбирается на средней панели, оранжевая стрелка ведёт туда. Число в узле означает ранг в отсортированном массиве.
Справа — сама операция. Векторы показаны полосками из шести ячеек, столбец g подсвечен жёлтым насквозь через все шесть строк. Сверху X1 и X2, под ними распределение α, дальше Y1…Y4 с формулами справа. Зелёным помечена единственная ячейка, которая в кандидатах отличается — это главное, что должно броситься в глаза. Внизу красным расход целевой функции, то есть отбор лучшего из четырёх и жадный приём, и четыре вызова на одну координату одного члена совета.
Снизу — шаг и цикл, пять пунктов, последний вынесен красным: за один шаг решение меняется ровно по одной координате из dim.
При переносе в C_AO пришлось решить некоторые вопросы.
Расход целевой функции. Стенд вызывает целевую функцию ровно popSize раз за эпоху, а CCE требует четыре последовательных вызова на одного агента на одну координату. Решение: popSize жёстко равен четырём — это размер четвёрки Y1..Y4, а не параметр алгоритма. Размер совета вынесен в отдельный параметр councilSize. Одна эпоха стенда = один член совета на одной координате.
Направление оптимизации. У автора минимизация, в C_AO максимизация. Все сравнения и направление сортировки инвертированы.
Параметр h (высота дерева) не нужен: у автора он лишь ограничивает диапазон обхода уровней и при рабочих значениях покрывает все узлы, то есть эквивалентен простому проходу по всем членам совета.
Полный код канонической версии:
//+------------------------------------------------------------------+ //| | //+------------------------------------------------------------------+ struct S_CCE_Member { double c []; // координаты принятого решения double f; // приспособленность принятого решения void Init(int coords) { ArrayResize(c, coords); f = -DBL_MAX; } }; //+------------------------------------------------------------------+ //| | //+------------------------------------------------------------------+ class C_AO_CCE : public C_AO { public: ~C_AO_CCE() {} C_AO_CCE() { ao_name = "CCE"; ao_desc = "City Councils Evolution"; ao_link = "https://www.mql5.com/ru/users/joo"; popSize = 4; // всегда 4: кандидаты Y1..Y4 одного члена совета councilSize = 2; // число членов совета (N в статье) treeDegree = 3; // d - степень дерева советов ArrayResize(params, 3); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "councilSize"; params [1].val = councilSize; params [2].name = "treeDegree"; params [2].val = treeDegree; } void SetParams() { //--- popSize не является параметром CCE: оператор Improve всегда // порождает ровно четыре кандидата. Значение фиксируется, чтобы // тестовый стенд верно посчитал бюджет вызовов ЦФ. popSize = 4; councilSize = (int)params [1].val; treeDegree = (int)params [2].val; if(councilSize < 2) councilSize = 2; // корень + минимум один потомок if(treeDegree < 2) treeDegree = 2; params [0].val = popSize; params [1].val = councilSize; params [2].val = treeDegree; } bool Init(const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0); void Moving(); void Revision(); //--- видимые параметры int councilSize; // N - число членов совета int treeDegree; // d - степень дерева советов //--- диагностика: доля кандидатов, упёршихся в границу диапазона double ClampRate() { return (probesTotal > 0 ? (double)probesClamped / probesTotal : 0.0); } private: S_CCE_Member M []; // [councilSize] совет S_CCE_Member Mt []; // буфер сортировки int gene; // индекс обрабатываемой координаты int curMember; // член совета, чья очередь в этой эпохе int filled; // сколько членов совета уже заполнено long probesClamped; // счётчики диагностики long probesTotal; double Alpha(); bool SameVector(const double &v1 [], const double &v2 []); }; //+------------------------------------------------------------------+ //| Init | //+------------------------------------------------------------------+ bool C_AO_CCE::Init(const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0) { if(!StandardInit(rangeMinP, rangeMaxP, rangeStepP)) return false; ArrayResize(M, councilSize); ArrayResize(Mt, councilSize); for(int i = 0; i < councilSize; i++) { M [i].Init(coords); Mt [i].Init(coords); } gene = 0; curMember = 0; filled = 0; probesClamped = 0; probesTotal = 0; return true; } //+------------------------------------------------------------------+ //| Alpha — авторская формула: | //| rnd = U[0;1), k = round(1 + rnd), alpha = (-1)^(k+1) * rnd | //| => alpha in [0; 0.5) либо alpha in [-1; -0.5] | //+------------------------------------------------------------------+ double C_AO_CCE::Alpha() { double rnd = u.RNDprobab(); return (rnd < 0.5 ? rnd : -rnd); } //+------------------------------------------------------------------+ //| SameVector — поэлементное сравнение | //+------------------------------------------------------------------+ bool C_AO_CCE::SameVector(const double &v1 [], const double &v2 []) { for(int c = 0; c < coords; c++) if(v1 [c] != v2 [c]) return false; return true; } //+------------------------------------------------------------------+ //| Moving | //| Одна эпоха = один член совета на одной координате. | //| Слоты a[0..3] — кандидаты Y1..Y4. | //+------------------------------------------------------------------+ void C_AO_CCE::Moving() { //--- фаза инициализации: заполнение совета случайными решениями if(filled < councilSize) { 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; } int g = gene; int m = curMember; int p; double x1, x2, alpha, raw; if(m == 0) { //--- корень: партнёр — копия самого себя со случайным геном g p = 0; x1 = M [0].c [g]; x2 = u.SeInDiSp(u.RNDfromCI(rangeMin [g], rangeMax [g]), rangeMin [g], rangeMax [g], rangeStep [g]); } else { //--- родитель узла m в d-арном дереве. Гаусс-Зейдель: p < m всегда, // значит M[p] уже обновлён на этой же координате g. p = (m - 1) / treeDegree; x1 = M [p].c [g]; x2 = M [m].c [g]; //--- ветвь оригинала if X1==X2: скрытая инъекция разнообразия if(SameVector(M [p].c, M [m].c)) x2 = u.SeInDiSp(u.RNDfromCI(rangeMin [g], rangeMax [g]), rangeMin [g], rangeMax [g], rangeStep [g]); } alpha = Alpha(); for(int k = 0; k < 4; k++) { ArrayCopy(a [k].c, M [m].c, 0, 0, coords); switch(k) { case 0: raw = x2 + alpha * x1; break; // Y1 case 1: raw = x2 + (1.0 - alpha) * x1; break; // Y2 case 2: raw = x1 + alpha * x2; break; // Y3 default: raw = x1 + (1.0 - alpha) * x2; break; // Y4 } //--- диагностика клампинга probesTotal++; if(raw < rangeMin [g] || raw > rangeMax [g]) probesClamped++; a [k].c [g] = u.SeInDiSp(raw, rangeMin [g], rangeMax [g], rangeStep [g]); } } //+------------------------------------------------------------------+ //| Revision | //+------------------------------------------------------------------+ void C_AO_CCE::Revision() { //--- фаза инициализации if(filled < councilSize) { //--- лучшие из четвёрки идут в свободные места совета int order []; ArrayResize(order, popSize); for(int i = 0; i < popSize; i++) order [i] = i; for(int i = 0; i < popSize - 1; i++) for(int j = i + 1; j < popSize; j++) if(a [order [j]].f > a [order [i]].f) { int t = order [i]; order [i] = order [j]; order [j] = t; } for(int i = 0; i < popSize && filled < councilSize; i++, filled++) { M [filled].f = a [order [i]].f; ArrayCopy(M [filled].c, a [order [i]].c, 0, 0, coords); } if(filled >= councilSize) { u.Sorting(M, Mt, councilSize); gene = 0; curMember = 0; } if(M [0].f > fB) { fB = M [0].f; ArrayCopy(cB, M [0].c, 0, 0, coords); } revision = true; return; } //--- лучший из четвёрки, жадный приём int bestIdx = 0; double bestF = a [0].f; for(int k = 1; k < 4; k++) { if(a [k].f > bestF) { bestF = a [k].f; bestIdx = k; } } int m = curMember; if(bestF > M [m].f) { M [m].f = bestF; ArrayCopy(M [m].c, a [bestIdx].c, 0, 0, coords); } if(M [m].f > fB) { fB = M [m].f; ArrayCopy(cB, M [m].c, 0, 0, coords); } //--- следующий член совета; после полного обхода — пересортировка и //--- переход к следующей координате curMember++; if(curMember >= councilSize) { curMember = 0; u.Sorting(M, Mt, councilSize); gene++; if(gene >= coords) gene = 0; } }
Протестируем каноническую версию. Первое, что выяснилось при подборе параметров: композит строго монотонен по размеру совета, и растёт он при уменьшении.
| councilSize | 30 | 25 | 10 | 5 | 3 | 2 |
| composite | 32.29% | 33.84% | 36.21% | 37.21% | 38.52% | 41.15% |
Совет из двух членов — корень плюс единственный потомок — работает на девять пунктов лучше совета из тридцати. Причина прямая: композит определяется числом проходов по координатам, а каждый лишний член совета отнимает бюджет у этих проходов. Популяция в CCE не помогает, она мешает.
Степень дерева проверена отдельно: d = 2 против d = 3 при фиксированном совете 40 дают 36.36% и 36.21%, то есть разница 0.15 пункта — внутри шума. Декоративность дерева подтверждена не только чтением кода, но и экспериментом.
Порядок обхода тоже проверен. Первая реализация использовала Якоби (все члены читают состояние предыдущей эпохи), вторая — точный Гаусс-Зейдель плюс восстановленную ветвь X1==X2 . Разница: 41.37% против 41.15%, то есть ноль. Алгоритм нечувствителен и к этому.
Финальный результат канона:
CCE|City Councils Evolution|4.0|2.0|3.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.6572185761914582
25 Hilly's; Func runs: 10000; result: 0.5634432555302793
500 Hilly's; Func runs: 10000; result: 0.35465293619703997
=============================
5 Forest's; Func runs: 10000; result: 0.36172559279184446
25 Forest's; Func runs: 10000; result: 0.1753046542071895
500 Forest's; Func runs: 10000; result: 0.07924288133843145
=============================
5 Megacity's; Func runs: 10000; result: 0.7453333333333332
25 Megacity's; Func runs: 10000; result: 0.5661333333333334
500 Megacity's; Func runs: 10000; result: 0.2007066666666673
=============================
All score: 3.70376 (41.15%)
Отдельно бросается в глаза Forest — 0.362 на малой размерности против 0.657 у Hilly и 0.745 у Megacity. Объяснение структурное: Forest единственная на стенде функция с диагональными гребнями, а покоординатный спуск принципиально не может идти вдоль гребня. Чтобы двигаться по дну диагонального оврага, надо менять две координаты согласованно, а оператор меняет ровно одну. Агент упирается в стенки оврага по обеим осям и застревает в точке, которая не оптимальна ни в каком смысле, кроме покоординатного.
Теперь к самому интересному. Посмотрим ещё раз на оператор:
Y = x2 + alpha * x1
Это сумма координат, а не интерполяция. Шаг никак не привязан к ширине диапазона поиска — он пропорционален абсолютной величине координат, то есть расстоянию до начала координат. Оператор не инвариантен к переносу системы координат.
Что это значит на практике. Когда родитель и потомок сблизились, x1 ≈ x2 = v:
| кандидат | множитель при v | alpha in [0; 0.5) | alpha in [-1; -0.5] |
|---|---|---|---|
Y1, Y3 | 1 + alpha | [1.0; 1.5) | [0; 0.5] |
| Y2, Y4 | 2 - alpha | (1.5; 2.0] | [2.5; 3.0] |
С вероятностью одна вторая на стол кладётся кандидат со сжатием координаты минимум вдвое в сторону нуля. Приём жадный, берётся лучший из четырёх.
Любой стенд тестирования — это не только набор функций, но и договорённость о том, где расположена область поиска. И почти всегда она расположена симметрично относительно нуля: диапазон вида от минус десяти до плюс десяти. А это значит, что начало координат лежит ровно в центре области.
Теперь представим алгоритм, который вообще ничего не ищет, а просто стягивает свои решения к нулю. На таком стенде он окажется в центре области поиска — а центр для большинства тестовых функций место статистически неплохое, куда лучше случайной точки. Алгоритм получит приличный балл, не сделав ни одного осмысленного шага.
Ровно такое подозрение и возникло к CCE. Оператор Y = x2 + alpha * x1 с отрицательной альфой даёт множитель в диапазоне от нуля до половины, то есть сжимает координату к нулю. Вопрос в том, сколько из набранного балла заработано поиском, а сколько — этим сжатием.
Отделить одно от другого можно, если сдвинуть систему координат, не трогая ландшафт. Функция остаётся той же самой, её оптимумы остаются на тех же местах относительно ландшафта, задача по сложности не меняется. Меняется только одно: точка ноль перестаёт совпадать с центром области поиска. Честный алгоритм обязан показать тот же результат — ему безразлично, как экспериментатор пронумеровал оси. Алгоритм, живущий за счёт сжатия к нулю, просядет.
Как устроен тест. Область поиска сдвигается на ShiftFactor ширин диапазона, а перед вызовом целевой функции сдвиг вычитается обратно.
Алгоритм получает сдвинутые границы и работает в сдвинутых координатах, ничего не подозревая. А целевая функция вычисляется от исходных значений:
//+------------------------------------------------------------------+ //| | //+------------------------------------------------------------------+ void OnStart() { //--- алгоритм C_AO *AO = new C_AO_CCE(); AO.params [0].val = PopSize_P; AO.params [1].val = TreeDegree_P; AO.SetParams(); Print(AO.GetName(), "|", AO.GetDesc(), "|", AO.GetParams()); //--- создаём 5 функций #define NFUNCS 5 C_Function *funcs [NFUNCS]; funcs [0] = new C_Hilly(); funcs [1] = new C_Forest(); funcs [2] = new C_Megacity(); funcs [3] = new C_Peaks(); funcs [4] = new C_Skin(); //--- 10 координат: пара 0-1 = Hilly, 2-3 = Forest, 4-5 = Megacity, // 6-7 = Peaks, 8-9 = Skin int params = NFUNCS * 2; double rangeMin []; double rangeMax []; double rangeStep []; double offset []; // сдвиг по каждой координате ArrayResize(rangeMin, params); ArrayResize(rangeMax, params); ArrayResize(rangeStep, params); ArrayResize(offset, params); for(int i = 0; i < NFUNCS; i++) { double xMin = funcs [i].GetMinRangeX(); double xMax = funcs [i].GetMaxRangeX(); double yMin = funcs [i].GetMinRangeY(); double yMax = funcs [i].GetMaxRangeY(); //--- сдвиг пропорционален ширине диапазона своей координаты, // поэтому геометрия ландшафта не искажается offset [i * 2] = ShiftFactor_P * (xMax - xMin); offset [i * 2 + 1] = ShiftFactor_P * (yMax - yMin); rangeMin [i * 2] = xMin + offset [i * 2]; rangeMax [i * 2] = xMax + offset [i * 2]; rangeStep [i * 2] = 0.0; rangeMin [i * 2 + 1] = yMin + offset [i * 2 + 1]; rangeMax [i * 2 + 1] = yMax + offset [i * 2 + 1]; rangeStep [i * 2 + 1] = 0.0; } //--- запуск тестов int epochCount = NumbTestFuncRuns_P / (int)AO.params [0].val; double aveResult = 0.0; Print("============================="); Print("Composite anti-cheat test: Hilly + Forest + Megacity + Peaks + Skin"); Print("Coordinates: ", params, "; Epochs: ", epochCount, "; Repeats: ", NumberRepetTest_P); Print("Origin shift factor: ", DoubleToString(ShiftFactor_P, 3), (ShiftFactor_P == 0.0 ? " (стандартный композитный прогон)" : " (ноль вынесен из области поиска)")); Print("============================="); for(int test = 0; test < NumberRepetTest_P; test++) { //--- StandardInit() сидит MathSrand от GetMicrosecondCount(), поэтому //--- сид меняется от прогона к прогону без задержки. Sleep оставлен //--- защитно для паритета условий с остальными прогонами серии. Sleep(1000); if(!AO.Init(rangeMin, rangeMax, rangeStep, epochCount)) break; for(int epochCNT = 1; epochCNT <= epochCount && !IsStopped(); epochCNT++) { AO.Moving(); //--- фитнес агента: среднее по 5 функциям. // Сдвиг вычитается ПЕРЕД вызовом Core, поэтому ландшафт // в точности тот же, что и при ShiftFactor_P = 0. for(int set = 0; set < ArraySize(AO.a); set++) { double sum = 0.0; for(int i = 0; i < NFUNCS; i++) { sum += funcs [i].Core(AO.a [set].c [i * 2] - offset [i * 2], AO.a [set].c [i * 2 + 1] - offset [i * 2 + 1]); } AO.a [set].f = sum / NFUNCS; } AO.Revision(); } Print("Run ", test + 1, "/", NumberRepetTest_P, ": ", AO.fB); aveResult += AO.fB; } aveResult /= (double)NumberRepetTest_P; Print("============================="); Print("Average result: ", DoubleToString(aveResult, 10), " (", DoubleToString(aveResult * 100.0, 2), "%)"); Print("============================="); //--- освобождение for(int i = 0; i < NFUNCS; i++) delete funcs [i]; delete AO; } //+------------------------------------------------------------------+
Две строки вычитания — и Core всегда получает аргументы из своего родного диапазона. Ландшафт побитово тот же, файл TestFunctions.mqh трогать не нужно. При ShiftFactor = 0 тест вырождается в обычный прогон, что удобно как контроль.
Проверка проводилась на композитном стенде из пяти функций — Hilly, Forest, Megacity, Peaks и Skin, по две координаты на функцию, десять координат всего. Композитный стенд взят не случайно: он заодно страхует от геометрических читов вроде диагонального выравнивания, поскольку пять функций с разной геометрией одновременно обмануть гораздо труднее.
Результаты. Контрольный прогон без сдвига, каноническая конфигурация с советом из двух членов:
CCE|City Councils Evolution|8.0|3.0|
=============================
Composite anti-cheat test: Hilly + Forest + Megacity + Peaks + Skin
Coordinates: 10; Epochs: 1250; Repeats: 10
Origin shift factor: 0.000 (стандартный композитный прогон)
=============================
Run 1/10: 0.6483110084799746
Run 2/10: 0.7951162265855023
Run 3/10: 0.5955865723649618
Run 4/10: 0.6205429819310735
Run 5/10: 0.8968435531503033
Run 6/10: 0.7412102326450956
Run 7/10: 0.5909374742006821
Run 8/10: 0.8204399277988635
Run 9/10: 0.5869085305194864
Run 10/10: 0.8755874206945741
=============================
Average result: 0.7171483928 (71.71%)
=============================
Прежде чем двигаться дальше, обратите внимание на сами повторы. Они разделяются на две группы без промежуточных значений: пять значений в районе 0.59–0.65 и четыре в районе 0.80–0.90. Это не разброс, а два разных исхода — покоординатный спуск либо попадает в нужный бассейн на ранних проходах, либо не попадает и до конца дистанции оттуда не выбирается, поскольку механизма перезапуска у алгоритма нет. Повторный прогон той же конфигурации, где верхний кластер оказался многочисленнее, дал 80.45 процента. То есть любую цифру CCE нужно читать с поправкой на несколько пунктов.
Теперь тот же тест, но начало координат вынесено далеко за пределы области поиска:
CCE|City Councils Evolution|8.0|3.0|
=============================
Composite anti-cheat test: Hilly + Forest + Megacity + Peaks + Skin
Coordinates: 10; Epochs: 1250; Repeats: 10
Origin shift factor: 15.000 (ноль вынесен из области поиска)
=============================
Run 1/10: 0.4603848022729261
Run 2/10: 0.49190177329804446
Run 3/10: 0.475808107746248
Run 4/10: 0.35919649700418627
Run 5/10: 0.6379800933132185
Run 6/10: 0.6107661070329395
Run 7/10: 0.496872946742357
Run 8/10: 0.3626605945005663
Run 9/10: 0.4922209229995909
Run 10/10: 0.5747480775044673
=============================
Average result: 0.4962539922 (49.63%)
=============================
Здесь уже не расслоение, а равномерно низкие значения: верхний кластер исчез целиком, ни один из десяти повторов не дотянул даже до 0.64.
ShiftFactor 0.0 : 0.7171483928 (71.71%) и повтор 0.8044943312 (80.45%)
ShiftFactor 0.7 : 0.7354187936 (73.54%)
ShiftFactor 1.5 : 0.6659142374 (66.59%)
ShiftFactor 2.0 : 0.7079809216 (70.80%)
ShiftFactor 3.0 : 0.6894945411 (68.95%)
ShiftFactor 5.0 : 0.5936715069 (59.37%)
ShiftFactor 15.0 : 0.4962539922 (49.63%)
Плато держится примерно до трёх ширин диапазона: значения от 66.6 до 73.5 неразличимы между собой на фоне того самого расслоения, которое мы только что видели в логе. Дальше начинается спад — 59.4 на пяти ширинах и 49.6 на пятнадцати.
Между сдвигом 0.7 и сдвигом 15 разрыв в 24 пункта. Подчеркну ещё раз: ландшафт при этом не менялся вообще, менялась только нумерация осей.
Почему так происходит. Спад оказался односторонним, и это существенная деталь. Из двух ожидаемых механизмов отказа реально работает только один.
Когда область поиска далеко от нуля — отказ. Шаг alpha * x1 при координатах порядка пятнадцати ширин диапазона составляет около семи с половиной ширин. Кандидат остаётся внутри границ, только пока alpha меньше отношения (ub - x2) / x1, то есть примерно меньше единицы, делённой на величину сдвига. Поскольку альфа распределена равномерно на половине единичного отрезка, доля выживших проб падает обратно пропорционально сдвигу: при сдвиге на три ширины внутри границ остаётся около 56 процентов положительных альф, при пяти — 40 процентов, при пятнадцати — всего 13. Остальные кандидаты вылетают за границу и обрезаются по границе. При больших сдвигах вся четвёрка вырождается в выбор между нижней и верхней границей, и осмысленный поиск прекращается.
Оговорка, важная для правильной формулировки: обрезанный кандидат не сбивает поиск с курса. Жадный приём просто отбрасывает его, если он оказался хуже текущего решения. То есть отказ при удалении области от нуля — это не порча направления, а постепенная кража бюджета: из четырёх проб на координату полезными остаются одна-две.
Когда область поиска рядом с нулём — не отказ, а подарок. При нулевом сдвиге начало координат лежит в центре области, и сжатие тянет агентов не в плохое место, а в центр. То самое бесплатное центральное смещение, ради поиска которого тест и затевался.
Что это значит для практики. Из этого следует простое правило, применимое к любому вашему набору параметров. Важна не дистанция до нуля сама по себе, а её отношение к ширине диапазона (далее — “эксцентриситет”). Берём середину диапазона, делим её модуль на ширину диапазона, и смотрим на результат: до трёх алгоритм в безопасной зоне, около пяти начинается спад, дальше обвал.
Посчитаем для типичных параметров советника. Период индикатора от 5 до 200: середина 102.5, ширина 195, эксцентриситет 0.53 — безопасно. Размер лота от 0.01 до 1.0 даёт 0.51, стоп-лосс от 100 до 500 пунктов — 0.75. Все на плато, всё в порядке.
А теперь опасные случаи. Период скользящей средней, который вы решили искать в узком коридоре от 200 до 250: середина 225, ширина всего 50, эксцентриситет 4.5 — уже зона спада. И совсем плохо с ценовыми уровнями: диапазон от 1.0800 до 1.0900 имеет ширину одну сотую при середине 1.085, то есть эксцентриситет около ста восьми. Здесь канонический CCE работать не будет вовсе.
Обратите внимание на закономерность: беда не в больших числах как таковых, а в узких диапазонах, удалённых от нуля. Один и тот же период скользящей средней, заданный как от 5 до 250, совершенно безопасен, а как от 200 до 250 — уже нет. Сузив диапазон поиска в надежде ускорить оптимизацию, вы можете незаметно для себя загнать алгоритм в режим отказа
Модификация CCEm. Диагноз поставлен, лечение напрашивается само. Две болезни, и обе лечит одна правка оператора.
Аддитивность → разностность. Заменяем x2 + alpha * x1 на x2 + alpha * (x1 - x2). Шаг теперь задаётся расстоянием между партнёрами, а не расстоянием до нуля, и оператор становится инвариантным к переносу.
Покоординатность → векторность. Ход применяется ко всем координатам сразу, а не к одной. Появляется способность двигаться вдоль диагонального гребня.
Здесь есть подводный камень. Наивная разностная замена вырождается:
Y2 = x2 + (1 - alpha)*(x1 - x2) = x1 + alpha*(x2 - x1) = Y3 Тождественно. Четыре кандидата схлопываются в три, четверть бюджета уходит на дубликат. Поэтому четвёрка построена как две пары интерполяция / экстраполяция:
dif = x1 - x2 Y1 = x2 + alpha * dif // к x1 Y2 = x2 + (1 + alpha) * dif // за x1 Y3 = x1 - alpha * dif // к x2 Y4 = x1 - (1 + alpha) * dif // за x2
Авторское распределение alpha сохранено целиком, и теперь оно осмысленно: положительная альфа даёт короткую интерполяцию у одного конца и перелёт за другой, отрицательная — зеркально.
Рисунок 2. Почему разностная форма чинит зависимость от системы координат
На обеих панелях изображена одна и та же ось координат: слева ноль, справа область поиска между lb и ub , внутри неё пара решений x1 и x2 — родитель и потомок. Фиолетовая размерная линия показывает, какая величина задаёт длину шага. У канона наверху это |x|, расстояние от нуля до решения, и красная стрелка показывает разброс, куда при таком шаге может улететь четвёрка кандидатов: практически на всю ось, причём большая часть попадёт за границы и будет обрезана (clamped). У модификации внизу шаг задаётся величиной |x1 − x2|, и зелёная стрелка укладывается в окрестность самой пары. Ноль при этом окрашен серым — он больше ни на что не влияет, отсюда и инвариантность к переносу (translation invariant). Нижние строки панелей отмечают вторую разницу: канон меняет одну координату за ход, модификация — все.
Ещё три момента. Alpha своя на каждую координату — один скаляр на весь вектор дал бы связку скаляр-на-вектор, то есть движение строго вдоль одной прямой и одну степень свободы на ход независимо от размерности. Партнёром корня становится свежий случайный вектор, поскольку при разностной форме копия с одним случайным геном дала бы нулевую разность по всем остальным координатам. И ветвь родитель равен потомку из декоративной становится несущей: при нулевой разности все четыре кандидата вырождаются в точку. Дерево советов, размер совета, жадный приём, пересортировка и сама четвёрка проб оставлены каноническими.
Полный код модификации:
//+------------------------------------------------------------------+ //| | //+------------------------------------------------------------------+ struct S_CCEm_Member { double c []; double f; void Init(int coords) { ArrayResize(c, coords); f = -DBL_MAX; } }; //+------------------------------------------------------------------+ //+------------------------------------------------------------------+ //| | //+------------------------------------------------------------------+ class C_AO_CCEm : public C_AO { public: ~C_AO_CCEm() {} C_AO_CCEm() { ao_name = "CCEm"; ao_desc = "City Councils Evolution M"; ao_link = "https://www.mql5.com/ru/articles/24072"; popSize = 4; // всегда 4: кандидаты Y1..Y4 одного члена совета councilSize = 20; // число членов совета (N в статье) treeDegree = 3; // d - степень дерева советов moveProb = 0.4; // вероятность участия координаты в ходе ArrayResize(params, 4); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "councilSize"; params [1].val = councilSize; params [2].name = "treeDegree"; params [2].val = treeDegree; params [3].name = "moveProb"; params [3].val = moveProb; } void SetParams() { popSize = (int)params [0].val; councilSize = (int)params [1].val; treeDegree = (int)params [2].val; moveProb = params [3].val; if(councilSize < 2) councilSize = 2; if(treeDegree < 2) treeDegree = 2; if(moveProb < 0.0) moveProb = 0.0; if(moveProb > 1.0) moveProb = 1.0; params [0].val = popSize; params [1].val = councilSize; params [2].val = treeDegree; params [3].val = moveProb; } bool Init(const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0); void Moving(); void Revision(); //--- видимые параметры int councilSize; int treeDegree; double moveProb; // вероятность участия координаты в ходе //--- диагностика: доля координат кандидатов, упёршихся в границу double ClampRate() { return (probesTotal > 0 ? (double)probesClamped / probesTotal : 0.0); } private: S_CCEm_Member M []; S_CCEm_Member Mt []; double partner []; bool gate []; // маска двигаемых координат int curMember; int filled; long probesClamped; long probesTotal; double Alpha(); bool SameVector(const double &v1 [], const double &v2 []); void MakeGate(); void MakeRandomVector(double &v []); }; //+------------------------------------------------------------------+ //+------------------------------------------------------------------+ //| Init | //+------------------------------------------------------------------+ bool C_AO_CCEm::Init(const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0) { if(!StandardInit(rangeMinP, rangeMaxP, rangeStepP)) return false; ArrayResize(M, councilSize); ArrayResize(Mt, councilSize); ArrayResize(partner, coords); ArrayResize(gate, coords); for(int i = 0; i < councilSize; i++) { M [i].Init(coords); Mt [i].Init(coords); } curMember = 0; filled = 0; probesClamped = 0; probesTotal = 0; return true; } //+------------------------------------------------------------------+ //+------------------------------------------------------------------+ double C_AO_CCEm::Alpha() { double rnd = u.RNDprobab(); return (rnd < 0.5 ? rnd : -rnd); } //+------------------------------------------------------------------+ //+------------------------------------------------------------------+ bool C_AO_CCEm::SameVector(const double &v1 [], const double &v2 []) { for(int c = 0; c < coords; c++) if(v1 [c] != v2 [c]) return false; return true; } //+------------------------------------------------------------------+ //+------------------------------------------------------------------+ void C_AO_CCEm::MakeRandomVector(double &v []) { for(int c = 0; c < coords; c++) v [c] = u.SeInDiSp(u.RNDfromCI(rangeMin [c], rangeMax [c]), rangeMin [c], rangeMax [c], rangeStep [c]); } //+------------------------------------------------------------------+ //+------------------------------------------------------------------+ //| MakeGate — маска двигаемых координат, общая для Y1..Y4 | //+------------------------------------------------------------------+ void C_AO_CCEm::MakeGate() { int cnt = 0; for(int c = 0; c < coords; c++) { gate [c] = (u.RNDprobab() < moveProb); if(gate [c]) cnt++; } //--- ни одной координаты не выбрано - берём одну случайную, //--- иначе четвёрка выродится в копию текущего решения if(cnt == 0) gate [u.RNDminusOne(coords)] = true; } //+------------------------------------------------------------------+ //+------------------------------------------------------------------+ //| Moving | //| Одна эпоха = один член совета. | //+------------------------------------------------------------------+ void C_AO_CCEm::Moving() { //--- фаза инициализации: заполнение совета случайными решениями if(filled < councilSize) { for(int i = 0; i < popSize; i++) MakeRandomVector(a [i].c); return; } int m = curMember; int p; //--- выбор партнёра X1 if(m == 0) { //--- корень: партнёр — свежий случайный вектор MakeRandomVector(partner); } else { //--- родитель узла m в d-арном дереве. Гаусс-Зейдель: p < m всегда. p = (m - 1) / treeDegree; if(SameVector(M [p].c, M [m].c)) MakeRandomVector(partner); // нулевая разность недопустима else ArrayCopy(partner, M [p].c, 0, 0, coords); } MakeGate(); //--- четыре кандидата, alpha своя на каждую двигаемую координату double x1, x2, alpha, dif, raw; for(int c = 0; c < coords; c++) { if(!gate [c]) { //--- координата не участвует в ходе for(int k = 0; k < 4; k++) a [k].c [c] = M [m].c [c]; continue; } x1 = partner [c]; // X1 - родитель (или случайный партнёр) x2 = M [m].c [c]; // X2 - сам член совета alpha = Alpha(); dif = x1 - x2; for(int k = 0; k < 4; k++) { switch(k) { case 0: raw = x2 + alpha * dif; break; // к x1 case 1: raw = x2 + (1.0 + alpha) * dif; break; // за x1 case 2: raw = x1 - alpha * dif; break; // к x2 default: raw = x1 - (1.0 + alpha) * dif; break; // за x2 } probesTotal++; if(raw < rangeMin [c] || raw > rangeMax [c]) probesClamped++; a [k].c [c] = u.SeInDiSp(raw, rangeMin [c], rangeMax [c], rangeStep [c]); } } } //+------------------------------------------------------------------+ //+------------------------------------------------------------------+ //| Revision | //+------------------------------------------------------------------+ void C_AO_CCEm::Revision() { //--- фаза инициализации if(filled < councilSize) { int order []; ArrayResize(order, popSize); for(int i = 0; i < popSize; i++) order [i] = i; for(int i = 0; i < popSize - 1; i++) for(int j = i + 1; j < popSize; j++) if(a [order [j]].f > a [order [i]].f) { int t = order [i]; order [i] = order [j]; order [j] = t; } for(int i = 0; i < popSize && filled < councilSize; i++, filled++) { M [filled].f = a [order [i]].f; ArrayCopy(M [filled].c, a [order [i]].c, 0, 0, coords); } if(filled >= councilSize) { u.Sorting(M, Mt, councilSize); curMember = 0; } if(M [0].f > fB) { fB = M [0].f; ArrayCopy(cB, M [0].c, 0, 0, coords); } revision = true; return; } //--- лучший из четвёрки, жадный приём int bestIdx = 0; double bestF = a [0].f; for(int k = 1; k < 4; k++) { if(a [k].f > bestF) { bestF = a [k].f; bestIdx = k; } } int m = curMember; if(bestF > M [m].f) { M [m].f = bestF; ArrayCopy(M [m].c, a [bestIdx].c, 0, 0, coords); } if(M [m].f > fB) { fB = M [m].f; ArrayCopy(cB, M [m].c, 0, 0, coords); } //--- следующий член совета; после полного обхода — перестройка дерева curMember++; if(curMember >= councilSize) { curMember = 0; u.Sorting(M, Mt, councilSize); } } //+------------------------------------------------------------------+
Результаты тестов
Для таблицы взят совет 50: композит тот же, а значение совпадает с дефолтным popSize серии.
CCEm|City Councils Evolution M|4.0|50.0|3.0|1000.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.7801904525720962
25 Hilly's; Func runs: 10000; result: 0.5674856077456875
500 Hilly's; Func runs: 10000; result: 0.2557411330267817
=============================
5 Forest's; Func runs: 10000; result: 0.934390650619403
25 Forest's; Func runs: 10000; result: 0.6492739753440023
500 Forest's; Func runs: 10000; result: 0.1171451679865052
=============================
5 Megacity's; Func runs: 10000; result: 0.8173333333333334
25 Megacity's; Func runs: 10000; result: 0.4378666666666667
500 Megacity's; Func runs: 10000; result: 0.10876000000000094
=============================
All score: 4.66819 (51.87%)
Forest 5 вырос с 0.362 до 0.934. Диагноз про диагональный гребень подтвердился радикально. Forest 25 поднялся с 0.175 до 0.649.
Визуализация работы алгоритма CCEm в 2D проекции на тестовых функциях и двух последних выбранных произвольно.
CCEm на тестовой функции Hilly
CCEm на тестовой функции Forest
CCEm на тестовой функции Megacity
CCEm на тестовой функции Ackley
CCEm на тестовой функции Shaffer
По результатам тестирования алгоритм CCEm занимает 44-е место в рейтинговой таблице.
| 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 | 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 |
| 13 | 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 |
| 14 | 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 |
| 15 | 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 |
| 16 | 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 |
| 17 | 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 |
| 18 | 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 |
| 19 | 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 |
| 20 | 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 |
| 21 | 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 |
| 22 | 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 |
| 23 | 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 |
| 24 | 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 |
| 25 | 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 |
| 26 | 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 |
| 27 | (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 |
| 28 | 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 |
| 29 | 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 |
| 30 | 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 |
| 31 | 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 |
| 32 | 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 |
| 33 | 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 |
| 34 | 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 |
| 35 | 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 |
| 36 | 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 |
| 37 | 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 | 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 |
| 39 | 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 |
| 40 | 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 |
| 41 | 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 |
| 42 | 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 |
| 43 | 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 |
| 44 | CCEm | city_councils_evolution_M_ | 0,78019 | 0,56748 | 0,25574 | 1,60341 | 0,93439 | 0,64927 | 0,11714 | 1,70080 | 0,81733 | 0,43786 | 0,10876 | 1,36395 | 4,668 | 51,87 |
| 45 | DOAm | dynastic_optimization_algorithm | 0,63202 | 0,58003 | 0,31943 | 1,53148 | 0,76947 | 0,62730 | 0,12425 | 1,52102 | 0,74133 | 0,59520 | 0,16550 | 1,50203 | 4,555 | 50,61 |
| 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 | |
Выводы
Казалось бы, можно закруглиться и на этом остановиться. Еще несколько попыток и перебор по двум параметрам — размеру совета и вероятности — вывел конфигурацию заметно лучше исходной:
CCEm|City Councils Evolution M|4.0|20.0|3.0|0.5|
=============================
5 Hilly's; Func runs: 10000; result: 0.9234158594854092
25 Hilly's; Func runs: 10000; result: 0.6662193087032339
500 Hilly's; Func runs: 10000; result: 0.29003867410771245
=============================
5 Forest's; Func runs: 10000; result: 0.9792448015016874
25 Forest's; Func runs: 10000; result: 0.7161320797886964
500 Forest's; Func runs: 10000; result: 0.15173332606789042
=============================
5 Megacity's; Func runs: 10000; result: 0.9440000000000002
25 Megacity's; Func runs: 10000; result: 0.5786666666666667
500 Megacity's; Func runs: 10000; result: 0.15142666666666718
=============================
All score: 5.40088 (60.01%)
Оговорка о методике. Значение 20 для совета и 0.5 для вероятности получены перебором по сетке, а не выведены из каких-либо соображений, и перебор этот не был исчерпывающим — оси взаимодействуют между собой, так что найденная точка почти наверняка не абсолютный максимум, а лишь лучшая из проверенных. Все результаты получены при 10 повторах; разброс составляет несколько пунктов (по логам композитного теста).
Работа над CCE оказалась в равной мере разбором алгоритма и разбором того, как алгоритм подан.
Метафора не соответствует коду. Ни дерева советов, ни выборов, ни продвижения по иерархии в реализации нет. Каждое из пяти заявленных свойств проверено экспериментально и не подтвердилось.
Степень дерева d мы меняли с двух на три при неизменном всём остальном — результат сдвинулся на 0.15 пункта, то есть меньше, чем гуляют два одинаковых прогона между собой. Значит, форма дерева на поведение не влияет вовсе. Размер совета мы уменьшали от тридцати до двух, и композит при этом не падал, а рос — с 32.29% до 41.15%. Популяция, которая должна была бы помогать, на деле только отнимала бюджет у полезной работы: чем меньше решений алгоритм держит одновременно, тем больше проходов по координатам успевает сделать. Что остаётся после всех этих проверок — покоординатный спуск с четырьмя пробами на координату. Простой локальный поиск без какой-либо иерархии.
Оператор не инвариантен к переносу. Мы сдвигали область поиска, не трогая при этом сам ландшафт: функции те же, оптимумы на тех же местах относительно рельефа, сложность задачи не изменилась ни на йоту. Изменилось только то, где находится точка ноль относительно области. Канон при этом потерял 13 пунктов на основном стенде (с 41.15% до 27.98%) и 24 пункта на композитном.
Причина в том, что у оператора нет собственной меры длины шага. Он берёт её из расстояния до начала координат: близко к нулю — шаги микроскопические, далеко — гигантские, вылетающие за границы диапазона. А поскольку тестовые стенды почти всегда центрированы, ноль на них лежит в середине области поиска, и эта особенность оборачивается для алгоритма бесплатной подсказкой иди к центру. Отсюда и главный практический вывод: балл на стенде и способность искать — это не одно и то же, и разделить их можно только специальной проверкой.
Правка оператора поднимает результат с 41% до 60%. Мы заменили сложение координат на их разность, разрешили менять все координаты за один ход вместо одной и добавили третьим параметром вероятность участия координаты в ходе. Лучшая найденная конфигурация — совет из двадцати членов при вероятности одна вторая — даёт 60.01% композита против 41.15% у канона.
Разберём, что именно улучшилось. Forest в десятимерной ячейке поднялся с 0.362 до 0.934, почти втрое — это функция с диагональными гребнями, вдоль которых покоординатный спуск ходить не умеет в принципе, а векторный ход умеет. Зависимость от системы координат исчезла, не стала меньше, а исчезла полностью и притом по построению: разность двух решений при переносе осей не меняется, значит и шаг не меняется. Это свойство, доказуемое на бумаге, а прогон со сдвигом служил лишь проверкой того, что код написан верно.
Стандартные стенды тестирования обычно центрированы: оптимум лежит в середине области поиска или недалеко от неё. Алгоритм, который просто тянет решения к центру, получает на таких тестах бесплатную фору и выглядит умнее, чем есть. Мы показали это на одном прогоне со сдвигом области поиска и сравнили поведение алгоритма без этого преимущества. Что из этого получает трейдер: готовый алгоритм для оптимизации советника и понимание, насколько важно проводить самостоятельную оценку работоспособности алгоритма от скрытых преимуществ.
Рисунок 3. Цветовая градация алгоритмов по результатам соответствующих тестов.
Рисунок 4. Гистограмма результатов тестирования алгоритмов (по шкале от 0 до 100: чем больше, тем лучше, где 100 — максимально возможный теоретический результат). В архиве — скрипт для расчёта рейтинговой таблицы
Плюсы и минусы алгоритма CCEm
Плюсы:
- Уверенно работает на овражных функциях.
- Существенно лучше оригинала в высокой размерности на нецентрированных задачах.
- Совет в CCEm впервые начинает приносить пользу — оптимум внутренний, а не на границе.
Минусы:
- Существенных недостатков не выявлено.
К статье прикреплён архив с актуальными версиями кодов алгоритмов. Автор статьи не несёт ответственности за абсолютную точность в описании канонических алгоритмов, во многие из них внесены изменения для улучшения поисковых возможностей. Выводы и суждения, представленные в статьях, основываются на результатах проведённых экспериментов.
Программы, используемые в статье
| # | Имя | Тип | Описание |
|---|---|---|---|
| 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_CCEm.mq5 | Скрипт | Испытательный стенд для CCEm |
Предупреждение: все права на данные материалы принадлежат MetaQuotes Ltd. Полная или частичная перепечатка запрещена.
Данная статья написана пользователем сайта и отражает его личную точку зрения. Компания MetaQuotes Ltd не несет ответственности за достоверность представленной информации, а также за возможные последствия использования описанных решений, стратегий или рекомендаций.
Машинное обучение и Data Science (Часть 47): Прогнозирование рынка с помощью модели DeepAR на Python
Нейросети в трейдинге: Адаптация прогноза при смене рыночного режима (Объект верхнего уровня)
База данных — это просто (Часть 1): Легковесный ORM-фреймворк для MQL5 на базе SQLite
Алгоритм оптимизации на основе кровеносной системы — Circulatory System Based Optimization (CSBO)
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Вы принимаете политику сайта и условия использования