Алгоритм анархической социальной оптимизации — Anarchic Society Optimization (ASO)
400
0
Содержание
1. Введение
Меня всегда привлекала тема социальных отношений и возможности построения алгоритма в концепции социальных связей, так как это является наиболее интересным явлением в развитии общества, и предполагает обширное поле деятельности для возможностей алгоритмически описать структуру системы взаимоотношений и реализовать на этом алгоритм оптимизации.
Ранее в статьях мы уже рассматривали алгоритмы социального поведения, такие как evolution of social groups, artificial cooperative search. В данной статье мы постараемся разобраться с концепцией анархического общества — системой социального взаимодействия, в которой отсутствует централизованная власть и иерархические структуры, и предполагается, что люди могут организовывать свою жизнь и взаимодействовать на основе добровольных соглашений.
В основе анархического общества заложены принципы автономии и свободы, когда каждый человек может самостоятельно и независимо принимать решения, касающиеся своей жизни, без внешнего вмешательства, принципы добровольного сотрудничества, при которых люди взаимодействуют на основе согласия всех участников без принуждения, равенства прав и возможностей, а также принципы солидарности, взаимопомощи и сотрудничества. Идея очень интересная для реализации алгоритма, и уже есть попытки воплощения такого социального построения в алгоритм оптимизации Anarchic Society Optimization (ASO). Алгоритм был предложен Ахмади Джавидом и опубликован в 2011 году.
Основной идеей, которую пытался донести создатель алгоритма ASO, является разработка оптимизационного метода, инспирированного поведением индивидуумов в анархических обществах. В отличие от существующих методов роевого интеллекта, разработанных на основе роев насекомых или животных, таких как PSO и ACO, разработка алгоритма на основе изучения построения стандартного общества людей может иметь лишь ограниченный успех, поскольку хорошо организованный социум не имеет возможности достичь своих желаний индивидуальными решениями. Кроме того, ни один из членов общества не является действительно независимым и автономным, и не может радикально улучшить свою ситуацию за определенный период времени. Осознание этого привело создателя алгоритма к идее заимствовать основную концепцию для разработки у общества, основанного на аномальном устройстве.
Основой ASO является группа индивидуумов, они непостоянны, авантюрны, не любят стабильности и часто ведут себя иррационально, перемещаясь к худшим позициям, которые посетили в фазе исследования. Уровень анархического поведения среди членов усиливается по мере увеличения различий в их ситуациях. Используя этих участников, ASO исследует пространство решений и старается избегать попадания в ловушки локального оптимума. Таким образом, создатель ASO пытается донести мысль о том, что изучение и применение принципов, основанных на аномальном поведении сообщества, может привести к созданию эффективных алгоритмов, способных решать сложные задачи оптимизации. Мы рассмотрим унифицированную структуру для ASO, которая может быть легко использована как для непрерывных, так и для дискретных задач.
2. Реализация алгоритма
Перед написанием кода алгоритма нам необходимо понять, как он устроен, и какие основные механизмы в него заложил автор. Алгоритм ASO представляет собой метод оптимизации, который сочетает в себе преимущества алгоритма particle swarm optimisation (PSO) с новыми механизмами, характерными для анархического социального поведения. Адаптивная природа и способность балансировать между различными стратегиями движения является основной "изюминкой" алгоритма.
Начнем с подробного описания алгоритма ASO:
1. Инициализация:
- Создается популяция (popSize) из членов общества.
- Каждый член инициализируется случайной позицией в пространстве поиска.
- Для каждого члена сохраняется его личная лучшая и предыдущая позиции.
2. Основной цикл оптимизации:
На каждой итерации алгоритм выполняет следующие шаги для каждого члена общества:
a) Расчет индексов:
- Fickleness Index (FI) — индекс непостоянства отражает нестабильность члена общества и измеряет его недовольство по сравнению с другими индивидуумами.
- External Irregularity Index (EI) — внешний индекс нерегулярности оценивает разнообразие позиций в обществе и показывает отклонение от глобального лучшего решения.
- Internal Irregularity Index (II) — внутренний индекс нерегулярности оценивает изменения положения индивидуума за итерацию и отражает отклонение от личного лучшего решения.
b) Выбор политики движения:
На основе сравнения индексов FI, EI и II выбирается одна из трех политик движения:
- Current Movement Policy (CurrentMP) — использует формулу PSO с инерцией и коэффициентами ускорения.
- Society Movement Policy (SocietyMP) — применяет кроссовер со случайно выбранным членом общества.
- Past Movement Policy (PastMP) — использует информацию о предыдущей позиции индивидуума.
c) Анархическое поведение: с вероятностью "anarchyProb" позиция индивидуума может быть полностью рандомизированна.
d) Обновление позиции: новая позиция проверяется на соответствие ограничениям пространства поиска.
e) Обновление лучших позиций:
- Обновляется личная лучшая позиция "pBest", если текущая позиция лучше.
- Обновляется глобальная лучшая позиция "gBest", если найдено новое лучшее решение.
3. Адаптация параметров:
- Вероятность анархического поведения "anarchyProb" постепенно уменьшается.
- Параметр "alpha" для расчета "FI" постепенно увеличивается.
- Инерционный вес "omega" постепенно уменьшается.
4. Параметры алгоритма:
- popSize — размер популяции.
- omega, lambda1, lambda2 - параметры для расчета скорости в "CurrentMP" (как в PSO).
- anarchyProb — вероятность анархического поведения.
- alpha, theta, delta — параметры для расчета индексов "FI","EI", "II" соответственно.
Алгоритм достаточно сложный и я постараюсь очень доходчиво и структурировано для простоты понимания расписать его механизм работы. Следующим шагом разберем формулы, задействованные в алгоритме.
Основная формула в алгоритме ASO унаследована из алгоритма PSO и представляет собой вычисление обновления скорости: V_i (k+1) = ω * V_i (k) + λ1 * r1 * (P_i (k) - X_i (k)) + λ2 * r2 * (G (k) - X_i (k)), где:
- V_i (k) — скорость частицы "i"в итерации "k".
- X_i (k) — позиция частицы "i" в итерации "k".
- P_i (k) — лучшая позиция, найденная частицей "i" до итерации "k".
- G (k) — глобально лучшая позиция, найденная всеми частицами до итерации "k".
- ω — инерционный коэффициент.
- λ1, λ2 — коэффициенты ускорения.
- r1, r2 — случайные числа из интервала (0, 1).
Автор указывает, что формула PSO является частным случаем общей структуры ASO, когда определены соответствующие политики движения и правило комбинации. В оригинальной версии участвовала в расчетах предыдущая скорость агента. Я изменил подход, оставив только текущее значение скорости, что привело к заметному улучшению результативности алгоритма.
Формулы (1) и (2) определяют индекс изменчивости "fickleness index", "FI" для члена общества "i" на итерации "k" в алгоритме ASO. Эти формулы помогают оценить степень неудовлетворенности индивидуума своей текущей позицией по сравнению с другими позициями. Рассмотрим их подробно:
1. Формула (1) для вычисления индекса непостоянства: (kFI)i = α - α (f (Xi (k)) - f (Pi (k))) / (f (Xi (k*)) - f (Xi (k))).
Эта формула показывает, насколько текущая позиция индивидуума "i" отличается от его лучшей личной позиции и лучшей глобальной позиции, взвешенной с учетом параметра "α" (alpha).
2. Формула (2) для вычисления индекса непостоянства индивидуума "i" на итерации "k": (kFI)i = α - α (f (Xi (k)) - f (Pi (k))) / (f (G (k)) - f (Xi (k))).
Эта формула аналогична первой, но используется для других целей, там где сравниваются текущая позиция, лучшая личная позиция и лучшая глобальная позиция.
Обе формулы служат для оценки степени неудовлетворенности членов общества, что позволяет им принимать более обоснованные решения о том, как изменять свои позиции в поиске оптимального решения.
Формулы (3) и (4) описывают индексы внешней и внутренней изменчивости "external irregularity index" и "internal irregularity index" для членов общества в алгоритме.
3. Формула (3) — внешний индекс изменчивости индивидуума "i" на итерации "k": (kEI)i = exp (-(θi) (f (G) - f (Xi (k)))).
4. Формула (4) — внутренний индекс изменчивости индивидуума "i" на итерации "k": (kEI)i = 1 - exp (-δi (kD)).
Где:
- (kFI)i — индекс непостоянства индивидуума "i" на итерации "k".
- α — неотрицательное число "alpha" в интервале [0,1].
- f (Xi (k)) — значение целевой функции для позиции индивидуума "i" на итерации "k".
- f (Pi (k)) — значение целевой функции для лучшей позиции, ранее посещенной индивидуумом "i".
- f (Xi (k)) — значение целевой функции для позиции лучшего индивидуума на итерации "k".
- f (G (k)) — значение целевой функции для глобально лучшей позиции, посещенной обществом до итерации "k".
- (kEI)i — индекс внешней нерегулярности индивидуума "i" на итерации "k".
- θi — положительное число "theta".
- kD — подходящая мера разнообразия в обществе, например, коэффициент вариации значений целевой функции индивидуумов.
- δi — положительное число "delta".
Эти формулы показывают, что если разнообразие в обществе увеличивается (то есть, индивидуумы имеют более отличающиеся значения целевой функции), индивидуумы будут более склонны вести себя нерегулярно. Формулы служат для оценки изменчивости поведения членов общества в алгоритме ASO, что позволяет им принимать более разнообразные и адаптивные решения в процессе поиска оптимального решения.
Рисунок 1. Если текущее лучшее решение агента (200) намного меньше по значению к лучшему решению по популяции агентов (1000), то линия на графике изменяется практически линейно.
Рисунок 2. Чем меньше разница между текущим лучшим решением агента (800) и лучшим решением по популяции агентов (1000), тем больше линия на графике нелинейна.
Рисунок 3. График зависимости индексов внешней и внутренней нерегулярностей в зависимости от коэффициентов "theta" и "delta" (на примере значений от 0.01 до 0.9).
Таким образом, члены общества могут использовать информацию о других членах для принятия решений о своих движениях, а также как их поведение может варьироваться в зависимости от уровня разнообразия в обществе.
Теперь мы уже немного больше знаем об алгоритме ASO и на основе полученной теории можем перейти к практической части, т.е. составим псевдокод алгоритма для его реализации в коде. Алгоритм ASO псевдокод:
Инициализация:
1. Задать параметры: popSize, omega, lambda1, lambda2, anarchyProb, alpha, theta, delta, rangeMin [], rangeMax [], rangeStep []
2. Создать популяцию из popSize членов: для каждого члена i от 0 до popSize-1: для каждой координаты c от 0 до coords-1:
position [i].[c] = случайное число между rangeMin [c] и rangeMax [c]
pBest [i].[c] = position [i].[c]
prevPosition [i].[c] = position [i].[c]
pBestFitness [i] = -бесконечность
3. Установить gBest = лучшая позиция из начальной популяции
4. Установить gBestFitness = фитнес gBest
Основной цикл:
5. Пока не достигнут критерий остановки: для каждого члена i от 0 до popSize-1:
5.1 Рассчитать индексы
FI = CalculateFI (i)
EI = CalculateEI (i)
II = CalculateII (i)
5.2 Выбрать политику движения
Если FI > EI и FI > II: newPosition = CurrentMP (i)
Иначе если EI > FI и EI > II: newPosition = SocietyMP (i)
Иначе: newPosition = PastMP (i)
5.3 Применить анархическое поведение
Если случайное число < anarchyProb: для каждой координаты c от 0 до coords-1:
newPosition [c] = случайное число между rangeMin [c] и rangeMax [c]
5.4 Обновить позицию для каждой координаты c от 0 до coords-1:
prevPosition [i].[c] = position [i].[c]
position [i].[c] = ограничить (newPosition [c], rangeMin [c], rangeMax [c], rangeStep [c])
5.5 Оценить новую позицию fitness = оценить_фитнес (position [i])
5.6 Обновить личный best если fitness > pBestFitness [i]:
pBestFitness [i] = fitness
pBest [i] = position [i]
5.7 Обновить глобальный best если fitness > gBestFitness:
gBestFitness = fitness
gBest = position [i]
5.8 Адаптировать параметр AdaptParameters ()
5.9 Функция CalculateFI (i): return 1 - alpha * (fitness [i] - pBestFitness [i]) / (gBestFitness - fitness [i])
5.10 Функция CalculateEI (i): return 1 - exp(-(gBestFitness - fitness [i]) / theta)
5.11 Функция CalculateII (i): return 1 - exp(-(pBestFitness [i] - fitness [i]) / delta)
5.12 Функция CurrentMP (i): для каждой координаты c от 0 до coords-1:
r1 = случайное число между 0 и 1
r2 = случайное число между 0 и 1
velocity = omega * (position [i].[c] - pBest [i].[c]) + lambda1 * r1 * (pBest [i].[c] - position [i].[c]) + lambda2 * r2 * (gBest [c] - position [i].[c])
newPosition [c] = position [i].[c] + velocity
return newPosition
5.13 Функция SocietyMP (i): j = случайный член популяции, не равный i, для каждой координаты c от 0 до coords - 1:
Если случайное число < 0.5:
newPosition [c] = position [i].[c]
Иначе: newPosition [c] = position [j].[c]
return newPosition
5.14 Функция PastMP (i): для каждой координаты c от 0 до coords - 1:
Если случайное число < 0.5:
newPosition [c] = position [i].[c]
Иначе: newPosition [c] = prevPosition [i].[c]
return newPosition
Теперь, когда у нас готов псевдокод, можем приступать к написанию по нему кода алгоритма. Опишем структуру "S_ASO_Member", которая используется для представления участника (агента) в алгоритме.
1. Поля структуры:
- pPrev [] — массив предыдущих позиций участников.
- pBest [] — массив наилучших известных позиций участников (личные лучшие).
- pBestFitness — переменная хранит значение фитнеса (качества) наилучшей известной позиции.
2. Метод "Init" инициализирует массивы "pPrev" и "pBest", устанавливая их размер в соответствии с количеством координат (или размерностью пространства поиска), переданным в качестве параметра "coords". "ArrayResize(pBest, coords)" и "ArrayResize(pPrev, coords)" — эти вызовы изменяют размер массивов до значения "coords". "pBestFitness = -DBL_MAX" — устанавливает начальное значение для фитнеса наилучшей позиции, чтобы гарантировать, что любое найденное значение будет лучше этого.
Структура "S_ASO_Member" предназначена для хранения информации о каждом участнике в алгоритме оптимизации. Она позволяет отслеживать как текущие, так и лучшие позиции участника, а также их приспособленность.
//—————————————————————————————————————————————————————————————————————————————— struct S_ASO_Member { double pPrev []; // Previous position double pBest []; // Personal best position double pBestFitness; // Personal best fitness void Init (int coords) { ArrayResize (pBest, coords); ArrayResize (pPrev, coords); pBestFitness = -DBL_MAX; } }; //——————————————————————————————————————————————————————————————————————————————
Определим класс "C_AO_ASO", который наследуется от базового класса "C_AO". Разберем его более подробно:
1. Параметры:
- popSize — размер популяции (количество членов общества).
- anarchyProb — вероятность анархического поведения, некоторые участники могут действовать независимо от других.
- omega, lambda1, lambda2 — параметры, связанные с инерцией и ускорением, используемые для управления поведением участников.
- alpha, theta, delta — параметры, используемые для вычисления показателей (FI, EI, II).
2. params — массив параметров, где каждый элемент содержит имя и значение.
3. SetParams () — метод обновляет значения параметров из массива "params", что позволяет изменять параметры алгоритма после его инициализации.
4. Init () — метод инициализирует алгоритм с заданными диапазонами и шагами. Он принимает массивы "rangeMinP", "rangeMaxP" и "rangeStepP", а также количество эпох "epochsP".
5. Moving() и Revision () — методы реализуют основную логику движения участников и их пересмотра (обновления) в процессе оптимизации.
6. Поля класса:
S_ASO_Member member [] — массив членов общества хранит информацию о каждом участнике алгоритма.
7. Приватные методы:
- CalculateFI — метод для вычисления значения FI (Fitness Indicator) для конкретного участника.
- CalculateEI — метод для вычисления значения EI (Exploration Indicator).
- CalculateII — метод для вычисления значения II (Inertia Indicator).
- CurrentMP, SocietyMP, PastMP — методы реализуют логику взаимодействия участников с их текущими, общественными и прошлыми позициями.
Класс "C_AO_ASO" представляет собой реализацию концепции "анархического общества", где участники могут действовать как совместно, так и независимо друг от друга, и включает в себя параметры, которые управляют поведением участников и методы для их инициализации и обновления.
//—————————————————————————————————————————————————————————————————————————————— class C_AO_ASO : public C_AO { public: //-------------------------------------------------------------------- ~C_AO_ASO () { } C_AO_ASO () { ao_name = "ASO"; ao_desc = "Anarchy Society Optimization"; ao_link = "https://www.mql5.com/ru/articles/15511"; popSize = 50; // Population size anarchyProb = 0.1; // Probability of anarchic behavior omega = 0.7; // Inertia weight lambda1 = 1.5; // Acceleration coefficient for P-best lambda2 = 1.5; // Acceleration coefficient for G-best alpha = 0.5; // Parameter for FI calculation theta = 1.0; // Parameter for EI calculation delta = 1.0; // Parameter for II calculation ArrayResize (params, 8); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "anarchyProb"; params [1].val = anarchyProb; params [2].name = "omega"; params [2].val = omega; params [3].name = "lambda1"; params [3].val = lambda1; params [4].name = "lambda2"; params [4].val = lambda2; params [5].name = "alpha"; params [5].val = alpha; params [6].name = "theta"; params [6].val = theta; params [7].name = "delta"; params [7].val = delta; } void SetParams () { popSize = (int)params [0].val; anarchyProb = params [1].val; omega = params [2].val; lambda1 = params [3].val; lambda2 = params [4].val; alpha = params [5].val; theta = params [6].val; delta = params [7].val; } bool Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0); void Moving (); void Revision (); //---------------------------------------------------------------------------- double anarchyProb; // Probability of anarchic behavior double omega; // Inertia weight double lambda1; // Acceleration coefficient for P-best double lambda2; // Acceleration coefficient for G-best double alpha; // Parameter for FI calculation double theta; // Parameter for EI calculation double delta; // Parameter for II calculation S_ASO_Member member []; // Vector of society members private: //------------------------------------------------------------------- double CalculateFI (int memberIndex); double CalculateEI (int memberIndex); double CalculateII (int memberIndex); void CurrentMP (S_AO_Agent &agent, S_ASO_Member &memb, int coordInd); void SocietyMP (S_AO_Agent &agent, int coordInd); void PastMP (S_AO_Agent &agent, S_ASO_Member &memb, int coordInd); }; //——————————————————————————————————————————————————————————————————————————————
Давайте разберем следующий метод "Init" класса "C_AO_ASO". Логика метода:
- StandardInit — метод вызывается для выполнения стандартной инициализации с использованием переданных диапазонов. Если этот метод возвращает "false" — значит, произошла ошибка.
- ArrayResize — метод изменяет размер массива "member" до значения "popSize", который определяет количество участников (членов общества) в алгоритме.
//—————————————————————————————————————————————————————————————————————————————— bool C_AO_ASO::Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0) { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //---------------------------------------------------------------------------- ArrayResize (member, popSize); for (int i = 0; i < popSize; i++) member [i].Init (coords); return true; } //——————————————————————————————————————————————————————————————————————————————
Разберем далее код метода "Moving" класса "C_AO_ASO". Структура и логика метода:
1. Проверка на первый вызов:
- Если "revision" равно "false", метод инициализирует массив "a" случайными значениями в пределах заданных диапазонов "rangeMin" и "rangeMax".
- Для каждой координаты "c" для каждого члена популяции "i" вызывается метод "u.RNDfromCI", который генерирует случайное значение, и затем это значение нормализуется с помощью "u.SeInDiSp".
- Значения сохраняются в "member [i].pPrev [c]" для дальнейшего использования.
- После этого "revision" устанавливается в "true", и метод завершает выполнение.
2. Основная логика перемещения:
- Для каждого члена популяции "i" вычисляются три индекса: "fi", "ei", и "ii", которые представляют собой метрики, характеризующие состояние члена популяции.
- Для каждой координаты "c" выполняется следующее:
- сохраняется текущее значение в "member [i].pPrev [c]".
- генерируется случайное число "rnd" с помощью "u.RNDprobab ()".
- если случайное число меньше "anarchyProb" (что означает исполнение вероятности проявления анархичности в поведении), то координата "c" для члена "i" будет инициализирована случайным образом из диапазона.
- в противном случае, в зависимости от значений "fi", "ei", и "ii", вызываются методы "CurrentMP", "SocietyMP", "PastMP".
- После всех изменений для каждой координаты "c" корректируется значение с помощью "u.SeInDiSp".
Метод "Moving" реализует логику перемещения членов популяции в пространстве решений, основываясь на их текущих состояниях и метриках.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_ASO::Moving () { //---------------------------------------------------------------------------- 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]); member [i].pPrev [c] = a [i].c [c]; } } revision = true; return; } //---------------------------------------------------------------------------- double fi = 0.0; //индекс недовольства double ei = 0.0; //индекс внешней нерегулярности double ii = 0.0; //индекс внутренней нерегулярности double rnd = 0.0; for (int i = 0; i < popSize; i++) { fi = CalculateFI (i); ei = CalculateEI (i); ii = CalculateII (i); for (int c = 0; c < coords; c++) { member [i].pPrev [c] = a [i].c [c]; rnd = u.RNDprobab (); if (u.RNDprobab () < anarchyProb) a [i].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]); else { if (rnd > fi) CurrentMP (a [i], member [i], c); else { if (rnd < ei) SocietyMP (a [i], c); else { if (rnd < ii) PastMP (a [i], member [i], c); } } } } for (int c = 0; c < coords; c++) { a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } } //——————————————————————————————————————————————————————————————————————————————
От метода "Moving" переходим к методу "Revision". Общая структура и логика:
1. Переменная "ind" инициализируется значением "-1". Она будет использоваться для хранения индекса члена популяции, который имеет наилучшее значение функции "f".
2. Метод проходит по всем членам популяции от "0" до "popSize - 1".
3. Поиск наилучшего значения функции: для каждого члена популяции "a [i]" проверяется, превышает ли его значение функции "f" текущее наилучшее значение "fB". Если это так, то "fB" обновляется на значение "a [i].f", а индекс "ind" устанавливается на "i".
4. Обновление личного наилучшего значения: метод также проверяет, превышает ли значение функции "a [i].f" текущее наилучшее значение для этого члена популяции "member [i].pBestFitness". Если да, то значение обновляется, и текущие координаты "a[i].c" копируются в "member[i].pBest" с помощью функции "ArrayCopy".
5. Копирование наилучшего решения: после завершения цикла, если был найден индекс "ind" (т.е. хотя бы один член популяции имел значение функции больше "fB"), то координаты этого члена популяции копируются в "cB" с помощью "ArrayCopy".
Метод "Revision" отвечает за обновление наилучшего найденного решения в популяции, а также за обновление личных наилучших значений для каждого члена популяции. Он использует простую логику сравнения значений функции, чтобы определить, какие решения являются наилучшими, и сохраняет их для дальнейшего использования.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_ASO::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 > member [i].pBestFitness) { member [i].pBestFitness = a [i].f; ArrayCopy (member [i].pBest, a [i].c, 0, 0, WHOLE_ARRAY); } } if (ind != -1) ArrayCopy (cB, a [ind].c, 0, 0, WHOLE_ARRAY); } //——————————————————————————————————————————————————————————————————————————————
Далее метод "CalculateFI" класса "C_AO_ASO". Описание метода:
1. Метод принимает индекс члена популяции "memberIndex", для которого будет вычисляться фитнес.
2. Получение значений фитнеса:
- currentFitness — получает текущее значение фитнеса члена популяции из массива "a" по индексу "memberIndex".
- personalBestFitness — получает личное наилучшее значение фитнеса этого члена из массива "member".
- globalBestFitness — получает глобальное наилучшее значение фитнеса, хранящееся в переменной "fB".
3. Вычисление фитнес-индекса (FI) — метод возвращает значение, вычисленное по формуле.
Формула нормализует разницу между личным и текущим фитнесом, деля её на разницу между глобальным и текущим фитнесом. Метод "CalculateFI" вычисляет фитнес-индекс для члена популяции, который используется для оценки его качества по сравнению с личным и глобальным наилучшими значениями фитнеса.
//—————————————————————————————————————————————————————————————————————————————— double C_AO_ASO::CalculateFI (int memberIndex) { double currentFitness = a [memberIndex].f; double personalBestFitness = member [memberIndex].pBestFitness; double globalBestFitness = fB; //1 - 0.9 * (800-x)/(1000-x) return 1 - alpha * (personalBestFitness - currentFitness) / (globalBestFitness - currentFitness); } //——————————————————————————————————————————————————————————————————————————————
Далее следует метод "CalculateEI" класса "C_AO_ASO". Метод выполняет почти те же действия, что и предыдущий метод, но использует для вычисления лучший глобальный и собственный текущий фитнес.
//—————————————————————————————————————————————————————————————————————————————— double C_AO_ASO::CalculateEI (int memberIndex) { double currentFitness = a [memberIndex].f; double globalBestFitness = fB; //1-exp(-(10000-x)/(10000*0.9)) return 1 - MathExp (-(globalBestFitness - currentFitness) / (globalBestFitness * theta)); } //——————————————————————————————————————————————————————————————————————————————
Метода "CalculateII" класса "C_AO_ASO" полностью аналогичен предыдущему, но в нём используются лучший и текущий собственный фитнес.
Экспоненциальная функция помогает сгладить изменения и обеспечивает плавный переход между значениями. Метод "CalculateII" вычисляет индекс улучшения для члена популяции, который учитывает насколько текущее состояние фитнеса соотносится к личным достижениям.
//—————————————————————————————————————————————————————————————————————————————— double C_AO_ASO::CalculateII (int memberIndex) { double currentFitness = a [memberIndex].f; double personalBestFitness = member [memberIndex].pBestFitness; //1-exp(-(10000-x)/(10000*0.9)) return 1 - MathExp (-(personalBestFitness - currentFitness) / (personalBestFitness * delta)); } //——————————————————————————————————————————————————————————————————————————————
Переходим к методу "CurrentMP" класса "C_AO_ASO". Описание:
1. Генерация случайных чисел:
- r1 = u.RNDprobab () — генерирует случайное число "r1" в диапазоне [0, 1].
- r2 = u.RNDprobab () — генерирует случайное число "r2" в диапазоне [0, 1].
2. Вычисление скорости "velocity" — формула включает три компонента:
- omega * (agent.c [coordInd] - memb.pBest [coordInd]) — инерционная составляющая, движение агента с учетом его предыдущего положения.
- lambda1 * r1 * (memb.pBest[coordInd] - agent.c[coordInd]) — направляет агента с учетом его личного наилучшего положения
- lambda2 * r2 * (cB[coordInd] - agent.c[coordInd]) — направляет агента с учетом наилучшего положения популяции.
3. Обновление положения агента путем добавления скорости к текущему значению координаты.
Метод "CurrentMP" реализует обновление положения агента в пространстве на основе его текущего положения, личного наилучшего положения и наилучшего положения популяции.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_ASO::CurrentMP (S_AO_Agent &agent, S_ASO_Member &memb, int coordInd) { double r1 = u.RNDprobab (); double r2 = u.RNDprobab (); double velocity = omega * (agent.c [coordInd] - memb.pBest [coordInd]) + lambda1 * r1 * (memb.pBest [coordInd] - agent.c [coordInd]) + lambda2 * r2 * (cB [coordInd] - agent.c [coordInd]); agent.c [coordInd] += velocity; } //——————————————————————————————————————————————————————————————————————————————
Метод "SocietyMP" класса "C_AO_ASO" обновляет координату агента, основываясь на случайном выборе между групповой и личной информацией. Это позволяет агенту адаптироваться к состоянию как всей популяции, так и отдельного агента.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_ASO::SocietyMP (S_AO_Agent &agent, int coordInd) { int otherMember = u.RNDminusOne (popSize); agent.c [coordInd] = u.RNDprobab () < 0.5 ? cB [coordInd] : member [otherMember].pBest [coordInd]; } //——————————————————————————————————————————————————————————————————————————————
Метод "PastMP" класса "C_AO_ASO" обновляет координату агента, основываясь на случайном выборе между текущим наилучшим состоянием члена популяции и его предыдущим состоянием. Это позволяет агенту учитывать как текущие достижения члена популяции, так и его прошлые результаты. Такой подход повышает комбинаторные свойства алгоритма.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_ASO::PastMP (S_AO_Agent &agent, S_ASO_Member &memb, int coordInd) { agent.c [coordInd] = u.RNDprobab () < 0.5 ? memb.pBest [coordInd] : memb.pPrev [coordInd]; } //——————————————————————————————————————————————————————————————————————————————
3. Результаты тестов
Распечатка работы алгоритма ASO на стенде с тестовыми функциями:
ASO|Anarchy Society Optimization|50.0|0.01|0.7|1.5|1.5|0.5|0.1|0.1|
=============================
5 Hilly's; Func runs: 10000; result: 0.8487202680440514
25 Hilly's; Func runs: 10000; result: 0.746458607174428
500 Hilly's; Func runs: 10000; result: 0.31465494017509904
=============================
5 Forest's; Func runs: 10000; result: 0.9614752193694915
25 Forest's; Func runs: 10000; result: 0.7915027321897546
500 Forest's; Func runs: 10000; result: 0.23802894131144553
=============================
5 Megacity's; Func runs: 10000; result: 0.5707692307692309
25 Megacity's; Func runs: 10000; result: 0.5406153846153848
500 Megacity's; Func runs: 10000; result: 0.16613846153846298
=============================
All score: 5.17836 (57.54%)
Рассматривая визуализацию работы алгоритма, можно сделать некоторые выводы: наблюдается разброс результатов. Однако алгоритм демонстрирует хорошие поисковые способности при работе с функциями большой размерности, что подтверждается также в распечатке результатов его работы.
ASO на тестовой функции Hilly
ASO на тестовой функции Forest
ASO на тестовой функции Megacity
Рейтинговая таблица популяционных алгоритмов оптимизации: алгоритм ASO после тестирования попал в десятку лучших и занял 9 место в рейтинговой таблице.
| № | 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 | (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 |
| 4 | 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 |
| 5 | 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 |
| 6 | 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 |
| 7 | 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 |
| 8 | 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 |
| 9 | 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 |
| 10 | 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 |
| 11 | 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 |
| 12 | 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 |
| 13 | 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 |
| 14 | 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 |
| 15 | 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 |
| 16 | (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 |
| 17 | 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 |
| 18 | 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 |
| 19 | 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 |
| 20 | 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 |
| 21 | 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 |
| 22 | 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 |
| 23 | 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 |
| 24 | 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 |
| 25 | 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 |
| 26 | 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 |
| 27 | 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 |
| 28 | 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 |
| 29 | 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 |
| 30 | 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 |
| 31 | 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 |
| 32 | 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 |
| 33 | 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 |
| 34 | 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 |
| 35 | 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 |
| 36 | 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 |
| 37 | 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 |
| 38 | 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 |
| 39 | MA | monkey algorithm | 0,59107 | 0,42681 | 0,31816 | 1,33604 | 0,31138 | 0,14069 | 0,06612 | 0,51819 | 0,22833 | 0,08567 | 0,02790 | 0,34190 | 2,196 | 24,40 |
| 40 | SFL | shuffled frog-leaping | 0,53925 | 0,35816 | 0,29809 | 1,19551 | 0,37141 | 0,11427 | 0,04051 | 0,52618 | 0,27167 | 0,08667 | 0,02402 | 0,38235 | 2,104 | 23,38 |
| 41 | FSS | fish school search | 0,55669 | 0,39992 | 0,31172 | 1,26833 | 0,31009 | 0,11889 | 0,04569 | 0,47467 | 0,21167 | 0,07633 | 0,02488 | 0,31288 | 2,056 | 22,84 |
| 42 | RND | random | 0,52033 | 0,36068 | 0,30133 | 1,18234 | 0,31335 | 0,11787 | 0,04354 | 0,47476 | 0,25333 | 0,07933 | 0,02382 | 0,35648 | 2,014 | 22,37 |
| 43 | GWO | grey wolf optimizer | 0,59169 | 0,36561 | 0,29595 | 1,25326 | 0,24499 | 0,09047 | 0,03612 | 0,37158 | 0,27667 | 0,08567 | 0,02170 | 0,38403 | 2,009 | 22,32 |
| 44 | CSS | charged system search | 0,44252 | 0,35454 | 0,35201 | 1,14907 | 0,24140 | 0,11345 | 0,06814 | 0,42299 | 0,18333 | 0,06300 | 0,02322 | 0,26955 | 1,842 | 20,46 |
| 45 | EM | electroMagnetism-like algorithm | 0,46250 | 0,34594 | 0,32285 | 1,13129 | 0,21245 | 0,09783 | 0,10057 | 0,41085 | 0,15667 | 0,06033 | 0,02712 | 0,24412 | 1,786 | 19,85 |
Выводы
Исходя из результатов работы алгоритма на тестовых функциях разной размерности, можно сделать следующие выводы: ASO показывает средние результаты на гладкой функции Hilly по сравнению с ближайшими соседями в таблице, но очень достойные результаты на "острой" Forest и в особенности на дискретной Megacity. Общий итоговый балл составил 5.17836 (57.54%). Алгоритм демонстрирует хорошие поисковые способности, особенно при работе с функциями большой размерности, то есть хорошо масштабируется. Алгоритм может быть рекомендован для решения дискретных задач оптимизации, что для трейдеров является приоритетным направлением.
Рисунок 4. Цветовая градация алгоритмов по соответствующим тестам. Белым цветом подсвечены результаты больше или равные 0.99
Рисунок 5. Гистограмма результатов тестирования алгоритмов (по шкале от 0 до 100, чем больше, тем лучше,
где 100 - максимально возможный теоретический результат, в архиве скрипт для расчета рейтинговой таблицы)
Плюсы и минусы алгоритма ASO:
Плюсы:
- Хорошая сходимость на различных функциях.
- Отличные результаты на дискретных функциях.
Минусы:
- Большое количество параметров (очень сложно настроить алгоритм).
- Разброс результатов на функциях малой размерности.
- Сложная реализация.
К статье прикреплён архив с актуальными версиями кодов алгоритмов. Автор статьи не несёт ответственности за абсолютную точность в описании канонических алгоритмов, во многие из них были внесены изменения для улучшения поисковых возможностей. Выводы и суждения, представленные в статьях, основываются на результатах проведённых экспериментов.
Метод группового учета аргументов: реализация многослойного итерационного алгоритма на MQL5
Нейросети в трейдинге: Комплексный метод прогнозирования траекторий (Traj-LLM)
Алгоритм искусственных водорослей — Artificial Algae Algorithm (AAA)
Создание самооптимизирующихся советников на MQL5
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Вы принимаете политику сайта и условия использования