Оптимизация сообществом ученых — Community of Scientist Optimization (CoSO): Теория
128
0
Содержание
Введение
В продолжение темы обучения, в данной статье рассмотрим еще один подход к решению задач оптимизации — алгоритм CoSO (Community of Scientist Optimization), основанный на моделировании механизмов функционирования научного сообщества. В отличие от классических биологически-инспирированных алгоритмов, CoSO воспроизводит уникальные особенности научной деятельности: публикацию результатов в изданиях, конкуренцию за гранты, формирование исследовательских групп и баланс между углубленным изучением известных направлений и поиском принципиально новых решений. Алгоритм CoSO был разработан и опубликован в 2012 году двумя учёными A. Milani и V. Santucci.
Интересной особенностью данного подхода является естественная самоорганизация процесса поиска. Подобно реальному научному сообществу, алгоритм концентрирует ресурсы в перспективных областях, сохраняет и распространяет лучшие решения через механизм журналов, и поддерживает необходимое разнообразие через финансирование "аутсайдеров". Динамически изменяющийся размер популяции позволяет алгоритму адаптироваться к особенностям конкретной задачи без необходимости тонкой настройки параметра, это еще одно нововведение, потому что обычно мы используем постоянную популяцию. В статье подробно ознакомимся с математическими основами алгоритма, его ключевыми компонентами и механизмами взаимодействия между ними.
Реализация алгоритма
В основе популяционного алгоритма CoSO лежит идея моделирования поведения исследователей, которые ищут оптимальные решения в многомерном пространстве, обмениваются знаниями через публикации в журналах и конкурируют за ограниченные ресурсы (гранты). Каждый исследователь — это точка в пространстве поиска. У него есть: позиция (где он ищет), направление движения, деньги на исследования и, если деньги заканчиваются, исследователь неактивен.
Каждый исследователь представлен набором параметров: позицией в пространстве поиска x, направлением движения v, личным лучшим результатом b, количеством средств m, стратегией управления средствами s и вероятностями публикации в различных журналах ρ.
Движение исследователей определяется формулой обновления направления, которая сочетает три компонента: инерцию (тенденцию продолжать движение в прежнем направлении), когнитивный компонент (стремление к личному лучшему результату) и социальный компонент (влияние лучших результатов из журналов):
v {i, t} = ω · v {i, t-1} + φ₁ · β₁ · (b {i, t-1} - x {i, t-1}) + φ₂ · β₂ · Σⱼ [ρᵢⱼ · (J {j,c} - x {i, t-1})],
где ω = 0.7298 — коэффициент инерции, φ₁ = φ₂ = 1.49618 — коэффициенты ускорения, β₁ и β₂ — случайные числа из [0,1], ρᵢⱼ — вероятность выбора журнала j исследователем i, J {j,c} — случайная статья из журнала j.
После обновления направления позиция исследователя изменяется по простой формуле: x {i, t} = x {i, t-1} + v {i, t}.
Журналы хранят лучшие найденные решения. Исследователи читают журналы и движутся к хорошим решениям, и только лучшие результаты попадают в журнал. Журналы в алгоритме служат коллективной памятью, сохраняя k лучших решений, найденных всеми исследователями. Когда исследователь получает новый результат, он подает его в один из журналов согласно своему распределению вероятностей ρ, который принимает результат, только если он лучше худшего из уже опубликованных. Это обеспечивает постоянное улучшение качества информации, доступной сообществу.
Успешные исследователи получают больше средств. Часть денег идет на "аутсайдеров" — новых исследователей в случайных местах. Это помогает не застрять в локальных оптимумах. Механизм распределения средств имитирует конкурентное финансирование в науке. На каждой итерации исследователи тратят одну единицу средств, а общая сумма потраченных денег перераспределяется на основе рангового рулеточного отбора. Вероятность получения средств для исследователя на позиции i в глобальном рейтинге определяется формулой:
P (i) = (N - i + 1) / (N · (N + 1) / 2),
где N — количество исследователей.
Часть средств Ω резервируется для создания "аутсайдеров" — новых исследователей в случайных позициях. Параметр Ω адаптивно изменяется для поддержания баланса между исследованием и эксплуатацией. Когда стандартное отклонение fitness-значений популяции σ становится меньше начального σ₀, это сигнализирует о сходимости, и доля аутсайдеров увеличивается:
Ω {t} = Ω {t-1} + (Ω {max} - Ω {min}) / 2 · ε⁺ при σ < σ₀, иначе Ω {t} = Ω {t-1} - (Ω {max} - Ω {min}) / 2 · ε⁻,
где Ω {min} = 0.2, Ω {max} = 0.5, ε⁺ = 0.2, ε⁻ = 0.1.
Успешные ученые могут нанимать помощников, которые начинают поиск рядом с руководителем. Это помогает детально исследовать перспективные области. Успешные исследователи с количеством средств m > 1 могут нанимать новых исследователей. При этом исследователь оставляет себе долю средств, согласно своей стратегии s, а остальное тратит на найм.
Новые исследователи наследуют характеристики супервизора с небольшими возмущениями: позиция инициализируется как x {new} = x {supervisor} + N (0, σv), стратегия как s {new} = N (s {supervisor}, σs), вероятности журналов как ρ {new, j} = N (ρ {supervisor, j}, σρ) с последующей нормализацией.
Поисковую работу в алгоритме можно сравнить со сбором грибов в лесу группой людей: каждый ищет в своем месте, и когда кто-то находит грибное место, он кричит другим, тогда часть группы идет к нему, а часть продолжает искать новые места. Те, кто долго ничего не находит, уходят домой, однако самые успешные грибники приводят друзей на грибные места.
Производительность алгоритма обусловлена сочетанием нескольких механизмов: журналы обеспечивают обмен информацией и направляют поиск к перспективным областям, конкурентное финансирование создает давление отбора, удаляя неэффективных исследователей, найм помощников обеспечивает локальный поиск вокруг хороших решений, а аутсайдеры предотвращают преждевременную сходимость.
Динамически изменяющийся размер популяции позволяет алгоритму адаптироваться к сложности задачи, увеличивая количество исследователей в перспективных областях и сокращая в бесперспективных. Все эти механизмы работают совместно, создавая самоорганизующуюся систему, способную решать задачи в сложных многомерных пространствах.
Рисунок 1. Иллюстрация работы алгоритма CoSO
Что показывает нам иллюстрация:
- Пространство поиска (Search Space), где исследователи (зеленые круги) движутся к оптимуму, показаны их векторы движения.
- Научные журналы (Scientific Journals) хранят лучшие найденные решения, исследователи читают их и публикуют свои результаты.
- Распределение средств (Funds Distribution) — вмногомерных пространствах механизм финансирования с адаптивным параметром Ω для аутсайдеров.
- Формула обновления направления — математическая основа движения исследователей.
- Ключевые механизмы — легенда с типами исследователей: активные (имеют средства), неактивные (без средств), новые наймы и аутсайдеры со случайными позициями.
Стрелки указывают потоки информации (серые), движения (синие) и средств (оранжевые). Перейдем к написанию псевдокода алгоритма.
1. ИНИЦИАЛИЗАЦИЯ:
- Создать 10 исследователей в случайных позициях
- Дать каждому по 15 единиц средств (150 / 10)
- Каждый получает:
* Случайную стратегию сбережений (от 0 до 1)
* Случайные предпочтения по журналам
* Начальное направление движения (малое случайное)
- Создать 3 пустых журнала
- Запомнить начальный разброс популяции
2. ОСНОВНОЙ ЦИКЛ (повторять заданное число раз):
2.1. ОЦЕНКА РЕЗУЛЬТАТОВ:
Для каждого живого исследователя:
- Вычислить качество текущей позиции f(x)
- Если результат лучше личного рекорда:
* Обновить личный рекорд
2.2. ПУБЛИКАЦИЯ В ЖУРНАЛЫ:
Для каждого живого исследователя:
- Выбрать журнал согласно личным предпочтениям
- Попытаться опубликовать результат:
* Журнал принимает, если результат входит в топ-10
* Худшая статья выбывает
2.3. УЧЕТ РАСХОДОВ И ОТЧЕТНОСТЬ:
- Собрать все потраченные средства (по 1 от каждого)
- Составить рейтинг живых исследователей
- Пометить как "мертвых" тех, у кого кончились деньги
2.4. РАСПРЕДЕЛЕНИЕ ФИНАНСИРОВАНИЯ:
- Определить долю для аутсайдеров (20-50%)
- Распределить остальное между существующими:
* Чем выше в рейтинге, тем больше шансов
* Использовать взвешенную рулетку
2.5. СОЗДАНИЕ АУТСАЙДЕРОВ:
- Потратить выделенные средства на 1-5 новичков
- Разместить их в случайных местах
- Дать равные доли от выделенного бюджета
2.6. НАЙМ ПОМОЩНИКОВ:
Для каждого богатого исследователя (средств > 1):
- Оставить себе часть согласно стратегии
- На остальное нанять 1-3 помощников:
* Разместить рядом с собой
* Передать свой опыт с небольшими изменениями
2.7. ВЫБОР НАПРАВЛЕНИЯ ДВИЖЕНИЯ:
Для каждого живого исследователя вычислить:
Новое_направление =
0.7 × Старое_направление + // Инерция
1.5 × Случайность × (Личный_рекорд - Позиция) + // К своему лучшему
1.5 × Случайность × Сумма_по_журналам // К лучшим из журналов
(Вес_журнала × (Статья_из_журнала - Позиция))
2.8. ДВИЖЕНИЕ:
Для каждого живого исследователя:
- Сделать шаг: Новая_позиция = Старая_позиция + Направление
- Если вышел за границы - вернуть на край
2.9. КОНТРОЛЬ РАЗНООБРАЗИЯ:
- Измерить текущий разброс популяции
- Если разброс уменьшился (сходятся):
* Увеличить долю аутсайдеров на 10%
- Иначе:
* Уменьшить долю аутсайдеров на 5%
2.10. УПРАВЛЕНИЕ РАЗМЕРОМ ПОПУЛЯЦИИ:
- Если мертвых больше 25% или всего больше 200:
* Убрать мертвых из массива
- Если осталось больше 150:
* Оставить только 150 лучших
3. РЕЗУЛЬТАТ:
- Вернуть лучшее найденное решение
Теперь можно перейти к практической реализации алгоритма CoSO. Напишем три структуры данных. Первая структура, "S_Journal_Entry", представляет собой отдельную запись в журнале, которая содержит:
- fitness — числовое значение, отражающее "качество" или "пригодность" данной записи.
- decision [] — динамический массив хранящий параметры, связанные с данной записью.
- entries [] — динамическим массивом записей "S_Journal_Entry".
- length — текущим количеством записей в журнале.
- maxLength — максимальным количеством записей, которое может хранить журнал.
Метод "Init" инициализирует журнал, устанавливая максимальную длину, выделяя память под записи и инициализируя каждую запись с минимальным значением фитнес. Метод "Add" используется для добавления новой записи в журнал. Особенностью этого метода является то, что он поддерживает журнал в отсортированном порядке по значению фитнеса. Если новая запись хуже самой худшей записи в уже заполненном журнале, она не добавляется. В противном случае, место для новой записи находится с помощью бинарного поиска, затем существующие записи сдвигаются, освобождая место, и новая запись вставляется, если журнал еще не заполнен, его "length" увеличивается.
Третья структура, "S_Researcher", описывает "исследователя" или "агента". Она содержит набор параметров:
- x [] — текущая позиция исследователя (массив координат)
- v [] — направление или вектор скорости движения исследователя
- b [] — лучшая позиция, найденная данным исследователем индивидуально
- rho [] — массив вероятностей публикации в различных журналах. Исследователь взаимодействует с несколькими "журналами" или источниками информации
- s — стратегия управления средствами
- m — количество средств (целое число)
- f — фитнес текущей позиции исследователя
- fb — фитнес лучшей позиции, найденной исследователем
- alive — флаг, указывающий на активность исследователя
//———————————————————————————————————————————————————————————————————— // Структура для журнала struct S_Journal_Entry { double fitness; double decision []; void Init (int coords) { ArrayResize (decision, coords); fitness = -DBL_MAX; } }; // Структура журнала struct S_Journal { S_Journal_Entry entries []; int length; int maxLength; void Init (int maxLen, int coords) { maxLength = maxLen; length = 0; ArrayResize (entries, maxLen); for (int i = 0; i < maxLen; i++) { entries [i].Init (coords); entries [i].fitness = -DBL_MAX; // Инициализируем минимальным значением } } void Add (double fit, const double &coord []) { // Быстрая проверка - если хуже всех и журнал полон, не добавляем if (length >= maxLength && fit <= entries [length - 1].fitness) return; int insertPos = length; // Находим позицию для вставки (бинарный поиск) if (length > 0) { int left = 0; int right = length - 1; while (left <= right) { int mid = (left + right) / 2; if (entries [mid].fitness < fit) right = mid - 1; else left = mid + 1; } insertPos = left; } // Если вставляем в конец и журнал полон if (insertPos >= maxLength) return; // Сдвигаем элементы if (length < maxLength) length++; for (int i = length - 1; i > insertPos; i--) { entries [i].fitness = entries [i - 1].fitness; ArrayCopy (entries [i].decision, entries [i - 1].decision, 0, 0, WHOLE_ARRAY); } // Вставляем новый элемент entries [insertPos].fitness = fit; ArrayCopy (entries [insertPos].decision, coord, 0, 0, WHOLE_ARRAY); } }; // Расширенная структура исследователя struct S_Researcher { double x []; // текущая позиция double v []; // направление движения double b []; // личный лучший результат double rho []; // вероятности публикации в журналах double s; // стратегия управления средствами int m; // количество средств double f; // fitness текущей позиции double fb; // fitness лучшей позиции bool alive; // флаг активности void Init (int coords, int journalsNum) { if (ArraySize (x) != coords) { ArrayResize (x, coords); ArrayResize (v, coords); ArrayResize (b, coords); } if (ArraySize (rho) != journalsNum) { ArrayResize (rho, 0); ArrayResize (rho, journalsNum); } f = -DBL_MAX; fb = -DBL_MAX; m = 0; s = 0.5; alive = true; } };
Напишем класс "C_AO_CoSO", который является реализацией алгоритма оптимизации "Community of Scientist Optimization" (CoSO). Класс "C_AO_CoSO" наследуется от базового класса "C_AO" и предполагает наличие общих свойств и методов для различных алгоритмов оптимизации.
Устанавливаются значения по умолчанию для различных управляющих параметров CoSO:
- начальный размер популяции "исследователей";
- общее количество "средств" (ресурсов), которые могут быть выделены (в метафоре ученых это могут быть гранты, которые они используют для своей "работы" (поиска решения));
- количество "журналов", в которых исследователи могут публиковать свои "открытия" (лучшие решения);
- максимальное количество статей/открытий, которое может содержать один "журнал";
- параметр "инерции", контролирующий влияние предыдущего направления движения.
- phi1 = 1.5; — когнитивный параметр, отражает индивидуальное влияние на движение исследователя (тяга к собственным лучшим открытиям);
- phi2 = 1.5; — социальный параметр, определяет, насколько сильно исследователь ориентируется на публикации в журналах;
- omegaMin = 0.2; — минимальный процент "аутсайдеров";
- omegaMax = 0.5; — максимальный процент "аутсайдеров";
- epsilonPlus = 0.2; — шаг увеличения разнообразия;
- epsilonMinus = 0.1; — шаг уменьшения разнообразия.
Init () — метод инициализации алгоритма. Принимает диапазоны поиска (минимальные, максимальные значения) и шаги для каждого параметра, а также количество эпох "epochsP".
Moving () — метод отвечает за "перемещение" (обновление позиций) исследователей в пространстве поиска, основываясь на их "скоростях" и "направлениях".
Revision () — метод отвечает за обновление лучшего глобального решения, найденного всеми исследователями до текущего момента.
Приватные поля (private): динамический массив структур "S_Researcher". Каждый элемент этой структуры представляет одного "исследователя" и содержит информацию о его текущей позиции, скорости, лучшем найденном решении, "жизнеспособности" (alive), "fitness" (f) и т.д. Динамический массив структур "S_Journal", где каждая структура хранит набор лучших решений, опубликованных исследователями в данном "журнале". Текущий процент "аутсайдеров". Начальное стандартное отклонение. Текущий фактический размер популяции. Он может меняться в процессе выполнения алгоритма. Максимально допустимый размер популяции.
struct S_GlobalReport — вложенная структура для хранения информации о лучшем глобальном решении: "fitness" (значение целевой функции) и "index" (индекс исследователя, который нашел это решение).
S_GlobalReport globalReport [] — массив для хранения глобальных отчетов.
Приватные методы алгоритма:
- UpdateDirection ()— обновляет направление движения (или "скорость") для конкретного исследователя с индексом "idx".
- SubmitToJournal () — позволяет исследователю с индексом "опубликовать" свое текущее лучшее решение в одном из "журналов".
- AssignFunds () — метод для распределения "средств" между исследователями. В CoSO гранты могут влиять на поведение или способность исследователей к поиску.
- HireResearchers () — метод создает новых исследователей.
- CreateOutsiders () — создает "аутсайдеров", специальных исследователей, которые могут вести более агрессивный или случайный поиск, чтобы избежать застревания в локальных оптимумах.
- ComputeStdDev () — вычисляет стандартное отклонение популяции, служит индикатором "разнообразия" или "сходимости" популяции.
- UpdateOmega () — обновляет текущий параметр "omegaCurrent".
- SelectJournal () — выбирает журнал для публикации на основе заданных вероятностей.
- NormalizeProbabilities () — нормализует массив вероятностей так, чтобы их сумма равнялась единице.
- CompactPopulation () — метод для "уплотнения" популяции, удаления наименее эффективных исследователей, т.е., управление размером популяции.
//———————————————————————————————————————————————————————————————————— class C_AO_CoSO : public C_AO { public: //---------------------------------------------------------- ~C_AO_CoSO () { } C_AO_CoSO () { ao_name = "CoSO"; ao_desc = "Community of Scientist Optimization"; ao_link = "https://www.mql5.com/ru/articles/18886"; popSize = 30; // начальный размер популяции totalFunds = 150; // общее количество средств journalsNum = 3; // количество журналов journalLen = 10; // длина журнала omega = 0.7; // параметр инерции ArrayResize (params, 5); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "totalFunds"; params [1].val = totalFunds; params [2].name = "journalsNum"; params [2].val = journalsNum; params [3].name = "journalLen"; params [3].val = journalLen; params [4].name = "omega"; params [4].val = omega; //---------------------------------------------------------------- phi1 = 1.5; // когнитивный параметр phi2 = 1.5; // социальный параметр omegaMin = 0.2; // минимальный процент аутсайдеров omegaMax = 0.5; // максимальный процент аутсайдеров epsilonPlus = 0.2; // шаг увеличения разнообразия epsilonMinus = 0.1; // шаг уменьшения разнообразия } void SetParams () { popSize = (int)params [0].val; totalFunds = (int)params [1].val; journalsNum = (int)params [2].val; journalLen = (int)params [3].val; omega = params [4].val; } bool Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0); void Moving (); void Revision (); //------------------------------------------------------------------ int totalFunds; // общее количество средств int journalsNum; // количество журналов int journalLen; // длина журнала double omega; // параметр инерции double phi1; // когнитивный параметр double phi2; // социальный параметр double omegaMin; // минимальный процент аутсайдеров double omegaMax; // максимальный процент аутсайдеров double epsilonPlus; // шаг увеличения разнообразия double epsilonMinus; // шаг уменьшения разнообразия private: //--------------------------------------------------------- S_Researcher researchers []; // массив исследователей S_Journal journals []; // массив журналов double omegaCurrent; // текущий процент аутсайдеров double sigma0; // начальное стандартное отклонение int actualPopSize; // текущий размер популяции int maxPopSize; // максимальный размер популяции double socialComponent []; // кэш для социального компонента struct S_GlobalReport { double fitness; int index; }; S_GlobalReport globalReport []; // Методы алгоритма void UpdateDirection (int idx); void SubmitToJournal (int idx); void AssignFunds (int availableFunds); void HireResearchers (int idx); void CreateOutsiders (int outsiderFunds); double ComputeStdDev (); void UpdateOmega (); int SelectJournal (const double &probs []); void NormalizeProbabilities (double &probs []); void CompactPopulation (); }; //————————————————————————————————————————————————————————————————————
Метод "Init" является частью класса "C_AO_CoSO" и отвечает за подготовку всех необходимых структур и параметров перед началом работы алгоритма. Сначала происходит стандартная инициализация, связанная с диапазонами параметров поиска (минимальные, максимальные значения и шаг), с установкой количества эпох (epochsP). Если эта стандартная инициализация не удалась, функция возвращает "false". Затем инициализируются внутренние переменные состояния алгоритма:
- actualPopSize — текущий размер популяции исследователей,
- maxPopSize — максимальный допустимый размер популяции (или выделенный объем памяти под исследователей),
- sigma0 — начальное значение стандартного отклонения, которое будет вычислено позже,
- omegaCurrent — текущий параметр "omega", инициализируемый как среднее арифметическое между "omegaMin" и "omegaMax".
Далее следуют проверки корректности входных параметров:
- totalFunds — общее количество "средств" должно быть не меньше размера популяции, каждому исследователю должно быть выделено некоторое количество средств или грантов;
- journalsNum — количество "журналов" должно быть не меньше одного;
- journalLen — длина каждого "журнала" также должна быть не меньше одного;
- omega (глобальный параметр) — должен находиться в диапазоне от 0.0 до 1.0.
После проверки параметров происходит "полная очистка от предыдущих запусков", что означает сброс размеров динамических массивов "researchers", "journals", "globalReport" и "socialComponent" до нуля, алгоритм всегда стартует с чистого состояния. Снова сбрасываются уже упомянутые переменные состояния (actualPopSize, maxPopSize, sigma0).
Затем происходит инициализация "журналов": массив "journals" изменяет размер в соответствии с "ournalsNum". Каждый журнал в этом массиве инициализируется с заданной длиной "journalLen" и количеством координат "coords".
Инициализация исследователей. Задается "maxPopSize" как минимум из утроенного "popSize" (размера популяции). Это создает "запас" для возможных изменений размера популяции (алгоритм создает новых исследователей). Вычисляется "fundsPerResearcher" - количество средств, которое будет выделено каждому исследователю (общее количество средств делится на размер популяции). Далее следует цикл по всем исследователям.
Каждый исследователь инициализируется с количеством координат "coords" и количеством журналов "journalsNum". Флаг "alive" устанавливается в "true" только для первых "popSize" исследователей, остальные пока неактивны. Для активных исследователей присваивается вычисленное количество средств "fundsPerResearcher". Их "стратегия управления средствами" "s" инициализируется случайным образом. Инициализируются их позиции "x", лучшие личные позиции "b" и векторы движения "v". Позиции "x" и "b" устанавливаются случайным образом в заданном диапазоне (rangeMin - rangeMax, с учетом шага "rangeStep"). Векторы движения "v" инициализируются малым случайным значением из нормального распределения. Инициализируются вероятности "rho" для каждого журнала случайными значениями.
Вызывается функция "NormalizeProbabilities", которая нормирует эти вероятности. После инициализации всех исследователей, вычисляется начальное стандартное отклонение "sigma0", которое характеризует разброс позиций исследователей по всем координатам. Если "sigma0" оказывается равным нулю (например, если все исследователи находятся в одной точке), оно устанавливается в 1.0 для предотвращения деления на 0. Параметр "omegaCurrent" снова устанавливается как среднее между "omegaMin" и "omegaMax".
В конце позиции всех инициализированных исследователей (popSize) копируются в "стандартный массив агентов" "a". Таким образом, функция "Init" полностью подготавливает среду для работы оптимизационного алгоритма, инициализируя всех агентов "исследователей", их параметры, "журналы" для хранения результатов, а также внутренние параметры управления алгоритмом.
//———————————————————————————————————————————————————————————————————— bool C_AO_CoSO::Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0) { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //------------------------------------------------------------------ // Инициализация переменных состояния actualPopSize = 0; maxPopSize = 0; sigma0 = 0; omegaCurrent = omegaMin + (omegaMax - omegaMin) / 2.0; // Проверка корректности параметров if (totalFunds < popSize) totalFunds = popSize; if (journalsNum < 1) journalsNum = 1; if (journalLen < 1) journalLen = 1; if (omega < 0.0) omega = 0.0; if (omega > 1.0) omega = 1.0; // Полная очистка от предыдущих запусков ArrayResize (researchers, 0); ArrayResize (journals, 0); ArrayResize (globalReport, 0); ArrayResize (socialComponent, 0); // Сброс параметров actualPopSize = 0; maxPopSize = 0; sigma0 = 0; // Инициализация журналов ArrayResize (journals, journalsNum); for (int i = 0; i < journalsNum; i++) { journals [i].Init (journalLen, coords); } // Инициализация массива исследователей с запасом maxPopSize = MathMin (popSize * 3, 300); // Ограничиваем максимальный размер ArrayResize (researchers, maxPopSize); ArrayResize (socialComponent, coords); actualPopSize = popSize; int fundsPerResearcher = totalFunds / popSize; for (int i = 0; i < maxPopSize; i++) { researchers [i].Init (coords, journalsNum); researchers [i].alive = (i < popSize); if (i < popSize) { researchers [i].m = fundsPerResearcher; researchers [i].s = u.RNDprobab (); // Инициализация позиции for (int c = 0; c < coords; c++) { researchers [i].x [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]); researchers [i].x [c] = u.SeInDiSp (researchers [i].x [c], rangeMin [c], rangeMax [c], rangeStep [c]); researchers [i].b [c] = researchers [i].x [c]; researchers [i].v [c] = u.GaussDistribution (0.0, -0.01, 0.01, 1); } // Инициализация вероятностей журналов for (int j = 0; j < journalsNum; j++) { researchers [i].rho [j] = u.RNDprobab (); } NormalizeProbabilities (researchers [i].rho); } } // Вычисляем начальное стандартное отклонение sigma0 = ComputeStdDev (); if (sigma0 == 0) sigma0 = 1.0; // Защита от деления на ноль omegaCurrent = omegaMin + (omegaMax - omegaMin) / 2.0; // Копируем исследователей в стандартный массив агентов for (int i = 0; i < popSize; i++) { ArrayCopy (a [i].c, researchers [i].x, 0, 0, WHOLE_ARRAY); } return true; } //————————————————————————————————————————————————————————————————————
Метод "Moving" является центральной частью итерационного процесса алгоритма, выполняет один шаг в поиске оптимального решения, моделируя поведение "исследователей" и их взаимодействие. В начале функции, если это первый вызов после инициализации (revision = false), она просто устанавливает "revision" в "true" и выходит. Далее следуют основные шаги алгоритма, которые выполняются на каждой итерации.
Обновление пригодности исследователей. Для каждого действующего исследователя (из текущей популяции) его значение пригодности (fitness) берется из общего массива "a", где хранятся результаты оценки пригодности всех агентов. Затем проверяется, является ли текущая пригодность исследователя лучше, чем его ранее зарегистрированная лучшая личная пригодность, и если да, то "fb" обновляется, и лучшая позиция исследователя "b" также сохраняется как его текущая позиция "x".
Подача результатов в журналы. Каждый активный исследователь "подает" свои актуальные результаты (текущую пригодность и позицию) в один или несколько "журналов". Детали этого процесса инкапсулированы в функции "SubmitToJournal", которая выбирает журнал на основе вероятностей "rho" исследователя и добавляет туда его результат, если он достаточно хорош.
Сбор глобального отчета и подсчет доступных средств. На этом шаге происходит переоценка статуса исследователей и подготовка к распределению ресурсов. Для каждого живого исследователя количество его "средств" (m) уменьшается на единицу, символизируя затраты на текущую итерацию. Общее количество доступных средств "availableFunds" увеличивается. Если у исследователя после траты средств остались средства (m > 0), он считается способным продолжить работу, и будет включен в "глобальный отчет". Если средства закончились, исследователь "умирает" (alive = false). Формируется "globalReport" — массив, содержащий пригодность и индекс только тех исследователей, которые остаются действующими и имеют средства.
Сортировка глобального отчета. Элементы в "globalReport" сортируются по убыванию значения "fitness" (от лучшего к худшему) с использованием простого алгоритма пузырьковой сортировки. Это позволяет быстро определить наиболее успешных исследователей.
Распределение средств. Функция "AssignFunds" вызывается для перераспределения "availableFunds" между действующими исследователями, лучшие исследователи (согласно "globalReport") получают больше средств, стимулируя их дальнейшую активность, в то время как менее успешные могут получить меньше или ничего, что может привести к их "смерти" в следующих итерациях.
Найм новых исследователей существующими. Действующие исследователи, у которых осталось достаточно средств (m > 1), могут "нанимать" новых исследователей. Это механизм увеличения популяции или создания новых агентов на основе успешных существующих. Детали в функции "HireResearchers".
Обновление направления и позиции. Для каждого действующего исследователя вызывается функция "UpdateDirection", которая вычисляет новый вектор движения "v" исследователя, основываясь на его личном лучшем результате "b", лучшем результате из журналов, социальном компоненте или других факторах алгоритма. Позиция исследователя "x" обновляется путем добавления вектора движения "v". Позиция проверяется на предмет выхода за границы допустимого диапазона и корректируется при необходимости, а также "дискретизируется" или "округляется" до ближайшего допустимого шага "rangeStep".
Обновление параметра разнообразия. Вызывается функция "UpdateOmega", которая корректирует параметр "omegaCurrent" алгоритма. Этот параметр используется для контроля баланса между исследованием (поиск новых областей) и эксплуатацией (уточнение найденных решений), изменяя его динамически в течение работы алгоритма для поддержания разнообразия популяции.
Компактизация популяции. Функция "CompactPopulation" вызывается для удаления неактивных (alive = false) исследователей из массива "researchers", эффективно уменьшая его размер и освобождая память.
Копирование позиций в массив агентов. Наконец, текущие позиции всех действующих исследователей копируются в массив "a". Размер "a" обновляется в соответствии с "actualPopSize". Глобальная переменная "popSize" также обновляется до нового "actualPopSize".
Таким образом, функция "Moving" инкапсулирует полный жизненный цикл итерации алгоритма CoSO, включающий оценку, социальное взаимодействие ("журналы"), управление ресурсами, динамическое изменение популяции и перемещение агентов в пространстве поиска.
//———————————————————————————————————————————————————————————————————— void C_AO_CoSO::Moving () { if (!revision) { revision = true; return; } //--- Основные шаги CoSO: // 1. Обновление fitness исследователей из массива агентов int aSize = ArraySize (a); for (int i = 0, j = 0; i < actualPopSize && j < aSize; i++) { if (!researchers [i].alive) continue; researchers [i].f = a [j].f; // Обновление личного лучшего if (researchers [i].f > researchers [i].fb) { researchers [i].fb = researchers [i].f; ArrayCopy (researchers [i].b, researchers [i].x, 0, 0, WHOLE_ARRAY); } j++; } // 2. Подача результатов в журналы for (int i = 0; i < actualPopSize; i++) { if (researchers [i].alive) SubmitToJournal (i); } // 3. Сбор глобального отчета и подсчет доступных средств int availableFunds = 0; int reportSize = 0; // Предварительный подсчет размера отчета for (int i = 0; i < actualPopSize; i++) { if (!researchers [i].alive) continue; researchers [i].m--; // Тратим 1 единицу средств за итерацию availableFunds++; if (researchers [i].m > 0) reportSize++; else researchers [i].alive = false; } // Заполнение глобального отчета ArrayResize (globalReport, reportSize); int idx = 0; for (int i = 0; i < actualPopSize && idx < reportSize; i++) { if (researchers [i].alive && researchers [i].m > 0) { globalReport [idx].fitness = researchers [i].f; globalReport [idx].index = i; idx++; } } // 4. Быстрая сортировка глобального отчета for (int i = 0; i < reportSize - 1; i++) { for (int j = i + 1; j < reportSize; j++) { if (globalReport [i].fitness < globalReport [j].fitness) { S_GlobalReport temp = globalReport [i]; globalReport [i] = globalReport [j]; globalReport [j] = temp; } } } // 5. Распределение средств AssignFunds (availableFunds); // 6. Найм новых исследователей существующими for (int i = 0; i < actualPopSize; i++) { if (researchers [i].alive && researchers [i].m > 1) HireResearchers (i); } // 7. Обновление направления и позиции для каждого исследователя for (int i = 0; i < actualPopSize; i++) { if (!researchers [i].alive) continue; UpdateDirection (i); // Обновление позиции for (int c = 0; c < coords; c++) { researchers [i].x [c] += researchers [i].v [c]; // Контроль границ if (researchers [i].x [c] < rangeMin [c]) researchers [i].x [c] = rangeMin [c]; if (researchers [i].x [c] > rangeMax [c]) researchers [i].x [c] = rangeMax [c]; researchers [i].x [c] = u.SeInDiSp (researchers [i].x [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } // 8. Обновление параметра разнообразия UpdateOmega (); // 9. Компактификация популяции CompactPopulation (); // 10. Копируем позиции в массив агентов для вычисления fitness ArrayResize (a, actualPopSize); idx = 0; for (int i = 0; i < maxPopSize && idx < actualPopSize; i++) { if (researchers [i].alive) { a [idx].Init (coords); ArrayCopy (a [idx].c, researchers [i].x, 0, 0, WHOLE_ARRAY); idx++; } } popSize = actualPopSize; // Обновляем размер популяции } //————————————————————————————————————————————————————————————————————
Функция "UpdateDirection" отвечает за обновление вектора движения "v" для отдельного исследователя в алгоритме CoSO. Этот процесс является ключевым для перемещения агентов (исследователей) в пространстве поиска и позволяет им исследовать новые области, а также использовать информацию, полученную как лично, так и от других агентов. Функция принимает на вход один параметр — "idx" (индекс исследователя, для которого необходимо обновить направление).
В начале функции генерируются две случайные величины от 0 до 1: "beta1", используемое как коэффициент для личного компонента и "beta2", используемое как коэффициент для социального компонента. Далее происходит вычисление социального компонента, при этом массив "socialComponent" обнуляется, что обеспечивает его чистоту перед каждым новым расчетом.
Затем цикл проходит по всем "журналам", доступным алгоритму, и для каждого журнала проверяется, содержит ли он записи (length > 0), так как пустой журнал не может предоставить информацию для социального компонента. Если журнал не пуст, из него случайно выбирается одна запись (entryIdx).
Для каждой координаты (размерности пространства поиска), социальный компонент обновляется. Вклад от выбранной записи журнала вычисляется как вероятность выбора данного журнала исследователем (rho[j]) * (позиция из журнала — текущая позиция исследователя). Эти вклады суммируются по всем журналам, формируя общее влияние социальной информации на движение исследователя. После вычисления социального компонента происходит обновление вектора движения исследователя, новый вектор движения (v [c]) = инерционный компонент + личный компонент + социальный компонент.
Разберем каждую часть:
Инерционный компонент: omega * researchers [idx]. v [c]. Здесь "omega" (параметр "omegaCurrent", установленный в функции "Init" и обновляемый в "Moving") является коэффициентом инерции. Он определяет, насколько исследователь сохранит свое предыдущее направление движения. Большое значение означает, что исследователь будет продолжать двигаться в том же направлении; малое означает, что он будет быстрее менять направление под влиянием других факторов.
Личный компонент: phi1 * beta1 * (researchers [idx]. b [c] — researchers [idx]. x [c]), где "phi1" — это коэффициент ускорения, связанный с личным опытом, а "beta1" — случайный множитель, добавляющий стохастичность.
(researchers [idx]. b [c] — researchers [idx]. x [c]) — это вектор, указывающий от текущей позиции исследователя к его лучшей ранее найденной личной позиции (fb). Этот компонент тянет исследователя обратно к его собственным успешным местам.
- поддерживать некоторое инерционное движение;
- "помнить" и возвращаться к своим собственным лучшим находкам;
- изучать и следовать за успешными находками других исследователей.
В результате, "UpdateDirection" вычисляет новый вектор движения для исследователя, который будет использован в следующем шаге для фактического обновления его позиции в пространстве поиска.
//———————————————————————————————————————————————————————————————————— void C_AO_CoSO::UpdateDirection (int idx) { double beta1 = u.RNDprobab (); double beta2 = u.RNDprobab (); // Социальный компонент ArrayInitialize (socialComponent, 0); for (int j = 0; j < journalsNum; j++) { if (journals [j].length > 0) { int entryIdx = u.RNDminusOne (journals [j].length); for (int c = 0; c < coords; c++) { socialComponent [c] += researchers [idx].rho [j] * (journals [j].entries [entryIdx].decision [c] - researchers [idx].x [c]); } } } // Обновление направления for (int c = 0; c < coords; c++) { researchers [idx].v [c] = omega * researchers [idx].v [c] + phi1 * beta1 * (researchers [idx].b [c] - researchers [idx].x [c]) + phi2 * beta2 * socialComponent [c]; } } //————————————————————————————————————————————————————————————————————
Функция "SubmitToJournal" описывает процесс, в котором отдельный исследователь "публикует" свои текущие результаты в одном из доступных "журналов". Это ключевой механизм для распространения информации и социального обучения в рамках алгоритма CoSO. Функция принимает один параметр: "idx" — индекс исследователя, который хочет отправить свои результаты в журнал. Работа функции состоит из двух основных шагов:
Выбор журнала. Сначала вызывается вспомогательная функция "SelectJournal". Эта функция принимает на вход массив "rho" исследователя. Массив "rho" (представляющий собой вероятности или предпочтения) определяет, с какой вероятностью данный исследователь предпочитает подавать свои результаты в тот или иной журнал. Функция "SelectJournal" на основе этих вероятностей случайным образом выбирает один из доступных журналов и возвращает его индекс (journalIdx).
Добавление записи в журнал. Как только журнал выбран, на него вызывается метод "Add". В этот метод передаются два параметра:
- researchers [idx]. f — текущее значение пригодности (fitness) исследователя. Это "качество" или "успешность" найденного им решения.
- researchers [idx]. x — текущая позиция (координаты в пространстве поиска) исследователя. Это само "решение", которое дало такую пригодность.
Метод "Add" в выбранном журнале (журнал по индексу journalIdx) отвечает за фактическое добавление этой информации. Таким образом, журнал хранит коллективные знания или лучшие практики, найденные различными исследователями.
В целом, "SubmitToJournal" моделирует процесс публикации научных результатов, где исследователи выбирают, куда отправить свои работы, и затем эти работы становятся доступными для ознакомления другим. Это позволяет алгоритму накапливать и распространять успешные решения среди популяции агентов.
//———————————————————————————————————————————————————————————————————— void C_AO_CoSO::SubmitToJournal (int idx) { int journalIdx = SelectJournal (researchers [idx].rho); journals [journalIdx].Add (researchers [idx].f, researchers [idx].x); } //————————————————————————————————————————————————————————————————————
Функция "SelectJournal", которая предназначена для выбора одного журнала из набора доступных, основываясь на заданных вероятностях. Это является реализацией выбора по колесу рулетки (roulette wheel selection) или пропорционального выбора, где каждый журнал имеет определённый "вес" или "предпочтение". Функция принимает один параметр: probs [] — массив чисел с плавающей точкой, представляющий собой вероятности или относительные предпочтения для выбора каждого журнала.
Работа функции происходит следующим образом: в начале генерируется случайное число "rnd", равномерно распределенное между 0 (включительно) и 1 (исключительно), оно будет использовано для определения, какой журнал будет выбран. Переменная "cumSum" инициализируется нулем и будет накапливать суммы вероятностей по мере прохождения по массиву "probs".
Обработка крайнего случая. Если цикл завершается, и ни один журнал не был выбран (что теоретически может произойти из-за крайне малой точности вычислений, если "rnd" равно 1 и сумма всех "probs" ровно 1, или если сумма "probs" немного меньше 1), функция возвращает индекс последнего журнала (probsSize - 1). Это гарантирует, что журнал всегда будет выбран, даже в пограничных или патологических случаях.
По сути, эта функция создает ряд "слотов" на числовой прямой от 0 до 1, где длина каждого слота пропорциональна вероятности соответствующего журнала. Затем она бросает "дротик" (случайное число "rnd") и смотрит, в какой слот он попадает. Это обеспечивает, что журналы с более высокими вероятностями будут выбираться чаще.
//———————————————————————————————————————————————————————————————————— int C_AO_CoSO::SelectJournal (const double &probs []) { double rnd = u.RNDprobab (); double cumSum = 0; int probsSize = ArraySize (probs); for (int i = 0; i < probsSize; i++) { cumSum += probs [i]; if (rnd <= cumSum) return i; } return probsSize - 1; } //————————————————————————————————————————————————————————————————————
Заключение
Итак, мы подробно рассмотрели теорию алгоритма 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: TWAP, VWAP и ордера Iceberg
Создание торговой панели администратора на MQL5 (Часть VIII): Панель аналитики
Торгуем опционы без опционов (Часть 2): Использование в реальной торговле
Оптимизация и тонкая настройка исходного кода для улучшения результатов тестирования на истории
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Вы принимаете политику сайта и условия использования