MetaTrader 5 / Тестер
preview
Алгоритм искусственных водорослей — Artificial Algae Algorithm (AAA)

Алгоритм искусственных водорослей — Artificial Algae Algorithm (AAA)

MetaTrader 5 — Тестер | 19 августа 2024, 16:11
44 0
Andrey Dik
Andrey Dik

Содержание

  1. Введение
  2. Реализация алгоритма
  3. Результаты тестов


Введение

Водоросли, одни из самых древних организмов на Земле, играют ключевую роль в водных экосистемах. Существует более 45,000 видов водорослей, которые могут значительно отличаться по цвету, форме, размерам и среде обитания. Они обеспечивают жизнь водной среды, так как являются основой рациона многих видов животных, кроме того, они производят кислород через фотосинтез, что делает их важными для поддержания жизни на планете. Эти живые организмы могут быть как одноклеточными, так и многоклеточными, и часто образуют колонии, которые функционируют как единое целое.

Одноклеточные водоросли могут делиться митозом, создавая новые клетки, которые остаются соединенными друг с другом, образуя колонию. Многоклеточные водоросли могут размножаться с помощью спор, которые распространяются в воде и прорастают в новые организмы, также образуя колонии. Эти удивительные организмы демонстрируют, как биологические процессы могут быть использованы для создания инновационных решений в математическом моделировании и оптимизации.

Алгоритм Artificial Algae Algorithm (AAA), предложенный Uymaz, Tezel и Yel в 2015 году, представляет собой сочетание биологического природного явления и математической элегантности. Этот метаэвристический алгоритм оптимизации черпает свое вдохновение из удивительного мира микроводорослей, чьи колониальные повадки и адаптивные способности стали основой для создания алгоритмической модели оптимизации. Инспирация способностью микроводорослей перемещаться к источнику света, адаптироваться к изменяющимся условиям окружающей среды и размножаться митозом для улучшения фотосинтеза, послужила разработкой AAA, чтобы математически смоделировать эти уникальные свойства.

Алгоритм включает три ключевых процесса: спиральное движение, эволюционный процесс и процесс адаптации. Спиральное движение моделирует трехмерное перемещение водорослей в питательном растворе, позволяя им находить оптимальные условия для роста. Эволюционный процесс обеспечивает размножение колоний водорослей в наиболее подходящих условиях, способствуя их развитию и улучшению решений. Процесс адаптации помогает менее успешным колониям уподобиться наибольшей колонии, обеспечивая их выживание и дальнейшее развитие.


Реализация алгоритма

Алгоритм искусственных водорослей (AAA) был разработан для математического моделирования свойств водорослей, таких как их спиральное движение, процесс адаптации и эволюционный процесс. Каждая колония водорослей представляет собой возможное кандидатное решение для задачи оптимизации (а каждая клетка колонии — отдельная координата), и эти колонии объединяются, чтобы сформировать популяцию водорослей. Каждая колония характеризуется своим размером, который отражает качество представляемого решения.

В эволюционном процессе колонии водорослей, которые достигают более подходящих условий окружающей среды, развиваются и растут. Колонии, которые не могут получить подходящие условия, не развиваются и умирают. После завершения процесса спирального движения, колонии водорослей ранжируются по их размеру. Случайно выбранная клетка самой большой колонии копируется в ту же клетку самой маленькой колонии, завершая эволюционный процесс.

Колонии водорослей совершают спиральное движение в воде, чтобы достичь лучших условий окружающей среды. Их энергия пропорциональна размеру колонии. В процессе движения они теряют энергию, но если достигают лучшей среды, восстанавливают половину потерянной энергии. Энергия колонии прямо пропорциональна концентрации питательных веществ, поэтому чем больше энергии у колонии, тем выше частота её движения.

Сила трения является еще одним немаловажным фактором, влияющим на движение в воде. Колонии с меньшей площадью поверхности имеют больший диапазон движения, так как их поверхность трения меньше. Колонии, достигшие лучших условий, имеют большую площадь поверхности трения из-за своего размера, следовательно, колонии замедляют свои движения, что помогает им исследовать окрестности найденного решения и увеличивать свои локальные поисковые возможности.

Процесс адаптации происходит, когда колонии водорослей, не достигшие достаточного развития во время спирального движения, пытаются уподобиться самой большой колонии. Колония с наибольшим значением голода подвергается этому процессу. В начале оптимизации значение голода всех колоний равно нулю. В процессе спирального движения значение голода колоний, не нашедших лучшее решение, увеличивается на единицу. После спирального движения и эволюционного процесса, колония с наибольшим значением голода входит в период адаптации. Однако процесс адаптации не происходит на каждой итерации. Сначала выбирается случайное значение между 0 и 1. Если это значение меньше параметра адаптации, выполняется процесс адаптации.

    После рассмотрения представленной модели свойств водорослей, перейдем к написанию псевдокода AAA:

    Инициализация:
        Создать популяцию агентов
        Для каждого агента:
            Инициализировать случайную позицию в пространстве поиска
            Инициализировать параметры (размер, энергия, голод и т.д.)

    Основной цикл:
        Пока не достигнут критерий остановки:
            Для каждого агента:
                Выполнить Движение
                Оценить фитнес-функцию
            
            Обновить лучшее найденное решение
            
            Для каждого агента:
                Обновить энергию
                Обновить размер
                Обновить голод
            
            Выполнить процесс эволюции
            Выполнить процесс адаптации

    Функция Движение:
        Для каждого агента:
            Выбрать другого агента с помощью турнирной селекции
            Для каждой координаты:
                Обновить позицию агента с использованием спиральной тригонометрической формулы движения
                и коэффициента трения

    Функция ПроцессЭволюции:
        Найти агента с наименьшим размером
        Заменить его координаты координатами случайно выбранного агента

    Функция ПроцессАдаптации:
        Найти агента с наибольшим голодом
        С определенной вероятностью:
            Найти агента с наибольшим размером
            Обновить координаты голодающего агента, приближая их к координатам
            большого агента
            Сбросить параметры голодающего агента

    Функция РасчетЭнергии:
        Рассчитать энергию на основе размера колонии, концентрации питательных
        веществ и текущей скорости роста

    Функция ТурнирнаяСелекция:
        Выбрать двух случайных агентов
        Вернуть агента с лучшим значением фитнес-функции

    Перечислим формулы, используемые в алгоритме. Формулы 1-5 относятся непосредственно к реализации основной логики алгоритма.

    1. Инициализация популяции: популяция = [[x1_1, x1_2, ..., x1_D], [x2_1, x2_2, ..., x2_D], [xN_1, xN_2, ..., xN_D]], где xj_i  — i-я клетка j-й колонии водорослей, D — размерность колонии, N — размер популяции.

    2. Спиральное движение: x'i_j = xi_j + α * cos (θ) * τ (Xi) * p; y'i_j = yi_j + α * sin (θ) * τ (Xi) * p; z'i_j = zi_j + r * v, где (x'i_j, y'i_j, z'i_j) — новые координаты i-й колонии, α, θ ∈ [0, 2π], p ∈ [-1, 1], r ∈ [-1, 1], v ∈ [-1, 1], τ (Xi)  — площадь трения i-й колонии.

    3. Эволюционный процесс: biggest = max (Gi), m = случайно выбранная клетка, smallest.xm = biggest.xm

    4. Адаптационный процесс: starving = max (Ai); starving.x = starving.x + (biggest.x - starving.x) * rand

    5. Монод-модель роста водорослей: μt = μtmax * St / (St + Kt), где μt - скорость роста водорослей в момент времени t, μtmax  —максимальная скорость роста, St — размер колонии в момент времени t, Kt — константа полунасыщения.

    6. Площадь трения: τ (Xi) = 2π * (3√ (3*Gi) / (4π))^2, где τ (Xi)  — площадь трения i-й колонии, Gi — размер i-й колонии.

    7. Выбор колонии для спирального движения: используется турнирный отбор для выбора колонии, которая будет перемещаться. Об этом поговорим подробнее ниже.

    8. Выбор случайных измерений для спирального движения: p, r, v  — случайно выбранные индексы измерений, отличные друг от друга.

    9. Выбор соседней колонии для спирального движения: Xj  — колония, выбранная методом турнирного отбора, к которой будет двигаться колония Xi.

    10. Начальное значение голода всех колоний: Ai = 0 для всех i.

    11. Увеличение голода колоний, не улучшивших решение: Ai = Ai + 1, если колония не нашла лучшего решения.

    12. Выбор колонии с максимальным голодом: starving = max (Ai).

    13. Вероятность проведения адаптационного процесса: rand < Ap, где Ap — параметр адаптации.

    Формулы 6-13 описывают дополнительные детали реализации алгоритма, такие как расчет площади трения, выбор колоний для перемещения, управление голодом колоний и вероятность проведения адаптационного процесса.

    Монод-модель или модель Монода достаточно часто используется для описания роста и поведения популяций в биологических системах. Она основана на работах Жака Монода, французского биохимика, который изучал кинетику роста микроорганизмов. Скорость роста популяции зависит от концентрации субстрата (питательного вещества). При низких концентрациях субстрата скорость роста пропорциональна концентрации, а при высоких концентрациях достигает максимума. В алгоритмах оптимизации Монод-модель используется для моделирования роста и адаптации популяций в эволюционных алгоритмах. В процессе оптимизации параметры популяции изменяются в зависимости от доступных ресурсов, что позволяет более точно моделировать реальные биологические процессы.

    Хотел бы акцентировать ваше внимание на турнирном отборе для выбора колонии, такой метод мы не использовали ранее в алгоритмах. Для того чтобы наглядно увидеть распределения вероятностей выбора особей по популяции при таком способе селекции, напишем скрипт и сделаем распечатку результатов. Выделенный синим цветом участок кода непосредственно участвует в формировании распределения при селекции.

    input int      PopSize = 50;
input int      Count   = 1000000;
input int      BarWidth = 50; // Ширина гистограммы в символах

void OnStart()
{
  int pop[];
  ArrayResize(pop, PopSize);

  for(int i = 0; i < PopSize; i++) pop[i] = PopSize - i;

  Print("Исходная популяция:");
  ArrayPrint(pop);

  int tur[];
  ArrayResize(tur, PopSize);
  ArrayInitialize(tur, 0);

  int ind1 = 0, ind2 = 0;

  for(int i = 0; i < Count; i++)
  {
    ind1 = MathRand() % PopSize;
    ind2 = MathRand() % PopSize;

    if(pop[ind1] > pop[ind2]) tur[ind1]++;
    else                      tur[ind2]++;
  }

  Print("Распределение вероятностей (в процентах):");

  double maxPercentage = 0;
  double percentages[];
  ArrayResize(percentages, PopSize);

  for(int i = 0; i < PopSize; i++)
  {
    percentages[i] = (double)tur[i] / Count * 100;
    if(percentages[i] > maxPercentage) maxPercentage = percentages[i];
  }

  for(int i = 0; i < PopSize; i++)
  {
    int barLength = (int)((percentages[i] / maxPercentage) * BarWidth);
    string bar = "";
    for(int j = 0; j < barLength; j++) bar += "|";

    PrintFormat("%2d: %5.2f%% %s", i, percentages[i], bar);
  }
}

    Ниже результат работы скрипта для визуализации распределения вероятностей выбора каждой особи в популяции:

    Исходная популяция:
    20 19 18 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1
    Распределение вероятностей (в процентах):
     0:  9.76% ||||||||||||||||||||||||||||||||||||||||||||||||||
     1:  9.24% |||||||||||||||||||||||||||||||||||||||||||||||
     2:  8.74% ||||||||||||||||||||||||||||||||||||||||||||
     3:  8.22% ||||||||||||||||||||||||||||||||||||||||||
     4:  7.77% |||||||||||||||||||||||||||||||||||||||
     5:  7.27% |||||||||||||||||||||||||||||||||||||
     6:  6.74% ||||||||||||||||||||||||||||||||||
     7:  6.26% ||||||||||||||||||||||||||||||||
     8:  5.78% |||||||||||||||||||||||||||||
     9:  5.25% ||||||||||||||||||||||||||
    10:  4.75% ||||||||||||||||||||||||
    11:  4.22% |||||||||||||||||||||
    12:  3.73% |||||||||||||||||||
    13:  3.25% ||||||||||||||||
    14:  2.75% ||||||||||||||
    15:  2.25% |||||||||||
    16:  1.75% ||||||||
    17:  1.25% ||||||
    18:  0.77% |||
    19:  0.25% |

    Распределение вероятностей уменьшается линейно, что позволяет выбирать колонии с более высокими шансами на хорошие решения, но при этом менее эффективные варианты также имеют вероятность быть отобранными. Такой подход к селекции не зависит от абсолютных значений приспособленности особей, что обеспечивает широкий диапазон разнообразия решений.

    В предыдущих статьях мы уже рассматривали формулы для изменения распределения вероятностей при отборе, но с возможностью обеспечивать как линейное, так и нелинейное убывание вероятностей, причем с меньшими вычислительными затратами (для турнирного отбора требуется двукратный вызов функции MathRand ()).

    graph

    Рисунок 1. Примеры формул для изменения формы распределения вероятностей, где x - равномерно распределенное случайное число в диапазоне [0.0, 1.0]

    Теперь, когда мы подробно разобрали все тонкости алгоритма, можем приступить к написанию самого кода.

    Опишем структуру "S_AAA_Agent", которая будет предназначаться для моделирования колонии водорослей (агента) в алгоритме. Структура содержит четыре поля:

    • energy — представляет уровень энергии агента.
    • hunger — используется для отслеживания уровня голода агента.
    • size — указывает размер агента (рост, длина водоросли).
    • friction — коэффициент трения, влияющий на движение агента.

    Init — метод инициализирует члены структуры значениями по умолчанию. 

    Таким образом, структура "S_AAA_Agent" представляет собой простую модель агента с базовыми характеристиками.

    //——————————————————————————————————————————————————————————————————————————————
struct S_AAA_Agent
{
  double energy;
  int    hunger;
  double size;
  double friction;

  void Init ()
  {
    energy   = 1.0;
    hunger   = 0;
    size     = 1.0;
    friction = 0.0;
  }
};
//——————————————————————————————————————————————————————————————————————————————

    Напишем определение класса "C_AO_AAA", который наследуется от базового класса "C_AO". Это означает, что он унаследует все члены и методы базового класса и может расширять или переопределять их.

    1. В конструкторе класса задаются значения для различных параметров, связанных с алгоритмом и также инициализируются:

    • popSize  — размер популяции.
    • adaptationProbability  — вероятность адаптации.
    • energyLoss — потеря энергии.
    • maxGrowthRate — максимальная скорость роста.
    • halfSaturationConstant — константа полупоглощения.

    Все эти параметры сохраняются в массиве "params".

    2. Метод "SetParams" обновляет значения параметров алгоритма из массива "params".

    3. Методы:

    • Init () — метод для инициализации принимает массивы для минимальных и максимальных значений параметров, а также шаги и количество эпох.
    • Moving () — метод отвечает за перемещение или обновление состояния агентов.
    • Revision ()  — метод для пересмотра или оценки состояния.
    • EvolutionProcess (), AdaptationProcess (), CalculateEnergy (), TournamentSelection () — приватные методы отвечают за эволюционный процесс, процесс адаптации, расчёт энергии водоросли и турнирную селекцию соответственно.

    Поля класса:

    • adaptationProbability, energyLoss, maxGrowthRate, halfSaturationConstant — переменные для хранения значений параметров.
    • S_AAA_Agent agent []  — массив агентов.
    • fMin, fMax — используются для хранения значений приспособленности (размер водорослей) по популяции.

    Класс "C_AO_AAA" представляет собой структуру, которая позволяет удобно управлять параметрами и состоянием агентов, а также интегрировать его в более широкую систему, основанную на наследовании от класса "C_AO".

    //——————————————————————————————————————————————————————————————————————————————
class C_AO_AAA : public C_AO
{
  public: //--------------------------------------------------------------------

  ~C_AO_AAA () { }

  C_AO_AAA ()
  {
    ao_name = "AAA";
    ao_desc = "Algae Adaptive Algorithm";
    ao_link = "https://www.mql5.com/ru/articles/15565";

    popSize                = 200;
    adaptationProbability  = 0.2;
    energyLoss             = 0.05;
    maxGrowthRate          = 0.1;
    halfSaturationConstant = 1.0;

    ArrayResize (params, 5);

    params [0].name = "popSize";                params [0].val = popSize;
    params [1].name = "adaptationProbability";  params [1].val = adaptationProbability;
    params [2].name = "energyLoss";             params [2].val = energyLoss;
    params [3].name = "maxGrowthRate";          params [3].val = maxGrowthRate;
    params [4].name = "halfSaturationConstant"; params [4].val = halfSaturationConstant;
  }

  void SetParams ()
  {
    popSize                = (int)params [0].val;
    adaptationProbability  = params      [1].val;
    energyLoss             = params      [2].val;
    maxGrowthRate          = params      [3].val;
    halfSaturationConstant = params      [4].val;
  }

  bool Init (const double &rangeMinP  [],
             const double &rangeMaxP  [],
             const double &rangeStepP [],
             const int     epochsP = 0);

  void Moving   ();
  void Revision ();

  //----------------------------------------------------------------------------
  double adaptationProbability;
  double energyLoss;
  double maxGrowthRate;
  double halfSaturationConstant;

  S_AAA_Agent agent [];

  private: //-------------------------------------------------------------------
  void   EvolutionProcess    ();
  void   AdaptationProcess   ();
  double CalculateEnergy     (int index);
  int    TournamentSelection ();
  double fMin, fMax;
};
//——————————————————————————————————————————————————————————————————————————————

    Давайте разберем следующий метод "Init" класса "C_AO_AAA" подробно:

    • rangeMinP — массив минимальных значений для каждого параметра.
    • rangeMaxP — массив максимальных значений для каждого параметра.
    • rangeStepP — массив шагов изменения для каждого параметра.
    • epochsP — количество эпох (по умолчанию 0).

    Поля метода:

    1. Метод "StandardInit" выполняет стандартную инициализацию с переданными параметрами. 

    2. Изменяет размер массива "agent" до значения "popSize". Это позволяет подготовить массив для хранения агентов.

    3. Устанавливает минимальное и максимальное значения для функций, используемых в процессе работы .

    4. Цикл проходит по каждому агенту, инициализируя его с помощью метода "Init".

    5. Внутренний цикл инициализирует координаты каждого агента:

    • сначала координата "c" устанавливается случайным образом в диапазоне от "rangeMin [c]" до "rangeMax [c]" с помощью метода "RNDfromCI".
    • затем эта координата будет изменена с использованием метода "SeInDiSp", который нормализует значения.

    Если все операции выполнены успешно, метод возвращает "true". Таким образом, метод "Init" инициализирует массив агентов с заданными диапазонами и шагами для их координат. Он включает в себя стандартную инициализацию, установку границ для функции и случайное задание значений координат.

    //——————————————————————————————————————————————————————————————————————————————
bool C_AO_AAA::Init (const double &rangeMinP  [],
                     const double &rangeMaxP  [],
                     const double &rangeStepP [],
                     const int     epochsP = 0)
{
  if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false;

  ArrayResize (agent, popSize);

  fMin = -DBL_MAX;
  fMax =  DBL_MAX;

  for (int i = 0; i < popSize; i++)
  {
    agent [i].Init ();

    for (int c = 0; c < coords; c++)
    {
      a [i].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]);
      a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }

  return true;
}
//——————————————————————————————————————————————————————————————————————————————

    Рассмотрим код метода "Moving" класса "C_AO_AAA". Общая структура и функциональность:

    1. Если переменная "revision" равно "false", она устанавливается в "true", и функция завершает выполнение. Это означает, что основная логика метода "Moving" не выполняется на первой итерации.

    2. Цикл проходит по всем элементам популяции "popSize".

    3. Турнирный отбор выполняется в функции "TournamentSelection", которая возвращает индекс одного из агентов (водорослей) для дальнейшего использования.

    4. Внутренний цикл проходит по каждой координате (размерность пространства, заданная переменной "coords").

    5. Генерируются три случайных значения: "α" и "β" (углы) и "ρ" (значение в диапазоне от -1 до 1) с использованием метода "u.RNDfromCI".

    6. В зависимости от значения "variant" (который меняется от 0 до 2) обновляются координаты "a [i].c [c]":

    • если "variant" равен 0, используется косинус угла "α".
    • если "variant" равен 1, используется синус угла "β".
    • если "variant" равен 2, используется значение "ρ".

    Использование переменной "variant" позволяет имитировать трехмерное спиральное движение водорослей в многомерном пространстве. Обновление координаты происходит с учетом трения, заданного как "agent[i].friction".

    7. Координаты "a [i].c [c]" ограничиваются с использованием функции "u.SeInDiSp", которая устанавливает значение в пределах заданного диапазона и с заданным шагом.

    Функция "Moving" реализует процесс, используя случайные изменения в координатах агентов на основе их текущего состояния и состояния других агентов. Использование трения и случайных значений позволяет создать динамику, которая имитирует поведение агентов в пространстве поиска. Код включает в себя механизмы, которые предотвращают выход за пределы заданных диапазонов, что важно для поддержания допустимых значений координат.

    //——————————————————————————————————————————————————————————————————————————————
void C_AO_AAA::Moving ()
{
  //----------------------------------------------------------------------------
  if (!revision)
  {
    revision = true;
    return;
  }

  //----------------------------------------------------------------------------
  for (int i = 0; i < popSize; i++)
  {
    int variant = 0;

    int j = TournamentSelection ();

    for (int c = 0; c < coords; c++)
    {
      double α = u.RNDfromCI (0.0, 2 * M_PI);
      double β = u.RNDfromCI (0.0, 2 * M_PI);
      double ρ = u.RNDfromCI (-1.0, 1.0);

      if (variant == 0) a [i].c [c] += (a [j].c [c] - a [i].c [c]) * agent [i].friction * MathCos (α);
      if (variant == 1) a [i].c [c] += (a [j].c [c] - a [i].c [c]) * agent [i].friction * MathSin (β);
      if (variant == 2) a [i].c [c] += (a [j].c [c] - a [i].c [c]) * agent [i].friction * ρ;

      variant++;

      if (variant > 2) variant = 0;

      a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

    После метода "Moving" перейдем к методу "Revision" класса "C_AO_AAA". Этот метод отвечает за обновление состояния агентов в популяции на основе их характеристик и взаимодействий. Общая структура:

    1. Переменная "ind" инициализируется значением "-1". Она будет использоваться для хранения индекса агента с наилучшим значением функции.

    2. Цикл проходит по всем агентам в популяции "popSize". Внутри цикла: если значение функции "a [i].f" больше текущего максимума "fB", 

    • то обновляется максимальное значение "fB".
    • запоминается индекс агента с наилучшим значением в переменной "ind".
    • размер агента "agent [i].size" обновляется в соответствии с его значением функции приспособленности "a [i].f".
    • обновляются минимальное "fMin" и максимальное "fMax" значения функции приспособленности для текущего агента.

    3. Если был найден агент с максимальным значением приспособленности "f", его координаты копируются в массив "cB" с помощью функции "ArrayCopy".

    4. Обновление энергии и других параметров агентов:

    • вычисляется его энергия с помощью функции "CalculateEnergy".
    • рассчитывается трение, нормализованное по значениям "fMin" и "fMax".
    • энергия агента уменьшается на величину "energyLoss".
    • если новая энергия больше текущей, то энергия увеличивается на половину потерь, и голод агента сбрасывается. В противном случае увеличивается уровень голода.
    • рассчитывается коэффициент роста, который зависит от текущего размера агента и его сытости, и размер агента обновляется.

    5. Вызов процессов: в конце функции вызываются методы "EvolutionProcess" и "AdaptationProcess", которые отвечают за дальнейшую эволюцию и адаптацию агентов на основе их текущего состояния.

    В целом, функция "Revision" отвечает за обновление состояния агентов в популяции, основываясь на их характеристиках и взаимодействиях. Она включает в себя анализ, обновление и вызов дополнительных процессов, что позволяет моделировать динамику популяции.

    //——————————————————————————————————————————————————————————————————————————————
void C_AO_AAA::Revision ()
{
  //----------------------------------------------------------------------------
  int ind = -1;

  for (int i = 0; i < popSize; i++)
  {
    if (a [i].f > fB)
    {
      fB = a [i].f;

      ind = i;
    }

    agent [i].size = a [i].f;

    if (a [i].f < fMin) fMin = a [i].f;
    if (a [i].f > fMax) fMax = a [i].f;
  }

  if (ind != -1) ArrayCopy (cB, a [ind].c, 0, 0, WHOLE_ARRAY);

  //----------------------------------------------------------------------------
  for (int i = 0; i < popSize; i++)
  {
    agent [i].energy   = CalculateEnergy (i);

    agent [i].friction = u.Scale (a [i].f, fMin, fMax, 0.1, 1.0, false);

    agent [i].energy -= energyLoss;

    double newEnergy = CalculateEnergy (i);

    if (newEnergy > agent [i].energy)
    {
      agent [i].energy += energyLoss / 2;
      agent [i].hunger = 0;
    }
    else
    {
      agent [i].hunger++;
    }

    double growthRate = maxGrowthRate * agent [i].size / (agent [i].size + halfSaturationConstant);

    agent [i].size *= (1 + growthRate);
  }

  //----------------------------------------------------------------------------
  EvolutionProcess  ();
  AdaptationProcess ();
}
//——————————————————————————————————————————————————————————————————————————————

    Опишем далее функцию "EvolutionProcess ()". Она отвечает за процесс эволюции агентов в популяции. Основная задача этой функции —найти самого неприспособленного агента (самую низкую водоросль) и заменить его координаты на координаты других случайных более приспособленных агентов (более высоких водорослей).

    1. Поиск самого неприспособленного агента:

    • инициализируется переменная"smallestIndex", которая будет хранить индекс самого неприспособленного агента. Изначально устанавливается на "0".
    • цикл проходит по всем агентам (начиная с первого) и сравнивает их приспособленность. Если приспособленность текущего агента меньше приспособленности агента с индексом "smallestIndex", обновляется "smallestIndex".

    2. Копирование координат:

    • инициализируется переменная "m", которая будет использоваться для хранения случайного индекса агента.
    • цикл проходит по всем координатам от "0" до "coords".
    • внутри цикла вызывается метод "u.RNDminusOne (popSize)", который генерирует случайный индекс "m" в диапазоне от "0" до "popSize 1".
    • затем координаты самого неприспособленного агента по индексу "smallestIndex" заменяются координатами случайного агента по индексу "m".

    Функция "EvolutionProcess" реализует простой механизм эволюции, в котором самый неприспособленный агент в популяции получает координаты случайного агента. Это операция является частью механизма адаптации, позволяющая агентам улучшать свои характеристики, подбирая более успешные координаты от других агентов и в целом выполняет комбинаторные функции алгоритма.

    //——————————————————————————————————————————————————————————————————————————————
void C_AO_AAA::EvolutionProcess ()
{
  int smallestIndex = 0;

  for (int i = 1; i < popSize; i++)
  {
    if (agent [i].size < agent [smallestIndex].size) smallestIndex = i;
  }

  int m = 0;

  for (int c = 0; c < coords; c++)
  {
    m = u.RNDminusOne (popSize);

    a [smallestIndex].c [c] = a [m].c [c];
  }
}
//——————————————————————————————————————————————————————————————————————————————

    Подробно разберем код функции "AdaptationProcess ()", она отвечает за процесс адаптации агентов в популяции, основываясь на их голоде и размерах. Основная цель этой функции изменить координаты самого голодного агента, если выполняется определенное условие вероятности адаптации.

    1. Поиск самого голодного агента (водоросли):

    • инициализируется переменная "starvingIndex", которая будет хранить индекс самого голодного агента. Изначально устанавливается на "0".
    • цикл проходит по всем агентам (начиная с первого) и сравнивает уровень голода. Если уровень голода текущего агента больше, чем у агента с индексом "starvingIndex", обновляется "starvingIndex".

    2. Проверка вероятности адаптации:

    • используется метод "u.RNDprobab ()", который генерирует случайное число (вероятность). Если это число меньше заданной вероятности адаптации "adaptationProbability", выполняется следующий блок кода.

    3. Поиск самого высокой водоросли - агента:

    • аналогично первому шагу, здесь ищется индекс самого высокого агента в популяции. Изначально "biggestIndex" устанавливается на "0".
    • цикл проходит по всем агентам и обновляет "biggestIndex", если текущий агент выше.

    4. Адаптация координат:

    • цикл проходит по всем координатам.
    • координаты агента с индексом "starvingIndex" обновляются, добавляя значение, которое вычисляется как разница между координатами самого высокого агента и самого голодного агента, умноженная на случайную вероятность.
    • затем координаты нормализуются с помощью метода "u.SeInDiSp ()", который проверяет и корректирует координаты в заданных пределах "rangeMin", "rangeMax", "rangeStep".

    5. Обновление состояния агента:

    • размер агента обновляется значением приспособленности "f" из массива "a".
    • уровень голода "hunger" устанавливается в "0", что означает, что агент сыт.
    • энергия агента "energy" устанавливается в "1.0", это максимальное значение.

    Функция "AdaptationProcess" реализует механизм адаптации, позволяющий наиболее голодному агенту улучшать свои координаты, заимствуя их у самого высокого агента, если выполняется условие вероятности. Это является частью системы, имитирующей естественный отбор, где агенты адаптируются к окружающей среде для повышения своих шансов на выживание.

    //——————————————————————————————————————————————————————————————————————————————
void C_AO_AAA::AdaptationProcess ()
{
  int starvingIndex = 0;

  for (int i = 1; i < popSize; i++) if (agent [i].hunger > agent [starvingIndex].hunger) starvingIndex = i;
  
  if (u.RNDprobab () < adaptationProbability)
  {
    int biggestIndex = 0;

    for (int i = 1; i < popSize; i++) if (agent [i].size > agent [biggestIndex].size) biggestIndex = i;

    for (int j = 0; j < coords; j++)
    {
      a [starvingIndex].c [j] += (a [biggestIndex].c [j] - a [starvingIndex].c [j]) * u.RNDprobab ();

      a [starvingIndex].c [j] = u.SeInDiSp (a [starvingIndex].c [j], rangeMin [j], rangeMax [j], rangeStep [j]);
    }

    agent [starvingIndex].size   = a [starvingIndex].f;
    agent [starvingIndex].hunger = 0;
    agent [starvingIndex].energy = 1.0;
  }
}
//——————————————————————————————————————————————————————————————————————————————

    Далее у нас идет код функции "CalculateEnergy". Она предназначена для вычисления энергии определенного агента в зависимости от его характеристик, таких как размер колонии, уровень энергии и концентрация питательных веществ. Функция возвращает значение энергии, которое используется в других частях алгоритма.

    1. Инициализация переменных:

    • colony_size — получает высоту водоросли, используя индекс "index".
    • max_growth_rate — устанавливается как максимальная скорость роста.
    • half_saturation_constant — устанавливается как половина постоянной насыщения.

    2. Нормализация фитнес-функции: вычисляется нормализованное значение концентрации питательных веществ. Оно рассчитывается как отношение разности между значением "f" (из массива "a") и минимальным значением "fMin" к диапазону между "fMax" и "fMin". Добавление "1e-10" предотвращает деление на ноль.

    3. Получение текущей скорости роста: current_growth_rate — получает текущее значение энергии агента, которое также интерпретируется как текущая скорость роста.

    4. Вычисление скорости роста: growth_rate — рассчитывается на основе максимальной скорости роста, нормализованной концентрации питательных веществ и текущей скорости роста. Формула учитывает эффект насыщения, где скорость роста уменьшается при увеличении текущей скорости роста.

    5. Вычисление энергии: "energy" вычисляется как разница между "growth_rate" и некоторыми потерями энергии "energyLoss". Это значение показывает, сколько энергии агент получает после учета потерь.

    6. Если вычисленная энергия оказывается отрицательной, она устанавливается в "0". Это предотвращает отрицательные значения энергии.

    7. Функция возвращает вычисленное значение энергии.

    Функция "CalculateEnergy" моделирует процесс, в котором агент получает энергию на основе своей скорости роста, размера колонии и концентрации питательных веществ. Она учитывает также потери энергии, чтобы обеспечить реалистичное поведение агентов в симуляции. 

    //——————————————————————————————————————————————————————————————————————————————
double C_AO_AAA::CalculateEnergy (int index)
{
  double colony_size              = agent [index].size;
  double max_growth_rate          = maxGrowthRate;
  double half_saturation_constant = halfSaturationConstant;

  // Используем нормализованное значение фитнес-функции
  double nutrient_concentration = (a [index].f - fMin) / (fMax - fMin + 1e-10);

  double current_growth_rate = agent [index].energy;

  double growth_rate = max_growth_rate * nutrient_concentration / (half_saturation_constant + current_growth_rate) * colony_size;

  double energy = growth_rate - energyLoss;

  if (energy < 0) energy = 0;

  return energy;
}
//——————————————————————————————————————————————————————————————————————————————

    Последним методом реализуем механизм турнирной селекции. Метод "TournamentSelection" выбирает одного из двух кандидатов из популяции на основе их значений функции фитнеса. Он возвращает индекс кандидата, который имеет лучшее значение фитнеса. Турнирный отбор обеспечивает селекцию, распределения вероятностей при которой по агентам в популяции мы рассмотрели выше.

    //——————————————————————————————————————————————————————————————————————————————
int C_AO_AAA::TournamentSelection ()
{
  int candidate1 = u.RNDminusOne (popSize);
  int candidate2 = u.RNDminusOne (popSize);

  return (a [candidate1].f > a [candidate2].f) ? candidate1 : candidate2;
}
//——————————————————————————————————————————————————————————————————————————————


    Результаты тестов

    Распечатка работы алгоритма AAA на тестовых функциях:

    AAA|Algae Adaptive Algorithm|200.0|0.2|0.05|0.1|0.1|
    =============================
    5 Hilly's; Func runs: 10000; result: 0.5000717048088521
    25 Hilly's; Func runs: 10000; result: 0.3203956013467087
    500 Hilly's; Func runs: 10000; result: 0.25525273777603685
    =============================
    5 Forest's; Func runs: 10000; result: 0.37021025883379577
    25 Forest's; Func runs: 10000; result: 0.2228350161785575
    500 Forest's; Func runs: 10000; result: 0.16784823154308887
    =============================
    5 Megacity's; Func runs: 10000; result: 0.2784615384615384
    25 Megacity's; Func runs: 10000; result: 0.14800000000000005
    500 Megacity's; Func runs: 10000; result: 0.097553846153847
    =============================
    All score: 2.36063 (26.23%)

    Как на распечатке, так и в визуализации работы алгоритма наблюдается слабая сходимость, что подтверждается результатами тестов. К сожалению, мои ожидания на высокие результаты не оправдались. При наличии комплексной стратегии поиска алгоритма, трудно определить причины его неэффективности, так как он слабо локализует глобальный оптимум. Однако, несмотря на эти недостатки, алгоритм всё же имеет достоинства, и о них ниже.

    Hilly

    AAA на тестовой функции Hilly

    Forest

    AAA на тестовой функции Forest

    Megacity

    AAA на тестовой функции Megacity

    По результатам тестирования алгоритм занимает 36 место в рейтинговой таблице.

    № 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 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 0,95346 0,86319 0,27770 2,09435 0,99794 0,85740 0,33949 2,19484 0,88769 0,56431 0,10512 1,55712 5,846 64,96
    6 SDSm stochastic diffusion search M 0,93066 0,85445 0,39476 2,17988 0,99983 0,89244 0,19619 2,08846 0,72333 0,61100 0,10670 1,44103 5,709 63,44
    7 ESG evolution of social groups 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
    8 SIA simulated isotropic annealing 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
    9 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
    10 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
    11 TSEA turtle shell evolution algorithm 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
    12 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
    13 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
    14 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
    15 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
    16 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
    17 (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
    18 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
    19 WOAm whale 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
    20 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
    21 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
    22 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
    23 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
    24 ASBO adaptive social behavior optimization 0,76331 0,49253 0,32619 1,58202 0,79546 0,40035 0,26097 1,45677 0,26462 0,17169 0,18200 0,61831 3,657 40,63
    25 MEC mind evolutionary computation 0,69533 0,53376 0,32661 1,55569 0,72464 0,33036 0,07198 1,12698 0,52500 0,22000 0,04198 0,78698 3,470 38,55
    26 IWO invasive weed optimization 0,72679 0,52256 0,33123 1,58058 0,70756 0,33955 0,07484 1,12196 0,42333 0,23067 0,04617 0,70017 3,403 37,81
    27 Micro-AIS micro artificial immune system 0,79547 0,51922 0,30861 1,62330 0,72956 0,36879 0,09398 1,19233 0,37667 0,15867 0,02802 0,56335 3,379 37,54
    28 COAm cuckoo optimization algorithm M 0,75820 0,48652 0,31369 1,55841 0,74054 0,28051 0,05599 1,07704 0,50500 0,17467 0,03380 0,71347 3,349 37,21
    29 SDOm spiral dynamics optimization M 0,74601 0,44623 0,29687 1,48912 0,70204 0,34678 0,10944 1,15826 0,42833 0,16767 0,03663 0,63263 3,280 36,44
    30 NMm Nelder-Mead method M 0,73807 0,50598 0,31342 1,55747 0,63674 0,28302 0,08221 1,00197 0,44667 0,18667 0,04028 0,67362 3,233 35,92
    31 FAm firefly algorithm M 0,58634 0,47228 0,32276 1,38138 0,68467 0,37439 0,10908 1,16814 0,28667 0,16467 0,04722 0,49855 3,048 33,87
    32 GSA gravitational search algorithm 0,64757 0,49197 0,30062 1,44016 0,53962 0,36353 0,09945 1,00260 0,32667 0,12200 0,01917 0,46783 2,911 32,34
    33 BFO bacterial foraging optimization 0,61171 0,43270 0,31318 1,35759 0,54410 0,21511 0,05676 0,81597 0,42167 0,13800 0,03195 0,59162 2,765 30,72
    34 ABC artificial bee colony 0,63377 0,42402 0,30892 1,36671 0,55103 0,21874 0,05623 0,82600 0,34000 0,14200 0,03102 0,51302 2,706 30,06
    35 BA bat algorithm 0,59761 0,45911 0,35242 1,40915 0,40321 0,19313 0,07175 0,66810 0,21000 0,10100 0,03517 0,34617 2,423 26,93
    36 AAA algae adaptive algorithm 0,50007 0,32040 0,25525 1,07572 0,37021 0,22284 0,16785 0,76089 0,27846 0,14800 0,09755 0,52402 2,361 26,23
    37 SA simulated annealing 0,55787 0,42177 0,31549 1,29513 0,34998 0,15259 0,05023 0,55280 0,31167 0,10033 0,02883 0,44083 2,289 25,43
    38 IWDm intelligent water drops M 0,54501 0,37897 0,30124 1,22522 0,46104 0,14704 0,04369 0,65177 0,25833 0,09700 0,02308 0,37842 2,255 25,06
    39 PSO particle swarm optimisation 0,59726 0,36923 0,29928 1,26577 0,37237 0,16324 0,07010 0,60572 0,25667 0,08000 0,02157 0,35823 2,230 24,77
    40 Boids boids algorithm 0,43340 0,30581 0,25425 0,99346 0,35718 0,20160 0,15708 0,71586 0,27846 0,14277 0,09834 0,51957 2,229 24,77
    41 MA monkey algorithm 0,59107 0,42681 0,31816 1,33604 0,31138 0,14069 0,06612 0,51819 0,22833 0,08567 0,02790 0,34190 2,196 24,40
    42 SFL shuffled frog-leaping 0,53925 0,35816 0,29809 1,19551 0,37141 0,11427 0,04051 0,52618 0,27167 0,08667 0,02402 0,38235 2,104 23,38
    43 FSS fish school search 0,55669 0,39992 0,31172 1,26833 0,31009 0,11889 0,04569 0,47467 0,21167 0,07633 0,02488 0,31288 2,056 22,84
    44 RND random 0,52033 0,36068 0,30133 1,18234 0,31335 0,11787 0,04354 0,47476 0,25333 0,07933 0,02382 0,35648 2,014 22,37
    45 GWO grey wolf optimizer 0,59169 0,36561 0,29595 1,25326 0,24499 0,09047 0,03612 0,37158 0,27667 0,08567 0,02170 0,38403 2,009 22,32



    Выводы

    Ориентируясь на результаты работы алгоритма на тестовых функциях различной размерности, можно сделать следующие выводы. Из распечатки видно, что сходимость низкая. Я несколько разочарован возможностями алгоритма: несмотря на использование множества методов и сложной ступенчатой логики, я ожидал, что алгоритм продемонстрирует хотя бы хорошие результаты и займет место в верхней части таблицы, а не окажется в числе замыкающих таблицу. Возможно, стоит уделить больше внимания и осмыслению примененных методов, поскольку их количество не всегда гарантирует качество. Тем, кто желает, уже сейчас можно экспериментировать, и если алгоритм покажет лучшие результаты, прошу поделиться ими, я с нетерпением жду комментариев к статье.

    К положительным аспектам алгоритма можно отнести хорошие результаты на функциях Forest и Megacity с 1000 переменными по сравнению с ближайшими конкурентами. Это свидетельствует о перспективности алгоритма в плане масштабируемости для задач с "острыми" экстремумами и дискретными задачами.

    Tab

    Рисунок 1. Цветовая градация алгоритмов по соответствующим тестам. Белым цветом подсвечены результаты больше или равные 0.99

    chart

    Рисунок 2. Гистограмма результатов тестирования алгоритмов (по шкале от 0 до 100, чем больше, тем лучше,

    где 100 - максимально возможный теоретический результат, в архиве скрипт для расчета рейтинговой таблицы)

    Плюсы и минусы алгоритма AAA:

    Плюсы:

    1. Перспективная идея и новаторские подходы.

    Минусы:

    1. Большое количество параметров (очень сложно настроить алгоритм).
    2. Слабая сходимость.
    3. Сложная для отладки реализация.

    К статье прикреплён архив с актуальными версиями кодов алгоритмов. Автор статьи не несёт ответственности за абсолютную точность в описании канонических алгоритмов, во многие из них были внесены изменения для улучшения поисковых возможностей. Выводы и суждения, представленные в статьях, основываются на результатах проведённых экспериментов.

    Прикрепленные файлы |
    Загрузить ZIP
    AAA.ZIP (30.25 KB)
    Предупреждение: все права на данные материалы принадлежат MetaQuotes Ltd. Полная или частичная перепечатка запрещена.

    Другие статьи автора

    Перейти к обсуждению на форуме трейдеров
    Особенности написания Пользовательских Индикаторов Особенности написания Пользовательских Индикаторов
    Написание пользовательских индикаторов в торговой системе MetaTrader 4
    Метод группового учета аргументов: реализация многослойного итерационного алгоритма на MQL5 Метод группового учета аргументов: реализация многослойного итерационного алгоритма на MQL5
    В этой статье мы описываем реализацию Многослойного итерационного алгоритма как метода группового учета аргументов на языке MQL5.
    Особенности написания экспертов Особенности написания экспертов
    Написание и тестирование экспертов в торговой системе MetaTrader 4.
    Алгоритм анархической социальной оптимизации — Anarchic Society Optimization (ASO) Алгоритм анархической социальной оптимизации — Anarchic Society Optimization (ASO)
    В очередной статье мы познакомимся с алгоритмом Anarchic Society Optimization (ASO) и обсудим, как алгоритм, основанный на иррациональном и авантюрном поведении участников анархического общества - аномальной системы социального взаимодействия, свободной от централизованной власти и различного рода иерархий способен исследовать пространство решений и избегать ловушек локального оптимума. В статье будет представлена унифицированная структура ASO, применимая как к непрерывным, так и к дискретным задачам.