Оптимизация коралловых рифов — Coral Reefs Optimization (CRO)
337
0
Содержание
Введение
Биоинспирированные алгоритмы, черпающие вдохновение в природных процессах и системах, в последнее время вызывают большой интерес со стороны разработчиков. Среди таких алгоритмов выделяется алгоритм оптимизации коралловых рифов (Coral Reef Optimization, CRO), предложенный изначально S. Salcedo-Sanz и соавторами в 2014 году.
Алгоритм CRO основан на моделировании процессов формирования и развития коралловых рифов в природе. Эти процессы включают различные механизмы размножения кораллов (внешнее и внутреннее половое размножение, а также бесполое), конкуренцию за ограниченное пространство в рифе и гибель слабых особей. Подобно тому, как эволюция формирует устойчивые и адаптированные коралловые рифы в природе, алгоритм CRO позволяет исследовать пространство поиска и находить оптимальные или близкие к оптимальным решениям различных задач.
В настоящей работе будет представлена усовершенствованная версия алгоритма CROm с модифицированным механизмом уничтожения, основанным на использовании обратного степенного распределения для генерации новых решений в окрестностях лучших. Предлагаемый подход не только сохраняет традиционные преимущества CRO такие, как эксплоративная способность, естественный баланс между глобальным исследованием и локальной эксплуатацией пространства поиска, но и дополняет их более эффективным механизмом, который позволяет точнее локализовать перспективные области поиска и быстрее сходиться к оптимальным решениям.
Будет приведено обширное тестирование предложенного алгоритма на наборе классических тестовых функций оптимизации, демонстрируя его лучшую эффективность в сравнении с оригинальным алгоритмом CRO и другими современными метаэвристиками. Результаты экспериментов показывают, что предложенный подход особенно эффективен для задач с многомодальными целевыми функциями и сложной структурой ландшафта поиска.
Статья структурирована следующим образом: сначала мы рассматриваем основные концепции и принципы работы стандартного алгоритма CRO, затем, детально описываем предложенные модификации и их теоретическое обоснование. Далее следует экспериментальная оценка алгоритма, анализ результатов. В заключении, мы обсуждаем полученные результаты, ограничения предложенного метода и возможные направления для будущих исследований.
Реализация алгоритма
Основная идея CRO заключается в моделировании коралловых колоний, которые развиваются и конкурируют за пространство в рифе, формируя в итоге оптимальную структуру. Каждый коралл в рифе представляет собой потенциальное решение рассматриваемой задачи оптимизации.
Риф моделируется, как двумерная решетка размером N×M. Каждая клетка решетки может быть либо занята кораллом, либо оставаться пустой. Коралл представляет собой закодированное решение задачи оптимизации. Для каждого коралла определяется функция приспособленности (здоровья), которая соответствует целевой функции оптимизационной задачи.
Параметр ρ₀ ∈ (0,1) определяет начальную долю заполненности рифа кораллами, то есть, отношение занятых клеток к общему числу клеток в начале работы алгоритма. Инициализация рифа выполняется следующим образом:
- Задается размер рифа N×M и начальная доля заполненности ρ₀.
- Случайным образом выбираются ⌊ρ₀ × N × M⌋ клеток рифа для размещения начальных кораллов.
- Начальные кораллы генерируются случайным образом в пределах области поиска и размещаются в выбранных клетках.
После инициализации рифа запускается итеративный процесс формирования и развития рифа, состоящий из нескольких этапов:
Внешнее половое размножение (Broadcast Spawning). Для этого типа размножения выбирается определенная доля Fₑ существующих кораллов. Выбранные кораллы формируют пары и с помощью операторов скрещивания создают потомство. Каждая пара производит личинку с использованием оператора скрещивания (обычное усреднение).
Внутреннее половое размножение (Brooding). Оставшаяся доля кораллов (1-Fₑ) участвует в процессе внутреннего размножения, где каждый коралл производит потомство путем мутации. Для каждого коралла, выбранного для внутреннего размножения, личинка создается с использованием оператора мутации и обычно представляет небольшое случайное изменение закодированного решения. Оседание личинок. После формирования личинок на этапах размножения каждая пытается занять место в рифе. Процесс оседания выполняется по следующим правилам:
- Личинка случайным образом выбирает клетку (i, j) в рифе.
- Если клетка свободна, личинка занимает ее.
- Если клетка занята, личинка может вытеснить существующий коралл, только если ее приспособленность выше: f(личинка) > f(Ξᵢⱼ).
- Если вытеснение не произошло, личинка может попытаться осесть в другом месте (до максимального числа попыток k).
- Если после k попыток личинка не смогла найти место, она погибает.
Бесполое размножение (Почкование). Лучшие кораллы в рифе (доля Fₐ) могут размножаться бесполым путем, создавая точные копии самих себя (клоны). Формально:
- Кораллы сортируются по значению функции приспособленности.
- Лучшие Fₐ × 100% кораллов выбираются для бесполого размножения.
- Каждый выбранный коралл создает клон, который пытается осесть в рифе по тем же правилам, что и в процессе оседания личинок.
Вымирание. В конце каждой итерации худшие кораллы в рифе могут погибнуть с вероятностью Pd, освобождая пространство для новых кораллов в следующих итерациях.
Процесс формирования рифа повторяется до выполнения заданного критерия остановки, достижения максимального числа итераций. После остановки, лучший коралл в рифе представляет найденное решение задачи оптимизации.
Рисунок 1. Схема работы алгоритма CRO
На иллюстрации выше представлены все шесть основных этапов работы алгоритма:
- Инициализация (ρ₀ = 0.6) — отображает двумерную решетку (риф), частично заполненную разноцветными кораллами, представляющими различные решения.
- Внешнее размножение (Fb = 0.9) — показывает кораллы, образующие пары и создающие личинки через скрещивание.
- Внутреннее размножение (1-Fb = 0.1) — демонстрирует отдельные кораллы, производящие личинки путем мутации.
- Оседание личинок (k = 3 попытки) — иллюстрирует процесс поиска личинками места в рифе, включая успешные и неудачные попытки.
- Бесполое размножение (Fa = 0.1) — показывает лучшие кораллы (отмеченные звездочками), создающие точные копии самих себя.
- Вымирание (Fd = 0.1, Pd = 0.05) — демонстрирует удаление худших кораллов из рифа.
Вход: Параметры рифа (N, M, ρ₀, Fₑ, Fₐ, Fd, Pd, k)
Выход: Лучшее найденное решение
1. Инициализация:
- Создать риф размером N×M
- Заполнить ⌊ρ₀ × N × M⌋ клеток случайными кораллами
- Вычислить приспособленность каждого коралла
2. Пока не выполнен критерий остановки:
3. Внешнее половое размножение:
- Выбрать долю Fₑ кораллов для участия
- Сформировать пары и создать личинки через скрещивание
4. Внутреннее половое размножение:
- Для оставшихся кораллов (1-Fₑ) создать личинки через мутацию
5. Оседание личинок:
- Для каждой личинки:
- Попытаться занять случайную клетку рифа
- Если занято, вытеснить существующий коралл при более высокой приспособленности
- Если не удалось, попытаться еще раз (до k попыток)
6. Бесполое размножение:
- Сортировать кораллы по приспособленности
- Лучшие Fₐ кораллов создают клоны
- Клоны пытаются осесть в рифе
7. Вымирание:
- С вероятностью Pd выполнить уничтожение
- Удалить долю Fd худших кораллов
8. Вернуть лучший коралл в рифе
Теперь можем составить код алгоритма CRO. Напишем класс "C_AO_CRO", который реализует алгоритм CRO и наследуется от базового класса "C_AO".
Параметры CRO:
В классе объявлены параметры, управляющие поведением алгоритма:
- popSize — размер популяции кораллов.
- reefRows — высота рифа (количество строк в сетке).
- reefCols — ширина рифа (количество столбцов в сетке).
- rho0 — начальная занятость рифа. Это процент клеток рифа, занятых кораллами в начале работы алгоритма.
- Fb — доля кораллов, участвующих во внешнем размножении (Broadcast Spawning).
- Fa — доля кораллов, участвующих в бесполом размножении (fragmentation).
- Fd — доля кораллов, подлежащих удалению из-за низкой приспособленности.
- Pd — вероятность уничтожения кораллов.
- attemptsNum — количество попыток, которые личинка предпринимает, чтобы осесть на рифе.
Методы класса:
- SetParams () — метод устанавливает значения параметров алгоритма, основываясь на значениях, хранящихся в массиве "params" — это массив, позволяющий динамически изменять параметры алгоритма во время выполнения.
- Init () — метод инициализации, принимает диапазоны поиска для переменных оптимизации (rangeMinP, rangeMaxP, rangeStepP) и количество эпох (epochsP). Метод "Init" выполняет необходимые приготовления для начала работы алгоритма, такие как инициализация популяции и рифа.
- Moving () — функция реализует основную логику перемещения кораллов в рифе.
- Revision () — метод отвечает за пересмотр и корректировку позиций кораллов на рифе.
- InitReef () — инициализирует структуру рифа, подготавливая его к заселению кораллами.
- LarvaSettling () — определяет, куда осядет личинка коралла на рифе, моделирует процесс заселения рифа новыми кораллами. Параметр "larva" представляет собой личинку коралла.
- BroadcastSpawning () — процесс внешнего размножения, когда кораллы выпускают личинки в воду.
- Brooding () — альтернативный процесс размножения, когда личинки развиваются внутри коралла.
- AsexualReproduction () — процесс бесполого размножения, когда кораллы фрагментируются и образуют новые колонии.
- Depredation () — процесс вымирания, когда кораллы уничтожаются.
- GetReefCoordIndex () — преобразует координаты рифа (строка и столбец) в индекс в одномерном массиве.
- SortAgentsByFitness () — сортирует кораллы в соответствии с их приспособленностью (fitness).
Приватные переменные:
- totalReefSize — общий размер рифа (произведение "reefRows" и "reefCols").
- occupied [] — массив булевых значений, указывающих, занята ли каждая клетка рифа кораллом.
- reefIndices [] — массив индексов, содержащий индексы кораллов (из массива "a []" базового класса "C_AO") в занятых клетках рифа.
//—————————————————————————————————————————————————————————————————————————————— class C_AO_CRO : public C_AO { public: //-------------------------------------------------------------------- ~C_AO_CRO () { } C_AO_CRO () { ao_name = "CRO"; ao_desc = "Coral Reef Optimization"; ao_link = "https://www.mql5.com/ru/articles/17760"; popSize = 50; // размер популяции reefRows = 20; // высота рифа reefCols = 20; // ширина рифа rho0 = 0.2; // начальная занятость рифа Fb = 0.99; // доля кораллов для внешнего размножения Fa = 0.01; // доля кораллов для бесполого размножения Fd = 0.8; // доля кораллов для удаления Pd = 0.9; // вероятность уничтожения attemptsNum = 20; // количество попыток для оседания личинок ArrayResize (params, 9); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "reefRows"; params [1].val = reefRows; params [2].name = "reefCols"; params [2].val = reefCols; params [3].name = "rho0"; params [3].val = rho0; params [4].name = "Fb"; params [4].val = Fb; params [5].name = "Fa"; params [5].val = Fa; params [6].name = "Fd"; params [6].val = Fd; params [7].name = "Pd"; params [7].val = Pd; params [8].name = "attemptsNum"; params [8].val = attemptsNum; } void SetParams () { popSize = (int)params [0].val; reefRows = (int)params [1].val; reefCols = (int)params [2].val; rho0 = params [3].val; Fb = params [4].val; Fa = params [5].val; Fd = params [6].val; Pd = params [7].val; attemptsNum = (int)params [8].val; } bool Init (const double &rangeMinP [], // минимальный диапазон поиска const double &rangeMaxP [], // максимальный диапазон поиска const double &rangeStepP [], // шаг поиска const int epochsP = 0); // количество эпох void Moving (); void Revision (); //---------------------------------------------------------------------------- int reefRows; // высота рифа int reefCols; // ширина рифа double rho0; // начальная занятость рифа double Fb; // доля кораллов для внешнего размножения double Fa; // доля кораллов для бесполого размножения double Fd; // доля кораллов для удаления double Pd; // вероятность уничтожения int attemptsNum; // количество попыток для оседания личинок private: //------------------------------------------------------------------- int totalReefSize; // общий размер рифа bool occupied []; // флаги занятости клеток рифа int reefIndices []; // индексы агентов в a[], соответствующие занятым клеткам // Вспомогательные методы void InitReef (); int LarvaSettling (S_AO_Agent &larva); void BroadcastSpawning (S_AO_Agent &larvae [], int &larvaCount); void Brooding (S_AO_Agent &larvae [], int &larvaCount); void AsexualReproduction (); void Depredation (); int GetReefCoordIndex (int row, int col); void SortAgentsByFitness (int &indices [], int &count); }; //——————————————————————————————————————————————————————————————————————————————
Метод "Init" инициализирует алгоритм CRO: вызывает "StandardInit" базового класса, далее вычисляет общий размер рифа "totalReefSize", определяет начальное количество кораллов "initialPopSize", инициализирует массивы "occupied" — занятость клеток и "reefIndices" — индексы кораллов, вызывает "InitReef ()" для размещения кораллов на рифе и наконец возвращает "true" при успехе.
//—————————————————————————————————————————————————————————————————————————————— bool C_AO_CRO::Init (const double &rangeMinP [], // минимальный диапазон поиска const double &rangeMaxP [], // максимальный диапазон поиска const double &rangeStepP [], // шаг поиска const int epochsP = 0) // количество эпох { // Стандартная инициализация родительского класса if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //---------------------------------------------------------------------------- // Рассчитываем общий размер рифа totalReefSize = reefRows * reefCols; // Количество начальных кораллов не должно превышать popSize int initialPopSize = (int)MathRound (rho0 * totalReefSize); if (initialPopSize > popSize) initialPopSize = popSize; // Инициализация массива занятости и индексов ArrayResize (occupied, totalReefSize); ArrayResize (reefIndices, totalReefSize); // Заполняем массивы начальными значениями for (int i = 0; i < totalReefSize; i++) { occupied [i] = false; reefIndices [i] = -1; } // Инициализация рифа InitReef (); return true; } //——————————————————————————————————————————————————————————————————————————————Метод "InitReef ()" класса "C_AO_CRO" инициализирует начальную популяцию кораллов на рифе. Сначала вычисляется количество кораллов для инициализации, исходя из заданной плотности (rho0) рифа, это количество ограничивается размером популяции "popSize". Затем, для каждого коралла выделяется случайная, но свободная позиция на рифе, после ее нахождения, она отмечается как занятая, и коралл связывается с этой позицией в массиве "reefIndices". Далее генерируются координаты для каждого коралла. Каждая координата выбирается случайным образом в пределах заданных границ (rangeMin, rangeMax) и дискретизуется с использованием функции "u.SeInDiSp", учитывающей шаг дискретизации (rangeStep). Это обеспечивает равномерное и контролируемое распределение начальных решений (кораллов) в пространстве поиска.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CRO::InitReef () { // Количество начальных кораллов в рифе (исходя из rho0) int initialCorals = (int)MathRound (rho0 * totalReefSize); // Количество начальных кораллов не должно превышать размер популяции if (initialCorals > popSize) initialCorals = popSize; // Инициализируем initialCorals случайных позиций в рифе for (int i = 0; i < initialCorals; i++) { int pos; // Ищем свободную позицию do { pos = (int)MathFloor (u.RNDfromCI (0, totalReefSize)); // Защита от выхода за пределы массива if (pos < 0) pos = 0; if (pos >= totalReefSize) pos = totalReefSize - 1; } while (occupied [pos]); // Создаем новый коралл на найденной позиции occupied [pos] = true; reefIndices [pos] = i; // Генерируем случайные координаты для нового коралла for (int c = 0; c < coords; c++) { double coordinate = u.RNDfromCI (rangeMin [c], rangeMax [c]); a [i].c [c] = u.SeInDiSp (coordinate, rangeMin [c], rangeMax [c], rangeStep [c]); } } } //——————————————————————————————————————————————————————————————————————————————
Метод "Moving ()" выполняет начальную оценку популяции кораллов. Если "revision" имеет значение "false", то метод выполняет итерацию по всем позициям рифа. Для каждой занятой позиции (определяется по значению элемента массива "occupied") метод получает индекс коралла, находящегося на этой позиции, из массива "reefIndices". Если полученный индекс "idx" является валидным, будет выполнено вычисление приспособленности этого коралла.
Важно отметить, что метод "Moving ()" сам напрямую не вычисляет приспособленность, а лишь обеспечивает необходимую информацию для ее вычисления. После завершения итерации по всем позициям рифа, метод устанавливает значение "revision" в "true", чтобы предотвратить повторный проход цикла оценки кораллов на этой же итерации оптимизации. По сути, метод "Moving ()" выполняет роль триггера для вычисления приспособленности кораллов, обеспечивая однократное выполнение этого процесса на каждой итерации оптимизации.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CRO::Moving () { if (!revision) { // Первичная оценка всех кораллов в рифе for (int i = 0; i < totalReefSize; i++) { if (occupied [i]) { int idx = reefIndices [i]; if (idx >= 0 && idx < popSize) { // Расчет приспособленности не требует использования GetFitness() // так как он будет вычислен во внешнем коде (в FuncTests) } } } revision = true; } } //——————————————————————————————————————————————————————————————————————————————
Метод "Revision ()" обновляет глобальное лучшее решение: ищет кораллы на рифе с приспособленностью лучше текущего глобального лучшего решения и заменяет его. Создает массив, приготавливая место для личинок, полученных в результате размножения. Далее метод запускает половые размножения: вызывает методы "BroadcastSpawning" и "Brooding" для создания личинок. Следующим шагом метод реализует оседание личинок, с помощью метода "LarvaSettling" для определения мест для новых личинок на рифе. Запускает бесполое размножение "AsexualReproduction", в конце происходит уничтожение. Короче говоря: обновляет решение, размножает кораллы, размещает личинки и моделирует влияние вымирания.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CRO::Revision () { // Обновление глобального наилучшего решения for (int i = 0; i < totalReefSize; i++) { if (occupied [i] && a [reefIndices [i]].f > fB) { fB = a [reefIndices [i]].f; ArrayCopy (cB, a [reefIndices [i]].c, 0, 0, WHOLE_ARRAY); } } // Формируем массив для хранения личинок S_AO_Agent larvae []; ArrayResize (larvae, totalReefSize * 2); // Выделяем с запасом int larvaCount = 0; // Этап 1: Broadcast Spawning (внешнее половое размножение) BroadcastSpawning (larvae, larvaCount); // Этап 2: Brooding (внутреннее половое размножение) Brooding (larvae, larvaCount); // Вычисляем функцию приспособленности для каждой личинки // (будет выполнено в внешнем коде в FuncTests) // Этап 3: Оседание личинок for (int i = 0; i < larvaCount; i++) { LarvaSettling (larvae [i]); } // Этап 4: Бесполое размножение AsexualReproduction (); // Этап 5: Вымирание Depredation (); } //——————————————————————————————————————————————————————————————————————————————
Метод "LarvaSettling" моделирует процесс заселения личинки на рифе. Он пытается найти подходящее место для личинки и, либо заселяет её на свободное место, либо заменяет существующий, но менее приспособленный коралл. При попытке заселения, личинка пытается заселиться "attemptsNum" раз. На каждой попытке выбирается случайная позиция на рифе. Если выбранная позиция свободна (не занята кораллом), метод ищет свободный индекс в массиве агентов "a []", если свободный индекс найден, личинка копирует своё решение (координаты "c []" и приспособленность "f") в соответствующую ячейку массива агентов.
Информация о том, что позиция на рифе теперь занята, обновляется, и метод возвращает индекс успешно заселенной позиции "pos". Если выбранная позиция занята, метод сравнивает приспособленность (fitness) личинки с приспособленностью текущего коралла на этой позиции. Если личинка лучше, то заменяет существующий коралл, копируя свои параметры в его ячейку в массиве агентов, и метод возвращает индекс "pos" позиции, на которой произошла замена. Если после всех попыток личинка не смогла заселиться (ни на свободное место, ни заменив существующий коралл), метод возвращает -1.
//—————————————————————————————————————————————————————————————————————————————— int C_AO_CRO::LarvaSettling (S_AO_Agent &larva) { // Пытаемся заселить личинку attemptsNum раз for (int attempt = 0; attempt < attemptsNum; attempt++) { // Выбираем случайную позицию в рифе int pos = (int)MathFloor (u.RNDfromCI (0, totalReefSize)); // Проверяем, что позиция находится в пределах массива if (pos < 0 || pos >= totalReefSize) continue; // Если позиция свободна, заселяем личинку if (!occupied [pos]) { // Ищем свободный индекс в массиве агентов int newIndex = -1; for (int i = 0; i < popSize; i++) { bool used = false; for (int j = 0; j < totalReefSize; j++) { if (reefIndices [j] == i) { used = true; break; } } if (!used) { newIndex = i; break; } } if (newIndex != -1) { // Копируем решение личинки ArrayCopy (a [newIndex].c, larva.c, 0, 0, WHOLE_ARRAY); a [newIndex].f = larva.f; // Обновляем информацию о рифе occupied [pos] = true; reefIndices [pos] = newIndex; return pos; } } // Если позиция занята, проверяем, лучше ли личинка текущего коралла else if (occupied [pos] && reefIndices [pos] >= 0 && reefIndices [pos] < popSize && larva.f > a [reefIndices [pos]].f) { // Личинка вытесняет существующий коралл ArrayCopy (a [reefIndices [pos]].c, larva.c, 0, 0, WHOLE_ARRAY); a [reefIndices [pos]].f = larva.f; return pos; } } // Если личинке не удалось заселиться, возвращаем -1 return -1; } //——————————————————————————————————————————————————————————————————————————————
Метод "BroadcastSpawning" моделирует внешнее размножение кораллов путем нереста. Он выполняет следующие основные шаги: находит индексы всех занятых кораллами мест на рифе, определяет количество кораллов, участвующих в нересте, основываясь на параметре "Fb" (Brooding Fraction) — доле кораллов, участвующих во внешнем размножении, перемешивает индексы занятых кораллов и затем выбирает пары для нереста. Создание личинок путем скрещивания: для каждой пары кораллов создается новая личинка, координаты личинки вычисляются, как среднее значение координат родителей с добавлением небольшой случайной мутации. Этот процесс скрещивания (crossover) стремится объединить лучшие черты родителей, созданные личинки добавляются в массив "larvae".
Ключевые моменты:
- "Fb" здесь отвечает за долю кораллов во внешнем размножении (нересте), в отличие от "Brooding", где отвечает за долю кораллов, занимающихся внутренним вынашиванием.
- Скрещивание и мутация усиливают генетическое разнообразие популяции.
- Цель метода — создание новых личинок, полученных от комбинации генов родительских кораллов, для дальнейшей колонизации рифа. Метод предполагает парное скрещивание.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CRO::BroadcastSpawning (S_AO_Agent &larvae [], int &larvaCount) { // Находим все занятые позиции int occupiedIndices []; int occupiedCount = 0; for (int i = 0; i < totalReefSize; i++) { if (occupied [i]) { ArrayResize (occupiedIndices, occupiedCount + 1); occupiedIndices [occupiedCount] = i; occupiedCount++; } } // Проверка на случай, если нет занятых позиций if (occupiedCount == 0) return; // Выбираем долю Fb для внешнего размножения int broadcastCount = (int)MathRound (Fb * occupiedCount); if (broadcastCount <= 0) broadcastCount = 1; // Минимум один коралл if (broadcastCount > occupiedCount) broadcastCount = occupiedCount; // Перемешиваем индексы for (int i = 0; i < occupiedCount; i++) { // Фиксируем проблему выхода за пределы массива int j = (int)MathFloor (u.RNDfromCI (0, occupiedCount)); // Гарантируем, что j в пределах массива if (j >= 0 && j < occupiedCount && i < occupiedCount) { int temp = occupiedIndices [i]; occupiedIndices [i] = occupiedIndices [j]; occupiedIndices [j] = temp; } } // Образуем пары и создаем потомство for (int i = 0; i < broadcastCount - 1; i += 2) { if (i + 1 < broadcastCount) // Проверяем, что есть второй родитель { int idx1 = reefIndices [occupiedIndices [i]]; int idx2 = reefIndices [occupiedIndices [i + 1]]; if (idx1 >= 0 && idx1 < popSize && idx2 >= 0 && idx2 < popSize) { // Инициализируем личинку larvae [larvaCount].Init (coords); // Создаем новую личинку как результат скрещивания for (int c = 0; c < coords; c++) { // Простой метод скрещивания: среднее значение координат родителей с небольшой мутацией double value = (a [idx1].c [c] + a [idx2].c [c]) / 2.0 + u.RNDfromCI (-0.1, 0.1) * (rangeMax [c] - rangeMin [c]); larvae [larvaCount].c [c] = u.SeInDiSp (value, rangeMin [c], rangeMax [c], rangeStep [c]); } // Увеличиваем счетчик личинок larvaCount++; } } } } //——————————————————————————————————————————————————————————————————————————————
Метод "Brooding" имитирует процесс внутреннего вынашивания личинок у кораллов в CRO и выполняет следующие шаги:
- определяет, какие места на рифе заняты кораллами, и сохраняет индексы этих позиций.
- рассчитывает, сколько кораллов будут участвовать в вынашивании личинок, используя параметр "Fb" (Brooding Fraction). Для случайного выбора кораллов, участвующих в размножении, индексы занятых позиций перемешиваются.
- создает и мутирует личинок: для каждого выбранного коралла создается личинка. Личинка инициализируется и мутирует: её координаты немного отклоняются от координат родительского коралла случайным образом. Мутировавшие личинки добавляются в массив "larvae".
Ключевые моменты:
- "Fb" определяет долю кораллов, НЕ участвующих в бесполом размножении (то есть, участвующих во внутреннем вынашивании).
- Мутация обеспечивает разнообразие генов в популяции личинок.
- Цель — создание новых, потенциально лучших особей, которые будут конкурировать за места на рифе.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CRO::Brooding (S_AO_Agent &larvae [], int &larvaCount) { // Находим все занятые позиции int occupiedIndices []; int occupiedCount = 0; for (int i = 0; i < totalReefSize; i++) { if (occupied [i]) { ArrayResize (occupiedIndices, occupiedCount + 1); occupiedIndices [occupiedCount] = i; occupiedCount++; } } // Проверка на случай, если нет занятых позиций if (occupiedCount == 0) return; // Количество кораллов для внутреннего размножения int broodingCount = (int)MathRound ((1.0 - Fb) * occupiedCount); if (broodingCount <= 0) broodingCount = 1; // Минимум один коралл if (broodingCount > occupiedCount) broodingCount = occupiedCount; // Перемешиваем индексы for (int i = 0; i < occupiedCount; i++) { // Фиксируем проблему выхода за пределы массива int j = (int)MathFloor (u.RNDfromCI (0, occupiedCount)); // Гарантируем, что j в пределах массива if (j >= 0 && j < occupiedCount && i < occupiedCount) { int temp = occupiedIndices [i]; occupiedIndices [i] = occupiedIndices [j]; occupiedIndices [j] = temp; } } // Для каждого выбранного коралла создаем мутированную копию for (int i = 0; i < broodingCount; i++) { if (i < occupiedCount) // Проверка на выход за границы { int idx = reefIndices [occupiedIndices [i]]; if (idx >= 0 && idx < popSize) { // Инициализируем личинку larvae [larvaCount].Init (coords); // Создаем новую личинку как мутацию исходного коралла for (int c = 0; c < coords; c++) { // Мутация: добавляем небольшое случайное отклонение double value = a [idx].c [c] + u.RNDfromCI (-0.2, 0.2) * (rangeMax [c] - rangeMin [c]); larvae [larvaCount].c [c] = u.SeInDiSp (value, rangeMin [c], rangeMax [c], rangeStep [c]); } // Увеличиваем счетчик личинок larvaCount++; } } } } //——————————————————————————————————————————————————————————————————————————————
Метод "AsexualReproduction" моделирует бесполое размножение кораллов путем почкования. Метод выполняет следующие шаги: находит индексы всех занятых кораллами мест на рифе, сортирует индексы занятых позиций в порядке убывания приспособленности, то есть сначала идут позиции с самыми приспособленными кораллами. На основе параметра "Fa" (Fraction for Asexual reproduction), который задает долю кораллов, участвующих в бесполом размножении. Определяется количество лучших кораллов, которые будут производить клоны. Создание и заселение клонов: для каждого выбранного коралла создается точная копия (клон) — личинка с такими же координатами и приспособленностью. Вызывается метод "LarvaSettling" для попытки заселения клона на рифе.
Ключевые моменты:
- Бесполое размножение позволяет наиболее приспособленным кораллам быстро распространять свои гены.
- Параметр "Fa" контролирует интенсивность бесполого размножения.
- Использование "LarvaSettling" для заселения клонов означает, что клоны должны конкурировать за место на рифе так же, как и личинки, полученные половым путем.
- Метод клонирования, в данном случае, — это точная копия родителя БЕЗ мутаций. Мутации происходят только при половом размножении.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CRO::AsexualReproduction () { // Находим все занятые позиции и их индексы int occupiedIndices []; int occupiedCount = 0; for (int i = 0; i < totalReefSize; i++) { if (occupied [i]) { ArrayResize (occupiedIndices, occupiedCount + 1); occupiedIndices [occupiedCount] = i; occupiedCount++; } } // Если нет занятых позиций, выходим if (occupiedCount == 0) return; // Сортируем индексы по приспособленности SortAgentsByFitness (occupiedIndices, occupiedCount); // Выбираем лучшие Fa% кораллов для бесполого размножения int budCount = (int)MathRound (Fa * occupiedCount); if (budCount <= 0) budCount = 1; // Минимум один коралл if (budCount > occupiedCount) budCount = occupiedCount; // Для каждого выбранного коралла создаем клон и пытаемся заселить его for (int i = 0; i < budCount; i++) { if (i < occupiedCount) // Проверка на выход за границы { int idx = reefIndices [occupiedIndices [i]]; if (idx >= 0 && idx < popSize) { // Создаем новую личинку как точную копию исходного коралла S_AO_Agent clone; clone.Init (coords); ArrayCopy (clone.c, a [idx].c, 0, 0, WHOLE_ARRAY); clone.f = a [idx].f; // Пытаемся заселить клон LarvaSettling (clone); } } } } //——————————————————————————————————————————————————————————————————————————————
Метод "Depredation" моделирует процесс вымирания кораллов из-за хищничества или других негативных факторов (например, загрязнение). В данном случае уничтожение применяется с вероятностью "Pd". Если случайное число меньше "Pd", то процесс уничтожения выполняется. Поиск занятых позиций определят индексы всех позиций рифа, занятых кораллами. Индексы занятых позиций сортируются по приспособленности кораллов (fitness).
Массив отсортированных индексов переворачивается, чтобы в начале массива оказались индексы наименее приспособленных кораллов. Определяется количество кораллов, которые будут удалены, на основе параметра "Fd" (Fraction for Depredation). Это значение округляется до целого числа. Удаляется указанное количество наименее приспособленных кораллов. Далее происходит очистка рифа: для каждой позиции, намеченной для удаления: соответствующая ячейка в массиве "occupied" устанавливается в "false", показывая, что позиция теперь свободна. Соответствующая ячейка в массиве "reefIndices" устанавливается в -1, указывая на отсутствие коралла на этой позиции.
//—————————————————————————————————————————————————————————————————————————————— oid C_AO_CRO::Depredation() { // Применяем уничтожение с вероятностью Pd if (u.RNDfromCI(0, 1) < Pd) { // Находим все занятые позиции и их индексы int occupiedIndices[]; int occupiedCount = 0; for (int i = 0; i < totalReefSize; i++) { if (occupied[i]) { ArrayResize(occupiedIndices, occupiedCount + 1); occupiedIndices[occupiedCount] = i; occupiedCount++; } } // Если нет занятых позиций, выходим if (occupiedCount == 0) return; // Сортируем индексы по приспособленности SortAgentsByFitness(occupiedIndices, occupiedCount); // Переворачиваем массив, чтобы худшие были первыми for (int i = 0; i < occupiedCount / 2; i++) { if(i < occupiedCount && (occupiedCount - 1 - i) < occupiedCount) // Проверка на выход за границы { int temp = occupiedIndices[i]; occupiedIndices[i] = occupiedIndices[occupiedCount - 1 - i]; occupiedIndices[occupiedCount - 1 - i] = temp; } } // Удаляем худшие Fd% кораллов int removeCount = (int)MathRound(Fd * occupiedCount); if (removeCount <= 0) removeCount = 1; // Минимум один коралл if (removeCount > occupiedCount) removeCount = occupiedCount; // Защита от переполнения for (int i = 0; i < removeCount; i++) { if(i < occupiedCount) // Проверка на выход за границы { int pos = occupiedIndices[i]; if(pos >= 0 && pos < totalReefSize) // Дополнительная проверка { occupied[pos] = false; reefIndices[pos] = -1; } } } } } //——————————————————————————————————————————————————————————————————————————————
Метод "GetReefCoordIndex" преобразует координаты рифа (строка и столбец) в одномерный индекс и принимает строку "row" и столбец "col" в качестве входных данных, возвращает соответствующий индекс в массиве, представляющем риф. Сначала метод проверяет, не выходят ли переданные координаты за границы рифа. В противном случае он вычисляет индекс, используя формулу (row * reefCols + col, где "reefCols" - это количество столбцов в рифе). Этот метод используется для доступа к элементам в массивах, представляющих риф.
//—————————————————————————————————————————————————————————————————————————————— int C_AO_CRO::GetReefCoordIndex (int row, int col) { // Проверка на выход за границы if (row < 0 || row >= reefRows || col < 0 || col >= reefCols) return -1; // Переводим двухмерную позицию в одномерный индекс return row * reefCols + col; } //——————————————————————————————————————————————————————————————————————————————
Метод "SortAgentsByFitness" сортирует массив индексов "indices" кораллов "count" элементов по убыванию их приспособленности (fitness), используя алгоритм пузырьковой сортировки, которая производится на основе значений приспособленности, хранящихся в массиве "a", доступ к которому осуществляется через массив "reefIndices". Таким образом, после работы метода "indices" содержит индексы кораллов, упорядоченные от наиболее приспособленного к наименее приспособленному. Дополнительные проверки включены для предотвращения выхода за границы массивов.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CRO::SortAgentsByFitness (int &indices [], int &count) { // Проверка на пустой массив if (count <= 0) return; // Сортировка пузырьком по убыванию приспособленности for (int i = 0; i < count - 1; i++) { for (int j = 0; j < count - i - 1; j++) { if (j + 1 < count) // Проверка, чтобы j+1 не выходил за пределы { int idx1 = reefIndices [indices [j]]; int idx2 = reefIndices [indices [j + 1]]; if (idx1 >= 0 && idx1 < popSize && idx2 >= 0 && idx2 < popSize) // Проверка индексов { if (a [idx1].f < a [idx2].f) { int temp = indices [j]; indices [j] = indices [j + 1]; indices [j + 1] = temp; } } } } } } //——————————————————————————————————————————————————————————————————————————————
Мы закончили приготовление алгоритма, описали в коде все многочисленные методы для его работы, теперь можем приступить непосредственно к тестированию.
Результаты тестов
После проведенных тестов видно, что алгоритм CRO работает достаточно слабо и необходимо пересмотреть какие-то методы оригинального подхода.CRO|Coral Reef Optimization|50.0|5.0|5.0|0.4|0.9|0.1|0.1|0.01|3.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.365266682511984
25 Hilly's; Func runs: 10000; result: 0.270828009448956
500 Hilly's; Func runs: 10000; result: 0.2504192846772352
=============================
5 Forest's; Func runs: 10000; result: 0.23618879234608753
25 Forest's; Func runs: 10000; result: 0.19453106526100442
500 Forest's; Func runs: 10000; result: 0.1679109693993047
=============================
5 Megacity's; Func runs: 10000; result: 0.13076923076923075
25 Megacity's; Func runs: 10000; result: 0.11138461538461542
500 Megacity's; Func runs: 10000; result: 0.09366153846153921
=============================
All score: 1.82096 (20.23%)
Прежде всего, на что я обратил внимание в алгоритме CRO, это метод уничтожения. Его необходимо модифицировать, чтобы улучить поиск, будем заменять худшие кораллы на рифе новыми, которые генерируются в окрестности лучших кораллов(решений), тем самым продвигая поиск в направлении более перспективных областей. Определим количество лучших "eliteCount" и худших "removeCount" кораллов.
Замена худших решений: для каждой "жертвы" выбирается "элитный" коралл, и генерируется новый коралл в окрестности этого "элитного" коралла. В улучшенном механизме уничтожения применим обратное степенное распределение с показателем 10 (где power = 0.1) для генерации отклонений от лучшего решения. Это распределение характеризуется тем, что большинство новых решений генерируются в непосредственной близости от лучшего, но с небольшой вероятностью могут возникать значительные отклонения, что обеспечивает баланс между локальным поиском (эксплуатацией) и глобальным исследованием пространства решений. Новые координаты ограничены допустимым диапазоном. Освободившаяся позиция на рифе затем заселяется новым кораллом.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CRO::Depredation () { // Применяем уничтожение с вероятностью Pd if (u.RNDfromCI (0, 1) < Pd) { // Находим все занятые позиции и их индексы int occupiedIndices []; int occupiedCount = 0; for (int i = 0; i < totalReefSize; i++) { if (occupied [i]) { ArrayResize (occupiedIndices, occupiedCount + 1); occupiedIndices [occupiedCount] = i; occupiedCount++; } } // Если нет занятых позиций, выходим if (occupiedCount == 0) return; // Сортируем индексы по приспособленности (от лучших к худшим) SortAgentsByFitness (occupiedIndices, occupiedCount); // Определяем количество лучших решений, используемых для генерации новых int eliteCount = (int)MathRound (0.1 * occupiedCount); // Используем 10% лучших if (eliteCount <= 0) eliteCount = 1; // Минимум одно элитное решение if (eliteCount > occupiedCount) eliteCount = occupiedCount; // Определяем количество худших решений для замены int removeCount = (int)MathRound (Fd * occupiedCount); if (removeCount <= 0) removeCount = 1; // Минимум одно решение заменяем if (removeCount > occupiedCount - eliteCount) removeCount = occupiedCount - eliteCount; // Не удаляем элитные решения // Удаляем худшие решения и заменяем их новыми в окрестности лучших for (int i = 0; i < removeCount; i++) { // Индекс удаляемого решения (с конца отсортированного массива) int removeIndex = occupiedCount - 1 - i; if (removeIndex < 0 || removeIndex >= occupiedCount) continue; int posToRemove = occupiedIndices [removeIndex]; if (posToRemove < 0 || posToRemove >= totalReefSize) continue; // Выбираем одно из элитных решений double power = 0.1; // Параметр степенного распределения double r = u.RNDfromCI (0, 1); int eliteIdx = (int)(eliteCount); if (eliteIdx >= eliteCount) eliteIdx = eliteCount - 1; int posBest = occupiedIndices [eliteIdx]; if (posBest < 0 || posBest >= totalReefSize) continue; int bestAgentIdx = reefIndices [posBest]; if (bestAgentIdx < 0 || bestAgentIdx >= popSize) continue; // Освобождаем позицию для нового решения occupied [posToRemove] = false; // Генерируем новое решение в окрестности выбранного элитного решения int newAgentIdx = reefIndices [posToRemove]; // Используем тот же индекс агента if (newAgentIdx >= 0 && newAgentIdx < popSize) { // Генерация через степенное распределение вокруг лучшего решения for (int c = 0; c < coords; c++) { // Определяем радиус поиска (можно адаптировать в зависимости от прогресса) double radius = 0.7 * (rangeMax [c] - rangeMin [c]); // 10% от диапазона // Генерируем значение по степенному закону double sign = u.RNDfromCI (0, 1) < 0.5 ? -1.0 : 1.0; // Случайный знак double deviation = sign * radius * MathPow (u.RNDfromCI (0, 1), 1.0 / power); // Новое значение в окрестности лучшего double newValue = a [bestAgentIdx].c [c] + deviation; // Ограничиваем значение в допустимом диапазоне a [newAgentIdx].c [c] = u.SeInDiSp (newValue, rangeMin [c], rangeMax [c], rangeStep [c]); } // Заселяем новое решение в риф occupied [posToRemove] = true; reefIndices [posToRemove] = newAgentIdx; } } } } //——————————————————————————————————————————————————————————————————————————————
Теперь, после внесенных изменений, протестируем алгоритм CROm. Как можно заметить, из результатов ниже, алгоритм намного улучшил показатели.
CROm|Coral Reef Optimization M|50.0|20.0|20.0|0.2|0.99|0.01|0.8|0.9|20.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.7851210159578113
25 Hilly's; Func runs: 10000; result: 0.4603296933002806
500 Hilly's; Func runs: 10000; result: 0.25958379129490083
=============================
5 Forest's; Func runs: 10000; result: 0.8668751980437325
25 Forest's; Func runs: 10000; result: 0.3529695710837671
500 Forest's; Func runs: 10000; result: 0.16267582083006701
=============================
5 Megacity's; Func runs: 10000; result: 0.6323076923076923
25 Megacity's; Func runs: 10000; result: 0.2673846153846154
500 Megacity's; Func runs: 10000; result: 0.10733846153846247
=============================
All score: 3.89459 (43.27%)
Визуализация алгоритма особенным не выделяется, немного труднее алгоритму справляться с дискретными задачами на тестовой функции "Megacity".
CROm на тестовой функции Hilly
CROm на тестовой функции Forest
CROm на тестовой функции Megacity
По результатам тестирования алгоритм CROm находится на 42 месте рейтинговой таблицы популяционных алгоритмов оптимизации.
| № | 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 | TETA | time evolution travel algorithm (joo) | 0,91362 | 0,82349 | 0,31990 | 2,05701 | 0,97096 | 0,89532 | 0,29324 | 2,15952 | 0,73462 | 0,68569 | 0,16021 | 1,58052 | 5,797 | 64,41 |
| 7 | 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 |
| 8 | BOAm | billiards optimization algorithm M | 0,95757 | 0,82599 | 0,25235 | 2,03590 | 1,00000 | 0,90036 | 0,30502 | 2,20538 | 0,73538 | 0,52523 | 0,09563 | 1,35625 | 5,598 | 62,19 |
| 9 | 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 |
| 10 | 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 |
| 11 | 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 |
| 12 | 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 |
| 13 | DA | dialectical algorithm | 0,86183 | 0,70033 | 0,33724 | 1,89940 | 0,98163 | 0,72772 | 0,28718 | 1,99653 | 0,70308 | 0,45292 | 0,16367 | 1,31967 | 5,216 | 57,95 |
| 14 | 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 |
| 15 | 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 |
| 16 | RFO | royal flush optimization (joo) | 0,83361 | 0,73742 | 0,34629 | 1,91733 | 0,89424 | 0,73824 | 0,24098 | 1,87346 | 0,63154 | 0,50292 | 0,16421 | 1,29867 | 5,089 | 56,55 |
| 17 | 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 |
| 18 | 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 |
| 19 | 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 |
| 20 | SRA | successful restaurateur algorithm (joo) | 0,96883 | 0,63455 | 0,29217 | 1,89555 | 0,94637 | 0,55506 | 0,19124 | 1,69267 | 0,74923 | 0,44031 | 0,12526 | 1,31480 | 4,903 | 54,48 |
| 21 | 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 |
| 22 | BIO | blood inheritance optimization (joo) | 0,81568 | 0,65336 | 0,30877 | 1,77781 | 0,89937 | 0,65319 | 0,21760 | 1,77016 | 0,67846 | 0,47631 | 0,13902 | 1,29378 | 4,842 | 53,80 |
| 23 | 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 |
| 24 | 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 |
| 25 | 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 |
| 26 | 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 |
| 27 | 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 |
| 28 | (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 |
| 29 | 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 |
| 30 | 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 |
| 31 | 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 |
| 32 | 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 |
| 33 | 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 |
| 34 | 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 |
| 35 | 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 |
| 36 | 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 |
| 37 | 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 |
| 38 | 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 |
| 39 | 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 |
| 40 | CGO | chaos game optimization | 0,57256 | 0,37158 | 0,32018 | 1,26432 | 0,61176 | 0,61931 | 0,62161 | 1,85267 | 0,37538 | 0,21923 | 0,19028 | 0,78490 | 3,902 | 43,35 |
| 41 | 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 |
| 42 | CROm | coral reefs optimization M | 0,78512 | 0,46032 | 0,25958 | 1,50502 | 0,86688 | 0,35297 | 0,16267 | 1,38252 | 0,63231 | 0,26738 | 0,10734 | 1,00703 | 3,895 | 43,27 |
| 43 | CFO | central force optimization | 0,60961 | 0,54958 | 0,27831 | 1,43750 | 0,63418 | 0,46833 | 0,22541 | 1,32792 | 0,57231 | 0,23477 | 0,09586 | 0,90294 | 3,668 | 40,76 |
| 44 | 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 |
| 45 | 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 |
| RW | neuroboids optimization algorithm 2(joo) | 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 | |
Выводы
Живые коралловые рифы представляют собой тонко настроенную систему, где непрерывно поддерживается баланс между стабильностью и изменчивостью, между сохранением проверенных стратегий выживания и экспериментированием с новыми. Модифицированный механизм вымирания с генерацией новых решений в окрестности лучших имитирует естественный процесс экологического успеха в коралловых рифах.
В природе, после гибели некоторых колоний, на освободившихся участках рифа появляются не случайные виды, а те, которые наиболее успешно адаптировались к локальным условиям среды. Более того, выживаемость новых колоний выше в зонах, окружающих успешные существующие колонии, что прямо отражено в алгоритме через генерацию новых решений вокруг элитных. Это обеспечивает постоянное исследование перспективных областей пространства поиска и поддерживает неизменный размер популяции.
Внедрение обратного степенного распределения (с показателем 10, где power = 0.1) позволяет генерировать отклонения от лучшего решения. Такое распределение концентрирует большинство новых решений близко к лучшему, с редкими значительными отклонениями, что обеспечивает оптимальный баланс между локальной эксплуатацией и глобальным исследованием.
Расширение радиуса поиска до 70% от допустимого диапазона позволяет алгоритму исследовать более широкие области пространства решений.
Использование только лучших решений (элиты) в качестве базы для генерации новых решений ускоряет сходимость к оптимальным областям и повышает качество получаемых решений, а разнообразные операторы, моделирующие ключевые аспекты эволюции кораллов: внешнее и внутреннее размножение, оседание личинок и бесполое размножение могут быть задействованы при разработке других популяционных методов оптимизации.
Рисунок 2. Цветовая градация алгоритмов по соответствующим тестам
Рисунок 3. Гистограмма результатов тестирования алгоритмов (по шкале от 0 до 100, чем больше, тем лучше, где 100 — максимально возможный теоретический результат, в архиве скрипт для расчета рейтинговой таблицы)
Плюсы и минусы алгоритма CROm:
Плюсы:
- Интересная идея.
- Перспективная разработка.
- Стабильные результаты.
Минусы:
- Более слабые результаты на дискретных функциях.
- Большое количество внешних параметров.
К статье прикреплён архив с актуальными версиями кодов алгоритмов. Автор статьи не несёт ответственности за абсолютную точность в описании канонических алгоритмов, во многие из них были внесены изменения для улучшения поисковых возможностей. Выводы и суждения, представленные в статьях, основываются на результатах проведённых экспериментов.
Программы, используемые в статье
| # | Имя | Тип | Описание |
|---|---|---|---|
| 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_CROm.mq5 | Скрипт | Испытательный стенд для CROm |
Как опередить любой рынок (Часть IV): Индексы волатильности евро и золота CBOE
Торговля по алгоритму: ИИ и его путь к золотым вершинам
Создание торговой панели администратора на MQL5 (Часть III): Улучшение графического интерфейса пользователя (GUI) с помощью визуального оформления (I)
Определение перекупленности и перепроданности по теории хаоса
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Вы принимаете политику сайта и условия использования