Алгоритм Поиска Ворона — Crow Search Algorithm (CSA)
66
0
Введение
В данной статье рассмотрим алгоритм Crow Search Algorithm (CSA), идея которого мне показалась очень перспективной, это ройный метаэвристический метод, предложенный для глобальной оптимизации. CSA моделирует поведение ворон при сокрытии и поиске "тайников" с пищей. Алгоритм прост в реализации, имеет небольшое число параметров и породил множество модификаций и гибридных версий, мы рассмотрим оригинальную версию.
Алгоритм CSA был предложен Али Аскарзаде (Ali Askarzadeh) и опубликован в 2016 году в журнале "Computers & Structures (Elsevier)".
Реализация алгоритма
Представьте себе раннее утро в парке. На ветке сидит ворона — чёрная, блестящая, с глазами, в которых отражается мысль. Она не просто птица, она стратег. И это не просто пернатые, это настоящие аналитики в мире природы, самые умные из птиц. Интеллектуальное поведение этих пернатых вдохновило на создание Crow Search Algorithm (CSA), потому что они умеют делать то, что должен уметь хороший алгоритм: искать, запоминать, адаптироваться и не дать себя обмануть.
Навык 1: Память о тайниках. Ворона находит кусочек хлеба и прячет его под листьями. Она не просто бросает, она запоминает место. Через день ворона возвращается и точно знает, где искать. В алгоритме это означает, что каждая "ворона" (агент) хранит свою лучшую позицию как тайник. Это её личное сокровище, и она не забывает, где оно.
Навык 2: Слежка за другими. Другая ворона наблюдает. Она сидит на фонарном столбе и смотрит, куда первая спрятала свою еду. Потом, когда та улетит, она спустится и проверит. В CSA агент выбирает другого и пытается "проследовать" к его тайнику, ведь если тот нашёл хорошее решение, почему бы не проверить это?
Навык 3: Обман. Однако, первая ворона не так глупа. Она знает, что за ней могут наблюдать. Поэтому делает ложный манёвр — притворяется, что прячет еду под кустом, а на самом деле прячет её за камнем. В алгоритме аналогично: если агент "замечает, что за ним наблюдают", он уводит преследователя в случайное место. Это помогает алгоритму не застревать в одном решении — как будто ворона говорит: «Ты думал, я поведу тебя туда, где много вкусного? Ха, обманула!»
Навык 4: Адаптация. Вороны не действуют по шаблону. Сегодня они прячут еду в траве, завтра — в щели забора. Они пробуют, учатся, меняют стратегию. В CSA: параметры движения и поведения могут меняться. Алгоритм не стоит на месте — он адаптируется, как ворона, которая ищет лучший способ выжить.
В итоге, ворона — это не просто птица, а метафора интеллекта и Crow Search Algorithm — это не сухая формула. Это попытка перенести в мир чисел то, что вороны делают каждый день: "искать лучшее, защищать своё, учиться у других и быть достаточно хитрыми, чтобы не дать себя обмануть".
Рисунок 1. Иллюстрация работы алгоритма CSA
На иллюстрации выше показаны основные сценарии и правила работы алгоритма. После детального рассмотрения стратегий метода оптимизации CSA можем составить подробный псевдокод алгоритма.
- Задать параметры:
- N = количество ворон (размер популяции)
- max_iter = максимальное число итераций
- fl = длина полета (flight length)
- AP = вероятность осознания (awareness probability)
- d = размерность задачи
- Инициализировать популяцию:
- Для каждой вороны i от 1 до N:
- Позиция[i] = случайная позиция в пространстве поиска
- Вычислить фитнес позиции[i]
- Память[i] = Позиция[i] (изначально память равна текущей позиции)
- Фитнес_памяти[i] = фитнес позиции[i]
- Для каждой вороны i от 1 до N:
- Повторять для каждой итерации t от 1 до max_iter:
- Для каждой вороны i от 1 до N: a. Выбрать цель следования:
- Случайно выбрать ворону j (где j ≠ i)
- r = случайное число от 0 до 1
- Для каждой размерности k:
- ri = случайное число от 0 до 1
- Новая_позиция[i][k] = Позиция[i][k] + ri × fl × (Память[j][k] - Позиция[i][k])
- Новая_позиция[i] = случайная позиция в пространстве поиска
- Убедиться, что Новая_позиция[i] находится в границах
- Если вышла за границы - вернуть на границу
- Вычислить фитнес новых позиций:
- Для каждой вороны i:
- Фитнес_новый[i] = вычислить фитнес(Новая_позиция[i])
- Для каждой вороны i:
- Обновить память:
- Для каждой вороны i:
- ЕСЛИ Фитнес_новый[i] лучше, чем Фитнес_памяти[i]:
- Память[i] = Новая_позиция[i]
- Фитнес_памяти[i] = Фитнес_новый[i]
- ИНАЧЕ:
- Память не изменяется
- ЕСЛИ Фитнес_новый[i] лучше, чем Фитнес_памяти[i]:
- Для каждой вороны i:
- Обновить текущие позиции:
- Для каждой вороны i:
- Позиция[i] = Новая_позиция[i]
- Для каждой вороны i:
- Для каждой вороны i от 1 до N: a. Выбрать цель следования:
- Найти лучшее решение:
- Лучшее_решение = Память с наилучшим фитнесом среди всех ворон
- Вернуть Лучшее_решение
Перейдем к самому главному, написанию кода. Структура "S_CrowMemory" предназначена для хранения информации о "памяти" вороны:
- Размерность позиции— сколько координат составляет одну "позицию" в этой памяти.
- Значения координат позиции— массив, где каждое число представляет собой конкретное значение координаты в этой позиции.
- Значение пригодности (фитнес)— характеризует, насколько "хороша" или "пригодна" данная позиция.
Метод "Init" служит для инициализации этой структуры. При его вызове передается количество измерений (dimensions). Этот метод выделяет необходимое место для хранения координат позиции, исходя из полученного количества измерений, и устанавливает начальное значение пригодности в очень маленькое число (максимально возможное отрицательное значение), чтобы любая полученная реальная оценка пригодности была больше.
//———————————————————————————————————————————————————————————————————— // Структура для хранения памяти вороны struct S_CrowMemory { double position[]; // позиция в памяти double fitness; // фитнес позиции в памяти void Init(int dimensions) { ArrayResize(position, dimensions); fitness = -DBL_MAX; } }; //————————————————————————————————————————————————————————————————————
Класс "C_AO_CrowSearchAlgorithm" представляет собой реализацию алгоритма поиска на основе поведения ворон. Он наследуется от базового класса "C_AO". При создании объекта класса, помимо установки имени и описания, инициализируются основные параметры алгоритма:
- popSize — количество агентов (ворон) в популяции,
- flightLength — параметр, определяющий дальность перемещения вороны во время полета,
- awarenessProbability — вероятность того, что ворона "осознает" свое окружение и действия других ворон.
- SetParams () — метод предназначен для обновления внутренних параметров алгоритма из внешнего источника (из массива "params").
- Init () — является основной точкой инициализации всего алгоритма. Он принимает диапазоны допустимых значений для параметров поиска (минимум, максимум, шаг) и общее количество эпох (итераций).
- Moving () — отвечает за основное движение и обновление позиций ворон в пространстве поиска на каждой итерации алгоритма.
- Revision () — производит проверку и коррекцию состояний, оценку качества найденных решений после каждой итерации.
- InitializeMemory () — инициализирует память для всех ворон в популяции,
- SelectRandomCrow () — выбирает случайную ворону из популяции, исключая при этом указанную ворону,
- UpdateMemory () — обновляет запись в памяти для конкретной вороны.
- flightLength — длина полета, параметр алгоритма
- awarenessProbability — вероятность осознания, параметр алгоритма
//———————————————————————————————————————————————————————————————————— class C_AO_CrowSearchAlgorithm : public C_AO { public: //---------------------------------------------------------- ~C_AO_CrowSearchAlgorithm () { } C_AO_CrowSearchAlgorithm () { ao_name = "CSA"; ao_desc = "Crow Search Algorithm"; ao_link = "https://www.mql5.com/ru/articles/19669"; popSize = 20; // размер популяции (количество ворон) flightLength = 2.0; // длина полета (fl) awarenessProbability = 0.1; // вероятность осознания (AP) ArrayResize (params, 3); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "flightLength"; params [1].val = flightLength; params [2].name = "awarenessProbability"; params [2].val = awarenessProbability; } void SetParams () { popSize = (int)params [0].val; flightLength = params [1].val; awarenessProbability = params [2].val; } bool Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP); void Moving (); void Revision (); private: void InitializeMemory (); int SelectRandomCrow (int excludeCrow); void UpdateMemory (int crowIndex); //------------------------------------------------------------------ public: double flightLength; // длина полета (fl) double awarenessProbability; // вероятность осознания (AP) private: //--------------------------------------------------------- S_CrowMemory crowMemory[]; // память ворон (массив структур) }; //————————————————————————————————————————————————————————————————————
Метод "Init" является начальной точкой для запуска алгоритма поиска ворон. Его основная задача — подготовить все необходимые структуры и проверить корректность входных параметров.
Стандартная инициализация. Сначала вызывается метод "StandardInit", который выполняет общую подготовку, необходимую для любого алгоритма оптимизации: устанавливает диапазоны поиска, шаг, количество эпох и определяют количество "измерений". Если эта стандартная инициализация завершается неудачно, метод "Init" сразу же возвращает "false".
Инициализация памяти ворон. Выделяется память для массива структур "crowMemory", размер которого равен "popSize" (количеству ворон в популяции). Затем для каждой вороны в этом массиве вызывается ее собственный метод "Init". Этот метод, в свою очередь, настраивает структуру памяти вороны, указывая, сколько измерений (параметров) она должна отслеживать (это значение берется из "coords", установленного "StandardInit"), и устанавливает начальное значение пригодности.
Проверка и корректировка параметров. Проверяется параметр "flightLength". Если он меньше или равен нуля, ему присваивается значение по умолчанию (2.0). Проверяется параметр "awarenessProbability". Если он меньше нуля, ему присваивается 0.0. Если он больше единицы, ему присваивается 1.0. Эти проверки гарантируют, что вероятностные параметры остаются в допустимом диапазоне.
Возврат результата. Если все шаги инициализации прошли успешно, метод возвращает "true", алгоритм готов к работе.//———————————————————————————————————————————————————————————————————— //--- Инициализация bool C_AO_CrowSearchAlgorithm::Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP) { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //------------------------------------------------------------------ // Инициализация массива структур памяти ArrayResize (crowMemory, popSize); for (int i = 0; i < popSize; i++) { crowMemory[i].Init(coords); } // Проверка корректности параметров if (flightLength <= 0.0) flightLength = 2.0; if (awarenessProbability < 0.0) awarenessProbability = 0.0; if (awarenessProbability > 1.0) awarenessProbability = 1.0; return true; } //————————————————————————————————————————————————————————————————————
Метод "InitializeMemory" отвечает за первоначальное наполнение "памяти" каждой вороны информацией о ее текущей позиции и ее качестве (пригодности).
Перебор всех ворон. Метод проходит по каждой вороне в популяции, используя цикл от нуля до "popSize" (общего числа ворон).
Копирование позиции. Для каждой вороны "i" происходит копирование текущей позиции вороны, "a [i].c" содержит текущие координаты вороны "i" (в виде массива), а "coords" — количество измерений (параметров) в пространстве поиска. Эти координаты затем сохраняются в "crowMemory [i].position", то есть в памяти вороны "i".
Сохранение пригодности. Одновременно с позицией, значение пригодности (качества) текущей позиции вороны "a [i].f" сохраняется в "crowMemory [i].fitness".Таким образом, после выполнения этого метода, каждая ворона в своей структуре памяти (crowMemory) будет хранить информацию о той позиции, которую она занимала в начале работы алгоритма, и соответствующее значение пригодности. Это является отправной точкой для дальнейшего процесса оптимизации, где вороны будут использовать эту "первичную память" для принятия решений о перемещении.
//———————————————————————————————————————————————————————————————————— //--- Инициализация памяти ворон void C_AO_CrowSearchAlgorithm::InitializeMemory () { // Инициализируем память текущими позициями for (int i = 0; i < popSize; i++) { ArrayCopy (crowMemory[i].position, a[i].c, 0, 0, coords); crowMemory[i].fitness = a[i].f; } } //————————————————————————————————————————————————————————————————————
Метод "SelectRandomCrow" предназначен для выбора случайной вороны из всей популяции, при этом гарантируется, что выбранная ворона не будет той, которую мы хотим исключить (указанной в параметре "excludeCrow").
Проверка размера популяции. Если в популяции всего одна ворона (popSize <= 1), то единственной доступной вороной является ворона с индексом "0", поэтому она и возвращается.
Генерация случайного индекса. Метод входит в цикл "do-while". Внутри цикла генерируется случайное число (selectedCrow), которое представляет собой индекс потенциально выбранной вороны. Для генерации используется функция "u.RNDfromCI", которая, выдает случайное число в диапазоне от 0.0 до "popSize" (исключая саму верхнюю границу, поэтому добавляется небольшое смещение). Полученное дробное число преобразуется в целое. Производятся дополнительные проверки, чтобы гарантировать, что полученный индекс находится в допустимых границах массива популяции. Если индекс выходит за эти границы, он корректируется.
Условие исключения. Цикл "do-while" продолжает генерировать случайные индексы до тех пор, пока сгенерированный "selectedCrow" не будет отличаться от "excludeCrow". То есть, если случайно была выбрана та ворона, которую мы хотим исключить, процесс повторяется.
Возврат выбранной вороны. Как только сгенерирован случайный индекс, который не совпадает с "excludeCrow", этот индекс возвращается как результат работы метода.
//———————————————————————————————————————————————————————————————————— //--- Выбор случайной вороны (исключая указанную) int C_AO_CrowSearchAlgorithm::SelectRandomCrow (int excludeCrow) { if (popSize <= 1) return 0; int selectedCrow; do { selectedCrow = (int)MathFloor(u.RNDfromCI(0.0, popSize - 0.001)); if (selectedCrow >= popSize) selectedCrow = popSize - 1; if (selectedCrow < 0) selectedCrow = 0; } while (selectedCrow == excludeCrow); return selectedCrow; } //————————————————————————————————————————————————————————————————————
Метод "Moving" является основным рабочим механизмом алгоритма поиска ворон. Он отвечает за движение и обновление позиций ворон в процессе поиска. Метод состоит из двух фаз: инициализации и основного цикла итераций.
Фаза 1: Инициализация популяции (при первом запуске). Если алгоритм запускается впервые (определяется по флагу "revision"), то происходит начальная инициализация всех ворон. Для каждой вороны в популяции ее координаты (a [i].c) заполняются случайными значениями. Эти значения генерируются в пределах заданных диапазонов (rangeMin, rangeMax) и с учетом определенных шагов (rangeStep), что обеспечивает, что начальные позиции ворон являются допустимыми. После инициализации флаг "revision" устанавливается в значение "истина", чтобы следующая активация метода перешла в фазу основного цикла.
Фаза 2: Основной цикл итераций (после инициализации). Этот цикл выполняется на каждой итерации алгоритма и включает следующие шаги для каждой вороны:
- Сохранение предыдущей позиции. Перед генерацией новой позиции, текущая позиция (a [i].c) и значение пригодности (a [i].f) текущей вороны сохраняются в "предыдущей" переменной (a [i].cP и a [i].fP соответственно). Это необходимо в случае, если новая позиция окажется хуже, можно будет вернуться к предыдущей,
- Выбор "соперника". Случайным образом выбирается другая ворона (j) из популяции. Эта выбранная ворона будет служить объектом для следования. Важно, что выбранная ворона не может быть той же самой, которую мы сейчас обрабатываем (SelectRandomCrow (i) гарантирует это),
- Определение сценария движения. Генерируется случайное число (r_j) от 0 до 1 и сравнивается с параметром "awarenessProbability" (вероятность осознания). Этот параметр определяет, как ворона будет двигаться:
-
Сценарий 1: Ворона следует за другой (Формула 1)
- Если "r_j" больше или равно "awarenessProbability", это означает, что ворона "i" будет пытаться приблизиться к лучшей позиции, основанной на позиции выбранной вороны "j".
- Новая позиция вычисляется по формуле: новая позиция = текущая позиция + случайный шаг * коэффициент полета * (позиция вороны (j) - текущая позиция).
- Случайный шаг (r_i) — это еще одно случайное число, обеспечивающее вариативность.
- Коэффициент полета "flightLength" — параметр, контролирующий насколько далеко ворона может перемещаться.
- Позиция вороны (j) - текущая_позиция — вектор, направленный от текущей позиции к позиции выбранной для следования вороны.
- После вычисления новой позиции, она также проверяется на допустимость в пределах заданных диапазонов (rangeMin, rangeMax, rangeStep).
-
Сценарий 2: Полное случайное перемещение (Формула 2)
- Если "r_j" меньше "awarenessProbability", это означает, что ворона "j" "замечает" слежку и принимает решительные меры.
- В этом случае ворона "i" игнорирует позицию вороны "j" и перемещается в абсолютно новую случайную позицию в пределах всего пространства поиска.
- Эта новая случайная позиция также генерируется с учетом допустимых диапазонов и шагов.
//———————————————————————————————————————————————————————————————————— //--- Основной шаг алгоритма (формулы 1 и 2 из документа) void C_AO_CrowSearchAlgorithm::Moving () { // Начальная инициализация популяции if (!revision) { // Шаг 1: Инициализация популяции ворон случайным образом for (int i = 0; i < popSize; i++) { for (int j = 0; j < coords; j++) { a [i].c [j] = u.RNDfromCI (rangeMin [j], rangeMax [j]); a [i].c [j] = u.SeInDiSp (a [i].c [j], rangeMin [j], rangeMax [j], rangeStep [j]); } } revision = true; return; } //------------------------------------------------------------------ // Основной цикл итерации // Шаг 5: Генерация новой позиции для каждой вороны for (int i = 0; i < popSize; i++) { // Сохраняем текущие позиции в cP (предыдущие координаты) ArrayCopy (a[i].cP, a[i].c, 0, 0, coords); a[i].fP = a[i].f; // Случайно выбираем ворону j для следования (кроме самой себя) int j = SelectRandomCrow(i); // Генерируем случайное число для определения осознания double r_j = u.RNDfromCI(0.0, 1.0); // Применяем формулы обновления позиции согласно сценариям if (r_j >= awarenessProbability) { // Сценарий 1: Ворона j не знает о слежке // Формула (1): P_i^(t+1) = P_i^t + r_i * fl_j * (M_j^t - P_i^t) for (int c = 0; c < coords; c++) { double r_i = u.RNDfromCI(0.0, 1.0); a[i].c[c] = a[i].c[c] + r_i * flightLength * (crowMemory[j].position[c] - a[i].c[c]); // Шаг 6: Проверка допустимости новой позиции a[i].c[c] = u.SeInDiSp (a[i].c[c], rangeMin[c], rangeMax[c], rangeStep[c]); } } else { // Сценарий 2: Ворона j осознает слежку // Формула (2): Перемещение в случайную позицию 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]); } } } } //————————————————————————————————————————————————————————————————————
Метод "UpdateMemory" отвечает за обновление "памяти" конкретной вороны. Память вороны хранит ее наилучшую найденную позицию и соответствующее значение пригодности.
Сравнение текущей пригодности с запомненной. Метод получает индекс вороны "crowIndex", чью память нужно обновить. Он сравнивает значение пригодности текущей позиции этой вороны "a [crowIndex].f" с ранее сохраненным значением пригодности в ее памяти.
Обновление памяти (если новая позиция лучше). Если текущая пригодность лучше, чем ранее запомненная пригодность, то происходит обновление: текущая позиция вороны копируется в ее память, и текущее значение пригодности копируется в память как новое лучшее значение.
Таким образом, этот метод гарантирует, что память каждой вороны всегда хранит информацию о самой лучшей точке, которую она достигала на данный момент. Если ворона находит новую позицию, которая дает более высокое значение пригодности, она "запоминает" эту новую позицию и ее пригодность. В противном случае, память остается без изменений.
//———————————————————————————————————————————————————————————————————— //--- Обновление памяти вороны void C_AO_CrowSearchAlgorithm::UpdateMemory (int crowIndex) { // Формула (3): Обновляем память если новая позиция лучше if (a[crowIndex].f > crowMemory[crowIndex].fitness) { ArrayCopy (crowMemory[crowIndex].position, a[crowIndex].c, 0, 0, coords); crowMemory[crowIndex].fitness = a[crowIndex].f; } } //————————————————————————————————————————————————————————————————————
Метод "Revision" отвечает за оценку и обновление результатов после каждого основного цикла перемещения ворон.
Первоначальная инициализация памяти. При первом запуске алгоритма (когда значения пригодности в памяти ворон установлены в минимально возможное значение, указывающее на еще не валидность), вызывается отдельный метод для инициализации памяти. Это гарантирует, что у каждой вороны есть корректно заполненная "база" для сравнения.
Обновление индивидуальной памяти каждой вороны. Метод проходит по всем воронам в популяции и для каждой вороны вызывается метод "UpdateMemory", который сравнивает текущую позицию вороны с ее наилучшей запомненной позицией. Если новая позиция лучше, память этой вороны обновляется.
Обновление глобальных лучших решений. Метод снова проходит по всем воронам, но на этот раз с целью найти наилучшее и наихудшее решение среди текущих позиций всех ворон и если текущая позиция какой-либо вороны (a [i].f) оказывается лучше глобального лучшего известного значения (fB), то это значение и соответствующая позиция сохраняются как новые глобальные лучшее решение (fB и cB).
Дополнительная проверка памяти. После оценки текущих позиций, проводится еще одна проверка, но уже по индивидуальной памяти каждой вороны. Если какая-либо из запомненных лучших (максимальных) позиций (crowMemory [i].fitness) оказывается лучше текущего глобального лучшего (fB), то глобальное лучшее решение обновляется. Это важно, так как метод "UpdateMemory" мог обновить память вороны, но затем ворона могла отойти от этой лучшей позиции в текущей итерации.Таким образом, метод "Revision" является точкой сбора информации после каждого шага алгоритма. Он поддерживает актуальными как наилучшие индивидуальные достижения каждой вороны, так и общее наилучшее и наихудшее решение, найденное всей популяцией на данный момент.
//———————————————————————————————————————————————————————————————————— //--- Обновление и проверка результатов void C_AO_CrowSearchAlgorithm::Revision () { // Если это первая итерация после инициализации if (crowMemory[0].fitness == -DBL_MAX) { InitializeMemory(); } // Шаг 8: Обновление памяти каждой вороны for (int i = 0; i < popSize; i++) { UpdateMemory(i); } // Обновляем глобальное лучшее решение for (int i = 0; i < popSize; i++) { if (a[i].f > fB) { fB = a[i].f; ArrayCopy (cB, a[i].c, 0, 0, WHOLE_ARRAY); } } // Дополнительно проверяем память на наличие лучших решений for (int i = 0; i < popSize; i++) { if (crowMemory[i].fitness > fB) { fB = crowMemory[i].fitness; ArrayCopy (cB, crowMemory[i].position, 0, 0, WHOLE_ARRAY); } } } //————————————————————————————————————————————————————————————————————
Результаты тестов
Как видно из результатов, они средние, слабее на дискретной функции Megacity.
=============================
5 Hilly's; Func runs: 10000; result: 0.7780377334241331
25 Hilly's; Func runs: 10000; result: 0.5107983411957056
500 Hilly's; Func runs: 10000; result: 0.2671707154561419
=============================
5 Forest's; Func runs: 10000; result: 0.9221928451900311
25 Forest's; Func runs: 10000; result: 0.48104687904934185
500 Forest's; Func runs: 10000; result: 0.16367212698152436
=============================
5 Megacity's; Func runs: 10000; result: 0.4846153846153848
25 Megacity's; Func runs: 10000; result: 0.34215384615384614
500 Megacity's; Func runs: 10000; result: 0.11487692307692406
=============================
All score: 4.06456 (45.16%)
На визуализации заметен большой разброс на функциях малой размерности, а продолжительные горизонтальные зеленые линии говорят нам о застревании в локальных экстремумах, также есть небольшой разброс на функциях средней размерности задач, труднее всего алгоритм справляется с многомерностью, красные линии.
CSA_crow на тестовой функции Hilly
CSA_crow на тестовой функции Forest
CSA_crow на тестовой функции Megacity
После серии тестовых испытаний алгоритм CSA_crow представлен в рейтинговой таблице ознакомительно.
| № | 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 | DOAdingom | dingo_optimization_algorithm_M | 0,47968 | 0,45367 | 0,46369 | 1,39704 | 0,94145 | 0,87909 | 0,91454 | 2,73508 | 0,78615 | 0,86061 | 0,84805 | 2,49481 | 6,627 | 73,63 |
| 2 | 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 |
| 3 | CLA | code lock algorithm (joo) | 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 |
| 4 | 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 |
| 5 | (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 |
| 6 | 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 |
| 7 | 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 |
| 8 | 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 |
| 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 | 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 |
| 26 | 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 |
| 27 | 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 |
| 28 | 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 |
| 29 | 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 |
| 30 | 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 |
| 31 | 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 |
| 32 | 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 |
| 33 | 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 |
| 34 | (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 |
| 35 | 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 |
| 36 | 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 |
| 37 | 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 |
| 38 | 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 |
| 39 | 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 |
| 40 | 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 |
| 41 | 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 |
| 42 | 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 |
| 43 | 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 |
| 44 | 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 |
| 45 | 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 |
| CSA_crow | crow_search_algorithm | 0,77804 | 0,51080 | 0,26717 | 1,55601 | 0,92219 | 0,48105 | 0,16367 | 1,56691 | 0,48461 | 0,34215 | 0,11487 | 0,94163 | 4,065 | 45,16 | |
| 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 | |
Выводы
После серии испытаний алгоритм не нашел своего места в рейтинговой таблице популяционных алгоритмов оптимизации, ему немного не хватило, однако это очень перспективный метод. Элегантная простота — алгоритм действительно завершенный и самодостаточный. Трудно что-то добавить без нарушения базовой концепции. Проблема в том, что простота, которая является достоинством для понимания, становится недостатком для производительности в данном случае. Не могу сказать, что это плохой метод оптимизации, он по-своему хорош, но все же застревает, особенно это заметно на функциях малой размерности. Несмотря на общие невысокие результаты, алгоритм демонстрирует стабильность в плане "нет сильных западаний на каком либо типе задач" по цветовой градации, как некоторые алгоритмы, которые находятся в топе, но имеют красный цвет по некоторым типам задач.
Биологическая обоснованность — метафора с воронами интуитивно понятна и логична, что делает алгоритм легким для понимания и реализации. Существует множество модификаций CSA (с полетами Леви, адаптивными параметрами, хаотическими картами), но большинство из них сильно усложняют алгоритм, теряя его главное преимущество — простоту, дают незначительное улучшение производительности и превращают CSA в гибрид с другими методами.
Минимум параметров — всего 3 настройки (N, fl, AP), это упрощает настройку по сравнению с более сложными метаэвристиками. CSA — это хороший учебный материал и достойный базовый метод оптимизации. Он не революционен, но надежен для несложных задач и его место в арсенале трейдера — как запасной вариант, когда более сложные методы избыточны, или когда важна простота реализации.
Рисунок 2. Цветовая градация алгоритмов по соответствующим тестам
Рисунок 3. Гистограмма результатов тестирования алгоритмов (по шкале от 0 до 100, чем больше, тем лучше, где 100 — максимально возможный теоретический результат, в архиве скрипт для расчета рейтинговой таблицы)
Плюсы и минусы алгоритма CSA_crow:
Плюсы:
- Красивая и перспективная идея как база для разработок.
- Небольшое количество параметров.
Минусы:
- Большой разброс результатов.
- Низкая эффективность на задачах высокой размерности.
К статье прикреплён архив с актуальными версиями кодов алгоритмов. Автор статьи не несёт ответственности за абсолютную точность в описании канонических алгоритмов, во многие из них были внесены изменения для улучшения поисковых возможностей. Выводы и суждения, представленные в статьях, основываются на результатах проведённых экспериментов.
Программы, используемые в статье
| # | Имя | Тип | Описание |
|---|---|---|---|
| 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_AO_CSA_crow.mq5 | Скрипт | Испытательный стенд для CSA_crow |
Предупреждение: все права на данные материалы принадлежат MetaQuotes Ltd. Полная или частичная перепечатка запрещена.
Данная статья написана пользователем сайта и отражает его личную точку зрения. Компания MetaQuotes Ltd не несет ответственности за достоверность представленной информации, а также за возможные последствия использования описанных решений, стратегий или рекомендаций.
Переходим на MQL5 Algo Forge (Часть 4): Работа с версиями и выпуск релизов
Торгуем опционы без опционов (Часть 3): Сложные опционные стратегии
Нейросети в трейдинге: От трансформеров к спайковым нейронам (Основные компоненты)
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Вы принимаете политику сайта и условия использования