Оптимизация сообществом ученых — Community of Scientist Optimization (CoSO): Практика
126
0
Содержание:
Реализация алгоритма
Продолжим описание реализации алгоритма, которое мы начали в первой части статьи, а также представим результаты экспериментального тестирования на специализированных тестовых функциях.
Функция "AssignFunds" описывает механизм распределения доступных "средств" между исследователями в алгоритме CoSO. Эти средства представляют собой возможности для обучения, перемещения или участия в дальнейших процессах, и их распределение влияет на динамику эволюции решений. Функция принимает один параметр: "availableFunds" — общее количество средств, которые необходимо распределить. Процесс этот делится на несколько этапов.
Разделение средств на две части. Рассчитывается "outsiderFunds" — часть средств, предназначенная для "аутсайдеров". Количество этих средств определяется как доля от общего "availableFunds", где "omegaCurrent" (параметр, контролирующий долю средств для аутсайдеров) является коэффициентом. Оставшиеся средства "existingFunds" идут на распределение среди активных исследователей.Распределение средств существующим исследователям. Эта часть выполняется только, если существует "глобальный отчёт" (globalReport) и если его размер больше нуля вычисляется "totalRank", сумма всех рангов в арифметической прогрессии от "1" до "reportSize". По сути, это сумма весовых коэффициентов, которые будут использоваться для пропорционального распределения средств. Затем средства (existingFunds) распределяются по одному: для каждого фонда генерируется случайное число, умноженное на "totalRank", и это будет использоваться для выбора исследователя. Происходит итерация по "globalReport".
Для каждой записи в "globalReport" вычисляется кумулятивная сумма "cumSum", к которой добавляется "вес", равный (reportSize - i). Это означает, что исследователям с более высокими позициями в отчете присваивается больший вес и, следовательно, они имеют больше шансов получить средства. Если случайное число попадает в интервал, ассоциированный с текущим исследователем (т.е. rnd <= cumSum), то количество средств этого исследователя увеличивается на единицу. После этого цикл распределения текущего фонда прерывается, и переходят к распределению следующего фонда.
Создание аутсайдеров. В завершение вызывается функция "CreateOutsiders", которой передается "outsiderFunds". Эта функция использует выделенные "аутсайдерские" средства для создания новых исследователей или, другими словами, для инициирования новых исследовательских путей.Таким образом, "AssignFunds" реализует стратегию управления грантами, которая поощряет хорошо зарекомендовавших себя исследователей (посредством "existingFunds" и рангового распределения) и одновременно стимулирует появление новых идей или агентов (посредством "outsiderFunds").
//———————————————————————————————————————————————————————————————————— void C_AO_CoSO::AssignFunds (int availableFunds) { // Средства для аутсайдеров int outsiderFunds = (int)(availableFunds * omegaCurrent); int existingFunds = availableFunds - outsiderFunds; int reportSize = ArraySize (globalReport); // Распределение средств существующим исследователям if (reportSize > 0) { int totalRank = reportSize * (reportSize + 1) / 2; for (int f = 0; f < existingFunds; f++) { double rnd = u.RNDprobab () * totalRank; double cumSum = 0; for (int i = 0; i < reportSize; i++) { cumSum += reportSize - i; if (rnd <= cumSum) { researchers [globalReport [i].index].m++; break; } } } } // Создание аутсайдеров CreateOutsiders (outsiderFunds); } //————————————————————————————————————————————————————————————————————
Функция "CreateOutsiders" описывает процесс создания новых "исследователей" в рамках модели CoSO, используя средства, выделенные специально для "аутсайдеров". Эти новые исследователи представляют собой потенциальное разнообразие или новые идеи, вводимые в систему. Функция принимает один параметр: "outsiderFunds" - количество средств, предназначенных для создания аутсайдеров. Если "outsiderFunds" меньше или равно нулю, функция немедленно прерывает выполнение, так как средств для создания аутсайдеров нет.
Определение количества новых исследователей. Устанавливается "maxNew": максимальное количество новых аутсайдеров, которое может быть создано в текущий момент. Это значение зависит от текущего размера популяции. Если популяция велика (более 100 элементов), то "maxNew" равно 2 (для замедления роста). В противном случае "maxNew" равно 5. Это механизм контроля роста популяции. Определяется фактическое количество новых исследователей, которое будет создано. Оно выбирается случайным образом в диапазоне от одного до минимального значения из "outsiderFunds" и "maxNew". Это гарантирует, что количество новых исследователей не превысит доступных средств и установленного лимита, далее рассчитывается, сколько средств получит каждый новый исследователь (простое деление общего "outsiderFunds" на "newResearchers").
Цикл создания новых исследователей. Функция в цикле создает "newResearchers" количество раз: сначала ищется "свободное" место в существующем массиве исследователей (researchers). Если свободное место найдено (idx != -1), оно используется. Если свободного места нет, но текущий размер популяции меньше максимально допустимого размера (maxPopSize), то новое место добавляется в конец массива (idx = actualPopSize).
Расширение массива (при необходимости). Если нет свободного места, и "actualPopSize" уже равен или превышает "maxPopSize", то проверяется, можно ли увеличить размер массива исследователей. Если "actualPopSize" уже достигает "maxPopSize" рассчитывается новый максимальный размер (newMaxSize) как "maxPopSize + 50", но не более 500. Это еще один механизм ограничения роста популяции. Если достигнут абсолютный лимит в 500, то текущая итерация пропускается (новые аутсайдеры не создаются). В противном случае, "maxPopSize" обновляется до "newMaxSize". После проверок "idx" устанавливается на "actualPopSize", чтобы использовать первое новое место. Если по какой-либо причине "idx" все еще "-1", после всех попыток найти или создать место, то создание текущего исследователя пропускается.
Инициализация нового исследователя. Если место "idx" успешно найдено или создано, "researchers [idx]. alive" устанавливается в "true", делая исследователя активным, а количество средств или "мотивация" устанавливается в "fundsPerNew", и "сила" или начальное значение другого параметра инициализируется случайным числом.
Инициализация координат (положения в пространстве решения). Для каждой координаты "c" (coords — количество измерений) позиция инициализируется случайным числом в заданном диапазоне. Затем "researchers [idx]. x [c]" корректируется с учетом шага дискретизации с помощью функции "SeInDiSp" и "лучшая" позиция, изначально равная текущей, также устанавливается в "researchers [idx]. x [c]". Скорость или вектор изменения инициализируется случайным числом, взятым из нормального распределения с заданными параметрами.
Инициализация вероятностей журналов (журналов публикации). Для каждого журнала "j" ( journalsNum — количество журналов) вероятность публикации в журнале "j" инициализируется случайным числом. Затем вызывается "NormalizeProbabilities" для "researchers [idx]. rho", чтобы обеспечить, что сумма всех "rho" для этого исследователя равна единице.
Обновление размера популяции. Если новый исследователь был добавлен в конец массива, то "actualPopSize" обновляется до "idx + 1".
Таким образом, "CreateOutsiders" динамически добавляет новых исследователей в популяцию, обеспечивая их случайную инициализацию в пространстве решений и распределяя между ними выделенные средства. Механизмы ограничения "maxNew" и "maxPopSize" служат для контроля за размером популяции, предотвращая ее бесконечный рост.
//———————————————————————————————————————————————————————————————————— void C_AO_CoSO::CreateOutsiders (int outsiderFunds) { if (outsiderFunds <= 0) return; // Ограничиваем количество новых аутсайдеров, особенно если популяция уже большая int maxNew = (actualPopSize > 100) ? 2 : 5; int newResearchers = (int)(u.RNDfromCI (1, MathMin (outsiderFunds, maxNew))); int fundsPerNew = outsiderFunds / newResearchers; for (int i = 0; i < newResearchers; i++) { // Находим свободное место int idx = -1; for (int j = 0; j < actualPopSize; j++) { if (!researchers [j].alive) { idx = j; break; } } if (idx == -1 && actualPopSize < maxPopSize) { idx = actualPopSize; } if (idx == -1) // Нет места, расширяем массив { if (actualPopSize >= maxPopSize) { // Ограничиваем рост популяции int newMaxSize = MathMin (maxPopSize + 50, 500); if (newMaxSize == maxPopSize) continue; // Достигнут лимит, пропускаем создание maxPopSize = newMaxSize; ArrayResize (researchers, maxPopSize); for (int j = actualPopSize; j < maxPopSize; j++) { researchers [j].Init (coords, journalsNum); researchers [j].alive = false; } idx = actualPopSize; } } if (idx == -1) continue; // Не удалось создать researchers [idx].alive = true; researchers [idx].m = fundsPerNew; researchers [idx].s = u.RNDprobab (); // Случайная инициализация for (int c = 0; c < coords; c++) { researchers [idx].x [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]); researchers [idx].x [c] = u.SeInDiSp (researchers [idx].x [c], rangeMin [c], rangeMax [c], rangeStep [c]); researchers [idx].b [c] = researchers [idx].x [c]; researchers [idx].v [c] = u.GaussDistribution (0.0, -0.01, 0.01, 1); } // Инициализация вероятностей журналов for (int j = 0; j < journalsNum; j++) { researchers [idx].rho [j] = u.RNDprobab (); } NormalizeProbabilities (researchers [idx].rho); if (idx >= actualPopSize) actualPopSize = idx + 1; } } //————————————————————————————————————————————————————————————————————
Функция "HireResearchers" описывает процесс "найма" новых исследователей существующим исследователем, который обладает достаточным количеством грантов. Это механизм создания новых элементов (решений) с учетом характеристик уже существующих, представляющий собой форму воспроизводства или диверсификации. Функция принимает один параметр индекс "супервизора" — исследователя, который будет нанимать новых. Если у исследователя по индексу менее или равно единице средств, функция немедленно прерывает выполнение. Это означает, что для найма необходимо достаточное количество средств.
Разделение средств супервизора. Рассчитывается часть средств, которые супервизор оставляет себе. Это общие средства супервизора, умноженные на "researchers [idx]. s". Рассчитывается средства, доступные для найма. Это оставшиеся средства. Средства супервизора обновляются. Если "hireFunds" меньше или равно 0, то найм невозможен, и функция прерывает выполнение.
Определение количества нанимаемых исследователей. Устанавливается максимальное количество новых исследователей, которое можно нанять. Если текущая популяция велика (более 100), "maxNew" равно 1. В противном случае, "maxNew" равно 3. Это механизм контроля роста популяции. Определяется фактическое количество новых исследователей, которое будет создано. Оно выбирается случайным образом в диапазоне от единицы до минимального значения из "hireFunds" и "maxNew". Рассчитывается, сколько средств получит каждый новый нанятый исследователь (простое деление "hireFunds" на "newCount").
Цикл создания новых исследователей (найм). Функция в цикле нанимает "newCount" количество раз: сначала ищется "свободное" место в существующем массиве исследователей. Свободным местом считается индекс, где флаг активности установлен в "false" и, если свободное место найдено, оно используется. Если свободного места нет, но текущий размер популяции меньше максимально допустимого размера, то новое место добавляется в конец массива.
Проверка возможности найма (при достижении лимитов). Если нет свободного места, и при этом "actualPopSize" уже равен или превышает "maxPopSize", или "actualPopSize" уже равен или превышает абсолютный лимит в 500, то создание текущего исследователя пропускается (цикл переходит к следующей итерации или завершается). Если "newIdx" все еще -1, это означает, что невозможно найти или создать место для нового исследователя, и текущая итерация цикла пропускается.
Инициализация нового исследователя. Если место успешно найдено, "researchers [newIdx]. alive" устанавливается в "true", делая нового исследователя активным, и средства нового исследователя устанавливаются в "fundsPerNew". Параметр "склонности" нового исследователя инициализируется случайным числом, взятым из распределения Гаусса. Среднее значение для этого распределения берется из "researchers [idx]. s" (параметр супервизора) и означает, что новый исследователь будет схож со своим "супервизором". Значение "s" ограничивается диапазоном от "0" до "1".
Наследование характеристик от супервизора. Лучшая найденная позиция или "знание" нового исследователя копируется непосредственно из лучшей позиции супервизора и позволяет новым исследователям наследовать "опыт".
Инициализация позиции (координат). Для каждой координаты "c" (coords — количество измерений) позиция нового исследователя инициализируется как позиция супервизора, плюс случайное возмущение, взятое из распределения Гаусса. Это означает, что новые исследователи появляются "рядом" со своим супервизором, но не в точно таком же месте. Позиция ограничивается заданными пределами. Затем, "researchers [newIdx]. x [c]" корректируется с учетом шага дискретизации с помощью функции "SeInDiSp", скорость или вектор изменения также инициализируется случайным образом из нормального распределения.
Инициализация вероятностей журналов (публикации). Для каждого журнала "j" (journalsNum — количество журналов) вероятность публикации в журнале "j" инициализируется случайным числом, взятым из распределения Гаусса. Среднее значение для этого распределения берется из вероятности супервизора. Это позволяет новым исследователям наследовать предпочтения супервизора по журналам, но с некоторым случайным отклонением. Отрицательные значения "rho" обрезаются до "0". Затем вызывается "NormalizeProbabilities" для "researchers [newIdx]. rho", чтобы обеспечить, что сумма всех "rho" для этого исследователя равна единице.
Обновление размера популяции. Если новый исследователь был добавлен в конец массива ("newIdx" равен или больше "actualPopSize"), то "actualPopSize" обновляется до "newIdx + 1".
Таким образом, "HireResearchers" позволяет успешным исследователям "размножаться", создавая новые экземпляры, которые наследуют часть их характеристик, но с некоторой случайной вариацией. Это способствует исследованию соседних областей в пространстве поиска и распространению успешных стратегий, при этом контролируя общий размер популяции.
//———————————————————————————————————————————————————————————————————— void C_AO_CoSO::HireResearchers (int idx) { if (researchers [idx].m <= 1) return; int keepFunds = (int)(researchers [idx].m * researchers [idx].s); int hireFunds = researchers [idx].m - keepFunds; researchers [idx].m = keepFunds; if (hireFunds <= 0) return; // Ограничиваем количество нанимаемых, особенно при большой популяции int maxNew = (actualPopSize > 100) ? 1 : 3; int newCount = (int)(u.RNDfromCI (1, MathMin (hireFunds, maxNew))); int fundsPerNew = hireFunds / newCount; for (int i = 0; i < newCount; i++) { // Находим свободное место int newIdx = -1; for (int j = 0; j < actualPopSize; j++) { if (!researchers [j].alive) { newIdx = j; break; } } if (newIdx == -1 && actualPopSize < maxPopSize) { newIdx = actualPopSize; } if (newIdx == -1) // Нет места { if (actualPopSize >= maxPopSize || actualPopSize >= 500) continue; // Пропускаем создание при достижении лимита } if (newIdx == -1) continue; // Не удалось найти место researchers [newIdx].alive = true; researchers [newIdx].m = fundsPerNew; researchers [newIdx].s = u.GaussDistribution (researchers [idx].s, 0, 1, 1); if (researchers [newIdx].s < 0) researchers [newIdx].s = 0; if (researchers [newIdx].s > 1) researchers [newIdx].s = 1; // Наследование от супервизора ArrayCopy (researchers [newIdx].b, researchers [idx].b, 0, 0, WHOLE_ARRAY); // Позиция около супервизора for (int c = 0; c < coords; c++) { researchers [newIdx].x [c] = researchers [idx].x [c] + u.GaussDistribution (0.0, -0.01, 0.01, 1); // Контроль границ if (researchers [newIdx].x [c] < rangeMin [c]) researchers [newIdx].x [c] = rangeMin [c]; if (researchers [newIdx].x [c] > rangeMax [c]) researchers [newIdx].x [c] = rangeMax [c]; researchers [newIdx].x [c] = u.SeInDiSp (researchers [newIdx].x [c], rangeMin [c], rangeMax [c], rangeStep [c]); researchers [newIdx].v [c] = u.GaussDistribution (0.0, -0.01, 0.01, 1); } // Возмущенные вероятности журналов for (int j = 0; j < journalsNum; j++) { researchers [newIdx].rho [j] = u.GaussDistribution (researchers [idx].rho [j], 0, 1, 1); if (researchers [newIdx].rho [j] < 0) researchers [newIdx].rho [j] = 0; } NormalizeProbabilities (researchers [newIdx].rho); if (newIdx >= actualPopSize) actualPopSize = newIdx + 1; } } //————————————————————————————————————————————————————————————————————
Функция "ComputeStdDev" предназначена для расчета стандартного отклонения значений целевой функции для всех активных исследователей в популяции. Это мера рассеяния данных вокруг среднего значения, и в контексте оптимизации может указывать на разнообразие решений в текущей популяции.
Расчет среднего значения (Mean):- Инициализируются переменные "mean" (для накопления суммы значений "f") и "count" (для подсчета количества активных исследователей).
- Функция итерирует по всем исследователям в массиве "researchers" от "0" до "actualPopSize - 1".
- Внутри цикла проверяется, является ли исследователь "researchers [i] "активным", так как только активные исследователи должны учитываться в расчетах.
- Если исследователь активен, его значение "f" добавляется к "mean", а "count" увеличивается на "1".
- После завершения первого цикла, если "count" все еще равен "0" (не найдено ни одного активного исследователя), функция возвращает "0".
- Наконец, "mean" делится на "count", чтобы получить среднее арифметическое значение "f" для всех активных исследователей.
- Инициализируется переменная "variance" равная "0".
- Функция снова итерирует по всем исследователям в массиве "researchers".
- Снова проверяется условие активного исследователя.
- Для каждого действующего исследователя рассчитывается квадрат разности между его значением "f" и уже вычисленным "mean". Этот квадрат разности добавляется к "variance".
- После завершения второго цикла, "variance" делится на "count". Это дает дисперсию значений "f" для активных исследователей.
//———————————————————————————————————————————————————————————————————— double C_AO_CoSO::ComputeStdDev () { if (actualPopSize == 0) return 0; double mean = 0; int count = 0; for (int i = 0; i < actualPopSize; i++) { if (researchers [i].alive) { mean += researchers [i].f; count++; } } if (count == 0) return 0; mean /= count; double variance = 0; for (int i = 0; i < actualPopSize; i++) { if (researchers [i].alive) { variance += MathPow (researchers [i].f - mean, 2); } } variance /= count; return MathSqrt (variance); } //————————————————————————————————————————————————————————————————————
Функция "UpdateOmega" динамически корректирует параметр "omegaCurrent", который представляет собой долю аутсайдеров или вероятность выбора аутсайдера в поведении алгоритма. Цель этой функции — адаптивно управлять стратегией исследования/эксплуатации в зависимости от текущего состояния популяции исследователей, а именно, от их рассеяния в пространстве поиска.
Функция в первую очередь вызывает "ComputeStdDev ()" для определения "currentSigma" — текущего стандартного отклонения значений целевой функции для активных исследователей. Высокое "currentSigma" означает большое разнообразие решений, а низкое — их сходимость.
Случай 1: Сходимость популяции (currentSigma < sigma0). Если текущее стандартное отклонение меньше некоторого предопределенного порога "sigma0", это является признаком того, что исследователи начинают сходиться или кластеризоваться вокруг определенных решений. В этом случае алгоритм переходит к стадии эксплуатации (уточнения) найденных решений. Чтобы избежать преждевременной сходимости к локальному оптимуму и стимулировать дальнейшее исследование, а также поиск лучших решений, доля аутсайдеров (omegaCurrent) увеличивается. Прибавка рассчитывается как (omegaMax - omegaMin) / 2.0 * epsilonPlus. Здесь "omegaMax" и "omegaMin" определяют верхнюю и нижнюю границы для "omegaCurrent", а "epsilonPlus" — положительный коэффициент, контролирующий скорость увеличения. Цель — дать больший вес элементам, которые могут "выбиваться" из общего тренда или представлять собой совершенно новые подходы.
Случай 2: Расхождение или отсутствие сходимости популяции (currentSigma >= sigma0). Если стандартное отклонение больше или равно порогу "sigma0", это означает, что популяция все еще сильно распределена или находится на ранних стадиях исследования. В этом случае доля аутсайдеров (omegaCurrent) уменьшается. Уменьшение рассчитывается как (omegaMax - omegaMin) / 2.0 * epsilonMinus, где "epsilonMinus" — отрицательный коэффициент, контролирующий скорость уменьшения. Это делается для того, чтобы алгоритм не тратил слишком много ресурсов на случайное исследование, когда популяция и так достаточно разнообразна, и можно начать фокусироваться на более перспективных областях.
Ограничение диапазона (omegaCurrent). После изменения "omegaCurrent" функция гарантирует, что его значение остается в пределах заданного диапазона, если "omegaCurrent" опускается ниже "omegaMin", оно приравнивается к "omegaMin", а если оно превышает "omegaMax", оно приравнивается к "omegaMax", предотвращает выход параметра за разумные рабочие пределы.
В целом, "UpdateOmega" функция реализует адаптивную стратегию. Когда популяция исследователей показывает признаки быстрой сходимости (низкое стандартное отклонение), алгоритм увеличивает вероятность выбора "аутсайдеров" (или элементов, которые могут нарушить текущую структуру), чтобы помочь избежать локальных оптимумов и стимулировать новый поиск или исследование более широкого пространства. И наоборот, когда популяция все еще широко распределена, алгоритм уменьшает акцент на аутсайдерах, чтобы сосредоточиться на более систематическом исследовании или эксплуатации уже найденных перспективных областей.
//———————————————————————————————————————————————————————————————————— void C_AO_CoSO::UpdateOmega () { double currentSigma = ComputeStdDev (); if (currentSigma < sigma0) { // Увеличиваем долю аутсайдеров при сходимости omegaCurrent += (omegaMax - omegaMin) / 2.0 * epsilonPlus; } else { // Уменьшаем долю аутсайдеров omegaCurrent -= (omegaMax - omegaMin) / 2.0 * epsilonMinus; } // Ограничиваем диапазон if (omegaCurrent < omegaMin) omegaCurrent = omegaMin; if (omegaCurrent > omegaMax) omegaCurrent = omegaMax; } //————————————————————————————————————————————————————————————————————
Функция "NormalizeProbabilities" предназначена для преобразования массива числовых значений "probs" таким образом, чтобы они представляли собой корректное распределение вероятностей. То есть, после выполнения функции сумма всех элементов в массиве "probs" будет равна единице. Инициализируется переменная "sum" равная 0, она будет использоваться для накопления суммы всех элементов в массиве "probs". Запускается цикл, который проходит по всем элементам этого массива. Внутри цикла каждое значение "probs [i]" добавляется к переменной "sum".
Если вычисленная "sum" положительна, запускается второй цикл, который также проходит по всем элементам массива "probs". Внутри этого цикла каждый элемент массива делится на "sum". В результате этого деления каждое значение "probs [i]" становится соответствующей долей от общей суммы, и сумма всех элементов в массиве становится равной "1". Это стандартная процедура нормализации.
Если "sum" равна "0" или отрицательна, хотя для вероятностей это обычно не ожидается, но функция обрабатывает и такой случай, это означает, что нормализовать исходные значения не на что. Например, все исходные вероятности были нулями. В этом случае функция переходит к "равномерному распределению". Вычисляется значение "val" как (1.0 / size). Это означает, что каждый элемент массива получит одинаковую вероятность, чтобы их сумма составляла "1". Запускается третий цикл, который проходит по всем элементам массива "probs". Внутри этого цикла каждому элементу присваивается вычисленное значение "val". Таким образом, каждый элемент массива становится равным (1 / size), и их сумма составит "1".
Эта функция является общим утилитным методом для обеспечения того, чтобы набор весов или "сырых" вероятностей мог быть использован как истинное распределение вероятностей (где "истинное" означает, что сумма всех вероятностей равна 1). Это важно во многих алгоритмах, таких как методы выбора на основе вероятностей, рулетки или метода Монте-Карло, где правильная нормализация предотвращает ошибки и обеспечивает корректное статистическое поведение.
//———————————————————————————————————————————————————————————————————— void C_AO_CoSO::NormalizeProbabilities (double &probs []) { double sum = 0; int size = ArraySize (probs); for (int i = 0; i < size; i++) { sum += probs [i]; } if (sum > 0) { for (int i = 0; i < size; i++) { probs [i] /= sum; } } else { // Равномерное распределение double val = 1.0 / size; for (int i = 0; i < size; i++) { probs [i] = val; } } } //————————————————————————————————————————————————————————————————————
Функция "CompactPopulation" занимается управлением размером и составом популяции исследователей в алгоритме. Основная цель — удалить наименее эффективных исследователей и при необходимости сократить популяцию до управляемого размера, чтобы поддерживать эффективность и производительность алгоритма.
Подсчет "активных" исследователей. Инициализируется переменная "aliveCount" (количество выживших) равная "0". Далее, в цикле перебираются все исследователи в текущей популяции (от 0 до actualPopSize - 1). Для каждого исследователя проверяется его состояние (researchers [i]. alive). Если исследователь "жив" (его свойство alive истинно), "aliveCount" увеличивается на единицу.Условие для компактификации/сокращения. После подсчета живых исследователей, функция проверяет, нужно ли выполнять компактификацию. Это происходит, если выполняется одно из двух условий: количество активных исследователей "aliveCount" составляет менее 75% от текущего общего размера популяции "actualPopSize" или если текущий размер популяции "actualPopSize" превышает 200 (даже если большинство из них живы, популяция считается слишком большой и нуждается в сокращении).
Первая фаза компактификации (удаление "неактивных"). Если одно из условий для компактификации выполнено, начинается процесс. Инициализируется новый индекс равный "0". Этот индекс будет указывать на следующее свободное место в начале массива "researchers", куда будут перемещаться "активные" исследователи. Запускается цикл, перебирающий всех исследователей (от 0 до actualPopSize - 1). Внутри цикла, если текущий исследователь "активен", проверяется, находится ли он уже на правильном месте, а если нет, это означает, что его нужно переместить вперед в массиве.
Исследователь копируется в позицию "newIdx". Обычно, в таких случаях,( researchers [i]. alive = false) устанавливается, чтобы пометить исходного исследователя как "удаленного" или неактивного, хотя он уже скопирован. Это очистка, "newIdx" увеличивается на единицу, чтобы указать на следующее место для следующего активного исследователя. После завершения этого цикла, все "живые" исследователи будут находиться в начале массива "researchers". Размер популяции обновляется до "aliveCount".
Вторая фаза компактификации (сокращение большой популяции). После первой фазы (где неактивные были удалены и живые смещены), функция проверяет, не превышает ли "actualPopSize" все еще 150. Это условие вложенное, то есть оно выполняется, только если популяция уже была компактифицирована или имела много неактивных исследователей. Если "actualPopSize" больше 150, это означает, что даже после удаления неактивных, популяция все еще слишком велика и нуждается в дальнейшем сокращении до максимально допустимого размера 150. Для этого выполняется сортировка по "fitness". После этого, исследователи с лучшими "fitness" будут находиться в начале массива.
Удаление "худших" исследователей. Все исследователи, начиная с 150-го элемента (то есть те, которые оказались в "хвосте" после сортировки), помечаются как "неактивные" (researchers [i]. alive = false). Их параметр "m" также обнуляется. Наконец, "actualPopSize" устанавливается в 150, эффективно обрезая популяцию до желаемого максимального размера. Эта функция обеспечивает, что популяция:- Не накапливает неиспользуемых индивидов, которые могут занимать память и замедлять обработку.
- Не растет бесконтрольно, что также может негативно сказаться на производительности и эффективности, а также привести к раннему параличу.
- Поддерживает определенный уровень качества, отсеивая худших индивидов, когда размер популяции становится критическим.
//———————————————————————————————————————————————————————————————————— void C_AO_CoSO::CompactPopulation () { // Подсчитываем живых исследователей int aliveCount = 0; for (int i = 0; i < actualPopSize; i++) { if (researchers [i].alive) aliveCount++; } // Если слишком много мертвых, компактифицируем if (aliveCount < actualPopSize * 0.75 || actualPopSize > 200) { int newIdx = 0; for (int i = 0; i < actualPopSize; i++) { if (researchers [i].alive) { if (i != newIdx) { // Копируем живого исследователя на новое место researchers [newIdx] = researchers [i]; researchers [i].alive = false; } newIdx++; } } actualPopSize = aliveCount; // Если популяция все еще слишком большая, ограничиваем if (actualPopSize > 150) { // Сортируем по fitness и оставляем лучших for (int i = 0; i < actualPopSize - 1; i++) { for (int j = i + 1; j < actualPopSize; j++) { if (researchers [i].f < researchers [j].f) { S_Researcher temp = researchers [i]; researchers [i] = researchers [j]; researchers [j] = temp; } } } // Убиваем худших for (int i = 150; i < actualPopSize; i++) { researchers [i].alive = false; researchers [i].m = 0; } actualPopSize = 150; } } } //————————————————————————————————————————————————————————————————————
Оставшийся метод "Revision" в алгоритме CoSO. Запускается цикл, который проходит по всем индивидам в массиве "a" от индекса "0" до "aSize - 1". Внутри цикла для каждого индивида "a [i]" проверяется условие: "if (a [i]. f > fB)". Если значение целевой функции текущего индивида оказывается больше, чем текущее глобально лучшее значение, "fB" обновляется до нового лучшего значения: "fB = a [i]. f". Индекс этого лучшего индивида запоминается.
После завершения цикла, который перебрал всех индивидов в массиве "a", проверяется условие "if (bestIND != -1)". Это условие истинно, если был найден хотя бы один индивид, чья целевая функция была лучше, чем предыдущее значение "fB". Если новый лучший индивид был найден (bestIND не равен -1), вызывается функция "ArrayCopy", которая копирует параметры "c" найденного лучшего индивида в глобальный массив "cB".
Основное назначение этого метода — поддерживать актуальное состояние глобально лучшего решения, найденного алгоритмом на данный момент. В эволюционных алгоритмах, таких как CoSO, концепция "глобального лучшего" (global best) постоянно отслеживается и обновляется по мере того, как находятся лучшие решения. Этот "глобальный лучший" результат затем используется для направления поиска. По сути, эта функция является реализацией шага "запоминания лучшего решения" на каждой итерации алгоритма.
//———————————————————————————————————————————————————————————————————— void C_AO_CoSO::Revision () { int bestIND = -1; int aSize = ArraySize (a); for (int i = 0; i < aSize; i++) { if (a [i].f > fB) { fB = a [i].f; bestIND = i; } } if (bestIND != -1) { ArrayCopy (cB, a [bestIND].c, 0, 0, WHOLE_ARRAY); } } //————————————————————————————————————————————————————————————————————
Результаты тестов
Алгоритм CoSO работает достаточно хорошо, неплохие показатели, можно еще, конечно, поэкспериментировать с параметрами, это для желающих. =============================
5 Hilly's; Func runs: 10000; result: 0.8047081198587067
25 Hilly's; Func runs: 10000; result: 0.5429326559833119
500 Hilly's; Func runs: 10000; result: 0.30916988715342353
=============================
5 Forest's; Func runs: 10000; result: 0.7383405771205314
25 Forest's; Func runs: 10000; result: 0.38224371519203115
500 Forest's; Func runs: 10000; result: 0.20600693936217676
=============================
5 Megacity's; Func runs: 10000; result: 0.553846153846154
25 Megacity's; Func runs: 10000; result: 0.2550769230769231
500 Megacity's; Func runs: 10000; result: 0.11129230769230862
=============================
All score: 3.90362 (43.37%)
Первый раз встречаюсь с такой необычной визуализацией алгоритма, связано это с многослойной логикой реализации.
CoSO на тестовой функции Hilly
CoSO на тестовой функции Forest
CoSO на тестовой функции Megacity
По итогам работы, алгоритм в турнирной таблице CoSO представлен ознакомительно. Хочу заметить, что наша таблица уплотняется, и результаты меньше 45% уже выходят за ее пределы.
| № | AO | Description | Hilly | Hilly Final | Forest | Forest Final | Megacity (discrete) | Megacity Final | Final Result | % of MAX | ||||||
| 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | ||||||||
| 1 | ANS | across neighbourhood search | 0,94948 | 0,84776 | 0,43857 | 2,23581 | 1,00000 | 0,92334 | 0,39988 | 2,32323 | 0,70923 | 0,63477 | 0,23091 | 1,57491 | 6,134 | 68,15 |
| 2 | CLA | code lock algorithm (joo) | 0,95345 | 0,87107 | 0,37590 | 2,20042 | 0,98942 | 0,91709 | 0,31642 | 2,22294 | 0,79692 | 0,69385 | 0,19303 | 1,68380 | 6,107 | 67,86 |
| 3 | AMOm | animal migration ptimization M | 0,90358 | 0,84317 | 0,46284 | 2,20959 | 0,99001 | 0,92436 | 0,46598 | 2,38034 | 0,56769 | 0,59132 | 0,23773 | 1,39675 | 5,987 | 66,52 |
| 4 | (P+O)ES | (P+O) evolution strategies | 0,92256 | 0,88101 | 0,40021 | 2,20379 | 0,97750 | 0,87490 | 0,31945 | 2,17185 | 0,67385 | 0,62985 | 0,18634 | 1,49003 | 5,866 | 65,17 |
| 5 | CTA | comet tail algorithm (joo) | 0,95346 | 0,86319 | 0,27770 | 2,09435 | 0,99794 | 0,85740 | 0,33949 | 2,19484 | 0,88769 | 0,56431 | 0,10512 | 1,55712 | 5,846 | 64,96 |
| 6 | 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 | EOm | extremal_optimization_M | 0,76166 | 0,77242 | 0,31747 | 1,85155 | 0,99999 | 0,76751 | 0,23527 | 2,00277 | 0,74769 | 0,53969 | 0,14249 | 1,42987 | 5,284 | 58,71 |
| 13 | BBO | biogeography based optimization | 0,94912 | 0,69456 | 0,35031 | 1,99399 | 0,93820 | 0,67365 | 0,25682 | 1,86867 | 0,74615 | 0,48277 | 0,17369 | 1,40261 | 5,265 | 58,50 |
| 14 | 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 |
| 15 | 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 |
| 16 | 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 |
| 17 | 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 |
| 18 | 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 |
| 19 | 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 |
| 20 | 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 |
| 21 | BSA | backtracking_search_algorithm | 0,97309 | 0,54534 | 0,29098 | 1,80941 | 0,99999 | 0,58543 | 0,21747 | 1,80289 | 0,84769 | 0,36953 | 0,12978 | 1,34700 | 4,959 | 55,10 |
| 22 | 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 |
| 23 | 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 |
| 24 | 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 |
| 25 | 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 |
| 26 | 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 |
| 27 | DEA | dolphin_echolocation_algorithm | 0,75995 | 0,67572 | 0,34171 | 1,77738 | 0,89582 | 0,64223 | 0,23941 | 1,77746 | 0,61538 | 0,44031 | 0,15115 | 1,20684 | 4,762 | 52,91 |
| 28 | 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 |
| 29 | 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 |
| 30 | 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 |
| 31 | 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 |
| 32 | (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 |
| 33 | FBA | fractal-based Algorithm | 0,79000 | 0,65134 | 0,28965 | 1,73099 | 0,87158 | 0,56823 | 0,18877 | 1,62858 | 0,61077 | 0,46062 | 0,12398 | 1,19537 | 4,555 | 50,61 |
| 34 | 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 |
| 35 | 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 |
| 36 | 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 |
| 37 | 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 |
| 38 | 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 |
| 39 | CAm | camel algorithm M | 0,78684 | 0,56042 | 0,35133 | 1,69859 | 0,82772 | 0,56041 | 0,24336 | 1,63149 | 0,64846 | 0,33092 | 0,13418 | 1,11356 | 4,444 | 49,37 |
| 40 | 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 |
| 41 | CMAES | covariance_matrix_adaptation_evolution_strategy | 0,76258 | 0,72089 | 0,00000 | 1,48347 | 0,82056 | 0,79616 | 0,00000 | 1,61672 | 0,75846 | 0,49077 | 0,00000 | 1,24923 | 4,349 | 48,33 |
| 42 | 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 |
| 43 | 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 |
| 44 | 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 |
| 45 | 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 |
| CoSO | community_of_scientist_optimization | 0,80471 | 0,54293 | 0,30917 | 1,65681 | 0,73834 | 0,38224 | 0,20600 | 1,32658 | 0,55384 | 0,25507 | 0,11129 | 0,92020 | 3,904 | 43,37 | |
| RW | random walk | 0,48754 | 0,32159 | 0,25781 | 1,06694 | 0,37554 | 0,21944 | 0,15877 | 0,75375 | 0,27969 | 0,14917 | 0,09847 | 0,52734 | 2,348 | 26,09 | |
Выводы
Алгоритм CoSO демонстрирует средние результаты на тестовых функциях, достигая 43% от максимально возможной производительности. Конечно, я ожидал более впечатляющих результатов. В тестовом стенде предлагается расширенный набор функций, в том числе стандартных и общеизвестных, где каждый желающий может дополнительно экспериментировать как с подбором параметров, так и с подбором функций для лучшего раскрытия возможностей алгоритма.
Главным недостатком текущей реализации является высокая вычислительная сложность. Многослойная архитектура с журналами, динамическим распределением средств и адаптивным управлением популяцией создает существенную нагрузку. Алгоритм заметно медленнее других популяционных методов, что ограничивает его применимость в задачах, требующих быстрых решений.
Однако концептуальная основа CoSO представляет значительный интерес. Моделирование научного сообщества привносит уникальные механизмы, которые были применены: динамическая популяция автоматически адаптирует вычислительные ресурсы к сложности задачи, система журналов обеспечивает эффективный обмен информацией без потери лучших решений, конкурентное финансирование создает естественный отбор без жестких правил, а механизм найма пытается решать дилемму локального/глобального поиска.
Потенциал для улучшения очевиден. CoSO следует рассматривать не как готовое решение, а как перспективную исследовательскую платформу. Алгоритм открывает новое направление в эволюционной оптимизации, где социальные механизмы человеческих сообществ становятся источником вычислительных стратегий. При должной доработке, CoSO может найти свою нишу в задачах, где важна адаптивность и устойчивость к изменениям, а время вычислений не критично.
Рисунок 1. Цветовая градация алгоритмов по соответствующим тестам
Рисунок 2. Гистограмма результатов тестирования алгоритмов (по шкале от 0 до 100, чем больше, тем лучше, где 100 — максимально возможный теоретический результат, в архиве скрипт для расчета рейтинговой таблицы)
Плюсы и минусы алгоритма CoSO:
Плюсы:
- хорошая база для развития ответвлений новых версий.
Минусы:
- большое количество внешних параметров;
- склонность к застреванию на задачах;
- медленный.
К статье прикреплён архив с актуальными версиями кодов алгоритмов. Автор статьи не несёт ответственности за абсолютную точность в описании канонических алгоритмов, во многие из них были внесены изменения для улучшения поисковых возможностей. Выводы и суждения, представленные в статьях, основываются на результатах проведённых экспериментов.
Программы, используемые в статье
| # | Имя | Тип | Описание |
|---|---|---|---|
| 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_CoSO.mq5 | Скрипт | Испытательный стенд для CoSO |
Разработка советника для мониторинга точек входа в свинг-сделки
Отправка сообщений из MQL5 в Discord, создание бота Discord-MetaTrader 5
Нейросети в трейдинге: Распутывание структурных компонентов (Энкодер)
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Вы принимаете политику сайта и условия использования