Алгоритм бактериальной эволюции — Bacterial Evolutionary Algorithm (BEA)
52
0
Содержание
Введение
Любая популяция живых организмов, поставленная в условия ограниченных ресурсов, веками решает одну и ту же задачу — найти в пространстве возможных форм те, что обеспечивают выживание, и закрепить их. Именно поэтому биология остаётся щедрым источником метафор для популяционных алгоритмов: естественный отбор дал начало генетическим алгоритмам, поведение роя — методам роевого интеллекта, охота хищников и миграции стай — десяткам частных схем, которые мы разбирали в этой серии. Сегодня очередь дошла до организмов, которые эволюционируют быстрее всех на планете и по правилам, заметно отличающимся от привычной нам схемы родитель — потомок. Поговорим о бактериях.
Бактериальная эволюция интересна тем, что в ней работает механизм, почти отсутствующий у высших организмов. Это горизонтальный перенос генов. Бактерии передают друг другу полезные фрагменты ДНК напрямую, минуя размножение: через конъюгацию, плазмиды, и захват свободных генов из среды. Соседняя клетка может за один акт обмена получить готовый, проверенный отбором участок генома — например, ген устойчивости к антибиотику — и немедленно им воспользоваться. Это и есть секрет феноменальной скорости бактериальной адаптации: полезная находка распространяется по популяции не за поколения, а почти мгновенно. Для оптимизации такая идея заманчива: если удачный фрагмент решения можно копировать между особями напрямую, поиск способен ускоряться там, где классический генетический алгоритм вынужден ждать череды скрещиваний.
Здесь, однако, нас поджидает терминологическая развилка, которую важно прояснить с самого начала, потому что под названием Bacterial Evolutionary Algorithm в литературе живут два совершенно разных алгоритма, и их регулярно путают. Первый восходит к работе Тисато Нумаоки 1996 года Bacterial Evolution Algorithm for Rapid Adaptation: это, строго говоря, не оптимизатор непрерывных функций, а агентная модель из области искусственной жизни. В ней колония адаптивных агентов-бактероидов приспосабливается к постоянно меняющейся среде, причём отбор осуществляет сама среда через гибель агентов, в общем случае безотносительно к их собственной функции приспособленности. Модель красива и посвящена быстрой ре-адаптации к подвижному оптимуму, но её перенос на статический стенд требует столь вольной интерпретации, что получается, по сути, другой алгоритм. Этой ветви — настоящей модели Нумаоки — будет посвящена отдельная статья, потому что её природа принципиально иная.
Второй алгоритм — тот, что в контексте оптимизации все называют BEA, — предложен Норберто Нава и Такеси Фурухаси в 1999 году. Из этой ветви позже выросли бактериальный меметический алгоритм и его дискретные варианты для задачи коммивояжёра. Именно этот оптимизационный вариант BEA Нава — Фурухаси мы и реализуем в нашем фреймворке C_AO. Проверим на тестовых функциях Hilly, Forest и Megacity, прогоним через композитный античит-тест и разберём, как алгоритм ведёт себя при росте размерности задачи. Историческую модель Нумаоки оставим на потом, обозначив её здесь лишь как развилку, к которой мы ещё вернёмся.
Реализация алгоритма
В основе BEA лежит наблюдение, что у бактерий за изменчивость и за обмен полезными находками отвечают два независимых механизма, и оба можно перевести на язык оптимизации. Точечные мутации генома порождают локальные вариации — это инструмент тонкой настройки уже имеющегося решения. Горизонтальный перенос распространяет удачные фрагменты по всей колонии — это инструмент обмена опытом между решениями. Нава и Фурухаси оформили эти два начала в виде двух операторов, и понимание алгоритма сводится к пониманию того, что делает каждый из них.
В терминах оптимизации каждая бактерия — это особь популяции, а её хромосома — вектор координат в пространстве поиска. Хромосома мысленно разбивается на сегменты: непрерывные блоки координат, которые будут обрабатываться как единое целое. Разбиение на сегменты принципиально, потому что именно оно превращает мутацию из слепого случайного возмущения в направленный покоординатный (точнее, поблочный) поиск.
Рисунок 1. Хромосома бактерии — это вектор координат в пространстве поиска, мысленно разбитый на сегменты (непрерывные блоки координат)
Бактерия как особь популяции из popSize и посегментная организация хромосомы — отображено на рисунке выше.
Бактериальная мутация. Первый оператор отвечает за локальную оптимизацию в пределах одной хромосомы и применяется к каждой бактерии популяции по очереди. Берётся одна бактерия, и с неё снимается несколько копий — клонов. Затем хромосома проходится по сегментам, и для каждого сегмента выполняется один и тот же цикл. Во всех клонах, кроме одного, координаты текущего сегмента случайно перегенерируются, тогда как один клон сохраняется неизменным — он удерживает текущий, уже достигнутый вариант сегмента. После этого все клоны оцениваются функцией приспособленности, и среди них выбирается лучший. Его версия данного сегмента переносится во все остальные клоны, фиксируя на этом участке хромосомы найденное улучшение. Затем процедура переходит к следующему сегменту, и так до конца хромосомы. Когда все сегменты пройдены, исходная бактерия заменяется получившимся лучшим клоном.
Ключевая деталь здесь — сохранение одного неизменного клона на каждом шаге. Благодаря ему текущий инкумбент всегда присутствует в наборе сравниваемых вариантов, поэтому лучший клон никогда не оказывается хуже исходной бактерии. Это придаёт бактериальной мутации важное свойство: приспособленность бактерии в ходе мутации монотонно не ухудшается. Оператор работает как встроенный локальный поиск — он способен только улучшать особь или оставлять её на месте, но не портить. Именно поэтому в BEA нет привычной для генетических алгоритмов проблемы потери хорошего решения при мутации: мутация здесь не вероятностное возмущение, а детерминированно-улучшающая посегментная оптимизация.
Рисунок 2. Бактериальная мутация как локальная оптимизация по сегментам.
Смотрим на рисунок 2. С бактерии снимаются Nc клонов (1); в выбранном сегменте координаты случайно перегенерируются во всех клонах, кроме одного, который сохраняется неизменным и удерживает текущий инкумбент; все клоны оцениваются (2); вариант сегмента лучшего клона распространяется на все клоны (3). Поскольку инкумбент всегда присутствует в наборе сравниваемых, итоговая бактерия никогда не оказывается хуже исходной — приспособленность в ходе мутации монотонно не убывает. Процедура повторяется для каждого сегмента.
Перенос генов. Второй оператор отвечает за обмен информацией между особями и моделирует тот самый горизонтальный перенос, что делает бактериальную эволюцию столь быстрой. Сначала вся популяция сортируется по приспособленности и делится на две половины — сильную, куда попадают лучшие бактерии, и слабую. Затем многократно повторяется акт переноса: из сильной половины случайно выбирается бактерия-источник, из слабой — бактерия-приёмник, и непрерывный блок координат источника копируется в приёмник, замещая соответствующий участок его хромосомы. Число таких актов за поколение задаётся отдельным параметром.
Содержательно перенос генов работает иначе, чем скрещивание в классическом генетическом алгоритме. Скрещивание — это вертикальная передача: признаки наследуются потомком от родителей, и хорошая комбинация распространяется лишь через размножение, поколение за поколением. Перенос генов горизонтален: удачный фрагмент копируется напрямую от приспособленной особи к неприспособленной, здесь и сейчас, без порождения потомства. Это позволяет полезным блокам решения быстро расходиться по популяции и подтягивать отстающих к структуре лидеров. Если бактериальная мутация — это интенсификация, углубление каждой особи в локальный оптимум, то перенос генов — это диверсификация через обмен, способ не дать слабым бактериям застрять в бесперспективных областях, передав им проверенные куски от сильных.
Рисунок 3. Перенос генов как горизонтальный обмен.
Популяция сортируется по приспособленности и делится на сильную половину (источники) и слабую (приёмники). Блок координат случайного источника копируется в случайный приёмник, замещая те же позиции его хромосомы. В отличие от вертикального наследования при скрещивании, удачный фрагмент распространяется напрямую и немедленно, подтягивая отстающих к структуре лидеров.
Общая схема. Собранный из двух операторов алгоритм укладывается в простой цикл. Популяция инициализируется случайно и оценивается. Далее, пока не исчерпан бюджет вычислений, на каждом поколении сначала ко всем бактериям по очереди применяется бактериальная мутация, полностью выполняющая локальную оптимизацию каждой особи по сегментам. Затем выполняется заданное число актов переноса генов, перемешивающих найденные блоки между сильными и слабыми бактериями. Глобально лучшее решение запоминается отдельно и не теряется при последующих преобразованиях.
инициализировать популяцию случайно оценить популяцию пока не исчерпан бюджет: # --- бактериальная мутация (локальная оптимизация каждой особи) --- для каждой бактерии b: создать Nc клонов бактерии b для каждого сегмента хромосомы: во всех клонах, кроме одного, перегенерировать сегмент случайно оценить все клоны лучший вариант сегмента распространить на все клоны b <- лучший клон # инкумбент в наборе => b не ухудшается # --- перенос генов (горизонтальный обмен блоками) --- отсортировать популяцию; разделить на сильную и слабую половины повторить Ninf раз: источник <- случайная бактерия из сильной половины приёмник <- случайная бактерия из слабой половины скопировать блок координат из источника в приёмник обновить глобально лучшее решение
Стоит заранее отметить особенность, которая станет ключевой при реализации. BEA — алгоритм с неоднородным и довольно дорогим поколением: бактериальная мутация требует вложенных оценок функции приспособленности, ведь каждый сегмент каждого клона нужно оценить, прежде чем перейти к следующему сегменту. Это плохо укладывается в привычную для нашего стенда схему "один пакет оценок на поколение". Это потребует аккуратной фазовой организации вычислений, а также честного учёта числа обращений к функции приспособленности — иначе сравнение BEA с другими алгоритмами на фиксированном бюджете окажется некорректным. Как именно мы решим эту задачу в рамках C_AO, разберём в следующем разделе, посвящённом реализации.
Все алгоритмы серии живут в едином каркасе C_AO, и контракт его предельно прост. На каждой эпохе внешний цикл стенда вызывает метод Moving, который заполняет координаты всех агентов популяции — массив a[i].c; затем стенд сам оценивает каждого агента функцией приспособленности, записывая результат в a[i].f. Затем вызывается Revision, который читает эти оценки и обновляет внутреннее состояние алгоритма. Ключевое следствие этого контракта в том, что за одну эпоху функция приспособленности вызывается ровно popSize раз — по одному разу на агента, и ни больше, ни меньше.
Здесь и кроется трудность, обещанная в конце предыдущего раздела. Бактериальная мутация по своей природе требует вложенных оценок: внутри обработки одной бактерии нужно оценить её клоны на текущем сегменте, узнать победителя и лишь затем перейти к следующему сегменту. Это не укладывается в схему один пакет из popSize оценок на поколение и на одно поколение BEA приходится множество таких пакетов. Поэтому класс реализован как конечный автомат: каждая эпоха стенда соответствует одному срезу оценки, а переменные состояния помнят, на каком сегменте, клоне или акте переноса мы сейчас находимся. За одну эпоху оцениваются либо одноимённые клоны всех бактерий сразу, либо все бактерии после инфицирования — и популяционный слот a[i].c каждую эпоху занят осмысленным кандидатом.
Особь представлена структурой с вектором координат и приспособленностью, а вся внутренняя кухня алгоритма — это массивы таких структур, без плоских буферов с ручной индексацией:
//+----------------------------------------------------------------------------+ //| Structure | //+----------------------------------------------------------------------------+ struct S_BEA_Ind { double c []; // координаты (валидные, уже прогнаны через SeInDiSp) double f; // фитнес void Init(int coords) { ArrayResize(c, coords); f = -DBL_MAX; } };
На уровне класса хранятся три массива. Первый, bact[] размера popSize, — это закреплённые бактерии, текущая популяция. Второй, clone[] размера popSize * Nc, — рабочие клоны: для каждой бактерии в нём отведено Nc подряд идущих ячеек, и клон номер j бактерии b лежит по индексу b * Nc + j. Третий, ord[] размера popSize, — вспомогательный массив индексов для сортировки при переносе генов. Переменные phase, segIdx, cloneIdx и transIdx образуют состояние автомата: фаза (мутация или перенос), текущий сегмент, текущий клон-срез и текущая эпоха переноса.
//+------------------------------------------------------------------+ //| Class | //+------------------------------------------------------------------+ class C_AO_BEA : public C_AO { public: ~C_AO_BEA() {} C_AO_BEA() { ao_name = "BEA"; ao_desc = "Bacterial Evolutionary Algorithm"; ao_link = "https://www.mql5.com/ru/users/joo"; popSize = 10; // число бактерий Nc = 2; // свежих мутантов сегмента на бактерию (>=1) Nseg = 10; // число сегментов хромосомы nTrans = 2; // эпох переноса генов на поколение transFrac = 0.2; // длина переносимого блока как доля coords (0..1] ArrayResize(params, 5); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "Nc"; params [1].val = Nc; params [2].name = "Nseg"; params [2].val = Nseg; params [3].name = "nTrans"; params [3].val = nTrans; params [4].name = "transFrac"; params [4].val = transFrac; } void SetParams() { popSize = (int)params [0].val; Nc = (int)params [1].val; Nseg = (int)params [2].val; nTrans = (int)params [3].val; transFrac = params [4].val; //--- предохранители if(popSize < 1) popSize = 1; if(Nc < 1) Nc = 1; // число свежих мутантов на сегмент if(Nseg < 1) Nseg = 1; if(nTrans < 0) nTrans = 0; if(transFrac <= 0.0) transFrac = 0.01; if(transFrac > 1.0) transFrac = 1.0; } bool Init(const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0); void Moving(); void Revision(); //--- видимые параметры int Nc; // клонов int Nseg; // сегментов int nTrans; // эпох переноса генов double transFrac; // доля coords для блока переноса private: //--- фазы конечного автомата enum E_Phase { PH_MUT = 0, PH_TRANS = 1 }; E_Phase phase; int segIdx; // текущий сегмент в мутации int cloneIdx; // текущий клон (срез оценки) в мутации int transIdx; // текущая эпоха переноса //--- данные (массивы структур) S_BEA_Ind bact []; // [popSize] — закреплённые бактерии S_BEA_Ind clone []; // [popSize * Nc] — рабочие клоны int ord []; // [popSize] — индексы для сортировки int transLen; // длина блока переноса (из transFrac) //--- вспомогательные void SegBounds(int s, int &lo, int &hi); void BuildClonesForSeg(int s); void DoGeneTransfer(); };
Метод Init после стандартной инициализации каркаса делает три вещи. Он ограничивает число сегментов сверху размерностью задачи (Nseg не может быть больше coords), вычисляет абсолютную длину переносимого блока из доли transFrac. Это важная деталь, поскольку параметры класса фиксированы на всю тройку тестов, а размерность от теста к тесту меняется, и привязка длины блока к доле координат делает её масштабируемой. Затем создаются массивы структур и стартовая популяция заполняется равномерно случайными координатами, после чего состояние автомата сбрасывается в начало фазы мутации.
//+------------------------------------------------------------------+ //| Init | //+------------------------------------------------------------------+ bool C_AO_BEA::Init(const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0) { if(!StandardInit(rangeMinP, rangeMaxP, rangeStepP)) return false; //--- сегментов не больше, чем координат if(Nseg > coords) Nseg = coords; //--- длина блока переноса transLen = (int)MathRound(transFrac * coords); if(transLen < 1) transLen = 1; if(transLen > coords) transLen = coords; //--- буферы (массивы структур) ArrayResize(bact, popSize); ArrayResize(clone, popSize * Nc); ArrayResize(ord, popSize); for(int i = 0; i < popSize; i++) bact [i].Init(coords); for(int i = 0; i < popSize * Nc; i++) clone [i].Init(coords); //--- стартовая случайная популяция бактерий for(int i = 0; i < popSize; i++) { for(int c = 0; c < coords; c++) bact [i].c [c] = u.SeInDiSp(u.RNDfromCI(rangeMin [c], rangeMax [c]), rangeMin [c], rangeMax [c], rangeStep [c]); bact [i].f = -DBL_MAX; } //--- стартовое состояние автомата phase = PH_MUT; segIdx = 0; cloneIdx = 0; transIdx = 0; return true; }
Сегментация хромосомы. Границы сегмента вычисляются так, чтобы остаток координат равномерно распределялся между сегментами:
//+------------------------------------------------------------------+ //| SegBounds — границы сегмента s в [lo, hi) с равномерным | //| распределением остатка координат по сегментам | //+------------------------------------------------------------------+ void C_AO_BEA::SegBounds(int s, int &lo, int &hi) { lo = (int)((long)s * coords / Nseg); hi = (int)((long)(s + 1) * coords / Nseg); if(lo < 0) lo = 0; if(hi > coords) hi = coords; }
Стоит обратить внимание на принятое здесь решение: число сегментов Nseg задано как параметр, а длина сегмента из него выводится. Альтернатива — фиксировать длину сегмента — приводила бы к тому, что на большой размерности число сегментов взрывается, а с ним и стоимость поколения. При фиксированном же числе сегментов стоимость мутации в обращениях к функции приспособленности не зависит от размерности, и это, как мы увидим ниже, принципиально для честного сравнения.
Фаза мутации: первое отступление от канона. Именно здесь реализация осознанно расходится с канонической формулировкой Нава — Фурухаси, и это расхождение стоит объяснить подробно. В каноне на каждом сегменте один клон сохраняется неизменным — он несёт текущий вариант сегмента и гарантирует, что лучший клон не окажется хуже исходной бактерии. Этот неизменный клон выполняет роль страховки инкумбента: он всегда присутствует среди сравниваемых вариантов.
В нашем каркасе такая страховка обходится дорого. Поскольку стенд в любом случае тратит один вызов функции приспособленности на каждый слот популяции, неизменный клон — это слот, израсходованный на переоценку уже известного значения: приспособленность нетронутой копии бактерии равна приспособленности самой бактерии, и пересчитывать её бессмысленно. Поэтому реализация регенерирует сегмент во всех клонах, а инкумбента сохраняет иначе — запоминая его приспособленность в bact.f и сравнивая с ней лучшего клона на этапе закрепления. Построение клонов поэтому не выделяет эталонную копию:
//+------------------------------------------------------------------+ //| BuildClonesForSeg — снять с каждой бактерии Nc клонов и во | //| ВСЕХ клонах случайно регенерировать координаты сегмента s. | //| Инкумбент не хранится отдельным клоном: его фитнес помнится в | //| bact.f и сравнивается при закреплении (см. Revision). | //+------------------------------------------------------------------+ void C_AO_BEA::BuildClonesForSeg(int s) { int lo, hi; SegBounds(s, lo, hi); for(int b = 0; b < popSize; b++) { for(int j = 0; j < Nc; j++) { int idx = b * Nc + j; //--- копия бактерии вне сегмента for(int c = 0; c < coords; c++) clone [idx].c [c] = bact [b].c [c]; //--- регенерация сегмента во ВСЕХ клонах. Инкумбент хранится // отдельно (bact.f) и сравнивается на этапе закрепления — // переоценивать его клоном не нужно, экономим вызовы FF. for(int c = lo; c < hi; c++) clone [idx].c [c] = u.SeInDiSp(u.RNDfromCI(rangeMin [c], rangeMax [c]), rangeMin [c], rangeMax [c], rangeStep [c]); clone [idx].f = -DBL_MAX; } } }
Фаза переноса: второе отступление от канона. Второе расхождение мельче и касается параметризации. В каноне перенос — это Ninf повторений, в каждом из которых случайный источник из сильной половины инфицирует случайного приёмника из слабой. В реализации удобнее было привязать перенос к эпохам автомата: за каждую из nTrans эпох переноса инфицируется вся слабая половина целиком — каждая её бактерия получает по блоку от случайно выбранного источника из сильной половины. Сортировка делается через массив индексов, без физического перемещения структур:
//+------------------------------------------------------------------+ //| DoGeneTransfer — сортировка популяции и инфицирование слабой | //| половины блоками из сильной. Модифицирует bact[] на месте. | //+------------------------------------------------------------------+ void C_AO_BEA::DoGeneTransfer() { if(popSize < 2) return; //--- сортировка индексов по фитнесу бактерий (по убыванию) for(int i = 0; i < popSize; i++) ord [i] = i; for(int i = 0; i < popSize - 1; i++) { int bi = i; for(int j = i + 1; j < popSize; j++) if(bact [ord [j]].f > bact [ord [bi]].f) bi = j; int t = ord [i]; ord [i] = ord [bi]; ord [bi] = t; } int half = popSize / 2; if(half < 1) half = 1; int span = coords - transLen + 1; if(span < 1) span = 1; //--- каждый приёмник «слабой» половины принимает блок от случайного // источника «сильной» половины for(int k = half; k < popSize; k++) { int dst = ord [k]; int src = ord [u.RNDminusOne(half)]; int start = u.RNDminusOne(span); for(int t = 0; t < transLen; t++) { int c = start + t; if(c < coords) bact [dst].c [c] = bact [src].c [c]; } } }
Приёмка перенесённых генотипов не жадная (non-greedy), как и в литературе: инфицированная бактерия принимается со своей новой приспособленностью независимо от того, стала ли она лучше или хуже. Это намеренно — перенос призван перемешивать материал, а не только улучшать, и временное ухудшение отдельной бактерии здесь допустимо. Глобально лучшее решение при этом не страдает: в Revision оно сохраняется отдельно в cB / fB сразу после оценки каждого слота, поэтому даже неудачный перенос не способен потерять найденный оптимум — за это отвечает элитизм каркаса.
Сама фаза распределена по эпохам через автомат. В Moving на старте сегмента (когда cloneIdx равен нулю) строятся все клоны текущего сегмента, после чего каждую эпоху в популяционные слоты загружается один клон-срез — клон с номером cloneIdx у всех бактерий сразу:
//+------------------------------------------------------------------+ //| Moving | //| Заполняет слоты a[i].c кандидатами для оценки этой эпохи. | //+------------------------------------------------------------------+ void C_AO_BEA::Moving() { //--- первый прогон: бактерии -> слоты для первичной оценки FF if(!revision) { for(int i = 0; i < popSize; i++) for(int c = 0; c < coords; c++) a [i].c [c] = u.SeInDiSp(bact [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); return; } if(phase == PH_MUT) { //--- на старте сегмента строим клоны if(cloneIdx == 0) BuildClonesForSeg(segIdx); //--- грузим текущий клон каждой бактерии в слоты for(int b = 0; b < popSize; b++) { int idx = b * Nc + cloneIdx; for(int c = 0; c < coords; c++) a [b].c [c] = clone [idx].c [c]; } } else // PH_TRANS { //--- инфицируем слабую половину и грузим бактерии в слоты DoGeneTransfer(); for(int b = 0; b < popSize; b++) for(int c = 0; c < coords; c++) a [b].c [c] = bact [b].c [c]; } }
Честный учёт обращений к функции приспособленности. Теперь видно, почему фазовая организация так важна для корректного сравнения. Стоимость одного поколения BEA в обращениях к функции приспособленности складывается из двух слагаемых: мутация требует Nseg * Nc * popSize оценок (каждый из Nseg сегментов перебирает Nc клонов у всех popSize бактерий), перенос — nTrans * popSize. Принципиально, что ни то, ни другое не зависит от размерности задачи: при coords, равном десяти или тысяче, поколение стоит одинаково. Благодаря этому BEA расходует общий бюджет в десять тысяч вычислений по тем же правилам, что и остальные алгоритмы серии, и сравнение на фиксированном бюджете остаётся честным — никакой алгоритм не получает скрытой форы за счёт того, что его «поколение» на самом деле прячет в себе разное число оценок.
В Revision оценки этого среза записываются в соответствующие клоны, счётчик cloneIdx продвигается, и когда оценены все Nc клонов сегмента, для каждой бактерии выбирается лучший и закрепляется по описанному выше правилу. После этого автомат переходит к следующему сегменту, а пройдя все сегменты — к фазе переноса генов.
А закрепление лучшего клона выполняется только при условии, что он действительно превзошёл бактерию:
//+------------------------------------------------------------------+ //| Revision | //| Считывает a[i].f, обновляет cB/fB и продвигает автомат. | //+------------------------------------------------------------------+ void C_AO_BEA::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++) bact [i].f = a [i].f; revision = true; phase = PH_MUT; segIdx = 0; cloneIdx = 0; transIdx = 0; return; } if(phase == PH_MUT) { //--- сохраняем фитнес оценённого среза клонов for(int b = 0; b < popSize; b++) clone [b * Nc + cloneIdx].f = a [b].f; cloneIdx++; //--- сегмент полностью оценён -> закрепляем лучший клон if(cloneIdx >= Nc) { for(int b = 0; b < popSize; b++) { int best = 0; double bf = clone [b * Nc + 0].f; for(int j = 1; j < Nc; j++) { double cf = clone [b * Nc + j].f; if(cf > bf) { bf = cf; best = j; } } //--- закрепляем лучший мутант ТОЛЬКО если он превзошёл // инкумбента; иначе бактерия остаётся прежней (монотонность // мутации сохраняется без переоценки инкумбента клоном) if(bf > bact [b].f) { int bi = b * Nc + best; for(int c = 0; c < coords; c++) bact [b].c [c] = clone [bi].c [c]; bact [b].f = bf; } } cloneIdx = 0; segIdx++; //--- все сегменты пройдены -> перенос генов (или новое поколение) if(segIdx >= Nseg) { segIdx = 0; if(nTrans > 0) { phase = PH_TRANS; transIdx = 0; } else phase = PH_MUT; } } } else // PH_TRANS { //--- принимаем инфицированные генотипы (не-greedy) for(int b = 0; b < popSize; b++) bact [b].f = a [b].f; transIdx++; if(transIdx >= nTrans) { phase = PH_MUT; segIdx = 0; cloneIdx = 0; } } }
Важно понимать, что это не косметическая оптимизация, а содержательное улучшение. При Nc = 2 каноническая схема даёт на сегмент одного неизменного клона и одного мутанта, то есть проверяет всего один новый вариант. Наша схема при той же стоимости в два вызова функции даёт двух мутантов. Освободившийся от переоценки инкумбента слот занимается лишним свежим кандидатом, и именно это в наших прогонах подняло итоговый результат базовой конфигурации примерно с пятидесяти до пятидесяти трёх процентов. При этом монотонность мутации полностью сохраняется: условие if (bf > bact.f) означает, что бактерия либо улучшается, либо остаётся на месте, но никогда не деградирует — ровно то свойство, ради которого в каноне держали неизменный клон.
Параметры. Видимых параметров у класса пять. Размер популяции popSize — число бактерий. Число клонов Nc — сколько свежих мутантов проверяется на каждом сегменте. Число сегментов Nseg определяет крупность поблочной мутации. Число эпох переноса nTrans задаёт интенсивность горизонтального обмена за поколение. Наконец, доля transFrac определяет длину переносимого блока относительно размерности задачи. Их взаимодействие с бюджетом — а именно размен между качеством одного поколения и числом поколений, укладывающихся в фиксированный бюджет, — мы разберём при анализе результатов тестирования.
Результаты тестов
На общем счёте наших тестовых функций алгоритм набрал 53.13% при конфигурации с популяцией в 10 особей.BEA|Bacterial Evolutionary Algorithm|10.0|2.0|10.0|2.0|0.2|
=============================
5 Hilly's; Func runs: 10000; result: 0.9217077440618244
25 Hilly's; Func runs: 10000; result: 0.5961506596554828
500 Hilly's; Func runs: 10000; result: 0.2934090356286264
=============================
5 Forest's; Func runs: 10000; result: 0.9690648482875481
25 Forest's; Func runs: 10000; result: 0.44500075828106833
500 Forest's; Func runs: 10000; result: 0.08233566231751262
=============================
5 Megacity's; Func runs: 10000; result: 0.9053333333333334
25 Megacity's; Func runs: 10000; result: 0.4317333333333332
500 Megacity's; Func runs: 10000; result: 0.13676000000000088
=============================
All score: 4.78150 (53.13%)
Античит-тест указывает на честные показатели поисковой способности алгоритма.
BEA|Bacterial Evolutionary Algorithm|10.0|2.0|10.0|2.0|0.2|
=============================
Composite anti-cheat test: Hilly + Forest + Megacity + Peaks + Skin
Coordinates: 10; Epochs: 1000; Repeats: 10
=============================
Run 1/10: 0.9468505530003426
Run 2/10: 0.9621805930887799
Run 3/10: 0.8517460551795464
Run 4/10: 0.968005214717207
Run 5/10: 0.8697467385084419
Run 6/10: 0.9729983388567323
Run 7/10: 0.9703386568386824
Run 8/10: 0.9663920708043637
Run 9/10: 0.9545824368636746
Run 10/10: 0.8336853637354364
=============================
Average result: 0.9296526022 (92.97%)
=============================
Визуализация работы алгоритма BEA на тестовых функциях, а также на функциях добровольного выбора.
BEA на тестовой функции Hilly
BEA на тестовой функции Forest
BEA на тестовой функции Megacity
BEA на тестовой функции Peaks
BEA на тестовой функции Ackley
По результатам тестирования алгоритм занимает 37-е место в общем рейтинге лучших популяционных методов оптимизации.
| 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 | 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 |
| 44 | 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 |
| 45 | 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 |
| 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 | |
Выводы
Бактериальный эволюционный алгоритм в версии Нава — Фурухаси оказался алгоритмом с ясным и честным характером — без скрытых геометрических уловок и с предсказуемым поведением, причины которого прозрачны. На общем счёте по тройке тестовых функций он набрал 53.13% при конфигурации с малой популяцией, и это число стоит читать не как одну цифру, а как сумму двух очень разных историй по разным размерностям.
В малой размерности BEA силён. На десяти координатах он показывает результаты верхней трети таблицы — порядка 0.92 на Hilly, 0.97 на Forest, 0.91 на Megacity. Объяснение лежит в самой природе бактериальной мутации: когда сегмент состоит из одной-двух координат, посегментная регенерация превращается в почти покоординатный глобальный поиск, который на мультимодальных функциях работает отлично, выбрасывая координату по всему диапазону и оставляя лучшее. Перенос генов добавляет к этому быстрый обмен удачными блоками, и вместе они дают сильную сходимость.
С ростом размерности картина закономерно ухудшается, и здесь мы упираемся в структурное ограничение, а не в недостаток настройки. Поскольку число сегментов фиксировано, на тысяче координат каждый сегмент охватывает около сотни измерений, и одновременная случайная регенерация такого блока почти никогда не превосходит инкумбента — мутация фактически замирает, и работать остаётся одному переносу генов, которому, в свою очередь, нечего перемешивать в почти случайной популяции. Существенно, что это не вопрос бюджета: даже при неограниченном числе оценок грубая блочная регенерация в высокой размерности не улучшает решение. Это честное свойство алгоритма, а не дефект реализации, и в статье оно показано именно так.
Композитный античит-тест из пяти разнородных функций подтвердил чистоту алгоритма: его результат на композите не превышает результата на одиночных функциях той же размерности, то есть BEA не эксплуатирует осевую симметрию тестового стенда и оптимизирует каждую координатную пару по-настоящему — следствие того, что и мутация, и перенос работают строго поблочно, без скрытого домножения целого вектора на общий скаляр.
Если попытаться охарактеризовать BEA одной фразой, то это аккуратный локальный оптимизатор с механизмом быстрого обмена находками, прекрасно приспособленный к задачам умеренной размерности и структурно ограниченный на больших. Его главная идея — горизонтальный перенос блоков решения напрямую между особями — остаётся ценной и переносимой: она показывает, как можно ускорить распространение удачных фрагментов, не дожидаясь череды скрещиваний.
И здесь уместно вернуться к развилке, с которой мы начали. Та, оптимизационная ветвь Нава — Фурухаси, что разобрана в этой статье, — лишь одна из двух, носящих имя бактериального алгоритма. Вторая, историческая модель Тисато Нумаоки 1996 года, устроена принципиально иначе: это не оптимизатор статических функций, а агентная модель быстрой адаптации, в которой отбор осуществляет среда через гибель агентов, а сама колония рассчитана на выживание в постоянно меняющихся условиях. Проверять такую модель на статическом стенде — значит нагружать её не тем, для чего она создана. Поэтому модели Нумаоки будет посвящена отдельная работа. Мы соберём стенд с подвижным оптимумом и посмотрим, проявит ли себя там энергетический механизм бактериальной адаптации — то самое свойство, которое на статических функциях выглядит избыточным, а на нестационарных может оказаться решающим.
Рисунок 4. Цветовая градация алгоритмов по соответствующим тестам
Рисунок 5. Гистограмма результатов тестирования алгоритмов (по шкале от 0 до 100: чем больше, тем лучше, где 100 — максимально возможный теоретический результат), в архиве скрипт для расчёта рейтинговой таблицы
Плюсы и минусы алгоритма BEA:
Плюсы:
- Хорошие поисковые качества.
- Стабильность результатов (малый разброс).
Минусы:
- Большое количество внешних параметров.
К статье прикреплён архив с актуальными версиями кодов алгоритмов. Автор статьи не несёт ответственности за абсолютную точность в описании канонических алгоритмов, во многие из них внесены изменения для улучшения поисковых возможностей. Выводы и суждения, представленные в статьях, основываются на результатах проведённых экспериментов.
Программы, используемые в статье
| # | Имя | Тип | Описание |
|---|---|---|---|
| 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_BEA.mq5 | Скрипт | Испытательный стенд для BEA |
Предупреждение: все права на данные материалы принадлежат MetaQuotes Ltd. Полная или частичная перепечатка запрещена.
Данная статья написана пользователем сайта и отражает его личную точку зрения. Компания MetaQuotes Ltd не несет ответственности за достоверность представленной информации, а также за возможные последствия использования описанных решений, стратегий или рекомендаций.
Неопределённость как модель (Часть 7): Стохастические регрессоры
MQL5 Bootstrap (I): Набор переиспользуемых функций для работы с позициями и ордерами
Нейросети в трейдинге: Когнитивная инерция в анализе финансовых рынков (Окончание)
Создание пользовательских индикаторов в MQL5 (Часть 5): Доработка WaveTrend Crossover с помощью Canvas — градиентный туман, сигнальные пузырьки и управление рисками
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Вы принимаете политику сайта и условия использования