Алгоритм кометного следа (Comet Tail Algorithm, CTA)
Содержание:
1.Введение
2.Реализация алгоритма
3.Результаты тестов
1. Введение
В мире астрономии кометы всегда вызывали особый интерес у ученых и исследователей. Эти уникальные космические объекты, состоящие в основном изо льда, пыли и газов, представляют собой важный источник информации о процессах, происходящих в космическом пространстве. Одним из наиболее заметных и впечатляющих аспектов комет является их хвост, который формируется при приближении кометы к Солнцу.
Солнце играет ключевую роль в формировании кометного хвоста. Его излучение и солнечный ветер вызывают испарение и разрушение материала на поверхности кометы. Этот процесс приводит к образованию кометного хвоста — области, состоящей из пыли, газов и ионизированных частиц, которые отдаляются от кометы под воздействием солнечного ветра и силы гравитации Солнца.
В этой статье мы рассмотрим авторский алгоритм оптимизации CTA (Comet Tail Algorithm), который был вдохновлен этим уникальным астрономическим явлением. Алгоритм CTA использует концепцию движения комет и их хвостов для поиска оптимальных решений в задачах оптимизации. Мы подробно рассмотрим движение кометы и ее хвоста, а также роль Солнца в этих процессах. Мы также обсудим, как эти концепции применяются в алгоритме CTA для эффективного поиска оптимальных решений.
Кометы — это малые тела Солнечной системы, которые, приближаясь к Солнцу, начинают испаряться и выделять газы. Этот процесс называется сублимацией. Кометы обычно имеют очень эллиптические орбиты, и они имеют широкий диапазон периодов обращения, от нескольких лет до потенциально нескольких миллионов лет.
Движение кометы и ее хвоста тесно связано с воздействием Солнца. Тепло Солнца вызывает превращение льда кометы в газы, заставляя кому (газовая оболочка, окружающая ядро кометы) увеличиваться. Давление солнечного излучения и высокоскоростных солнечных частиц (солнечный ветер) может унести пыль и газ комы от Солнца, иногда формируя длинный, яркий хвост. Кроме того, солнечное излучение и солнечный ветер вызывают ионизацию газов в хвосте кометы, что приводит к его свечению.
В контексте алгоритма CTA, мы можем представить каждое решение как частицы хвоста кометы, движущиеся в пространстве решений. Ядро кометы представляет собой наилучшее решение, а частицы в хвосте — производные решения, отходящие от ядра. Такое представление позволяет алгоритму "изучать" пространство решений и адаптироваться к его особенностям.
2.Реализация алгоритма
Давайте более подробно рассмотрим движение кометы и ее хвоста, которые являются ключевыми элементами в этом алгоритме, а также роль Солнца в этих процессах.
Движение кометы:
- Комета движется по эллиптической орбите вокруг Солнца.
- Когда комета приближается к Солнцу, она начинает испускать газ и пыль, формируя кометный хвост.
- Движение кометы определяется гравитационным притяжением Солнца, а также отталкиванием от солнечного ветра и солнечного излучения.
- Комета движется по своей орбите, а ее хвост всегда направлен в сторону, противоположную Солнцу.
Движение хвоста кометы:
- Газовый хвост кометы состоит из ионизированных газов, которые "выбрасываются" из ядра кометы под действием солнечного ветра.
- Солнечный ветер - поток заряженных частиц, исходящих от Солнца. Он "сдувает" газовый хвост кометы, направляя его в сторону, противоположную Солнцу.
- Пылевой хвост кометы состоит из более крупных частиц, которые "выбрасываются" из ядра кометы под действием солнечного излучения.
- Солнечное излучение оказывает давление на пылевые частицы, слегка отклоняя их от направления движения кометы, формируя изогнутый пылевой хвост.
Роль Солнца:
- Солнце является центральным объектом, вокруг которого движется комета по своей орбите.
- Гравитационное притяжение Солнца определяет движение кометы по эллиптической орбите.
- Солнечный ветер и солнечное излучение "формируют" кометный хвост, направляя его в сторону, противоположную Солнцу.
Рисунок 1. Форма и размер комет в контексте алгоритма CTA в зависимости от расстояния до звезды (лучшего глобального решения).
Комета под номером 1 слишком близко приблизилась к светилу и испарилась. Однако, в алгоритме уничтожение кометы на самом деле не происходит. Вместо этого продолжает действовать формирование облака хвоста с центром, соответствующим центру звезды. Это означает, что чем меньше облако хвоста, тем интенсивнее происходит уточнение решения в области кометы. И наоборот, чем больше размер хвоста, тем более интенсивно происходит исследование пространства поиска. При этом оси эллипсов всех комет всегда направлены в сторону от звезды, то есть в сторону от текущего лучшего глобального решения.
Логика алгоритма позволяет регулировать коэффициенты расширения облаков комет как в сторону расширения с удалением от звезды, так и в сторону уменьшения. Также можно отрегулировать степень уплощения эллипсов в зависимости от радиуса орбиты кометы. Даже можно направить хвост кометы не в сторону от звезды, а в сторону к звезде (при желании).
На рисунке 1 также показан момент условной миграции кометы под номером 2 на новую орбиту (окаймленная цифра 2). Это происходит в процессе обмена веществом ядер двух комет. На рисунке комета 2 заимствует вещество кометы 4. Если в процессе обмена веществом между кометами будет найдено лучшее решение, то соответствующая комета, формирование вещества которой происходило в данный момент, переходит на новую орбиту.
Размер хвоста кометы и его смещение относительно ядра в зависимости от расстояния до звезды можно условно рассчитать по линейному закону. При этом максимальное расстояние, равное 1, соответствует диапазону минимального и максимального значений по соответствующей оптимизируемой координате задачи. Данный подход позволяет описать изменение параметров хвоста кометы в зависимости от расстояния до звезды простым и наглядным способом.
Рисунок 2. Графики зависимости коэффициентов смещения следа кометы (фиолетовый) и размера следа (зелёный) в зависимости от расстояния до звезды.
Итак, мы разработали законы изменения формы и размера облака частиц для комет, поэтому можем суммировать выводы о возможных свойствах алгоритма. Основные свойства алгоритма, инспирированного следом кометы, с учетом направления хвоста от Солнца (глобального оптимума) и поиска не только лучших, но и в области менее оптимальных решений, могут быть следующими:
1. Испарение и эволюция решений. Алгоритм может использовать процесс испарения и эволюции решений, при котором как лучшие, так и области менее оптимальных решений могут быть исследованы.
2. Многовариантность. Алгоритм может стремиться к созданию множества вариантов решений, отражающих различные уровни оптимальности, аналогично разнообразию состава в кометном хвосте.
3. Адаптивность к внешним факторам. Как комета реагирует на воздействие Солнца, алгоритм может быть адаптивным к изменениям в окружающей среде или целевой функции.
4. Поиск глобального оптимума. Направление хвоста от Солнца может символизировать стремление алгоритма к поиску глобального оптимума, но при этом учитывая и менее оптимальные решения, чтобы избежать преждевременной сходимости к локальным оптимумам.
Напишем набросок алгоритма в виде псевдокода:
1. Создать ядра комет случайным образом.
2. От ядер комет создать их хвосты - частицы с нормальным распределением с ядром в центре.
3. Вычислить приспособленность частиц комет.
4. Обновить глобальное решение.
5. Назначить лучшую из частиц соответствующей кометы её ядром.
6. Для каждой координаты частиц комет выполнить следующее:
С вероятностью 0.6 выполнить либо:
Создать частицы с нормальным распределением с ядром кометы в центре.
Либо:
Создать частицу кометы используя координаты ядер двух случайно выбранных комет.
7. Обновить глобальное решение.
8. Назначить лучшую из частиц соответствующей кометы её ядром.
9. Повторять с п. 6 до выполнения критерия останова.
Для алгоритма CTA не понадобится писать специфичную структуру, для описания комет и их частиц, нам вполне подойдет базовая структура агента, используемая для обмена решениями между алгоритмом и исполняющей программой. Вспомним, как выглядит эта структура.
Структура "S_AO_Agent"содержит два поля:
- c[] - массив хранит координаты агента в пространстве решений.
- f - значение приспособленности (fitness) агента, которое используется для оценки качества решения.
В контексте алгоритма CTA этой структурой мы опишем как сами кометы, так и частицы их хвостов.
//—————————————————————————————————————————————————————————————————————————————— struct S_AO_Agent { double c []; //coordinates double f; //fitness }; //——————————————————————————————————————————————————————————————————————————————
Определим класс "C_AO_CTA", который является наследником класса "C_AO".
- C_AO_CTA () - конструктор инициализирует объект класса с предопределенными значениями. Он также устанавливает некоторые параметры алгоритма, такие как размер популяции "popSize", количество комет "cometsNumb", коэффициент длины хвоста "tailLengthKo", максимальный и минимальный коэффициенты сдвига "maxShiftCoef" и "minShiftCoef", а также максимальный и минимальный коэффициенты размера "maxSizeCoef" и "minSizeCoef".
- SetParams() устанавливает параметры алгоритма на основе значений в массиве "params".
- Init() - инициализирует алгоритм с заданными диапазонами поиска и количеством эпох.
- Методы "Moving()", "Revision()" - эти методы реализуют основную логику алгоритма.
Поле "comets[]" является массивом объектов типа "S_AO_Agent", который представляет кометы в алгоритме.
Приватные поля "tailLength[]", "maxSpaceDistance[]", "partNumber" используются для внутренней работы алгоритма.
//—————————————————————————————————————————————————————————————————————————————— class C_AO_CTA : public C_AO { public: //-------------------------------------------------------------------- ~C_AO_CTA () { } C_AO_CTA () { ao_name = "CTA"; ao_desc = "Comet Tail Algorithm"; ao_link = "https://www.mql5.com/ru/articles/14841"; popSize = 50; //population size cometsNumb = 5; //number of comets tailLengthKo = 0.2; //tail length coefficient maxShiftCoef = 0.9; minShiftCoef = 0.5; maxSizeCoef = 0.1; minSizeCoef = 1.5; ArrayResize (params, 7); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "cometsNumb"; params [1].val = cometsNumb; params [2].name = "tailLengthKo"; params [2].val = tailLengthKo; params [3].name = "maxShiftCoef"; params [3].val = maxShiftCoef; params [4].name = "minShiftCoef"; params [4].val = minShiftCoef; params [5].name = "maxSizeCoef"; params [5].val = maxSizeCoef; params [6].name = "minSizeCoef"; params [6].val = minSizeCoef; } void SetParams () { popSize = (int)params [0].val; cometsNumb = (int)params [1].val; tailLengthKo = params [2].val; maxShiftCoef = params [3].val; minShiftCoef = params [4].val; maxSizeCoef = params [5].val; minSizeCoef = params [6].val; } bool Init (const double &rangeMinP [], //minimum search range const double &rangeMaxP [], //maximum search range const double &rangeStepP [], //step search const int epochsP = 0); //number of epochs void Moving (); void Revision (); void Injection (const int popPos, const int coordPos, const double value); //---------------------------------------------------------------------------- int cometsNumb; //number of comets double tailLengthKo; //tail length coefficient double maxShiftCoef; //maximum shift coefficient double minShiftCoef; //minimum shift coefficient double maxSizeCoef; //maximum size coefficient double minSizeCoef; //minimum size coefficient S_AO_Agent comets []; private: //------------------------------------------------------------------- int epochs; int epochNow; double tailLength []; double maxSpaceDistance []; //maximum distance in space int partNumber; //number of particles }; //——————————————————————————————————————————————————————————————————————————————
Определим метод "Init" в классе "C_AO_CTA". Этот метод инициализирует алгоритм с заданными диапазонами поиска и количеством эпох. Описание каждого шага:
1. "if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false;" - этот код вызывает метод "StandardInit" с заданными диапазонами поиска. Если "StandardInit" возвращает "false", то метод "Init" также немедленно возвращает "false".
2. "ArrayResize (comets, cometsNumb);" - изменение размера массива "comets" в соответствии с количеством комет.
3. Внутри цикла "for", для каждой кометы инициализируются ее координаты и значение функции приспособленности.
4. "ArrayResize (tailLength, coords); ArrayResize (maxSpaceDistance, coords);" - изменяется размер массивов "tailLength" и "maxSpaceDistance" в соответствии с количеством координат.
5. Внутри следующего цикла "for", для каждой координаты вычисляются максимальное расстояние в пространстве и длина хвоста.
6. "partNumber = popSize / cometsNumb;" - вычисляется количество частиц в хвосте каждой кометы.
//—————————————————————————————————————————————————————————————————————————————— bool C_AO_CTA::Init (const double &rangeMinP [], //minimum search range const double &rangeMaxP [], //maximum search range const double &rangeStepP [], //step search const int epochsP = 0) //number of epochs { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //---------------------------------------------------------------------------- epochs = epochsP; epochNow = 0; ArrayResize (comets, cometsNumb); for (int i = 0; i < cometsNumb; i++) { ArrayResize (comets [i].c, coords); comets [i].f = -DBL_MAX; } ArrayResize (tailLength, coords); ArrayResize (maxSpaceDistance, coords); for (int i = 0; i < coords; i++) { maxSpaceDistance [i] = rangeMax [i] - rangeMin [i]; tailLength [i] = maxSpaceDistance [i] * tailLengthKo; } partNumber = popSize / cometsNumb; return true; } //——————————————————————————————————————————————————————————————————————————————
Образование частиц в хвостах комет происходит в методе "Moving()" класса "C_AO_CTA". Основные шаги метода:
1. Функция начинается с увеличения счетчика эпох "epochNow" и инициализации локальных переменных "cnt", "min", и "max".
2. Если "revision" равен "false", то происходит инициализация координат комет в пределах заданных диапазонов "rangeMin" и "rangeMax". Затем создаются частицы (агенты) вокруг каждой кометы, используя гауссово распределение в пределах диапазона, определяемого длиной хвоста "tailLength".
3. Если "revision" равен "true", то происходит обновление положения частиц (агентов). Для каждой частицы вычисляются коэффициенты "coefTail" и "coefSize", которые определяют смещение и размер хвоста кометы в зависимости от расстояния до центральной точки "cB". Эти коэффициенты используются для определения нового положения частицы в пределах диапазона, ограниченного длиной хвоста.
4. Если вероятность "u.RNDprobab()" меньше 0.6, то новое положение частицы вычисляется с использованием гауссова распределения. В противном случае новое положение частицы вычисляется как линейная комбинация координат ядер двух других случайно выбранных комет.
5. Во всех случаях, новые координаты частицы ограничиваются диапазонами "rangeMin" и "rangeMax" и дискретизируются с шагом "rangeStep".
Общая идея этого метода заключается в моделировании движения и поведения комет в алгоритме CTA, где частицы (агенты) представляют собой хвост кометы, а их координаты и размер хвоста зависят от расстояния до глобального лучшего решения (Солнце).
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CTA::Moving () { epochNow++; int cnt = 0; double min = 0.0; double max = 0.0; //---------------------------------------------------------------------------- if (!revision) { for (int i = 0; i < cometsNumb; i++) { for (int c = 0; c < coords; c++) { comets [i].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]); comets [i].c [c] = u.SeInDiSp (comets [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } for (int i = 0; i < cometsNumb; i++) { for (int p = 0; p < partNumber; p++) { for (int c = 0; c < coords; c++) { min = comets [i].c [c] - tailLength [c] * 0.5; if (min < rangeMin [c]) min = rangeMin [c]; max = comets [i].c [c] + tailLength [c] * 0.5; if (max > rangeMax [c]) max = rangeMax [c]; a [cnt].c [c] = u.GaussDistribution (comets [i].c [c], min, max, 1); a [cnt].c [c] = u.SeInDiSp (a [cnt].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } cnt++; } } revision = true; return; } //---------------------------------------------------------------------------- cnt = 0; double coefTail = 0.0; double coefSize = 0.0; for (int i = 0; i < cometsNumb; i++) { for (int p = 0; p < partNumber; p++) { for (int c = 0; c < coords; c++) { if (u.RNDprobab () < 0.6) { coefTail = fabs (comets [i].c [c] - cB [c]) / maxSpaceDistance [c]; coefSize = coefTail; //(1-x)*0.9+x*0.5 coefTail = (1 - coefTail) * maxShiftCoef + coefTail * minShiftCoef; //(1-x)*0.1+x*0.9 coefSize = (1 - coefSize) * maxSizeCoef + coefSize * minSizeCoef; if (cB [c] * Dir > comets [i].c [c] * Dir) { min = comets [i].c [c] - tailLength [c] * coefTail * coefSize; max = comets [i].c [c] + tailLength [c] * (1.0 - coefTail) * coefSize; } if (cB [c] * Dir < comets [i].c [c] * Dir) { min = comets [i].c [c] - tailLength [c] * (1.0 - coefTail) * coefSize; max = comets [i].c [c] + tailLength [c] * (coefTail)*coefSize; } if (cB [c] == comets [i].c [c]) { min = comets [i].c [c] - tailLength [c] * 0.1; max = comets [i].c [c] + tailLength [c] * 0.1; } if (min < rangeMin [c]) min = rangeMin [c]; if (max > rangeMax [c]) max = rangeMax [c]; a [cnt].c [c] = u.GaussDistribution (comets [i].c [c], min, max, Power); a [cnt].c [c] = u.SeInDiSp (a [cnt].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } else { int r = 0; int r1 = 0; int r2 = 0; do { r = u.RNDminusOne (cometsNumb); r1 = r; } while (r1 == i); do { r = u.RNDminusOne (cometsNumb); r2 = r; } while (r2 == i || r2 == r1); a [cnt].c [c] = comets [r1].c [c] + 0.1 * (comets [r2].c [c] - comets [i].c [c]) * u.RNDprobab(); a [cnt].c [c] = u.SeInDiSp (a [cnt].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } cnt++; } } } //——————————————————————————————————————————————————————————————————————————————
Далее реализуем метод "Revision()" класса "C_AO_CTA", который отвечает за пересмотр положения комет в алгоритме Comet Tail Algorithm (CTA).
Основные шаги метода:
1. Поиск лучшего решения в популяции:
- Метод проходит по всем решениям в популяции "popSize" и находит решение с наилучшим значением целевой функции "fB".
- Если найдено лучшее решение, то его положение "a[ind].c" копируется в вектор "cB", который хранит лучшее известное решение.
2. Обновление положения комет:
- Метод проходит по всем кометам "cometsNumb" и для каждой кометы ищет лучшее решение среди частиц, связанных с этой кометой "partNumber".
- Если найдено лучшее решение для кометы, то положение этой кометы "comets[i].c" обновляется на положение найденного лучшего решения "a[ind].c".
Этот метод реализует важный шаг алгоритма CTA, где происходит пересмотр положения комет на основе лучших найденных решений в их хвостах. Это позволяет направлять поиск к областям с более высокими значениями целевой функции.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CTA::Revision () { int ind = -1; for (int i = 0; i < popSize; i++) { if (a [i].f > fB) { fB = a [i].f; ind = i; } } if (ind != -1) ArrayCopy (cB, a [ind].c, 0, 0, WHOLE_ARRAY); //set a new kernel------------------------------------------------------------ int cnt = 0; for (int i = 0; i < cometsNumb; i++) { ind = -1; for (int p = 0; p < partNumber; p++) { if (a [cnt].f > comets [i].f) { comets [i].f = a [cnt].f; ind = cnt; } cnt++; } if (ind != -1) ArrayCopy (comets [i].c, a [ind].c, 0, 0, WHOLE_ARRAY); } } //——————————————————————————————————————————————————————————————————————————————
3. Результаты тестов
Распечатка результатов работы алгоритма кометного следа CTA:
CTA|Comet Tail Algorithm|80.0|40.0|4.0|-1.0|0.2|1.0|0.5|0.1|15.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.9534613588697962
25 Hilly's; Func runs: 10000; result: 0.863192334000326
500 Hilly's; Func runs: 10000; result: 0.27769783965091077
=============================
5 Forest's; Func runs: 10000; result: 0.997942251272262
25 Forest's; Func runs: 10000; result: 0.857403562283056
500 Forest's; Func runs: 10000; result: 0.33949224947400775
=============================
5 Megacity's; Func runs: 10000; result: 0.8876923076923078
25 Megacity's; Func runs: 10000; result: 0.5643076923076924
500 Megacity's; Func runs: 10000; result: 0.10512307692307787
=============================
All score: 5.84631 (64.96%)
Исходя из проведённых тестов можно сделать следующие выводы о работе алгоритма оптимизации CTA (Comet Tail Algorithm):
Общая оценка алгоритма составляет 5.84631, что соответствует 64.96% от максимально возможного балла. Это указывает на отличную эффективность алгоритма CTA.
CTA на тестовой функции Hilly.
CTA на тестовой функции Forest.
CTA на тестовой функции Megacity.
По итогам тестирования алгоритм CTA занимает достойное 3-тье место в рейтинговой таблице.
№ | 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 | BGA | binary genetic algorithm | 0,99992 | 0,99484 | 0,50483 | 2,49959 | 1,00000 | 0,99975 | 0,32054 | 2,32029 | 0,90667 | 0,96400 | 0,23035 | 2,10102 | 6,921 | 76,90 |
2 | (P+O)ES | (P+O) evolution strategies | 0,99934 | 0,91895 | 0,56297 | 2,48127 | 1,00000 | 0,93522 | 0,39179 | 2,32701 | 0,83167 | 0,64433 | 0,21155 | 1,68755 | 6,496 | 72,18 |
3 | CTA | comet tail algorithm | 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 |
4 | 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 |
5 | ESG | evolution of social groups | 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 |
6 | SIA | simulated isotropic annealing | 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 |
7 | TSEA | turtle shell evolution algorithm | 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 |
8 | 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 |
9 | BSA | bird swarm algorithm | 0,90857 | 0,73661 | 0,25767 | 1,90285 | 0,90437 | 0,81619 | 0,16401 | 1,88457 | 0,61692 | 0,54154 | 0,10951 | 1,26797 | 5,055 | 56,17 |
10 | 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 |
11 | 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 |
12 | (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 |
13 | BSO | brain storm optimization | 0,91301 | 0,56222 | 0,30047 | 1,77570 | 0,97162 | 0,57162 | 0,23449 | 1,77772 | 0,60462 | 0,27138 | 0,12011 | 0,99611 | 4,550 | 50,55 |
14 | 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 |
15 | 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 |
16 | BFO-GA | bacterial foraging optimization - ga | 0,89150 | 0,55111 | 0,31529 | 1,75790 | 0,96982 | 0,39612 | 0,06305 | 1,42899 | 0,72667 | 0,27500 | 0,03525 | 1,03692 | 4,224 | 46,93 |
17 | MEC | mind evolutionary computation | 0,69533 | 0,53376 | 0,32661 | 1,55569 | 0,72464 | 0,33036 | 0,07198 | 1,12698 | 0,52500 | 0,22000 | 0,04198 | 0,78698 | 3,470 | 38,55 |
18 | IWO | invasive weed optimization | 0,72679 | 0,52256 | 0,33123 | 1,58058 | 0,70756 | 0,33955 | 0,07484 | 1,12196 | 0,42333 | 0,23067 | 0,04617 | 0,70017 | 3,403 | 37,81 |
19 | Micro-AIS | micro artificial immune system | 0,79547 | 0,51922 | 0,30861 | 1,62330 | 0,72956 | 0,36879 | 0,09398 | 1,19233 | 0,37667 | 0,15867 | 0,02802 | 0,56335 | 3,379 | 37,54 |
20 | COAm | cuckoo optimization algorithm M | 0,75820 | 0,48652 | 0,31369 | 1,55841 | 0,74054 | 0,28051 | 0,05599 | 1,07704 | 0,50500 | 0,17467 | 0,03380 | 0,71347 | 3,349 | 37,21 |
21 | SDOm | spiral dynamics optimization M | 0,74601 | 0,44623 | 0,29687 | 1,48912 | 0,70204 | 0,34678 | 0,10944 | 1,15826 | 0,42833 | 0,16767 | 0,03663 | 0,63263 | 3,280 | 36,44 |
22 | NMm | Nelder-Mead method M | 0,73807 | 0,50598 | 0,31342 | 1,55747 | 0,63674 | 0,28302 | 0,08221 | 1,00197 | 0,44667 | 0,18667 | 0,04028 | 0,67362 | 3,233 | 35,92 |
23 | FAm | firefly algorithm M | 0,58634 | 0,47228 | 0,32276 | 1,38138 | 0,68467 | 0,37439 | 0,10908 | 1,16814 | 0,28667 | 0,16467 | 0,04722 | 0,49855 | 3,048 | 33,87 |
24 | GSA | gravitational search algorithm | 0,64757 | 0,49197 | 0,30062 | 1,44016 | 0,53962 | 0,36353 | 0,09945 | 1,00260 | 0,32667 | 0,12200 | 0,01917 | 0,46783 | 2,911 | 32,34 |
25 | BFO | bacterial foraging optimization | 0,61171 | 0,43270 | 0,31318 | 1,35759 | 0,54410 | 0,21511 | 0,05676 | 0,81597 | 0,42167 | 0,13800 | 0,03195 | 0,59162 | 2,765 | 30,72 |
26 | ABC | artificial bee colony | 0,63377 | 0,42402 | 0,30892 | 1,36671 | 0,55103 | 0,21874 | 0,05623 | 0,82600 | 0,34000 | 0,14200 | 0,03102 | 0,51302 | 2,706 | 30,06 |
27 | BA | bat algorithm | 0,59761 | 0,45911 | 0,35242 | 1,40915 | 0,40321 | 0,19313 | 0,07175 | 0,66810 | 0,21000 | 0,10100 | 0,03517 | 0,34617 | 2,423 | 26,93 |
28 | SA | simulated annealing | 0,55787 | 0,42177 | 0,31549 | 1,29513 | 0,34998 | 0,15259 | 0,05023 | 0,55280 | 0,31167 | 0,10033 | 0,02883 | 0,44083 | 2,289 | 25,43 |
29 | IWDm | intelligent water drops M | 0,54501 | 0,37897 | 0,30124 | 1,22522 | 0,46104 | 0,14704 | 0,04369 | 0,65177 | 0,25833 | 0,09700 | 0,02308 | 0,37842 | 2,255 | 25,06 |
30 | PSO | particle swarm optimisation | 0,59726 | 0,36923 | 0,29928 | 1,26577 | 0,37237 | 0,16324 | 0,07010 | 0,60572 | 0,25667 | 0,08000 | 0,02157 | 0,35823 | 2,230 | 24,77 |
31 | Boids | boids algorithm | 0,43340 | 0,30581 | 0,25425 | 0,99346 | 0,35718 | 0,20160 | 0,15708 | 0,71586 | 0,27846 | 0,14277 | 0,09834 | 0,51957 | 2,229 | 24,77 |
32 | MA | monkey algorithm | 0,59107 | 0,42681 | 0,31816 | 1,33604 | 0,31138 | 0,14069 | 0,06612 | 0,51819 | 0,22833 | 0,08567 | 0,02790 | 0,34190 | 2,196 | 24,40 |
33 | SFL | shuffled frog-leaping | 0,53925 | 0,35816 | 0,29809 | 1,19551 | 0,37141 | 0,11427 | 0,04051 | 0,52618 | 0,27167 | 0,08667 | 0,02402 | 0,38235 | 2,104 | 23,38 |
34 | FSS | fish school search | 0,55669 | 0,39992 | 0,31172 | 1,26833 | 0,31009 | 0,11889 | 0,04569 | 0,47467 | 0,21167 | 0,07633 | 0,02488 | 0,31288 | 2,056 | 22,84 |
35 | RND | random | 0,52033 | 0,36068 | 0,30133 | 1,18234 | 0,31335 | 0,11787 | 0,04354 | 0,47476 | 0,25333 | 0,07933 | 0,02382 | 0,35648 | 2,014 | 22,37 |
36 | GWO | grey wolf optimizer | 0,59169 | 0,36561 | 0,29595 | 1,25326 | 0,24499 | 0,09047 | 0,03612 | 0,37158 | 0,27667 | 0,08567 | 0,02170 | 0,38403 | 2,009 | 22,32 |
37 | CSS | charged system search | 0,44252 | 0,35454 | 0,35201 | 1,14907 | 0,24140 | 0,11345 | 0,06814 | 0,42299 | 0,18333 | 0,06300 | 0,02322 | 0,26955 | 1,842 | 20,46 |
38 | EM | electroMagnetism-like algorithm | 0,46250 | 0,34594 | 0,32285 | 1,13129 | 0,21245 | 0,09783 | 0,10057 | 0,41085 | 0,15667 | 0,06033 | 0,02712 | 0,24412 | 1,786 | 19,85 |
Выводы
Рассмотренный алгоритм CTA основан на концепции движения комет и имеет ряд особенностей, которые противоречат физическим законам и эволюции комет. Влияние этих особенностей на конечные результаты работы алгоритма следует рассмотреть подробнее.
Одно из противоречий заключается в направлении хвоста кометы. В алгоритме CTA использование направления хвоста в сторону звезды (Dir_P = -1) в целом значительно улучшает его эффективность. Однако, использование направления хвоста от звезды также повышает способность алгоритма исследовать пространство. Энтузиасты методов оптимизации могут при желании рассмотреть возможность использования динамического коэффициента направления хвоста в зависимости от текущей эпохи. Стоит отметить, что направление хвоста от звезды обеспечивает лучшую сходимость на задачах малой размерности, в то время как направление к звезде более эффективно на задачах большой размерности.
Другим противоречием является размер хвоста кометы. В алгоритме CTA было выявлено, что динамическое изменение размера хвоста, увеличивая его с ростом расстояния до звезды, улучшает эффективность алгоритма. Это противоречит физическим законам, поскольку в реальности размер хвоста кометы увеличивается при приближении к Солнцу. Однако, такое динамическое изменение размера хвоста позволяет расширить область исследования пространства решений вокруг ядра кометы в отдалённых участках от глобального решения, увеличивая шансы на обнаружение перспективных решений и снижая вероятность застревания в локальных экстремумах. При приближении к звезде хвост кометы уменьшается, что усиливает интенсивность уточнения решения.
Алгоритм CTA также предусматривает обмен информацией между кометами, аналогично тому, как это происходит в природе, когда кометы захватывают частицы, оставленные другими кометами. Это дополнительная возможность алгоритма для исследования пространства решений. Были предприняты попытки использовать методы увеличения разнообразия популяции путем моделирования коронарных выбросов вещества звезды и использования комбинаторных свойств алгоритма путем заимствования координат одних комет у других.
Алгоритм CTA (Comet Tail Algorithm) представляет собой интересный новый подход к оптимизации, который использует концепцию движения комет. Алгоритм демонстрирует хорошую сходимость на различных типах функций (как на гладких, так и на дискретных), очень прост в реализации (структура алгоритма очень проста, что упрощает его программную реализацию), не требует значительных вычислительных ресурсов (поскольку не использует сортировку решений и не использует вычислений расстояний между всеми решениями, что позволяет применять его на широком круге задач), демонстрирует небольшой разброс результатов на дискретных функциях (стабильность и воспроизводимость результатов при работе с дискретными целевыми функциями, как в большинстве задач оптимизации торговых систем), но при этом алгоритм имеет много внешних параметров (таких, как размер хвоста кометы, коэффициенты смещения хвоста и направления и т.д.), на гладких функциях высокой размерности алгоритм может показывать не самые высокие результаты.
В целом, особенности алгоритма CTA заключаются в динамическом балансе между исследованием пространства решений и уточнением найденного глобального оптимума.
Таким образом, алгоритм CTA использует ряд упрощений и допущений, не соответствующих полностью физическим законам движения комет. Тем не менее, эти отступления от реальности позволяют повысить эффективность алгоритма в решении задач оптимизации, сохраняя при этом простоту реализации.
Рисунок 3. Цветовая градация алгоритмов по соответствующим тестам. Белым цветом подсвечены результаты больше или равные 0.99.
Рисунок 4. Гистограмма результатов тестирования алгоритмов (по шкале от 0 до 100, чем больше, тем лучше,
где 100 - максимально возможный теоретический результат, в архиве скрипт для расчета рейтинговой таблицы).
Плюсы и минусы алгоритма кометного следа (CTA):
Плюсы:
- Хорошая сходимость на различных типах функций.
- Простая реализация.
- Нетребователен к вычислительным ресурсам.
- Небольшой разброс результатов на дискретных функциях.
Минусы:
- Много внешних параметров.
- Невысокие результаты на гладких функциях высокой размерности.
Исходные коды
К статье прикреплен архив с актуальными версиями кодов алгоритмов. Автор статьи не несёт ответственности за абсолютную точность в описании канонических алгоритмов, во многие из них были внесены изменения для улучшения поисковых возможностей. Выводы и суждения, представленные в статьях, основываются на результатах проведённых экспериментов.
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Вы принимаете политику сайта и условия использования