Алгоритм бактериальной эволюции Нумаоки для быстрой адаптации (NBE)
201
0
Содержание
Введение
В предыдущей статье, разбирая бактериальный эволюционный алгоритм, мы наткнулись на терминологическую развилку и одну её ветвь сознательно отложили. Напомню суть: под названием "бактериальный эволюционный алгоритм" в литературе живут два совершенно разных метода. Первый — оптимизатор Нава и Фурухаси 1999 года с операторами бактериальной мутации и переноса генов, который мы подробно реализовали и протестировали. Второй — историческая модель Тисато Нумаоки 1996 года под названием Bacterial Evolution Algorithm for Rapid Adaptation. Именно ей посвящена эта статья, и сразу предупрежу: это совсем другой зверь, и подходить к нему с привычной меркой оптимизатора статических функций было бы ошибкой.
Модель Нумаоки выросла не из задач оптимизации, а из области искусственной жизни и многоагентных систем. В ней колония адаптивных агентов — бактероидов — живёт в среде и приспосабливается к ней, причём ключевое слово здесь даже не приспосабливается, а быстро. Нумаоку интересовала не финальная точка сходимости, а скорость, с которой колония способна перестроиться, когда условия меняются. Отбор в его модели осуществляет сама среда через гибель агентов, и этот отбор в общем случае происходит безотносительно к собственной функции приспособленности бактероида. Агент может погибнуть не потому, что плохо решает задачу, а просто потому, что исчерпал энергию или оказался не в том месте. Это принципиальный отход от логики классической оптимизации, где выживание жёстко привязано к качеству решения.
Чтобы оценить, насколько это иной взгляд, полезно сопоставить две постановки. Обычный популяционный оптимизатор предполагает неподвижный ландшафт приспособленности: есть фиксированный оптимум, и задача — сойтись к нему, после чего популяция замирает, а всякое дальнейшее шевеление считается напрасной тратой бюджета. Модель Нумаоки предполагает ровно обратное — ландшафт движется, оптимум уползает, и алгоритм, который однажды успокоился и сошёлся, обречён: он останется сидеть там, где оптимума уже нет. Поэтому такая модель построена так, чтобы никогда полностью не успокаиваться, постоянно поддерживая оборот популяции, готовый в любой момент развернуть колонию вслед за сместившейся целью. То, что в статическом оптимизаторе выглядит дефектом — неугомонность, неспособность замереть в точке, — здесь оказывается главным проектным достоинством.
Источник этой неугомонности — снова биология, но другая её сторона, нежели в предыдущей статье. Там нас интересовал горизонтальный перенос генов как способ быстро делиться находками. Здесь к нему добавляется энергетическая экономика бактериальной колонии: бактероид тратит энергию на жизнь и пополняет её за счёт адаптированности, накопленная энергия служит буфером, а гибель неэнергичных и деление энергичных обеспечивают непрерывный, асинхронный оборот популяции. Именно энергетический буфер и есть скрытая память о недавней приспособленности. Бактероид, который только что был хорош, переживёт временную просадку при смене среды за счёт запаса и успеет переадаптироваться, тогда как алгоритм без такой памяти просто выбросил бы его как ставшего вдруг плохим.
Отсюда вытекает и честное предупреждение, которым стоит предварить всё дальнейшее. Главную силу модели Нумаоки — быструю реадаптацию к подвижному оптимуму — статический тестовый стенд попросту не создает нагрузки. Для неподвижной цели нет того перехода, который энергетический буфер призван пережить. Поэтому в этой статье мы аккуратно реинтерпретируем модель как оптимизатор в нашем фреймворке C_AO и честно прогоним её на стандартных функциях Hilly, Forest и Megacity. Это нужно для сопоставимости с остальной серией и ради того, чтобы увидеть, чего модель стоит вне своей стихии. А затем, в следующей, поставим перед ней ту задачу, для которой она создавалась, — стенд с дрейфующим оптимумом, — и посмотрим, проявит ли себя там энергетический механизм, который на статике выглядит избыточным.
Реализация алгоритма
Что моделирует алгоритм Нумаоки. В основе модели лежит колония бактероидов, каждый из которых характеризуется генотипом — в нашем случае это вектор координат в пространстве поиска — и скалярной энергией. Энергия здесь не вспомогательная величина, а валюта отбора. На каждом шаге бактероид получает энергетический приход тем больший, чем лучше он приспособлен, и платит фиксированную метаболическую стоимость за сам факт существования. Хорошо приспособленные накапливают энергию, плохо приспособленные её проедают.
Отбор работает не через сортировку и отсечение худших, как в большинстве эволюционных алгоритмов, а через гибель и деление, и работает асинхронно. Бактероид гибнет, когда его энергия исчерпывается. Кроме того, с некоторой вероятностью он может погибнуть средово — независимо от своей приспособленности, что прямо отражает идею Нумаоки об отборе, осуществляемом средой. Освободившееся место занимает потомок энергичного бактероида. При делении родитель отдаёт потомку часть своей энергии и порождает его мутированную копию рядом с собой, в той же удачной области. Так возникает непрерывный steady-state оборот: неприспособленные и невезучие выбывают, приспособленные размножаются вокруг хороших точек, и популяция всё время обновляется, не застывая.
Рисунок 1. Оборот популяции бактероидов как механизм отбора.
На иллюстрации каждый шаг бактероид получает энергетический приход по адаптированности и несёт метаболическую стоимость (1). При исчерпании энергии или со "средовой" вероятностью pDeath он гибнет, освобождая слот (2). Слот заполняется делением энергичного бактероида, выбранного рулеткой по энергии, — потомок является мутированной копией родителя рядом, а энергия делится пополам (3). В результате колония непрерывно обновляется и принципиально не успокаивается (4) — то самое свойство, что выглядит избыточным на статической задаче и должно работать в плюс на подвижном оптимуме.
Второй несущий механизм — плазмидный, или горизонтальный, перенос. С некоторой вероятностью бактероид получает блок генетического материала напрямую от другого, более энергичного бактероида, минуя размножение. Это тот же принцип, что делает реальные бактерии чемпионами по скорости адаптации. Удачный фрагмент решения распространяется по колонии не за поколения, а за один акт обмена. В модели Нумаоки перенос асинхронен и завязан на энергию донора, что делает его инструментом именно быстрого распространения находок.
Наконец, изменчивость обеспечивается движением — небольшим случайным смещением генотипа, хемотаксис-подобным локальным поиском, который позволяет бактероиду исследовать окрестность своего текущего положения. Вместе эти четыре начала — энергетическая экономика, гибель-деление, горизонтальный перенос и движение — и образуют модель быстрой адаптации.
Интерпретация под стенд C_AO. Здесь необходимо быть предельно честным: оригинал Нумаоки — это агентная модель в динамической среде, и любой её перенос на статический оптимизационный стенд неизбежно содержит проектные решения, которых в исходной работе нет. Поэтому ниже я явно перечислю принятые допущения, чтобы читатель отличал собственно идею Нумаоки от наших инженерных решений.
Прежде всего, статическая тестовая функция заменяет меняющуюся среду оригинала — а значит, быстрая адаптация вырождается в обычную оптимизацию, и главная сила модели остаётся незадействованной. Энергетический приход мы делаем популяционно-относительным: приспособленность бактероида нормируется на текущий разброс приспособленностей в популяции, что избавляет от привязки к абсолютному масштабу конкретной функции и делает метаболическую стоимость осмысленной величиной.
Движение реализовано как покоординатное гауссово смещение с затухающим по ходу прогона шагом и greedy-приёмкой — бактероид принимает новое положение, только если оно не хуже прежнего. Это привносит в модель элемент хемотаксиса, делающий её работоспособным оптимизатором. Плазмидный перенос принимается безусловно, как и в оригинале, — он не тестируется немедленно, а проходит проверку средой опосредованно, через последующий энергобаланс и гибель. Деление выбирает родителя рулеткой по энергии и делит его энергию пополам с потомком. Существенно, что вся случайность в алгоритме покоординатная: ни движение, ни перенос, ни деление не домножают целый вектор на общий скаляр, поэтому осевой симметрией тестового стенда — той самой диагональю, на которой подлавливаются многие алгоритмы, — модель не пользуется.
Рисунок 2. Плазмидный (горизонтальный) перенос.
Донор, согласно иллюстрации процесса, выбирается рулеткой по энергии: чем больше у бактероида запас энергии, тем вероятнее он станет источником (слева). Непрерывный блок координат копируется от донора к реципиенту, замещая те же позиции его хромосомы. В отличие от переноса генов у Нава-Фурухаси, приёмка безусловна — перенос не тестируется немедленно, а проходит проверку средой опосредованно, через последующий энергобаланс и гибель.
Общая схема. Собранный алгоритм укладывается в один цикл по эпохам, причём, в отличие от бактериального оптимизатора из первой статьи, он ложится на каркас C_AO естественно: каждый бактероид оценивается ровно один раз за эпоху, как в обычном популяционном методе, без всякой фазовой машины.
Напишем псевдокод алгоритма.
инициализировать популяцию случайно; задать стартовую энергию E0 оценить; зафиксировать энергию пока не исчерпан бюджет (одна эпоха = один шаг): # --- ход каждого бактероида --- для каждого бактероида i: с вероятностью pPlasmid: получить блок координат от донора (рулетка по энергии) # перенос иначе: сместить координаты гауссом с затухающим шагом # хемотаксис оценить всех бактероидов # --- приёмка хода --- для каждого i: если был перенос: принять безусловно если было движение: принять, только если не хуже (greedy) # --- энергобаланс --- для каждого i: E_i += адаптированность_i - cost # приход популяционно-относительный ограничить E_i сверху потолком # --- гибель и деление (асинхронный отбор) --- для каждого i: если E_i <= 0 или случайно с вероятностью pDeath: пометить мёртвым для каждого освободившегося слота: родитель <- живой бактероид (рулетка по энергии) потомок <- мутированная копия родителя рядом энергию родителя разделить пополам между ним и потомком обновить глобально лучшее решение
Стоит подчеркнуть, что глобально лучшее решение сохраняется отдельно и не теряется в этом непрерывном обороте. Даже когда удачный бактероид гибнет средово или его вытесняет неудачный перенос, найденная им точка остаётся записанной. Это и есть тот компромисс, на который приходится идти, заставляя принципиально неуспокаивающуюся модель работать на статической задаче. Алгоритм продолжает молотить оборот, как и задумано, а механизм элитизма страхует нас от потери лучшего из того, что этот оборот успел нащупать. Насколько такой компромисс оправдан на неподвижном оптимуме и что меняется, когда оптимум приходит в движение, — предмет раздела о тестировании.
Реализуем алгоритм. Бактероид представлен структурой с тремя полями — генотипом, приспособленностью и энергией:
//+------------------------------------------------------------------+ //| | //+------------------------------------------------------------------+ struct S_Bacteroid { double c []; // генотип (валидные координаты) double f; // фитнес double E; // энергия void Init(int coords) { ArrayResize(c, coords); f = -DBL_MAX; E = 0.0; } };
В отличие от бактериального оптимизатора из первой статьи, которому потребовалась громоздкая фазовая машина, модель Нумаоки ложится на каркас C_AO без всяких ухищрений. Причина проста: здесь каждый бактероид оценивается ровно один раз за эпоху — как в обычном популяционном методе вроде роя частиц. Контракт каркаса: Moving заполняет координаты всех агентов. Стенд оценивает их функцией приспособленности. Revision обрабатывает оценки — выполняется буквально: Moving предлагает каждому бактероиду ход, а Revision принимает этот ход и прокручивает всю энергетическую механику. Никакого внутреннего автомата не нужно, и это само по себе показательно: модель устроена как честный шаг живой колонии во времени, а не как развёрнутая в эпохи процедура.
Сама колония — это массив таких структур bro[] размера popSize. Рядом с ним живут три служебных целочисленных массива. Массив actType[] запоминает, что именно сделал каждый бактероид на текущей эпохе — перенос или движение, — поскольку от этого зависит правило приёмки в Revision. Массив allIdx[] содержит индексы от нуля до popSize-1 и служит пулом для выбора донора плазмидного переноса. Массив living[] заполняется в каждом Revision живыми бактероидами и используется как пул для выбора родителя при делении.
//+------------------------------------------------------------------+ //| Class | //+------------------------------------------------------------------+ class C_AO_NBE : public C_AO { public: ~C_AO_NBE() {} C_AO_NBE() { ao_name = "NBE"; ao_desc = "Numaoka Bacterial Evolution"; ao_link = "https://www.mql5.com/ru/articles/23267"; popSize = 30; // число бактероидов stepSize = 0.1; // стартовый масштаб движения (доля диапазона) pPlasmid = 0.1; // вероятность плазмидного переноса на бактероид/эпоху transFrac = 0.2; // длина плазмиды как доля coords (0..1] cost = 0.5; // метаболическая стоимость (приход в [0,1]) pDeath = 0.0005; // «средовая» вероятность гибели на бактероид/эпоху ArrayResize(params, 6); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "stepSize"; params [1].val = stepSize; params [2].name = "pPlasmid"; params [2].val = pPlasmid; params [3].name = "transFrac"; params [3].val = transFrac; params [4].name = "cost"; params [4].val = cost; params [5].name = "pDeath"; params [5].val = pDeath; } void SetParams() { popSize = (int)params [0].val; stepSize = params [1].val; pPlasmid = params [2].val; transFrac = params [3].val; cost = params [4].val; pDeath = params [5].val; //--- предохранители if(popSize < 1) popSize = 1; if(stepSize <= 0.0) stepSize = 0.001; if(pPlasmid < 0.0) pPlasmid = 0.0; if(pPlasmid > 1.0) pPlasmid = 1.0; if(transFrac <= 0.0) transFrac = 0.01; if(transFrac > 1.0) transFrac = 1.0; if(cost < 0.0) cost = 0.0; if(pDeath < 0.0) pDeath = 0.0; if(pDeath > 1.0) pDeath = 1.0; } bool Init(const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0); void Moving(); void Revision(); //--- видимые параметры double stepSize; // стартовый масштаб движения double pPlasmid; // вероятность переноса double transFrac; // доля coords для плазмиды double cost; // метаболическая стоимость double pDeath; // средовая гибель private: //--- данные (массивы структур) S_Bacteroid bro []; // [popSize] — бактероиды int actType []; // [popSize] 0=движение, 1=перенос (на эпоху) int allIdx []; // [popSize] — 0..popSize-1 int living []; // [popSize] — живые в текущем Revision int transLen; // длина плазмиды (из transFrac) //--- прогресс прогона (для отжига шага) int epochsDen; int epochNow; //--- константы double E0; // стартовая энергия double Emax; // потолок энергии double STEP_MIN_RATIO; //--- вспомогательные double Gauss(); double StepNow(); int RouletteByE(int &pool [], int n, int exclude); void Respawn(int i); }; //+------------------------------------------------------------------+
Метод Init после стандартной инициализации каркаса вычисляет абсолютную длину плазмиды из доли transFrac, готовит знаменатель для отжига шага. Далее метод задаёт энергетические константы — стартовую энергию, потолок энергии и нижнюю долю шага при отжиге — и заполняет стартовую популяцию. Создание одного бактероида вынесено в отдельный метод Respawn, который присваивает случайный генотип и стартовую энергию:
//+------------------------------------------------------------------+ //| Init | //+------------------------------------------------------------------+ bool C_AO_NBE::Init(const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0) { if(!StandardInit(rangeMinP, rangeMaxP, rangeStepP)) return false; //--- длина плазмиды transLen = (int)MathRound(transFrac * coords); if(transLen < 1) transLen = 1; if(transLen > coords) transLen = coords; //--- прогресс / константы epochsDen = (epochsP > 1) ? epochsP - 1 : 1; epochNow = 0; E0 = 1.0; Emax = 5.0; STEP_MIN_RATIO = 0.025; //--- буферы ArrayResize(bro, popSize); ArrayResize(actType, popSize); ArrayResize(allIdx, popSize); ArrayResize(living, popSize); for(int i = 0; i < popSize; i++) { bro [i].Init(coords); allIdx [i] = i; } //--- стартовая популяция for(int i = 0; i < popSize; i++) Respawn(i); return true; }
Этот же метод используется как аварийный механизм: если в какой-то момент погибнет вся колония разом, Revision просто возрождает её целиком случайной.
//+------------------------------------------------------------------+ //| Respawn — случайный генотип, стартовая энергия | //+------------------------------------------------------------------+ void C_AO_NBE::Respawn(int i) { for(int c = 0; c < coords; c++) bro [i].c [c] = u.SeInDiSp(u.RNDfromCI(rangeMin [c], rangeMax [c]), rangeMin [c], rangeMax [c], rangeStep [c]); bro [i].f = -DBL_MAX; bro [i].E = E0; }
Gauss возвращает стандартное нормальное число по преобразованию Бокса — Мюллера и используется и в движении, и в делении.
//+------------------------------------------------------------------+ //| Gauss — стандартное нормальное (Box–Muller) | //+------------------------------------------------------------------+ double C_AO_NBE::Gauss() { double u1 = u.RNDfromCI(0.0, 1.0); double u2 = u.RNDfromCI(0.0, 1.0); if(u1 < 1e-15) u1 = 1e-15; return MathSqrt(-2.0 * MathLog(u1)) * MathCos(2.0 * M_PI * u2); }
StepNow реализует линейный отжиг масштаба шага по доле пройденного прогона.
//+------------------------------------------------------------------+ //| StepNow — масштаб движения с линейным отжигом | //+------------------------------------------------------------------+ double C_AO_NBE::StepNow() { double t = (double)epochNow / (double)epochsDen; if(t > 1.0) t = 1.0; return stepSize * (STEP_MIN_RATIO + (1.0 - STEP_MIN_RATIO) * (1.0 - t)); }
RouletteByE выбирает индекс из переданного пула с вероятностью, пропорциональной энергии, с защитой от вырожденного случая нулевых весов и с возможностью исключить заданный индекс — это нужно, чтобы при переносе бактероид не выбрал донором сам себя.
//+------------------------------------------------------------------+ //| RouletteByE — индекс из pool[0..n-1], взвешенный по энергии, | //| с исключением exclude (или -1) | //+------------------------------------------------------------------+ int C_AO_NBE::RouletteByE(int &pool [], int n, int exclude) { double sum = 0.0; for(int k = 0; k < n; k++) { int idx = pool [k]; if(idx == exclude) continue; double e = bro [idx].E; if(e < 1e-12) e = 1e-12; sum += e; } if(sum <= 0.0) { int idx = pool [u.RNDminusOne(n)]; return idx; } double r = u.RNDprobab() * sum; double acc = 0.0; for(int k = 0; k < n; k++) { int idx = pool [k]; if(idx == exclude) continue; double e = bro [idx].E; if(e < 1e-12) e = 1e-12; acc += e; if(acc >= r) return idx; } return pool [n - 1]; }
Метод Moving каждой эпохой даёт каждому бактероиду один из двух взаимоисключающих ходов. С вероятностью pPlasmid бактероид совершает плазмидный перенос: выбирает донора рулеткой по энергии и копирует от него непрерывный блок координат. В противном случае он совершает хемотаксис-движение — покоординатное гауссово смещение с затухающим шагом.
Масштаб шага step берётся из метода StepNow, который линейно снижает его по ходу прогона от стартового значения stepSize до малой доли от него. Это придаёт движению характер: сначала широкий поиск, затем точная доводка. Выбор донора делегирован методу RouletteByE, реализующему обычную рулетку, но с весами по энергии бактероидов, а не по их приспособленности.
//+------------------------------------------------------------------+ //| Moving | //| Каждый бактероид этой эпохой делает ЛИБО плазмидный перенос, | //| ЛИБО хемотаксис-движение. Кандидат пишется в a[i].c. | //+------------------------------------------------------------------+ void C_AO_NBE::Moving() { //--- первый прогон: генотипы -> слоты для первичной оценки if(!revision) { for(int i = 0; i < popSize; i++) for(int c = 0; c < coords; c++) a [i].c [c] = bro [i].c [c]; return; } epochNow++; double step = StepNow(); for(int i = 0; i < popSize; i++) { //--- стартуем кандидата с текущего генотипа for(int c = 0; c < coords; c++) a [i].c [c] = bro [i].c [c]; if(popSize > 1 && u.RNDprobab() < pPlasmid) { //--- ПЛАЗМИДНЫЙ ПЕРЕНОС: блок от донора (рулетка по энергии) actType [i] = 1; int donor = RouletteByE(allIdx, popSize, i); int span = coords - transLen + 1; if(span < 1) span = 1; int start = u.RNDminusOne(span); for(int t = 0; t < transLen; t++) { int c = start + t; if(c < coords) a [i].c [c] = bro [donor].c [c]; } } else { //--- ХЕМОТАКСИС: покоординатное гауссово движение actType [i] = 0; for(int c = 0; c < coords; c++) { double rng = rangeMax [c] - rangeMin [c]; double v = bro [i].c [c] + Gauss() * step * rng; a [i].c [c] = u.SeInDiSp(v, rangeMin [c], rangeMax [c], rangeStep [c]); } } } }
Вся содержательная механика модели сосредоточена в Revision, и проходит он в четыре этапа. Первый — приёмка хода. Перенос принимается безусловно, как и задумано: горизонтальный обмен не тестируется немедленно, его проверит среда. Движение же принимается по greedy-правилу — только если новое положение не хуже прежнего, иначе бактероид откатывается.
Второй этап — энергобаланс. Приспособленность каждого бактероида нормируется на текущий разброс приспособленностей в популяции, давая приход в диапазоне от нуля до единицы, из которого вычитается метаболическая стоимость.
Важно учесть одну тонкость поведения модели. Приход популяционно-относительный, а значит давление отбора адаптивно: когда колония улучшается и уплотняется, относительные приходы у большинства растут, и метаболическая стоимость перестаёт массово выкашивать популяцию — отбор сам собой смягчается, переходя от прополки к накоплению вокруг хороших точек. Это свойство оказалось ценным: попытка заменить относительный приход жёстким ранговым (когда ровно нижняя половина истощается всегда, независимо от того, насколько популяция уже хороша) заметно ухудшила результат, поскольку навязывала вечную прополку там, где давление уже должно было ослабнуть.
Третий этап — гибель. Бактероид помечается мёртвым, если его энергия исчерпана или если сработала средовая вероятность гибели pDeath, не зависящая от приспособленности. Выжившие собираются в массив living[].
Четвёртый этап — деление, заполняющее освободившиеся слоты. Для каждого мёртвого слота рулеткой по энергии среди живых выбирается родитель, и слот занимает мутированная копия этого родителя, размещённая рядом с ним. Энергия родителя делится пополам между ним и потомком.
//+------------------------------------------------------------------+ //| Revision | //| Приёмка хода -> энергобаланс -> гибель -> деление. | //+------------------------------------------------------------------+ void C_AO_NBE::Revision() { //--- глобальный лучший for(int i = 0; i < popSize; i++) { if(a [i].f > fB) { fB = a [i].f; ArrayCopy(cB, a [i].c, 0, 0, coords); } } //--- первичная фиксация if(!revision) { for(int i = 0; i < popSize; i++) { bro [i].f = a [i].f; bro [i].E = E0; } revision = true; return; } //--- приёмка хода: перенос безусловно, движение — greedy for(int i = 0; i < popSize; i++) { if(actType [i] == 1) { for(int c = 0; c < coords; c++) bro [i].c [c] = a [i].c [c]; bro [i].f = a [i].f; } else { if(a [i].f >= bro [i].f) { for(int c = 0; c < coords; c++) bro [i].c [c] = a [i].c [c]; bro [i].f = a [i].f; } //--- иначе откат: bro[i] остаётся прежним } } //--- энергобаланс: приход ~ популяционно-относительной адаптированности double fmin = DBL_MAX; double fmax = -DBL_MAX; for(int i = 0; i < popSize; i++) { if(bro [i].f < fmin) fmin = bro [i].f; if(bro [i].f > fmax) fmax = bro [i].f; } double span = fmax - fmin; if(span < 1e-12) span = 1e-12; for(int i = 0; i < popSize; i++) { double gain = (bro [i].f - fmin) / span; // [0,1] bro [i].E += gain - cost; if(bro [i].E > Emax) bro [i].E = Emax; } //--- гибель: энергетическая (E<=0) или средовая (pDeath) int nLiving = 0; bool dead []; ArrayResize(dead, popSize); for(int i = 0; i < popSize; i++) { bool die = (bro [i].E <= 0.0) || (u.RNDprobab() < pDeath); dead [i] = die; if(!die) { living [nLiving] = i; nLiving++; } } //--- заполнение освободившихся слотов делением (или массовый респаун) if(nLiving == 0) { for(int i = 0; i < popSize; i++) Respawn(i); return; } double step = StepNow(); for(int i = 0; i < popSize; i++) { if(!dead [i]) continue; //--- родитель — энергичный живой (рулетка по энергии) int p = RouletteByE(living, nLiving, -1); //--- деление: потомок = мутированная копия родителя рядом for(int c = 0; c < coords; c++) { double rng = rangeMax [c] - rangeMin [c]; double v = bro [p].c [c] + Gauss() * step * rng; bro [i].c [c] = u.SeInDiSp(v, rangeMin [c], rangeMax [c], rangeStep [c]); } //--- энергия делится пополам double half = bro [p].E * 0.5; bro [i].E = half; bro [p].E = bro [p].E - half; //--- фитнес потомка оценится на следующей эпохе; оценка-заглушка bro [i].f = bro [p].f; } }
Деление энергии пополам — содержательная деталь: оно ограничивает чрезмерное размножение одного удачливого родителя, ведь каждое деление вдвое урезает его собственный запас, делая следующее деление менее вероятным. Приспособленность потомка пока ей неоткуда взяться — она будет вычислена на следующей эпохе, — поэтому ей временно присваивается приспособленность родителя как разумная оценка. В энергобаланс она войдёт уже своим настоящим значением, так что заглушка ни на что не влияет.
Отдельно отмечу, что глобально лучшее решение обновляется в самом начале Revision, до всей этой механики, и хранится в cB / fB каркаса. Благодаря этому непрерывный оборот популяции — гибель удачных бактероидов, перезапись неудачным переносом — не способен потерять найденный оптимум: элитизм каркаса страхует результат, пока колония продолжает молотить свой steady-state.
Результаты тестов
По результатам тестирования NBE набирает 44,52% и значительно уступает алгоритмам из рейтинга.NBE|Numaoka Bacterial Evolution|30.0|0.1|0.1|0.2|0.5|0.0005|
=============================
5 Hilly's; Func runs: 10000; result: 0.8192159815167424
25 Hilly's; Func runs: 10000; result: 0.49855422323618664
500 Hilly's; Func runs: 10000; result: 0.27964847429941897
=============================
5 Forest's; Func runs: 10000; result: 0.8390788490589818
25 Forest's; Func runs: 10000; result: 0.331571269993976
500 Forest's; Func runs: 10000; result: 0.06909155068965439
=============================
5 Megacity's; Func runs: 10000; result: 0.7293333333333335
25 Megacity's; Func runs: 10000; result: 0.3192
500 Megacity's; Func runs: 10000; result: 0.12144000000000103
=============================
All score: 4.00713 (44.52%)
Античит-тест на честность работы алгоритма.
NBE|Numaoka Bacterial Evolution (rapid adaptation)|30.0|0.1|0.1|0.2|0.5|0.0005|
=============================
Composite anti-cheat test: Hilly + Forest + Megacity + Peaks + Skin
Coordinates: 10; Epochs: 333; Repeats: 10
=============================
Run 1/10: 0.7924952224378096
Run 2/10: 0.7890303169792431
Run 3/10: 0.805857730930511
Run 4/10: 0.9025599823187104
Run 5/10: 0.7760608747746541
Run 6/10: 0.6997834424845257
Run 7/10: 0.9422331414891965
Run 8/10: 0.8147796080573018
Run 9/10: 0.8163391404105331
Run 10/10: 0.763698395783302
=============================
Average result: 0.8102837856 (81.03%)
=============================
NBE на тестовой функции Hilly
NBE на тестовой функции Forest
NBE на тестовой функции Megacity
NBE на тестовой функции Ackley
NBE на тестовой функции Peaks
По итогам тестирования алгоритм NBE представлен в нашей рейтинговой таблице лучших популяционных методов ознакомительно.
| 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 |
| NBE | numaoka_bacterial_evolution | 0,81921 | 0,49855 | 0,27964 | 1,59740 | 0,83907 | 0,33157 | 0,06909 | 1,23973 | 0,72933 | 0,31920 | 0,12144 | 1,16997 | 4,007 | 44,52 | |
| 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 | |
Выводы
Историческая модель бактериальной эволюции Нумаоки оказалась алгоритмом принципиально иной природы, чем оптимизатор Нава — Фурухаси из первой статьи, и эта статья, по сути, была попыткой честно перенести агентную модель быстрой адаптации на оптимизационный стенд и посмотреть, что от неё останется.
На статических функциях ответ однозначен и закономерен: NBE набирает 44,52% и уступает сходящимся алгоритмам. Причина не в слабости поиска, а в самом устройстве модели — она построена так, чтобы никогда не успокаиваться, постоянно поддерживая оборот популяции через гибель и деление. На неподвижном оптимуме это свойство — чистый расход: пока хороший оптимизатор замирает в найденной точке и шлифует её, NBE продолжает молотить свой steady-state, расшвыривая удачные решения. Энергетический аппарат, буфер истории приспособленности, на статике работает вхолостую, потому что нет того перехода, который этот буфер призван пережить. Отдельно это подтвердил эффект средовой гибели: чем её меньше, тем выше статический счёт, ведь всякая не-фитнесная гибель на неподвижной цели — лишь шум.
Но именно в этом недостатке и заключалась гипотеза. Модель Нумаоки создавалась не для неподвижных функций, а для сред, которые меняются, и её настоящий экзамен — слежение за движущимся оптимумом. Для читателей предоставлен полный набор инструментов, чтобы можно было провести собственные эксперименты. В следующей статье мы соберем стенд с дрейфом, который поставит экзамен напрямую, сравнивая неугомонный NBE со сходящимся BEA по онлайн-метрике слежения и не только.
Рисунок 3. Цветовая градация алгоритмов по соответствующим тестам
Рисунок 4. Гистограмма результатов тестирования алгоритмов (по шкале от 0 до 100: чем больше, тем лучше, где 100 — максимально возможный теоретический результат), в архиве скрипт для расчёта рейтинговой таблицы
Плюсы и минусы алгоритма NBE:
Плюсы:
- Только один внешний параметр — размер популяции.
- Относительно низкий разброс результатов (относительно алгоритмов с высоким рейтингом, но высоким разбросом в результатах).
Минусы:
- Средние поисковые качества для статичного стенда.
К статье прикреплён архив с актуальными версиями кодов алгоритмов. Автор статьи не несёт ответственности за абсолютную точность в описании канонических алгоритмов, во многие из них внесены изменения для улучшения поисковых возможностей. Выводы и суждения, представленные в статьях, основываются на результатах проведённых экспериментов.
Программы, используемые в статье
| # | Имя | Тип | Описание |
|---|---|---|---|
| 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_NBE.mq5 | Скрипт | Испытательный стенд для NBE |
Предупреждение: все права на данные материалы принадлежат MetaQuotes Ltd. Полная или частичная перепечатка запрещена.
Данная статья написана пользователем сайта и отражает его личную точку зрения. Компания MetaQuotes Ltd не несет ответственности за достоверность представленной информации, а также за возможные последствия использования описанных решений, стратегий или рекомендаций.
Разработка самовосстанавливающегося советника в MQL5 (Часть 1): Архитектура постоянного хранения состояния сделки
Автоматизация торговых стратегий в MQL5 (Часть 32): Создание системы распознавания гармонического паттерна "5 Drives" с использованием Price Action
Валютный граф и справедливая цена 28 пар через DFS по кросс-путям
Встраивание торговой дисциплины в код (Часть 6): Построение единого фреймворка дисциплины на MQL5
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Вы принимаете политику сайта и условия использования