Кооперация бионических алгоритмов — Co-Operation of Biology Related Algorithms (COBRA)
60
0
Содержание
Введение
На гладком ландшафте параметров одного советника отлично работает один метод, на изрезанном рельефе другого — совершенно иной, а заранее угадать характер поверхности, которую предстоит исследовать, практически невозможно.
Естественная мысль — выбрать несколько методов оптимизации. Запустить несколько алгоритмов одновременно, дать каждому свою долю вычислительного бюджета и позволить им обмениваться находками: пусть тот, чей поисковый механизм лучше подходит к конкретному ландшафту, вытягивает остальных. Именно эта идея лежит в основе метаэвристики COBRA — Co-Operation of Biology Related Algorithms, предложенной Шахназ Ахмедовой и Евгением Семенкиным в 2013 году.
COBRA интересна нам не как очередной алгоритм в коллекции, а как представитель отдельного класса — кооперативных метаэвристик, работающих поверх уже известных методов. В составе кооперации шесть популярных бионических алгоритмов: роевой PSO, волчья стая WPS, светлячки FFA, кукушки CSA, летучие мыши BA и рыбий косяк FSS. Пять из них в том или ином виде уже знакомы читателям серии. Вопрос прост по формулировке, но сложен по сути: даёт ли координация нескольких методов эффект сверх суммы частей? Если да, за счёт какого механизма? Забегая вперёд: ответ оказался неожиданным и для авторов первоисточника, и для нас, а путь к нему потребовал серии экспериментов, в которой отрицательные результаты оказались не менее содержательными, чем положительные.
Реализация алгоритма
Оригинальный COBRA устроен так. Для каждого из шести алгоритмов-компонетов создаётся собственная популяция, и все шесть исполняются параллельно, решая одну и ту же задачу. Авторы выбирали компоненты по признаку структурной схожести схем: каждый из них оперирует популяцией агентов с позициями в вещественном пространстве и правилом обновления, построенным на притяжении к лучшим найденным решениям. Эта однородность интерфейса и делает возможным главное — обмен особями между популяциями без каких-либо преобразований.
Координация в первоисточнике основана на трёх механизмах. Первый — общий рост и сжатие: если суммарный лучший результат не улучшается заданное число итераций, все популяции увеличиваются, а при устойчивом прогрессе — сокращаются, экономя вычисления. Второй — миграция к победителю: популяция, чей средний фитнес лучше остальных, вправе принимать особей, изымаемых у отстающих; так ресурсы перетекают к методу, наиболее успешному на данном ландшафте. Третий — коммуникация: периодически часть худших особей каждой популяции замещается лучшими особями других популяций, что, по замыслу авторов, предотвращает преждевременную сходимость каждого компонента к собственному локальному оптимуму.
В работе 2017 года авторы пошли дальше и заменили жёсткие правила изменения размеров популяций нечётким контроллером с правилами: на вход подаются показатели успешности компонентов, на выходе — вещественные поправки к размерам популяций. Существенный вывод той работы пригодится нам позже. Вариант контроллера, оценивающий успешность компонента по среднему фитнесу его популяции, деградировал. Он либо отдавал все ресурсы одному компоненту, либо сжимал все популяции к нулю, — тогда как оценка по лучшему найденному решению работала устойчиво. Как выяснится, это наблюдение глубже, чем кажется, и воспроизводится далеко за пределами нечёткой логики.
Дословно перенести конструкцию на наш фреймворк нельзя по принципиальной причине. Стенд серии сравнивает алгоритмы при строго одинаковом бюджете: фиксированном числе обращений к целевой функции. Однако оригинальный COBRA свободно раздувает и сжимает суммарный размер популяции по ходу работы. Для честного сравнения с алгоритмами рейтинга нужно зафиксировать суммарный popSize. Адаптацию следует свести к перераспределению квот между шестью субпопуляциями.Это ключевое проектное решение реализации. Из‑за него работу пришлось вести как эксперимент: каждый механизм координации заново проверялся при фиксированном бюджете, без опоры на выводы первоисточника (они получены в иных условиях).
Первый и главный вопрос — работает ли кооперация вообще. Отключение коммуникации превращает COBRA в шесть изолированных алгоритмов, делящих общий бюджет, и стоит это дорого: 35.98% против ~41% у базы. Пять процентных пунктов — многократно больше шума, так что обмен между популяциями не косметика, а источник всего преимущества над простым портфелем методов. Уже это оправдывает существование кооперативного слоя: разнородные поисковые механизмы, обменивающиеся находками, действительно сильнее самих себя поодиночке.
Куда интереснее оказался вопрос, чем именно они обмениваются. В нашей реализации коммуникация выполнена агрессивно: худшая особь получает от донора не только стартовую точку, но и личную память — cB (best coordinates) и fB (best fitness).
Рисунок 1. COBRA: архитектура
Шесть компонентных алгоритмов имеют равные фиксированные квоты внутри одной популяции; кооперация осуществляется исключительно через коммуникационное кольцо, где худшие агенты наследуют лучшую точку донора вместе с его личной памятью (cB/fB). Обмен только точкой эквивалентен отсутствию кооперации; перераспределение квот не даёт преимуществ при фиксированном вычислительном бюджете.
Псевдокод алгоритма:
COBRA — Co-Operation of Biology Related Algorithms Init: распределить popSize агентов поровну между 6 компонентами для каждого агента: скорость v = 0, вес FSS w = wMax/2 для каждого компонента k: fBest_k = -∞, n_k = popSize/6 случайная инициализация позиций всех агентов Moving (эпоха t): scale = 1 - 0.9·t/T // отжиг радиусов для каждого агента i с владельцем k: k = PSO: v = 0.729·v + 1.49445·r1◦(cB_i - c) + 1.49445·r2◦(cBest_k - c) c = c + v k = WPS: вожак (fB_i = fBest_k): c = c + U(-1,1)◦0.1·scale·range стая: c = c + U(0,1)◦(cBest_k - c) k = FFA: для каждого j из k с fB_j > fB_i: β = exp(-4·d²norm(c, cB_j)) c = c + β·(cB_j - c) + 0.05·scale·U(-0.5,0.5)◦range k = CSA: c = c + 0.2·Levy()◦(c - cBest_k) покоординатно с P=0.25: c = c + U(0,1)·(cB_p1 - cB_p2) k = BA: f = U(0,1); v = v + (c - cBest_k)·f; c = c + v с P=0.5: c = cBest_k + 0.01·scale·N(0,1)◦range k = FSS: c = c + U(-1,1)◦0.05·scale·range // индивидуальный c = c + Inst // инстинктивный (t-1) c = c - dir·U(0,1)·0.1·scale·(c - Bary) // волевой (t-1) привести c к [rangeMin, rangeMax] с шагом rangeStep Revision: обновить cB_i/fB_i агентов, cB/fB глобальные для каждого k: пересчитать fAvg_k, fBest_k, cBest_k // миграция к победителю w = argmax fBest_k; l = argmin fBest_k если w ≠ l и n_l > minPop: худший агент l переходит к w, v = 0 // защита от застоя если fB не улучшался stagnPeriod эпох: один агент от argmax n_k к argmin n_k // коммуникация (раз в commPeriod эпох) для каждого k: m = round(commPart·n_k) худших агентов k получают c, cB, fB лучших решений других компонентов (доноры по кругу), v = 0, w = wMax/2 // бухгалтерия FSS (для следующей эпохи) df_i = max(0, f_i - fP_i); веса: w_i += df_i/max(df), кламп [1, wMax] Inst = Σ df_i·(c_i - cP_i) / Σ df_i Bary = Σ w_i·c_i / Σ w_i; dir = +1 если Σw выросла, иначе -1 fP = f, cP = c для всех агентов Внешний цикл: Moving → оценка FF всей популяции → Revision, T эпох
Наша реализация опирается на две вспомогательные структуры. Первая, S_COBRA_Ext, расширяет стандартного агента фреймворка состоянием, которое требуется не всем компонентам сразу. Вектор скорости v[] используют PSO и BA, вес рыбы w — механизм кормления FSS, а поле comp хранит идентификатор компонента-владельца. Именно это поле реализует ключевое архитектурное решение: одна популяция — шесть владельцев. Здесь агент навсегда закреплён за своим слотом массива a[], и любые пертурбации внутри кооперации сводятся к правке одного целого числа, без физических перемещений по буферам. Метод Init структуры выделяет вектор скорости под размерность задачи и обнуляет состояние.
//+------------------------------------------------------------------+ //| Structure | //+------------------------------------------------------------------+ struct S_COBRA_Ext // дополнительное состояние агента { double v []; // скорость (PSO, BA) double w; // вес рыбы (FSS) int comp; // принадлежность компоненту void Init(int coords) { ArrayResize(v, coords); ArrayInitialize(v, 0.0); w = 0.0; comp = 0; } };
Вторая структура, S_COBRA_Comp, агрегирует состояние компонента-алгоритма: лучшие найденные им координаты cBest[] с фитнесом fBest, средний текущий фитнес субпопуляции fAvg и её размер n. Вектор cBest — внутренний аттрактор компонента: к нему обращён социальный член PSO, на него ориентируется стая WPS, вокруг него строятся полёты Леви CSA и локальный поиск BA. До момента коммуникации аттракторы шести компонентов независимы, и субпопуляции разрабатывают шесть собственных траекторий поиска.
//+------------------------------------------------------------------+ //| Structure | //+------------------------------------------------------------------+ struct S_COBRA_Comp // состояние компонента-алгоритма { double cBest []; // лучшие найденные компонентом координаты double fBest; // лучший фитнес компонента double fAvg; // средний текущий фитнес субпопуляции int n; // размер субпопуляции void Init(int coords) { ArrayResize(cBest, coords); ArrayInitialize(cBest, 0.0); fBest = -DBL_MAX; fAvg = -DBL_MAX; n = 0; } };
Класс C_AO_COBRA наследует C_AO и выносит наружу пять параметров координационного слоя: суммарный размер популяции popSize (фиксирован на протяжении всей работы — это условие честного бюджета на стенде), минимальный размер субпопуляции minPop, период коммуникации commPeriod, долю замещаемых худших особей commPart и порог застоя stagnPeriod. Значение minPop одновременно служит выключателем миграции: при minPop = popSize/6 квоты заморожены равными, и перераспределение отключено (каноническая конфигурация по итогам тестирования).
Константы шести компонентов заданы в конструкторе и снабжены построчными комментариями: коэффициенты сжатия Клерка для PSO, шаг притяжения и радиус вожака WPS, привлекательность и поглощение FFA, масштаб Леви и вероятность abandonment CSA, частотный диапазон и радиус локального поиска BA, шаги и предельный вес FSS. Их вынос во внешние параметры подменил бы исследование координации подгонкой полутора десятков констант; наружу выведен только координационный слой, влияние которого и изучается.
Метод SetParams помимо чтения параметров содержит предохранители: popSize не может опуститься ниже числа компонентов (по агенту на каждого), minPop зажат в диапазон от 1 до popSize/6, период коммуникации — не меньше единицы, доля обмена — в пределах [0; 0.9], порог застоя — не меньше единицы. Приватная часть класса хранит массивы структур ext[] и comp[], агрегаты FSS, вычисляемые по итогам предыдущей эпохи (инстинктивный вектор fssInst[], барицентр fssBary[], суммарный вес и направление волевого оператора), а также счётчики эпох и застоя.
//+------------------------------------------------------------------+ //| Class | //+------------------------------------------------------------------+ class C_AO_COBRA : public C_AO { public: ~C_AO_COBRA() {} C_AO_COBRA() { ao_name = "COBRA"; ao_desc = "Co-Operation of Biology Related Algorithms"; ao_link = "https://www.mql5.com/ru/articles/23630"; popSize = 60; // суммарный размер популяции (фиксирован) minPop = 10; // минимальный размер субпопуляции компонента commPeriod = 10; // период коммуникации, эпох commPart = 0.2; // доля худших особей, замещаемых при коммуникации stagnPeriod = 15; // эпох застоя до шага ребалансировки ArrayResize(params, 5); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "minPop"; params [1].val = minPop; params [2].name = "commPeriod"; params [2].val = commPeriod; params [3].name = "commPart"; params [3].val = commPart; params [4].name = "stagnPeriod"; params [4].val = stagnPeriod; //--- константы компонентов (зашиты, см. шапку) psoW = 0.729; // PSO: инерция (Clerc) psoC1 = 1.49445; // PSO: когнитивный коэффициент psoC2 = 1.49445; // PSO: социальный коэффициент wpsStep = 1.0; // WPS: шаг притяжения к вожаку wpsBeta = 0.1; // WPS: радиус локального поиска вожака (доля диапазона) ffaBeta0 = 1.0; // FFA: базовая привлекательность ffaGamma = 4.0; // FFA: поглощение (на нормированной дистанции) ffaAlpha = 0.05; // FFA: случайная составляющая (доля диапазона) csaAlpha = 0.2; // CSA: масштаб шага Леви csaPa = 0.25; // CSA: вероятность abandonment (покоординатно) baFmin = 0.0; // BA: нижняя частота baFmax = 1.0; // BA: верхняя частота baSigma = 0.01; // BA: радиус локального поиска (доля диапазона) fssStepInd = 0.05; // FSS: индивидуальный шаг (доля диапазона) fssStepVol = 0.1; // FSS: волевой шаг fssWmax = 10.0; // FSS: максимальный вес рыбы } void SetParams() { popSize = (int)params [0].val; minPop = (int)params [1].val; commPeriod = (int)params [2].val; commPart = params [3].val; stagnPeriod = (int)params [4].val; //--- предохранители if(popSize < compNum) popSize = compNum; // минимум по одному агенту на компонент if(minPop < 1) minPop = 1; if(minPop > popSize / compNum) minPop = popSize / compNum; if(commPeriod < 1) commPeriod = 1; if(commPart < 0.0) commPart = 0.0; if(commPart > 0.9) commPart = 0.9; if(stagnPeriod < 1) stagnPeriod = 1; } bool Init(const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0); void Moving(); void Revision(); //--- видимые параметры int minPop; // минимальный размер субпопуляции int commPeriod; // период коммуникации (эпох) double commPart; // доля замещаемых худших особей int stagnPeriod; // эпох застоя до ребалансировки private: static const int compNum; // число компонентов (6) int epochs; // всего эпох (от стенда) int epochNow; // текущая эпоха S_COBRA_Ext ext []; // [popSize] — доп. состояние агентов S_COBRA_Comp comp []; // [compNum] — состояние компонентов //--- агрегаты FSS (по данным предыдущей эпохи) double fssInst []; // [coords] — инстинктивное смещение косяка double fssBary []; // [coords] — барицентр косяка double fssWsumPr; // суммарный вес косяка на предыдущей эпохе double fssVolDir; // направление волевого оператора: +1 сжатие, -1 расширение double fBprev; // fB предыдущей эпохи (трекинг застоя) int stagnCnt; // эпох без улучшения fB //--- константы компонентов double psoW, psoC1, psoC2; double wpsStep, wpsBeta; double ffaBeta0, ffaGamma, ffaAlpha; double csaAlpha, csaPa; double baFmin, baFmax, baSigma; double fssStepInd, fssStepVol, fssWmax; //--- вспомогательные void MoveAgent(int i, double scale); void Communication(); void MigrateAgent(int agentInd, int compTo); int WorstInComp(int k); int RandInComp(int k); double GaussBM(); double LevyStep(); }; const int C_AO_COBRA::compNum = 6;
После стандартной инициализации фреймворка метод сохраняет число эпох для расписания отжига, сбрасывает трекинг застоя, выделяет и инициализирует массивы структур и агрегаты FSS. Агенты распределяются между компонентами по кругу — i % 6, — что при кратном шести popSize даёт равные квоты; веса рыб выставляются в середину диапазона, счётчики субпопуляций накапливаются по фактическому распределению.
//+------------------------------------------------------------------+ //| Init | //+------------------------------------------------------------------+ bool C_AO_COBRA::Init(const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0) { if(!StandardInit(rangeMinP, rangeMaxP, rangeStepP)) return false; epochs = epochsP; if(epochs < 1) epochs = 1; epochNow = 0; fBprev = -DBL_MAX; stagnCnt = 0; //--- буферы (массивы структур) ArrayResize(ext, popSize); ArrayResize(comp, compNum); for(int i = 0; i < popSize; i++) ext [i].Init(coords); for(int k = 0; k < compNum; k++) comp [k].Init(coords); ArrayResize(fssInst, coords); ArrayResize(fssBary, coords); ArrayInitialize(fssInst, 0.0); ArrayInitialize(fssBary, 0.0); fssWsumPr = 0.0; fssVolDir = 1.0; //--- равномерное распределение агентов по компонентам for(int i = 0; i < popSize; i++) { ext [i].comp = i % compNum; ext [i].w = fssWmax * 0.5; comp [ext [i].comp].n++; } return true; }
Moving следует стандартной схеме серии: первый вызов рассеивает популяцию равномерно по диапазону поиска с приведением к сетке SeInDiSp и взводит флаг revision. Последующие вызовы инкрементируют счётчик эпох, вычисляют коэффициент отжига scale = 1 − 0.9·t/T, линейно сжимающий радиусы локальных поисков от полного до одной десятой, и прогоняют каждого агента через MoveAgent.
//+------------------------------------------------------------------+ //| Moving | //+------------------------------------------------------------------+ void C_AO_COBRA::Moving() { //--- первый прогон: вся популяция случайна if(!revision) { for(int i = 0; i < popSize; i++) { for(int c = 0; c < coords; c++) a [i].c [c] = u.SeInDiSp(u.RNDfromCI(rangeMin [c], rangeMax [c]), rangeMin [c], rangeMax [c], rangeStep [c]); } revision = true; return; } epochNow++; if(epochNow > epochs) epochNow = epochs; //--- отжиг радиусов локальных поисков (WPS, FFA, BA, FSS) double scale = 1.0 - 0.9 * (double)epochNow / (double)epochs; for(int i = 0; i < popSize; i++) MoveAgent(i, scale); }
MoveAgent — диспетчер: один switch по владельцу агента, шесть веток, каждая — компонент-алгоритм в миниатюре. Решение сознательно прямолинейное: шесть механизмов движения читаются подряд и сравниваются глазами.
Ветка PSO — каноника с коэффициентами Клерка: скорость складывается из инерционного члена, когнитивного притяжения к личному лучшему cB и социального — к аттрактору компонента cBest, случайные множители r1 и r2 генерируются покоординатно, что исключает диагональное смещение поиска. Ветка WPS различает две роли по признаку совпадения личного лучшего с fBest компонента. Вожак ведёт локальный случайный поиск в кубе с ребром 10% диапазона, затухающим по отжигу, остальная стая покоординатно подтягивается к cBest со случайным множителем. При единичном шаге wpsStep это геометрическое стягивание с сохранением разброса.
Ветка FFA перебирает более ярких соседей своей субпопуляции: привлекательность вычисляется экспонентой от квадрата дистанции, нормированного на диапазон и размерность, с коэффициентом поглощения 4, к каждому притяжению добавляется покоординатный шум амплитудой 5% диапазона с отжигом. Светлячок притягивается к личным лучшим позициям cB соседей, а не к мгновенным координатам. В батчевой архитектуре мгновенные позиции меняются одновременно, и погоня за ними означала бы гонку за движущимися мишенями внутри эпохи. Ветка CSA складывает покоординатный полёт Леви относительно cBest с abandonment-механизмом. Каждая координата с вероятностью 0.25 получает добавку смещённого случайного блуждания между личными лучшими двух случайных гнёзд субпопуляции. Эта ветка, среди прочего, не даёт застыть агенту, сидящему точно в cBest, для которого множитель Леви-шага обнуляется.
Ветка BA обновляет скорость частотным правилом v += (c − cBest)·f со случайной частотой из [0; 1] и с вероятностью 0.5 переизлучает агента в гауссову окрестность cBest радиусом 1% диапазона с отжигом. При этом скорость сознательно не ограничена. Вариант с клампом и сбросом был проверен на стенде и измеримого выигрыша не дал, а дивергентные скорости части агентов попутно обеспечивают бесплатное обследование границ диапазона, куда их прижимает SeInDiSp.
Ветка FSS складывает три слагаемых: индивидуальный случайный шаг 5% диапазона с отжигом, коллективно-инстинктивный сдвиг fssInst и волевое сжатие либо расширение относительно барицентра fssBary. Оба коллективных оператора вычислены по итогам предыдущей эпохи, это цена перекладки последовательной схемы FSS на конвейер типа: сгенерировали — оценили — обновили. Завершает метод общее для всех веток приведение координат к диапазону и шагу задачи.
//+------------------------------------------------------------------+ //| MoveAgent — один шаг агента по правилам его компонента | //+------------------------------------------------------------------+ void C_AO_COBRA::MoveAgent(int i, double scale) { int k = ext [i].comp; double x, r1, r2; switch(k) { //--- 0: PSO ---------------------------------------------------- case 0: { for(int c = 0; c < coords; c++) { r1 = u.RNDprobab(); r2 = u.RNDprobab(); ext [i].v [c] = psoW * ext [i].v [c] + psoC1 * r1 * (a [i].cB [c] - a [i].c [c]) + psoC2 * r2 * (comp [k].cBest [c] - a [i].c [c]); a [i].c [c] += ext [i].v [c]; } break; } //--- 1: WPS ---------------------------------------------------- case 1: { bool leader = (a [i].fB == comp [k].fBest); for(int c = 0; c < coords; c++) { if(leader) a [i].c [c] += u.RNDfromCI(-1.0, 1.0) * wpsBeta * scale * (rangeMax [c] - rangeMin [c]); else a [i].c [c] += u.RNDprobab() * wpsStep * (comp [k].cBest [c] - a [i].c [c]); } break; } //--- 2: FFA ---------------------------------------------------- case 2: { for(int j = 0; j < popSize; j++) { if(ext [j].comp != k || j == i) continue; if(a [j].fB <= a [i].fB) continue; //--- нормированная квадратичная дистанция до более яркого double d2 = 0.0; for(int c = 0; c < coords; c++) { double dn = (a [j].cB [c] - a [i].c [c]) / (rangeMax [c] - rangeMin [c]); d2 += dn * dn; } d2 /= (double)coords; double beta = ffaBeta0 * MathExp(-ffaGamma * d2); for(int c = 0; c < coords; c++) a [i].c [c] += beta * (a [j].cB [c] - a [i].c [c]) + ffaAlpha * scale * (u.RNDprobab() - 0.5) * (rangeMax [c] - rangeMin [c]); } break; } //--- 3: CSA ---------------------------------------------------- case 3: { //--- полёт Леви вокруг лучшего решения компонента for(int c = 0; c < coords; c++) a [i].c [c] += csaAlpha * LevyStep() * (a [i].c [c] - comp [k].cBest [c]); //--- abandonment: смещённое случайное блуждание по подмножеству координат int p1 = RandInComp(k); int p2 = RandInComp(k); for(int c = 0; c < coords; c++) { if(u.RNDprobab() < csaPa) a [i].c [c] += u.RNDprobab() * (a [p1].cB [c] - a [p2].cB [c]); } break; } //--- 4: BA ----------------------------------------------------- case 4: { double freq = baFmin + (baFmax - baFmin) * u.RNDprobab(); for(int c = 0; c < coords; c++) { ext [i].v [c] += (a [i].c [c] - comp [k].cBest [c]) * freq; a [i].c [c] += ext [i].v [c]; } //--- локальный поиск вокруг лучшего решения компонента if(u.RNDprobab() > 0.5) { for(int c = 0; c < coords; c++) a [i].c [c] = comp [k].cBest [c] + baSigma * scale * GaussBM() * (rangeMax [c] - rangeMin [c]); } break; } //--- 5: FSS ---------------------------------------------------- default: { for(int c = 0; c < coords; c++) { //--- индивидуальное движение x = a [i].c [c] + u.RNDfromCI(-1.0, 1.0) * fssStepInd * scale * (rangeMax [c] - rangeMin [c]); //--- коллективно-инстинктивное движение (данные предыдущей эпохи) x += fssInst [c]; //--- коллективно-волевое движение (данные предыдущей эпохи) x -= fssVolDir * u.RNDprobab() * fssStepVol * scale * (x - fssBary [c]); a [i].c [c] = x; } break; } } for(int c = 0; c < coords; c++) a [i].c [c] = u.SeInDiSp(a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); }
Метод Revision начинается стандартно — обновлением личных лучших агентов и глобального лучшего. Затем метод пересчитывает статистику компонентов: fAvg по текущим фитнесам субпопуляции, fBest и cBest по личным лучшим её членов. Далее следует координационный слой.
Трекинг застоя сравнивает глобальный лучший с сохранённым значением предыдущей эпохи и либо сбрасывает, либо наращивает счётчик stagnCnt. Миграция определяет победителя и аутсайдера по среднему фитнесу fAvg — в соответствии с первоисточником — и, если у аутсайдера есть запас сверх minPop, передаёт победителю его худшего агента через MigrateAgent. В канонической конфигурации minPop = popSize/6 блокирует эту ветвь намеренно. Как покажет раздел тестирования, пользы перераспределение не приносит, однако код оставлен рабочим, и одно значение параметра включает механизм обратно для экспериментов. Защита от застоя срабатывает по достижении stagnPeriod и делает один шаг ребалансировки — переводит агента от самой населённой субпопуляции к самой малочисленной, а при замороженных квотах спит и она.
Коммуникация вызывается раз в commPeriod эпох. Замыкает Revision бухгалтерия FSS: по разностям текущего и предыдущего фитнеса вычисляются приросты df с отсечкой отрицательных, кормление наращивает веса пропорционально df/max(df) с клампом в [1; wMax], инстинктивный вектор собирается как взвешенная по приростам сумма успешных смещений c − cP, барицентр — как взвешенное по весам среднее позиций. Направление волевого оператора задаётся знаком изменения суммарного веса косяка: потяжелел — сжатие, полегчал — расширение. Последним действием позиции и фитнесы всех агентов сохраняются как предыдущие — сырьё FSS для следующей эпохи. Защита от неинициализированного fP на первой эпохе обнуляет приросты.
//+------------------------------------------------------------------+ //| Revision | //+------------------------------------------------------------------+ void C_AO_COBRA::Revision() { //--- личные и глобальный лучшие for(int i = 0; i < popSize; i++) { if(a [i].f > a [i].fB) { a [i].fB = a [i].f; ArrayCopy(a [i].cB, a [i].c, 0, 0, WHOLE_ARRAY); } if(a [i].f > fB) { fB = a [i].f; ArrayCopy(cB, a [i].c, 0, 0, WHOLE_ARRAY); } } //--- статистика компонентов for(int k = 0; k < compNum; k++) { comp [k].fAvg = 0.0; for(int i = 0; i < popSize; i++) { if(ext [i].comp != k) continue; comp [k].fAvg += a [i].f; if(a [i].fB > comp [k].fBest) { comp [k].fBest = a [i].fB; ArrayCopy(comp [k].cBest, a [i].cB, 0, 0, WHOLE_ARRAY); } } if(comp [k].n > 0) comp [k].fAvg /= (double)comp [k].n; else comp [k].fAvg = -DBL_MAX; } //--- трекинг застоя if(fB > fBprev) { fBprev = fB; stagnCnt = 0; } else stagnCnt++; //--- миграция к победителю: лучший средний фитнес забирает у худшего int winner = 0; int loser = 0; for(int k = 1; k < compNum; k++) { if(comp [k].fAvg > comp [winner].fAvg) winner = k; if(comp [k].fAvg < comp [loser].fAvg) loser = k; } if(winner != loser && comp [loser].n > minPop) MigrateAgent(WorstInComp(loser), winner); //--- застой: шаг ребалансировки к равномерному распределению if(stagnCnt >= stagnPeriod) { int kMax = 0; int kMin = 0; for(int k = 1; k < compNum; k++) { if(comp [k].n > comp [kMax].n) kMax = k; if(comp [k].n < comp [kMin].n) kMin = k; } if(kMax != kMin && comp [kMax].n > comp [kMin].n + 1) MigrateAgent(WorstInComp(kMax), kMin); } //--- коммуникация между популяциями if(epochNow > 0 && epochNow % commPeriod == 0) Communication(); //--- бухгалтерия FSS (использует f против fP предыдущей эпохи) double dfMax = 0.0; double df; for(int i = 0; i < popSize; i++) { if(ext [i].comp != 5) continue; if(a [i].fP == -DBL_MAX) continue; df = a [i].f - a [i].fP; if(df > dfMax) dfMax = df; } double sumDf = 0.0; double wSum = 0.0; ArrayInitialize(fssInst, 0.0); ArrayInitialize(fssBary, 0.0); for(int i = 0; i < popSize; i++) { if(ext [i].comp != 5) continue; df = (a [i].fP == -DBL_MAX) ? 0.0 : a [i].f - a [i].fP; if(df < 0.0) df = 0.0; //--- кормление if(dfMax > 0.0) { ext [i].w += df / dfMax; if(ext [i].w > fssWmax) ext [i].w = fssWmax; if(ext [i].w < 1.0) ext [i].w = 1.0; } //--- числитель инстинктивного оператора: успешные смещения if(df > 0.0) { for(int c = 0; c < coords; c++) fssInst [c] += df * (a [i].c [c] - a [i].cP [c]); sumDf += df; } //--- числитель барицентра for(int c = 0; c < coords; c++) fssBary [c] += ext [i].w * a [i].c [c]; wSum += ext [i].w; } if(sumDf > 0.0) { for(int c = 0; c < coords; c++) fssInst [c] /= sumDf; } else ArrayInitialize(fssInst, 0.0); if(wSum > 0.0) { for(int c = 0; c < coords; c++) fssBary [c] /= wSum; } fssVolDir = (wSum >= fssWsumPr) ? 1.0 : -1.0; // косяк потяжелел -> сжатие fssWsumPr = wSum; //--- сохранение предыдущего состояния для следующей эпохи for(int i = 0; i < popSize; i++) { a [i].fP = a [i].f; ArrayCopy(a [i].cP, a [i].c, 0, 0, WHOLE_ARRAY); } }
Следующий метод является сердцем алгоритма. Для каждого компонента вычисляется число замен m = round(commPart·n), ограниченное сверху величиной n − 1. Это означает, что лучшая особь субпопуляции неприкосновенна. Затем m раз подряд выбирается худший по текущему фитнесу агент и замещается лучшим решением очередного донора. Доноры назначаются по кругу, собственный компонент пропускается. Жертва наследует от донора всё: стартовую точку c, личную память cB и fB; её скорость обнуляется, вес рыбы возвращается к середине диапазона.
Присвоение донорского fBest в поле f решает и техническую задачу — служит маркером против повторного выбора той же особи внутри вызова. На следующей эпохе стенд перезапишет f честной оценкой, так что фабрикации фитнеса не происходит. Наследование памяти — принципиальный и экспериментально проверенный выбор: жертва становится элитным рестартом, полноценным носителем чужого лучшего решения, которое оператор её компонента немедленно начинает разрабатывать собственным способом. Вариант мягкого обмена — передача одной лишь стартовой точки, оказался на стенде эквивалентен полному отключению коммуникации. Подробный разбор этого результата ждёт читателя в разделе тестирования.
//+------------------------------------------------------------------+ //| Communication — доля худших особей каждой популяции замещается | //| лучшими решениями других компонентов (доноры по кругу) | //+------------------------------------------------------------------+ void C_AO_COBRA::Communication() { for(int k = 0; k < compNum; k++) { int m = (int)MathRound(commPart * comp [k].n); if(m < 1) continue; if(m > comp [k].n - 1) m = comp [k].n - 1; // лучшую особь не трогаем int donor = (k + 1) % compNum; for(int r = 0; r < m; r++) { int w = WorstInComp(k); if(w < 0) break; if(donor == k) donor = (donor + 1) % compNum; // свой компонент донором не бывает ArrayCopy(a [w].c, comp [donor].cBest, 0, 0, WHOLE_ARRAY); ArrayCopy(a [w].cB, comp [donor].cBest, 0, 0, WHOLE_ARRAY); a [w].fB = comp [donor].fBest; a [w].f = comp [donor].fBest; ArrayInitialize(ext [w].v, 0.0); ext [w].w = fssWmax * 0.5; donor = (donor + 1) % compNum; } } }
MigrateAgent меняет принадлежность агента правкой поля comp с корректировкой счётчиков субпопуляций, обнуляет скорость и возвращает вес рыбы к середине — состояние, накопленное в одном компоненте, не имеет смысла в другом.
//+------------------------------------------------------------------+ //| MigrateAgent — смена принадлежности агента (слот сохраняется), | //| скоростные состояния мигранта сбрасываются | //+------------------------------------------------------------------+ void C_AO_COBRA::MigrateAgent(int agentInd, int compTo) { if(agentInd < 0) return; int compFrom = ext [agentInd].comp; if(compFrom == compTo) return; comp [compFrom].n--; comp [compTo].n++; ext [agentInd].comp = compTo; ArrayInitialize(ext [agentInd].v, 0.0); ext [agentInd].w = fssWmax * 0.5; }
WorstInComp — линейный поиск худшего по текущему фитнесу.
//+------------------------------------------------------------------+ //| WorstInComp — индекс худшего (по текущему f) агента компонента | //+------------------------------------------------------------------+ int C_AO_COBRA::WorstInComp(int k) { int ind = -1; double f = DBL_MAX; for(int i = 0; i < popSize; i++) { if(ext [i].comp != k) continue; if(a [i].f < f) { f = a [i].f; ind = i; } } return ind; }
RandInComp — выбор равновероятного случайного агента внутри компонента.
//+------------------------------------------------------------------+ //| RandInComp — случайный агент внутри компонента | //+------------------------------------------------------------------+ int C_AO_COBRA::RandInComp(int k) { int cnt = 0; for(int i = 0; i < popSize; i++) if(ext [i].comp == k) cnt++; if(cnt == 0) return 0; int target = u.RNDintInRange(0, cnt - 1); for(int i = 0; i < popSize; i++) { if(ext [i].comp != k) continue; if(target == 0) return i; target--; } return 0; }
GaussBM возвращает стандартную нормальную величину преобразованием Бокса-Мюллера с защитой от нулевого аргумента логарифма.
//+------------------------------------------------------------------+ //| GaussBM — стандартная нормальная величина, Бокс-Мюллер | //+------------------------------------------------------------------+ double C_AO_COBRA::GaussBM() { double r1 = u.RNDprobab(); double r2 = u.RNDprobab(); if(r1 <= 0.0) r1 = 1.0e-12; return MathSqrt(-2.0 * MathLog(r1)) * MathCos(2.0 * M_PI * r2); }
LevyStep реализует шаг Мантеньи для β = 1.5 с предвычисленной σ = 0.696575 как отношение gU/|gV|^(1/β) двух гауссовых величин и ограничением |step| ≤ 10 — защитой от взрывных значений, способных единичным скачком выбросить кукушку на границу диапазона.
//+------------------------------------------------------------------+ //| LevyStep — шаг полёта Леви, алгоритм Мантеньи, beta = 1.5 | //+------------------------------------------------------------------+ double C_AO_COBRA::LevyStep() { static const double beta = 1.5; static const double sigmaU = 0.696575; // предвычислено для beta = 1.5 double gU = GaussBM() * sigmaU; double gV = GaussBM(); if(MathAbs(gV) < 1.0e-12) gV = 1.0e-12; double step = gU / MathPow(MathAbs(gV), 1.0 / beta); //--- защита от взрывных шагов if(step > 10.0) step = 10.0; if(step < -10.0) step = -10.0; return step; }
Результаты тестов
Каноническая конфигурация COBRA — суммарная популяция 60 агентов с равными замороженными квотами по 10 на компонент, обмен пятой частью худших особей каждые 10 эпох — показала на стенде следующие результаты:
=============================
5 Hilly's; Func runs: 10000; result: 0.7075827714675647
25 Hilly's; Func runs: 10000; result: 0.47633305564548173
500 Hilly's; Func runs: 10000; result: 0.29376941566326953
=============================
5 Forest's; Func runs: 10000; result: 0.7858382701655537
25 Forest's; Func runs: 10000; result: 0.3111803778575543
500 Forest's; Func runs: 10000; result: 0.08177025934742739
=============================
5 Megacity's; Func runs: 10000; result: 0.5693333333333334
25 Megacity's; Func runs: 10000; result: 0.32
500 Megacity's; Func runs: 10000; result: 0.14188000000000084
=============================
All score: 3.68769 (40.97%)
Профиль по функциям типичен для методов с сильной эксплуатационной составляющей. В малой размерности алгоритм уверен: 0.71 на Hilly и 0.79 на Forest — неплохие значения, элитистский обмен быстро сосредотачивает портфель операторов на лучшем найденном бассейне, и шесть разных механизмов движения дожимают его эффективнее, чем сделал бы любой из них в одиночку. Дискретная Megacity в малой размерности даётся тяжелее (0.57) — ступенчатый ландшафт обесценивает тонкую локальную разработку, которой сильна кооперация. С ростом размерности картина выравнивается до среднего по серии уровня, а самой тяжёлой клеткой ожидаемо оказывается Forest 500 (0.082): острые пики в высокой размерности требуют широкого систематического исследования, на которое у сходящегося к общему бассейну портфеля не остаётся ни бюджета, ни механизма.
Важно подчеркнуть воспроизводимость: четыре независимых прогона базовой конфигурации дали от 39.74 до 41.71%, поэтому публикуемое значение 40.97% следует читать как «41 ± 1», а не как точечную оценку. Эта же калибровка шума определила методологию всего раздела: значимыми мы признаём только эффекты, кратно превышающие двухпунктовый коридор.
Протокол завершает композитный античит‑тест — обязательная для серии проверка на эксплуатацию геометрии тестовых функций. Десять координат задачи разбиваются на пять пар, и каждая пара принадлежит собственной функции — Hilly, Forest, Megacity, Peaks и Skin — со своим диапазоном и своей геометрией оптимума; фитнесом агента служит среднее по пяти функциям. Любой осевой или диагональный трюк, дающий выигрыш на симметричных ландшафтах основного стенда, на таком составном рельефе способен помочь максимум на одной паре из пяти и в общем счёте не виден.
Для COBRA эта проверка не формальность. Хотя случайности всех шести компонентов генерируются покоординатно и намеренных связей между осями в реализации нет, три канонических механизма, унаследованных от первоисточников, связывают координаты скалярными множителями: привлекательность β светлячка вычисляется от полной дистанции и умножает весь вектор разности, частота летучей мыши едина для всех координат агента, а инстинктивный вектор FSS общий для всего косяка. Теоретически такие связки могут порождать слабую осевую корреляцию траекторий. Нужно количественно проверить, не даёт ли она незаслуженный выигрыш на симметричных функциях.
COBRA|Co-Operation of Biology Related Algorithms|60.0|10.0|10.0|0.2|15.0|
=============================
Composite anti-cheat test: Hilly + Forest + Megacity + Peaks + Skin
Coordinates: 10; Epochs: 166; Repeats: 10
=============================
Run 1/10: 0.6460199058552666
Run 2/10: 0.6533200096658662
Run 3/10: 0.7960661240559889
Run 4/10: 0.6072814662671574
Run 5/10: 0.6457604027057026
Run 6/10: 0.6861950483559006
Run 7/10: 0.7058370356461463
Run 8/10: 0.5923478597680134
Run 9/10: 0.7162676751458411
Run 10/10: 0.7838829742267341
=============================
Average result: 0.6832978502 (68.33%)
=============================
Ответ получен: средний результат десяти прогонов составил 68.33%. Сравним его с ожиданием: три теста основного стенда с пятью функциями имеют ту же размерность в десять координат, и среднее по ним равно 68.8% — на смешанном ландшафте из пяти разнородных геометрий алгоритм показал практически то же самое, что и на однородных функциях равной размерности, с точностью до долей процентного пункта. Никакого проседания, которое выдало бы зависимость от осевой симметрии, не наблюдается: производительность COBRA переносится на составной рельеф без потерь. Канонические скалярные связки компонентов остаются тем, чем являются по замыслу их авторов, — механикой поиска, а не эксплуатацией геометрии стенда. Вердикт протокола: алгоритм честен.
Ниже можно увидеть визуализацию работы алгоритма как на стандартных функциях, так и на двух дополнительных.
COBRA на тестовой функции Hilly
COBRA на тестовой функции Forest
COBRA на тестовой функции Megacity
COBRA на тестовой функции Ackley
COBRA на тестовой функции Paraboloid
По результатам тестирования алгоритм COBRA в рейтинговой таблице лучших оптимизационных методов представлен ознакомительно.
| 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 | 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 |
| 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 | 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 |
| 31 | 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 |
| 32 | 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 |
| 33 | 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 |
| 34 | 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 |
| 35 | 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 |
| 36 | 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 |
| 37 | 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 |
| 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 |
| 39 | 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 |
| 40 | 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 |
| 41 | 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 |
| 42 | 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 |
| 43 | 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 |
| 44 | 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 |
| 45 | 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 |
| COBRA | co-operation_of_biology_related_algorithms | 0,70758 | 0,47633 | 0,29376 | 1,47767 | 0,78583 | 0,31118 | 0,08177 | 1,17878 | 0,56933 | 0,32000 | 0,14188 | 1,03121 | 3,688 | 40,97 | |
| 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 | |
Выводы
COBRA пришла в серию как носитель привлекательной идеи: не выбирать алгоритм под задачу, а заставить несколько алгоритмов работать сообща. Экспериментальная проверка на равном фиксированном бюджете оставила от оригинальной конструкции меньше половины — и это, пожалуй, самый содержательный результат статьи. Динамическое перераспределение вычислительных ресурсов, центральный механизм первоисточника и предмет нечёткого контроллера в работе 2017 года, не показало пользы ни по среднему, ни по лучшему фитнесу. Первый критерий патологичен по построению, второй монотонен и навсегда закрепляет ранний успех одного компонента. Защита от застоя при замороженных квотах спит по определению. Работает же то, что в описаниях COBRA обычно проходит вспомогательной строкой, — коммуникация, и работает только в полной, агрессивной форме: худшие особи должны наследовать от доноров не координаты, а память. Пересадка одной лишь стартовой точки эквивалентна отсутствию обмена; пересадка личного лучшего превращает худших агентов в элитные рестарты, и портфель из шести операторов движения начинает разрабатывать общий бассейн — каждый своим способом. Пять процентных пунктов композита, отделяющие кооперацию от простой суммы частей, целиком заработаны этим механизмом.
Для конструкции, собранной из шести алгоритмов среднего уровня, это честный результат с ясной моралью: координация окупает себя, однако не творит чудес — потолок портфеля определяется не числом участников, а качеством механизма обмена. Практическую ценность алгоритму добавляет нечувствительность к настройке: все исследованные оси, кроме включения-выключения коммуникации, оказались плоскими, и конфигурация по умолчанию близка к потолку возможностей.
Что читатель уносит с собой. Во-первых, готовый рабочий класс C_AO_COBRA — не только алгоритм, но и каркас для собственных экспериментов с кооперацией: архитектура: одна популяция — шесть владельцев, расширяется новым компонентом ценой одной ветки в MoveAgent, и каждый может собрать портфель из любых методов серии, заменив наши шесть на свои.
Во-вторых, воспроизводимую методику препарирования составных алгоритмов: отключение механизмов по одному, обязательные контрольные прогоны, калибровка шума стенда повторными измерениями одной конфигурации — приёмы, применимые к любой гибридной конструкции, а не только к COBRA.
И в-третьих, главное — переносимый практический принцип: если вы объединяете несколько методов оптимизации, будь то подбор параметров торговой системы несколькими алгоритмами или ансамбль любой другой природы, решает не количество участников и не хитрость распределения ресурсов между ними, а содержание обмена. Передавайте лучшие решения вместе с контекстом, в котором они найдены.
Рисунок 2. Цветовая градация алгоритмов по соответствующим тестам
Рисунок 3. Гистограмма результатов тестирования алгоритмов (по шкале от 0 до 100: чем больше, тем лучше, где 100 — максимально возможный теоретический результат). В архиве скрипт для расчёта рейтинговой таблицы
Плюсы и минусы алгоритма COBRA
Плюсы:
- Малочувствителен к настройке: рабочая конфигурация по умолчанию.
- Хорошие результаты в малой размерности на гладких и лесных ландшафтах.
- Архитектура: одна популяция — шесть владельцев сохраняет строгий бюджет FF и легко расширяется новыми компонентами.
Минусы:
- Невысокий итоговый результат: кооперация компонентов среднего уровня не достигает лучших специализированных алгоритмов.
- Слабость на острых многоэкстремальных ландшафтах высокой размерности (Forest 500).
- Заявленное в первоисточнике перераспределение ресурсов на фиксированном бюджете не работает — от оригинальной идеи остаётся только коммуникация.
- Код заметно объёмнее одиночного алгоритма: шесть механизмов движения плюс координационный слой.
К статье прикреплён архив с актуальными версиями кодов алгоритмов. Автор статьи не несёт ответственности за абсолютную точность в описании канонических алгоритмов, во многие из них внесены изменения для улучшения поисковых возможностей. Выводы и суждения, представленные в статьях, основываются на результатах проведённых экспериментов.
Программы, используемые в статье
| # | Имя | Тип | Описание |
|---|---|---|---|
| 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_COBRA.mq5 | Скрипт | Испытательный стенд для COBRA |
Предупреждение: все права на данные материалы принадлежат MetaQuotes Ltd. Полная или частичная перепечатка запрещена.
Данная статья написана пользователем сайта и отражает его личную точку зрения. Компания MetaQuotes Ltd не несет ответственности за достоверность представленной информации, а также за возможные последствия использования описанных решений, стратегий или рекомендаций.
Особенности написания Пользовательских Индикаторов
Моделирование рынка: Position View (X)
Автоматизация торговых стратегий на MQL5 (Часть 36): Торговля по зонам спроса и предложения на основе модели ретеста и импульса
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Вы принимаете политику сайта и условия использования