Алгоритм верблюда — Camel Algorithm (CA)
264
0
Содержание
Введение
В последние десятилетия появилось значительное количество оптимизационных алгоритмов, вдохновленных природными явлениями и поведением животных. Данные био-вдохновлённые подходы показали превосходные результаты во многих задачах. В этой статье разберем новый алгоритм оптимизации, названный Camel Algorithm (CA), основанный на стратегиях выживания и перемещения верблюдов в экстремальных условиях пустыни. Алгоритм был разработан и представлен в 2016 году двумя учеными: Mohammed Khalid Ibrahim и Ramzy Salim Ali.
Верблюды обладают уникальными физиологическими характеристиками и поведенческими адаптациями, позволяющими им эффективно ориентироваться и выживать в суровых условиях пустыни с ограниченными ресурсами, экстремальными температурами и меняющимся ландшафтом. Алгоритм CA моделирует ключевые аспекты этого поведения: влияние температуры, управление запасами воды и пищи, выносливость, эффект "оазисов" (перспективных областей поиска), а также групповое взаимодействие в караване.
Мы, как обычно, разберем всю "начинку" оригинального алгоритма, сделаем модификацию и протестируем обе версии на тестовых функциях, а результаты занесем в нашу рейтинговую таблицу алгоритмов оптимизации.
Реализация алгоритма
Представьте себе караван верблюдов, отправляющийся в путешествие через огромную пустыню. Их цель — найти оазисы с водой и пищей, спрятанные среди бескрайних песков. Именно это путешествие вдохновило авторов на создание алгоритма оптимизации "Camel Algorithm" (CA).
Алгоритм имитирует ситуацию, как эти удивительные животные выживают и находят ресурсы в суровых условиях пустыни. Каждый верблюд в алгоритме — это потенциальное решение, которое исследует пространство поиска (пустыню), пытаясь найти оптимальное решение (самый богатый оазис).
Караваны верблюдов путешествуют вместе не случайно — это стратегия выживания. В алгоритме популяция "верблюдов" (потенциальных решений) обменивается информацией о лучших найденных маршрутах, что очень схоже с тем, как настоящие верблюды в караване следуют по проверенным путям к источникам воды.
Ключевые элементы:
Температура (T) — случайный фактор, влияющий на поведение верблюдов. В пустыне температура меняется от прохладных ночей до жарких дней, влияя на скорость и направление движения верблюдов. Уникальная способность верблюдов адаптироваться к экстремальным температурам (от холодных ночей до жарких дней в пустыне) послужила вдохновением для параметра "температуры" в алгоритме. Этот параметр вносит элемент случайности и адаптивности, что помогает избегать локальных оптимумов — аналогично тому, как верблюды должны адаптировать свой маршрут к меняющимся условиям.
Запасы (S) — вода и пища, которые постепенно истощаются в пути. Верблюды эволюционировали, чтобы выживать в одних из самых суровых условий на планете. Их способность эффективно распределять ресурсы (воду и пищу) напрямую отражена в алгоритме через параметр "supply", который уменьшается на протяжении "путешествия" и влияет на стратегию поиска. Чем дольше верблюд путешествует без нахождения оазиса, тем меньше у него остается сил. Эта особенность делает алгоритм особенно эффективным в задачах с ограниченными вычислительными ресурсами.
Выносливость (E) — энергия верблюда, зависящая от температуры и длительности путешествия. Палящее солнце медленно истощает силы каравана. Верблюды известны своей исключительной выносливостью, способностью преодолевать большие расстояния с минимальными ресурсами. В алгоритме параметр "endurance" влияет на способность агента исследовать пространство решений. Постепенно уменьшаясь и действуя на баланс между исследованием новых областей и использованием уже найденных перспективных решений.
Эффект оазиса — когда верблюд находит перспективное место (лучшее решение), его запасы и выносливость восстанавливаются, позволяя продолжить исследование. В алгоритме, когда находится решение, параметры "supply" и "endurance" пополняются, что позволяет более тщательно обследовать эту область — точно как верблюд задерживается у оазиса для восстановления сил, поэтому, это одна из самых интересных особенностей алгоритма.
Случайное блуждание — отклонения от основного пути, помогающие исследовать новые территории.
Как показано на иллюстрации ниже, группа из пяти верблюдов ищет богатый оазис в пустыне. Изначально они находятся в разных местах и движутся в разных направлениях:
Верблюд 1 направляется на север, но из-за высокой температуры его скорость замедляется, и ему приходится делать больше остановок.Верблюд 2 находит небольшой оазис (локальный оптимум) с некоторыми запасами еды и воды. Он сообщает остальным о своей находке, но продолжает поиск, подозревая, что где-то есть оазис побольше.
Верблюд 3 блуждает по относительно ровной местности, его запасы постепенно уменьшаются, но он продолжает исследовать новые направления.
Верблюд 4 попадает в район с очень высокой температурой, что значительно снижает его выносливость. Однако, случайное блуждание помогает ему выбраться из этого района.
Верблюд 5, используя информацию от других верблюдов и благоприятное направление случайного блуждания, находит самый богатый оазис (глобальный оптимум).
Рисунок 1. Иллюстрация работы алгоритма CA
Напишем псевдокод работы алгоритма CA:
// Инициализация параметров
Инициализировать:
popSize = размер популяции (караван верблюдов)
Tmin = минимальная температура
Tmax = максимальная температура
omega = фактор нагрузки для запасов
dyingRate = скорость "смерти" верблюдов
alpha = параметр видимости для эффекта оазиса
initialSupply = начальный запас воды и пищи (обычно 1.0)
initialEndurance = начальная выносливость (обычно 1.0)
totalSteps = общее количество шагов пути
traveledSteps = 0 (начальное значение пройденных шагов)
// Инициализация начальной популяции
Создать начальный караван верблюдов (несколько решений):
Для каждого верблюда i от 1 до popSize:
Сгенерировать случайное решение в допустимом диапазоне
Установить начальные значения:
temperature [i] = случайное значение между Tmin и Tmax
supply [i] = initialSupply
endurance [i] = initialEndurance
Вычислить приспособленность (fitness) каждого верблюда в караване
Найти текущее лучшее решение
// Основной цикл оптимизации
Пока (traveledSteps < totalSteps):
traveledSteps++
// Для каждого верблюда в караване
Для i от 1 до popSize:
// 1. Обновить факторы (температура, запасы, выносливость)
// Формула (1): Tnow = (Tmax - Tmin) * Rand(0,1) + Tmin
temperature [i] = CalculateTemperature (i)
// Формула (2): Snow = Spast * (1 - ω * Traveled steps/Total journey steps)
supply [i] = CalculateSupply (i)
// Формула (4): Enow = Epast * (1 - Tnow/Tmax) * (1 - Traveled steps /Total journey steps)
endurance [i] = CalculateEndurance (i)
// 2. Проверка на "смерть" верблюда
Если (случайное_число < dyingRate):
Сгенерировать новое случайное решение для верблюда i
Продолжить следующую итерацию
// 3. Обновить позицию верблюда
delta = случайное число в диапазоне [-1, 1] // фактор случайного блуждания
Сохранить старые координаты верблюда
// Для каждой координаты
Для каждой координаты c:
// Вычислить факторы для формулы обновления
enduranceFactor = (1.0 - endurance [i] / initialEndurance)
supplyFactor = exp(1.0 - supply [i] / initialSupply)
// Обновить позицию по формуле (6)
new_position [c] = old_position [c] + delta * enduranceFactor * supplyFactor * (best_position [c] - old_position [c])
// Проверить выход за границы и скорректировать при необходимости
new_position [c] = Привести к допустимому диапазону
// 4. Применить эффект оазиса
Если (случайное_число > (1.0 - alpha) И fitness_new > fitness_old):
// Найден оазис, пополнить запасы и выносливость
supply [i] = initialSupply
endurance [i] = initialEndurance
// Ранжировать верблюдов и найти лучшее решение
Обновить лучшее решение
// Вернуть итоговое лучшее решение
Теперь можем приступить к написанию кода, внутри которого будет рассматриваться, как оригинальная версия авторов (часть строк будет закомментирована), так и моя модификация, направленная на улучшение логики работы алгоритма. Напишем класс "C_AO_CAm", который будет представлять собой реализацию алгоритма CAm и будет наследоваться от базового класса "C_AO".
Класс содержит параметры, характерные для алгоритма, такие как размер популяции, минимальная и максимальная температура, фактор нагрузки, скорость "смерти" верблюдов и параметр видимости. Эти параметры могут быть заданы при инициализации и удобно настраиваются через массив параметров.
Конструктор класса задаёт основные свойства алгоритма, включая название, описание и ссылку на источник идеи, а также инициализирует массив параметров. В методе "SetParams" эти параметры можно обновить во время выполнения.
Класс реализует методы инициализации популяции, шагов перемещения верблюдов, а также их ревизии, обновления факторов, а также эффектов, связанных с оазисами — всё, что моделирует поведение верблюдов в пустыне и ищет оптимальные решения. Основные свойства класса — это массивы, хранящие температуру каждого верблюда, их запас воды и пищи, выносливость, а также счётчики пройденных и всего шагов. Есть переменные, задающие стартовые уровни запасов и выносливости, которые обычно инициализируются в начале работы алгоритма.
В целом, данный класс реализует модифицированную версию алгоритма оптимизации на основе поведения каравана верблюдов, где "температура" и "запас" моделируют промежуточные состояния поиска, а динамики движения и гибели верблюдов помогают эффективно искать решение.
//—————————————————————————————————————————————————————————————————————————————— class C_AO_CAm : public C_AO { public: //-------------------------------------------------------------------- ~C_AO_CAm () { } C_AO_CAm () { ao_name = "CA"; ao_desc = "Camel Algorithm M"; ao_link = "https://www.mql5.com/ru/articles/18057"; popSize = 50; // размер популяции (camel caravan) Tmin = 50; // минимальная температура Tmax = 100; // максимальная температура omega = 0.8; // фактор нагрузки для supply dyingRate = 0.01; // скорость "смерти" верблюдов alpha = 0.9; // параметр видимости для эффекта оазиса ArrayResize (params, 6); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "Tmin"; params [1].val = Tmin; params [2].name = "Tmax"; params [2].val = Tmax; params [3].name = "omega"; params [3].val = omega; params [4].name = "dyingRate"; params [4].val = dyingRate; params [5].name = "alpha"; params [5].val = alpha; } void SetParams () { popSize = (int)params [0].val; Tmin = params [1].val; Tmax = params [2].val; omega = params [3].val; dyingRate = params [4].val; alpha = params [5].val; } bool Init (const double &rangeMinP [], // минимальные значения const double &rangeMaxP [], // максимальные значения const double &rangeStepP [], // шаг изменения const int epochsP = 0); // количество эпох void Moving (); void Revision (); //---------------------------------------------------------------------------- double Tmin; // минимальная температура double Tmax; // максимальная температура double omega; // фактор нагрузки для supply double dyingRate; // скорость "смерти" верблюдов double alpha; // параметр видимости для эффекта оазиса private: //------------------------------------------------------------------- double temperature []; // текущая температура для каждого верблюда double supply []; // текущий запас воды и пищи для каждого верблюда double endurance []; // текущая выносливость для каждого верблюда double initialSupply; // начальный запас (обычно 1.0) double initialEndurance; // начальная выносливость (обычно 1.0) int traveledSteps; // количество пройденных шагов int totalSteps; // общее количество шагов // Вспомогательные методы void InitializePopulation (); void UpdateFactors (); void UpdatePositions (); void ApplyOasisEffect (); }; //——————————————————————————————————————————————————————————————————————————————
Метод "Init" предназначен для инициализации алгоритма CAm. В ходе выполнения этого метода происходит подготовка необходимых структур данных и параметров для дальнейшей работы. Основные шаги метода включают вызов стандартной инициализации, которая устанавливает диапазоны и шаги изменения переменных поиска. Если инициализация не удалась, метод завершается с ошибкой.
Далее происходит выделение памяти под массивы, хранящие параметры каждого верблюда — температуру, запас воды и пищи, выносливость — размер которых равен размеру популяции. Эти массивы необходимы для моделирования поведения верблюдов во время оптимизации. Задаются начальные значения для запаса и выносливости, устанавливается количество пройденных шагов в ноль, а также всего количества шагов, соответствующего количеству эпох.
//—————————————————————————————————————————————————————————————————————————————— bool C_AO_CAm::Init (const double &rangeMinP [], // минимальные значения const double &rangeMaxP [], // максимальные значения const double &rangeStepP [], // шаг изменения const int epochsP = 0) // количество эпох { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //---------------------------------------------------------------------------- // Инициализация массивов для каждого верблюда ArrayResize (temperature, popSize); ArrayResize (supply, popSize); ArrayResize (endurance, popSize); // Установка начальных значений initialSupply = 1.0; initialEndurance = 1.0; traveledSteps = 0; totalSteps = epochsP; return true; } //——————————————————————————————————————————————————————————————————————————————
Метод "Moving" реализует итерационный процесс алгоритма, отвечая за обновление состояний и перемещений верблюдов. В первую очередь, он проверяет, была ли выполнена первая итерация; если нет, то инициализирует начальную популяцию верблюдов и отмечает, что инициализация завершена.
На каждом последующем шаге увеличивается счетчик пройденных шагов, после чего, происходит последовательное выполнение следующих действий:
- Обновление факторов, таких как температура, запас ресурсов и выносливость каждого верблюда — это важно для моделирования динамического поведения и поиска.
- Обновление позиций верблюдов в пространстве поиска — то есть, перемещение в направлении, которое потенциально улучшит решение.
- Применение эффекта оазиса, при котором верблюды могут увеличить свои запасы и восстановить выносливость, что помогает избегать локальных минимумов и стимулирует более сложное исследование пространства.
В конце каждого шага происходит сохранение значения фитнес-функции для каждого верблюда, чтобы можно было сравнить текущее состояние с предыдущим и, на основе этого, принимать дальнейшие решения.
//+----------------------------------------------------------------------------+ //| Основной метод оптимизации | //+----------------------------------------------------------------------------+ void C_AO_CAm::Moving () { // Первая итерация - инициализация начальной популяции if (!revision) { InitializePopulation (); revision = true; return; } // Увеличиваем счетчик пройденных шагов traveledSteps++; // Основной процесс оптимизации // 1. Обновляем факторы (температура, запас, выносливость) UpdateFactors (); // 2. Обновляем позиции верблюдов UpdatePositions (); // 3. Применяем эффект оазиса (обновление запасов и выносливости) ApplyOasisEffect (); // 4. Сохраняем состояние верблюдов for (int i = 0; i < popSize; i++) a [i].fP = a [i].f; } //——————————————————————————————————————————————————————————————————————————————
Метод "Revision" отвечает за обновление лучшего найденного решения в текущей популяции верблюдов. Он проходит по всем верблюдам в популяции и сравнивает значение целевой функции (fitness) каждого верблюда с текущим лучшим значением. Если значение фитнес-функции текущего верблюда (a [i].f) оказывается лучше, чем текущее лучшее значение (fB), то происходит обновление:
- "fB" присваивается новое лучшее значение (a [i].f).
- Положение (координаты, параметры) верблюда, достигшего лучшего значения, копируется из координат текущего лучшего верблюда (a [i].c) в массив координат лучшего решения (cB).
После завершения цикла по всем верблюдам в популяции, "fB" и "cB" будут содержать значение и координаты лучшего решения, найденного на текущей итерации.
//+----------------------------------------------------------------------------+ //| Обновление лучшего решения | //+----------------------------------------------------------------------------+ void C_AO_CAm::Revision () { // Поиск лучшего решения в текущей популяции 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); } } } //——————————————————————————————————————————————————————————————————————————————
Метод "InitializePopulation" предназначен для формирования начальной популяции верблюдов в алгоритме оптимизации. Он создает равномерное распределение начальных решений по всему допустимому пространству поиска.
Основные шаги метода включают обход всей популяции, то есть, всех верблюдов. Для каждого верблюда происходит генерация случайных координат внутри допустимых диапазонов для каждой переменной (каждой координаты). Эти координаты выбираются случайным образом, чтобы равномерно покрыть весь допустимый диапазон.
После генерации координат, каждую из них округляют до ближайшего допустимого шага, что обеспечивает соответствие поиска ограничениям по дискретности. Это делается для того, чтобы начальные решения точно соответствовали допустимым диапазонам и шагам. Также, для каждого верблюда устанавливаются начальные значения параметров, таких как запас воды и выносливость, что задается заранее установленными значениями по умолчанию для всей популяции.
В результате выполнения метода, создается стартовая популяция решений, равномерно расположенная по всему пространству поиска, что способствует эффективной организации начала процесса оптимизации.
//+----------------------------------------------------------------------------+ //| Инициализация начальной популяции | //+----------------------------------------------------------------------------+ void C_AO_CAm::InitializePopulation () { // Инициализация начальной популяции равномерно по всему пространству for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { // Генерация случайных координат в допустимых пределах a [i].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]); // Округление до ближайшего допустимого шага a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } // Инициализация факторов для каждого верблюда supply [i] = initialSupply; endurance [i] = initialEndurance; } } //——————————————————————————————————————————————————————————————————————————————
Метод "UpdateFactors" в классе "C_AO_CAm" отвечает за обновление ключевых факторов, влияющих на поведение каждого "верблюда" в популяции: температуры, запаса и выносливости. Эти факторы динамически изменяются на каждой итерации алгоритма и влияют на процесс поиска оптимального решения.
Сначала вычисляется "journeyRatio", представляющее собой отношение пройденных шагов "traveledSteps" к общему количеству шагов "totalSteps". Эта величина отражает прогресс выполнения алгоритма. Для каждого верблюда (i от 0 до popSize -1) температура (temperature [i]) устанавливается случайным образом в пределах заданного диапазона от "Tmin" до "Tmax". Новая температура генерируется независимо для каждого верблюда, что вносит случайность в процесс.
Запас верблюда (supply [i]) уменьшается в зависимости от пройденного пути. Он вычисляется, как предыдущее значение запаса, умноженное на коэффициент (1.0 - omega * journeyRatio). Параметр "omega" контролирует скорость уменьшения запаса. Чем больше "omega", и чем больше "journeyRatio" (т.е., чем дальше зашел алгоритм), тем быстрее уменьшается запас.
Выносливость верблюда (endurance [i]) уменьшается в зависимости, как от температуры, так и от пройденного пути. Выносливость вычисляется как предыдущее значение выносливости, умноженное на (1.0 - temperatureRatio) * (1.0 - journeyRatio). temperatureRatio - это отношение текущей температуры верблюда к максимальной температуре "Tmax". Чем выше температура, и чем дальше зашел алгоритм, тем больше уменьшается выносливость.
Таким образом, метод динамически изменяет характеристики каждого верблюда, используя как случайные величины (температура), так и информацию о прогрессе алгоритма (пройденный путь). Эти изменения оказывают влияние на то, как верблюды исследуют пространство поиска.
//+----------------------------------------------------------------------------+ //| Обновление факторов (температура, запас, выносливость) | //+----------------------------------------------------------------------------+ void C_AO_CAm::UpdateFactors () { double journeyRatio = (double)traveledSteps / (double)totalSteps; for (int i = 0; i < popSize; i++) { // Обновление температуры - случайное значение в диапазоне [Tmin, Tmax], // формула (1): Tnow = (Tmax - Tmin) * Rand(0,1) + Tmin temperature [i] = u.RNDfromCI (Tmin, Tmax); // Обновление запаса - уменьшается с течением времени, // формула (2): Snow = Spast * (1 - ω * Traveled steps / Total journey steps) supply [i] = supply [i] * (1.0 - omega * journeyRatio); // Обновление выносливости - зависит от температуры и времени, // формула (4): Enow = Epast * (1 - Tnow/Tmax) * (1 - Traveled steps / Total journey steps) double temperatureRatio = temperature [i] / Tmax; endurance [i] = endurance [i] * (1.0 - temperatureRatio) * (1.0 - journeyRatio); } } //——————————————————————————————————————————————————————————————————————————————
Метод "UpdatePositions" предназначен для обновления положений верблюдов на каждом шаге алгоритма оптимизации. Он моделирует перемещения и случайные события, влияющие на обновление решений.
Основные этапы метода включают итерацию по всему населению верблюдов. Для каждого верблюда выполняются следующие действия:
-
С некоторой вероятностью (например, из-за неблагоприятных условий, таких как зыбучие пески, или штормы, или высокая температура) верблюд считается погибшим. В таком случае, его позиция в пространстве случайным образом генерируется заново в пределах допустимого диапазона и корректируется, согласно минимальным шагам.
-
Если верблюд не "умирает", его новая позиция определяется с помощью модели случайного блуждания. Для каждого координатного измерения генерируется случайный фактор "delta" в диапазоне [-1, 1], моделирующий случайное изменение.
-
Новая координата рассчитывается, как старое значение с добавлением модифицирующего члена, который учитывает случайное блуждание, текущие характеристики верблюда (выносливость и запас), а также разницу между текущей координатой и позицией оазиса. При этом учитывается влияние факторов истощения "endurance" и запаса "supply".
-
После вычисления новой координаты, она проверяется на выход за допустимые границы диапазона.
В результате этого процесса, позиции верблюдов динамически изменяются, моделируя их перемещения в пространстве поиска с учетом случайных факторов и внутреннего состояния (выносливости и запаса). Такие обновления помогают алгоритму исследовать пространство решений более эффективно, избегая локальных минимумов и способствуя поиску оптимального решения.
Закомментированный код оригинального функционала "смерти" и пересоздания позиции в текущей модифицированной версии алгоритма не используется.
Ключевые изменения модифицированной версии: проверка на "смерть" верблюда теперь выполняется для каждой координаты отдельно, а не для всего верблюда, вместо полностью случайной генерации новой позиции, используется нормальное (гауссово) распределение вокруг лучшего решения (cB), функция "GaussDistribution" создает новую позицию по нормальному распределению с центром в лучшем решении, что дает более целенаправленное исследование перспективных областей.
//+----------------------------------------------------------------------------+ //| Обновление позиций верблюдов | //+----------------------------------------------------------------------------+ void C_AO_CAm::UpdatePositions () { for (int i = 0; i < popSize; i++) { /* // Проверка на "смерть" верблюда (quicksand, storm, etc.) if (u.RNDprobab () < dyingRate) { // Генерируем новую позицию случайным образом 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]); } continue; } */ // Обновление позиции------------------------------------------------------- double delta = u.RNDfromCI (-1.0, 1.0); // Фактор случайного блуждания // Обновляем каждую координату for (int c = 0; c < coords; c++) { /* // Применяем формулу обновления из статьи double enduranceFactor = (1.0 - endurance [i] / initialEndurance); double supplyFactor = MathExp (1.0 - supply [i] / initialSupply); // Обновление позиции a [i].c [c] = a [i].c [c] + delta * enduranceFactor * supplyFactor * (cB [c] - a [i].c [c]); // Проверка на выход за границы и корректировка до допустимого значения a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); */ // Проверка на "смерть" верблюда (quicksand, storm, etc.) if (u.RNDprobab () < dyingRate) { // Генерируем новую позицию относительно координаты оазиса по нормальному распределению a [i].c [c] = u.GaussDistribution (cB [c], rangeMin [c], rangeMax [c], 8); } else { // Применяем формулу обновления из статьи double enduranceFactor = (1.0 - endurance [i] / initialEndurance); double supplyFactor = MathExp (1.0 - supply [i] / initialSupply); // Обновление позиции a [i].c [c] = a [i].c [c] + delta * enduranceFactor * supplyFactor * (cB [c] - a [i].c [c]); } // Проверка на выход за границы и корректировка до допустимого значения a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } } //——————————————————————————————————————————————————————————————————————————————
Метод "ApplyOasisEffect" моделирует влияние оазиса на состояние верблюдов в процессе поиска. Его основная задача — определить, обнаружил ли верблюд оазис и, при этом, улучшить состояние его ресурсов.
Проходя по всей популяции, метод проверяет для каждого верблюда два условия. Первое — вероятность обнаружить оазис, которая задается случайным числом и зависит от параметра "alpha". Чем выше "alpha", тем больше шансов на обнаружение. Второе — проверка, что текущее значение фитнес-функции (или качество решения) верблюда лучше, чем у него было на предыдущей итерации. Это обеспечивает влияние оазиса только на тех верблюдов, результаты которых действительно улучшились.
Если оба условия выполнены, считается, что верблюд обнаружил оазис. В этом случае, его запасы "supply" и выносливость "endurance" обновляются до своих первоначальных значений. Таким образом, оазис способствует восстановлению ресурсов верблюда и позволяет ему продолжить активное исследование пространства поиска с повышенной эффективностью.
Общий смысл метода — моделировать способность верблюдов находить оазисы, что дает им возможность восстанавливаться и продолжать поисковую деятельность, улучшая свои шансы на достижение глобального оптимума.
//+----------------------------------------------------------------------------+ //| Применение эффекта оазиса (обновление запасов и выносливости) | //+----------------------------------------------------------------------------+ void C_AO_CAm::ApplyOasisEffect () { for (int i = 0; i < popSize; i++) { // Условие для обнаружения оазиса: // 1) Верблюд должен "видеть" оазис (случайная вероятность, зависящая от alpha) // 2) Текущее решение должно быть лучше, чем в предыдущей итерации if (u.RNDprobab () > (1.0 - alpha) && a [i].f > a [i].fP) { // Обнаружен оазис, пополняем запасы и выносливость supply [i] = initialSupply; endurance [i] = initialEndurance; } } } //——————————————————————————————————————————————————————————————————————————————
Результаты тестов
Как можно заметить, при работе оригинальной версии алгоритма CA, он набирает максимально 32,56%
=============================
5 Hilly's; Func runs: 10000; result: 0.5872886802671936
25 Hilly's; Func runs: 10000; result: 0.3896531310299016
500 Hilly's; Func runs: 10000; result: 0.3412707468979892
=============================
5 Forest's; Func runs: 10000; result: 0.5248302942062708
25 Forest's; Func runs: 10000; result: 0.2760893244414008
500 Forest's; Func runs: 10000; result: 0.18881523788478266
=============================
5 Megacity's; Func runs: 10000; result: 0.3507692307692308
25 Megacity's; Func runs: 10000; result: 0.16676923076923078
500 Megacity's; Func runs: 10000; result: 0.10464615384615475
=============================
All score: 2.93013 (32.56%)
Алгоритм с модификацией показывает более высокие результаты:
CAm|Camel Algorithm|50.0|50.0|100.0|0.8|0.01|0.9|
=============================
5 Hilly's; Func runs: 10000; result: 0.786842172387197
25 Hilly's; Func runs: 10000; result: 0.560421361070792
500 Hilly's; Func runs: 10000; result: 0.3513297097198401
=============================
5 Forest's; Func runs: 10000; result: 0.8277193604225209
25 Forest's; Func runs: 10000; result: 0.5604138230149972
500 Forest's; Func runs: 10000; result: 0.24335977579892912
=============================
5 Megacity's; Func runs: 10000; result: 0.6484615384615386
25 Megacity's; Func runs: 10000; result: 0.33092307692307693
500 Megacity's; Func runs: 10000; result: 0.13417692307692433
=============================
All score: 4.44365 (49.37%)
Визуализация работы алгоритма представлена для версии CA и CAm, для лучшего восприятия разниц между двумя алгоритмами. Обе версии демонстрируют характерное для логики алгоритма "кучкование" в окрестностях потенциально хороших решений.
CA на тестовой функции Hilly
CAm на тестовой функции Hilly
CA на тестовой функции Forest
CAm на тестовой функции Forest
CA на тестовой функции Megacity
CAm на тестовой функции Megacity
Модифицированная версия алгоритма находится на 35 месте в рейтинге популяционных алгоритмов оптимизации, оригинальная версия представлена только для информации и рейтингового номера не имеет.
| № | AO | Description | Hilly | Hilly Final | Forest | Forest Final | Megacity (discrete) | Megacity Final | Final Result | % of MAX | ||||||
| 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | ||||||||
| 1 | ANS | across neighbourhood search | 0,94948 | 0,84776 | 0,43857 | 2,23581 | 1,00000 | 0,92334 | 0,39988 | 2,32323 | 0,70923 | 0,63477 | 0,23091 | 1,57491 | 6,134 | 68,15 |
| 2 | CLA | code lock algorithm (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 |
| 3 | AMOm | animal migration ptimization M | 0,90358 | 0,84317 | 0,46284 | 2,20959 | 0,99001 | 0,92436 | 0,46598 | 2,38034 | 0,56769 | 0,59132 | 0,23773 | 1,39675 | 5,987 | 66,52 |
| 4 | (P+O)ES | (P+O) evolution strategies | 0,92256 | 0,88101 | 0,40021 | 2,20379 | 0,97750 | 0,87490 | 0,31945 | 2,17185 | 0,67385 | 0,62985 | 0,18634 | 1,49003 | 5,866 | 65,17 |
| 5 | CTA | comet tail algorithm (joo) | 0,95346 | 0,86319 | 0,27770 | 2,09435 | 0,99794 | 0,85740 | 0,33949 | 2,19484 | 0,88769 | 0,56431 | 0,10512 | 1,55712 | 5,846 | 64,96 |
| 6 | TETA | time evolution travel algorithm (joo) | 0,91362 | 0,82349 | 0,31990 | 2,05701 | 0,97096 | 0,89532 | 0,29324 | 2,15952 | 0,73462 | 0,68569 | 0,16021 | 1,58052 | 5,797 | 64,41 |
| 7 | SDSm | stochastic diffusion search M | 0,93066 | 0,85445 | 0,39476 | 2,17988 | 0,99983 | 0,89244 | 0,19619 | 2,08846 | 0,72333 | 0,61100 | 0,10670 | 1,44103 | 5,709 | 63,44 |
| 8 | 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 |
| 9 | 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 |
| 10 | 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 |
| 11 | 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 |
| 12 | 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 |
| 13 | 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 |
| 14 | 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 |
| 15 | 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 |
| 16 | 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 |
| 17 | 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 |
| 18 | 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 |
| 19 | 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 |
| 20 | 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 |
| 21 | 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 |
| 22 | 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 |
| 23 | 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 |
| 24 | 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 |
| 25 | 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 |
| 26 | 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 |
| 27 | 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 |
| 28 | (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 |
| 29 | 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 |
| 30 | 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 |
| 31 | 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 |
| 32 | 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 |
| 33 | 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 |
| 34 | 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 |
| 35 | 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 |
| 36 | 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 |
| 37 | 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 |
| 38 | SOA | simple optimization algorithm | 0,91520 | 0,46976 | 0,27089 | 1,65585 | 0,89675 | 0,37401 | 0,16984 | 1,44060 | 0,69538 | 0,28031 | 0,10852 | 1,08422 | 4,181 | 46,45 |
| 39 | ABHA | artificial bee hive algorithm | 0,84131 | 0,54227 | 0,26304 | 1,64663 | 0,87858 | 0,47779 | 0,17181 | 1,52818 | 0,50923 | 0,33877 | 0,10397 | 0,95197 | 4,127 | 45,85 |
| 40 | ACMO | atmospheric cloud model optimization | 0,90321 | 0,48546 | 0,30403 | 1,69270 | 0,80268 | 0,37857 | 0,19178 | 1,37303 | 0,62308 | 0,24400 | 0,10795 | 0,97503 | 4,041 | 44,90 |
| 41 | ADAMm | adaptive moment estimation M | 0,88635 | 0,44766 | 0,26613 | 1,60014 | 0,84497 | 0,38493 | 0,16889 | 1,39880 | 0,66154 | 0,27046 | 0,10594 | 1,03794 | 4,037 | 44,85 |
| 42 | CGO | chaos game optimization | 0,57256 | 0,37158 | 0,32018 | 1,26432 | 0,61176 | 0,61931 | 0,62161 | 1,85267 | 0,37538 | 0,21923 | 0,19028 | 0,78490 | 3,902 | 43,35 |
| 43 | ATAm | artificial tribe algorithm M | 0,71771 | 0,55304 | 0,25235 | 1,52310 | 0,82491 | 0,55904 | 0,20473 | 1,58867 | 0,44000 | 0,18615 | 0,09411 | 0,72026 | 3,832 | 42,58 |
| 44 | CROm | coral reefs optimization M | 0,78512 | 0,46032 | 0,25958 | 1,50502 | 0,86688 | 0,35297 | 0,16267 | 1,38252 | 0,63231 | 0,26738 | 0,10734 | 1,00703 | 3,895 | 43,27 |
| 45 | CFO | central force optimization | 0,60961 | 0,54958 | 0,27831 | 1,43750 | 0,63418 | 0,46833 | 0,22541 | 1,32792 | 0,57231 | 0,23477 | 0,09586 | 0,90294 | 3,668 | 40,76 |
| CA | camel algorithm | 0,58729 | 0,38965 | 0,34127 | 1,31821 | 0,52483 | 0,27609 | 0,18882 | 0,98974 | 0,35077 | 0,16677 | 0,10465 | 0,62219 | 2,930 | 32,56 | |
| RW | neuroboids optimization algorithm 2(joo) | 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 | |
Выводы
Модифицированная версия алгоритма верблюда CAm демонстрирует существенно более высокие показатели эффективности по сравнению с оригинальной, благодаря ряду ключевых усовершенствований.
Прежде всего, принципиально изменен механизм "смерти" верблюда — вместо полностью случайной генерации новых решений, используется гауссово распределение вокруг лучшего найденного решения, что обеспечивает целенаправленный и интенсивный поиск в наиболее перспективных областях.
Точное отслеживание улучшений решений через сохранение предыдущих значений фитнес-функции для каждого верблюда, обеспечивает более корректное применение эффекта оазиса. Повышение гибкости алгоритма за счет добавления "Tmin" в настраиваемые параметры и использования внешнего параметра для определения общего количества шагов, делает CAm более адаптивным к различным типам задач оптимизации.
Эти комплексные улучшения, в совокупности, обеспечивают значительное улучшение модифицированной версии в скорости сходимости, точности найденных решений и стабильности работы.
Рисунок 2. Цветовая градация алгоритмов по соответствующим тестам
Рисунок 3. Гистограмма результатов тестирования алгоритмов (по шкале от 0 до 100, чем больше, тем лучше, где 100 — максимально возможный теоретический результат, в архиве скрипт для расчета рейтинговой таблицы)
Плюсы и минусы алгоритма CAm:
Плюсы:
- Быстрый.
- Простая реализация.
- Хорошие результаты на функциях большой и средней размерности (особенно на "гладких" задачах).
Минусы:
- Большое количество внешних параметров.
- Разброс результатов на функциях малой размерности.
К статье прикреплён архив с актуальными версиями кодов алгоритмов. Автор статьи не несёт ответственности за абсолютную точность в описании канонических алгоритмов, во многие из них были внесены изменения для улучшения поисковых возможностей. Выводы и суждения, представленные в статьях, основываются на результатах проведённых экспериментов.
Программы, используемые в статье
| # | Имя | Тип | Описание |
|---|---|---|---|
| 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_CAm.mq5 | Скрипт | Испытательный стенд для CAm |
Как создать торговый журнал с помощью MetaTrader и Google Sheets
Машинное обучение и Data Science (Часть 30): Тандем из сверточных (CNN) и рекуррентных (RNN) нейросетей для прогнозирования фондового рынка
Компьютерное зрение для трейдинга (Часть 2): Усложняем архитектуру до 2D-анализа RGB-изображений
Критерий независимости Гильберта-Шмидта (HSIC)
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Вы принимаете политику сайта и условия использования