
Популяционные алгоритмы оптимизации: Алгоритм оптимизации спиральной динамики (Spiral Dynamics Optimization, SDO)
Содержание:
1. Введение
2. Описание алгоритма
3. Результаты тестов
1. Введение
В научной литературе представлено обширное множество алгоритмов метаэвристической оптимизации, основанных на различных аспектах природы и популяций. Эти алгоритмы классифицируются по нескольким категориям, например: роевой интеллект, физика, химия, социальное человеческое поведение, растения, животные и другие. Существует множество метаэвристических алгоритмов оптимизации, основанных на роевом интеллекте. Также широко предлагаемыми и успешно применяемыми в различных областях являются алгоритмы, основанные на физических явлениях.
Алгоритмы, основанные на роевом интеллекте, включают элементы интеллекта в процессе поиска оптимального решения. Они моделируют поведение стаи или колонии, где индивидуальные агенты обмениваются информацией и сотрудничают для достижения общей цели. Эти алгоритмы могут быть эффективными в задачах, где требуется глобальный поиск и адаптивность к изменяющимся условиям.
С другой стороны, алгоритмы, основанные на физике, опираются на законы и принципы физики для решения оптимизационных задач. Они моделируют физические явления, такие как гравитация, электромагнетизм или термодинамика, и используют эти принципы для поиска оптимального решения. Одним из главных преимуществ алгоритмов, основанных на физике, является их простая интерпретация. Они могут точно и последовательно отображать динамику во всей области поиска.
Кроме того, некоторые алгоритмы, основанные на физике, используют золотое сечение, математическое и природное соотношение, которое имеет особые свойства и помогает быстро и эффективно сходиться к оптимальному решению. Золотое сечение было изучено и применено в различных областях, включая оптимизацию искусственных нейронных сетей, распределение ресурсов и другие.
Таким образом, алгоритмы метаэвристической оптимизации, основанные на физике, представляют собой мощный инструмент для решения сложных оптимизационных задач. Их точность и применение фундаментальных физических принципов делают их привлекательными для различных областей, где требуется эффективный поиск оптимальных решений.
Оптимизация спиральной динамики (SDO) — один из наиболее простых физических алгоритмов, предложенный Тамурой и Ясудой в 2011 году и разработанный с использованием явления логарифмической спирали в природе. Алгоритм прост и имеет мало управляющих параметров. Более того, алгоритм обладает высокой скоростью вычислений, возможностью локального поиска, диверсификацией на ранней стадии и интенсификацией на более позднем этапе.
В природе доступно множество спиралей, таких как галактики, полярные сияния, рога животных, торнадо, морские ракушки, улитки, аммониты, хвост хамелеона, морской конёк. Спирали также можно увидеть в древнем искусстве, созданном человечеством на заре своего существования. На протяжении многих лет несколько исследователей прилагали усилия, чтобы понять спиральные последовательности и сложности, а также разработать уравнения и алгоритмы спиралей. Более того, стоит подчеркнуть, что часто встречающимся спиральным явлением в природе является логарифмическая спираль, которую можно наблюдать в галактиках и тропических циклонах. Дискретные процессы генерации логарифмической спирали были реализованы как эффективное поведение поиска в метаэвристике, что вдохновило на разработку алгоритма оптимизации спиральной динамики.
Узоры, называемые видимыми спиральными последовательностями, встречающимися в природе, представляют собой растения, деревья, волны и многие другие формы. Визуальные узоры в природе могут быть моделированы с использованием теории хаоса, фракталов, спиралей и других математических концепций. В некоторых природных узорах спирали и фракталы тесно связаны между собой. Например, спираль Фибоначчи является вариантом логарифмической спирали, основанной на золотом сечении и числах Фибоначчи. Поскольку она является логарифмической, кривая в каждом масштабе выглядит одинаковой, и ее также можно считать фракталом.
Вышеупомянутые закономерности вдохновили исследователей на разработку алгоритмов оптимизации. Существуют различные типы спиральных траекторий, вот основные из них:
- Архимедова спираль
- Циклоидная спираль
- Эпитрохоидная спираль
- Гипотрохоидная спираль
- Логарифмическая спираль
- Роза спиральная
- Фермацова спираль
Каждый из этих типов спиралей имеет свои уникальные свойства и может использоваться для моделирования различных природных узоров и особый интерес уделяется освещению различных алгоритмов оптимизации, вдохновленных природой, основанных на концепции спиральных путей. За прошедшие годы исследователи разработали различные новые алгоритмы оптимизации, в которых использовалось спиральное движение.
Кроме того, поведение неспиральных алгоритмов можно изменить, используя спиральные пути как надстройку или дополнение для повышения точности оптимального решения.
Двумерный алгоритм спиральной оптимизации, предложенный Тамурой и Ясудой, представляет собой многоточечный метаэвристический метод поиска для двумерных задач непрерывной оптимизации. Затем Тамура и Ясуда предложили n-мерную оптимизацию, используя философию двумерной оптимизации.
2. Описание алгоритма
Алгоритм SDO для поиска в многомерных пространствах, описанный авторами, имеет ограничения и недостатки:- Невозможность использования для одномерных и других задач оптимизации, имеющих нечетную мерность.
- Связывание алгоритмом по-парно координат могут влиять на качество решения на специфических задачах и показывать ложно-положительные результаты на синтетических тестах.
Построение спиральных траекторий в многомерном пространстве представляет определенные трудности. Так, если задача ограничена одномерным пространством, то спираль не может быть построена в привычном смысле, так как для спирали требуется движение в не менее чем в двух измерениях. В этом случае можно использовать простую функцию для изменения значения координаты с течением времени, без применения спирали. Если же речь идет об одномерной задаче оптимизации, то спираль не применяется, поскольку нет дополнительных измерений для движения по спирали.
В многомерном пространстве спирали могут быть построены для каждой пары координат, но для одной оставшейся координаты спираль не может быть определена. Например, в случае 13-мерного пространства можно построить спирали для 6 пар координат, но одна координата будет двигаться без спиральной компоненты.
Для построения спиралей в многомерном пространстве можно использовать метод "многомерной спирали" или "гиперспирали". Этот метод включает в себя введение дополнительных виртуальных координат и определение спиральной формы в каждом измерении. Для построения гиперспирали можно использовать матрицы вращения и алгоритмы, основанные на геометрии многомерных пространств. Однако такой подход требует более сложных вычислений и может быть трудно реализуемым в практических задачах оптимизации.
Поскольку в статьях используются многомерные функции в виде многократно продублированных двумерных, то оригинальный SDO может показать неоправданно высокие результаты, ведь в нём используется связывание координат попарно. Таким образом на других многомерных задачах, где координаты никак не связаны между собой, спиральный алгоритм покажет низкие результаты. Т.е., для спирального алгоритма в данном примере на продублированных функциях неумышленно будут созданы "тепличные" условия.
Что бы избежать вышеназванных проблем со спиральным алгоритмом, я предлагаю подход, основанный на проекции двумерной спирали на одну координатную ось. Если мы рассмотрим движение точки на двумерной спирали как движение маятника, то проекция движения точки на каждую из двух координат будет подчиняться проекции движения маятника на каждую из координат. Таким образом, мы можем использовать проекцию движения точки маятника на каждую из осей в многомерном пространстве для моделирования движения точки по спирали в двумерном пространстве.
При использовании метода построения спиралей, моделирующих поведение маятника на каждой из координат в многомерном пространстве, радиус каждой "виртуальной" спирали может быть разным. Это может оказать положительный эффект на качество оптимизации, поскольку некоторые координаты могут быть ближе к известным оптимумам, и их не нужно значительно изменять.
Мы можем взять любой закон гармонических колебаний с затуханием в качестве проекции двумерной спирали на одномерную ось. Был выбран простой затухающий гармонический осциллятор, зависимость положения точки от времени, формула которого:
x(t) = A*e^(-γt)*cos(ωt + φ)
где:
- A - амплитуда колебаний
- γ - коэффициент затухания
- ω - собственная частота осциллятора
- φ - начальная фаза колебаний
Из формулы становится понятным, что коэффициент затухания, частота и начальная фаза - константы и могут быть использованы в качестве входных параметров алгоритма, но мы будем использовать не три, а два параметра. Начальную фазу колебаний будем использовать в качестве случайной компоненты на каждой итерации (каждая координата будет несколько смещена по фазе относительно других координат), в противном случае алгоритм является полностью детерминированным и зависит только от первоначального размещения точек в пространстве.
Идея заключается в том, что как только будет обнаружен новый лучший глобальный экстремум, для всех точек будет рассчитана новая амплитуда, которая есть разница между координатой глобального экстремума и соответствующей координатой точки. С этого момента амплитуды по координатам индивидуальны и сохранены в памяти каждой точки, пока не будет обнаружен новый экстремум лучше и будут определены новые амплитуды.
После определения амплитуд каждая точка начинает колебаться с затуханием, где ось симметрии колебаний и есть известная координата глобального оптимума. Визуально удобно оценить влияние коэффициентов затухания и частоты (внешних параметров) по рисункам 1 и 2.
Рисунок 1. Влияние амплитуды на характер колебаний.
Рисунок 2. Влияние частоты на характер колебаний.
Хотя у нас в алгоритме все координаты абсолютно независимы, как было упомянуто, нет никаких попарных комбинаций и связей между ними в логике для построения спиралей, если бы мы построили движение точки на двумерной плоскости, то получили бы спираль следующего вида, как на рисунке 3.
Рисунок 3. Гипотетическая спираль, с параметрами алгоритма по умолчанию, где 6 - значение амплитуды, 0.3 - коэффициент затухания, и 4 - частота.
На самом деле в реальных задачах, как, впрочем, и на тестовых функциях, амплитуды по каждой из координат могут быть и не обязаны быть одинаковыми (в отличие от оригинального алгоритма). Разница амплитуд будет давать сплющенные спирали, с меньшей амплитудой соответствующая координата будет уточнена быстрее, так как она ближе к известному лучшему значению.
Рисунок 4. Значение точки по координате Y находится ближе к известному значению и амплитуда колебаний у неё меньше, чем по оси X.
Все построения на графиках произведены относительно нуля, так как мы рассматриваем разницу относительно значения известного оптимума, то есть, смещение от нуля есть приращение.
Переходим к описанию кода. Для начала определимся со структурой алгоритма и составим псевдокод:
- Инициализировать популяцию точек
- Вычислить значение фитнес-функции
- Рассчитать амплитуду для каждой координаты точек при появлении нового лучшего оптимума
- При появлении нового лучшего оптимума "выкинуть" лучшую точку в случайном направлении
- Вычислить новое положение точек по формуле затухающих гармонических колебаний
- Повторить с п.2.
Пункт 4 специально добавлен и призван обеспечить повышение устойчивости к застреванию, что бы точки не сошлись по "спирали" к некоторому локальному экстремуму и не застряли там. У авторов алгоритма этот момент не освещён.
Для описания агента (частица, точка) хорошо подойдет структура S_Particle, которая содержит следующие переменные:
- c [] - массив координат частицы
- cD[] - массив скоростей частицы
- t - шаг итерации, играет роль "времени" в формуле
- f - значение функции приспособленности частицы
Также в структуре определена функция Init, которая используется для инициализации переменных структуры. Параметр coords задает количество координат частицы.
//—————————————————————————————————————————————————————————————————————————————— struct S_Particle { void Init (int coords) { ArrayResize (c, coords); ArrayResize (cD, coords); t = 0; f = -DBL_MAX; } double c []; //coordinates double cD []; //coordinates int t; //iteration (time) double f; //fitness }; //——————————————————————————————————————————————————————————————————————————————
Определим класс алгоритма SDOm, C_AO_SDOm. Класс содержит следующие переменные и методы:
- cB [] - массив лучших координат
- fB - значение функции приспособленности лучших координат
- p [] - массив частиц, тип данных - S_Particle
- rangeMax [] - массив максимальных значений диапазона поиска
- rangeMin [] - массив минимальных значений диапазона поиска
- rangeStep [] - массив шагов поиска
- Init - метод для инициализации параметров класса, принимает следующие параметры: "coordinatesNumberP" - количество координат, "populationSize" - размер популяции, "dampingFactorP" - коэффициент затухания, "frequencyP" - частота, "precisionP" - точность.
- Moving - метод для перемещения частиц в пространстве поиска
- Revision - метод для ревизии и обновления лучших координат
- coords - количество координат
- popSiz - размер популяции
- A, e, γ, ω, φ - компоненты формулы затухающего гармонического колебания
- precision, revision - приватные переменные, которые используются внутри класса
- SeInDiSp - метод вычисляет новое значение координаты в заданном диапазоне с заданным шагом
- RNDfromCI - метод генерирует случайное число в заданном диапазоне
Данный код описывает класс C_AO_SDOm, который представляет реализацию алгоритма с дополнительными функциями для ревизии и обновления лучших координат.
Первые три переменные класса — это массив cB, который хранит лучшие координаты, переменная fB, которая хранит значение функции приспособленности лучших координат, и массив p, который хранит кандидатов (частицы) популяции.
Следующие три переменные класса — это массивы rangeMax, rangeMin и rangeStep, которые хранят максимальные и минимальные значения диапазона поиска и шаги поиска соответственно.
Далее, класс содержит три публичных метода: Init, Moving и Revision. Метод Init используется для инициализации параметров класса и создания начальной популяции частиц. Метод Moving используется для перемещения частиц по пространству поиска. Метод Revision используется для ревизии лучших координат и обновления их значений.
Класс также содержит несколько приватных переменных, которые используются внутри класса. Это переменные coords и popSize, которые хранят количество координат и размер популяции соответственно, переменная A, которая используется в методе Moving, переменная precision, которая хранит значение точности, и переменная revision, которая отвечает за необходимость ревизии лучших координат.
Класс содержит несколько приватных методов: Research, SeInDiSp и RNDfromCI. Метод Research используется для исследования новых координат частицы, методы SeInDiSp и RNDfromCI используются для вычисления случайных значений в заданном диапазоне.
"precision" - внешний параметр алгоритма, отвечает за дискретность движения по траектории затухающего колебания, чем больше значение, тем точнее воспроизводится траектория, а меньшие значение приводят к "рванности" траектории (это не значит, что будет негативное влияние на результат, зависит от специфики задачи). Параметр по умолчанию выбран оптимальным после серии моих экспериментов.
//—————————————————————————————————————————————————————————————————————————————— class C_AO_SDOm { //---------------------------------------------------------------------------- public: double cB []; //best coordinates public: double fB; //FF of the best coordinates public: S_Particle p []; //particles public: double rangeMax []; //maximum search range public: double rangeMin []; //manimum search range public: double rangeStep []; //step search public: void Init (const int coordinatesNumberP, //coordinates number const int populationSizeP, //population size const double dampingFactorP, //damping factor const double frequencyP, //frequency const double precisionP); //precision public: void Moving (); public: void Revision (); //---------------------------------------------------------------------------- private: int coords; //coordinates number private: int popSize; //population size private: double A; private: double e; private: double γ; private: double ω; private: double φ; private: double precision; private: bool revision; private: double SeInDiSp (double In, double InMin, double InMax, double Step); private: double RNDfromCI (double min, double max); }; //——————————————————————————————————————————————————————————————————————————————
Метод Init класса C_AO_SDOm, используется для инициализации параметров класса и создания начальной популяции частиц.
Сначала используется "MathSrand" для сброса генератора случайных чисел и функцию "GetMicrosecondCount" для инициализации генератора.
Далее метод устанавливает начальные значения для переменных "fB" и "revision" и назначения размера массиву популяции, а так же назначает значения константным переменным, участующих в формуле затухающих колебаний.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_SDOm::Init (const int coordinatesNumberP, //coordinates number const int populationSizeP, //population size const double dampingFactorP, //damping factor const double frequencyP, //frequency const double precisionP) //precision { MathSrand ((int)GetMicrosecondCount ()); // reset of the generator fB = -DBL_MAX; revision = false; coords = coordinatesNumberP; popSize = populationSizeP; e = M_E; γ = dampingFactorP; ω = frequencyP; φ = 0.0; precision = precisionP; ArrayResize (rangeMax, coords); ArrayResize (rangeMin, coords); ArrayResize (rangeStep, coords); ArrayResize (cB, coords); ArrayResize (p, popSize); for (int i = 0; i < popSize; i++) { p [i].Init (coords); } } //——————————————————————————————————————————————————————————————————————————————Для перемещения частиц в пространстве поиска будем использовать метод "Moving".
Первый блок кода (if (!revision)) выполняется только на первой итерации и предназначен для случайного размещения частиц в пространстве поиска. Затем метод устанавливает значение "revision" в "true", чтобы в следующий раз использовать обычный блок кода.
Следующая часть кода метода отвечает за перемещение частиц популяции. Если значение приспособленности текущей частицы равно значению приспособленности лучших координат (p[i].f == fB), то координаты частицы обновляются так же, как и в первом блоке кода. Это означает, что частица выбрасывается из своего положения в случайном направлении, чтобы предотвратить схождение всех частиц в одну единственную точку.
В противном случае метод использует переменную "t", чтобы имитировать текущее время для каждой частицы, используя счетчик итераций (который сбрасывается при обновлении лучшего глобального решения). Затем вычисляются координаты каждой частицы по формуле затухающих гармонических колебаний.
Закомментированная часть кода добавляет случайное приращение к вычисленному по формуле значению координаты и может использоваться для получения красивого визуального эффекта "фейерверка". Однако этот эффект не имеет практической ценности и не улучшает результаты, поэтому код закомментирован.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_SDOm::Moving () { //---------------------------------------------------------------------------- if (!revision) { for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { p [i].c [c] = RNDfromCI (rangeMin [c], rangeMax [c]); p [i].c [c] = SeInDiSp (p [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } revision = true; return; } //---------------------------------------------------------------------------- int t = 0.0; for (int i = 0; i < popSize; i++) { if (p [i].f == fB) { for (int c = 0; c < coords; c++) { p [i].c [c] = RNDfromCI (rangeMin [c], rangeMax [c]); p [i].c [c] = SeInDiSp (p [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } continue; } p [i].t++; t = p [i].t; for (int c = 0; c < coords; c++) { A = p [i].cD [c]; φ = RNDfromCI (0.0, 2.0); p [i].c [c] = p [i].c [c] + A * pow (e, -γ * t / precision) * cos (ω * t / (precision) + φ);// + RNDfromCI (-0.01, 0.01) * (rangeMax [c] - rangeMin [c]); p [i].c [c] = SeInDiSp (p [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } } //——————————————————————————————————————————————————————————————————————————————
Метод Revision класса используется для обновления лучших координат и вычисления разницы между координатами частиц и известным лучшим решением. Эта разница служит начальной амплитудой, и как только будет найдено новое лучшее решение, частицы начнут совершать колебательные движения вокруг лучших известных координат, которые находятся в центре этих движений.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_SDOm::Revision () { //---------------------------------------------------------------------------- bool flag = false; for (int i = 0; i < popSize; i++) { if (p [i].f > fB) { flag = true; fB = p [i].f; ArrayCopy (cB, p [i].c, 0, 0, WHOLE_ARRAY); } } if (flag) { for (int i = 0; i < popSize; i++) { p [i].t = 0; for (int c = 0; c < coords; c++) { p [i].cD [c] = (cB [c] - p [i].c [c]); } } } } //——————————————————————————————————————————————————————————————————————————————
3. Результаты тестов
Распечатка работы алгоритма спиральной динамики на тестовом стенде, судя по всему - неплохие результаты:
C_AO_SDOm:100;0.3;4.0;10000.0
=============================
5 Rastrigin's; Func runs 10000 result: 76.22736727464056
Score: 0.94450
25 Rastrigin's; Func runs 10000 result: 64.5695106264092
Score: 0.80005
500 Rastrigin's; Func runs 10000 result: 47.607500083305425
Score: 0.58988
=============================
5 Forest's; Func runs 10000 result: 1.3265635010116805
Score: 0.75037
25 Forest's; Func runs 10000 result: 0.5448141810532924
Score: 0.30817
500 Forest's; Func runs 10000 result: 0.12178250603909949
Score: 0.06889
=============================
5 Megacity's; Func runs 10000 result: 5.359999999999999
Score: 0.44667
25 Megacity's; Func runs 10000 result: 1.552
Score: 0.12933
500 Megacity's; Func runs 10000 result: 0.38160000000000005
Score: 0.03180
=============================
All score: 4.06967
Визуализация алгоритма SDOm выявила некоторые отличительные особенности: график сходимости на всех тестовых функциях нестабилен, меняется характер кривой сходимости на протяжении всех итераций и это не повышает чувство уверенности в результатах. На визуализации работы с функцией Megacity я специально показал несколько повторных тестов (обычно на видео только один, что бы не получился GIF слишком объёмным), чтобы показать нестабильность результатов от теста к тесту, разброс в результатах очень велик.
В характере движения частиц никаких особенностей не замечено, за исключением острой Forest и дискретной Megacity, где координаты частиц выстраиваются в хорошо заметные линии. Сложно судить, хорошо это или плохо, например, в случае с алгоритмом ACOm это было признаком качественной сходимости, но в случае с SDOm этого сказать нельзя.
SDOm на тестовой функции Rastrigin.
SDOm на тестовой функции Forest.
SDOm на тестовой функции Megacity.
При использовании закомментированного в методе Moving кода, который отвечает за добавление случайного шума к координате частицы, происходит интересное явление, похожее на фейерверк, при этом случайное изменение фазы колебаний не используется. Предполагаю, что после массового схождения частиц к известному решению, происходит их выброс в разные стороны, этим и обусловлен красивый эффект, демонстрирующий застревание алгоритма. Это видно по совпадению момента взрыва фейерверка с началом горизонтального участка графика сходимости.
Демонстрация бесполезного, но красивого эффекта "фейерверка".
Алгоритм SDOm показал достаточно хорошие результаты в целом и оказался на 8 месте из 23 участвующих в обзоре рейтинговой таблицы. SDOm демонстрирует заметно лучшие результаты на гладкой функции Rastrigin. Склонность к застреванию не способствует отличным результатам на сложных функциях Forest и Megacity.
№ | AO | Description | Rastrigin | Rastrigin final | Forest | Forest final | Megacity (discrete) | Megacity final | Final result | ||||||
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 | SDSm | stochastic diffusion search M | 0,99809 | 1,00000 | 0,69149 | 2,68958 | 1,00000 | 1,00000 | 1,00000 | 3,00000 | 1,00000 | 1,00000 | 1,00000 | 3,00000 | 100,000 |
2 | SDS | stochastic Diffusion Search | 0,99737 | 0,97322 | 0,58904 | 2,55963 | 0,96778 | 0,93572 | 0,79649 | 2,69999 | 0,78696 | 0,93815 | 0,71804 | 2,44315 | 88,208 |
3 | SSG | saplings sowing and growing | 1,00000 | 0,92761 | 0,51630 | 2,44391 | 0,72654 | 0,65201 | 0,83760 | 2,21615 | 0,54782 | 0,61841 | 0,99522 | 2,16146 | 77,678 |
4 | HS | harmony search | 0,99676 | 0,88385 | 0,44686 | 2,32747 | 0,99882 | 0,68242 | 0,37529 | 2,05653 | 0,71739 | 0,71842 | 0,41338 | 1,84919 | 70,647 |
5 | IWO | invasive weed optimization | 0,95828 | 0,62227 | 0,27647 | 1,85703 | 0,70690 | 0,31972 | 0,26613 | 1,29275 | 0,57391 | 0,30527 | 0,33130 | 1,21048 | 48,267 |
6 | ACOm | ant colony optimization M | 0,34611 | 0,16683 | 0,15808 | 0,67103 | 0,86785 | 0,68980 | 0,64798 | 2,20563 | 0,71739 | 0,63947 | 0,05579 | 1,41265 | 47,419 |
7 | MEC | mind evolutionary computation | 0,99270 | 0,47345 | 0,21148 | 1,67763 | 0,60691 | 0,28046 | 0,21324 | 1,10061 | 0,66957 | 0,30000 | 0,26045 | 1,23002 | 44,061 |
8 | SDOm | spiral dynamics optimization M | 0,81076 | 0,56474 | 0,35334 | 1,72884 | 0,72333 | 0,30644 | 0,30985 | 1,33963 | 0,43479 | 0,13289 | 0,14695 | 0,71463 | 41,370 |
9 | COAm | cuckoo optimization algorithm M | 0,92400 | 0,43407 | 0,24120 | 1,59927 | 0,58309 | 0,23477 | 0,13842 | 0,95629 | 0,52174 | 0,24079 | 0,17001 | 0,93254 | 37,845 |
10 | FAm | firefly algorithm M | 0,59825 | 0,31520 | 0,15893 | 1,07239 | 0,51012 | 0,29178 | 0,41704 | 1,21894 | 0,24783 | 0,20526 | 0,35090 | 0,80398 | 33,152 |
11 | ABC | artificial bee colony | 0,78170 | 0,30347 | 0,19313 | 1,27829 | 0,53774 | 0,14799 | 0,11177 | 0,79750 | 0,40435 | 0,19474 | 0,13859 | 0,73768 | 29,784 |
12 | BA | bat algorithm | 0,40526 | 0,59145 | 0,78330 | 1,78002 | 0,20817 | 0,12056 | 0,21769 | 0,54641 | 0,21305 | 0,07632 | 0,17288 | 0,46225 | 29,488 |
13 | CSS | charged system search | 0,56605 | 0,68683 | 1,00000 | 2,25289 | 0,14065 | 0,01853 | 0,13638 | 0,29555 | 0,07392 | 0,00000 | 0,03465 | 0,10856 | 27,914 |
14 | GSA | gravitational search algorithm | 0,70167 | 0,41944 | 0,00000 | 1,12111 | 0,31623 | 0,25120 | 0,27812 | 0,84554 | 0,42609 | 0,25525 | 0,00000 | 0,68134 | 27,807 |
15 | BFO | bacterial foraging optimization | 0,67203 | 0,28721 | 0,10957 | 1,06881 | 0,39655 | 0,18364 | 0,17298 | 0,75317 | 0,37392 | 0,24211 | 0,18841 | 0,80444 | 27,549 |
16 | EM | electroMagnetism-like algorithm | 0,12235 | 0,42928 | 0,92752 | 1,47915 | 0,00000 | 0,02413 | 0,29215 | 0,31628 | 0,00000 | 0,00527 | 0,10872 | 0,11399 | 18,981 |
17 | SFL | shuffled frog-leaping | 0,40072 | 0,22021 | 0,24624 | 0,86717 | 0,20129 | 0,02861 | 0,02221 | 0,25211 | 0,19565 | 0,04474 | 0,06607 | 0,30646 | 13,201 |
18 | MA | monkey algorithm | 0,33192 | 0,31029 | 0,13582 | 0,77804 | 0,10000 | 0,05443 | 0,07482 | 0,22926 | 0,15652 | 0,03553 | 0,10669 | 0,29874 | 11,771 |
19 | FSS | fish school search | 0,46812 | 0,23502 | 0,10483 | 0,80798 | 0,12825 | 0,03458 | 0,05458 | 0,21741 | 0,12175 | 0,03947 | 0,08244 | 0,24366 | 11,329 |
20 | IWDm | intelligent water drops M | 0,26459 | 0,13013 | 0,07500 | 0,46972 | 0,28568 | 0,05445 | 0,05112 | 0,39126 | 0,22609 | 0,05659 | 0,05054 | 0,33322 | 10,434 |
21 | PSO | particle swarm optimisation | 0,20449 | 0,07607 | 0,06641 | 0,34696 | 0,18873 | 0,07233 | 0,18207 | 0,44313 | 0,16956 | 0,04737 | 0,01947 | 0,23641 | 8,431 |
22 | RND | random | 0,16826 | 0,09038 | 0,07438 | 0,33302 | 0,13480 | 0,03318 | 0,03949 | 0,20747 | 0,12175 | 0,03290 | 0,04898 | 0,20363 | 5,056 |
23 | GWO | grey wolf optimizer | 0,00000 | 0,00000 | 0,02093 | 0,02093 | 0,06562 | 0,00000 | 0,00000 | 0,06562 | 0,23478 | 0,05789 | 0,02545 | 0,31812 | 1,000 |
Выводы
Оригинальный подход к реализации модифицированной версии позволил избежать тяжелых матричных вычислений как в исходном авторском алгоритме, а также позволил сделать его универсальным без привязки к взаимосвязям между координатами для n-мерного пространства.Мной были предприняты попытки использовать понятия "массы" в формуле затухающих гармонических колебаний, с целью сделать индивидуальным поведение частиц в зависимости от их приспособленности. Идея состояла в том, чтобы снизить амплитуду и частоту частичкам с большей массой (с лучшим значением фитнес функции), при этом легкие частицы должны были бы совершать более размашистые по амплитуде движения и с более высокой частотой. Это могло бы обеспечить более высокую степень уточнения известных лучших решений, и в то же время повысить поисковые способности за счет "широких" движений легких частиц. К сожалению, в результате тестирования эта идея не принесла ожидаемого улучшения результатов.
Физическое моделирование траекторий движения частиц в алгоритме наводит на мысль о возможности применения таких физических понятий, как скорость, ускорение и инерция. Это вопрос дальнейших исследований для такого интересного алгоритма, как SDO.
Рисунок 5. Цветовая градация алгоритмов по соответствующим тестам.
Рисунок 6. Гистограмма результатов тестирования алгоритмов (по шкале от 0 до 100, чем больше, тем лучше,
в архиве скрипт для расчета рейтинговой таблицы по методике в этой статье).
Плюсы и минусы модифицированного алгоритма оптимизации спиральной динамики (SDOm):
Плюсы:
1. Небольшое количество внешних параметров.
2. Простая реализация.
3. Скорость работы.
Минусы:
1. Высокий разброс результатов.
2. Склонность к застреванию в локальных экстремумах.
К статье прикреплен архив с обновленными актуальными версиями кодов алгоритмов, описанных в предыдущих статьях. Автор статьи не несёт ответственности за абсолютную точность в описании канонических алгоритмов, во многие из них были внесены изменения для улучшения поисковых возможностей. Выводы и суждения, представленные в статьях, основываются на результатах проведённых экспериментов.





- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Вы принимаете политику сайта и условия использования
Андрей, где ты это берешь
это на свой ум вопрос
О чем ты?))
это про все эти варианты для работы,
я то вроде много умею, но удивляюсь Вашим знаниям каждый раз
это про все эти варианты для работы,
я то вроде много умею, но удивляюсь Вашим знаниям каждый раз
Большое спасибо.
Вы преувеличиваете, "я не волшебник, а только учусь".
Большое спасибо.
Вы преувеличиваете, "я не волшебник, а только учусь".
у меня есть команда топеров игровых, которые маил не могли забанить по многочисленным требованиям
вот не знаю куда этих уникальных можно деть
пропадут зря,