Алгоритм оптимизации шимпанзе: от ChOA к BChimp

Содержание

1. Введение
2. Реализация алгоритма
3. Результаты тестов
4. Выводы

Введение

Среди популяционных метаэвристик, механизмы которых заимствованы у коллективного поведения животных, отдельную нишу занимают алгоритмы, вдохновлённые групповой охотой. Самый известный их представитель — алгоритм серого волка (GWO) — построен на простой иерархии: вся стая движется к трём лучшим особям, и каждый волк действует по одной и той же стратегии. Алгоритм оптимизации шимпанзе Chimp Optimization Algorithm (ChOA), предложенный Khishe и Mosavi в 2020 году, внешне напоминает эту схему, но основан на иной идее — неоднородности интеллекта внутри группы.

Шимпанзе живут в обществе типа fission-fusion, где состав и численность охотничьей группы постоянно меняются, и где успех охоты зависит не от единообразия, а от разделения ролей. Авторы алгоритма выделяют четыре типа особей с разными способностями и стратегиями: водители (drivers) следуют за добычей и теснят её, не атакуя; преградители (barriers) перекрывают пути отхода, загоняя жертву в ловушку; преследователи (chasers) быстро настигают добычу, вызывая панику; и, наконец, атакующие (attackers) предугадывают путь бегства и завершают охоту. В терминах оптимизации эти четыре роли назначаются четырём лучшим решениям популяции, и остальные особи обновляют свои позиции, ориентируясь сразу на всю четвёрку, а не на единственного лидера. Именно эта разнородность — разные законы изменения коэффициентов для разных групп — и отличает ChOA от однородного семейства GWO.

Второй опорой алгоритма служит то, что авторы называют социальной мотивацией. Помимо рационального преследования добычи, шимпанзе склонны к импульсивному, хаотическому поведению — стремлению добыть мясо любой ценой ради последующего социального обмена. В математической модели это превращается в хаотическую компоненту: с некоторой вероятностью особь обновляет свою позицию не по охотничьим формулам, а скачком, заданным хаотическим отображением. Замысел этого механизма — придать алгоритму способность вырываться из локальных оптимумов, куда плавный коллективный поиск неизбежно сходится.

Математически ChOA описывается компактно. Положение каждой особи пересчитывается как среднее четырёх кандидатов. Каждый кандидат притягивается к своему вожаку через расстояние, искажённое случайными и хаотическими коэффициентами. Динамический коэффициент, отвечающий за баланс разведки и эксплуатации, монотонно убывает по ходу итераций: вначале шаги велики и популяция широко обследует пространство, к концу — стягивается к найденным лидерам. Поверх этого работает хаотическое замещение, описанное выше.

ChOA по своей природе континуален. Однако многие прикладные задачи требуют бинарного решения. Классический пример — это отбор признаков в машинном обучении, где из тысяч признаков нужно выбрать подмножество, а ответ кодируется битовой строкой включён/исключён. Этот разрыв в 2023 году закрыли Ayeche и Alti, предложив Enhanced Binary Chimp (BChimp): они взяли ядро ChOA и добавили слой бинаризации в двух вариантах — BChimp1 (стохастическое скрещивание четырёх бинарных шагов) и BChimp2 (сигмоидальная передаточная функция). Именно эту работу мы берём за основу — из неё взяты конкретные кривые коэффициентов и сама формулировка алгоритма.

Но рейтинг у нас непрерывный, поэтому слой бинаризации снимается, и под ним обнажается то же непрерывное ядро — по механизму это соответствует исходному ChOA, круг замыкается. Соглашение об именах в статье: за реализацией мы сохраняем имя BChimp — конкретную работу, которую воспроизводим и тестируем, — а имя ChOA используем там, где речь идёт о непрерывном предке, давшем ядро.

В этой статье мы реализуем алгоритм в рамках стандартного фреймворка C_AO. Проведём его через привычный набор тестовых функций (Hilly, Forest, Megacity) на разных размерностях и оценим его место в общем рейтинге. По пути нам придётся внимательно сверить код с публикацией и с первоисточником. Также исправить унаследованный дефект коэффициента, который в бинарной задаче остаётся незаметным, а в континуальной разрушает поиск, — а заодно увидеть, что у алгоритма есть скрытые особенности, искажающие его оценку на привычных тестах.

Реализация алгоритма

Структура популяции и четвёрка вожаков. Популяция ChOA состоит из NN особей-шимпанзе, каждая из которых — точка-решение в пространстве поиска. На каждой итерации четыре лучших по приспособленности особи назначаются вожаками и получают роли: атакующий (Attacker), преградитель (Barrier), преследователь (Chaser) и водитель (Driver). Эта четвёрка несёт информацию о наиболее вероятном местоположении добычи; остальные особи перестраивают свои позиции, ориентируясь сразу на всех четырёх вожаков. 

Базовые уравнения охоты. Сближение особи с добычей описывается двумя векторными уравнениями. Сначала вычисляется расстояние между особью и преследуемой целью:

$$d=\mid c\cdot X_{prey}(t)-m\cdot X(t)\mid$$

$$$$

затем по нему — новое положение:

$$X(t+1)=X_{prey}(t)-a\cdot d$$

$$$$

Здесь $X(t)$ — текущая позиция особи, $X_{prey}(t)$ — позиция вожака, а $a$, $c$ и $m$ — коэффициенты, управляющие поведением. Коэффициент $a$ отвечает за величину и направление шага, $c$ — за вес позиции вожака в расчёте расстояния, $m$ — хаотический множитель, моделирующий импульсивность.

Динамические коэффициенты. Коэффициенты a и c строятся из убывающего управляющего параметра f и случайных чисел:

$$a = 2 f r_1 - f, \qquad c = 2 r_2, \qquad f = 2 - 2\frac{t}{T}$$​

где $t$ — номер текущей итерации, $T$ — общее число итераций, $r_1, r_2 \in [0,1]$. Параметр $f$ линейно убывает от 2 до 0: в начале прогона $|a|$ может превышать единицу, и особь делает крупные шаги (разведка), к концу $f \to 0$ и шаги стягиваются к вожакам (эксплуатация).

Разнородность четырёх ролей задаётся тем, что для каждой группы $r_1$ и $r_2$ масштабируются своими динамическими кривыми. Для четырёх групп:

$$\begin{aligned} c_1g_1 &= 1.95 - 2\left(\tfrac{t}{T}\right)^{1/3}, & c_2g_1 &= 2\left(\tfrac{t}{T}\right)^{1/3} + 0.5 \\ c_1g_2 &= 1.95 - 2\left(\tfrac{t}{T}\right)^{1/3}, & c_2g_2 &= 2\left(\tfrac{t}{T}\right)^{1/3} + 0.5 \\ c_1g_3 &= -2\left(\tfrac{t}{T}\right)^{3} + 2.5, & c_2g_3 &= 2\left(\tfrac{t}{T}\right)^{1/3} + 0.5 \\ c_1g_4 &= -2\left(\tfrac{t}{T}\right)^{3} + 2.5, & c_2g_4 &= 2\left(\tfrac{t}{T}\right)^{1/3} + 0.5 \end{aligned}$$​

Две группы используют корневой закон $\left(\tfrac{t}{T}\right)^{1/3}$ — быстрое убывание в начале и пологий хвост, ещё две — кубический  $\left(\tfrac{t}{T}\right)^{3}$, который наоборот долго держит высокое значение и резко падает в конце. Так группы получают разный баланс разведки и эксплуатации во времени. (Отметим: в эталонном коде авторов кривые $c_2g_2$​ и $c_2g_4$​ записаны через кубический закон, а не корневой, как в тексте статьи, — мелкое расхождение, к которому мы ещё вернёмся.)

Обновление позиции по четвёрке. Каждая особь рассчитывает четыре кандидата — по одному на вожака. Для атакующего:

$$D_a = \left| c_1 X_a - m X \right|, \qquad X_1 = X_a - a_1 D_a$$​

и аналогично $X_2, X_3, X_4$ для преградителя, преследователя и водителя со своими коэффициентами $a_k$, $c_k$​. Итоговое положение — среднее четырёх кандидатов:

$$X(t+1) = \frac{X_1 + X_2 + X_3 + X_4}{4}$$​​

Усреднение и есть механизм, стягивающий популяцию к лучшим решениям: каждая особь оказывается в центре тяжести четырёх притяжений.

Хаотическая компонента и социальная мотивация. Вторая опора алгоритма — хаотическое поведение, отражающее импульсивное стремление шимпанзе к добыче. С вероятностью 50 % обычное обновление по четвёрке заменяется скачком, заданным хаотическим отображением:

$$X(t+1) = \begin{cases} \dfrac{X_1 + X_2 + X_3 + X_4}{4}, & \mu < 0.5 \\[2mm] \text{хаотическое значение}, & \mu \ge 0.5 \end{cases}$$​

где $\mu \in [0,1]$ — случайное число. Хаотическое значение порождается одной из детерминированных карт — логистической, Гаусса, тентовой и т. п. Логистическая карта, например, итерируется как

$$x_{k+1} = 4 x_k (1 - x_k)$$

и при стартовом значении вне неподвижных точек даёт апериодическую последовательность в $(0,1)$. Замысел этой фазы — давать популяции выходы из локальных оптимумов, недостижимые плавным коллективным движением.

Бинаризация: BChimp1 и BChimp2. Сам ChOA континуален. Для задач, где решение — битовая строка (отбор признаков), Ayeche и Alti добавили к его ядру слой бинаризации в двух вариантах.

BChimp1 превращает каждый из четырёх кандидатов в бинарный шаг. Сначала непрерывный шаг прогоняется через сигмоид:

$$cstep = \frac{1}{1 + e^{-10\,(A \cdot D - 0.5)}}$$​

затем сравнивается со случайным числом, давая бинарный шаг, и складывается с позицией вожака:

$$bstep = \begin{cases} 1, & cstep \ge r \\ 0, & \text{иначе} \end{cases}, \qquad Y = \begin{cases} 1, & X_{leader} + bstep \ge 1 \\ 0, & \text{иначе} \end{cases}$$​

Из четырёх бинарных векторов $Y_1, \dots, Y_4$Y1​,…,Y4​ итоговая координата выбирается случайно — стохастическое скрещивание с равными долями по $\tfrac14$​.

BChimp2 идёт иначе: усредняет четыре непрерывных кандидата и пропускает среднее через сигмоид с пороговой отсечкой:

$$X^d(t+1)=\{\begin{array}{ll}1,& s\text{⁣}\left(\frac{X_1+X_2+X_3+X_4}{4}\right)\ge r\\ 0,& \text{иначе}\end{array},s(x)=\frac{1}{1+e^{-10(x-0.5)}}$$

В обоих случаях непрерывные значения нигде не сохраняются — они мгновенно схлопываются в 0 или 1. Это важная деталь: бинаризация маскирует любые особенности масштаба и знака непрерывного шага. Именно она прячет дефект, который мы сейчас разберём.

Пример: смещение коэффициента A. Соберём коэффициент $A$ так, как он записан в публикации. Управляющий параметр $f = 2 - 2\,t/T$ остаётся общим, а групповая кривая затаскивается внутрь случайного множителя: $r_{k1} = c_1g_k \cdot \text{rand}()$​​. Подстановка даёт:

$$A_k = 2 f\, r_{k1} - f = f\left(2\, c_1g_k \cdot \text{rand} - 1\right)$$

Посчитаем математическое ожидание. Поскольку $\text{rand} \in [0,1]$ со средним $0.5$:

$$E[A_k] = f\left(2\, c_1g_k \cdot 0.5 - 1\right) = f\left(c_1g_k - 1\right)$$

В начале прогона $f \approx 2$ и $c_1g_1 \approx 1.95$, поэтому

$$E[A_1] \approx 2 \cdot (1.95 - 1) = 1.9 > 0$$

Коэффициент $A$ в среднем положителен и велик. А обновление имеет вид $X_1 = X_a - A_1 D_1$​, где $D_1 \ge 0$. Положительное $A$ систематически сносит координату ниже вожака — и так по всем осям одновременно, поскольку структура коэффициентов для всех координат одинакова. Результат — направленный дрейф всей популяции в угол $X_{min}$​ пространства и движение вдоль главной диагонали. Ближе к середине прогона $c_1g$ падает, $E[A]$ меняет знак, и популяцию выносит из угла обратно: это не сходимость, а раскачивание под смещённым коэффициентом.

В бинарной задаче этого не видно: каким бы ни был непрерывный $A \cdot D$, сигмоид и порог превращают его в 0 или 1. Но стоит убрать бинаризацию — и алгоритм работает хуже случайного поиска.

Лечится это симметрированием случайной части. Вместо смещённого множителя $(2\,c_1g_k\cdot\text{rand} - 1)$ берём симметричный $c_1g_k\,(2\,\text{rand} - 1)$ с нулевым средним; сохранив общий множитель $f$, получаем

$$A_k = f\,c_1g_k\,(2\,\text{rand} - 1), \qquad E[A_k] = 0$$

Теперь коэффициент симметричен относительно нуля — в среднем особь не смещается ни к вожаку, ни от него, — а амплитуда $f\,c_1g_k$к концу прогона гаснет до нуля, обеспечивая сходимость. (В каноническом ChOA та же симметрия достигается ещё проще: там групповая кривая сама служит амплитудой $f$, а $r_1$ плоское.) Именно эту форму мы используем в реализации; о ней и результатах — в следующем разделе.

Рисунок 1. Два режима обновления позиции в ChOA

Левая панель — фаза охоты. Особь X(t) (серая) перестраивается, ориентируясь на четвёрку вожаков, окружающих добычу: атакующего, преградителя, преследователя и водителя. Для каждого вожака рассчитывается свой кандидат (X1…X4) — притяжение вдоль соответствующего направления с собственными коэффициентами роли. Новое положение X(t+1) (зелёное) есть среднее четырёх кандидатов — центр тяжести притяжений, стягивающий популяцию к лучшим решениям.

Правая панель — хаотическая фаза. С вероятностью 0.5 обычное обновление заменяется скачком: координаты особи замещаются значением хаотического отображения (серые точки показывают, как хаотическая последовательность покрывает пространство поиска). Именно эта фаза опущена в нашей непрерывной реализации.

Ниже — псевдокод BChimp в том виде, в каком он реализован и прогоняется по рейтингу: непрерывное ядро ChOA с исправленным коэффициентом a, без хаотической фазы замещения.

Вход:  N — размер популяции, T — число итераций, [lo, hi] — границы поиска
Выход: лучшее найденное решение

 1.  Инициализировать популяцию X = {X_1, …, X_N} случайно в [lo, hi]
 2.  Задать статический хаотический множитель m[i] для каждого агента
         (Piecewise-карта, одно значение на агента, считается один раз)
 3.  Вычислить приспособленность всех агентов
 4.  Выделить четвёрку вожаков по приспособленности:
         X_attacker, X_barrier, X_chaser, X_driver

 5.  для t = 1 … T:

 6.      f = 2 − 2·(t/T)                              // общий множитель, 2 → 0
 7.      // групповые кривые, k = 1..4
 8.      C1G_1 = C1G_2 = 1.95 − 2·(t/T)^(1/3)
 9.      C1G_3 = C1G_4 = −2·(t/T)^3 + 2.5
10.      C2G_1 = C2G_3 = 2·(t/T)^(1/3) + 0.5
11.      C2G_2 = C2G_4 = 2·(t/T)^3     + 0.5

12.      для каждого агента i:
13.          для каждой координаты j:
14.              sum ← 0
15.              для каждого вожака k ∈ {attacker, barrier, chaser, driver}:
16.                  a_k = f · C1G_k · (2·rand() − 1)           // симметрично, E[a]=0
17.                  c_k = C2G_k · rand()
18.                  d_k = | c_k · X_leader_k[j] − m[i] · X_i[j] |
19.                  sum += X_leader_k[j] − a_k · d_k
20.              X_i[j] ← sum / 4
21.              ограничить X_i[j] границами [lo[j], hi[j]]

22.      Вычислить приспособленность всех агентов
23.      Обновить четвёрку вожаков (элитарно: хранить лучших за всё время)
24.      Обновить глобальное лучшее

25.  вернуть глобальное лучшее

Покоординатная случайность. Коэффициенты a_k и c_k разыгрываются заново на каждую координату j; хаотический множитель m[i] свой у каждого агента. Даже при том, что m[i] один на все координаты агента, покоординатный разброс обеспечивают a_k и c_k — поэтому общего скаляра, запирающего кандидата в подпространство, не возникает, и диагонального выигрыша на симметричном бенчмарке нет.

Симметричный a. Множитель f·C1G_k задаёт амплитуду шага и к концу прогона гаснет до нуля, а сомножитель (2·rand − 1) делает шаг симметричным (нулевое среднее). Это и есть исправление дефекта, разобранного в разделе описания: в опубликованной форме случайная часть смещена, что в континууме сносит популяцию в угол.

Элитарность. Каждый из четырёх вожаков хранит лучшую позицию за всё время, а не лучшую в текущей популяции; сама популяция движется свободно, без отката.

Хаотическая фаза замещения оригинального ChOA (с вероятностью 0.5 позиция заменяется хаотическим значением) опущена: в непрерывной задаче она оказалась разрушительной для сходимости. Для бинарной задачи (отбор признаков) строка 20 заменяется шагом бинаризации — сигмоидальной отсечкой усреднённого значения (BChimp2) либо скрещиванием четырёх бинарных шагов (BChimp1).

Переходим к реализации. Класс C_AO_BChimp наследуется от базового C_AO и придерживается принятого в фреймворке жизненного цикла: метод Moving предлагает новые позиции, внешний цикл оценивает приспособленность, метод Revision обновляет лучших. Всё внутреннее состояние, выходящее за рамки базового агента, вынесено в структуры — это держит данные четвёрки вожаков и персональное состояние особей самодостаточными, без плоских буферов (индекс × координата). 

Четвёрка вожаков хранится как массив lead[4] (0=attacker, 1=barrier, 2=chaser, 3=driver). Каждый вожак самодостаточен, и работа с ним не требует ручного пересчёта смещений в общем буфере. Помимо этого класс держит счётчики итераций epochs, epochsDen, epochNow для отношения t/T и единственный видимый параметр popSize.

//+------------------------------------------------------------------+
class C_AO_BChimp : public C_AO
 {
public:
                    ~C_AO_BChimp() {}
                     C_AO_BChimp()
   {
    ao_name = "BChimp";
    ao_desc = "Chimp Optimization Algorithm";
    ao_link = "https://www.mql5.com/ru/articles/23132";

    popSize = 30;

    ArrayResize(params, 1);
    params [0].name = "popSize";
    params [0].val  = popSize;
   }

  void               SetParams()
   {
    popSize = (int)params [0].val;
   }

  bool               Init(const double &rangeMinP  [],
                          const double &rangeMaxP  [],
                          const double &rangeStepP [],
                          const int     epochsP = 0);

  void               Moving();
  void               Revision();

private:
  //--- четыре вожака: 0=attacker, 1=barrier, 2=chaser, 3=driver
  S_Leader           lead [4];

  //--- персональное состояние агентов
  S_Chimp            chimp [];

  //--- счётчики итераций (для отношения t/T)
  int                epochs;
  int                epochsDen;
  int                epochNow;

  //--- попытка вставить агента в элитарную лесенку вожаков
  void               InsertLeader(const int i);
 };

Вожак стаи описывается структурой S_Leader — координаты и фитнес в одном объекте:

//+------------------------------------------------------------------+
//| вожак стаи: координаты + фитнес                                  |
//+------------------------------------------------------------------+
struct S_Leader
 {
  double c           [];   // координаты
  double             f;      // фитнес

  void               Init(const int coords)
   {
    ArrayResize(c, coords);
    f = -DBL_MAX;
   }
 };

Персональное состояние особи — структура S_Chimp с единственным полем m, хаотическим множителем. Поле одно, но вынос его в структуру отделяет состояние алгоритма от базового S_AO_Agent и оставляет место для расширения.

//+------------------------------------------------------------------+
//| персональное состояние шимпанзе                                  |
//+------------------------------------------------------------------+
struct S_Chimp
 {
  double             m;      // хаотический множитель (Piecewise-карта), статичен
 };

Init начинается со StandardInit, который разворачивает границы поиска и массив агентов. Затем стартовая популяция случайно раскидывается в cP[] — на первом вызове Moving она будет скопирована в рабочие координаты c[], чтобы внешний цикл смог её оценить. Четвёрка вожаков инициализируется фитнесом -DBL_MAX, то есть пустыми слотами, которые заполнятся на первой ревизии.

Отдельный блок предвычисляет хаотический множитель на основе Piecewise-карту (индекс 6, P = 0.4, старт x0 = 0.7). Значение берётся до очередного обновления карты. Каждый агент получает свой статический множитель m[i], одинаковый для всех его координат и неизменный на протяжении прогона — ровно как в исходной реализации. Счётчик epochsDen задаётся как epochs − 1: так отношение t/T достигает единицы именно на последней боевой итерации, и управляющий множитель f = 2 − 2·t/T корректно гаснет до нуля к концу прогона.

//+------------------------------------------------------------------+
//|                              Init                                |
//+------------------------------------------------------------------+
bool C_AO_BChimp::Init(const double &rangeMinP  [],
                       const double &rangeMaxP  [],
                       const double &rangeStepP [],
                       const int     epochsP = 0)
 {
  if(!StandardInit(rangeMinP, rangeMaxP, rangeStepP))
    return false;

//--- начальная случайная популяция в cP[] (попадёт в c[] на первом Moving)
  for(int i = 0; i < popSize; i++)
    for(int c = 0; c < coords; c++)
      a [i].cP [c] = u.RNDfromCI(rangeMin [c], rangeMax [c]);

//--- вожаки
  for(int k = 0; k < 4; k++)
    lead [k].Init(coords);

//--- персональное состояние
  ArrayResize(chimp, popSize);

//--- хаотический множитель m[i] — Piecewise-карта (index=6 в источнике),
//    P=0.4, x0=0.7, Value=1; значение берётся ДО обновления
  double P = 0.4;
  double x = 0.7;
  for(int i = 0; i < popSize; i++)
   {
    chimp [i].m = x;
    if(x >= 0.0 && x < P)
      x = x / P;
    else
      if(x >= P && x < 0.5)
        x = (x - P) / (0.5 - P);
      else
        if(x >= 0.5 && x < 1.0 - P)
          x = (1.0 - P - x) / (0.5 - P);
        else
          x = (1.0 - x) / P;
   }

//--- счётчики итераций
  epochs    = epochsP;
  epochsDen = (epochs > 1) ? epochs - 1 : 1;
  epochNow  = 0;

  return true;
 }

Первый вызов особый: пока revision ещё false, метод лишь переносит стартовые координаты из cP[] в c[] через проекцию SeInDiSp (приведение в границы с учётом шага) и выходит, отдавая управление внешнему циклу для первой оценки.

На рабочих итерациях сначала пересчитываются коэффициенты эпохи: отношение tRatio = epochNow / epochsDen, общий множитель aCoef = 2 − 2·tRatio, и групповые кривые через корневой u1 = (t/T)^{1/3} и кубический u3 = (t/T)^3 законы (массивы C1G, C2G). Дальше для каждого агента и каждой координаты собираются четыре кандидата — по одному на вожака — и усредняются.

Ключевая деталь — форма Ak: групповая кривая C1G[k] служит амплитудой, а случайность входит симметричным множителем (2·rand − 1) с нулевым средним. Это и есть исправление унаследованного смещения: в опубликованной форме случайная часть была сдвинута, что в континууме сносило популяцию в угол. Случайные Ak и Ck разыгрываются заново на каждую координату, поэтому, несмотря на скалярный m[i], общего множителя на весь вектор не возникает и геометрического диагонального выигрыша алгоритм не получает.

//+------------------------------------------------------------------+
//|                            Moving                                |
//|                                                                  |
//|  1. первый прогон: cP -> c (внешний цикл оценит FF);             |
//|  2. далее: a и четыре группы коэффициентов на итерацию;          |
//|  3. для каждого агента/координаты — четыре кандидата от вожаков, |
//|     усреднение, проекция в границы (SeInDiSp).                   |
//+------------------------------------------------------------------+
void C_AO_BChimp::Moving()
 {
//--- первый прогон: cP -> c
  if(!revision)
   {
    for(int i = 0; i < popSize; i++)
      for(int c = 0; c < coords; c++)
        a [i].c [c] = u.SeInDiSp(a [i].cP [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    return;
   }

//--- отношение t/T (зажато в 1.0); a: спад 2 -> 0
  epochNow++;
  double tRatio = (double)epochNow / (double)epochsDen;
  if(tRatio > 1.0)
    tRatio = 1.0;

  double aCoef = 2.0 - 2.0 * tRatio;

//--- групповые динамические коэффициенты
//    u1 = (t/T)^(1/3) — корневой закон,  u3 = (t/T)^3 — кубический
  double u1 = MathPow(tRatio, 1.0 / 3.0);
  double u3 = tRatio * tRatio * tRatio;

  double C1G [4], C2G [4];
  C1G [0] = 1.95 - 2.0 * u1;
  C2G [0] = 2.0 * u1 + 0.5;   // группа 1 (attacker)
  C1G [1] = 1.95 - 2.0 * u1;
  C2G [1] = 2.0 * u3 + 0.5;   // группа 2 (barrier)
  C1G [2] = -2.0 * u3 + 2.5;
  C2G [2] = 2.0 * u1 + 0.5;   // группа 3 (chaser)
  C1G [3] = -2.0 * u3 + 2.5;
  C2G [3] = 2.0 * u3 + 0.5;   // группа 4 (driver)

//--- движение
  for(int i = 0; i < popSize; i++)
   {
    double mi = chimp [i].m;

    for(int c = 0; c < coords; c++)
     {
      double xi  = a [i].c [c];
      double sum = 0.0;

      for(int k = 0; k < 4; k++)
       {
        //--- A симметричен относительно 0: амплитуда aCoef*C1G[k] -> 0
        //    к концу прогона (E[A]=0, нет сноса в угол). C масштабирован
        //    к канону [0..~2.5]. Знак C1G[k] роли не играет — множится
        //    на симметричное (2r-1).
        double Ak = aCoef * C1G [k] * (2.0 * u.RNDprobab() - 1.0);
        double Ck = C2G [k] * u.RNDprobab();
        double Dk = MathAbs(Ck * lead [k].c [c] - mi * xi);
        sum += lead [k].c [c] - Ak * Dk;
       }

      double v = sum / 4.0;
      a [i].c [c] = u.SeInDiSp (v, rangeMin [c], rangeMax [c], rangeStep [c]);
     }
   }
 }

Revision сначала обновляет персональные (fB, cB каждого агента) и глобальное (fB, cB) лучшие решения. Затем по всем агентам вызывается InsertLeader, поддерживающий элитарную четвёрку вожаков: на первом вызове она наполняется лучшими из стартовой популяции, на последующих — обновляется, если найден кто-то сильнее текущих лидеров. Вожаки хранят лучшие позиции за всё время, а не лучших в текущей популяции.

Отката (greedy-приёмки) здесь нет — популяция движется свободно, и это сознательное решение: версия эталонная, без надстроек поверх исходной механики.

//+------------------------------------------------------------------+
//|                           Revision                               |
//|                                                                  |
//|  Обновление личных/глобального лучших + элитарная актуализация   |
//|  четвёрки вожаков (best-ever). Откатов нет — версия эталонная.   |
//+------------------------------------------------------------------+
void C_AO_BChimp::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, coords);
     }
    if(a [i].f > fB)
     {
      fB = a [i].f;
      ArrayCopy(cB, a [i].c, 0, 0, coords);
     }
   }

//--- элитарная актуализация вожаков (инициализация на первом вызове
//    и поддержание top-4 на последующих)
  for(int i = 0; i < popSize; i++)
    InsertLeader(i);

  if(!revision)
    revision = true;
 }

InsertLeader вставляет агента в отсортированную по убыванию фитнеса лесенку из четырёх вожаков. Если фитнес агента превосходит кого-то из лидеров, найденная позиция определяет точку вставки, хвост лесенки сдвигается вниз, и агент занимает своё место. Поскольку между итерациями вожаки не сбрасываются, накопленная таким образом четвёрка всегда отражает четыре лучших решения, встреченных с начала прогона.

//+------------------------------------------------------------------+
//|        InsertLeader — вставка агента в лесенку вожаков           |
//|  Вожаки отсортированы по убыванию фитнеса (lead[0] — лучший).    |
//+------------------------------------------------------------------+
void C_AO_BChimp::InsertLeader(const int i)
 {
  double f = a [i].f;

  int p = -1;
  if(f > lead [0].f)
    p = 0;
  else
    if(f > lead [1].f)
      p = 1;
    else
      if(f > lead [2].f)
        p = 2;
      else
        if(f > lead [3].f)
          p = 3;

  if(p < 0)
    return;

//--- сдвиг вниз от хвоста к позиции вставки
  for(int s = 3; s > p; s--)
   {
    lead [s].f = lead [s - 1].f;
    ArrayCopy(lead [s].c, lead [s - 1].c, 0, 0, coords);
   }

//--- вставка
  lead [p].f = f;
  ArrayCopy(lead [p].c, a [i].c, 0, 0, coords);
 }

Результаты тестов

На полном стандартном стенде BChimp набрал 33.94%, средний результат для большинства исследованных метаэвристик, которые не попали в рейтинговую таблицу.

BChimp|Chimp Optimization Algorithm|30.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.6320626505708679
25 Hilly's; Func runs: 10000; result: 0.4688540395277016
500 Hilly's; Func runs: 10000; result: 0.25059324375826325
=============================
5 Forest's; Func runs: 10000; result: 0.45946276339630393
25 Forest's; Func runs: 10000; result: 0.19717796572435656
500 Forest's; Func runs: 10000; result: 0.054934191314905144
=============================
5 Megacity's; Func runs: 10000; result: 0.6186666666666667
25 Megacity's; Func runs: 10000; result: 0.27653333333333335
500 Megacity's; Func runs: 10000; result: 0.09597333333333409
=============================
All score: 3.05426 (33.94%)

Композитный античит-тест даёт честную оценку:

BChimp|Chimp Optimization Algorithm|30.0|
=============================
Composite anti-cheat test: Hilly + Forest + Megacity + Peaks + Skin
Coordinates: 10; Epochs: 333; Repeats: 10
=============================
Run 1/10: 0.7950338893702603
Run 2/10: 0.7018012473036442
Run 3/10: 0.632016537203568
Run 4/10: 0.6372459064975272
Run 5/10: 0.605584348691656
Run 6/10: 0.7925826976716779
Run 7/10: 0.7760618579627041
Run 8/10: 0.6940213206471844
Run 9/10: 0.6152242781717281
Run 10/10: 0.8067332465317811
=============================
Average result: 0.7056305330 (70.56%)
=============================

Визуализация работы алгоритма BChimp на тестовом стенде, а также на некоторых других функциях.

BChimp на тестовой функции Hilly

BChimp на тестовой функции Forest

BChimp на тестовой функции Megacity

BChimp на тестовой функции Ackley

BChimp на тестовой функции Shaffer

По результатам тестирования алгоритм представлен ознакомительно в рейтинге лучших популяционных методов оптимизации.

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	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
38	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
39	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
40	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
41	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
42	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
43	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
44	CAm	camel algorithm M	0,71534	0,56917	0,35985	1,64436	0,84094	0,47174	0,10850	1,42118	0,70400	0,41947	0,19563	1,31910	4,385	48,72
45	ACOm	ant colony optimization_M	0,71885	0,48410	0,30990	1,51285	0,75792	0,48639	0,11871	1,36302	0,83600	0,48667	0,16148	1,48415	4,360	48,44
	Bchimp	BChimp_optimization_algorithm	0,63206	0,46885	0,25059	1,35150	0,45946	0,19717	0,05493	0,71156	0,61866	0,27653	0,09597	0,99116	3,054	33,94
	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

Выводы

BChimp в непрерывном виде — алгоритм среднего уровня среди большинства метаэвристик. После исправления унаследованного смещения коэффициента он набирает 33.94% на стандартном наборе функций, проседая особенно сильно на Forest и теряя хватку с ростом размерности: то, что на 10 координатах держится прилично, к 1000 рассыпается. Хаотическая фаза замещения, унаследованная от оригинального ChOA и задуманная как механизм выхода из локальных оптимумов, в непрерывной задаче оказалась скорее разрушительной для сходимости, поэтому в нашей реализации она опущена — и без неё одна охотничья фаза с симметричным коэффициентом работает устойчивее.

Главная ценность разбора — не в самих баллах, а в том, что вскрылось по пути. Во-первых, опубликованная форма коэффициента A имеет смещение знака (E[A] = f·(c1g − 1) ≠ 0). Это незаметно в бинарной задаче, потому что сигмоидальная передаточная функция съедает и знак, и масштаб шага, — но в продолжении это смещение сносит всю популяцию в угол пространства поиска. Урок наглядный: дефект, спрятанный за бинаризацией, всплывает при переносе алгоритма в другую область, и дословный перенос кода из публикации даёт неработающий оптимизатор. Во-вторых, сверка кода с публикацией и с оригинальным ChOA обнажила цепочку расхождений — от перепутанных законов коэффициентов до спорной фазы замещения. В-третьих, прогон на функции Ackley обнажил смещение алгоритма к центру координат: почти идеальный результат там — не достижение поиска, а совпадение структурного аттрактора алгоритма с положением оптимума, стоящего в центре симметричного диапазона.

Как универсальный оптимизатор BChimp рекомендовать трудно. В рейтинге при той же вычислительной стоимости есть гораздо более сильные алгоритмы. Его реальная ниша — разве что низкоразмерные задачи, либо роль одной из компонент в гибридной схеме. Для серьёзной многомерной оптимизации это не первый и не второй выбор.

Для трейдера, оптимизирующего параметры эксперта, пороги входа или правила управления капиталом, вывод простой: инструмент нужно выбирать по его реальной силе на сложном многомерном ландшафте. Пространство параметров торговой системы обычно изрезанное и не центрированное относительно нуля — то есть как раз там, где BChimp слаб, а его центральное смещение работает против поиска.

Эффектный результат может оказаться артефактом геометрии теста, а не настоящим преимуществом — ровно как идеальный на функции Ackley возник из совпадения оптимума с центром пространства. Дисциплина, спасающая в обоих случаях, одна и та же — проверять на смещённых, неудобных, на вневыборочных условиях, а не на тех, где результат заведомо льстит.

Что остаётся с читателем независимо от судьбы конкретного BChimp, — привычка не доверять источнику вслепую. Опубликованный алгоритм, как и чужая стратегия, может содержать ошибки в формулах, расхождения и скрытые смещения. Сверка с первоисточником, разбор по уравнениям и честный бенчмарк отделяют работающее от красиво описанного.

Рисунок 2. Цветовая градация алгоритмов по соответствующим тестам

Рисунок 3. Гистограмма результатов тестирования алгоритмов (по шкале от 0 до 100: чем больше, тем лучше, где 100 — максимально возможный теоретический результат), в архиве скрипт для расчёта рейтинговой таблицы

Плюсы и минусы алгоритма BChimp:

Плюсы:

1. Только один внешний параметр — размер популяции.

Минусы:

1. Слабые поисковые качества.

К статье прикреплён архив с актуальными версиями кодов алгоритмов. Автор статьи не несёт ответственности за абсолютную точность в описании канонических алгоритмов, во многие из них внесены изменения для улучшения поисковых возможностей. Выводы и суждения, представленные в статьях, основываются на результатах проведённых экспериментов.

• github: https://github.com/JQSakaJoo/Population-optimization-algorithms-MQL5

Программы, используемые в статье

#	Имя	Тип	Описание
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_BChimp.mq5	Скрипт	Испытательный стенд для BChimp