Алгоритм циклического партеногенеза — Cyclic Parthenogenesis Algorithm (CPA)
301
0
Содержание
Введение
Оптимизационные алгоритмы, инспирированные природными явлениями, продолжают играть важную роль в решении сложных задач оптимизации. Особый интерес представляют алгоритмы, основанные на поведении социальных насекомых, таких как муравьи, пчелы и тли. В предыдущих статьях мы уже рассматривали ряд из них ACOm, ABHA. В данной статье представлен новый метаэвристический алгоритм оптимизации — Алгоритм Циклического Партеногенеза (Cyclic Parthenogenesis Algorithm, CPA), который имитирует уникальную репродуктивную стратегию тлей (aphids).
Тли демонстрируют замечательную адаптивную способность, благодаря их необычному жизненному циклу, который включает как бесполое размножение (партеногенез), так и половое. В благоприятных условиях тли размножаются партеногенетически, что позволяет быстро увеличивать популяцию. При ухудшении условий, они переключаются на половое размножение, что способствует генетическому разнообразию и повышает шансы на выживание в изменяющейся среде.
CPA математически моделирует эти биологические механизмы, создавая баланс между эксплуатацией найденных решений (через партеногенез) и исследованием новых областей поискового пространства (через половое размножение). Алгоритм также имитирует социальное поведение тлей, организуя решения в колонии и реализуя механизм миграции между ними, что способствует обмену информацией.
Особенности, перечисленные выше, должны показать CPA особенно эффективным для решения многомерных задач оптимизации, где требуется найти баланс между локальным и глобальным поиском. В данной статье мы подробно рассмотрим принципы работы алгоритма, его математическую модель и практическую реализацию. Алгоритм циклического партеногенеза был предложен Али Кавехом и Золгадром. Впервые он был опубликован в 2019 году.Реализация алгоритма
Представьте, что вы наблюдаете за колонией тлей в саду. Эти крошечные создания используют два способа размножения и очень эффективно адаптируются к окружающей среде. Алгоритм CPA (Cyclic Parthenogenesis Algorithm) имитирует именно это поведение для решения сложных задач оптимизации. Как это работает? При начальной организации создается несколько групп (колоний) решений, в каждой из которых есть "женские" и "мужские" особи.
В алгоритме предлагается два способа создания новых решений:- Первым способом является "Самостоятельное размножение", где лучшие решения создают свои копии с небольшими изменениями.
- Второй способ традиционный — "Размножение парами", где два разных решения комбинируются, создавая новое.
Иногда лучшее решение из одной колонии "перелетает" в другую. Алгоритм постоянно проверяет, какие решения лучше работают, и сохраняет самые лучшие находки и, в продолжении поиска, комбинирует успешные варианты. И всё это для того, чтобы найти самое оптимальное решение. Главная особенность алгоритма в том, что он находит баланс между использованием уже найденных хороших решений и поиском совершенно новых вариантов, подобно тому, как тли адаптируются к изменениям в окружающей среде.
Рисунок 1. Схема работы алгоритма CPA, основные формулы
Перейдем к визуальному представлению алгоритма CPA, где основными элементами на иллюстрации являются колонии, розовыми квадратиками отмечены женские особи (решения), синими — мужские особи (решения), пунктирной линией — путь перелета между колониями. Иллюстрация демонстрирует структуру колоний, механизмы размножения, процесс перелета между колониями, взаимодействие особей внутри колоний. Это поможет лучше понять принципы работы алгоритма через визуальную метафору с реальными афидами (тлями).
Рисунок 2. Колонии тлей и их взаимодействие в алгоритме CPA
Когда мы немного разобрались с описанием алгоритма, перейдем к написанию псевдокода:
Инициализация:
Создать популяцию размером Na особей
Разделить популяцию на Nc колоний
В каждой колонии:
Определить количество особей женского пола (Fr * Nm)
Определить количество особей мужского пола (остальные)
Задать начальные параметры:
alpha1 (коэффициент партеногенеза)
alpha2 (коэффициент спаривания)
Pf (вероятность перелета)
Основной цикл (для каждой эпохи):
Для каждой колонии:
Для особей женского пола:
Обновить позицию используя партеногенез:
новая_позиция = текущая_позиция + alpha1 * k * N(0,1) * (max_range - min_range)
где k = (total_epochs - current_epoch) / total_epochs
N(0,1) - нормальное распределение
Для особей мужского пола:
Выбрать случайную особь женского пола из той же колонии
Обновить позицию через спаривание:
новая_позиция = текущая_позиция + alpha2 * random[0,1] * (позиция_самки - текущая_позиция)
Ревизия позиций:
Обновить лучшее найденное решение
Сохранить текущие позиции
Отсортировать особей в каждой колонии по значению целевой функции
Миграция (с вероятностью Pf):
Выбрать две случайные колонии
Сравнить их лучшие решения
Переместить лучшее решение в худшую колонию
Пересортировать особей в колонии
Все подготовлено к написанию кода алгоритма, идем дальше. Напишем класс "C_AO_CPA", который наследуется от класса "C_AO". Этот класс реализует весь алгоритм, краткое описание его компонентов:
Конструктор C_AO_CPA:
- Устанавливает параметры, такие как размер популяции, количество колоний, соотношение самок, вероятность полета и коэффициенты масштабирования для партеногенеза и спаривания.
- Резервирует массив параметров и заполняет его значениями.
Метод SetParams устанавливает значения параметров из массива "params", преобразуя их в соответствующие типы.
Методы Init, Moving и Revision:
- Init — предназначен для инициализации алгоритма с заданными диапазонами и количеством эпох.
- Moving и Revision — методы реализуют логику перемещения и пересмотра в рамках алгоритма.
Члены класса определены переменными для хранения параметров алгоритма, таких как количество колоний, соотношение самок и самцов, а также параметры для управления процессом.
Приватные члены включают переменные для отслеживания текущей эпохи, количества членов в колонии и временный массив агентов.
//—————————————————————————————————————————————————————————————————————————————— // Класс реализующий Алгоритм Циклического Партеногенеза (CPA) // Наследуется от базового класса оптимизации class C_AO_CPA : public C_AO { public: C_AO_CPA (void) { ao_name = "CPA"; ao_desc = "Cyclic Parthenogenesis Algorithm"; ao_link = "https://www.mql5.com/ru/articles/16877"; popSize = 50; // общий размер популяции Na Nc = 10; // количество колоний Fr = 0.2; // соотношение особей женского пола Pf = 0.9; // вероятность перелета между колониями alpha1 = 0.3; // коэффициент масштабирования для партеногенеза alpha2 = 0.9; // коэффициент масштабирования для спаривания ArrayResize (params, 6); // Установка параметров алгоритма params [0].name = "popSize"; params [0].val = popSize; params [1].name = "Nc"; params [1].val = Nc; params [2].name = "Fr"; params [2].val = Fr; params [3].name = "Pf"; params [3].val = Pf; params [4].name = "alpha1_init"; params [4].val = alpha1; params [5].name = "alpha2_init"; params [5].val = alpha2; } void SetParams () { popSize = (int)params [0].val; Nc = (int)params [1].val; Fr = params [2].val; Pf = params [3].val; alpha1 = params [4].val; alpha2 = params [5].val; } bool Init (const double &rangeMinP [], // минимальный диапазон поиска const double &rangeMaxP [], // максимальный диапазон поиска const double &rangeStepP [], // шаг поиска const int epochsP = 0); // количество эпох void Moving (); // функция перемещения особей void Revision (); // функция пересмотра и обновления позиций //---------------------------------------------------------------------------- int Nc; // количество колоний double Fr; // соотношение особей женского пола double Pf; // вероятность перелета между колониями private: //------------------------------------------------------------------- int epochs; // общее количество эпох int epochNow; // текущая эпоха int Nm; // количество особей в каждой колонии double alpha1; // коэффициент масштабирования для партеногенеза double alpha2; // коэффициент масштабирования для спаривания int fNumber; // количество особей женского пола в колонии int mNumber; // количество особей мужского пола в колонии S_AO_Agent aT []; // временная колония для сортировки void SortFromTo (S_AO_Agent &p [], S_AO_Agent &pTemp [], int from, int count); // функция сортировки агентов }; //——————————————————————————————————————————————————————————————————————————————
Реализация метода "Init" класса "C_AO_CPA", его функциональность:
Параметры метода:
- rangeMinP, rangeMaxP, rangeStepP - массивы, определяющие минимальные и максимальные значения диапазона, а также шаг поиска.
- epochsP — количество эпох (по умолчанию 0).
- Метод сначала вызывает "StandardInit", чтобы выполнить стандартную инициализацию с переданными диапазонами. Если инициализация не удалась, метод возвращает "false".
- Устанавливает количество эпох (epochs) и текущую эпоху (epochNow).
- Вычисляет количество членов в колонии (Nm) на основе размера популяции и количества колоний.
- Определяет количество самок (fNumber) в колонии, гарантируя, что оно не меньше 1. Количество самцов (mNumber) вычисляется как разница между общим количеством членов и количеством самок.
- Резервирует массив "aT" для хранения временных агентов колонии.
- Метод возвращает "true", если инициализация прошла успешно.
Этот метод настраивает параметры и структуру для работы алгоритма, обеспечивая правильную инициализацию перед началом его выполнения.
//—————————————————————————————————————————————————————————————————————————————— // Инициализация алгоритма с заданными параметрами поиска bool C_AO_CPA::Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0) { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //---------------------------------------------------------------------------- epochs = epochsP; epochNow = 0; // Вычисление размера колонии и количества особей каждого пола Nm = popSize / Nc; fNumber = int(Nm * Fr); if (fNumber < 1) fNumber = 1; mNumber = Nm - fNumber; ArrayResize (aT, Nm); return true; } //——————————————————————————————————————————————————————————————————————————————
Метод "Moving" класса "C_AO_CPA" осуществляет перемещение агентов в пространстве решений, адаптируя их координаты на основе определённых правил и случайных факторов. Давайте разберем поэтапно:
Увеличение эпохи. Метод начинает с увеличения текущего показателя эпохи (epochNow), что говорит о том, что вызывался очередной шаг в процессе оптимизации или эволюции.
Первый этап (если ревизия не требуется) - если поле "revision" установлено в "false", выполняется инициализация координат каждого агента в популяции (popSize):
- Каждый агент (a[i]) получает новые координаты в каждом измерении (coords) с использованием функции "RNDfromCI", которая генерирует случайные значения в заданном диапазоне [rangeMin[c], rangeMax[c]].
- Затем координация модифицируется с помощью функции "SeInDiSp", которая обеспечивает коррекцию значений в соответствии с шагом дискретизации (rangeStep[c]).
- Устанавливается флаг "revision" в "true", и метод завершает выполнение.
- Переменная "k" рассчитывается как отношение оставшегося количества эпох к общему количеству эпох. Это позволяет постепенно сужать размах передвижения агентов по мере приближения завершения оптимизации.
- Перебираются колонии (col) и функции (fNumber), чтобы обновить координаты каждого агента для первых "fNumber" агентов в колонии это обновление происходит на основе их предыдущих координат (cP), с добавлением случайного значения, сгенерированного с помощью нормального распределения (GaussDistribution). Это значение масштабируется в диапазоне между "rangeMin" и "rangeMax".
- Для остальных агентов (m от fNumber до Nm) также обновляются координаты, но теперь используются случайно выбранные координаты одного из лучших агентов в той же колонии. Случайные значения добавляются к координатам каждого агента с учетом параметра "alpha2".
- Общая цель этого метода — переместить агентов в пространстве решений, основываясь на их предыдущем положении и вливая элемент случайности для изучения района, чтобы улучшить возможность нахождения глобального оптимума.
- Параметры, такие как "alpha1" и "alpha2", помогают контролировать уровень адаптации и случайности.
Таким образом, метод "Moving" в контексте алгоритма оптимизации имеет важное значение для перемещения агентов по пространству решений с учетом как их собственных предыдущих позиций, так и позиций других агентов.
//—————————————————————————————————————————————————————————————————————————————— // Основная функция перемещения особей в пространстве поиска void C_AO_CPA::Moving () { epochNow++; //---------------------------------------------------------------------------- // Начальная случайная инициализация позиций, если это первая итерация if (!revision) { for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { // Генерация случайной позиции в заданном диапазоне a [i].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]); a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } revision = true; return; } //---------------------------------------------------------------------------- // Вычисление коэффициента уменьшения силы поиска с течением времени double k = (epochs - epochNow)/(double)epochs; int ind = 0; int indF = 0; // Обработка каждой колонии for (int col = 0; col < Nc; col++) { // Обновление позиций особей женского пола (партеногенез) for (int f = 0; f < fNumber; f++) { ind = col * Nm + f; for (int c = 0; c < coords; c++) { // Партеногенетическое обновление позиции с использованием нормального распределения a [ind].c [c] = a [ind].cP [c] + alpha1 * k * u.GaussDistribution (0.0, -1.0, 1.0, 8) * (rangeMax [c] - rangeMin [c]); } } // Обновление позиций особей мужского пола (спаривание) for (int m = fNumber; m < Nm; m++) { ind = col * Nm + m; // Выбор случайной особи женского пола для спаривания indF = u.RNDintInRange (ind, col * Nm + fNumber - 1); for (int c = 0; c < coords; c++) { // Обновление позиции на основе выбранной особи женского пола a [ind].c [c] = a [ind].cP [c] + alpha2 * u.RNDprobab () * (a [indF].cP [c] - a [ind].cP [c]); } } } } //——————————————————————————————————————————————————————————————————————————————
Метод "Revision" класса "C_AO_CPA" отвечает за обновление состояния агентов в популяции на основе их значений функции "f", рассмотрим подробнее:
Инициализация — метод начинает с инициализации переменной "ind" со значением "-1", которая будет использоваться для хранения индекса агента с наилучшим значением функции "f".
Поиск лучшего агента — в первом цикле "for" происходит перебор всех агентов в популяции (popSize) и если значение функции "f" текущего агента (a[i].f) больше, чем текущее лучшее значение "fB", то:
- Обновляется "fB" на значение "a[i].f".
- Сохраняется индекс лучшего агента в переменной "ind".
- После завершения цикла, если был найден агент с лучшим значением (ind != -1), его координаты (c) копируются в массив "cB".
Копирование текущих координат. Во втором цикле "for" копируются текущие координат (c) каждого агента в их предыдущие координаты (cP). Это позволяет сохранить предыдущее состояние агентов для дальнейшего анализа.
Сортировка агентов. Третий цикл "for" проходит по всем колониям (Nc), и для каждой колонии вызывается метод "SortFromTo", который сортирует агентов в пределах колонии по их значениям функции "f". Индекс для сортировки рассчитывается как (ind = col * Nm).
Вероятностное обновление. Метод проверяет, если случайное значение, сгенерированное функцией "u.RNDprobab()", меньше порогового значения "Pf":
- Если условие выполняется, выбираются два случайных индекса колоний (indCol_1 и indCol_2), при этом гарантируется, что они не равны друг другу.
- Сравниваются значения функции "f" агентов в этих колониях. Если значение функции в первой колонии меньше, чем во второй, индексы меняются местами.
- Затем координаты первого агента в первой колонии копируются в координаты последнего агента во второй колонии.
- После этого снова вызывается "SortFromTo" для обновления порядка агентов во второй колонии.
Общая логика:
Метод "Revision" служит для обновления состояния агентов, сохраняя информацию о лучшем агенте и обеспечивая возможность обмена информацией между колониями.
//—————————————————————————————————————————————————————————————————————————————— // Функция пересмотра позиций и обмена информацией между колониями void C_AO_CPA::Revision () { // Поиск и обновление лучшего решения int ind = -1; for (int i = 0; i < popSize; i++) { if (a [i].f > fB) { fB = a [i].f; ind = i; } } if (ind != -1) ArrayCopy (cB, a [ind].c, 0, 0, WHOLE_ARRAY); //---------------------------------------------------------------------------- // Сохранение текущих позиций for (int i = 0; i < popSize; i++) { ArrayCopy (a [i].cP, a [i].c, 0, 0, WHOLE_ARRAY); } // Сортировка особей в каждой колонии по значению целевой функции for (int col = 0; col < Nc; col++) { ind = col * Nm; SortFromTo (a, aT, ind, Nm); } // Механизм перелета (миграции) между колониями if (u.RNDprobab () < Pf) { int indCol_1 = 0; int indCol_2 = 0; // Выбор двух случайных различных колоний indCol_1 = u.RNDminusOne (Nc); do indCol_2 = u.RNDminusOne (Nc); while (indCol_1 == indCol_2); // Обеспечение, чтобы лучшее решение было в первой колонии if (a [indCol_1 * Nm].f < a [indCol_2 * Nm].f) { int temp = indCol_1; indCol_1 = indCol_2; indCol_2 = temp; } // Копирование лучшего решения в худшую колонию ArrayCopy (a [indCol_2 * Nm + Nm - 1].cP, a [indCol_1 * Nm].cP, 0, 0, WHOLE_ARRAY); // Пересортировка колонии после миграции SortFromTo (a, aT, indCol_2 * Nm, Nm); } } //——————————————————————————————————————————————————————————————————————————————
Метод "SortFromTo" класса "C_AO_CPA" предназначен для сортировки массива агентов на основе их значений функции "f", разберем подробнее:
Инициализация переменных:
- Метод принимает три параметра — массив агентов "p", временный массив "pTemp", индекс начала сортировки "from" и количество элементов для сортировки "count".
- Переменные "cnt", "t0", и "t1" используются для отслеживания количества обменов и временного хранения значений.
- Массивы "ind" и "val" создаются для хранения индексов и значений функции приспособленности "f" соответственно.
Заполнение массивов индексов и значений. В первом цикле "for" заполняются массивы "ind" и "val":
- ind[i] получает индекс агента в исходном массиве, начиная с "from".
- val[i] получает значение функции "f" для соответствующего агента.
Сортировка. Основной цикл "while" выполняется до тех пор, пока есть обмены (т.е. cnt > 0). Внутренний цикл "for" проходит по массиву "val" и сравнивает соседние значения:
- Если текущее меньше следующего (val[i] < val[i + 1]), происходит обмен индексов в массиве "ind" и значений в массиве "val" .
- Увеличивается счетчик "cnt", чтобы показать, что произошел обмен.
- Этот процесс продолжается до тех пор, пока не будет выполнена полная итерация без обменов.
Копирование отсортированных значений:
- После завершения сортировки, в первом цикле "for" происходит копирование отсортированных агентов из временного массива "pTemp" обратно в исходный массив "p", начиная с индекса "from".
- Второй цикл "for" обновляет оригинальный массив "p", заменяя его отсортированными значениями.
//—————————————————————————————————————————————————————————————————————————————— // Вспомогательная функция сортировки агентов по значению целевой функции void C_AO_CPA::SortFromTo (S_AO_Agent &p [], S_AO_Agent &pTemp [], int from, int count) { int cnt = 1; int t0 = 0; double t1 = 0.0; int ind []; double val []; ArrayResize (ind, count); ArrayResize (val, count); // Копирование значений для сортировки for (int i = 0; i < count; i++) { ind [i] = i + from; val [i] = p [i + from].f; } // Сортировка пузырьком по убыванию while (cnt > 0) { cnt = 0; for (int i = 0; i < count - 1; i++) { if (val [i] < val [i + 1]) { // Обмен индексов t0 = ind [i + 1]; ind [i + 1] = ind [i]; ind [i] = t0; // Обмен значений t1 = val [i + 1]; val [i + 1] = val [i]; val [i] = t1; cnt++; } } } // Применение результатов сортировки for (int i = 0; i < count; i++) pTemp [i] = p [ind [i]]; for (int i = from; i < from + count; i++) p [i] = pTemp [i - from]; } //——————————————————————————————————————————————————————————————————————————————
После написания и подробного разбора кода алгоритма, перейдем к результатам тестирования алгоритма CPA.
Результаты тестов
При реализации интересной и своеобразной логики алгоритма, я даже не допускал мысли, что он не попадет в первые строки рейтинговой таблицы, и было некоторое разочарование при детальном рассмотрении результатов тестирования алгоритма CPA. По итогам тестирования алгоритм набрал самое большее 34,76 % от максимально возможного результата.
CPA|Cyclic Parthenogenesis Algorithm|50.0|10.0|0.2|0.9|0.3|0.9|
=============================
5 Hilly's; Func runs: 10000; result: 0.7166412833856777
25 Hilly's; Func runs: 10000; result: 0.4001377868508138
500 Hilly's; Func runs: 10000; result: 0.25502012607456315
=============================
5 Forest's; Func runs: 10000; result: 0.6217765628284961
25 Forest's; Func runs: 10000; result: 0.3365148812759322
500 Forest's; Func runs: 10000; result: 0.192638189788532
=============================
5 Megacity's; Func runs: 10000; result: 0.34307692307692306
25 Megacity's; Func runs: 10000; result: 0.16769230769230772
500 Megacity's; Func runs: 10000; result: 0.09455384615384692
=============================
All score: 3.12805 (34.76%)
Визуализация демонстрирует характерное для алгоритма перемещение виртуальных тлей в пространстве поиска, особенно это заметно при высоких размерностях задачи, можно даже на глаз определить отдельные колонии и движение виртуальных созданий в них.
CPA на тестовой функции Hilly
CPA на тестовой функции Forest
CPA на тестовой функции Megacity
Алгоритм CPA после тестирования расположился на 44-м месте в рейтинговой таблице и вошел в группу из 45 лучших популяционных алгоритмов оптимизации.
| № | 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 | BHAm | black hole algorithm M | 0,75236 | 0,76675 | 0,34583 | 1,86493 | 0,93593 | 0,80152 | 0,27177 | 2,00923 | 0,65077 | 0,51646 | 0,15472 | 1,32195 | 5,196 | 57,73 |
| 12 | 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 |
| 13 | 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 |
| 14 | 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 |
| 15 | 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 |
| 16 | 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 |
| 17 | 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 |
| 18 | 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 |
| 19 | 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 |
| 20 | 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 |
| 21 | 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 |
| 22 | (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 |
| 23 | 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 |
| 24 | 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 |
| 25 | 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 |
| 26 | 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 |
| 27 | 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 |
| 28 | 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 |
| 29 | 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 |
| 30 | 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 |
| 31 | 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 |
| 32 | 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 |
| 33 | 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 |
| 34 | 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 |
| 35 | 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 |
| 36 | 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 |
| 37 | 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 |
| 38 | 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 |
| 39 | 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 |
| 40 | 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 |
| 41 | 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 |
| 42 | 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 |
| 43 | BBBC | big bang-big crunch algorithm | 0,60531 | 0,45250 | 0,31255 | 1,37036 | 0,52323 | 0,35426 | 0,20417 | 1,08166 | 0,39769 | 0,19431 | 0,11286 | 0,70486 | 3,157 | 35,08 |
| 44 | CPA | cyclic parthenogenesis algorithm | 0,71664 | 0,40014 | 0,25502 | 1,37180 | 0,62178 | 0,33651 | 0,19264 | 1,15093 | 0,34308 | 0,16769 | 0,09455 | 0,60532 | 3,128 | 34,76 |
| 45 | 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 |
| RW | random walk | 0,48754 | 0,32159 | 0,25781 | 1,06694 | 0,37554 | 0,21944 | 0,15877 | 0,75375 | 0,27969 | 0,14917 | 0,09847 | 0,52734 | 2,348 | 26,09 | |
Выводы
Работа над реализацией и тестированием алгоритма CPA позволила сделать интересные наблюдения и выводы. Алгоритм представляет собой популяционный метод оптимизации, основанный на поведении тлей, и, хотя сама идея выглядит многообещающей, результаты тестирования показывают относительно низкую эффективность по сравнению с другими популяционными алгоритмами.
Основная идея алгоритма заключается в использовании двух типов размножения (со спариванием и без) и разделении популяции на колонии с возможностью миграции между ними. Биологическая метафора здесь достаточно элегантна: тли действительно используют как партеногенез, так и половое размножение, адаптируясь к условиям среды. Однако, математическая реализация этих концепций оказалась не столь эффективной, как хотелось бы.
Слабые места алгоритма проявляются в нескольких аспектах. Во-первых, деление особей популяции на женские и мужские не обеспечивает достаточного разнообразия и качества решений. Во-вторых, разделение на колонии, хотя и призвано способствовать исследованию различных областей пространства поиска, на практике часто приводит к преждевременной сходимости к локальным оптимумам. Механизм перелета между колониями, который должен противодействовать этому эффекту, оказывается недостаточно эффективным.
Настройка параметров алгоритма также представляет собой нетривиальную задачу. Такие параметры как размер колоний (Nm), доля женских особей (Fr), вероятность перелета (Pf) и коэффициенты масштабирования (alpha1, alpha2) существенно влияют на производительность алгоритма и нахождение их оптимальных значений затруднительно. Попытки улучшить алгоритм путем введения адаптивных параметров привели к некоторым улучшениям, но не смогли кардинально повысить его эффективность. Это наводит на мысль, что проблема может быть более фундаментальной и связана с самой структурой алгоритма.
Тем не менее, работа над этим алгоритмом была полезной с нескольких точек зрения. Во-первых, она предоставила хороший опыт анализа и реализации биоинспирированного алгоритма. Во-вторых, процесс отладки и оптимизации помог лучше понять важность баланса между исследованием пространства поиска и эксплуатацией найденных решений в метаэвристических алгоритмах. В-третьих, это хороший пример того, как красивая биологическая аналогия не всегда трансформируется в эффективный оптимизационный алгоритм.
В заключение стоит отметить, что даже не самые успешные алгоритмы вносят вклад в развитие области метаэвристической оптимизации, предоставляя новые идеи и подходы, которые могут быть использованы при разработке более эффективных методов. CPA, несмотря на свои ограничения, демонстрирует интересный подход к балансировке между различными стратегиями поиска решений и может служить отправной точкой для дальнейших исследований в этом направлении.
Рисунок 3. Цветовая градация алгоритмов по соответствующим тестам
Рисунок 3. Гистограмма результатов тестирования алгоритмов (по шкале от 0 до 100, чем больше, тем лучше, где 100 - максимально возможный теоретический результат, в архиве скрипт для расчета рейтинговой таблицы)
Плюсы и минусы алгоритма CPA:
Плюсы:
- Интересная идея.
- Достаточно простая реализация.
- Неплохо работает на задачах больших размерностей.
Минусы:
- Много внешних параметров.
- Низкая скорость и точность сходимости.
К статье прикреплён архив с актуальными версиями кодов алгоритмов. Автор статьи не несёт ответственности за абсолютную точность в описании канонических алгоритмов, во многие из них были внесены изменения для улучшения поисковых возможностей. Выводы и суждения, представленные в статьях, основываются на результатах проведённых экспериментов.
Программы, используемые в статье
| # | Имя | Тип | Описание |
|---|---|---|---|
| 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_CPA.mq5 | Скрипт | Испытательный стенд для CPA |
От начального до среднего уровня: Операторы
Разработка системы репликации (Часть 59): Новое будущее
Визуальная оценка и корректировка торговли в MetaTrader 5
Нейросети в трейдинге: Контекстно-зависимое обучение, дополненное памятью (MacroHFT)
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Вы принимаете политику сайта и условия использования