Алгоритм оптимизации на основе приспособленности — Fitness Dependent Optimizer (FDO)
45
0
Содержание
Введение
В серии, посвящённой алгоритмам оптимизации, в очередном кандидате я обычно ищу что-нибудь, чего раньше не встречал: необычный оператор, неожиданную геометрию поиска, простую с виду идею, которая при этом может работать.
Fitness Dependent Optimizer (FDO), предложенный Jaza M. Abdullah и Tarik A. Rashid в 2019 году, заинтересовал меня по другой причине. Идея у него простая, метафора пчелиная и, как бывает, к делу отношения не имеет. Зато внутри обнаружился конструктивный дефект. Он лежит на поверхности, но остался незамеченным, а низкая размерность авторских тестов объясняет почему. Дефект устраняется правкой в одну строку, после которой алгоритм прибавляет на восемнадцать процентных пунктов.
Один из результатов лучше назвать сразу, а не приберегать к выводам. Со строкой случайного алгоритма в рейтинговой таблице мы сверяемся постоянно. Любой мало-мальски работающий алгоритм её проходит. FDO не прошёл проверку. Каноническая версия, израсходовав весь бюджет вычислений целевой функции, приходит к решению хуже, чем десять тысяч случайных точек в пространстве поиска. Как мы к этому пришли и что с этим делать — дальше по тексту.
Реализация алгоритма
Что в этом алгоритме особенного? Метафора. Авторы вдохновлялись роением пчёл — той фазой жизненного цикла, когда колония делится и разведчики ищут место для нового улья. Разведчики облетают окрестности, оценивают найденные дупла по объёму, размеру летка, освещённости, а затем голосуют танцем; решение принимается, когда на одном месте сходится кворум.
Авторы отдельно оговаривают, что с алгоритмом пчелиной колонии (ABC) у FDO нет ничего общего, кроме источника вдохновения. Это правда — общего действительно нет. Как нет, впрочем, ничего общего и с настоящим роением: никакого кворума, никакого голосования и никакой коммуникации между агентами в алгоритме не появится. Метафору можно спокойно отложить и посмотреть на механику. У каждого агента вычисляется одна скалярная величина — вес приспособленности:fw = | f* / f_i | - wf
где f* — значение целевой функции глобального лучшего решения, f_i — значение у текущего агента, а wf — весовой фактор, принимающий значения 0 или 1. Это, не считая размера популяции, единственный настраиваемый параметр алгоритма. Формула записана для минимизации; для максимизации отношение переворачивается.
Дальше генерируется одно случайное число r в диапазоне [-1, 1] и по трём правилам вычисляется шаг:
pace = X_i · r (3) Во всех остальных случаях, то есть при 0 < fw < 1 , шаг строится от вектора, соединяющего агента с глобальным лучшим решением, а знак случайного числа задаёт направление:
r < 0: pace = -(X_i - X*) · fw (4) r ≥ 0: pace = (X_i - X*) · fw (5)
Новая позиция: X_new = X_i + pace. Если она лучше текущей, ход принимается, а значение pace запоминается. Если хуже — агент пробует шагнуть ещё раз, но уже сохранённым с прошлого удачного хода вектором; авторы называют это использованием предыдущего направления и выносят в число главных достижений работы. Если и это не помогает, агент остаётся на месте до следующей итерации.
Ни персонального лучшего решения, ни взаимодействия между агентами, ни каких-либо адаптивных коэффициентов в алгоритме нет. Вся память агента — один сохранённый вектор шага.
Геометрия, которую авторы не проговаривают. Вот здесь и обнаруживается самое интересное. Раскроем правила (4) и (5):
r < 0: X_new = X* + (X_i - X*) · (1 - fw) r ≥ 0: X_new = X* + (X_i - X*) · (1 + fw)
То есть FDO — это случайное радиальное масштабирование относительно глобального лучшего решения с коэффициентом (1 ± fw), где в штатном случае fw лежит в интервале от нуля до единицы. Агент либо приближается к лучшему, сокращая расстояние в некоторое число раз, либо отдаляется от него, но не более чем вдвое за шаг. Перелететь через лучшего он не может в принципе.
А теперь ключевое следствие, из-за которого вся эта статья и написана. Направление (X_i - X*) при таком преобразовании не меняется. Агент навсегда заперт на прямой, проходящей через глобального лучшего в направлении его собственной стартовой точки. Независимо от размерности задачи (10, 50 или 1000 координат) за одну итерацию агент имеет только одну степень свободы. Вся популяция исследует не пространство поиска, а объединение нескольких десятков одномерных прямых в нём, то есть множество нулевой меры.
Направления обновляются только тогда, когда сдвигается сам глобальный лучший. А сдвинуть его может почти исключительно правило (3) — та самая вырожденная ветвь pace = X_i · r. Она срабатывает ровно для лучшего агента: у него f_i совпадает с f*, вес приспособленности становится равным единице, и обычная формула дала бы нулевой шаг. Получается, что весь двигатель алгоритма — это один агент за итерацию, который масштабирует свой радиус-вектор относительно начала координат.
Рисунок 1. Геометрия поиска в каноническом FDO.
Слева: отдельный агент. Синим отмечено глобальное лучшее решение cB, тёмным — текущая позиция агента, оранжевым — две возможные позиции после шага. Обе лежат на одной прямой, проходящей через cB и агента, поэтому за итерацию у агента есть ровно одна степень свободы, сколько бы координат ни было в задаче. Справа: та же картина для всей популяции. Область поиска, доступная рою, — не пространство, а звезда из нескольких десятков прямых, то есть множество нулевой меры.
Заодно отметим, что привязка шага к началу координат геометрически некорректна, сама по себе. Размер шага здесь зависит от расстояния до нулевой точки, а не от размеров области поиска: вблизи нуля он вырождается, вдали становится огромным. Забегая вперёд, скажу, что на результатах это, вопреки ожиданиям, никак не сказалось, — но проверять пришлось отдельным опытом.
Ещё две мелочи:
Первая: формула веса приспособленности корректна только для неотрицательных значений целевой функции. При знакопеременной функции отношение вылетает за пределы [0, 1] и вся логика ветвления ломается.
Вторая: параметр wf описан авторами как переключатель между быстрой сходимостью и широким покрытием пространства. Проверка показала, что в каноническом алгоритме он не влияет вообще ни на что, а после нашей модификации внезапно оживает и становится значимым — причём смысл его оказывается противоположным описанию. Но это уже раздел с результатами тестирования.
Диагноз формулируется коротко: один случайный скаляр на агента запирает его на луче. Отсюда и напрашивается правка. Достаточно генерировать r не один раз на агента, а отдельно для каждой координаты. Формулы, веса, правила ветвления, приём хода, хранение шага — всё остаётся канонически нетронутым, меняется единственная строка кода: генератор случайного числа переезжает внутрь цикла по координатам.
Что при этом происходит геометрически. Раньше все координаты агента масштабировались одним и тем же множителем, и точка ползала по лучу. Теперь по каждой оси независимо выбирается либо сжатие с коэффициентом (1 - fw), либо растяжение с коэффициентом (1 + fw). Вместо одного луча агент получает в своё распоряжение вершины бокса вокруг лучшего решения, а число степеней свободы становится равным размерности задачи — как и должно быть у нормального популяционного алгоритма.
Рисунок 2. Геометрия поиска после модификации.
Слева: тот же агент, что и на рисунке 1, но выбор направления делается по каждой координате независимо. Прямая, по которой агент был вынужден ходить раньше, показана серым; вместо двух точек на ней он получает вершины бокса, и в задаче размерности n таких вершин 2 в степени n. Справа: для всей популяции звезда прямых превращается в набор областей, а суммарно доступное для поиска множество перестаёт быть вырожденным.
Важно, что при этом сохраняется идентичность алгоритма. Вес приспособленности остаётся скалярным и по-прежнему управляет длиной шага именно так, как задумано авторами; правила (3), (4) и (5) не переписываются. Это по-прежнему FDO, а не другой алгоритм под чужим именем — иначе сравнивать было бы не с чем.
Помимо основной правки надо было проверить ещё три гипотезы, и две из них пришлось отклонить:
- замена вырожденной ветви. Привязку шага к началу координат заменили на ядро, привязанное к диапазону поиска. Результат не изменился в пределах разброса стенда — дефект в конструкции есть, но на счёт он не влияет;
- перезапуск застойных агентов. Механизм оказался не нужен: после основной правки доля агентов с нулевым шагом падает практически до нуля, чинить нечего;
- отключение хранения шага. Единственный из трёх заявленных авторами вкладов работы, который выдержал проверку. Механизм действительно стоит около шести процентных пунктов, но работает совершенно не так, как его описывают.
Наконец — о методике. Разрыв между канонической версией и модификацией настолько велик, что возникает вопрос: с чем сравнивать нижнюю границу? Для этого мы поставили нуль-модель — прогон, в котором алгоритм не делает ни одного шага, а просто оценивает десять тысяч равномерно случайных точек и берёт лучшую. Получилась отсечка, ниже которой любой результат означает, что итерации алгоритма приносят вреда больше, чем пользы. Приём простой, но в этой серии он раньше не использовался, а стоило бы — и, судя по тому, что показала каноническая версия FDO, применять его теперь придётся регулярно.
Перед тем как перейти к коду, соберём алгоритм целиком. В записи ниже X_i — принятая позиция агента, f_i — соответствующее ей значение целевой функции, cB и fB — координаты и значение глобального лучшего решения.
ВХОД: popSize, wf ∈ {0,1}, rangeMin[], rangeMax[]
СОСТОЯНИЕ АГЕНТА: X_i, f_i, paceCand_i, pacePrev_i, hasPrev_i, stage_i
// ── инициализация ───────────────────────────────────────────────
для i = 1..popSize:
paceCand_i = 0; pacePrev_i = 0
hasPrev_i = false
stage_i = MAIN
f_i = -∞
// ── первая эпоха: равномерный разброс по пространству ───────────
для i = 1..popSize:
кандидат_i = случайная точка в [rangeMin, rangeMax]
вычислить ЦФ для всех кандидатов // расход бюджета: popSize
для i = 1..popSize:
X_i = кандидат_i; f_i = ЦФ(кандидат_i)
обновить cB, fB
// ── основной цикл ───────────────────────────────────────────────
пока не исчерпан бюджет:
// ---- фаза 1: построение кандидатов -------------------------
для i = 1..popSize:
если stage_i == MAIN:
// вес приспособленности, ур. (6)
если |fB| < eps: fw = 0
иначе: fw = |f_i / fB| - wf
// вырожденность — свойство агента, не координаты
degenerate = ( |fw| < eps ИЛИ |fw - 1| < eps )
для c = 1..coords:
r = СЛУЧ[-1, 1] // ← свой r на каждую координату
если degenerate:
pace = X_i[c] * r // ур. (3)
иначе если r < 0:
pace = -(X_i[c] - cB[c]) * fw // ур. (4)
иначе:
pace = (X_i[c] - cB[c]) * fw // ур. (5)
paceCand_i[c] = pace
кандидат_i[c] = ограничить(X_i[c] + pace) // ур. (1)
иначе: // stage_i == PREV, повтор сохранённым шагом
для c = 1..coords:
кандидат_i[c] = ограничить(X_i[c] + pacePrev_i[c])
// ---- вычисление ЦФ ------------------------------------------
вычислить ЦФ для всех кандидатов // расход бюджета: popSize
// ---- фаза 2: приём и переключение состояний -----------------
обновить cB, fB по лучшему из кандидатов
для i = 1..popSize:
если ЦФ(кандидат_i) лучше f_i:
X_i = кандидат_i; f_i = ЦФ(кандидат_i)
если stage_i == MAIN:
pacePrev_i = paceCand_i // запомнить удачный шаг
hasPrev_i = true
// в PREV шаг не перезаписывается: инерция используется как есть
stage_i = MAIN
иначе:
если stage_i == MAIN И hasPrev_i:
stage_i = PREV // дать второй шанс
иначе:
stage_i = MAIN // агент остаётся на месте Три места здесь требуют пояснения.
Строка с генерацией r. Это и есть вся модификация. В оригинале она стоит на одну вложенность выше — до цикла по координатам, а не внутри него.
Автомат MAIN/PREV. У авторов вторая проба условная и выполняется внутри той же итерации: агент тратит то одно вычисление целевой функции, то два. Наш стенд требует фиксированного расхода бюджета, поэтому повторная проба вынесена в следующий такт. Семантика при этом сохраняется полностью — агент по-прежнему сначала пробует свежий шаг, при неудаче повторяет сохранённый, а при второй неудаче остаётся на месте. Меняется лишь то, что одна итерация FDO иногда занимает две эпохи стенда.
Проверка |fB| < eps. В оригинале защита от деления на ноль стоит на знаменателе, а знаменателем в версии для минимизации выступает значение целевой функции самого агента. При переходе к максимизации отношение переворачивается, и защита обязана переехать на fB. Авторы уравнение (6) привели, а правило деления под него переписать забыли — недосмотр небольшой, но при реализации на него легко наступить.
Структура агента. Прежде чем писать класс, стоит решить, что именно придётся хранить между эпохами. Базовый класс C_AO уже даёт каждому агенту довольно много: a[i].c — координаты текущего кандидата, которые оценивает стенд, a[i].cB и a[i].fB — лучшие координаты агента и их значение целевой функции, a[i].cnt — счётчик общего назначения.
FDO ложится на эту структуру на удивление точно. Приём хода здесь жадный: позиция агента может только улучшаться, а значит его текущее положение и есть его личный рекорд — отдельно хранить их незачем, a[i].cB и a[i].fB подходят напрямую. Состояние автомата, о котором шла речь выше, занимает a[i].cnt. Не хватает только двух векторов шага и флага, есть ли что переиспользовать, — под них и заводим свою структуру:
//+------------------------------------------------------------------+ //| Хранит только то, чего нет в S_AO_Agent. Принятая позиция агента | //| и её фитнес живут в a[i].cB и a[i].fB (при жадном приёме принятая| //| позиция и есть личный рекорд), состояние автомата — в a[i].cnt. | //+------------------------------------------------------------------+ struct S_FDOm_Pace { double cand []; // pace текущей основной пробы double prev []; // сохранённый pace последнего принятого хода bool hasPrev; // есть ли сохранённая инерция void Init(int coords) { ArrayResize(cand, coords); ArrayResize(prev, coords); ArrayInitialize(cand, 0.0); ArrayInitialize(prev, 0.0); hasPrev = false; } };
Класс алгоритма. Параметров у FDO всего два — размер популяции и весовой фактор:
//+------------------------------------------------------------------+ //| | //+------------------------------------------------------------------+ class C_AO_FDOm : public C_AO { public: ~C_AO_FDOm() {} C_AO_FDOm() { ao_name = "FDOm"; ao_desc = "Fitness Dependent Optimizer M"; ao_link = "https://www.mql5.com/ru/articles/21639"; popSize = 50; // размер популяции (в статье 30 разведчиков) wf = 0.0; // весовой фактор, каноника: 0 или 1 ArrayResize(params, 2); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "wf"; params [1].val = wf; } void SetParams() { popSize = (int)params [0].val; wf = params [1].val; if(popSize < 2) popSize = 2; //--- в каноне wf принимает только 0 или 1 if(wf != 0.0 && wf != 1.0) wf = (wf >= 0.5) ? 1.0 : 0.0; } bool Init(const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0); void Moving(); void Revision(); //--- видимые параметры double wf; // весовой фактор из ур. (2)/(6) private: S_FDOm_Pace pace []; // [popSize] - векторы шага, которых нет в S_AO_Agent //--- состояния автомата, хранятся в a[i].cnt // STAGE_MAIN - основная проба по ур. (3)/(4)/(5) // STAGE_PREV - повторная проба сохранённым pace #define STAGE_MAIN 0 #define STAGE_PREV 1 };
Обратите внимание на приведение wf в SetParams. Авторы определяют этот параметр как принимающий значения 0 или 1, и промежуточные величины в их формулах смысла не имеют, поэтому любое введённое пользователем число округляется до ближайшего из двух допустимых.
Метод Init после вызова StandardInit раздаёт память только под свою структуру — всё остальное базовый класс сделал сам, включая обнуление a[i].cnt и установку a[i].fB в минус бесконечность:
//+------------------------------------------------------------------+ //| Init | //+------------------------------------------------------------------+ bool C_AO_FDOm::Init(const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0) { //--- StandardInit создаёт a[], обнуляет a[i].cnt и ставит a[i].fB = -DBL_MAX if(!StandardInit(rangeMinP, rangeMaxP, rangeStepP)) return false; ArrayResize(pace, popSize); for(int i = 0; i < popSize; i++) pace [i].Init(coords); return true; }
Метод Moving. Здесь строятся кандидаты. Первая эпоха особая — популяция разбрасывается по пространству поиска равномерно. Дальше каждый агент действует в зависимости от своего состояния:
//+------------------------------------------------------------------+ //| Moving | //| STAGE_MAIN: основная проба, pace по ур. (3)/(4)/(5) | //| STAGE_PREV: повторная проба сохранённым pace (второй шанс) | //| | //| Условная вторая проба оригинала разложена в автомат на два | //| такта: каждый агент отдаёт стенду ровно одного кандидата за | //| эпоху, поэтому бюджет вычислений ЦФ расходуется точно. | //+------------------------------------------------------------------+ void C_AO_FDOm::Moving() { //--- первый прогон: вся популяция случайна if(!revision) { for(int i = 0; i < popSize; i++) for(int c = 0; c < coords; c++) a [i].c [c] = u.SeInDiSp(u.RNDfromCI(rangeMin [c], rangeMax [c]), rangeMin [c], rangeMax [c], rangeStep [c]); return; } const double eps = 1e-12; double fw, r, p, x, xc; for(int i = 0; i < popSize; i++) { if(a [i].cnt == STAGE_MAIN) { //--- вес приспособленности, ур. (6) — версия для максимизации. // Делитель здесь fB, поэтому защита от деления на ноль // переезжает с фитнеса агента на фитнес лучшего. if(MathAbs(fB) < eps) fw = 0.0; else fw = MathAbs(a [i].fB / fB) - wf; //--- вырожденность определяется скалярным fw, значит решается // один раз на агента, а не на координату bool degenerate = (MathAbs(fw) < eps || MathAbs(fw - 1.0) < eps); for(int c = 0; c < coords; c++) { //--- ключевое отличие: свой случайный скаляр на каждую координату r = u.RNDfromCI(-1.0, 1.0); xc = a [i].cB [c]; if(degenerate) p = xc * r; // ур. (3) else { if(r < 0.0) p = -(xc - cB [c]) * fw; // ур. (4) else p = (xc - cB [c]) * fw; // ур. (5) } pace [i].cand [c] = p; x = xc + p; // ур. (1) a [i].c [c] = u.SeInDiSp(x, rangeMin [c], rangeMax [c], rangeStep [c]); } } else { //--- продолжить в прежнем направлении for(int c = 0; c < coords; c++) { x = a [i].cB [c] + pace [i].prev [c]; a [i].c [c] = u.SeInDiSp(x, rangeMin [c], rangeMax [c], rangeStep [c]); } } } }
Вся модификация: r = u.RNDfromCI(-1.0, 1.0); внутри цикла по координатам. В каноническом варианте она стоит на одну вложенность выше, рядом с вычислением fw . Проверка на вырожденность при этом остаётся снаружи цикла и это принципиально: fw — величина скалярная, она характеризует агента целиком, и решать по каждой координате отдельно, вырожден он или нет, было бы уже не FDO.
Отдельно стоит сказать про обработку выхода за границы. В оригинальной работе о ней не сказано ни слова, хотя ветвь pace = X_i · r регулярно выбрасывает агента за пределы области. Мы используем SeInDiSp , то есть обрезку по границе — самый нейтральный из возможных вариантов. Отражение от границы дало бы алгоритму дополнительный источник разнообразия, которого авторы не закладывали.
Метод Revision. Здесь принимаются ходы и переключаются состояния автомата:
//+------------------------------------------------------------------+ //| Revision | //| Жадный приём: позиция агента может только улучшаться, поэтому | //| a[i].cB/fB и есть его текущее положение. Персонального лучшего | //| в отдельном смысле в FDO нет, память агента — только pace. | //+------------------------------------------------------------------+ void C_AO_FDOm::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++) { ArrayCopy(a [i].cB, a [i].c, 0, 0, coords); a [i].fB = a [i].f; a [i].cnt = STAGE_MAIN; pace [i].hasPrev = false; } revision = true; return; } for(int i = 0; i < popSize; i++) { if(a [i].f > a [i].fB) { //--- ход принят ArrayCopy(a [i].cB, a [i].c, 0, 0, coords); a [i].fB = a [i].f; if(a [i].cnt == STAGE_MAIN) { //--- новый pace запоминается для потенциального переиспользования ArrayCopy(pace [i].prev, pace [i].cand, 0, 0, coords); pace [i].hasPrev = true; } //--- в STAGE_PREV prev не обновляется: инерция переиспользуется как есть a [i].cnt = STAGE_MAIN; } else { //--- основная проба провалилась -> следующий такт по сохранённой инерции; // если инерции нет или провалилась уже она — агент остаётся на месте if(a [i].cnt == STAGE_MAIN && pace [i].hasPrev) a [i].cnt = STAGE_PREV; else a [i].cnt = STAGE_MAIN; } } }
Тонкость в ветке приёма: сохранённый шаг перезаписывается только тогда, когда удачной оказалась основная проба. Если сработал повтор по инерции, вектор остаётся прежним и может быть использован ещё раз. Именно так это описано у авторов, и именно эта деталь, как выяснится в разделе с результатами, отвечает за пять с лишним процентных пунктов итогового счёта.
Ещё одно отступление от оригинала — обновление глобального лучшего. В псевдокоде авторов оно происходит асинхронно, прямо внутри цикла по агентам, так что агенты в конце списка уже видят улучшения, найденные агентами в начале. Схема Moving / Revision требует пакетного обновления, поэтому все агенты одной эпохи работают с одним и тем же cB . Отклонение небольшое, но упомянуть его честнее, чем умолчать.
Две версии. Для тестов нам понадобятся оба варианта: канонический, чтобы честно измерить алгоритм в том виде, в каком его предложили авторы, и модифицированный. Отличаются они, повторюсь, одной строкой — положением генератора случайного числа относительно цикла по координатам. Канонический вариант получает имя FDO, модифицированный — FDOm.
Результаты тестов
Каноническая версия. Запускаем FDO ровно в том виде, в каком его описали авторы, с их же настройками по умолчанию — тридцать агентов, весовой фактор ноль:
FDO|Fitness Dependent Optimizer|30.0|0.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.4506265183374849
25 Hilly's; Func runs: 10000; result: 0.31420642999764575
500 Hilly's; Func runs: 10000; result: 0.25694128705845914
=============================
5 Forest's; Func runs: 10000; result: 0.2477545234983984
25 Forest's; Func runs: 10000; result: 0.10741019765506517
500 Forest's; Func runs: 10000; result: 0.04695720206771069
=============================
5 Megacity's; Func runs: 10000; result: 0.2795555555555555
25 Megacity's; Func runs: 10000; result: 0.15946666666666673
500 Megacity's; Func runs: 10000; result: 0.10117333333333417
=============================
All score: 1.96409 (21.82%)
Само по себе число 21.82% ещё ни о чём не говорит: слабые алгоритмы в серии встречались и раньше. Вопрос в другом — насколько это плохо в абсолютном выражении? С чем вообще сравнивать нижнюю границу?
Нуль-модель: а нужен ли здесь алгоритм? Ответ на такой вопрос в серии есть давно: в рейтинговой таблице присутствует строка чисто случайного алгоритма RND, с которой мы сверяемся постоянно. Но есть и второй способ получить ту же отсечку — прямо в прогоне исследуемого алгоритма, не имея под рукой отдельной реализации случайного поиска. Способ пригодится всякому, кто тестирует свой алгоритм в отрыве от нашей таблицы, поэтому покажу его отдельно.
Технически это делается без единой правки кода. Достаточно задать размер популяции равным всему бюджету — десять тысяч агентов. Тогда число эпох становится равным единице, Moving уходит в ветку первого прогона и раскидывает десять тысяч равномерно случайных точек, стенд их оценивает, Revision забирает лучшую. Ни одного шага FDO при этом не выполняется:
FDO|Fitness Dependent Optimizer|10000.0|0.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.4903288565198099
25 Hilly's; Func runs: 10000; result: 0.3250854283913946
500 Hilly's; Func runs: 10000; result: 0.2581589552458167
=============================
5 Forest's; Func runs: 10000; result: 0.3117621608401851
25 Forest's; Func runs: 10000; result: 0.11762072646712074
500 Forest's; Func runs: 10000; result: 0.043999588590179974
=============================
5 Megacity's; Func runs: 10000; result: 0.3333333333333333
25 Megacity's; Func runs: 10000; result: 0.16702222222222224
500 Megacity's; Func runs: 10000; result: 0.10272000000000085
=============================
All score: 2.15003 (23.89%)
23.89% против 21.82%. Случайный перебор оказался лучше алгоритма на два процентных пункта.
Композитный балл — величина суммарная, и на неё одну полагаться не стоит, поэтому сравним поячеечно. Случайный перебор впереди на семи ячейках из девяти, ещё в двух разница лежит в третьем знаке и содержательного смысла не имеет, а FDO выигрывает единственную ячейку — Forest в высокой размерности, с отрывом 0.003. Согласованность по девяти независимым задачам делает вывод куда убедительнее, чем разница в композите.
Формулируется он так: триста тридцать три итерации канонического FDO приводят к худшему решению, чем однократная оценка десяти тысяч случайных точек. Иными словами, итерации этого алгоритма имеют отрицательную предельную полезность — работа хуже бездействия.
Причина уже разобрана в разделе 2. Сжатие к глобальному лучшему улучшает фитнес чаще, чем растяжение, поэтому принимается чаще, и расстояние от агента до cB убывает геометрически. Когда оно схлопывается, шаг обращается в ноль, кандидат совпадает с текущей позицией, приём не срабатывает — и агент замирает навсегда, продолжая тратить по одному вычислению целевой функции за эпоху до конца прогона.
Модификация. Теперь та же конфигурация, но с генератором случайного числа, перенесённым внутрь цикла по координатам:
FDOm|Fitness Dependent Optimizer M|30.0|0.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.5783073646507747
25 Hilly's; Func runs: 10000; result: 0.5041297306171266
500 Hilly's; Func runs: 10000; result: 0.30349616788626477
=============================
5 Forest's; Func runs: 10000; result: 0.5870110150402623
25 Forest's; Func runs: 10000; result: 0.44914298226938415
500 Forest's; Func runs: 10000; result: 0.1073782418893213
=============================
5 Megacity's; Func runs: 10000; result: 0.44000000000000017
25 Megacity's; Func runs: 10000; result: 0.44702222222222227
500 Megacity's; Func runs: 10000; result: 0.1703155555555559
=============================
All score: 3.58680 (39.85%)
21.82% → 39.85%. Восемнадцать процентных пунктов за перенос одной строки на уровень вложенности ниже. Прирост есть во всех девяти ячейках, но распределён он неравномерно, и это распределение подтверждает диагноз:
| Ячейка | FDO | FDOm | Отношение |
|---|---|---|---|
| Hilly 5 | 0.451 | 0.578 | 1.3 |
| Hilly 25 | 0.314 | 0.504 | 1.6 |
| Hilly 500 | 0.257 | 0.303 | 1.2 |
| Forest 5 | 0.248 | 0.587 | 2.4 |
| Forest 25 | 0.107 | 0.449 | 4.2 |
| Forest 500 | 0.047 | 0.107 | 2.3 |
| Megacity 5 | 0.280 | 0.440 | 1.6 |
| Megacity 25 | 0.159 | 0.447 | 2.8 |
| Megacity 500 | 0.101 | 0.170 | 1.7 |
Максимум приходится на среднюю размерность — двадцать пять функций, то есть пятьдесят координат. Логика такая: в десяти координатах потеря девяти степеней свободы из десяти ещё терпима, случайная прямая с заметной вероятностью пройдёт достаточно близко к чему-то полезному. В пятидесяти координатах ограничение становится удушающим, и снятие его даёт кратный выигрыш. В тысяче координатах прирост снова сжимается, но уже по другой причине — там в бюджет упирается любой алгоритм.
Сравнение с нуль-моделью теперь выглядит здоровым: 39.85% против 23.89%, то есть итерации FDOm приносят шестнадцать пунктов сверх случайного перебора.
Весовой фактор: мёртвый параметр, который ожил. Единственный настраиваемый параметр алгоритма, помимо размера популяции, авторы описывают как переключатель между быстрой сходимостью и широким покрытием пространства. Проверим. В каноническом варианте wf = 0 даёт 22.87%, а wf = 1 — 22.95% (десять повторов). Разница в восемь сотых пункта при разбросе в 1.7 — это не почти одинаково, это в точности одно и то же. Единственный параметр алгоритма не влияет ни на что.
Механика понятна, если проследить, что происходит при wf = 1. Вес приспособленности меняет знак, и вместе с ним меняются местами роли положительного и отрицательного r: то, что раньше вело агента к лучшему, теперь ведёт от него, и наоборот. Но r симметричен на отрезке [-1, 1], поэтому по распределению направлений это тождественная операция. Меняется лишь модуль шага — вместо ratio он становится 1 - ratio, — а при единственном r на агента это различие размывается по популяции и тонет.
А вот после модификации параметр внезапно оживает: 39.85% против 28.88%. Причём смысл его оказывается противоположным описанию авторов. При покоординатном r модуль шага определяет геометрию бокса вокруг cB, и переотображение ratio в 1 - ratio перестаёт быть нейтральным. Оно меняет то, кто именно замирает. При wf = 0 нулевой шаг достаётся плохим агентам — тем, чей фитнес далёк от лучшего. При wf = 1 замирают, наоборот, хорошие: те, что сидят у оптимума и двигают fB. Авторский вариант по умолчанию оказался правильным, но, судя по их же описанию параметра, скорее по счастливой случайности.
Размер популяции. С размером популяции 50 были получены несколько лучшие результаты:
FDOm|Fitness Dependent Optimizer M|50.0|0.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.6582011735378811
25 Hilly's; Func runs: 10000; result: 0.532363366069693
500 Hilly's; Func runs: 10000; result: 0.29692460081977007
=============================
5 Forest's; Func runs: 10000; result: 0.7110671771319258
25 Forest's; Func runs: 10000; result: 0.3931805908348741
500 Forest's; Func runs: 10000; result: 0.07900269755933396
=============================
5 Megacity's; Func runs: 10000; result: 0.4995555555555555
25 Megacity's; Func runs: 10000; result: 0.4106666666666668
500 Megacity's; Func runs: 10000; result: 0.14908444444444519
=============================
All score: 3.73005 (41.44%)
Что было проверено и отвергнуто.Помимо основной правки я проверил три гипотезы. Две из них пришлось отклонить, и обе стоят упоминания — отрицательный результат экономит время тем, кто пойдёт следом.
Привязка вырожденной ветви к началу координат. Правило (3) масштабирует радиус-вектор агента относительно нулевой точки пространства, а не относительно области поиска. Геометрически это некорректно: величина шага зависит от расстояния до нуля. Вблизи него шаг вырождается, вдали становится огромным. Напрашивается замена на локальное ядро с радиусом, заданным в долях диапазона. Результат: 40.77% при радиусе 0.1, 39.80% при 0.3, 41.59% при 0.7 — против 41.36% у канонической ветви (все на десяти повторах). Зависимости от радиуса нет, весь размах укладывается в разброс стенда.
Перезапуск застойных агентов. Гипотеза выглядела разумной: раз агенты замирают, надо считать простои и отправлять безнадёжных в случайную точку. Прежде чем писать механизм, я измерил долю агентов с практически нулевым шагом — она составила от 0.00 до 0.03% в средней и высокой размерности и единицы процентов в низкой. Исправлять нечего: покоординатный выбор направления закрыл проблему сам. Раньше все координаты сжимались синхронно, теперь примерно половина на каждом шаге растягивается, и шаг попросту не успевает обратиться в ноль.
Третья гипотеза оказалась продуктивной. Хранение и переиспользование удачного шага авторы объявляют одним из трёх главных достижений работы, так что проверить вклад стоило прямым экспериментом — отключить механизм и посмотреть. Отключение даёт 35.69% против 41.36% (десять повторов). Около пяти с половиной пунктов — это единственный из трёх заявленных авторами вкладов, который выдержал проверку. Но диагностические счётчики показали, что работает он совершенно не так, как его подают.
Повторная проба по сохранённому шагу принимается хуже основной, причём всюду. На тысяче координат в задаче Hilly основная проба принимается в 23–40% случаев, повторная — в 0.8–3.7%. При этом повторные пробы съедают от 30 до 47% всего бюджета вычислений. По прямой отдаче это худшая инвестиция в алгоритме — и тем не менее её удаление роняет счёт почти на шесть пунктов.
Без хранения шага популяция схлопывается на глобальном лучшем: доля агентов с нулевым шагом уходит в 10–15%, а частота срабатывания вырожденной ветви растёт впятеро и больше — то есть агенты массово достигают состояния, в котором их фитнес равен фитнесу лучшего, и буквально садятся на него.
Значит, сохранённый шаг — не ускоритель сходимости, а тормоз схлопывания. Принятые основные ходы смещены в сторону сжатия к cB, поэтому чем их больше, тем быстрее коллапс. Повторная проба занимает ход провалившегося агента чем-то, что к cB его не притягивает. Низкий процент приёма здесь не недостаток, а описание роли: механизм оплачивает разнообразие эффективностью отдельного хода.
Осевого или диагонального чита нет: покоординатный r связку между координатами снял, и композит это подтверждает.
FDOm|Fitness Dependent Optimizer M|50.0|0.0|
=============================
Composite anti-cheat test: Hilly + Forest + Megacity + Peaks + Skin
Coordinates: 10; Epochs: 200; Repeats: 10
Shift factor: 0.00 range widths (landscape unchanged, origin moved)
=============================
Run 1/10: 0.7733279387870868
Run 2/10: 0.9688070744238695
Run 3/10: 0.9834501241818984
Run 4/10: 0.8667420238367877
Run 5/10: 0.6682500612356771
Run 6/10: 0.7705050391750058
Run 7/10: 0.6788865956809605
Run 8/10: 0.6061625607074728
Run 9/10: 0.8640987853837709
Run 10/10: 0.7874534212323144
=============================
Average result: 0.7967683625 (79.68%)
=============================
Визуализация работы алгоритма FDOm на тестовых функциях и двух дополнительных, случайно выбранных.
FDOm на тестовой функции Hilly
FDOm на тестовой функции Forest
FDOm на тестовой функции Megacity
FDOm на тестовой функции Paraboloid
FDOm на тестовой функции Peaks
По результатам тестирования алгоритм FDOm представлен ознакомительно в рейтинговой таблице.
| cc | AO | Description | Hilly | Hilly Final | Forest | Forest Final | Megacity (discrete) | Megacity Final | Final Result | % of MAX | ||||||
| 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | ||||||||
| 1 | ANS | across neighbourhood search | 1,00000 | 0,88228 | 0,40138 | 2,28366 | 1,00000 | 0,95281 | 0,28092 | 2,23373 | 0,94667 | 0,85733 | 0,22389 | 2,02789 | 6,545 | 72,72 |
| 2 | AMOm | animal migration optimization M | 0,91624 | 0,83603 | 0,46790 | 2,22017 | 0,98482 | 0,92010 | 0,36391 | 2,26883 | 0,91733 | 0,81707 | 0,25177 | 1,98617 | 6,475 | 71,94 |
| 3 | CLA | code lock algorithm (joo) | 0,95139 | 0,86199 | 0,37879 | 2,19217 | 0,99349 | 0,93500 | 0,26497 | 2,19346 | 0,93600 | 0,84267 | 0,24060 | 2,01927 | 6,405 | 71,17 |
| 4 | (P+O)ES | (P+O) evolution strategies | 0,86571 | 0,89539 | 0,39740 | 2,15850 | 0,97761 | 0,89820 | 0,26878 | 2,14459 | 0,92133 | 0,80240 | 0,23952 | 1,96325 | 6,266 | 69,62 |
| 5 | SDSm | stochastic diffusion search M | 0,95195 | 0,84944 | 0,36249 | 2,16388 | 0,98061 | 0,88457 | 0,22112 | 2,08630 | 0,92267 | 0,79013 | 0,21380 | 1,92660 | 6,177 | 68,63 |
| 6 | AAm | archery algorithm M | 0,84685 | 0,73320 | 0,42590 | 2,00595 | 0,96709 | 0,77837 | 0,27789 | 2,02335 | 0,86133 | 0,77707 | 0,28712 | 1,92552 | 5,955 | 66,17 |
| 7 | SIA | simulated isotropic annealing (joo) | 0,93543 | 0,86504 | 0,38483 | 2,18530 | 0,94069 | 0,80609 | 0,23835 | 1,98513 | 0,86400 | 0,66160 | 0,19536 | 1,72096 | 5,891 | 65,46 |
| 8 | TETA | time evolution travel algorithm (joo) | 0,91452 | 0,86369 | 0,25579 | 2,03400 | 0,99654 | 0,91291 | 0,14394 | 2,05339 | 0,85467 | 0,82213 | 0,10443 | 1,78123 | 5,869 | 65,21 |
| 9 | ESG | evolution of social groups (joo) | 0,98111 | 0,79857 | 0,31167 | 2,09135 | 0,98954 | 0,82270 | 0,15032 | 1,96256 | 0,92133 | 0,73440 | 0,15315 | 1,80888 | 5,863 | 65,14 |
| 10 | CTA | comet tail algorithm (joo) | 0,92435 | 0,86786 | 0,27838 | 2,07059 | 0,99039 | 0,84571 | 0,19448 | 2,03058 | 0,95467 | 0,69680 | 0,11008 | 1,76155 | 5,863 | 65,14 |
| 11 | COA | coyote_optimization_algorithm | 0,88909 | 0,70681 | 0,32718 | 1,92308 | 0,99467 | 0,85358 | 0,15152 | 1,99977 | 0,88533 | 0,71040 | 0,18981 | 1,78554 | 5,708 | 63,43 |
| 12 | ECBO | enhanced colliding bodies optimization | 0,94024 | 0,72363 | 0,32356 | 1,98743 | 0,99477 | 0,80291 | 0,13056 | 1,92824 | 0,87600 | 0,70160 | 0,17433 | 1,75193 | 5,668 | 62,98 |
| 13 | DA | dialectical algorithm | 0,93117 | 0,75400 | 0,26205 | 1,94722 | 0,98925 | 0,81375 | 0,08662 | 1,88962 | 0,92667 | 0,68107 | 0,11315 | 1,72089 | 5,558 | 61,76 |
| 14 | BBO | biogeography based optimization | 0,95876 | 0,70609 | 0,35752 | 2,02237 | 0,92981 | 0,70660 | 0,16970 | 1,80611 | 0,87467 | 0,63013 | 0,20813 | 1,71293 | 5,541 | 61,57 |
| 15 | BHAm | black hole algorithm M | 0,79558 | 0,76207 | 0,34682 | 1,90447 | 0,99836 | 0,75798 | 0,13826 | 1,89460 | 0,85067 | 0,64427 | 0,17020 | 1,66514 | 5,464 | 60,71 |
| 16 | HS | harmony search | 0,91420 | 0,69049 | 0,29924 | 1,90393 | 0,97627 | 0,73373 | 0,14193 | 1,85193 | 0,91733 | 0,62720 | 0,15364 | 1,69817 | 5,454 | 60,60 |
| 17 | RFO | royal flush optimization (joo) | 0,80989 | 0,74481 | 0,34546 | 1,90016 | 0,95251 | 0,77926 | 0,15185 | 1,88362 | 0,80400 | 0,66427 | 0,19071 | 1,65898 | 5,443 | 60,48 |
| 18 | BOAm | billiards optimization algorithm M | 0,76177 | 0,72421 | 0,25275 | 1,73873 | 0,90890 | 0,81960 | 0,28853 | 2,01703 | 0,83733 | 0,74613 | 0,09763 | 1,68109 | 5,437 | 60,41 |
| 19 | ASO | anarchy society optimization | 0,73070 | 0,73713 | 0,31195 | 1,77978 | 0,99732 | 0,87700 | 0,17619 | 2,05051 | 0,72000 | 0,68773 | 0,18988 | 1,59761 | 5,428 | 60,31 |
| 20 | EOm | extremal optimization_M | 0,76527 | 0,75205 | 0,31908 | 1,83640 | 0,99999 | 0,76426 | 0,12437 | 1,88862 | 0,84133 | 0,64133 | 0,15247 | 1,63513 | 5,360 | 59,56 |
| 21 | ACS | artificial cooperative search | 0,75545 | 0,77162 | 0,31653 | 1,84360 | 1,00000 | 0,80488 | 0,10705 | 1,91193 | 0,76933 | 0,60800 | 0,14157 | 1,51890 | 5,274 | 58,60 |
| 22 | SSG | saplings sowing and growing | 0,75436 | 0,63206 | 0,35935 | 1,74577 | 0,91907 | 0,69694 | 0,19755 | 1,81356 | 0,81867 | 0,60533 | 0,21347 | 1,63747 | 5,197 | 57,74 |
| 23 | AOSm | atomic orbital search M | 0,76184 | 0,68435 | 0,31344 | 1,75963 | 0,90015 | 0,80044 | 0,11501 | 1,81560 | 0,82800 | 0,63280 | 0,15696 | 1,61776 | 5,193 | 57,70 |
| 24 | TSEA | turtle shell evolution algorithm (joo) | 0,95809 | 0,64852 | 0,29571 | 1,90232 | 0,99522 | 0,58104 | 0,10542 | 1,68168 | 0,92133 | 0,52160 | 0,14567 | 1,58860 | 5,173 | 57,48 |
| 25 | DE | flow_direction_algorithm | 0,96398 | 0,62346 | 0,26089 | 1,84833 | 0,98482 | 0,77018 | 0,11459 | 1,86959 | 0,93067 | 0,36213 | 0,11000 | 1,40280 | 5,121 | 56,90 |
| 26 | BIO | blood inheritance optimization (joo) | 0,72580 | 0,66522 | 0,31228 | 1,70330 | 0,99995 | 0,68125 | 0,11540 | 1,79660 | 0,85467 | 0,59333 | 0,15364 | 1,60164 | 5,102 | 56,69 |
| 27 | (PO)ES | (PO) evolution strategies | 0,73972 | 0,58190 | 0,38896 | 1,71058 | 0,91199 | 0,59975 | 0,21262 | 1,72436 | 0,82400 | 0,56240 | 0,23432 | 1,62072 | 5,056 | 56,18 |
| 28 | BO | bonobo optimizer | 0,75555 | 0,64366 | 0,32657 | 1,72578 | 0,94332 | 0,70442 | 0,13999 | 1,78773 | 0,73467 | 0,61440 | 0,16728 | 1,51635 | 5,030 | 55,89 |
| 29 | SRA | successful restaurateur algorithm (joo) | 0,89010 | 0,63359 | 0,29115 | 1,81484 | 0,96634 | 0,55285 | 0,08914 | 1,60833 | 0,89333 | 0,52800 | 0,13911 | 1,56044 | 4,984 | 55,38 |
| 30 | FDAm | flow_direction_algorithm_M | 0,87573 | 0,58806 | 0,27135 | 1,73514 | 0,99997 | 0,64399 | 0,09633 | 1,74029 | 0,84267 | 0,48453 | 0,11888 | 1,44608 | 4,922 | 54,70 |
| 31 | CRO | chemical reaction optimisation | 0,91281 | 0,65681 | 0,29866 | 1,86828 | 0,90513 | 0,56020 | 0,10939 | 1,57472 | 0,82800 | 0,50133 | 0,14149 | 1,47082 | 4,914 | 54,60 |
| 32 | BCOm | bacterial chemotaxis optimization M | 0,82589 | 0,61733 | 0,31584 | 1,75906 | 0,95296 | 0,63718 | 0,11984 | 1,70998 | 0,76533 | 0,51653 | 0,15800 | 1,43986 | 4,909 | 54,54 |
| 33 | DOA | dream optimization algorithm | 0,78522 | 0,78121 | 0,36036 | 1,92679 | 0,61584 | 0,42117 | 0,12254 | 1,15955 | 0,86667 | 0,72587 | 0,21127 | 1,80381 | 4,890 | 54,33 |
| 34 | ABO | african buffalo optimization | 0,92295 | 0,62528 | 0,29885 | 1,84708 | 0,92992 | 0,57468 | 0,09372 | 1,59832 | 0,73333 | 0,51333 | 0,14324 | 1,38990 | 4,835 | 53,72 |
| 35 | BSA | bird swarm algorithm | 0,94432 | 0,67941 | 0,26401 | 1,88774 | 0,91649 | 0,65619 | 0,12054 | 1,69322 | 0,80933 | 0,33547 | 0,10652 | 1,25132 | 4,832 | 53,69 |
| 36 | TSm | tabu search M | 0,87806 | 0,61040 | 0,28993 | 1,77839 | 0,98116 | 0,52165 | 0,08544 | 1,58825 | 0,82667 | 0,49547 | 0,13552 | 1,45766 | 4,824 | 53,60 |
| 37 | BSA | backtracking search algorithm | 0,87128 | 0,53190 | 0,28675 | 1,68993 | 0,92408 | 0,51602 | 0,09153 | 1,53163 | 0,96000 | 0,47253 | 0,13760 | 1,57013 | 4,792 | 53,24 |
| 38 | BEA | bacterial_evolutionary_algorithm | 0,92170 | 0,59615 | 0,29340 | 1,81125 | 0,96906 | 0,44500 | 0,08233 | 1,49639 | 0,90533 | 0,43173 | 0,13676 | 1,47382 | 4,781 | 53,13 |
| 39 | BWOm | beluga_whale_optimization_M | 0,78488 | 0,56872 | 0,29557 | 1,64917 | 0,91370 | 0,61760 | 0,12988 | 1,66118 | 0,81333 | 0,49946 | 0,15004 | 1,46283 | 4,773 | 53,04 |
| 40 | WOAm | whale optimization algorithm M | 0,93893 | 0,59477 | 0,26695 | 1,80065 | 0,98036 | 0,53873 | 0,07112 | 1,59021 | 0,78667 | 0,47600 | 0,11892 | 1,38159 | 4,772 | 53,02 |
| 41 | ACA | andean_condor_algorithm | 0,78444 | 0,53260 | 0,33108 | 1,64812 | 0,79071 | 0,44960 | 0,10685 | 1,34716 | 0,92266 | 0,67733 | 0,17613 | 1,77612 | 4,771 | 53,02 |
| 42 | CSO | competitive swarm optimizer | 0,85151 | 0,60786 | 0,29896 | 1,75833 | 0,84085 | 0,58491 | 0,11974 | 1,54550 | 0,80000 | 0,48560 | 0,14184 | 1,42744 | 4,731 | 52,57 |
| 43 | FBA | fractal-based algorithm | 0,69419 | 0,64267 | 0,28955 | 1,62641 | 0,99812 | 0,54905 | 0,08705 | 1,63422 | 0,76133 | 0,51253 | 0,13689 | 1,41075 | 4,671 | 51,90 |
| 44 | DOAm | dynastic_optimization_algorithm | 0,63202 | 0,58003 | 0,31943 | 1,53148 | 0,76947 | 0,62730 | 0,12425 | 1,52102 | 0,74133 | 0,59520 | 0,16550 | 1,50203 | 4,555 | 50,61 |
| 45 | 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 |
| FDOm | fitness_dependent_optimizer_M | 0,65820 | 0,53236 | 0,29692 | 1,48748 | 0,71106 | 0,39318 | 0,07900 | 1,18324 | 0,49955 | 0,41066 | 0,14908 | 1,05929 | 3,730 | 41,44 | |
| 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 | |
Выводы
Fitness Dependent Optimizer оказался редким случаем, когда разбор алгоритма даёт больше материала, чем сам алгоритм. В основе FDO лежит одна геометрическая операция — случайное радиальное масштабирование относительно глобального лучшего решения. Операция сама по себе не бессмысленна, но реализована так, что агент за итерацию получает единственную степень свободы вне зависимости от размерности задачи. Популяция при этом исследует не пространство поиска, а звезду из нескольких десятков прямых в нём. Дефект не бросается в глаза ни в тексте авторов, ни в их формулах, ни в их тестах — но на сетке нашего стенда проявляется в полную силу.
По результатам канонической версии. 21.82% против 23.89% у чистого случайного перебора на том же бюджете, с преимуществом перебора на семи ячейках из девяти. Триста тридцать три итерации алгоритма приводят к худшему решению, чем однократная оценка десяти тысяч случайных точек. Это, пожалуй, самый жёсткий результат за всё время существования серии, и получен он не подгонкой параметров, а на авторских настройках по умолчанию.
По модификации. Перенос генератора случайного числа внутрь цикла по координатам даёт 39.85% — восемнадцать пунктов прироста при изменении одной строки. Правка не добавляет алгоритму ни новых операторов, ни новых параметров, ни дополнительных вычислений целевой функции: вес приспособленности остаётся скалярным, правила ветвления сохраняются в исходном виде. Это по-прежнему FDO, просто перестающий терять степени свободы на пустом месте.
По заявленным авторами вкладам. Их было три. Вес приспособленности как механизм управления шагом — работает, но в каноническом исполнении задушен лучевой запертостью. Хранение и переиспользование удачного шага — работает, стоит около шести пунктов, однако выполняет функцию, противоположную заявленной: это не ускоритель сходимости, а тормоз схлопывания популяции. Единственный настраиваемый параметр wf — в каноническом алгоритме не влияет ни на что, а после исправления оживает и приобретает смысл, обратный описанию авторов.
Отдельно отмечу приём, которым получена отсечка случайного поиска. Строка RND в рейтинговой таблице у нас есть давно, но та же нижняя граница снимается и без неё, прямо в прогоне исследуемого алгоритма: достаточно приравнять размер популяции к бюджету вычислений, чтобы прогон выродился в однократную оценку случайных точек. Приём не требует усилий: не нужна отдельная реализация и не нужна правка кода. Он работает в любом окружении, включая случаи, когда под рукой нет ни стенда, ни таблицы. А отсечка, им полученная, отвечает на вопрос, который стоит задавать каждому новому алгоритму: приносят ли его итерации пользу вообще.
Рисунок 3. Цветовая градация алгоритмов по соответствующим тестам
Рисунок 4. Гистограмма результатов тестирования алгоритмов (по шкале от 0 до 100: чем больше, тем лучше, где 100 — максимально возможный теоретический результат). В архиве — скрипт для расчёта рейтинговой таблицы
Плюсы и минусы алгоритма FDOm
Плюсы:
- предельная простота: два параметра, отсутствие адаптивных коэффициентов и расписаний;
- дёшев по вычислениям — на агента приходится один скаляр веса и по одному случайному числу на координату, без накопительных сумм по популяции;
Минусы:
- слабая точность на гладких функциях высокой размерности — характерная беда всех схем с единственным аттрактором;
- формула веса приспособленности корректна только для неотрицательных значений целевой функции; при знакопеременной функции отношение выходит за пределы [0, 1] и логика ветвления ломается;
- вырожденная ветвь привязана к началу координат, а не к области поиска — на результатах это, как выяснилось, не сказывается, но конструктивно неверно;
- отсутствие персонального лучшего решения и какого-либо обмена информацией между агентами ограничивает потолок алгоритма.
К статье прикреплён архив с актуальными версиями кодов алгоритмов. Автор статьи не несёт ответственности за абсолютную точность в описании канонических алгоритмов, во многие из них внесены изменения для улучшения поисковых возможностей. Выводы и суждения, представленные в статьях, основываются на результатах проведённых экспериментов.
Программы, используемые в статье
| # | Имя | Тип | Описание |
|---|---|---|---|
| 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_FDOm.mq5 | Скрипт | Испытательный стенд для FDOm |
Предупреждение: все права на данные материалы принадлежат MetaQuotes Ltd. Полная или частичная перепечатка запрещена.
Данная статья написана пользователем сайта и отражает его личную точку зрения. Компания MetaQuotes Ltd не несет ответственности за достоверность представленной информации, а также за возможные последствия использования описанных решений, стратегий или рекомендаций.
Моделирование рынка: В единстве — сила (I)
Нейросети в трейдинге: Адаптация прогноза при смене рыночного режима (OMPB)
От начального до среднего уровня: Перегрузка операторов (III)
Пайплайны Codex: от Python к MQL5 для выбора индикаторов — анализ ETF FXI за несколько кварталов
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Вы принимаете политику сайта и условия использования