Алгоритм эволюции панциря черепахи (Turtle Shell Evolution Algorithm, TSEA)
480
0
Содержание:
1.Введение
2.Реализация алгоритма
3.Результаты тестов
1. Введение
Черепаха — древнейшее и удивительное творение природы. Она несет на себе панцирь — символ стойкости, защиты и выживания. Этот величественный щит, формируемый в процессе жизненного пути черепахи, воплощает в себе не только ее физическую защиту, но и символизирует непрерывное развитие и преодоление препятствий.
Рисунок на панцире является свидетельством уникальности ее пути развития, символизируя гармонию между временем и самим существом. Рост панциря черепахи происходит из центральной точки, называемой пуповиной. Новые слои материала добавляются к уже существующему панцирю, что приводит к формированию различных узоров. Каждый сегмент узора представляет собой отдельный год или сезон роста черепахи. Слой за слоем, из года в год, панцирь взрослеет вместе с черепахой. Он приобретает новые узоры, образуя уникальные кластеры, которые являются отражением ее жизненного опыта и роста.
Панцирь черепахи состоит из двух основных частей: верхней части, называемой карапаксом, и нижней части, называемой пластроном. Рост панциря у черепах происходит в результате процесса, называемого метаморфозом. Узоры на панцире черепахи являются результатом сложного взаимодействия многих факторов, включая генетику, окружающую среду и процесс роста самого панциря.
Панцирь черепахи состоит из биологической ткани и карбонатных субстанций, таких как кальций и магний. Карбонатная структура панциря обеспечивает ему прочность и защищает внутренние органы черепахи. У молодых черепашек панцирь состоит из мягких хрящевых пластин, которые со временем каменеют и становятся твердыми костями. Панцирь растет благодаря регулярному отложению новых слоев костной ткани под кожей черепахи. Этот процесс позволяет панцирю увеличиваться в размере по мере того, как черепаха растет и, с течением времени, может привести к появлению новых узоров или изменению существующих.
Узоры на панцире черепахи не случайны. Они образуются в результате определенных биологических процессов и могут быть классифицированы в различные группы или "кластеры" на основе их формы, цвета и расположения. Например, некоторые черепахи имеют узоры в виде звезд, в то время как другие имеют узоры, напоминающие леопардовую шкуру. Так как панцирь черепахи растет, узоры на нем могут меняться и развиваться. Это может привести к изменению кластера, к которому принадлежит узор. Например, узор, который изначально был классифицирован как "звездчатый", может со временем стать более сложным.
Важно отметить, что у каждой черепахи узоры на панцире уникальны, они помогают ей адаптироваться к окружающей среде и выполнять важные функции, такие как маскировка или привлечение партнеров для размножения.
Узоры на панцире черепахи вдохновили меня на создание оригинального алгоритма оптимизации, а эволюция панциря черепахи стала метафорой для процесса слияния и кластеризации данных и определила создание нового инструмента, способного приспосабливаться и развиваться на основе опыта и знаний.
2.Реализация алгоритма
Идея алгоритма эволюции панциря черепахи заключается в эмуляции роста панциря за счет постепенного образования новых ороговевших участков кожи, представляющих собой решения оптимизационной задачи. В этой модели лучшие решения становятся более твердыми и находятся ближе к внешней поверхности панциря, в то время как менее удачные решения остаются мягкими и располагаются внутри панциря.
Панцирь в данном контексте разделяется на кластеры, формирующие рисунок на его поверхности, а его слои моделируются через вертикальное разделение на кластеры. Процесс эмуляции роста панциря в алгоритме включает движение как вверх (наружу), так и вниз (внутрь), а также в ширину. Уникальной особенностью этого алгоритма оптимизации является сохранение менее успешных решений, что проявляется в росте панциря внутрь. Внутренний слой панциря является единственным, который расширяется в обоих направлениях, в то время как остальные слои увеличиваются только наружу, причем худшие решения заменяются новыми. Каждый вертикальный кластер (слой) имеет ограниченную вместимость для решений; в случае, если максимальное количество не достигнуто, происходит простое добавление решений, в противном случае – решение заменяется согласно описанному принципу.
На рисунке 1 наглядно представлена кластеризация решений по их качеству и расстоянию между ними. Для лучшего понимания использован гипотетический пример с одномерным пространством решений. Эта схема позволяет наглядно увидеть, как происходит формирование кластеров в зависимости от качества и близости решений друг к другу.
Рисунок 1. Кластеризация по качеству решений и по расстоянию между решениями в алгоритме TSEA.
Напишем псевдокод алгоритма TSEA:
1. Сгенерировать случайные особи в популяцию.
2. Посчитать ФФ.
3. Начальная кластеризация популяции по вертикали.
4. Начальная кластеризация популяции K-Means по горизонтали.
5. Поместить популяцию в панцирь.
6. Генерация новой популяции на основе данных в панцире:
6.1. С вероятностью 0.8:
Выбрать кластер по вертикали.
Выбрать с вероятностью 0.5 лучшего агента в ячейке, либо любого случайного в ячейке.
С вероятностью 0.6 по каждой координате использовать выбранного агента в ячейке, либо использовать лучшее глобальное решение.
С помощью степенного распределения создать новую координату агента.
6.2 Либо:
Выбрать кластер по вертикали.
Выбрать два кластера по вертикали, из которых случайно выбрать по одному агенту.
Создать новую координату, как среднее значение координат выбранных агентов.
7. Посчитать ФФ.
8. Кластеризация популяции по вертикали.
9. Определить принадлежность агентов к кластерам панциря K-NN (метод ближайших N соседей).
10. Через каждые 50 эпох выполнить кластеризацию панциря по вертикали.
11. Поместить популяцию в панцирь.
12. Повторять с п.6.
Выбор кластера по вертикали будем выполнять по квадратичному закону (рис. 2), который определят большую вероятность быть выбранным последнему (лучшему) по списку кластеру по сравнению с 0-м (худшим).
Рисунок 2. Закон вероятности выбора кластера по вертикали (по качеству), где 3 - количество кластеров.
Таким образом, логика создания новых участков панциря (агенты - решения оптимизационной задачи) заключается в следующем:
- Выбор слоя панциря (вертикального кластера). Вероятность выбора верхнего, более твердого слоя выше, чем нижних, менее твердых слоев.
- Выбор участков панциря из горизонтальных кластеров в выбранном слое.
- "Сращивание" выбранных участков.
Вероятность "сращивания" (затвердевания) выше для верхних слоев, чем для нижних.
Теперь, когда у нас есть псевдокод и закон выбора агентов в родительской популяции, можно сказать, что задача выполнена на 99%. Конечно, я шучу, код всё же придётся написать.
Агента оптимизации алгоритма TSEA опишем в виде структуры "S_TSEA_Agent", нам понадобятся метки кластеров по вертикали и горизонтали.
1. Структура содержит следующие поля:
- c[] - массив для хранения координат агента
- f - переменная для хранения оценки (фитнеса) агента
- label - метка принадлежности к кластеру
- labelClustV - вертикальное кластеризование
- minDist - минимальное расстояние до ближайшего центроида
2. Init - это метод структуры "S_TSEA_Agent", который инициализирует поля структуры. Он принимает целочисленный аргумент "coords", который используется для изменения размера массива c с помощью функции ArrayResize.
3. f = -DBL_MAX - устанавливает начальное значение переменной f равным минимально возможной величине числа типа double.
4. label = -1 и labelClustV = -1 - инициализируют метки принадлежности к кластеру значением -1.
5. minDist = DBL_MAX - устанавливает начальное значение переменной "minDist" равным максимально возможной величине числа типа double.
Этот код представляет собой базовую структуру данных для агентов в алгоритме оптимизации TSEA и инициализирует их поля при создании нового агента. Это позволяет агентам хранить информацию о своем текущем состоянии и обновлять ее по мере выполнения алгоритма.
//—————————————————————————————————————————————————————————————————————————————— struct S_TSEA_Agent { double c []; //coordinates double f; //fitness int label; //cluster membership label int labelClustV; //clusters vertically double minDist; //minimum distance to the nearest centroid void Init (int coords) { ArrayResize (c, coords); f = -DBL_MAX; label = -1; labelClustV = -1; minDist = DBL_MAX; } }; //——————————————————————————————————————————————————————————————————————————————
Нам понадобится описать панцирь черепахи, представляющий собой двумерный массив, в котором по вертикали расположены кластеры по приспособленности, а по горизонтали кластеры по расположению. Каждая ячейка двумерного массива содержит от 0 до максимального значения, заданного во внешних параметрах алгоритма.
Кластер по горизонтали опишем структурой "S_TSEA_horizontal", которая содержит поля:
- indBest - индекс лучшего агента в ячейке
- agent[] - массив структур S_TSEA_Agent, который используется для хранения агентов
Кластер по вертикали можем описать структурой "S_TSEA_horizontal", содержащей поля:
- cell[] - массив структур "S_TSEA_horizontal".
Таким образом, код предоставляет нам возможность описать панцирь черепахи в двух направлениях двумерного массива, в каждой ячейке которого можно хранить агентов оптимизации. По сути, панцирь – это специальным образом структурированная родительская популяция, к которой будет удобно обращаться при создании дочерних агентов.
//—————————————————————————————————————————————————————————————————————————————— struct S_TSEA_horizontal { int indBest; S_TSEA_Agent agent []; }; struct S_TSEA_vertical { S_TSEA_horizontal cell []; }; //——————————————————————————————————————————————————————————————————————————————
Для выполнения кластеризации, согласно приведённому псевдокоду, в алгоритме TSEA используются два метода кластеризации: K-Means и K-NN. K-Means мы рассмотрели в статье об алгоритме BSO, а здесь мы лишь вспомним, как выглядит структура кластера:
- centroid[] - массив для хранения координат центроида ячейки
- f - переменная для хранения оценки (фитнеса) центроида
- count - количество агентов в кластере
- agentList[] - список агентов в кластере
- Init - метод структуры "S_Cluster", который инициализирует поля структуры
//—————————————————————————————————————————————————————————————————————————————— struct S_Cluster { double centroid []; //cluster centroid double f; //centroid fitness int count; //number of points in the cluster void Init (int coords) { ArrayResize (centroid, coords); f = -DBL_MAX; count = 0; ArrayResize (ideasList, 0, 100); } }; //——————————————————————————————————————————————————————————————————————————————
Для определения принадлежности дочернего агента к соответствующему кластеру, будем использовать метод K-NN (метод к-ближайших соседей).
В классе "C_TSEA_clusters" помимо метода K-Means содержатся следующие методы:
1. Метод "VectorDistance":
- Этот метод вычисляет Евклидово расстояние между двумя векторами "v1" и "v2", представленными массивами чисел типа "double".
- Он использует формулу Евклидова расстояния:
. - Возвращается вычисленное расстояние.
2. Структура "DistanceIndex":
- Структура представляет пару значений: расстояние "distance" и индекс "index".
- Используется для хранения расстояний от точки до других точек и их индексов.
3. Метод "BubbleSort":
- Этот метод сортирует массив объектов типа "DistanceIndex" методом пузырьковой сортировки по возрастанию расстояний.
- Используется временная переменная "temp" для обмена элементами массива.
4. Метод "KNN" реализует алгоритм k-ближайших соседей для классификации точки "point":
- Вычисляет расстояния от точки "point" до всех точек в массиве "data", сортирует эти расстояния и определяет принадлежность точки к одному из "n_clusters", кластеров на основе k ближайших соседей.
- Используется массив "votes" для подсчета голосов каждого кластера.
- Возвращается индекс кластера с наибольшим количеством голосов.
//—————————————————————————————————————————————————————————————————————————————— class C_TSEA_clusters { public: double VectorDistance (double &v1 [], double &v2 []) { double distance = 0.0; for (int i = 0; i < ArraySize (v1); i++) { distance += (v1 [i] - v2 [i]) * (v1 [i] - v2 [i]); } return MathSqrt (distance); } struct DistanceIndex { double distance; int index; }; void BubbleSort (DistanceIndex &arr [], int start, int end) { for (int i = start; i < end; i++) { for (int j = start; j < end - i; j++) { if (arr [j].distance > arr [j + 1].distance) { DistanceIndex temp = arr [j]; arr [j] = arr [j + 1]; arr [j + 1] = temp; } } } } int KNN (S_TSEA_Agent &data [], S_TSEA_Agent &point, int k_neighbors, int n_clusters) { int n = ArraySize (data); DistanceIndex distances_indices []; // Вычисление расстояний от точки до всех других точек for (int i = 0; i < n; i++) { DistanceIndex dist; dist.distance = VectorDistance (point.c, data [i].c); dist.index = i; ArrayResize (distances_indices, n); distances_indices [i] = dist; } // Сортировка расстояний BubbleSort (distances_indices, 0, n - 1); // Определение кластера для точки int votes []; ArrayResize (votes, n_clusters); ArrayInitialize (votes, 0); for (int j = 0; j < k_neighbors; j++) { int label = data [distances_indices [j].index].label; if (label != -1 && label < n_clusters) { votes [label]++; } } int max_votes = 0; int max_votes_cluster = -1; for (int j = 0; j < n_clusters; j++) { if (votes [j] > max_votes) { max_votes = votes [j]; max_votes_cluster = j; } } return max_votes_cluster; } }; //——————————————————————————————————————————————————————————————————————————————
Переходим непосредственно к описанию класса "C_AO_TSEA", который является производным от базового класса "C_AO" и реализует алгоритм "Turtle Shell Evolution Algorithm" (TSEA). Поля и методы класса:
1. C_AO_TSEA - конструктор инициализирует поля класса. Он устанавливает название алгоритма, его описание и ссылку на статью об алгоритме. Также он устанавливает параметры алгоритма, такие как: размер популяции, количество вертикальных и горизонтальных кластеров, количество ближайших соседей и максимальное количество агентов в ячейке.
2. SetParams - метод устанавливает параметры алгоритма на основе значений массива "params".
3. Init - метод инициализирует алгоритм. Он принимает минимальный и максимальный диапазоны поиска, шаг поиска и количество эпох.
4. Методы "Moving", "Revision" - основные методы алгоритма TSEA, которые реализуют его основную логику.
5. Поля "vClusters", "hClusters", "neighbNumb" и "maxAgentsInCell" - параметры алгоритма, которые устанавливаются в конструкторе и могут быть изменены с помощью метода "SetParams".
6. Массивы "agent", "cell" и "clusters" - структуры данных, используемые алгоритмом. Они содержат информацию об агентах, ячейках и кластерах соответственно.
7. Объект "km" класса "C_TSEA_clusters" - используется для выполнения операций кластеризации.
8. Приватные поля "minFval", "stepF", "epochs" и "epochsNow" - внутренние переменные. Они не предназначены для доступа извне класса.
//—————————————————————————————————————————————————————————————————————————————— class C_AO_TSEA : public C_AO { public: //-------------------------------------------------------------------- ~C_AO_TSEA () { } C_AO_TSEA () { ao_name = "TSEA"; ao_desc = "Turtle Shell Evolution Algorithm"; ao_link = "https://www.mql5.com/ru/articles/14789"; popSize = 100; //population size vClusters = 3; //number of vertical clusters hClusters = 10; //number of horizontal clusters neighbNumb = 5; //number of nearest neighbors maxAgentsInCell = 3; //max agents in cell ArrayResize (params, 5); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "vClusters"; params [1].val = vClusters; params [2].name = "hClusters"; params [2].val = hClusters; params [3].name = "neighbNumb"; params [3].val = neighbNumb; params [4].name = "maxAgentsInCell"; params [4].val = maxAgentsInCell; } void SetParams () { popSize = (int)params [0].val; vClusters = (int)params [1].val; hClusters = (int)params [2].val; neighbNumb = (int)params [3].val; maxAgentsInCell = (int)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 (); void Injection (const int popPos, const int coordPos, const double value); //---------------------------------------------------------------------------- int vClusters; //number of vertical clusters int hClusters; //number of horizontal clusters int neighbNumb; //number of nearest neighbors int maxAgentsInCell; S_TSEA_Agent agent []; S_TSEA_vertical cell []; S_Cluster clusters []; C_TSEA_clusters km; private: //------------------------------------------------------------------- double minFval; double stepF; int epochs; int epochsNow; }; //——————————————————————————————————————————————————————————————————————————————
Метод "Init" класса "C_AO_TSEA" инициализирует алгоритм TSEA. Подробное описание его работы:
1. StandardInit (rangeMinP, rangeMaxP, rangeStepP) - метод вызывается для стандартной инициализации алгоритма. Он принимает минимальный и максимальный диапазоны поиска и шаг поиска. Если инициализация не удалась, метод возвращает "false".
2. ArrayResize (agent, popSize) - изменяет размер массива "agent" до размера популяции "popSize". Затем для каждого агента вызывается метод "Init(coords)", который инициализирует агента.
3. ArrayResize (clusters, hClusters) - изменяет размер массива "clusters" до количества горизонтальных кластеров "hClusters". Затем для каждого кластера вызывается метод "Init(coords)", который инициализирует кластер.
4. ArrayResize (cell, vClusters) - изменяет размер массива "cell" до количества вертикальных кластеров "vClusters". Затем для каждой ячейки инициализируется массив "cell[i].cell" и массив агентов в каждой ячейке.
5. "minFval = DBL_MAX", "stepF = 0.0", "epochs = epochsP", "epochsNow = 0". Это инициализация внутренних переменных алгоритма.
6. В конце метод возвращает "true", указывая, что инициализация прошла успешно.
//—————————————————————————————————————————————————————————————————————————————— bool C_AO_TSEA::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 { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //---------------------------------------------------------------------------- ArrayResize (agent, popSize); for (int i = 0; i < popSize; i++) agent [i].Init (coords); ArrayResize (clusters, hClusters); for (int i = 0; i < hClusters; i++) clusters [i].Init (coords); ArrayResize (cell, vClusters); for (int i = 0; i < vClusters; i++) { ArrayResize (cell [i].cell, hClusters); for (int c = 0; c < hClusters; c++) ArrayResize (cell [i].cell [c].agent, 0, maxAgentsInCell); } minFval = DBL_MAX; stepF = 0.0; epochs = epochsP; epochsNow = 0; return true; } //——————————————————————————————————————————————————————————————————————————————
Метод "Moving" класса "C_AO_TSEA" реализует основную логику движения агентов в алгоритме TSEA. Краткое описание основных шагов:
1. Инициализация популяции:
- Если это первая итерация (revision == false), то генерируются случайные особи в популяцию.
- Иначе, происходит обновление популяции на основе существующих решений.
2. Обновление популяции:
- Для каждого кластера (vClusters х hClusters) находится лучшее решение.
- Новые решения формируются следующим образом:
- С вероятностью 0.5 копируется лучшее решение из случайного кластера с некоторым смещением
- С вероятностью 0.2 новое решение формируется, как среднее между двумя случайными решениями из разных кластеров
- Новые координаты решений генерируются с использованием степенного распределения, чтобы сохранять близость к лучшим решениям.
3. Обновление агентов (особей) в популяции
Этот метод реализует основную идею эволюции панциря черепахи, где лучшие решения становятся более "твердыми" и располагаются ближе к внешней поверхности, в то время как менее успешные решения остаются "мягкими" и находятся внутри. Кластеризация решений и сохранение менее успешных вариантов обеспечивают гибкость и адаптивность алгоритма.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_TSEA::Moving () { epochsNow++; //---------------------------------------------------------------------------- //1. Сгенерировать случайные особи в популяцию 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]); agent [i].c [c] = a [i].c [c]; } } return; } //---------------------------------------------------------------------------- int vPos = 0; int hPos = 0; int pos = 0; int size = 0; double val = 0.0; double rnd = 0.0; double min = 0.0; double max = 0.0; for (int v = 0; v < vClusters; v++) { for (int h = 0; h < hClusters; h++) { size = ArraySize (cell [v].cell [h].agent); if (size > 0) { max = -DBL_MAX; pos = -1; for (int c = 0; c < size; c++) { if (cell [v].cell [h].agent [c].f > max) { max = cell [v].cell [h].agent [c].f; pos = c; cell [v].cell [h].indBest = c; } } } } } for (int i = 0; i < popSize; i++) { if (u.RNDprobab () < 0.8) { while (true) { rnd = u.RNDprobab (); rnd = (-rnd * rnd + 1.0) * vClusters; vPos = (int)rnd; if (vPos > vClusters - 1) vPos = vClusters - 1; hPos = u.RNDminusOne (hClusters); size = ArraySize (cell [vPos].cell [hPos].agent); if (size > 0) break; } pos = u.RNDminusOne (size); if (u.RNDprobab () < 0.5) pos = cell [vPos].cell [hPos].indBest; for (int c = 0; c < coords; c++) { if (u.RNDprobab () < 0.6) val = cell [vPos].cell [hPos].agent [pos].c [c]; else val = cB [c]; double dist = (rangeMax [c] - rangeMin [c]) * 0.1; min = val - dist; if (min < rangeMin [c]) min = rangeMin [c]; max = val + dist; if (max > rangeMax [c]) max = rangeMax [c]; val = u.PowerDistribution (val, min, max, 30); a [i].c [c] = u.SeInDiSp (val, rangeMin [c], rangeMax [c], rangeStep [c]); agent [i].c [c] = a [i].c [c]; } } else { int size2 = 0; int hPos2 = 0; int pos2 = 0; while (true) { rnd = u.RNDprobab (); rnd = (-rnd * rnd + 1.0) * vClusters; vPos = (int)rnd; if (vPos > vClusters - 1) vPos = vClusters - 1; hPos = u.RNDminusOne (hClusters); size = ArraySize (cell [vPos].cell [hPos].agent); hPos2 = u.RNDminusOne (hClusters); size2 = ArraySize (cell [vPos].cell [hPos2].agent); if (size > 0 && size2 > 0) break; } pos = u.RNDminusOne (size); pos2 = u.RNDminusOne (size2); for (int c = 0; c < coords; c++) { val = (cell [vPos].cell [hPos ].agent [pos ].c [c] + cell [vPos].cell [hPos2].agent [pos2].c [c]) * 0.5; a [i].c [c] = u.SeInDiSp (val, rangeMin [c], rangeMax [c], rangeStep [c]); agent [i].c [c] = a [i].c [c]; } } } } //——————————————————————————————————————————————————————————————————————————————Метод "Revision" класса "C_AO_TSEA" реализует этап перераспределения участков панциря черепахи в алгоритме TSEA.
Он отвечает за процесс ревизии (обновления) популяции агентов и обновления лучшего глобального решения.
Основные шаги этой части алгоритма:
2. Разметка агентов по вертикальным кластерам "labelClustV" на основе их приспособленности.
3. Если это первая итерация (revision == false), то инициализируется кластеризация агентов с помощью алгоритма K-Means.
4. Если это не первая итерация, то выполняется следующее:
- Собираются все агенты в единый массив data.
- Для каждого агента в популяции определяется его горизонтальный кластер "label" с помощью алгоритма K-Nearest Neighbors.
- Каждые 50 эпох происходит обновление структуры "cell", в которой хранятся агенты, разделенные по кластерам.
5. Размещение каждого агента в соответствующую ячейку. Если ячейка уже заполнена, агент заменяет агента в ячейке с наименьшей (или наибольшей, если ячейка находится на нижнем уровне) приспособленностью.
Основная идея этого этапа - поддержание структуры панциря, где лучшие решения располагаются ближе к внешней поверхности, а менее успешные - внутри. Кластеризация агентов и динамическое обновление структуры панциря обеспечивают гибкость и адаптивность алгоритма.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_TSEA::Revision () { //получить приспособленность-------------------------------------------------- int pos = -1; for (int i = 0; i < popSize; i++) { agent [i].f = a [i].f; if (a [i].f > fB) { fB = a [i].f; pos = i; } if (a [i].f < minFval) minFval = a [i].f; } if (pos != -1) ArrayCopy (cB, a [pos].c, 0, 0, WHOLE_ARRAY); stepF = (fB - minFval) / vClusters; //Разметка по вертикали дочерней популяции------------------------------------ for (int i = 0; i < popSize; i++) { if (agent [i].f == fB) agent [i].labelClustV = vClusters - 1; else { agent [i].labelClustV = int((agent [i].f - minFval) / stepF); if (agent [i].labelClustV > vClusters - 1) agent [i].labelClustV = vClusters - 1; } } //---------------------------------------------------------------------------- if (!revision) { km.KMeansPlusPlusInit (agent, popSize, clusters); km.KMeans (agent, popSize, clusters); revision = true; } //---------------------------------------------------------------------------- else { static S_TSEA_Agent data []; ArrayResize (data, 0, 1000); int size = 0; for (int v = 0; v < vClusters; v++) { for (int h = 0; h < hClusters; h++) { for (int c = 0; c < ArraySize (cell [v].cell [h].agent); c++) { size++; ArrayResize (data, size); data [size - 1] = cell [v].cell [h].agent [c]; } } } for (int i = 0; i < popSize; i++) { agent [i].label = km.KNN (data, agent [i], neighbNumb, hClusters); } if (epochsNow % 50 == 0) { for (int v = 0; v < vClusters; v++) { for (int h = 0; h < hClusters; h++) { ArrayResize (cell [v].cell [h].agent, 0); } } for (int i = 0; i < ArraySize (data); i++) { if (data [i].f == fB) data [i].labelClustV = vClusters - 1; else { data [i].labelClustV = int((data [i].f - minFval) / stepF); if (data [i].labelClustV > vClusters - 1) data [i].labelClustV = vClusters - 1; } int v = data [i].labelClustV; int h = data [i].label; int size = ArraySize (cell [v].cell [h].agent) + 1; ArrayResize (cell [v].cell [h].agent, size); cell [v].cell [h].agent [size - 1] = data [i]; } } } //Поместить популяцию в панцирь---------------------------------------- for (int i = 0; i < popSize; i++) { int v = agent [i].labelClustV; int h = agent [i].label; int size = ArraySize (cell [v].cell [h].agent); int pos = 0; int posMin = 0; int posMax = 0; if (size >= maxAgentsInCell) { double minF = DBL_MAX; double maxF = -DBL_MAX; for (int c = 0; c < maxAgentsInCell; c++) { if (cell [v].cell [h].agent [c].f < minF) { minF = cell [v].cell [h].agent [c].f; posMin = c; } if (cell [v].cell [h].agent [c].f > maxF) { maxF = cell [v].cell [h].agent [c].f; posMax = c; } } if (v == 0) { if (agent [i].f < minF) { pos = posMin; } else { pos = posMax; } } else pos = posMin; } else { ArrayResize (cell [v].cell [h].agent, size + 1); pos = size; } cell [v].cell [h].agent [pos] = agent [i]; } } //——————————————————————————————————————————————————————————————————————————————
3. Результаты тестов
Вывод в принт результатов работы алгоритма эволюции панциря черепахи TSEA:
TSEA|Turtle Shell Evolution Algorithm|100.0|3.0|10.0|5.0|3.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.811921100517765
25 Hilly's; Func runs: 10000; result: 0.5537631430428238
500 Hilly's; Func runs: 10000; result: 0.2813575513298344
=============================
5 Forest's; Func runs: 10000; result: 0.9564485273109922
25 Forest's; Func runs: 10000; result: 0.481362270824773
500 Forest's; Func runs: 10000; result: 0.181400891410298
=============================
5 Megacity's; Func runs: 10000; result: 0.6676923076923076
25 Megacity's; Func runs: 10000; result: 0.3633846153846153
500 Megacity's; Func runs: 10000; result: 0.11670769230769343
=============================
All score: 4.41404 (49.04%)
Общий счет по всем тестовым функциям составляет 4.41404, что соответствует 49.04% от теоретического оптимального решения.
Визуализация работы тестового стенда демонстрирует хорошую сходимость алгоритма. На всех тестовых функциях наблюдается разброс траекторий на графике сходимости, однако с увеличением степеней свободы, этот разброс уменьшается. Использование кластеризации в алгоритме, а также поддержание постоянного количества агентов в каждой ячейке, позволяет алгоритму эффективно исследовать значимые участки фитнес-функции.
TSEA на тестовой функции Hilly.
TSEA на тестовой функции Forest.
TSEA на тестовой функции Megacity.
Алгоритм после тестирования на тестовых функциях занимет достойное 6-ое место в верхней части итоговой рейтинговой таблицы.
№ | 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 | BGA | binary genetic algorithm | 0,99992 | 0,99484 | 0,50483 | 2,49959 | 1,00000 | 0,99975 | 0,32054 | 2,32029 | 0,90667 | 0,96400 | 0,23035 | 2,10102 | 6,921 | 76,90 |
| 2 | (P+O)ES | (P+O) evolution strategies | 0,99934 | 0,91895 | 0,56297 | 2,48127 | 1,00000 | 0,93522 | 0,39179 | 2,32701 | 0,83167 | 0,64433 | 0,21155 | 1,68755 | 6,496 | 72,18 |
| 3 | 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 |
| 4 | 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 |
| 5 | 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 |
| 6 | 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 |
| 7 | 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 |
| 8 | BSA | bird swarm algorithm | 0,90857 | 0,73661 | 0,25767 | 1,90285 | 0,90437 | 0,81619 | 0,16401 | 1,88457 | 0,61692 | 0,54154 | 0,10951 | 1,26797 | 5,055 | 56,17 |
| 9 | 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 |
| 10 | 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 |
| 11 | (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 |
| 12 | BSO | brain storm optimization | 0,91301 | 0,56222 | 0,30047 | 1,77570 | 0,97162 | 0,57162 | 0,23449 | 1,77772 | 0,60462 | 0,27138 | 0,12011 | 0,99611 | 4,550 | 50,55 |
| 13 | 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 |
| 14 | 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 |
| 15 | 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 |
| 16 | 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 |
| 17 | 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 |
| 18 | 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 |
| 19 | 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 |
| 20 | 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 |
| 21 | 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 |
| 22 | 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 |
| 23 | 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 |
| 24 | 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 |
| 25 | 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 |
| 26 | 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 |
| 27 | 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 |
| 28 | 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 |
| 29 | 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 |
| 30 | 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 |
| 31 | 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 |
| 32 | 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 |
| 33 | 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 |
| 34 | 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 |
| 35 | 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 |
| 36 | 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 |
| 37 | 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 |
Выводы
Идея алгоритма оптимизации, основанной на росте панциря черепахи, оказалась достаточно интересной, даже такие медлительные животные могут служить вдохновением и примером "технических" решений, на которые природа неисчерпаема. На основе проведенных тестирований алгоритма TSEA (Turtle Shell Evolution Algorithm), можно выделить его особенности.
Сохранение менее успешных решений является уникальной особенностью алгоритма. Это проявляется в том, что менее успешные варианты сохраняются во внутреннем слое панциря. Такой подход позволяет поддерживать разнообразие в популяции и предотвращать преждевременную сходимость к локальным оптимумам. Важно помнить, что локальный минимум, кажущийся худшим решением, может находиться близко к глобальному оптимуму, поэтому продолжение исследования его окрестностей имеет смысл. Хотя алгоритм может менее интенсивно исследовать такие области, по сравнению с более перспективными местами, они все же остаются в фокусе внимания.
Разделение решений на кластеры по вертикали, имитирующие слои панциря, и горизонтали, имитирующие характерные рисунки на поверхности, позволяет достаточно эффективно выделять области пространства решений и исследовать их по отдельности. В то же время рисунок на панцире остаётся подвижным и может изменяться и адаптироваться к поверхности фитнес-функции.
Использование разделения панциря на слои позволяет формировать новые решения в пределах каждого слоя. Верхние твердые слои не взаимодействуют с нижними мягкими, и наоборот. Это напоминает процесс роста панциря у живой черепахи, но с отличием в том, что твердый участок с нижнего слоя может перейти на более верхние слои, благодаря периодической перекластеризации. Это можно сравнить со сбрасыванием старого панциря и формированием нового, более прочного и совершенного.
Алгоритм демонстрирует хорошую производительность на задачах с различным количеством измерений (масштабируемость), что свидетельствует о его гибкости.
В целом, TSEA представляет собой интересный подход, сочетающий механизмы эволюционных алгоритмов и кластеризации. Однако я уверен, что потенциал алгоритма еще далеко не исчерпан. На данный момент были использованы лишь некоторые способы создания новых решений из того огромного разнообразия, что рассматривались ранее в статьях. Алгоритм по-прежнему остается в фокусе моего внимания и открыт для дальнейшего совершенствования. Возможно, он послужит основой для появления новых модификаций, подобно тому, как произошло с PSO и другими известными алгоритмами.
Рисунок 3. Цветовая градация алгоритмов по соответствующим тестам. Белым цветом подсвечены результаты больше или равные 0.99.
Рисунок 4. Гистограмма результатов тестирования алгоритмов (по шкале от 0 до 100, чем больше, тем лучше,
где 100 - максимально возможный теоретический результат, в архиве скрипт для расчета рейтинговой таблицы).
Плюсы и минусы алгоритма эволюции панциря черепахи (TSEA):
Плюсы:
- Хорошая сходимость на различных типах функций
- Небольшое количество внешних параметров
Минусы:
- Высокий разброс результатов на функциях малой размерности
- Требовательность к вычислительным ресурсам
К статье прикреплен архив с актуальными версиями кодов алгоритмов. Автор статьи не несёт ответственности за абсолютную точность в описании канонических алгоритмов, во многие из них были внесены изменения для улучшения поисковых возможностей. Выводы и суждения, представленные в статьях, основываются на результатах проведённых экспериментов.
github: https://github.com/JQSakaJoo/Population-optimization-algorithms-MQL5
CodeBase: https://www.mql5.com/ru/code/49355
Разрабатываем мультивалютный советник (Часть 10): Создание объектов из строки
Разметка данных в анализе временных рядов (Часть 6)：Применение и тестирование советника с помощью ONNX
Риск-менеджер для алгоритмической торговли
Нейросети — это просто (Часть 89): Трансформер частотного разложения сигнала (FEDformer)
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Вы принимаете политику сайта и условия использования