Алгоритм эволюции элитных кристаллов — Elite Crystal Evolution Algorithm (CEO-inspired): Теория
275
0
Содержание
Введение
Данная работа представляет адаптацию алгоритма Crystal Energy Optimizer (CEO) для задач непрерывной оптимизации. Алгоритм основан на физическом процессе замерзания озера, моделируя поведение кристаллов льда при переходе воды из жидкого состояния в твердое. Оригинальный CEO разработан для комбинаторных задач (TSP), где используется граф связей между кристаллами и представлен публикацией в 2016 году.
Elite Crystal Evolution Algorithm (ECEA) — это мой авторский популяционный алгоритм оптимизации, вдохновлённый процессом кристаллизации воды при замерзании озера, идеей реализации алгоритма CEO. Представьте себе озеро зимой: когда температура падает, вода начинает замерзать, образуя кристаллы льда. Лучшие кристаллы (те, что находятся в оптимальных условиях) становятся "замёрзшими" и стабильными, в то время как остальные продолжают двигаться и искать лучшие позиции. Эта природная метафора легла в основу нашего алгоритма, адаптированного для решения задач непрерывной оптимизации в многомерном пространстве.
Реализация алгоритма
Алгоритм ECEA работает с популяцией "кристаллов" — точек в пространстве поиска, каждая из которых представляет потенциальное решение задачи. В начале работы все кристаллы размещаются случайным образом по всему пространству поиска. После вычисления качества каждого решения (фитнеса), алгоритм разделяет популяцию на две группы: элитные кристаллы (лучшие десять решений) и обычные кристаллы (остальные сорок). Это разделение динамическое — на каждой итерации статус кристалла может измениться в зависимости от его текущего качества.
Элитные кристаллы представляют собой аналог "замёрзших" кристаллов из оригинальной природной метафоры. Они уже нашли хорошие области в пространстве поиска и теперь занимаются детальным локальным исследованием своей окрестности, совершая небольшие случайные шаги вокруг текущей позиции. Размер этих шагов постепенно уменьшается по мере прогресса алгоритма — вначале элитные кристаллы могут исследовать более широкую область, но с каждой итерацией их движения становятся всё более осторожными и точными, что позволяет находить более качественные решения в уже обнаруженных перспективных зонах.
Обычные неэлитные кристаллы работают совершенно иначе. Они представляют "незамёрзшие" частицы, которые всё ещё находятся в активном поиске лучших областей пространства. Для каждого такого кристалла на каждой итерации случайным образом выбирается одна из трёх стратегий движения для обеспечения баланса между исследованием новых областей и использованием уже найденной информации.
Первая стратегия (срабатывает в 40% случаев) заставляет кристалл двигаться к глобально лучшему найденному решению — это аналог притяжения к центру озера, где условия наиболее благоприятны. Сила этого притяжения адаптивна: в начале работы алгоритма она составляет около 30% от расстояния до лучшего решения, но по мере прогресса увеличивается до 70%, что усиливает эксплуатацию найденных хороших областей.
Вторая стратегия (30% случаев) реализует движение к ближайшему элитному кристаллу и одновременно к центру масс всех элитных кристаллов. Это имитирует влияние уже "замёрзших" кристаллов на незамёрзшие — представьте, что замёрзшие участки озера излучают холод, притягивая к себе окружающие молекулы воды. Кристалл вычисляет, где находится ближайший к нему элитный "сосед", а также определяет центр масс всей элитной группы (средняя точка между всеми элитными кристаллами), после чего совершает шаг, учитывающий оба этих направления с весами 30 и 20 процентов соответственно, модулированными случайными коэффициентами для внесения разнообразия.
Третья стратегия (оставшиеся 30% случаев) представляет собой исследовательское движение, аналог броуновского движения молекул в жидкой фазе. Здесь кристалл совершает случайный шаг, причём с вероятностью 70% это небольшой шаг (10% от размера пространства поиска, масштабированный текущим коэффициентом исследования), а с вероятностью 30% — большой прыжок (пятьдесят процентов от размера пространства). Комбинация маленьких и больших шагов позволяет одновременно исследовать локальные области и совершать дальние прыжки для обнаружения новых перспективных зон.
Важным механизмом алгоритма является эффект "ветра" (Wind Effect), который срабатывает случайным образом с вероятностью 10% на каждой итерации. Этот механизм вдохновлён природным явлением, когда ветер над замерзающим озером разрушает хрупкие кристаллические структуры и переносит осколки в новые места. В алгоритме ветер находит худший из неэлитных кристаллов (тот, что имеет наихудшее значение фитнеса) и перемещает его в новое место. С вероятностью 50/50 кристалл размещается в окрестности глобально лучшего решения (с разбросом плюс-минус 30% от размера пространства), а в остальных случаях — в полностью случайную точку пространства поиска. Механизм служит для диверсификации популяции, чтобы избежать преждевременной сходимости к локальным экстремумам.
Алгоритм ECEA использует адаптивное управление интенсивностью исследования. Параметр скорости исследования начинается со значения 0.5 (задаётся пользователем) и постепенно уменьшается по мере работы алгоритма. Конкретно, через первые сто итераций параметр уменьшается на 70% от начального значения, что означает переход от активного глобального поиска к более консервативной эксплуатации найденных решений. Эта адаптация происходит плавно и влияет как на размер шагов элитных кристаллов при локальном поиске, так и на амплитуду исследовательских движений обычных кристаллов.
На каждой итерации алгоритм вычисляет центр масс элитной группы — среднюю точку между всеми элитными кристаллами по каждой координате пространства. Эта точка играет роль "центра озера" в природной аналогии и используется как один из аттракторов для движения неэлитных кристаллов. Дополнительно вычисляются радиусы влияния для каждого элитного кристалла, определяемые как половина расстояния до ближайшего другого элитного кристалла.
Процесс работы алгоритма повторяется итеративно: на каждом шаге сначала все кристаллы сортируются по качеству их решений, обновляется элитный статус (лучшие десять получают статус элитных, остальные его теряют), затем вычисляется центр масс элитной группы, после чего для каждого кристалла применяется соответствующая стратегия движения (локальный поиск для элитных или одна из трёх стратегий для обычных), с некоторой вероятностью срабатывает эффект ветра, и наконец вычисляются новые значения фитнеса и обновляются глобально лучшее и худшее найденные решения. Алгоритм продолжает работу до достижения заданного числа итераций.
В итоге, от оригинального алгоритма Crystal Energy Optimizer, разработанного для комбинаторных задач типа задачи коммивояжёра, мы унаследовали несколько ключевых концептуальных идей, адаптировав их для непрерывной оптимизации. Что же мы заменили и чем?
Концепция замёрзших и незамёрзших кристаллов была сохранена в виде разделения популяции на элитные и обычные кристаллы. В оригинале кристаллы физически "замерзали" при достижении определённого энергетического порога, формируя стабильные структуры. Мы заменили физический процесс замерзания на более простой механизм ранжирования по качеству решения — лучшие становятся элитными (аналог замёрзших), остальные остаются в активном поиске (аналог незамёрзших).
Идея центра озера как аттрактора трансформировалась в использование глобально лучшего решения и центра масс элитных кристаллов. В оригинальном CEO центр озера был источником энергии, притягивающим незамёрзшие кристаллы согласно физической формуле теплопередачи обратно пропорционально расстоянию. Мы упростили эту идею, используя прямое направленное движение к лучшему решению с адаптивной силой притяжения, что концептуально похоже, но избегает сложных физических расчётов.
Механизм Wind-Blow был сохранён как метод периодической диверсификации популяции. В оригинальном алгоритме ветер разрывал связи между замёрзшими кристаллами и перемещал выбранные кристаллы в новые позиции. Поскольку в нашей адаптации нет явной структуры связей (графа), мы реализовали ветер как механизм регенерации худших неэлитных кристаллов, помещая их в новые позиции либо около лучшего решения, либо случайно.
Баланс исследования и эксплуатации реализован через три стратегии движения и адаптивные параметры. Оригинальный CEO использовал сложную систему влияний от центра озера, замёрзших кристаллов и ветра, объединённых в формуле суммарного влияния с весовыми коэффициентами лямбда. Мы заменили физические формулы на три концептуально похожие стратегии: движение к лучшему (аналог влияния центра), движение к элитным (аналог влияния замёрзших) и исследовательское движение (аналог случайных возмущений).
Локальный поиск для элитных решений унаследован от поведения замёрзших кристаллов в оригинале. В CEO замёрзшие кристаллы продолжали медленно "расти", совершая микродвижения для улучшения своих позиций. Мы реализовали это через малые случайные шаги вокруг текущих позиций элитных кристаллов с постепенно уменьшающейся амплитудой. Это позволяет тонко настраивать найденные хорошие решения, не теряя их в процессе глобального поиска.
Важно отметить, что мы не сохранили ключевые элементы оригинала, специфичные для комбинаторной оптимизации: структуру связей между кристаллами (граф), формулу влияния замёрзших кристаллов через расстояния до пар связанных соседей, физические формулы теплопередачи, процесс осаждения с выбором оптимальной позиции между двумя замёрзшими соседями, и механизм разрыва и создания связей при замерзании новых кристаллов. Эти элементы имеют смысл для перестановок (TSP), но неприменимы напрямую к непрерывным пространствам, поэтому были заменены на более универсальные операторы движения, сохраняющие концептуальную суть, но адаптированные к геометрии непрерывного многомерного пространства.
Рисунок 1. Блок-схема работы алгоритма ECEA
На изображении выше представлена концепция работы алгоритма ECEA: элитные кристаллы (золотые) с меткой "E", обычные кристаллы (синие), центр масс элитных (красный), три стратегии движения со стрелками и Wind-эффект. Теперь можем приступить к написанию псевдокода алгоритма.
ЭТАП ИНИЦИАЛИЗАЦИИ:
Шаг 1: Создать массив из кристаллов
Шаг 2: Для каждого кристалла выполнить:
- Для каждой координаты пространства поиска:
- сгенерировать случайное число от нуля до единицы
- вычислить позицию как минимальное значение плюс случайное число умножить на диапазон (максимум минус минимум)
- Присвоить кристаллу статус "не элитный"
- Обнулить счётчик стагнации
Шаг 3: Вычислить значение целевой функции (фитнес) для всех кристаллов
Шаг 4: Найти глобально лучшее и глобально худшее решение среди всех кристаллов
Шаг 5: Установить счётчик итераций равным нулю
Шаг 6: Установить счётчик отсутствия улучшений равным нулю
ОСНОВНОЙ ЦИКЛ ОПТИМИЗАЦИИ:
ПОВТОРЯТЬ до достижения критерия останова:
ФАЗА 1: ОБНОВЛЕНИЕ ЭЛИТНОГО СТАТУСА
Шаг 7: Увеличить счётчик итераций на единицу
Шаг 8: Отсортировать все кристаллы по убыванию фитнеса (от лучших к худшим)
Шаг 9: Присвоить элитный статус первым кристаллам после сортировки
Шаг 10: Снять элитный статус с обычных кристаллов
ФАЗА 2: ВЫЧИСЛЕНИЕ ЦЕНТРА МАСС ЭЛИТНЫХ
Шаг 11: Обнулить все координаты центра масс
Шаг 12: Подсчитать количество элитных кристаллов
Шаг 13: Для каждого элитного кристалла:
- Для каждой координаты:
- Добавить значение координаты этого кристалла к соответствующей координате центра масс
Шаг 14: Если найдены элитные кристаллы:
- Для каждой координаты центра масс:
- Разделить накопленную сумму на количество элитных кристаллов
Шаг 15: Если элитных кристаллов не найдено (исключительная ситуация):
- Установить центр масс равным глобально лучшему решению
ФАЗА 3: ВЫЧИСЛЕНИЕ РАДИУСОВ ВЛИЯНИЯ
Шаг 16: Для каждого элитного кристалла выполнить:
- Установить минимальное расстояние до другого элитного в значение "очень большое число"
- Для каждого другого элитного кристалла:
- Если это не тот же самый кристалл:
- Вычислить евклидово расстояние между ними:
- Обнулить сумму квадратов разностей
- Для каждой координаты:
- Вычислить разность координат
- Возвести в квадрат и добавить к сумме
- Взять квадратный корень из суммы
- Если это расстояние меньше текущего минимального:
- Обновить минимальное расстояние
- Вычислить евклидово расстояние между ними:
- Если это не тот же самый кристалл:
- Установить радиус влияния этого кристалла равным половине минимального расстояния
ФАЗА 4: РОСТ КРИСТАЛЛОВ (ОСНОВНОЕ ДВИЖЕНИЕ)
Шаг 17: Вычислить текущий коэффициент исследования:
- Вычислить прогресс как отношение текущей итерации к ста
- Динамический коэффициент исследования вычислить по формуле
Шаг 18: Для каждого кристалла выполнить:
ЕСЛИ кристалл элитный, ТО:
Шаг 18а: Локальный поиск для элитного кристалла:
- Для каждой координаты:
- Вычислить диапазон поиска как максимум минус минимум для этой координаты
- Вычислить размер шага
- Сгенерировать случайное смещение
- Добавить смещение к текущей координате кристалла
Шаг 18б: Выбрать стратегию движения:
- Сгенерировать случайное число от нуля до единицы
Стратегия 1: Движение к глобально лучшему решению
- Вычислить силу притяжения по формуле
- Для каждой координаты:
- Вычислить направление движения как координата лучшего решения минус текущая координата кристалла
- Вычислить величину перемещения как сила притяжения умножить на направление
- Добавить перемещение к текущей координате
Стратегия 2: Движение к кластеру элитных
- Найти ближайший элитный кристалл к текущему:
- Установить минимальное расстояние в "очень большое число"
- Установить индекс ближайшего в "не найден"
- Для каждого кристалла в популяции:
- Если это не текущий кристалл И он элитный:
- Вычислить евклидово расстояние до него
- Если это расстояние меньше минимального:
- Обновить минимальное расстояние и индекс ближайшего
- Если это не текущий кристалл И он элитный:
- Если ближайший элитный найден:
- Для каждой координаты:
- Вычислить направление к ближайшему элитному как его координата минус текущая координата
- Вычислить направление к центру масс как координата центра минус текущая координата
- Сгенерировать первый случайный коэффициент от нуля до единицы
- Сгенерировать второй случайный коэффициент от нуля до единицы
- Вычислить перемещение по формуле
- Добавить перемещение к текущей координате
- Для каждой координаты:
Стратегия 3: Исследовательское движение
- Для каждой координаты:
- Вычислить диапазон как максимум минус минимум для этой координаты
- Сгенерировать случайное число от нуля до единицы
- ЕСЛИ случайное число меньше (семьдесят процентов от тридцати процентов):
- Малое исследование: вычислить перемещение по формуле
- ИНАЧЕ:
- Большое исследование: вычислить перемещение по формуле
- Добавить перемещение к текущей координате
ФАЗА 5: ЭФФЕКТ ВЕТРА (ДИВЕРСИФИКАЦИЯ)
Шаг 19: Сгенерировать случайное число от нуля до единицы
Шаг 20: ЕСЛИ случайное число меньше вероятности ветра, ТО:
Выполнить эффект ветра:
Шаг 20а: Найти худший неэлитный кристалл:
- Установить индекс худшего в "не найден"
- Установить худший фитнес в "очень большое положительное число"
- Для каждого кристалла в популяции:
- Если кристалл НЕ элитный И его фитнес хуже текущего худшего:
- Обновить индекс худшего и значение худшего фитнеса
- Если кристалл НЕ элитный И его фитнес хуже текущего худшего:
Шаг 20б: Если худший неэлитный найден:
- Сгенерировать случайное число от нуля до единицы
- ЕСЛИ случайное число меньше 50 процентов:
- Стратегия регенерации около лучшего:
- Для каждой координаты:
- Вычислить диапазон как максимум минус минимум
- Сгенерировать шум как случайное число по формуле
- Установить координату худшего кристалла равной координате лучшего решения плюс шум
- Для каждой координаты:
- Стратегия регенерации около лучшего:
- ИНАЧЕ:
- Стратегия полностью случайной регенерации:
- Для каждой координаты:
- Сгенерировать случайное число от нуля до единицы
- Установить координату как минимум плюс случайное число умножить на диапазон
- Для каждой координаты:
- Стратегия полностью случайной регенерации:
ФАЗА 6: ОЦЕНКА И ОБНОВЛЕНИЕ
Шаг 21: Вычислить значение целевой функции (фитнес) для всех кристаллов после их перемещения
Шаг 22: Сохранить текущее глобально лучшее значение фитнеса
Шаг 23: Для каждого кристалла выполнить:
- Если текущий фитнес кристалла лучше его персонального лучшего:
- Обновить персональное лучшее значение фитнеса
- Сохранить текущие координаты как персональные лучшие координаты
- Если текущий фитнес кристалла хуже его персонального худшего:
- Обновить персональное худшее значение фитнеса
- Сохранить текущие координаты как персональные худшие координаты
- Если текущий фитнес кристалла лучше глобального лучшего:
- Обновить глобальное лучшее значение фитнеса
- Сохранить координаты этого кристалла как глобально лучшие координаты
- Если текущий фитнес кристалла хуже глобального худшего:
- Обновить глобальное худшее значение фитнеса
- Сохранить координаты этого кристалла как глобально худшие координаты
Шаг 24: Проверить улучшение:
- Если абсолютная разность между новым и сохранённым лучшим фитнесом меньше одной миллионной:
- Увеличить счётчик отсутствия улучшений на единицу
- Иначе:
- Обнулить счётчик отсутствия улучшений
ФАЗА 7: ПРОВЕРКА КРИТЕРИЯ ОСТАНОВА
Шаг 25: Проверить условия останова:
- ЕСЛИ достигнуто максимальное количество итераций ИЛИ
- ЕСЛИ глобально лучшее решение достигло целевого значения ИЛИ
- ЕСЛИ счётчик отсутствия улучшений превысил заданный порог:
- ЗАВЕРШИТЬ цикл и перейти к шагу 26
- ИНАЧЕ:
- ВЕРНУТЬСЯ к шагу 7 (начать новую итерацию)
ЗАВЕРШЕНИЕ АЛГОРИТМА:
Шаг 26: Вернуть глобально лучшее найденное решение:
- Координаты лучшего кристалла
- Значение целевой функции в этой точке
- Количество выполненных итераций
КОНЕЦ АЛГОРИТМА
Переходим к реализации. Перед нами упрощённая структура, предназначенная для представления кристалла, который используется в системе, ориентированной на непрерывную оптимизацию. Назовём эту структуру "S_ECEA_Crystal".
Каждый такой кристалл обладает тремя основными характеристиками:
- isElite — логическое значение (истина или ложь) указывает, является ли данный кристалл элитным
- stagnationCnt — счётчик стагнации
- radius — радиус влияния кристалла
Структура также содержит метод инициализации, названный "Init". При вызове этого метода значение "isElite" устанавливается в "ложь", то есть по умолчанию кристалл не считается элитным. Счётчик стагнации "stagnationCnt" обнуляется, начиная отсчёт с нуля. Радиус влияния "radius" устанавливается в нулевое значение.
//———————————————————————————————————————————————————————————————————— // Упрощённая структура для ECEA (адаптация к непрерывной оптимизации) struct S_ECEA_Crystal { bool isElite; // элитный кристалл int stagnationCnt; // счётчик стагнации double radius; // радиус влияния void Init () { isElite = false; stagnationCnt = 0; radius = 0.0; } }; //————————————————————————————————————————————————————————————————————
Назовём класс "C_AO_ECEA", который будет наследником базового класса "C_AO" и реализует наш алгоритм оптимизации, основанный на эволюции элитных кристаллов. Публичная часть класса устанавливает некоторые параметры алгоритма. Подготавливаем массив "params" для хранения параметров, изменяемых пользователем. Его размер устанавливаем равным 4 и заполняем этот массив.
SetParams () — метод предназначен для установки значений параметров алгоритма на основе данных из массива "params". После установки значений, он выполняет корректировку (валидацию), чтобы все оставалось в допустимых пределах.
Init () — отвечает за первоначальную инициализацию алгоритма. Он принимает диапазоны минимальных и максимальных значений, шаги для параметров и количество эпох.
Moving () — отвечает за основной шаг движения или эволюции популяции в рамках алгоритма.
Revision () — отвечает за пересмотр или ревизию состояния популяции или параметров алгоритма.
Члены данных класса (видимые извне):
- eliteSize — количество элитных элементов.
- explorationRate — коэффициент исследования.
- windProbability — вероятность "ветра".
Приватная часть класса (private):
- crystalData [] — массив, содержащий данные о кристаллах.
- iterationCount — значение, отслеживающее текущий номер итерации.
- noImprovementCount — значение, отражающее количество итераций, в течение которых не было улучшений.
- centerMass [] — массив, хранящий координаты центра масс элитных элементов.
Приватные вспомогательные методы:
- InitializePopulation () — метод для первоначального создания популяции.
- UpdateEliteStatus () — метод для обновления статуса элитных элементов.
- CrystalGrowth () — метод, представляющий рост кристаллов, который является аналогом процесса "осаждения".
- WindEffect () — метод, моделирующий "эффект ветра", что является аналогом "wind-blow" (раздувания ветром).
- MoveTowardsBest () — метод заставляет элемент с индексом "idx" двигаться в сторону лучшего решения с определённой силой.
- MoveTowardsEliteCluster () — метод заставляет элемент с индексом "idx" двигаться в сторону кластера элитных элементов.
- ExploratoryMove () — метод выполняет исследовательское движение для элемента с индексом "idx".
- FindNearestElite () — метод находит ближайший элитный элемент к элементу с индексом "idx".
- CalculateEliteRadii () — метод для вычисления радиусов элитных элементов.
- GetDynamicExplorationRate () — метод для получения динамического (изменяющегося) коэффициента исследования.
//———————————————————————————————————————————————————————————————————— class C_AO_ECEA : public C_AO { public: ~C_AO_ECEA () { } C_AO_ECEA () { ao_name = "ECEA"; ao_desc = "Elite Crystal Evolution Algorithm"; ao_link = "https://www.mql5.com/ru/articles/20052"; popSize = 50; eliteSize = 10; // элитных (аналог замёрзших) explorationRate = 0.5; // баланс исследование/эксплуатация windProbability = 0.1; // вероятность "ветра" на итерацию ArrayResize (params, 4); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "eliteSize"; params [1].val = eliteSize; params [2].name = "explorationRate"; params [2].val = explorationRate; params [3].name = "windProbability"; params [3].val = windProbability; } void SetParams () { popSize = (int)params [0].val; eliteSize = (int)params [1].val; explorationRate = params [2].val; windProbability = params [3].val; if (eliteSize < 2) eliteSize = 2; if (eliteSize > popSize / 2) eliteSize = popSize / 2; if (explorationRate < 0.1) explorationRate = 0.1; if (explorationRate > 0.9) explorationRate = 0.9; if (windProbability < 0.0) windProbability = 0.0; if (windProbability > 0.5) windProbability = 0.5; } bool Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP); void Moving (); void Revision (); //------------------------------------------------------------------ int eliteSize; double explorationRate; double windProbability; private: //--------------------------------------------------------- S_ECEA_Crystal crystalData []; int iterationCount; int noImprovementCount; double centerMass []; // центр масс элитных void InitializePopulation (); void UpdateEliteStatus (); void CrystalGrowth (); // аналог осаждения void WindEffect (); // аналог wind-blow void MoveTowardsBest (int idx, double strength); void MoveTowardsEliteCluster (int idx); void ExploratoryMove (int idx); int FindNearestElite (int idx); void CalculateEliteRadii (); double GetDynamicExplorationRate (); }; //————————————————————————————————————————————————————————————————————
Функция "Init" вызывает базовую функцию инициализации "StandardInit" с предоставленными диапазонами и шагами параметров. Если эта базовая инициализация не удалась, текущая функция также возвращает ложное значение, сигнализируя о невозможности продолжения. Для каждого кристалла в популяции (от 0 до popSize - 1) вызывается его собственный метод инициализации. Если все предыдущие шаги выполнены успешно, функция возвращает истинное значение, показывая, что инициализация завершена корректно.
//———————————————————————————————————————————————————————————————————— bool C_AO_ECEA::Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP) { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //------------------------------------------------------------------ ArrayResize (crystalData, popSize); ArrayResize (centerMass, coords); for (int i = 0; i < popSize; i++) crystalData [i].Init (); iterationCount = 0; noImprovementCount = 0; return true; } //————————————————————————————————————————————————————————————————————
Метод "Moving" вызывается на каждой итерации оптимизации. В начале проверяется флаг "revision". Если "revision" ложен, вызывается метод "InitializePopulation ()" для создания начальной популяции, флаг "revision" устанавливается в истинное значение, и выполнение метода завершается (переходя к следующему шагу в более общем цикле). Счетчик "iterationCount" увеличивается на единицу, отмечая начало новой итерации.
Вычисление центра масс элитных элементов: массив "centerMass", хранящий координаты центра масс, обнуляется. Производится перебор всех элементов популяции (crystalData). Если элемент помечен как элитный, его координаты добавляются к соответствующим элементам массива "centerMass". Подсчитывается общее количество элитных элементов (eliteCount).
Если есть хотя бы один элитный элемент (eliteCount > 0): координаты "centerMass" делятся на количество элитных элементов, чтобы получить средние координаты. Если элитных элементов нет (eliteCount == 0): координаты "centerMass" копируются из "cB". Расчет радиусов влияния элитных: вызывается метод "CalculateEliteRadii ()", он определяет, как далеко простирается влияние каждого элитного элемента на другие элементы популяции.
Основная фаза — рост кристаллов: вызывается метод "CrystalGrowth ()", он реализует ключевую часть алгоритма, где "кристаллы" (элементы популяции) "растут", приближаясь к более качественным решениям.
Периодический эффект ветра: случайным образом с вероятностью, заданной "windProbability" генерируется число. Если сгенерированное число меньше "windProbability", то вызывается метод "WindEffect ()", который вносит некоторый случайный "разброс" или "смещение" в положение элементов, имитируя влияние ветра.Метод "Moving" управляет процессом эволюции популяции, проверяя необходимость инициализации, обновляя информацию о лучших (элитных) элементах, моделируя рост и периодически применяя случайные возмущения.
//———————————————————————————————————————————————————————————————————— void C_AO_ECEA::Moving () { if (!revision) { InitializePopulation (); revision = true; return; } //------------------------------------------------------------------ iterationCount++; // Вычисляем центр масс элитных ArrayInitialize (centerMass, 0.0); int eliteCount = 0; for (int i = 0; i < popSize; i++) { if (crystalData [i].isElite) { for (int c = 0; c < coords; c++) centerMass [c] += a [i].c [c]; eliteCount++; } } if (eliteCount > 0) { for (int c = 0; c < coords; c++) centerMass [c] /= (double)eliteCount; } else { ArrayCopy (centerMass, cB, 0, 0, coords); } // Рассчитываем радиусы влияния элитных CalculateEliteRadii (); // Основная фаза: рост кристаллов CrystalGrowth (); // Периодический эффект ветра if (u.RNDfromCI (0.0, 1.0) < windProbability) { WindEffect (); } } //————————————————————————————————————————————————————————————————————
Начальное создание популяции или генерация случайных начальных решений для алгоритма ECEA. Функция "InitializePopulation" проходит по каждому элементу (кристаллу) в популяции, от первого (индекс 0) до последнего (индекс "popSize - 1") и генерирует значения для каждого из его параметров (координат), от первого (индекс 0) до последнего (индекс coords - 1). Для каждого параметра (координаты "j") генерируется случайное значение в пределах заданного диапазона. Это делается с помощью генератора случайных чисел "u.RNDfromCI".
Сразу после генерации случайного значения, оно "обрабатывается" или "квантуется" с помощью функции "u.SeInDiSp". Это гарантирует, что начальные значения параметров будут соответствовать дискретным и шаговым ограничениям. Таким образом, "InitializePopulation" отвечает за первоначальное заполнение популяции случайными, но допустимыми, решениями, которые послужат отправной точкой для дальнейшей эволюции в алгоритме.
//———————————————————————————————————————————————————————————————————— void C_AO_ECEA::InitializePopulation () { for (int i = 0; i < popSize; i++) { for (int j = 0; j < coords; j++) { a [i].c [j] = u.RNDfromCI (rangeMin [j], rangeMax [j]); a [i].c [j] = u.SeInDiSp (a [i].c [j], rangeMin [j], rangeMax [j], rangeStep [j]); } } } //————————————————————————————————————————————————————————————————————
Метод "UpdateEliteStatus" отвечает за определение и обновление статуса "элитных" элементов в популяции. Метод использует "пузырьковую сортировку" для упорядочивания всей популяции (как самих агентов "a", так и их сопутствующих данных "crystalData") по убыванию приспособленности. Это означает, что элементы с наилучшей приспособленностью окажутся в начале списка. В процессе сортировки, если сравниваемые элементы имеют разную приспособленность, они меняются местами. При этом происходит одновременный обмен как самих агентов (a [j] и a [j+1]), так и их структур данных (crystalData [j] и crystalData [j+1]), чтобы сохранить соответствие между агентом и его характеристиками.
После того как популяция отсортирована по приспособленности, происходит финальное назначение статуса "элитности". Для каждого элемента популяции, начиная с самого лучшего (индекс 0) и до заданного количества лучших (eliteSize), устанавливается флаг "isElite" в истинное значение. Все остальные элементы, чьи индексы больше или равны "eliteSize", помечаются как неэлитные (их флаг "isElite" автоматически становится ложным, если он был истинным до этого, или просто устанавливается в ложный, если это не так).
Таким образом, "UpdateEliteStatus" гарантирует, что после каждого шага в алгоритме, самые лучшие решения (определяемые по функции приспособленности) будут явно помечены как "элитные", что позволит другим частям алгоритма использовать эту информацию для дальнейшей эволюции.
//———————————————————————————————————————————————————————————————————— void C_AO_ECEA::UpdateEliteStatus () { S_AO_Agent temp; S_CEO_Crystal tempData; // Сортируем по фитнесу for (int i = 0; i < popSize - 1; i++) { for (int j = 0; j < popSize - i - 1; j++) { if (a [j].f < a [j + 1].f) { temp = a [j]; a [j] = a [j + 1]; a [j + 1] = temp; tempData = crystalData [j]; crystalData [j] = crystalData [j + 1]; crystalData [j + 1] = tempData; } } } // Обновляем элитный статус for (int i = 0; i < popSize; i++) { crystalData [i].isElite = (i < eliteSize); } } //————————————————————————————————————————————————————————————————————
Процесс "роста кристаллов" является ключевым этапом в алгоритме ECEA. Этот этап определяет, как каждый отдельный элемент (кристалл) в популяции будет эволюционировать, чтобы потенциально найти лучшие решения.
Функция "CrystalGrowth" работает следующим образом: сначала вычисляется переменная "explRate", которая представляет собой "динамическую ставку исследования". Эта ставка меняется в процессе работы алгоритма, делая его более или менее склонным к случайному исследованию.
Метод проходит по всем элементам популяции (popSize). Если элемент является "элитным" (то есть, он входит в число лучших решений, определенных ранее), тогда элитные элементы выполняют локальный поиск. Для каждой характеристики (координаты "c") элитного элемента вычисляется "stepSize" — размер возможного шага, который пропорционален размеру диапазона допустимых значений (rangeMax [c] - rangeMin [c]) и динамической ставке исследования (explRate). Генерируется случайное число "step" в пределах этого "stepSize" (со знаком плюс или минус). К текущему значению характеристики (a [i].c [c]) прибавляется этот случайный шаг.
Полученное значение снова "квантуется" или приводится к допустимому шагу (rangeStep [c]) в пределах диапазона (rangeMin [c], rangeMax [c]), аналогично тому, как это делалось при инициализации. Элитные элементы "исследуют" очень ограниченную область вокруг своего текущего положения, чтобы попытаться найти еще более оптимальное решение в непосредственной близости.
Если элемент не является "элитным": неэлитные элементы используют комбинацию различных стратегий для своего развития, причем выбор стратегии происходит случайным образом. Генерируется случайное число "strategy" от 0.0 до 1.0. В зависимости от значения "strategy" применяются три различные стратегии:
- Движение к лучшему (с вероятностью 40%): используется функция "MoveTowardsBest", которая перемещает неэлитный элемент в направлении лучшего известного решения в популяции. Размер шага зависит от динамической ставки исследования (explRate), делая движение к лучшему более интенсивным, когда исследование менее активно.
- Движение к ближайшему элитному (с вероятностью 30%): используется функция "MoveTowardsEliteCluster". Эта стратегия перемещает неэлитный элемент в сторону "центра" или ближайшего члена группы элитных элементов. Это помогает неэлитным элементам "подтянуться" к уже найденным хорошим областям.
- Исследование (с вероятностью 30%): используется функция "ExploratoryMove". Эта стратегия осуществляет более широкие случайные шаги, чтобы исследовать новые, еще не изученные области пространства решений.
Этот метод имитирует рост и эволюцию популяции, где:
- Элитные элементы действуют как "стабильные, хорошо развитые кристаллы", которые тонко настраивают свои свойства в локальной области.
- Неэлитные элементы используют более разнообразные подходы: они могут стремиться к уже найденным хорошим решениям (элитным), активно искать лучшие места, или же исследовать новые территории, чтобы в будущем стать элитными.
//———————————————————————————————————————————————————————————————————— void C_AO_ECEA::CrystalGrowth () { double explRate = GetDynamicExplorationRate (); for (int i = 0; i < popSize; i++) { if (crystalData [i].isElite) { // Элитные делают локальный поиск for (int c = 0; c < coords; c++) { double range = rangeMax [c] - rangeMin [c]; double stepSize = range * 0.05 * explRate; double step = u.RNDfromCI (-stepSize, stepSize); a [i].c [c] = a [i].c [c] + step; a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } else { // Не-элитные: комбинация стратегий double strategy = u.RNDfromCI (0.0, 1.0); if (strategy < 0.4) { // Движение к лучшему (40%) MoveTowardsBest (i, 0.3 + 0.4 * (1.0 - explRate)); } else if (strategy < 0.7) { // Движение к ближайшему элитному (30%) MoveTowardsEliteCluster (i); } else { // Исследование (30%) ExploratoryMove (i); } } } } //————————————————————————————————————————————————————————————————————
Процедура "MoveTowardsBest" предназначена для перемещения конкретного агента (кристалла) в направлении лучшего решения, известного на данный момент.
Параметры:- idx — это индекс агента в популяции, который будет перемещаться.
- strength — параметр, определяющий "силу" или "амплитуду" перемещения. Чем больше "strength", тем сильнее агент будет стремиться к лучшему решению.
Перемещение по каждой координате:метод проходит по всем характеристикам (координатам "c") агента и для каждой координаты "c" вычисляется "direction". Это разница между лучшим значением этой координаты "cB [c]"(это координата лучшего агента в популяции) и текущим значением этой координаты у перемещаемого агента (a [idx].c [c]), "direction" показывает, в какую сторону нужно двигаться, чтобы приблизиться к лучшему решению.
Вычисляется "move". Это величина шага, на которую агент сместится по данной координате. Этот шаг равен произведению "strength" (силы перемещения) на "direction" (направление к лучшему). Текущее значение координаты агента обновляется путем добавления вычисленного "move". После обновления значения координаты, оно пропускается через функцию "u.SeInDiSp". Эта функция корректирует значение, чтобы оно оставалось в допустимых пределах (от "rangeMin [c]" до "rangeMax [c]") и соответствовало дискретизации шага "rangeStep [c]").
Метод реализует простую, но эффективную стратегию: если агент не является элитным, он получает возможность "подражать" лучшему агенту в популяции. Величина этого "подражания" контролируется параметром "strength". Это помогает слабым агентам быстро перемещаться в перспективные области пространства решений, где уже были найдены хорошие решения.
//———————————————————————————————————————————————————————————————————— void C_AO_ECEA::MoveTowardsBest (int idx, double strength) { for (int c = 0; c < coords; c++) { double direction = cB [c] - a [idx].c [c]; double move = strength * direction; a [idx].c [c] = a [idx].c [c] + move; a [idx].c [c] = u.SeInDiSp (a [idx].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } //————————————————————————————————————————————————————————————————————
Заключение
Мы познакомились с адаптированным для непрерывной оптимизации алгоритмом Elite Crystal Evolution Algorithm (ECEA), основанным на идее кристаллизации из оригинального Crystal Energy Optimizer (CEO). Предложенный подход переносит физическую метафору замерзания озера в контекст эволюционного поиска, сочетая локальное уточнение решений элитными кристаллами с глобальным стохастическим поиском, выполняемым обычными кристаллами.
Благодаря адаптивным стратегиям движения и механизму Wind Effect, обеспечивающему диверсификацию популяции, алгоритм достигает устойчивого баланса между исследованием и эксплуатацией пространства решений. Как видим, ECEA демонстрирует потенциал как универсальный метод непрерывной оптимизации и может быть расширен для гибридных систем, объединяющих эволюционные и машинно-обучающие подходы.
В следующей статье мы продолжим описание специфичных методов алгоритма ECEA, проведем тестирование и сделаем выводы по его работе.
К статье прикреплён архив с актуальными версиями кодов алгоритмов. Автор статьи не несёт ответственности за абсолютную точность в описании канонических алгоритмов, во многие из них были внесены изменения для улучшения поисковых возможностей. Выводы и суждения, представленные в статьях, основываются на результатах проведённых экспериментов.
Программы, используемые в статье
| # | Имя | Тип | Описание |
|---|---|---|---|
| 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_ECEA.mq5 | Скрипт | Испытательный стенд для ECEA |
Предупреждение: все права на данные материалы принадлежат MetaQuotes Ltd. Полная или частичная перепечатка запрещена.
Данная статья написана пользователем сайта и отражает его личную точку зрения. Компания MetaQuotes Ltd не несет ответственности за достоверность представленной информации, а также за возможные последствия использования описанных решений, стратегий или рекомендаций.
Разработка динамического советника на нескольких парах (Часть 4): Корректировка риска на основе волатильности
Нейросети в трейдинге: Рекуррентное моделирование микродвижений рынка (EV-MGRFlowNet)
Моделирование рынка (Часть 11): Сокеты (V)
Быстрая интеграция большой языковой модели и MetaTrader 5 (Часть I): Создаем модель
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Вы принимаете политику сайта и условия использования