Алгоритм Искусственного Племени (Artificial Tribe Algorithm, ATA)
562
0
Содержание
Введение
В последнее время стремительно развиваются технологии, а задачи оптимизации становятся еще более сложными, ученые и исследователи продолжают искать вдохновение в природе. Одним из ярких примеров такого подхода является Алгоритм Искусственного Племени (Artificial Tribe Algorithm, ATA), созданный учеными Т. Ченом, Ю. Ваном и Ц. Ли и опубликованный в 2012 году. Вдохновленный поведением племен, ATA использует два основных механизма — распространение и миграцию, позволяя адаптироваться к меняющимся условиям и находить оптимальные решения в самых разнообразных задачах. Представьте себе бескрайние просторы, где группы людей, как и их далекие предки, объединяются в поисках лучших ресурсов. Они мигрируют, обмениваются знаниями и опытом, создавая уникальные стратегии для решения сложных задач. Именно это поведение стало основой для создания ATA — алгоритма, который гармонично сочетает два ключевых механизма: распространение и миграцию.
Алгоритм Искусственного Племени представляет собой совершенно новый метод оптимизации, основанный на принципах бионических интеллектуальных алгоритмов. Он моделирует поведение природных племен, используя их способности к размножению и миграции для достижения оптимальных решений. В этом алгоритме племя состоит из индивидов, которые взаимодействуют друг с другом, чтобы найти глобальный оптимум.
Реализация алгоритма
Процесс работы алгоритма ATA начинается с установки параметров и случайной инициализации племени, после чего рассчитывается значение приспособленности. Далее увеличивается счетчик итераций, и оценивается текущая ситуация племени. Если ситуация благоприятна (разница в оптимальном значении приспособленности между поколениями больше заданного критерия), выполняется поведение размножения, где особи обмениваются информацией. В противном случае, используется поведение миграции, при котором индивиды перемещаются с учетом опыта как отдельной особи, так и всего племени. Миграция не может выполняться постоянно, чтобы избежать чрезмерной дисперсии. Затем вновь рассчитывается значение приспособленности и сравнивается с лучшими значениями, зарегистрированными для племени и каждого индивида. Если найдено лучшее решение, оно заносится в память. Проверяется, удовлетворяют ли условия завершения, и если они выполнены, итерация завершается. В противном случае, процесс возвращается к шагу оценки ситуации.
Включение глобальной информации в ATA придает вес историческому опыту племени, что помогает находить лучшие решения и улучшать способность поиска. Увеличение веса опыта племени способствует повышению эффективности алгоритма, ускоряя сходимость. Для этого ATA вводит глобальный инерционный вес, который усиливает поисковые способности и ускоряет процесс.
Основной инновацией ATA является наличие двойной системы поведения, которая адаптируется в зависимости от ситуации: размножение используется для углубленного исследования, когда прогресс хороший, а миграция активируется при застревании в локальных оптимумах, что способствует более глубокой исследовательской деятельности. Также важно сочетание индивидуального и социального обучения. Индивидуальная память (Xs) используется при миграции, а глобальная память (Xg) взвешивается по инерционному коэффициенту AT_w. При размножении партнеры выбираются случайным образом, что помогает улучшить разнообразие и ускорить поиск.
Система параметров в ATA проста, но эффективна. Она контролирует численность популяции (tribe_size), критерий переключения поведения (AT_criterion) и глобальное влияние на поиск (AT_w), что делает алгоритм гибким и мощным инструментом, который легко, как утверждают авторы, конкурирует с более сложными алгоритмами, особенно при работе с малыми размерами популяции.
Основные компоненты алгоритма включают поведение размножения, которое применяется при хорошем прогрессе, когда разница в приспособленности больше установленного критерия. В этом случае особи обмениваются частичной информацией. Поведение миграции используется при плохой ситуации, когда разница в приспособленности мала, и включает движение на основе индивидуального и глобального опыта, с учетом веса инерции для усиления глобального поиска. Критерий существования оценивает изменения лучшей приспособленности между итерациями: если изменения значительны, то используется размножение, если изменения незначительны, происходит миграция.
Алгоритм также включает систему обновления памяти, которая отслеживает лучшие позиции как для отдельных особей, так и для всего племени. Эти позиции обновляются, когда находятся новые лучшие решения.
Особенности проектирования ATA заключаются в простоте параметров, интеграции индивидуального и социального обучения, а также в самоадаптивном переключении между размножением и миграцией. Глобальный вес инерции улучшает способность поиска, ускоряя нахождение оптимальных решений.
Итак, правила индивидуального поведения можно описать следующим образом:
1. Распространение. Индивид использует информацию в популяции для формирования генетического материала будущих поколений. Если существующая ситуация в окружающей среде благоприятна, индивид случайным образом выбирает другого индивида из племени и скрещивается, чтобы возродить следующее поколение через обмен генетической информацией.
2. Миграция. Если существующая ситуация плохая (что указывает на то, что межпоколенческая разница в оптимальном значении приспособленности меньше существующего критерия), индивид перемещается, в соответствии со своим и племенным историческим опытом, для реализации миграции племени.
Визуально схематично ключевые фазы, происходящие в популяции алгоритма, можно представить как на рисунке 1.
Рисунок 1. Фазы перемещения индивидов в популяции алгоритма ATA
Напишем псевдокод алгоритма ATA:
// Основные параметры:
// размер_племени - размер популяции племени
// ATA_criterion - пороговое значение критерия существования
// ATA_w - глобальный вес инерции
// X - вектор позиции особи
// Xs - лучшая историческая позиция особи
// Xg - глобальная лучшая историческая позиция племени
Алгоритм ATA:
Инициализация:
Создать племя из tribe_size особей со случайными позициями X
Вычислить начальные значения пригодности для всех особей
Инициализировать Xs и Xg найденными лучшими позициями
итерация = 0
Пока (итерация < макс_итераций):
итерация = итерация + 1
// Проверить благоприятность ситуации для существования
разница = |текущая_лучшая_пригодность - предыдущая_лучшая_пригодность|
Если (разница > ATA_criterion):
// Хорошая ситуация - выполнить поведение размножения
Для каждой особи i:
// Выбрать случайного партнера j из племени
j = случайное (1, размер_племени) где j ≠ i
// Формулы размножения:
r1 = случайное (0,1)
Yi+1 = r1 * Yj + (1 - r1) * Xi // Новая позиция партнера
Xi+1 = r1 * Xi + (1- r1) * Yi // Новая позиция особи
Иначе:
// Плохая ситуация - выполнить поведение миграции
Для каждой особи i:
// Формула миграции:
r1 = случайное (0,1)
r2 = случайное (0,1)
Xi+1 = Xi + r1 * (Xs - Xi) + ATA_w * r2 * (Xg - Xi)
// Обновить значения пригодности и лучшие позиции
Для каждой особи i:
Вычислить новая_пригодность для Xi
Если новая_пригодность лучше, чем лучшая_пригодность_особи:
Обновить Xs для особи i
Если новая_пригодность лучше, чем глобальная_лучшая_пригодность:
Обновить Xg
Сохранить текущую_лучшую_пригодность для следующей итерации
Вернуть Xg как найденное лучшее решение
Рисунок 2. Логическая схема работы алгоритма ATA
Определим класс C_AO_ATA, который реализует алгоритм ATA. Кратко опишем его содержание:
Наследование и основные члены:- Класс наследуется от базового класса C_AO
- Содержит деструктор и конструктор
- popSize = 50 (размер племени)
- AT_criterion = 0.3 (критерий благоприятности обстановки)
- AT_w = 1.46 (инерционный вес)
- SetParams () - установка параметров из массива "params"
- Init () - инициализация с диапазонами поиска
- Moving () - реализация движения особей
- Revision () - оценка и обновление решений
- prevBestFitness - хранит предыдущее лучшее значение для сравнения
Это базовый каркас алгоритма, где определены все необходимые параметры и методы для его работы.
//—————————————————————————————————————————————————————————————————————————————— class C_AO_ATA : public C_AO { public: //-------------------------------------------------------------------- ~C_AO_ATA () { } C_AO_ATA () { ao_name = "ATA"; ao_desc = "Artificial Tribe Algorithm"; ao_link = "https://www.mql5.com/ru/articles/16588"; popSize = 50; // Размер популяции AT_criterion = 0.3; // Критерий оценки текущей ситуации AT_w = 1.46; // Глобальный инерционный вес ArrayResize (params, 3); // Инициализация параметров params [0].name = "popSize"; params [0].val = popSize; params [1].name = "AT_criterion"; params [1].val = AT_criterion; params [2].name = "AT_w"; params [2].val = AT_w; } void SetParams () // Метод для установки параметров { popSize = (int)params [0].val; AT_criterion = params [1].val; AT_w = params [2].val; } bool Init (const double &rangeMinP [], // Минимальный диапазон поиска const double &rangeMaxP [], // Максимальный диапазон поиска const double &rangeStepP [], // Шаг поиска const int epochsP = 0); // Количество эпох void Moving (); // Метод перемещения void Revision (); // Метод ревизии //---------------------------------------------------------------------------- double AT_criterion; // Критерий оценки текущей ситуации double AT_w; // Глобальный инерционный вес private: //------------------------------------------------------------------- double prevBestFitness; //Предыдущее лучшее решение }; //——————————————————————————————————————————————————————————————————————————————
Метод "Init" класса C_AO_ATA отвечает за инициализацию алгоритма. Разберем его по частям:
Параметры метода:- rangeMinP [] - массив минимальных значений для каждой размерности поиска
- rangeMaxP [] - массив максимальных значений
- rangeStepP [] - массив шагов дискретизации
- epochsP - количество эпох (по умолчанию 0)
- Вызывает "StandardInit" из базового класса для инициализации стандартных параметров
- Если "StandardInit" вернул "false", метод прерывается
- Устанавливает "prevBestFitness" в "-DBL_MAX" (для задачи максимизации)
- true в случае успешной инициализации
- false если стандартная инициализация не удалась
Это минимальная реализация инициализации, которая подготавливает алгоритм к работе.
//—————————————————————————————————————————————————————————————————————————————— bool C_AO_ATA::Init (const double &rangeMinP [], // Минимальный диапазон поиска const double &rangeMaxP [], // Максимальный диапазон поиска const double &rangeStepP [], // Шаг поиска const int epochsP = 0) // Количество эпох { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; // Инициализация стандартных параметров //---------------------------------------------------------------------------- prevBestFitness = -DBL_MAX; return true; } //——————————————————————————————————————————————————————————————————————————————
Метод "Moving ()" отвечает за перемещение особей племени и состоит из двух основных частей:
Если это первый запуск (revision = false):- Случайно размещает все особи в пространстве поиска
- приводит их позиции к допустимым дискретным значениям
- помечает, что начальное размещение выполнено (revision = true)
- каждая особь выбирает случайного партнера
- они обмениваются информацией о своих позициях
- формируют новые позиции на основе этого обмена
- своей лучшей позиции
- глобальной лучшей позиции
- инерционного веса "AT_w"
При любых перемещениях все новые позиции проверяются и приводятся к допустимым значениям в заданных диапазонах. Дополнительно можно отметить следующий нюанс, так как критерий оценки ситуации является внешним параметром и имеет безразмерную величину, то необходимо нормировать разницу текущей лучшей приспособленности и предыдущей на разницу между самой лучшей исторической приспособленностью и самой худшей: diff = (fB - prevBestFitness) / (fB - fW). Именно для этих целей в данном алгоритме отслеживается не только глобально лучшее решение, но и глобально худшее.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_ATA::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]); // Приведение к дискретным значениям } } revision = true; // Установка флага ревизии return; // Выход из метода } //---------------------------------------------------------------------------- // Проверка критерия существования double diff = (fB - prevBestFitness) / (fB - fW); double Xi = 0.0; double Xi_1 = 0.0; double Yi = 0.0; double Yi_1 = 0.0; double Xs = 0.0; double Xg = 0.0; int p = 0; double r1 = 0.0; double r2 = 0.0; if (diff > AT_criterion) { // Поведение распространения (хорошая ситуация) for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { p = u.RNDminusOne (popSize); r1 = u.RNDprobab (); Xi = a [i].cP [c]; Yi = a [p].cP [c]; Xi_1 = r1 * Xi + (1.0 - r1) * Yi; Yi_1 = r1 * Yi + (1.0 - r1) * Xi; a [i].c [c] = u.SeInDiSp (Xi_1, rangeMin [c], rangeMax [c], rangeStep [c]); a [p].c [c] = u.SeInDiSp (Yi_1, rangeMin [c], rangeMax [c], rangeStep [c]); } } } else { // Поведение миграции (плохая ситуация) for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { r1 = u.RNDprobab (); r2 = u.RNDprobab (); Xi = a [i].cP [c]; Xs = a [i].cB [c]; Xg = cB [c]; Xi_1 = Xi + r1 * (Xs - Xi) + AT_w * r2 * (Xg - Xi); a [i].c [c] = u.SeInDiSp (Xi_1, rangeMin [c], rangeMax [c], rangeStep [c]); } } } } //——————————————————————————————————————————————————————————————————————————————
Метод "Revision ()" отвечает за оценку и обновление лучших решений после перемещения особей. Вот что он делает:
Для всех особей в племени:- проверяет, улучшено ли глобальное лучшее решение (fB)
- обновляет худшее найденное решение (fW)
- проверяет и обновляет личное лучшее решение каждой особи (a [i].fB)
- сохраняет текущие позиции как предыдущие (в cP)
- сохраняет предыдущее лучшее значение (prevBestFitness = tempB)
- копирует координаты лучшей особи в глобальное лучшее решение (cB)
По сути, это метод "ревизии" текущего состояния племени, где обновляются все важные показатели: глобальные лучшие/худшие значения, личные лучшие значения каждой особи и сохраняется история позиций.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_ATA::Revision () { //---------------------------------------------------------------------------- int indB = -1; // Индекс лучшей частицы double tempB = fB; for (int i = 0; i < popSize; i++) // Для каждой частицы { if (a [i].f > fB) // Если значение функции лучше, чем текущее лучшее { fB = a [i].f; // Обновление лучшего значения функции indB = i; // Сохранение индекса лучшей частицы } if (a [i].f < fW) // Если значение функции хуже, чем текущее худшее { fW = a [i].f; // Обновление худшего значения функции } if (a [i].f > a [i].fB) { a [i].fB = a [i].f; ArrayCopy (a [i].cB, a [i].c, 0, 0, WHOLE_ARRAY); } ArrayCopy (a [i].cP, a [i].c, 0, 0, WHOLE_ARRAY); } if (indB != -1) { prevBestFitness = tempB; ArrayCopy (cB, a [indB].c, 0, 0, WHOLE_ARRAY); // Копирование координат лучшей частицы } } //——————————————————————————————————————————————————————————————————————————————
Переходим к результатам тестирования алгоритма ATA на испытательном стенде.
ATA|Artificial Tribe Algorithm|50.0|0.3|0.5|
=============================
5 Hilly's; Func runs: 10000; result: 0.540711768815426
25 Hilly's; Func runs: 10000; result: 0.31409437631469717
500 Hilly's; Func runs: 10000; result: 0.2512638813618161
=============================
5 Forest's; Func runs: 10000; result: 0.40309649266442193
25 Forest's; Func runs: 10000; result: 0.2572536671383149
500 Forest's; Func runs: 10000; result: 0.18349902023635473
=============================
5 Megacity's; Func runs: 10000; result: 0.24
25 Megacity's; Func runs: 10000; result: 0.13600000000000004
500 Megacity's; Func runs: 10000; result: 0.09518461538461616
=============================
All score: 2.42110 (26.90%)
Как видно из распечатки результатов работы алгоритма и на визуализации, при таких показателях алгоритм, к сожалению, не способен попасть в нашу рейтинговую таблицу. На визуализации ниже заметны слабые возможности алгоритма выбираться из локальных ловушек, в которых ATA застревает. Алгоритму явно не хватает разнообразия в популяции решений, что ведет к ее вырождению.
ATAm на тестовой функции Hilly
Попробуем улучшить алгоритм ATA, сосредоточив внимание на недостатке разнообразия решений в популяции. Это важный аспект, поскольку разнообразие является ключевым для эффективного поиска в пространстве решений. В нашей модификации мы введем динамическую вероятность, которая будет зависеть от состояния приспособленности популяции.
Когда популяция сжимается в узком диапазоне пространства решений, это может привести к тому, что алгоритм застрянет в локальном оптимуме. Мы будем, как и в оригинальной версии алгоритма отслеживать разницу между текущим и предыдущим лучшими глобальными решениями, но при этом, если эта разница оказывается слишком малой, это будет сигналом о том, что популяция недостаточно разнообразна и, возможно, приближается к коллапсу решений.
Для предотвращения такой ситуации, мы будем с определенной вероятностью выбрасывать особей, которые находятся далеко от текущего глобального решения. Это будет происходить в пределах допустимых границ задачи, что обеспечит соблюдение условий задачи и предотвратит выход за ее рамки. Мы будем использовать нормальное распределение для определения того, насколько далеко от текущего глобального решения будут находиться выбрасываемые особи.
Интересно, что чем больше разница между текущим и предыдущим лучшими решениями (обозначена как "diff"), тем выше вероятность таких выбросов. Это позволит нам адаптивно реагировать на состояние популяции: когда она начинает застревать, мы будем более активно более активно использовать фазу миграции, что в свою очередь повысит шансы покинуть локальный оптимум и найти более оптимальные решения.
Таким образом, наша модификация алгоритма ATA будет способствовать не только поддержанию разнообразия решений, но и улучшению общей эффективности поиска в пространстве решений. Это может привести к более устойчивым результатам и более высокому качеству найденных решений.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_ATAm::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]); // Приведение к дискретным значениям } } revision = true; // Установка флага ревизии return; // Выход из метода } //---------------------------------------------------------------------------- // Проверка критерия существования double diff = (fB - prevBestFitness) / (fB - fW); double Xi = 0.0; double Xi_1 = 0.0; double Yi = 0.0; double Yi_1 = 0.0; double Xs = 0.0; double Xg = 0.0; int p = 0; double r1 = 0.0; double r2 = 0.0; if (diff > AT_criterion) { // Поведение распространения (хорошая ситуация) for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { p = u.RNDminusOne (popSize); r1 = u.RNDprobab (); Xi = a [i].cP [c]; Yi = a [p].cP [c]; Xi_1 = r1 * Xi + (1.0 - r1) * Yi; Yi_1 = r1 * Yi + (1.0 - r1) * Xi; a [i].c [c] = u.SeInDiSp (Xi_1, rangeMin [c], rangeMax [c], rangeStep [c]); a [p].c [c] = u.SeInDiSp (Yi_1, rangeMin [c], rangeMax [c], rangeStep [c]); } } } else { // Поведение миграции (плохая ситуация) for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { if (u.RNDprobab () < diff) { Xi_1 = u.GaussDistribution (cB [c], rangeMin [c], rangeMax [c], 1); a [i].c [c] = u.SeInDiSp (Xi_1, rangeMin [c], rangeMax [c], rangeStep [c]); } else { r1 = u.RNDprobab (); r2 = u.RNDprobab (); Xi = a [i].cP [c]; Xs = a [i].cB [c]; Xg = cB [c]; Xi_1 = Xi + r1 * (Xs - Xi) + AT_w * r2 * (Xg - Xi); a [i].c [c] = u.SeInDiSp (Xi_1, rangeMin [c], rangeMax [c], rangeStep [c]); } } } } } //——————————————————————————————————————————————————————————————————————————————
Результаты тестов
Результаты работы модифицированной версии алгоритма ATAm:
ATAm|Artificial Tribe Algorithm M|50.0|0.9|0.8|
=============================
5 Hilly's; Func runs: 10000; result: 0.7177133636761123
25 Hilly's; Func runs: 10000; result: 0.553035897955171
500 Hilly's; Func runs: 10000; result: 0.25234636879284034
=============================
5 Forest's; Func runs: 10000; result: 0.8249072382287125
25 Forest's; Func runs: 10000; result: 0.5590392181296365
500 Forest's; Func runs: 10000; result: 0.2047284499286112
=============================
5 Megacity's; Func runs: 10000; result: 0.43999999999999995
25 Megacity's; Func runs: 10000; result: 0.18615384615384617
500 Megacity's; Func runs: 10000; result: 0.09410769230769304
=============================
All score: 3.83203 (42.58%)
На этот раз результаты оказались значительно более перспективными и уже достойны внесения в рейтинговую таблицу, что позволит вытеснить очередного аутсайдера. Визуализация показывает гораздо более активное перемещение особей в популяции по пространству решений. Однако, возникла новая проблема: наблюдается значительный разброс результатов, и полностью избавиться от застревания в локальных оптимумах не удалось.
ATAm на тестовой функции Hilly
ATAm на тестовой функции Forest
ATAm на тестовой функции Megacity
Алгоритм искусственного племени разместился на 33-м месте в рейтинговой таблице.
| № | 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 | 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 (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 |
| 9 | 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 |
| 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 | 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 |
| 13 | 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 |
| 14 | 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 |
| 15 | 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 |
| 16 | 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 |
| 17 | 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 |
| 18 | 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 |
| 19 | 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 |
| 20 | 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 |
| 21 | (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 |
| 22 | 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 |
| 23 | 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 |
| 24 | 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 |
| 25 | 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 |
| 26 | 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 |
| 27 | 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 |
| 28 | 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 |
| 29 | 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 |
| 30 | 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 |
| 31 | 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 |
| 32 | 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 |
| 33 | 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 |
| 34 | 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 |
| 35 | 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 |
| 36 | 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 |
| 37 | 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 |
| 38 | 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 |
| 39 | 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 |
| 40 | 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 |
| 41 | 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 |
| 42 | 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 |
| 43 | 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 |
| 44 | 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 |
| 45 | 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 |
Выводы
В данной статье мы подробно рассмотрели один из самых современных алгоритмов оптимизации — алгоритм ATA. Несмотря на то, что этот алгоритм не может похвастаться выдающимися результатами в сравнении с другими методами, его значимость заключается в том, что он вносит ценный вклад в наше понимание динамического управления состоянием популяции и методов анализа проблем, связанных с застреванием в локальных оптимумах.
Интерес к алгоритму ATA не ограничивается лишь его двумя основными фазами, которые сами по себе представляют небольшую ценность в качестве методов поиска решений. Куда более важным является подход, использующий динамический выбор фаз передвижения особей и контроль за состоянием популяции. Именно этот аспект позволяет более эффективно адаптировать алгоритм к изменяющимся условиям задачи и улучшать качество получаемых решений. Таким образом, изучение ATA открывает новые горизонты для дальнейших исследований в области алгоритмической оптимизации и может служить основой для разработки более совершенных методов.
Я также уверен, что к обсуждаемому алгоритму можно применить различные операторы, которые значительно повысят его эффективность. Например, использование операторов селекции, основанных на сортировке или кроссовере, может значительно улучшить результаты.
Однако стоит отметить, что в текущей версии алгоритма отсутствуют зависимости от качества решения, а также не хватает комбинаторных свойств, что ограничивает его возможности. Все эти аспекты представляют собой интересные направления для дальнейших исследований и улучшений, хотя и выходят за рамки данной статьи. Я был бы очень рад, если кто-то из читателей решит поэкспериментировать с предложенными изменениями и поделится своими версиями алгоритма в комментариях.
Рисунок 3. Цветовая градация алгоритмов по соответствующим тестам. Белым цветом подсвечены результаты больше или равные 0.99
Рисунок 4. Гистограмма результатов тестирования алгоритмов (по шкале от 0 до 100, чем больше, тем лучше, где 100 - максимально возможный теоретический результат, в архиве скрипт для расчета рейтинговой таблицы)
Плюсы и минусы алгоритма ATAm:
Плюсы:
- Мало внешних параметров.
- Простая реализация.
- Интересная идея динамического переключения стратегий поиска.
Минусы:
- Большой разброс результатов.
- Низкая точность сходимости.
- Склонность к застреванию.
К статье прикреплён архив с актуальными версиями кодов алгоритмов. Автор статьи не несёт ответственности за абсолютную точность в описании канонических алгоритмов, во многие из них были внесены изменения для улучшения поисковых возможностей. Выводы и суждения, представленные в статьях, основываются на результатах проведённых экспериментов.
Программы, используемые в статье
| # | Имя | Тип | Описание |
|---|---|---|---|
| 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_ATAm.mq5 | Скрипт | Испытательный стенд для ATAm |
Предупреждение: все права на данные материалы принадлежат MetaQuotes Ltd. Полная или частичная перепечатка запрещена.
Данная статья написана пользователем сайта и отражает его личную точку зрения. Компания MetaQuotes Ltd не несет ответственности за достоверность представленной информации, а также за возможные последствия использования описанных решений, стратегий или рекомендаций.
Критерии тренда в трейдинге
Индикатор рыночного профиля — Market Profile (Часть 2): Оптимизация и отрисовка на канвасе
Построение модели для ограничения диапазона сигналов по тренду (Часть 5): Система уведомлений (Часть III)
Оптимизация портфеля на форексе: Синтез VaR и теории Марковица
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Вы принимаете политику сайта и условия использования