Алгоритм искусственного орошения — Artificial Showering Algorithm (ASHA)
35
0
Содержание
Введение
Объемы данных в современном мире стремительно растут, а задачи становятся все более сложными и энергоемкими, необходимость в эффективных методах оптимизации становится как никогда актуальной. Метаэвристические алгоритмы, обладающие высокой сходимостью и быстротой обработки, открывают новые горизонты для решения разнообразных задач в различных областях, от финансовых рынков до научных исследований.
Скорость обработки данных и качество получаемых решений играют ключевую роль в успешной реализации проектов. В условиях жестких временных ограничений, где каждое мгновение может иметь критическое значение, метаэвристические алгоритмы позволяют достигать результатов, которые ранее казались недостижимыми. Они не только обеспечивают быструю обработку больших объемов информации, но и помогают находить более качественные решения по сравнению с традиционными численными методами.
Экономия ресурсов — еще один важный аспект, который необходимо учитывать при оптимизации. В условиях ограниченных вычислительных мощностей, такие алгоритмы требуют меньше времени и памяти, что особенно ценно в облачных вычислениях. Адаптивность алгоритмов к изменяющимся условиям и способность к быстрой реакции на новые данные делают их практически идеальными для динамических систем. Это позволяет поддерживать актуальность решений и повышать эффективность решения задач в реальных условиях.
Сравнение различных алгоритмов по их характеристикам, таким как скорость сходимости, качество решений и устойчивость к застреванию в локальных экстремумах, дает возможность выбирать наиболее качественные из них, что в свою очередь, способствует инновациям и развитию совершенно новых методов, зачастую подсмотренных у природы, и является важным шагом в области оптимизации.
Алгоритм искусственного орошения (ASHA) или Artificial Showering Algorithm представляет собой новый метаэвристический метод, разработанный для решения общих задач оптимизации. Этот алгоритм основан на моделировании процессов потока и накопления воды, распределяемой с помощью управляемого человеком оборудования на идеальном поле. ASHA моделирует процесс распределения воды (орошение) на поле, где вода представляет собой единицы ресурса, а поле — пространство поиска. Алгоритм использует принципы потока и накопления для нахождения оптимальных решений в задачах без ограничений. Алгоритм Искусственного Орошения (ASHA) был разработан группой авторов: Али Дж., М. Саид, Н. А. Чаудри, М. Лукман и М. Ф. Табасум и опубликован в 2015 году.
Реализация алгоритма
Метод основан на следующих постулатах:
- Идеальное поле. Поисковое пространство представляет собой идеальное поле, где вода течет без сопротивления, а инфильтрация происходит только в самой низкой точке.
- Отсутствие внешних факторов. Не происходит ни испарения, ни дождя, ни потока воды.
- Доступность распылителей. Каждая часть поискового пространства находится в пределах досягаемости распылителей, расположенных над полем.
- Постоянное количество воды. Воды в избытке, и ее количество в замкнутой системе остается постоянным на протяжении всех итераций.
- Движение воды. Каждая единица воды имеет вероятностную тенденцию двигаться вниз по склону.
Описание алгоритма ASHA (Artificial Showering Algorithm) по шагам.
Параметры алгоритма:
- f - целевая функция, которую нужно минимизировать
- R*n - n-мерное пространство поиска
- K - текущее положение в счетчике итераций
- m - количество единиц воды (агентов поиска)
- F - скорость потока воды
- δ - уровень сопротивления (порог инфильтрации)
- ρ₀ - начальная вероятность
- β - параметр, контролирующий скорость изменения вероятности
- M - максимальное количество итераций
Шаги алгоритма:
1. Инициализация:
Устанавливаем начальное значение ρ = ρ₀
Создаем m единиц воды и размещаем их случайным образом в пространстве поиска R*n
2. Оценка ландшафта: для каждой единицы воды вычисляем значение целевой функции f в её текущей позиции
3. Основной цикл (повторяем M раз): для каждой единицы воды i (1 ≤ i ≤ m):
a) Выбираем случайное число r_i ∈ (0, 1)
b) Если r_i < ρ:
Выбираем случайную позицию x_lower ниже текущей
Генерируем случайный вектор s ∈ (0, 1)*n
Вычисляем новую позицию:
x_new = x_old + F × (s ∘ (x_lower x_old))
где ∘ обозначает поэлементное умножение
Если x_new находится на более низком уровне, чем x_old:
Принимаем новую позицию
Иначе:
Генерируем случайное число r ∈ (0, 1)
Находим самую низкую позицию x_lowest среди всех единиц воды
Вычисляем новую позицию:
x_new = x_old + F × r × (x_lowest x_old)
c) Проверка инфильтрации:
Если единица воды преодолела уровень сопротивления δ:
Создаем новую единицу воды в случайной позиции
d) Сравнение с самой низкой позицией:
Находим единицу воды с самым низким значением целевой функции
Если текущая единица воды имеет меньшее значение, меняем их местами
e) Обновление вероятности ρ = max((M - K) / (β × M), ρ₀)
4. Завершение:
Находим единицу воды с наименьшим значением целевой функции
Возвращаем её позицию как наилучшее найденное решение
Пояснения к алгоритму:
1. Алгоритм имитирует процесс орошения поля, где каждая единица воды представляет собой агент поиска.
2. Пространство поиска рассматривается как ландшафт, где более низкие значения целевой функции соответствуют более низким точкам рельефа.
3. Единицы воды стремятся "стечь" в нижние точки ландшафта, что соответствует поиску минимума целевой функции.
4. Параметр ρ контролирует баланс между исследованием пространства (большие значения ρ) и эксплуатацией найденных решений (малые значения ρ).
5. Механизм инфильтрации позволяет избежать застревания в локальных минимумах, создавая новые единицы воды в случайных позициях.
6. Сравнение и обмен с самой низкой позицией обеспечивает сохранение лучшего найденного решения.
7. Динамическое обновление ρ позволяет алгоритму постепенно переходить от исследования к эксплуатации по мере увеличения числа итераций.
Алгоритм использует аналогию водного потока для оптимизации, где вода (агенты поиска) стремится найти самые низкие точки в ландшафте (минимумы целевой функции).
По словам авторов, основными преимуществами этого алгоритма являются:
- Способность исследовать большое пространство решений благодаря случайному движению воды.
- Возможность избегать локальных минимумов с помощью механизма инфильтрации.
- Адаптивное поведение благодаря динамическому изменению вероятности ρ.
Рассмотрим подробно все формулы, которые используются алгоритмом.
1. Формула обновления позиции в случае исполнения вероятности "ρ": x_new = x_old + F × (s ∘ (x_lower - x_old)), где:
- x_new - новая позиция единицы воды
- x_old - текущая позиция единицы воды
- F - скорость потока воды (параметр алгоритма)
- s - случайный вектор в диапазоне (0, 1)
- x_lower - случайно выбранная позиция ниже текущей
- ∘ - оператор поэлементного умножения
Формула моделирует движение воды вниз по склону. Случайный вектор "s" добавляет элемент случайности в движение, а "F" контролирует величину шага.
2. Альтернативная формула, в случае неисполнения вероятности "ρ", обновления позиции: x_new = x_old + F × r × (x_lowest - x_old), где:
- r - случайное число в диапазоне (0, 1)
- x_lowest - позиция с самым низким значением целевой функции
Формула используется, когда основная формула не приводит к улучшению. Она направляет единицу воды в сторону глобального минимума.
Как видно из этих формул, вода всегда стремится в сторону позиций, которые ниже её текущей позиции. Если реализовать алгоритм только до этого шага, то он обязательно будет застревать в локальных экстремумах.
3. Формула обновления вероятности, ρ = max ((M - K) / (β × M), ρ₀), где:
- ρ - текущая вероятность движения воды
- M - максимальное количество итераций
- K - номер текущей итерации
- β - параметр, контролирующий скорость изменения вероятности
- ρ₀ - начальная вероятность
Эта формула постепенно уменьшает вероятность движения воды в сторону случайно выбранных более низких позиций и увеличивает вероятность движения в сторону глобального минимума. Это позволяет алгоритму перейти от исследования пространства к уточнению найденных решений.
4. Условие инфильтрации, если f (x_current) < δ, то создается новая единица воды, где:
- f (x_current) - значение целевой функции в текущей позиции
- δ - уровень сопротивления (порог инфильтрации)
Это условие позволяет создавать новые единицы воды в случайных позициях, когда текущая единица воды находит достаточно низкую точку. Это задумано, чтобы избегать застревания в локальных минимумах.
5. Сравнение позиций, если f (x_i) < f (x_lowest), то поменять x_i и x_lowest местами, где:
- f (x_i) - значение целевой функции для i-й единицы воды
- f (x_lowest) - наименьшее найденное значение целевой функции
Формулы выше составляют основу алгоритма ASHA.
- Формула обновления позиции имитирует движение воды вниз по склону. Случайный элемент (s или r) добавляет разнообразие в поиск, позволяя исследовать различные области пространства решений.
- Альтернативная формула обновления позиции используется с увеличением вероятности с каждой новой итерацией для обеспечения повышения степени уточнения глобального решения на протяжении всех итераций.
- Формула обновления вероятности ρ обеспечивает баланс между исследованием и эксплуатацией. В начале алгоритма вероятность движения в сторону случайно выбранных более низких позиций ландшафта высока, что способствует широкому исследованию пространства. По мере выполнения итераций вероятность уменьшается, что приводит к более тщательному исследованию перспективных областей.
- Условие инфильтрации позволяет алгоритму "перезапускать" поиск из новых случайных позиций, когда найдено достаточно хорошее решение. Это помогает избежать застревания в локальных минимумах.
- Сравнение позиций обеспечивает, что алгоритм всегда "помнит" лучшее найденное решение и использует его для направления дальнейшего поиска.
Таким образом, суть в том, что алгоритм сначала пытается найти лучшую позицию, двигаясь к случайной нижней точке. Если это не удается, он пытается двигаться в направлении глобально лучшей найденной позиции. Это обеспечивает баланс между локальным поиском и глобальным исследованием пространства решений.
Принцип инфильтрации в алгоритме ASHA может быть неочевидным на первый взгляд. Давайте вместе разберем его подробнее:
- У нас есть параметр δ (дельта), который называется уровнем сопротивления или порогом инфильтрации.
- На каждой итерации для каждой единицы воды мы проверяем, не стала ли она "слишком хорошей", то есть не опустилась ли она ниже уровня δ.
- Если значение целевой функции для данной единицы воды становится меньше δ, то считается, что вода "просочилась" или "инфильтровалась" в землю.
- В этом случае мы "создаем" новую единицу воды, помещая ее в случайную позицию в пространстве поиска.
Формально это можно записать так: если f (x_i) < δ, то x_i = случайная_позиция (), где f (x_i) — значение целевой функции для i-й единицы воды, x_i — позиция i-й единицы воды.
Смысл этого механизма в том, чтобы избежать застревания всех единиц воды в одном локальном минимуме; стараться продолжить исследование пространства поиска даже после нахождения хорошего решения; потенциально находить еще лучшие решения в неисследованных областях.
Важно правильно выбрать значение δ. Если δ слишком мало, инфильтрация может не произойти вовсе; если же δ слишком велико, алгоритм может постоянно "перезапускаться", не успевая найти оптимальное решение. Кроме того, определение подходящего значения δ может оказаться нетривиальной задачей, особенно когда мы не знаем заранее диапазон значений целевой функции и не можем установить этот параметр как внешний. Поэтому я ввёл счетчик попыток "просочиться" для каждой капли, а во внешнем параметре необходимо задать его максимальное значение. С каждой новой попыткой вероятность "просачивания" увеличивается по квадратичному закону, то есть с ускорением. Таким образом, ни одна капля не будет слишком долго оставаться в одном месте, что поможет избежать застревания в локальных экстремумах.
Рисунок 1. Примеры изменения вероятности инфильтрации в зависимости от числа попыток
Что касается использования координат низшей точки, обычно применяется следующий подход:
- Находится единица воды с наименьшим значением целевой функции (назовем ее x_lowest).
- При обновлении позиции используются все координаты этой низшей точки: x_new = x_old + F × r × (x_lowest - x_old). Здесь x_new, x_old и x_lowest — это векторы, содержащие все координаты.
- Это векторное уравнение применяется ко всем координатам одновременно. То есть, новая позиция "притягивается" к низшей точке по всем измерениям пространства поиска.
Такой подход позволяет направить поиск к наиболее перспективной области пространства решений, учитывая все измерения одновременно.
Как будто бы все, на чем мы хотели заострить ваше внимание, было сказано, теперь перейдем к написанию кода алгоритма. Да, еще один момент, для этого алгоритма и, возможно, если понадобится, для последующих, необходимо было расширить стандартную структуру для хранения дополнительной информации об агенте оптимизации, введенные поля обозначены зеленым цветом.
Вспомним, как выглядит стандартная структура агента оптимизации, к которой обращается пользовательская программа, "S_AO_Agent", с дополнениями она выглядит так:
1. Поля структуры:
- c [] - массив текущих координат агента в пространстве поиска.
- cP [] - массив предыдущих координат агента.
- cB [] - массив наилучших координат, найденных агентом за все время.
- f - значение функции приспособленности (fitness) для текущих координат агента для оценки насколько хорошо агент справляется с задачей.
- fP - значение функции приспособленности для предыдущих координат для отслеживания изменения производительности агента.
- fB - значение функции приспособленности для наилучших координат, сохраняет наилучший результат, достигнутый агентом.
- cnt - счетчик для отслеживания количества итераций.
2. Init () - метод инициализации принимает количество координат, необходимых для агента и выполняет следующие действия:
- изменяет размер массива "c" до "coords", выделяя память для хранения текущих координат.
- аналогично изменяет размер массива "cP" для хранения предыдущих координат и размер массива "cB" для хранения наилучших координат.
- инициализирует текущее значение функции приспособленности минимально возможным значением, что позволяет агенту обновлять его при первой оценке.
- инициализирует предыдущее и наилучшее значение функции приспособленности аналогичным образом.
- инициализирует значение счетчика в ноль.
Итак, структура "S_AO_Agent" позволяет хранить информацию о текущем состоянии агента, его производительности и истории изменений. Внесённые изменения в структуру никак не повлияют на уже написанные на ее основе алгоритмы оптимизации, но позволит упростить построение новых алгоритмов в дальнейшем.
//—————————————————————————————————————————————————————————————————————————————— struct S_AO_Agent { double c []; //coordinates double cP []; //previous coordinates double cB []; //best coordinates double f; //fitness double fP; //previous fitness double fB; //best fitness int cnt; //counter void Init (int coords) { ArrayResize (c, coords); ArrayResize (cP, coords); ArrayResize (cB, coords); f = -DBL_MAX; fP = -DBL_MAX; fB = -DBL_MAX; cnt = 0; } }; //——————————————————————————————————————————————————————————————————————————————
Класс "C_AO_ASHA" наследуется от базового класса "C_AO" и представляет собой реализацию алгоритма оптимизации ASHA, разберем его структуру и функциональность:
- F, δ, β, ρ0 - параметры, специфичные для алгоритма, описанные ранее, определяют его поведение.
- params - массив структур хранит параметры алгоритма. Каждый элемент массива содержит имя параметра и его значение.
Метод "SetParams ()" используется для установки значений параметров алгоритма из массива "params".
Метод "Init ()" инициализирует алгоритм, принимая на вход минимальные и максимальные границы поиска, шаг поиска и количество эпох.
Методы "Moving ()" и "Revision ()" отвечают за перемещение агентов в пространстве поиска, за пересмотр и обновление состояния агентов и их позиций на основе критериев оптимизации.
Приватные поля:
- S_AO_Agent aT [] - массив для временной популяции, используется для сортировки популяции.
- epochs - общее количество эпох, используемое в процессе оптимизации.
- epochNow - текущая эпоха, в которой находится алгоритм.
Класс "C_AO_ASHA" включает в себя параметры, методы и структуры, необходимые для управления процессом оптимизации и взаимодействия агентов.
//—————————————————————————————————————————————————————————————————————————————— class C_AO_ASHA : public C_AO { public: //-------------------------------------------------------------------- ~C_AO_ASHA () { } C_AO_ASHA () { ao_name = "ASHA"; ao_desc = "Artificial Showering Algorithm"; ao_link = "https://www.mql5.com/ru/articles/15980"; popSize = 100; //population size F = 0.3; //water flow velocity δ = 2; //resistance level(infiltration threshold) β = 0.8; //parameter that controls the rate of change in probability ρ0 = 0.1; //initial probability ArrayResize (params, 5); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "F"; params [1].val = F; params [2].name = "δ"; params [2].val = δ; params [3].name = "β"; params [3].val = β; params [4].name = "ρ0"; params [4].val = ρ0; } void SetParams () { popSize = (int)params [0].val; F = params [1].val; δ = (int)params [2].val; β = params [3].val; ρ0 = params [4].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 (); //---------------------------------------------------------------------------- double F; //water flow velocity int δ; //resistance level(infiltration threshold) double β; //parameter that controls the rate of change in probability double ρ0; //initial probability private: //------------------------------------------------------------------- S_AO_Agent aT []; int epochs; int epochNow; }; //——————————————————————————————————————————————————————————————————————————————
Метод "Init" отвечает за инициализацию алгоритма оптимизации. Логика метода:
1. Проверка стандартной инициализации: метод вызывает "StandardInit", который выполняет базовые проверки и инициализацию параметров.
2. Установка счетчиков:
- epochs - устанавливается равным переданному значению "epochsP" (общее количество итераций, которые алгоритм должен выполнить).
- epochNow - инициализируется нулем, алгоритм только начинает выполнение и еще не провел ни одной эпохи.
3. Резервирование памяти для временной популяции агентов.
4. Если все этапы инициализации прошли успешно, метод возвращает "true", указывая на успешную инициализацию алгоритма.
Метод "Init" является ключевым для подготовки алгоритма к работе. Он проверяет корректность входных параметров, устанавливает необходимые значения для управления процессом оптимизации и выделяет память для агентов. Успешная инициализация позволяет алгоритму продолжать выполнение дальнейших операций, таких как перемещение и пересмотр агентов.
//—————————————————————————————————————————————————————————————————————————————— bool C_AO_ASHA::Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0) { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //---------------------------------------------------------------------------- epochs = epochsP; epochNow = 0; ArrayResize (aT, popSize); return true; } //——————————————————————————————————————————————————————————————————————————————
Метод "Moving" реализует логику перемещения агентов в пространстве поиска в рамках алгоритма ASHA, разберем его по шагам:
1. Метод увеличивает счетчик текущей эпохи, что позволяет отслеживать количество выполненных итераций.
2. Первоначальная инициализация (если не требуется ревизия): для каждого агента "i" и для каждой координаты "c"
- метод генерирует начальные позиции для всех агентов в пределах заданных диапазонов с помощью "u.RNDfromCI" и применяет дискретизацию.
- после этого "revision" устанавливается в "true", и метод завершает выполнение.
3. Основной цикл перемещения агентов, для каждого агента "i" выполняются следующие действия:
- inf - вероятность, вычисляется с использованием "u.Scale", чтобы получить значение, зависящее от счетчика "cnt" агента. Это значение затем возводится в четвертую степень для усиления влияния.
- генерируется случайное число "rnd" для принятия решений.
4. Цикл по координатам, для каждой координаты "c" выполняются следующие действия:
- генерируется индекс "ind" для выбора другого агента с более низкой позицией в пространстве поиска, который будет использоваться для обновления координат.
- если "i < 1", то: если "rnd < inf", то координаты текущего агента обновляются с использованием нормального распределения вокруг лучших координат "cB" с помощью "u.GaussDistribution".
- если "i >= 1", то: если "rnd < inf", то аналогично обновляются координаты текущего агента относительно координат другого агента "a[ind].cB".
- в противном случае: сохраняется старое значение "xOld". Если сгенерированное случайное число меньше "ρ", то:
- обновляется "xNew" на основе лучшего значения другого агента "xLower".
- в противном случае: обновляется "xNew" на основе глобального лучшего значения "xLowest".
- затем новое значение "xNew" присваивается текущему агенту.
5. Коррекция координат: наконец, каждое новое значение координаты корректируется с использованием "u.SeInDiSp", чтобы оно соответствовало заданным диапазонам и шагам.
Метод "Moving" обеспечивает как инициализацию позиций агентов, так и обновление, в процессе оптимизации основываясь на их текущем состоянии и взаимодействии с другими агентами.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_ASHA::Moving () { epochNow++; //---------------------------------------------------------------------------- if (!revision) { 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]); } } revision = true; return; } //---------------------------------------------------------------------------- double xOld = 0.0; double xNew = 0.0; double xLower = 0.0; double xLowest = 0.0; double ρ = MathMax (β * (epochs - epochNow) / epochs, ρ0); double inf = 0.0; int ind = 0; double rnd = 0.0; for (int i = 0; i < popSize; i++) { inf = u.Scale (a [i].cnt, 0, δ, 0, 1); inf = inf * inf * inf * inf; rnd = u.RNDprobab (); for (int c = 0; c < coords; c++) { ind = (int)u.RNDintInRange (0, i - 1); if (i < 1) { if (rnd < inf) { a [i].c [c] = u.GaussDistribution (cB [c], rangeMin [c], rangeMax [c], 8); } } else { if (rnd < inf) { a [i].c [c] = u.GaussDistribution (a [ind].cB [c], rangeMin [c], rangeMax [c], 8); } else { xOld = a [i].c [c]; if (u.RNDprobab () < ρ) { xLower = a [ind].cB [c]; xNew = xOld + F * (u.RNDprobab () * (xLower - xOld)); } else { xLowest = cB [c]; xNew = xOld + F * (u.RNDprobab () * (xLowest - xOld)); } a [i].c [c] = xNew; } } a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } } //——————————————————————————————————————————————————————————————————————————————
Метод "Revision" отвечает за обновление информации о лучших решениях (агентах) в популяции, а также за отслеживание их приспособленности, далее по шагам:
1. Переменная "ind" инициализируется значением "-1" и будет использоваться для хранения индекса агента с наилучшим значением функции приспособленности "f".
2. Цикл по агентам: метод проходит по всем агентам в популяции "popSize":
- если значение функции приспособленности "f" текущего агента больше, чем его текущее наилучшее значение "fB", то обновляется "fB" и сохраняется индекс этого агента в переменной "ind".
- если значение функции приспособленности "f" текущего агента больше, чем его локальное наилучшее значение "fB", то также обновляется локальное наилучшее значение "fB" для этого агента.
- копируются координаты "c" агента в "cB", это его лучшие известные координаты.
- счетчик "cnt" сбрасывается на "0", в противном случае, если значение функции приспособленности не улучшилось, увеличивается счетчик "cnt".
3. Копирование лучших координат: если был найден агент с наилучшим значением функции (индекс "ind" не равен "-1"), то его координаты копируются в глобальную переменную "cB".
4. Сортировка агентов: в конце вызывается метод "u.Sorting_fB", сортирует агентов по их локальным наилучшим значениям "fB".
Метод "Revision" играет основную роль в алгоритме, отслеживая производительность агентов и обновляя их лучшие известные решения.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_ASHA::Revision () { //---------------------------------------------------------------------------- int ind = -1; for (int i = 0; i < popSize; i++) { if (a [i].f > fB) { fB = a [i].f; ind = i; } if (a [i].f > a [i].fB) { a [i].fB = a [i].f; ArrayCopy (a [i].cB, a [i].c, 0, 0, WHOLE_ARRAY); a [i].cnt = 0; } else { a [i].cnt++; } } if (ind != -1) ArrayCopy (cB, a [ind].c, 0, 0, WHOLE_ARRAY); //---------------------------------------------------------------------------- u.Sorting_fB (a, aT, popSize); } //——————————————————————————————————————————————————————————————————————————————
Результаты тестов
Результаты тестов алгоритма ASHA показали среднюю производительность: =============================
5 Hilly's; Func runs: 10000; result: 0.8968571984324711
25 Hilly's; Func runs: 10000; result: 0.40433437407600525
500 Hilly's; Func runs: 10000; result: 0.25617375427148387
=============================
5 Forest's; Func runs: 10000; result: 0.8036024134603961
25 Forest's; Func runs: 10000; result: 0.35525531625936474
500 Forest's; Func runs: 10000; result: 0.1916000538491299
=============================
5 Megacity's; Func runs: 10000; result: 0.4769230769230769
25 Megacity's; Func runs: 10000; result: 0.1812307692307692
500 Megacity's; Func runs: 10000; result: 0.09773846153846236
=============================
All score: 3.66372 (40.71%)
Наблюдая за работой ASHA на тестовом стенде, сложно выявить какие-либо характерные черты этого алгоритма, обособленные исследования перспективных участков поискового пространства не обнаруживаются.
ASHA на тестовой функции Hilly
ASHA на тестовой функции Forest
ASHA на тестовой функции Megacity
По итогам проведенных тестов алгоритм ASHA занял 28 место в рейтинговой таблице.
| № | 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 | 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 | 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 | 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 |
| 7 | 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 |
| 8 | 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 |
| 9 | 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 |
| 10 | 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 |
| 11 | 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 |
| 12 | 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 |
| 13 | 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 |
| 14 | 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 |
| 15 | 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 |
| 16 | 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 |
| 17 | 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 |
| 18 | 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 |
| 19 | (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 |
| 20 | 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 |
| 21 | 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 |
| 22 | 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 |
| 23 | 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 |
| 24 | 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 |
| 25 | 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 |
| 26 | 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 |
| 27 | 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 |
| 28 | ASHA | artificial showering algorithm | 0,89686 | 0,40433 | 0,25617 | 1,55737 | 0,80360 | 0,35526 | 0,19160 | 1,35046 | 0,47692 | 0,18123 | 0,09774 | 0,75589 | 3,664 | 40,71 |
| 29 | ASBO | adaptive social behavior optimization | 0,76331 | 0,49253 | 0,32619 | 1,58202 | 0,79546 | 0,40035 | 0,26097 | 1,45677 | 0,26462 | 0,17169 | 0,18200 | 0,61831 | 3,657 | 40,63 |
| 30 | 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 |
| 31 | 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 |
| 32 | 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 |
| 33 | 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 |
| 34 | 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 |
| 35 | 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 |
| 36 | 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 |
| 37 | 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 |
| 38 | 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 |
| 39 | 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 |
| 40 | 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 |
| 41 | AAA | algae adaptive algorithm | 0,50007 | 0,32040 | 0,25525 | 1,07572 | 0,37021 | 0,22284 | 0,16785 | 0,76089 | 0,27846 | 0,14800 | 0,09755 | 0,52402 | 2,361 | 26,23 |
| 42 | 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 |
| 43 | 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 |
| 44 | 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 |
| 45 | 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 |
Выводы
Идея алгоритма мне понравилась, однако при реализации и тестировании возникло ощущение, что алгоритму чего-то не хватает. Нельзя сказать, что его результаты самые слабые, но и до лучших ему далеко. Это создаёт возможность для исследователей продолжить работу с ним, особенно благодаря его простоте, поскольку сама идея, на мой взгляд, очень перспективна. Кроме того, авторы не предоставили более детального объяснения коэффициента инфильтрации, что позволяет интерпретировать его по-разному, ограничиваясь лишь фантазией исследователя.
Основной вывод, который можно сделать из данной статьи, заключается в следующем: не каждая простая идея оказывается столь же эффективной, как и более сложная. Эффективность алгоритма оптимизации — это сложная субстанция и выбор компромиссных решений. Надеюсь, что этот алгоритм станет ещё одной страницей в большой книге знаний о тонкостях и хитростях искусства нахождения наилучших решений.
Рисунок 2. Цветовая градация алгоритмов по соответствующим тестам. Белым цветом подсвечены результаты больше или равные 0.99
Рисунок 3. Гистограмма результатов тестирования алгоритмов (по шкале от 0 до 100, чем больше, тем лучше,
где 100 - максимально возможный теоретический результат, в архиве скрипт для расчета рейтинговой таблицы)
Плюсы и минусы алгоритма ASHA:
Плюсы:
- Быстрый.
- Простая реализация.
Минусы:
- Невысокая точность сходимости.
К статье прикреплён архив с актуальными версиями кодов алгоритмов. Автор статьи не несёт ответственности за абсолютную точность в описании канонических алгоритмов, во многие из них были внесены изменения для улучшения поисковых возможностей. Выводы и суждения, представленные в статьях, основываются на результатах проведённых экспериментов.
Построение модели ограничения тренда свечей (Часть 3): Обнаружение изменений трендов при использовании системы
Возможности Мастера MQL5, которые вам нужно знать (Часть 20): Символьная регрессия
Разрабатываем мультивалютный советник (Часть 18): Автоматизация подбора групп с учётом форвард-периода
Нейросети в трейдинге: Сегментация данных на основе уточняющих выражений
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Вы принимаете политику сайта и условия использования