Алгоритм Стрекозы — Dragonfly Algorithm (DA)
77
0
Содержание
Введение
Рассмотрим еще один из современных метаэвристических популяционных методов, алгоритм стрекозы, для целей наших оптимизационных задач. Стрекозы — одни из самых эффектных летающих насекомых, существующих на планете почти 300 миллионов лет. Их уникальная способность к маневрированию в воздухе — зависание, мгновенная смена направления, полёт в шести степенях свободы — давно привлекала внимание исследователей. Однако для области метаэвристической оптимизации особый интерес представляет не аэродинамика отдельной стрекозы, а коллективное поведение роёв.
В 2015 году Сейедали Мирджалили (Seyedali Mirjalili) предложил алгоритм Dragonfly Algorithm (DA), который моделирует два типа роевого поведения стрекоз: статическое и динамическое. Статический рой формируется при охоте — стрекозы собираются в небольшие группы, перемещаясь над ограниченной территорией в поисках добычи. Динамический рой возникает при миграции — большие группы движутся в одном направлении на значительные расстояния. Эти два режима естественным образом соответствуют двум фундаментальным фазам оптимизации: exploitation (эксплуатация найденных решений) и exploration (исследование нового пространства).
Реализация алгоритма
Представьте себе тёплый летний вечер у пруда. Над водой кружат десятки стрекоз. Если присмотреться, можно заметить закономерность: стрекозы не летают хаотично. Они держатся группой, но не сталкиваются, летят примерно в одном направлении, но каждая — своим маршрутом. Если одна находит скопление мошкары — остальные подтягиваются, если появляется птица — вся группа рассеивается. Алгоритм моделирует рой стрекоз, где каждая стрекоза — это потенциальное решение задачи, а качество решения — это количество пойманной добычи.
Пять простых правил поведения. Каждая стрекоза в алгоритме подчиняется пяти правилам. Все они интуитивно понятны, потому что мы наблюдаем подобное поведение и в обычной жизни — в толпе людей, в стаях птиц, в потоке машин.
1. Не толкайся (Separation). Если соседи подлетели слишком близко — отодвинься. Это правило предотвращает скопление всех стрекоз в одной точке. Например, вы стоите в лифте с другими людьми, никто не договаривался, но все инстинктивно распределились по кабине на примерно равных расстояниях. В терминах оптимизации: если все агенты соберутся в одной точке — алгоритм перестанет исследовать пространство и застрянет. Separation защищает от этого.
2. Лети как все (Alignment). Посмотри, куда летят соседи, и подстрой свою скорость и направление. Это правило обеспечивает координированное движение группы. Представьте себе, что вы идёте по тротуару в потоке людей: даже не задумываясь, вы идёте примерно с той же скоростью и в том же направлении, что и окружающие. В оптимизации: если одна стрекоза нашла перспективное направление — её соседи начинают двигаться туда же, усиливая поиск в этой области.
3. Держись стаи (Cohesion). Стремись к центру группы соседей, не отставай и не улетай далеко в одиночку. Представьте группу туристов в незнакомом городе: каждый хочет осмотреться, но никто не отходит слишком далеко от группы — чтобы не потеряться. Для оптимизации: Cohesion не даёт агентам бесконтрольно разлетаться по пространству поиска, удерживая их вместе для совместного исследования перспективных зон.
4. Лети к еде (Food Attraction). Если рядом обнаружен источник пищи — двигайся к нему. В алгоритме «еда» — это лучшее решение, найденное за всё время. Например, вы гуляете по торговому центру и чувствуете запах свежей выпечки. Ноги сами несут в ту сторону, поэтому в рамках оптимизации лучшее найденное решение притягивает агентов, концентрируя поиск вокруг наиболее перспективной точки.
5. Беги от врага (Enemy Distraction). Если рядом обнаружен хищник — удаляйся от него. Опасность — это худшее из найденных решений. Если в городе вы идёте по незнакомому переулку и видите предупреждающий знак, вы развернётесь и пойдёте другой дорогой. Отталкивание от худших решений помогает не тратить время на бесперспективные области пространства.
Как эти правила работают вместе. На каждом шаге алгоритма каждая стрекоза вычисляет все пять факторов и комбинирует их в один вектор движения: необходимо отодвинуться от соседей (separation), полететь туда, куда они летят (alignment), но не отрываться от группы (cohesion), при этом держать курс на еду (food) и подальше от хищника (enemy). Результирующее направление — это компромисс между всеми пятью стремлениями. К нему добавляется инерция — стрекоза не может мгновенно сменить направление, поэтому часть предыдущей скорости сохраняется.
Вот простой числовой пример. Допустим, стрекоза находится в точке X = 5 по одной из координат. Пять факторов дают следующие значения:
- Separation = +2 (соседи слева, нужно отодвинуться вправо)
- Alignment = −1 (соседи в среднем летят влево)
- Cohesion = −3 (центр стаи левее)
- Food = +4 (лучшее решение правее)
- Enemy = +1 (худшее решение левее, бежим вправо)
С весами s=0.05, a=0.05, c=0.05, f=1.2, e=0.05 и инерцией w·ΔX = 0.3: ΔX = 0.05·2 + 0.05·(−1) + 0.05·(−3) + 1.2·4 + 0.05·1 + 0.3 = 5.15. Новая позиция: X = 5 + 5.15 = 10.15. Стрекоза сильно сдвинулась вправо — в основном из-за притяжения к еде (4 × 1.2 = 4.8), которое доминирует. Остальные факторы внесли минимальные коррекции.
Одинокая стрекоза и полёт Леви. Иногда стрекоза оказывается в изоляции — у неё нет соседей в радиусе обзора, и еда тоже далеко. В этом случае пять правил бесполезны: не от кого отталкиваться, не к кому присоединяться, нечего преследовать. Что делает одинокая стрекоза? Она совершает полёт Леви — особый тип случайного блуждания, названный в честь французского математика Поля Леви. В чём его отличие от обычного случайного поиска? Обычный случайный шаг — это как бросание монетки: шаг вперёд или назад на одинаковое расстояние. Полёт Леви — это множество маленьких шагов с редкими большими прыжками.
Как алгоритм взрослеет. У алгоритма присутствует ключевая особенность: его поведение меняется со временем. В начале работы стрекозы ведут себя как исследователи. К концу — как группа охотников, которые уже нашли цель и сужают кольцо. Это достигается через три адаптивных параметра:
Радиус обзора (r) — в начале маленький. Стрекозы видят мало соседей, часто оказываются в изоляции и совершают полёты Леви — исследуют всё пространство. К концу радиус вырастает до огромных значений — все стрекозы видят друг друга и действуют как единый организм, точно настраивая позицию. Весовые коэффициенты (s, a, c, e) — убывают от ненулевых значений до нуля за первую половину итераций. Во второй половине остаётся только притяжение к еде (f).
Инерция (w) — убывает от 0.9 к 0.4. Высокая инерция в начале означает, что стрекоза долго набирает разгон и не может быстро развернуться — это помогает исследовать большие расстояния. Низкая инерция к концу позволяет делать точные маневры вблизи оптимума.
Итого: один шаг алгоритма. Соберём всё вместе. На каждой итерации алгоритм выполняет следующее:
Для каждой стрекозы:
- Посмотри вокруг — найди соседей в радиусе r.
- Вычисли пять факторов: separation, alignment, cohesion, food, enemy.
- Если рядом есть еда и достаточно соседей — выполни полное обновление, комбинируя все пять факторов с адаптивными весами.
- Если еды рядом нет, но соседи есть — двигайся по роевым правилам (separation + alignment + cohesion).
- Если ты в изоляции — совершай полёт Леви.
Ограничь позицию границами пространства поиска. После того как все стрекозы переместились:
- Вычисли качество (fitness) каждого решения.
- Обнови "еду" (лучшее решение) и "опасность" (худшее решение).
Повторяй до исчерпания итераций. Лучшее найденное решение за все итерации — это результат работы алгоритма.
Еще раз повторим поведение каждой стрекозы в рое:
- Separation (разделение) — стрекозы избегают столкновений с соседями, отклоняясь от слишком близких особей. В терминах оптимизации это предотвращает скопление агентов в одной точке и поддерживает разнообразие популяции.
- Alignment (выравнивание) — стрекозы согласовывают свою скорость и направление полёта с соседями. Это обеспечивает координированное движение группы в перспективных направлениях.
- Cohesion (сплочение) — стрекозы стремятся к центру масс своих соседей. Этот механизм притягивает разрозненных агентов обратно к группе, не давая им разлетаться бесконтрольно.
- Attraction to food (притяжение к еде) — стрекозы движутся в направлении источника пищи, что соответствует притяжению агентов к лучшему найденному решению.
- Distraction from enemy (избежание врага) — стрекозы удаляются от хищников, что в модели означает отталкивание от худшего известного решения.
Математическая модель. Для каждой стрекозы i с позицией X и вектором скорости DeltaX вычисляются пять корректирующих векторов на основе соседей в радиусе r:
Separation (Eq. 1): S = -SUM(X - Xj)
Alignment (Eq. 2): A = SUM(Vj) / N
Cohesion (Eq. 3): C = SUM(Xj) / N - X
Food (Eq. 4): F = X+ - X
Enemy (Eq. 5): E = X- + X; где N — число соседей, Vj — скорость j-го соседа, X+ — позиция лучшего решения (Food), X- — позиция худшего решения (Enemy).
Обновление вектора скорости объединяет все пять факторов с адаптивными весами (Eq. 6):
DeltaX(t+1) = s*S + a*A + c*C + f*F + e*E + w*DeltaX(t), а новая позиция вычисляется как (Eq. 7):
X(t+1) = X(t) + DeltaX(t+1)
Когда стрекоза оказывается в изоляции (менее двух соседей в радиусе r и Food вне досягаемости), она совершает случайный полёт Леви (Eq. 8) — случайное блуждание с тяжёлыми хвостами, позволяющее совершать как малые шаги, так и редкие большие прыжки:
X(t+1) = X(t) + Levy(d) * X(t)
Значение шага Леви вычисляется по алгоритму Mantegna (Eq. 9):
Levy = 0.01 * (r1 * sigma) / |r2|^(1/beta)
где r1 ~ N(0, sigma^2), r2 ~ N(0, 1), beta = 1.5, а sigma определяется через Гамма-функцию (Eq. 10).
Адаптивный механизм. Ключевая особенность DA — плавный переход от "exploration" к "exploitation" через адаптивные параметры:
Радиус соседства r растёт с каждой итерацией. В начале оптимизации стрекозы видят мало соседей и чаще совершают полёты Леви (exploration). К концу — радиус покрывает большую часть пространства, все агенты координируются как единая стая (exploitation).
Весовые коэффициенты (s, a, c, e) убывают от максимальных значений к нулю за первую половину итераций. Во второй половине остаётся только притяжение к Food (f), что концентрирует поиск вокруг лучшего решения.
Инерция "w" убывает от 0.9 к 0.4, плавно уменьшая влияние предыдущей скорости и обеспечивая точную настройку позиции в конце оптимизации. Этот механизм не требует настройки пользователем — единственный внешний параметр алгоритма это размер популяции.
Иллюстрация содержит четыре секции:
1. Five Behavioral Patterns — визуальные схемы всех пяти факторов (Separation, Alignment, Cohesion, Food, Enemy) с иконками стрекоз, стрелками направлений и формулами.
2. Position Update Decision Logic — блок-схема выбора режима движения: Food в радиусе → Full Update (Eq. 6), иначе проверка соседей >1 → Swarm Update или Lévy Flight (Eq. 8). Все три пути сходятся к финальному Clamp + Discretize.
3. Adaptive Parameter Dynamics — графики трёх ключевых параметров на временной шкале: r (растёт), w (убывает 0.9→0.4), my_c (убывает 0.1→0 за первую половину). Показан переход Exploration → Exploitation.
4. Lévy Flight Mechanism — визуализация траектории полёта Леви (много малых шагов + редкие длинные прыжки) и формулы Mantegna с параметрами.
Можем перейти непосредственно к реализации алгоритма.
Класс "C_AO_DA_Dragonfly" реализует алгоритм оптимизации Dragonfly Algorithm, вдохновлённый роевым поведением стрекоз в природе. Класс наследуется от базового класса "C_AO", предоставляющего общую инфраструктуру для всех популяционных алгоритмов оптимизации: массив агентов, границы пространства поиска, хранение лучшего и худшего найденных решений, утилиты для генерации случайных чисел и дискретизации координат.
Внутри класса хранятся скорости всех агентов в виде плоского массива "DeltaX", где каждому агенту соответствует набор компонент скорости по всем координатам. Доступ к элементам этого массива осуществляется через вспомогательные методы "GetDX" и "SetDX", вычисляющие линейный индекс по номеру агента и номеру координаты.
Алгоритм оперирует двумя ключевыми точками в пространстве поиска: "Food" и "Enemy", первый из которых хранит позицию и фитнес лучшего найденного решения за всё время работы и служит аттрактором — агенты, оказавшиеся достаточно близко к "Food", испытывают притяжение к этой точке. "Enemy" хранит позицию и фитнес худшего найденного решения и служит репеллентом — агенты вблизи "Enemy" отталкиваются от него.
Для управления адаптивными параметрами класс хранит общее число эпох оптимизации и счётчик текущей эпохи. Их отношение определяет значения радиуса соседства, инерции и весовых коэффициентов на каждом шаге. Также предвычисляются ширина диапазона по каждой координате и максимально допустимая скорость, равная одной сотой этой ширины. Единственный настраиваемый извне параметр — размер популяции. Все остальные коэффициенты алгоритма вычисляются автоматически.
Метод "SetParams" считывает значение размера популяции из внешнего массива "params" и записывает его во внутреннее поле класса. Вызывается после того, как тестовый скрипт записал нужные значения параметров. В данном алгоритме параметр только один, поэтому метод тривиален, но его наличие обеспечивает единообразие интерфейса со всеми остальными алгоритмами.
//———————————————————————————————————————————————————————————————————— class C_AO_DA_Dragonfly : public C_AO { public: //---------------------------------------------------------- ~C_AO_DA_Dragonfly () { } C_AO_DA_Dragonfly () { ao_name = "DA(Dragonfly)"; ao_desc = "Dragonfly Algorithm"; ao_link = "https://www.mql5.com/ru/articles/21310"; popSize = 50; ArrayResize (params, 1); params [0].name = "popSize"; params [0].val = popSize; } void SetParams () { popSize = (int)params [0].val; } bool Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0); void Moving (); void Revision (); private: //--------------------------------------------------------- // Velocities (DeltaX) double DeltaX []; // [popSize * coords] flat array // Food (best) and Enemy (worst) double Food_pos []; double Food_f; double Enemy_pos []; double Enemy_f; // Iteration tracking int epochs; int epochNow; // Helpers double Delta_max []; // max velocity per dimension double r_base []; // (ub-lb) per dimension double LevyStep (); double RandN (); // normal distribution N(0,1) via Box-Muller // Flat array access helpers double GetDX (int i, int c) { return DeltaX [i * coords + c]; } void SetDX (int i, int c, double v) { DeltaX [i * coords + c] = v; } }; //————————————————————————————————————————————————————————————————————
Метод "Init" выполняет полную инициализацию алгоритма перед запуском цикла оптимизации. Принимает массивы минимальных и максимальных границ пространства поиска, шаги дискретизации по каждой координате и общее число эпох.
В первую очередь вызывается метод "StandardInit" родительского класса, который сбрасывает генератор случайных чисел, устанавливает фитнес лучшего решения в минус бесконечность, выделяет память под массивы агентов, границ и лучших координат. При ошибке инициализация прерывается. Далее сохраняется общее число эпох — оно необходимо для вычисления адаптивных параметров в "Moving". Если переданное значение нулевое или отрицательное, используется значение по умолчанию — тысяча. Счётчик текущей эпохи обнуляется.
Выделяется память под плоский массив скоростей. Для каждой координаты предвычисляется ширина диапазона — разность верхней и нижней границы — и максимально допустимая скорость, равная одной сотой этой ширины. Ограничение скорости предотвращает чрезмерно большие перемещения на одном шаге.
Позиция "Food" инициализируется с фитнесом минус бесконечность, позиция "Enemy" — с фитнесом плюс бесконечность. Это гарантирует, что первый же вычисленный агент обновит обе позиции. Начальные позиции всех агентов генерируются равномерно случайно в пределах заданных границ с последующей дискретизацией по шагу. Начальные скорости также генерируются случайно в тех же диапазонах.
//———————————————————————————————————————————————————————————————————— bool C_AO_DA_Dragonfly::Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0) { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //------------------------------------------------------------------ epochs = epochsP > 0 ? epochsP : 1000; epochNow = 0; //--- allocate DeltaX ArrayResize (DeltaX, popSize * coords); //--- Delta_max and r_base ArrayResize (Delta_max, coords); ArrayResize (r_base, coords); for (int c = 0; c < coords; c++) { r_base [c] = rangeMax [c] - rangeMin [c]; Delta_max [c] = r_base [c] / 100.0; } //--- Food (best) and Enemy (worst) — for maximization ArrayResize (Food_pos, coords); ArrayResize (Enemy_pos, coords); Food_f = -DBL_MAX; Enemy_f = DBL_MAX; //--- Initialize positions randomly, DeltaX randomly for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { a [i].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]); a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); SetDX (i, c, u.RNDfromCI (rangeMin [c], rangeMax [c])); } } return true; } //————————————————————————————————————————————————————————————————————
Метод "Moving" — это центральная часть алгоритма, выполняющая перемещение всех агентов на текущей эпохе. Вызывается один раз за итерацию перед вычислением фитнес-функции. После его выполнения внешний код рассчитывает значения фитнеса для каждого агента и передаёт управление методу "Revision".
В начале метода инкрементируется счётчик эпох и вычисляются адаптивные параметры, управляющие балансом между исследованием пространства и эксплуатацией найденных решений.
Адаптивный радиус соседства вычисляется для каждой координаты как четверть ширины диапазона плюс удвоенная ширина, умноженная на долю пройденных эпох. В начале оптимизации радиус мал — агенты видят мало соседей, часто оказываются в изоляции и совершают полёты Леви, исследуя всё пространство. К концу оптимизации радиус вырастает настолько, что охватывает практически всё пространство поиска — все агенты видят друг друга и действуют как координированный рой, точно настраивая позицию вблизи оптимума.
Инерция убывает линейно от 0.9 к 0.4 на протяжении всех эпох. Высокая инерция в начале означает, что агент сохраняет значительную часть предыдущей скорости и движется длинными прыжками, что способствует быстрому преодолению больших расстояний. Низкая инерция к концу позволяет совершать короткие точные перемещения для уточнения позиции.
Коэффициент "my_c" убывает линейно от 0.1 до нуля за первую половину эпох и остаётся нулевым во второй половине, он масштабирует веса разделения, выравнивания, сплочения и врага. Когда "my_c" достигает нуля, все эти веса обнуляются и на агентов действует только притяжение к лучшему решению — алгоритм полностью переключается на эксплуатацию.
Весовые коэффициенты пяти факторов поведения вычисляются один раз за эпоху. Коэффициенты разделения, выравнивания и сплочения равны произведению двух, случайного числа от нуля до единицы и "my_c". Коэффициент опасности равен просто "my_c". Коэффициент притяжения к еде равен произведению двух и случайного числа — он не зависит от "my_c" и остаётся активным на протяжении всей оптимизации.
Далее для каждого агента выполняется пятишаговая процедура. На первом шаге определяются соседи текущего агента. Для каждого другого агента проверяется, не превышает ли расстояние до него адаптивный радиус по каждой из координат. Агент считается соседом, только если расстояние по всем координатам одновременно укладывается в соответствующие компоненты радиуса. Параллельно с подсчётом числа соседей накапливаются три набора сумм: суммы скоростей соседей, суммы их позиций и суммы разностей позиций соседей и текущего агента. Эти суммы используются для вычисления факторов поведения без повторного обхода массива.
На втором шаге вычисляются пять поведенческих факторов. Разделение равно инвертированной сумме разностей позиций соседей и текущего агента — это формирует вектор, направленный от скопления соседей, предотвращая столкновения. В данной реализации разделение активируется при наличии более четырёх соседей; при меньшем числе обнуляется. Выравнивание равно средней скорости всех соседей и заставляет агента лететь в том же направлении, что и остальная группа; при числе соседей менее двух используется собственная скорость агента. Сплочение равно разности средней позиции соседей и текущей позиции агента — это вектор, направленный к центру масс группы; при недостатке соседей обнуляется.
Притяжение к еде равно разности позиции "Food" и позиции агента, но вычисляется только если "Food" находится в пределах адаптивного радиуса по всем координатам; в противном случае обнуляется. Отталкивание от врага вычисляется как сумма позиции "Enemy" и позиции агента и также активируется только при нахождении "Enemy" в пределах радиуса.
На третьем шаге выполняется заворачивание границ с ресетом скорости. Если позиция агента по какой-либо координате вышла за верхнюю границу, она переносится на нижнюю границу, и наоборот. При таком переносе соответствующая компонента скорости сбрасывается в случайное значение от нуля до единицы.
На четвёртом шаге обновляются скорость и позиция агента. Режим обновления определяется двумя условиями: находится ли "Food" в пределах адаптивного радиуса и имеет ли агент более одного соседа. Если "Food" в пределах радиуса, выполняется полное обновление: новая скорость равна взвешенной сумме всех пяти факторов плюс инерционная часть предыдущей скорости. Это основная формула алгоритма, объединяющая все поведенческие сигналы в одно результирующее перемещение.
Если "Food" вне радиуса, но соседей более одного, выполняется роевое обновление без явного притяжения к еде: скорость формируется из инерции и случайно взвешенных факторов выравнивания, сплочения и разделения. Агент координируется с ближайшей группой, пока не окажется достаточно близко к "Food". Если "Food" вне радиуса и соседей не более одного, агент совершает полёт Леви: новая позиция равна текущей плюс произведение шага Леви на текущую позицию, а скорость обнуляется. Этот режим обеспечивает стохастическое исследование пространства при изоляции агента от роя.
Во всех трёх режимах скорость ограничивается по модулю значением "Delta_max" для каждой координаты, предотвращая чрезмерно большие перемещения.
На пятом шаге позиция жёстко ограничивается границами пространства поиска — значения, вышедшие за максимум, обрезаются до максимума, вышедшие за минимум — до минимума — и дискретизируется шагом через метод "SeInDiSp", финальная гарантия валидности координат перед вычислением фитнес-функции.
//———————————————————————————————————————————————————————————————————— void C_AO_DA_Dragonfly::Moving () { epochNow++; double iter_ratio = (double)epochNow / (double)epochs; //--- Adaptive neighbourhood radius: r = (ub-lb)/4 + (ub-lb)*(iter/Max_iter)*2 double r []; ArrayResize (r, coords); for (int c = 0; c < coords; c++) { r [c] = r_base [c] / 4.0 + r_base [c] * iter_ratio * 2.0; } //--- Inertia weight: w = 0.9 - iter*((0.9-0.4)/Max_iter) double w = 0.9 - epochNow * ((0.9 - 0.4) / (double)epochs); //--- Adaptive coefficient my_c = 0.1 - iter*(0.1/(Max_iter/2)) double my_c = 0.1 - epochNow * (0.1 / ((double)epochs / 2.0)); if (my_c < 0.0) my_c = 0.0; //--- Weights (computed once per epoch as in MATLAB) double s_w = 2.0 * u.RNDfromCI (0.0, 1.0) * my_c; // Separation weight double a_w = 2.0 * u.RNDfromCI (0.0, 1.0) * my_c; // Alignment weight double c_w = 2.0 * u.RNDfromCI (0.0, 1.0) * my_c; // Cohesion weight double f_w = 2.0 * u.RNDfromCI (0.0, 1.0); // Food attraction weight double e_w = my_c; // Enemy distraction weight //--- For each dragonfly for (int i = 0; i < popSize; i++) { //================================================================ // 1. Find neighbours within radius r //================================================================ int nCount = 0; double sumNDX []; ArrayResize (sumNDX, coords); ArrayInitialize (sumNDX, 0.0); double sumNX []; ArrayResize (sumNX, coords); ArrayInitialize (sumNX, 0.0); double sepV []; ArrayResize (sepV, coords); ArrayInitialize (sepV, 0.0); for (int j = 0; j < popSize; j++) { if (j == i) continue; // Per-dimension distance check: all(dist <= r) bool inNeighbour = true; for (int c = 0; c < coords; c++) { if (MathAbs (a [i].c [c] - a [j].c [c]) > r [c]) { inNeighbour = false; break; } } if (inNeighbour) { nCount++; for (int c = 0; c < coords; c++) { sumNDX [c] += GetDX (j, c); sumNX [c] += a [j].c [c]; sepV [c] += (a [j].c [c] - a [i].c [c]); } } } //================================================================ // 2. Compute swarm behaviours (Eq. 3.1 – 3.5) //================================================================ //--- Separation S (Eq. 3.1): S = -Σ(Xj - Xi) // requires neighbours_no > 1 double S []; ArrayResize (S, coords); if (nCount > 4) { for (int c = 0; c < coords; c++) S [c] = -sepV [c]; } else { ArrayInitialize (S, 0.0); } //--- Alignment A (Eq. 3.2): A = Σ Vj / N // If no neighbours: A = own DeltaX double A []; ArrayResize (A, coords); if (nCount > 1) { for (int c = 0; c < coords; c++) A [c] = sumNDX [c] / (double)nCount; } else { for (int c = 0; c < coords; c++) A [c] = GetDX (i, c); } //--- Cohesion C (Eq. 3.3): C = Σ Xj / N - Xi // If no neighbours: C = 0 double C []; ArrayResize (C, coords); if (nCount > 1) { for (int c = 0; c < coords; c++) C [c] = sumNX [c] / (double)nCount - a [i].c [c]; } else { for (int c = 0; c < coords; c++) C [c] = 0.0; } //--- Food attraction F (Eq. 3.4): F = Food_pos - Xi (if food within r) double F []; ArrayResize (F, coords); ArrayInitialize (F, 0.0); bool foodInRange = false; if (Food_f > -DBL_MAX) { foodInRange = true; for (int c = 0; c < coords; c++) { if (MathAbs (a [i].c [c] - Food_pos [c]) > r [c]) { foodInRange = false; break; } } if (foodInRange) { for (int c = 0; c < coords; c++) F [c] = Food_pos [c] - a [i].c [c]; } } //--- Enemy distraction E (Eq. 3.5) // Enemy = Enemy_pos + Xi (if enemy within r) double E []; ArrayResize (E, coords); ArrayInitialize (E, 0.0); if (Enemy_f < DBL_MAX) { bool enemyInRange = true; for (int c = 0; c < coords; c++) { if (MathAbs (a [i].c [c] - Enemy_pos [c]) > r [c]) { enemyInRange = false; break; } } if (enemyInRange) { for (int c = 0; c < coords; c++) E [c] = Enemy_pos [c] + a [i].c [c]; } } //================================================================ // 3. Boundary wrap-around with velocity reset // AFTER S/A/C/F/E computation, BEFORE velocity/position update //================================================================ for (int c = 0; c < coords; c++) { if (a [i].c [c] > rangeMax [c]) { a [i].c [c] = rangeMin [c]; SetDX (i, c, u.RNDfromCI (0.0, 1.0)); } if (a [i].c [c] < rangeMin [c]) { a [i].c [c] = rangeMax [c]; SetDX (i, c, u.RNDfromCI (0.0, 1.0)); } } //================================================================ // 4. Update velocity and position //================================================================ if (!foodInRange) { // Food NOT in range if (nCount > 1) // neighbours_no > 1 { // Swarm behaviour: use S, A, C with inertia for (int c = 0; c < coords; c++) { double dx = w * GetDX (i, c) + u.RNDfromCI (0.0, 1.0) * A [c] + u.RNDfromCI (0.0, 1.0) * C [c] + u.RNDfromCI (0.0, 1.0) * S [c]; if (dx > Delta_max [c]) dx = Delta_max [c]; if (dx < -Delta_max [c]) dx = -Delta_max [c]; SetDX (i, c, dx); a [i].c [c] += dx; } } else { // Levy flight (Eq. 3.8): X = X + Levy(d) * X for (int c = 0; c < coords; c++) { a [i].c [c] += LevyStep () * a [i].c [c]; SetDX (i, c, 0.0); } } } else { // Food IS in range — full update (Eq. 3.6) // ΔX(t+1) = (s·S + a·A + c·C + f·F + e·E) + w·ΔX(t) for (int c = 0; c < coords; c++) { double dx = (s_w * S [c] + a_w * A [c] + c_w * C [c] + f_w * F [c] + e_w * E [c]) + w * GetDX (i, c); if (dx > Delta_max [c]) dx = Delta_max [c]; if (dx < -Delta_max [c]) dx = -Delta_max [c]; SetDX (i, c, dx); a [i].c [c] += dx; } } //================================================================ // 5. Post-update clamp to bounds and discretize // X = X.*(~(Flag4ub+Flag4lb)) + ub.*Flag4ub + lb.*Flag4lb //================================================================ for (int c = 0; c < coords; c++) { if (a [i].c [c] > rangeMax [c]) a [i].c [c] = rangeMax [c]; if (a [i].c [c] < rangeMin [c]) a [i].c [c] = rangeMin [c]; a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } } //————————————————————————————————————————————————————————————————————
Метод "Revision" выполняет пересмотр результатов после того, как внешний код вычислил значения фитнеса для всех агентов. Вызывается один раз за эпоху и проходит по всей популяции, выполняя три обновления.
Первое обновление касается глобального лучшего решения. Если фитнес текущего агента превышает фитнес лучшего решения "fB" родительского класса, записывается новый фитнес и копируются координаты в массив "cB". Эти поля используются тестовым стендом для отслеживания прогресса оптимизации и итоговой оценки качества.
Второе обновление касается внутреннего аттрактора "Food". Если фитнес агента превышает текущий "Food_f", обновляются фитнес и позиция "Food". Хотя "Food" и "fB" на практике содержат одно и то же значение, они разделены логически: "fB" и "cB" — это интерфейс с внешним миром, а "Food" — внутренняя механика алгоритма, используемая в "Moving" для вычисления вектора притяжения.
Третье обновление касается внутреннего репеллента "Enemy". Перед обновлением проверяется, находится ли агент в пределах границ пространства поиска по всем координатам. Если агент в пределах границ и его фитнес ниже текущего "Enemy_f", обновляются фитнес и позиция "Enemy". Проверка границ предотвращает назначение "Enemy" в невалидных точках, которые могли бы генерировать некорректные векторы отталкивания.
//———————————————————————————————————————————————————————————————————— void C_AO_DA_Dragonfly::Revision () { for (int i = 0; i < popSize; i++) { //--- Update global best (Food in maximization) if (a [i].f > fB) { fB = a [i].f; ArrayCopy (cB, a [i].c, 0, 0, coords); } if (a [i].f > Food_f) { Food_f = a [i].f; ArrayCopy (Food_pos, a [i].c, 0, 0, coords); } //--- Update global worst (Enemy in maximization) // Only if within bounds bool inBounds = true; for (int c = 0; c < coords; c++) { if (a [i].c [c] > rangeMax [c] || a [i].c [c] < rangeMin [c]) { inBounds = false; break; } } if (inBounds && a [i].f < Enemy_f) { Enemy_f = a [i].f; ArrayCopy (Enemy_pos, a [i].c, 0, 0, coords); } } } //————————————————————————————————————————————————————————————————————
Метод "RandN" генерирует случайные числа с нормальным распределением N(0, 1) по методу преобразования Бокса-Мюллера. Берутся два независимых равномерно распределённых числа на интервале от нуля до единицы, и из них вычисляется одно нормально распределённое значение: корень квадратный из минус двух натуральных логарифмов первого числа, умноженный на косинус произведения двух пи и второго числа.
Этот метод необходим для корректной реализации полёта Леви. В формуле Mantegna величины "r1" и "r2" должны иметь нормальное распределение. Использование равномерного распределения вместо нормального искажает характер тяжёлых хвостов распределения Леви — уменьшается вероятность длинных прыжков, что снижает эффективность исследования пространства и по сути превращает полёт Леви в обычное случайное блуждание.
Для защиты от вычисления логарифма нуля первое равномерное число ограничивается снизу малой величиной.
//———————————————————————————————————————————————————————————————————— // Normal distribution N(0,1) via Box-Muller transform double C_AO_DA_Dragonfly::RandN () { double u1 = u.RNDfromCI (0.0, 1.0); double u2 = u.RNDfromCI (0.0, 1.0); // Avoid log(0) if (u1 < 1e-10) u1 = 1e-10; return MathSqrt (-2.0 * MathLog (u1)) * MathCos (2.0 * M_PI * u2); } //————————————————————————————————————————————————————————————————————
Метод "LevyStep" вычисляет один скалярный шаг полёта Леви по алгоритму Mantegna. Полёт Леви — это случайное блуждание, в котором длины шагов подчиняются степенному закону: подавляющее большинство шагов малы, но изредка случаются очень длинные прыжки. Такой характер блуждания математически доказанно оптимален для поиска разреженно распределённых целей и применяется во многих метаэвристических алгоритмах для фазы исследования пространства.
Шаг вычисляется как произведение масштабирующего коэффициента 0.01 и частного: в числителе — нормально распределённая величина, умноженная на предвычисленную константу "sigma", в знаменателе — абсолютное значение другой нормально распределённой величины, возведённое в степень, обратную параметру стабильности "beta".
Константа "sigma" предвычислена по формуле через Гамма-функцию для "beta" равного 1.5 и составляет приблизительно 0.6966. Множитель 0.01 обеспечивает умеренную амплитуду шагов, не допуская чрезмерно больших выбросов. Знаменатель защищён от деления на ноль ограничением снизу малой величиной.
Возвращаемый скалярный шаг используется в методе "Moving": умножается на текущую позицию агента и прибавляется к ней, формируя новую позицию при полёте Леви.
//———————————————————————————————————————————————————————————————————— // Levy flight step — Mantegna's algorithm (Eq. 9, 10) // Levy(x) = 0.01 * (r1 * sigma) / |r2|^(1/beta) // where r1 ~ N(0, sigma^2), r2 ~ N(0, 1), beta = 1.5 // sigma = (Gamma(1+beta)*sin(pi*beta/2) / (Gamma((1+beta)/2)*beta*2^((beta-1)/2)))^(1/beta) double C_AO_DA_Dragonfly::LevyStep () { double beta = 1.5; // For beta = 1.5: // Gamma(2.5) = 1.329340 // sin(3*pi/4) = 0.707107 // Gamma(1.25) = 0.906402 // 1.5 * 2^0.25 = 1.783811 // sigma = (1.329340 * 0.707107 / 1.616873)^(1/1.5) ≈ 0.6966 double sigma = 0.6966; double u_val = RandN () * sigma; // r1 ~ N(0, sigma^2) double v_val = MathAbs (RandN ()); // |r2|, r2 ~ N(0, 1) if (v_val < 1e-10) v_val = 1e-10; double step = u_val / MathPow (v_val, 1.0 / beta); return 0.01 * step; } //————————————————————————————————————————————————————————————————————
Результаты тестов
Алгоритм стрекозы (DA) продемонстрировал результат 36% на нашем тестовом стенде, что, к сожалению, не позволяет ему войти в рейтинговую таблицу. Это средний показатель, свидетельствующий о некоторых трудностях алгоритма при решении задач оптимизации различной сложности.=============================
5 Hilly's; Func runs: 10000; result: 0.6776724523765025
25 Hilly's; Func runs: 10000; result: 0.3961601008221486
500 Hilly's; Func runs: 10000; result: 0.27032293850032585
=============================
5 Forest's; Func runs: 10000; result: 0.6088666045448039
25 Forest's; Func runs: 10000; result: 0.3063399651091877
500 Forest's; Func runs: 10000; result: 0.18032255251950144
=============================
5 Megacity's; Func runs: 10000; result: 0.5061538461538462
25 Megacity's; Func runs: 10000; result: 0.21415384615384614
500 Megacity's; Func runs: 10000; result: 0.1035384615384625
=============================
All score: 3.26353 (36.26%)
Визуализация работы алгоритма стрекозы на наших тестовых задачах разной размерности и стандартных функциях.
DA_Dragonfly на тестовой функции Hilly
DA_Dragonfly на тестовой функции Forest
DA_Dragonfly на тестовой функции Megacity
DA_Dragonfly на стандартной функции Ackey
DA_Dragonfly на стандартной функции Paraboloid
Алгоритм DA_Dragonfly по результатам тестирования представлен в рейтинговой таблице ознакомительно.
| № | 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 | 0,94948 | 0,84776 | 0,43857 | 2,23581 | 1,00000 | 0,92334 | 0,39988 | 2,32323 | 0,70923 | 0,63477 | 0,23091 | 1,57491 | 6,134 | 68,15 |
| 2 | CLA | code lock algorithm (jo o) | 0,95345 | 0,87107 | 0,37590 | 2,20042 | 0,98942 | 0,91709 | 0,31642 | 2,22294 | 0,79692 | 0,69385 | 0,19303 | 1,68380 | 6,107 | 67,86 |
| 3 | AMOm | animal migration ptimization M | 0,90358 | 0,84317 | 0,46284 | 2,20959 | 0,99001 | 0,92436 | 0,46598 | 2,38034 | 0,56769 | 0,59132 | 0,23773 | 1,39675 | 5,987 | 66,52 |
| 4 | (P+O)ES | (P+O) evolution strategies | 0,92256 | 0,88101 | 0,40021 | 2,20379 | 0,97750 | 0,87490 | 0,31945 | 2,17185 | 0,67385 | 0,62985 | 0,18634 | 1,49003 | 5,866 | 65,17 |
| 5 | CTA | comet tail algorithm (joo) | 0,95346 | 0,86319 | 0,27770 | 2,09435 | 0,99794 | 0,85740 | 0,33949 | 2,19484 | 0,88769 | 0,56431 | 0,10512 | 1,55712 | 5,846 | 64,96 |
| 6 | TETA | time evolution travel algorithm (joo) | 0,91362 | 0,82349 | 0,31990 | 2,05701 | 0,97096 | 0,89532 | 0,29324 | 2,15952 | 0,73462 | 0,68569 | 0,16021 | 1,58052 | 5,797 | 64,41 |
| 7 | SDSm | stochastic diffusion search M | 0,93066 | 0,85445 | 0,39476 | 2,17988 | 0,99983 | 0,89244 | 0,19619 | 2,08846 | 0,72333 | 0,61100 | 0,10670 | 1,44103 | 5,709 | 63,44 |
| 8 | ECBO | enhanced_colliding_bodies_optimization | 0,93479 | 0,75747 | 0,32471 | 2,01697 | 0,97436 | 0,77446 | 0,23037 | 1,97919 | 0,88923 | 0,58061 | 0,15224 | 1,62208 | 5,618 | 62,43 |
| 9 | BOAm | billiards optimization algorithm M | 0,95757 | 0,82599 | 0,25235 | 2,03590 | 1,00000 | 0,90036 | 0,30502 | 2,20538 | 0,73538 | 0,52523 | 0,09563 | 1,35625 | 5,598 | 62,19 |
| 10 | AAm | archery algorithm M | 0,91744 | 0,70876 | 0,42160 | 2,04780 | 0,92527 | 0,75802 | 0,35328 | 2,03657 | 0,67385 | 0,55200 | 0,23738 | 1,46323 | 5,548 | 61,64 |
| 11 | ESG | evolution of social groups (joo) | 0,99906 | 0,79654 | 0,35056 | 2,14616 | 1,00000 | 0,82863 | 0,13102 | 1,95965 | 0,82333 | 0,55300 | 0,04725 | 1,42358 | 5,529 | 61,44 |
| 12 | SIA | simulated isotropic annealing (joo) | 0,95784 | 0,84264 | 0,41465 | 2,21513 | 0,98239 | 0,79586 | 0,20507 | 1,98332 | 0,68667 | 0,49300 | 0,09053 | 1,27020 | 5,469 | 60,76 |
| 13 | EOm | extremal_optimization_M | 0,76166 | 0,77242 | 0,31747 | 1,85155 | 0,99999 | 0,76751 | 0,23527 | 2,00277 | 0,74769 | 0,53969 | 0,14249 | 1,42987 | 5,284 | 58,71 |
| 14 | BBO | biogeography based optimization | 0,94912 | 0,69456 | 0,35031 | 1,99399 | 0,93820 | 0,67365 | 0,25682 | 1,86867 | 0,74615 | 0,48277 | 0,17369 | 1,40261 | 5,265 | 58,50 |
| 15 | ACS | artificial cooperative search | 0,75547 | 0,74744 | 0,30407 | 1,80698 | 1,00000 | 0,88861 | 0,22413 | 2,11274 | 0,69077 | 0,48185 | 0,13322 | 1,30583 | 5,226 | 58,06 |
| 16 | DA | dialectical algorithm | 0,86183 | 0,70033 | 0,33724 | 1,89940 | 0,98163 | 0,72772 | 0,28718 | 1,99653 | 0,70308 | 0,45292 | 0,16367 | 1,31967 | 5,216 | 57,95 |
| 17 | BHAm | black hole algorithm M | 0,75236 | 0,76675 | 0,34583 | 1,86493 | 0,93593 | 0,80152 | 0,27177 | 2,00923 | 0,65077 | 0,51646 | 0,15472 | 1,32195 | 5,196 | 57,73 |
| 18 | ASO | anarchy society optimization | 0,84872 | 0,74646 | 0,31465 | 1,90983 | 0,96148 | 0,79150 | 0,23803 | 1,99101 | 0,57077 | 0,54062 | 0,16614 | 1,27752 | 5,178 | 57,54 |
| 19 | RFO | royal flush optimization (joo) | 0,83361 | 0,73742 | 0,34629 | 1,91733 | 0,89424 | 0,73824 | 0,24098 | 1,87346 | 0,63154 | 0,50292 | 0,16421 | 1,29867 | 5,089 | 56,55 |
| 20 | AOSm | atomic orbital search M | 0,80232 | 0,70449 | 0,31021 | 1,81702 | 0,85660 | 0,69451 | 0,21996 | 1,77107 | 0,74615 | 0,52862 | 0,14358 | 1,41835 | 5,006 | 55,63 |
| 21 | TSEA | turtle shell evolution algorithm (joo) | 0,96798 | 0,64480 | 0,29672 | 1,90949 | 0,99449 | 0,61981 | 0,22708 | 1,84139 | 0,69077 | 0,42646 | 0,13598 | 1,25322 | 5,004 | 55,60 |
| 22 | BSA | backtracking_search_algorithm | 0,97309 | 0,54534 | 0,29098 | 1,80941 | 0,99999 | 0,58543 | 0,21747 | 1,80289 | 0,84769 | 0,36953 | 0,12978 | 1,34700 | 4,959 | 55,10 |
| 23 | DE | differential evolution | 0,95044 | 0,61674 | 0,30308 | 1,87026 | 0,95317 | 0,78896 | 0,16652 | 1,90865 | 0,78667 | 0,36033 | 0,02953 | 1,17653 | 4,955 | 55,06 |
| 24 | SRA | successful restaurateur algorithm (joo) | 0,96883 | 0,63455 | 0,29217 | 1,89555 | 0,94637 | 0,55506 | 0,19124 | 1,69267 | 0,74923 | 0,44031 | 0,12526 | 1,31480 | 4,903 | 54,48 |
| 25 | BO | bonobo_optimizer | 0,77565 | 0,63805 | 0,32908 | 1,74278 | 0,88088 | 0,76344 | 0,25573 | 1,90005 | 0,61077 | 0,49846 | 0,14246 | 1,25169 | 4,895 | 54,38 |
| 26 | CRO | chemical reaction optimisation | 0,94629 | 0,66112 | 0,29853 | 1,90593 | 0,87906 | 0,58422 | 0,21146 | 1,67473 | 0,75846 | 0,42646 | 0,12686 | 1,31178 | 4,892 | 54,36 |
| 27 | BIO | blood inheritance optimization (joo) | 0,81568 | 0,65336 | 0,30877 | 1,77781 | 0,89937 | 0,65319 | 0,21760 | 1,77016 | 0,67846 | 0,47631 | 0,13902 | 1,29378 | 4,842 | 53,80 |
| 28 | DOA | dream_optimization_algorithm | 0,85556 | 0,70085 | 0,37280 | 1,92921 | 0,73421 | 0,48905 | 0,24147 | 1,46473 | 0,77231 | 0,47354 | 0,18561 | 1,43146 | 4,825 | 53,62 |
| 29 | BSA | bird swarm algorithm | 0,89306 | 0,64900 | 0,26250 | 1,80455 | 0,92420 | 0,71121 | 0,24939 | 1,88479 | 0,69385 | 0,32615 | 0,10012 | 1,12012 | 4,809 | 53,44 |
| 30 | DEA | dolphin_echolocation_algorithm | 0,75995 | 0,67572 | 0,34171 | 1,77738 | 0,89582 | 0,64223 | 0,23941 | 1,77746 | 0,61538 | 0,44031 | 0,15115 | 1,20684 | 4,762 | 52,91 |
| 31 | HS | harmony search | 0,86509 | 0,68782 | 0,32527 | 1,87818 | 0,99999 | 0,68002 | 0,09590 | 1,77592 | 0,62000 | 0,42267 | 0,05458 | 1,09725 | 4,751 | 52,79 |
| 32 | SSG | saplings sowing and growing | 0,77839 | 0,64925 | 0,39543 | 1,82308 | 0,85973 | 0,62467 | 0,17429 | 1,65869 | 0,64667 | 0,44133 | 0,10598 | 1,19398 | 4,676 | 51,95 |
| 33 | BCOm | bacterial chemotaxis optimization M | 0,75953 | 0,62268 | 0,31483 | 1,69704 | 0,89378 | 0,61339 | 0,22542 | 1,73259 | 0,65385 | 0,42092 | 0,14435 | 1,21912 | 4,649 | 51,65 |
| 34 | ABO | african buffalo optimization | 0,83337 | 0,62247 | 0,29964 | 1,75548 | 0,92170 | 0,58618 | 0,19723 | 1,70511 | 0,61000 | 0,43154 | 0,13225 | 1,17378 | 4,634 | 51,49 |
| 35 | (PO)ES | (PO) evolution strategies | 0,79025 | 0,62647 | 0,42935 | 1,84606 | 0,87616 | 0,60943 | 0,19591 | 1,68151 | 0,59000 | 0,37933 | 0,11322 | 1,08255 | 4,610 | 51,22 |
| 36 | FBA | fractal-based Algorithm | 0,79000 | 0,65134 | 0,28965 | 1,73099 | 0,87158 | 0,56823 | 0,18877 | 1,62858 | 0,61077 | 0,46062 | 0,12398 | 1,19537 | 4,555 | 50,61 |
| 37 | TSm | tabu search M | 0,87795 | 0,61431 | 0,29104 | 1,78330 | 0,92885 | 0,51844 | 0,19054 | 1,63783 | 0,61077 | 0,38215 | 0,12157 | 1,11449 | 4,536 | 50,40 |
| 38 | BSO | brain storm optimization | 0,93736 | 0,57616 | 0,29688 | 1,81041 | 0,93131 | 0,55866 | 0,23537 | 1,72534 | 0,55231 | 0,29077 | 0,11914 | 0,96222 | 4,498 | 49,98 |
| 39 | WOAm | wale optimization algorithm M | 0,84521 | 0,56298 | 0,26263 | 1,67081 | 0,93100 | 0,52278 | 0,16365 | 1,61743 | 0,66308 | 0,41138 | 0,11357 | 1,18803 | 4,476 | 49,74 |
| 40 | AEFA | artificial electric field algorithm | 0,87700 | 0,61753 | 0,25235 | 1,74688 | 0,92729 | 0,72698 | 0,18064 | 1,83490 | 0,66615 | 0,11631 | 0,09508 | 0,87754 | 4,459 | 49,55 |
| 41 | AEO | artificial ecosystem-based optimization algorithm | 0,91380 | 0,46713 | 0,26470 | 1,64563 | 0,90223 | 0,43705 | 0,21400 | 1,55327 | 0,66154 | 0,30800 | 0,28563 | 1,25517 | 4,454 | 49,49 |
| 42 | CAm | camel algorithm M | 0,78684 | 0,56042 | 0,35133 | 1,69859 | 0,82772 | 0,56041 | 0,24336 | 1,63149 | 0,64846 | 0,33092 | 0,13418 | 1,11356 | 4,444 | 49,37 |
| 43 | ACOm | ant colony optimization M | 0,88190 | 0,66127 | 0,30377 | 1,84693 | 0,85873 | 0,58680 | 0,15051 | 1,59604 | 0,59667 | 0,37333 | 0,02472 | 0,99472 | 4,438 | 49,31 |
| 44 | CMAES | covariance_matrix_adaptation_evolution_strategy | 0,76258 | 0,72089 | 0,00000 | 1,48347 | 0,82056 | 0,79616 | 0,00000 | 1,61672 | 0,75846 | 0,49077 | 0,00000 | 1,24923 | 4,349 | 48,33 |
| 45 | DA_duelist | duelist_algorithm | 0,92782 | 0,53778 | 0,27792 | 1,74352 | 0,86957 | 0,47536 | 0,18193 | 1,52686 | 0,62153 | 0,33569 | 0,11715 | 1,07437 | 4,345 | 48,28 |
| DA_dr.fly | dragonfly_algorithm | 0,67767 | 0,39616 | 0,27032 | 1,34415 | 0,60887 | 0,30634 | 0,18032 | 1,09553 | 0,50615 | 0,21415 | 0,10353 | 0,82383 | 3,264 | 36,26 | |
| RW | random walk | 0,48754 | 0,32159 | 0,25781 | 1,06694 | 0,37554 | 0,21944 | 0,15877 | 0,75375 | 0,27969 | 0,14917 | 0,09847 | 0,52734 | 2,348 | 26,09 | |
Выводы
Основная проблема DA — склонность к застреванию в локальных оптимумах. Несмотря на наличие механизма полёта Леви, который теоретически должен обеспечивать выход из ловушек за счёт случайных длинных прыжков, на практике этого оказывается недостаточно. Во второй половине оптимизации, когда радиус соседства становится большим и весовые коэффициенты разделения, выравнивания, сплочения и опасности обнуляются, рой фактически утрачивает механизмы диверсификации. Все агенты оказываются в зоне видимости друг друга и притягиваются к единственной точке — Food, — что лишает алгоритм способности исследовать альтернативные области пространства. Если к этому моменту лучшее найденное решение оказалось локальным оптимумом, алгоритм не имеет инструментов для выхода из него.
Из положительных моментов следует отметить простоту использования. Формально у алгоритма всего один внешний параметр — размер популяции. Это существенное преимущество перед многими метаэвристиками, требующими тонкой настройки нескольких коэффициентов. Однако нужно оговориться: помимо размера популяции в реализации присутствуют внутренние коэффициенты, подобранные эмпирическим путём, — это ограничение максимальной скорости "Delta_max", начальные и конечные значения инерции, скорость затухания коэффициента "my_c" и порог активации разделения. Они не вынесены в параметры, но тем не менее влияют на поведение алгоритма и при желании могут быть объектом дополнительной настройки.
Отдельного упоминания заслуживает поведение алгоритма на визуализации. Алгоритм стрекозы работает визуально интересно: агенты формируют характерные геометрические паттерны — линии и лучи, — особенно заметные при больших размерностях задачи. Это наглядно отражает механику алгоритма: выравнивание скоростей и притяжение к общим точкам организуют рой в упорядоченные структуры, в отличие от хаотичного облака точек, типичного для многих популяционных алгоритмов. Впрочем, эстетическая привлекательность визуализации не компенсирует эффективность поиска.
Подводя итог, алгоритм стрекозы представляет собой добротную академическую работу с красивой биологической метафорой и элегантным адаптивным механизмом, но его практическая эффективность на нашем наборе тестовых функций оказалась ниже ожиданий. Алгоритм стрекозы может представлять интерес как учебный пример роевого алгоритма с понятной механикой и минимумом настроек, однако для задач, требующих высокой точности оптимизации, предпочтительнее обратиться к алгоритмам из верхней части нашего рейтинга.
Рисунок 2. Цветовая градация алгоритмов по соответствующим тестам
Рисунок 3. Гистограмма результатов тестирования алгоритмов (по шкале от 0 до 100, чем больше, тем лучше, где 100 — максимально возможный теоретический результат, в архиве скрипт для расчета рейтинговой таблицы)
Плюсы и минусы алгоритма DA_Dragonfly:
Плюсы:
- Всего один внешний параметр.
Минусы:
- Застревает.
К статье прикреплён архив с актуальными версиями кодов алгоритмов. Автор статьи не несёт ответственности за абсолютную точность в описании канонических алгоритмов, во многие из них были внесены изменения для улучшения поисковых возможностей. Выводы и суждения, представленные в статьях, основываются на результатах проведённых экспериментов.
Программы, используемые в статье
| # | Имя | Тип | Описание |
|---|---|---|---|
| 1 | #C_AO.mqh | Включаемый файл | Родительский класс популяционных алгоритмов оптимизации |
| 2 | #C_AO_enum.mqh | Включаемый файл | Перечисление популяционных алгоритмов оптимизации |
| 3 | TestFunctions.mqh | Включаемый файл | Библиотека тестовых функций |
| 4 | TestStandFunctions.mqh | Включаемый файл | Библиотека функций тестового стенда |
| 5 | Utilities.mqh | Включаемый файл | Библиотека вспомогательных функций |
| 6 | CalculationTestResults.mqh | Включаемый файл | Скрипт для расчета результатов в сравнительную таблицу |
| 7 | Testing AOs.mq5 | Скрипт | Единый испытательный стенд для всех популяционных алгоритмов оптимизации |
| 8 | Simple use of population optimization algorithms.mq5 | Скрипт | Простой пример использования популяционных алгоритмов оптимизации без визуализации |
| 9 | Test_DA_Dragonfly.mq5 | Скрипт | Испытательный стенд для DA_Dragonfly |
Предупреждение: все права на данные материалы принадлежат MetaQuotes Ltd. Полная или частичная перепечатка запрещена.
Данная статья написана пользователем сайта и отражает его личную точку зрения. Компания MetaQuotes Ltd не несет ответственности за достоверность представленной информации, а также за возможные последствия использования описанных решений, стратегий или рекомендаций.
Создание самооптимизирующихся советников на MQL5 (Часть 8): Анализ нескольких стратегий
От начального до среднего уровня: Индикатор (V)
Знакомство с языком MQL5 (Часть 36): Освоение API и функции WebRequest в языке MQL5 (X)
Нейросети в трейдинге: Единая архитектура взаимодействия рыночных признаков и торгового контекста (Основные компоненты)
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Вы принимаете политику сайта и условия использования