MetaTrader 5 / Трейдинг
preview
Оптимизация на основе биогеографии — Biogeography-Based Optimization (BBO)

Оптимизация на основе биогеографии — Biogeography-Based Optimization (BBO)

MetaTrader 5 — Трейдинг |
229 0
Andrey Dik
Andrey Dik

Содержание

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


Введение

Пересматривая некоторые оптимизационные алгоритмы, меня заинтересовал алгоритм биогеографической оптимизации (BBO), он был разработан профессором Dan Simon в 2008 году. BBO черпает вдохновение из биогеографии — науки о географическом распределении биологических организмов. Математические модели, описывающие распределение видов, были впервые разработаны еще в 1960-х годах. Подобно тому, как генетические алгоритмы были вдохновлены биологической генетикой, а нейронные сети — биологическими нейронами, BBO использует математические принципы биогеографии для решения оптимизационных задач.

В природе острова архипелага с благоприятными условиями (высокий индекс пригодности среды обитания - HSI) имеют большое количество видов и высокую эмиграцию, в то время как острова с плохими условиями имеют мало видов и высокую иммиграцию. Эта естественная динамика миграции видов между островами легла в основу механизма оптимизации BBO. Алгоритм использует концепцию миграции видов для обмена характеристиками между решениями, вероятность мутации основана на теоретически обоснованной модели распределения видов, кроме того, хорошие решения активно делятся своими характеристиками, но остаются устойчивыми к изменениям. Эта изюминка является основной характеристикой алгоритма.

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


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

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

1. Хабитат (Habitat) = Остров = Решение задачи. Каждый остров в нашем алгоритме представляет одно возможное решение. Если у вас 50 островов, значит у вас 50 разных решений.

2. HSI (Habitat Suitability Index) = Пригодность острова для жизни = Качество решения. Богатый остров с пресной водой, фруктами и хорошим климатом = Хорошее решение (высокий HSI). Пустынный остров без воды = Плохое решение (низкий HSI)

3. Виды (Species) = Характеристики решения. На богатом острове живет много видов животных. На бедном острове — мало видов, потому что он неразнообразен.

Как работает миграция? Пример из жизни: Гавайи (богатый остров), много видов → животные часто уплывают/улетают на другие острова (высокая эмиграция), но мало кто приплывает (низкая иммиграция — остров уже и так переполнен). Необитаемый остров: мало видов → животные редко уплывают (низкая эмиграция), но часто приплывают новые (высокая иммиграция — много свободного места).

В алгоритме: Плохое решение (мало видов) → Высокая иммиграция → принимает характеристики от хороших решений. Хорошее решение (много видов) → Высокая эмиграция → делится характеристиками с другими.

Еще пример из жизни, допустим, мы ищем лучшее расположение магазина в городе. Каждый "остров" — это вариант расположения. Создаем 50 случайных расположений (островов), из которых:

Остров 1: плохое место — окраина
Остров 2: отличное место — центр
Остров 50: средне хорошее место

Оцениваем каждое расположение (HSI): Остров 2 (центр): HSI = 95 (много покупателей, хорошая доступность), Остров 1 (окраина): HSI = 20 (мало покупателей), тогда Остров 1 (плохой) имеет высокую иммиграцию и он "принимает" некоторые характеристики от Острова 2 (хорошего). Например, если Остров 2 находится "возле метро", то Остров 1 тоже попытается найти место возле метро. Иногда могут происходить "катастрофы" (землетрясения, цунами), когда решение случайно изменяется — магазин "прыгает" в совершенно новое место, и такое перемещение помогает найти неожиданно хорошие решения.

Почему средние решения мутируют реже? В природе очень богатые острова (как Галапагосы) — редки и нестабильны, в то же время очень бедные острова — тоже редки и нестабильны, а средние острова — самые распространенные и устойчивые. В алгоритме это означает:

Очень хорошие решения (HSI = 95): высокая вероятность мутации
Очень плохие решения (HSI = 5): высокая вероятность мутации
Средние решения (HSI = 50): низкая вероятность мутации

Первые 2 лучших острова (решения) защищены от изменений — это наши "заповедники". Мы не хотим потерять лучшие найденные решения! Тогда итоговый процесс оптимизации: создаем 50 случайных решений (острова), сортируем их по качеству (от лучших к худшим), далее плохие решения учатся у хороших, а некоторые решения случайно изменяются. Таким образом, BBO имитирует природный процесс распределения видов между островами для поиска оптимального решения. Ниже представлена иллюстрация работы алгоритма.

BBO

Рисунок 1. Иллюстрация работы алгоритма BBO 

Согласно схеме на рисунке 1, которая визуально показывает:

  1. Три типа островов— (богатый, средний, бедный) с разным количеством видов
  2. Процесс миграции  — стрелки показывают, как виды перемещаются между островами
  3. Пошаговый процесс оптимизации  — от инициализации до повторения
  4. Ключевые концепции  — легенда и основные принципы алгоритма

Иллюстрация наглядно демонстрирует, как богатые острова (хорошие решения) имеют высокую эмиграцию, бедные острова (плохие решения) имеют высокую иммиграцию, происходит обмен характеристиками между решениями, работает весь цикл оптимизации. После подробного разбора алгоритма, переходим к написанию псевдокода.

1. ИНИЦИАЛИЗАЦИЯ:
   - Задать параметры:
     * размер популяции (количество хабитатов) = 50
     * максимальная скорость иммиграции I = 1.0
     * максимальная скорость эмиграции E = 1.0
     * вероятность мутации = 0.01
     * количество элитных решений = 2
     * максимальное количество видов = 50
     * количество итераций
   
   - Создать популяцию из N случайных хабитатов (решений)
   - Вычислить HSI (пригодность) для каждого хабитата
   - Рассчитать вероятности существования для разного количества видов

2. ОСНОВНОЙ ЦИКЛ (повторять заданное количество итераций):
   
   2.1. ОЦЕНКА И СОРТИРОВКА:
        - Вычислить HSI для каждого хабитата
        - Отсортировать хабитаты по убыванию HSI
        - Сохранить лучшее решение
   
   2.2. РАСЧЕТ ПАРАМЕТРОВ МИГРАЦИИ:
        Для каждого хабитата i:
        - Определить количество видов: Si = Smax × (N - ранг_i) / N
        - Рассчитать скорость иммиграции: λi = I × (1 - Si/Smax)
        - Рассчитать скорость эмиграции: μi = E × (Si/Smax)
        - Определить вероятность существования на основе Si
   
   2.3. МИГРАЦИЯ (обмен характеристиками):
        Для каждого хабитата Hi (кроме элитных):
        
        ЕСЛИ случайное_число < λi (скорость иммиграции) ТО:
           
           Для каждой переменной решения (SIV) j:
              
              ЕСЛИ случайное_число < λi ТО:
                 - Выбрать хабитат-донор:
                   * рассчитать сумму всех скоростей эмиграции (кроме Hi)
                   * использовать рулеточную селекцию на основе μ
                   * выбрать хабитат Hk с вероятностью μk/Σμ
                 
                 - Скопировать j-ю переменную из Hk в Hi
              
              КОНЕЦ ЕСЛИ
           
           КОНЕЦ цикла по переменным
        
        КОНЕЦ ЕСЛИ
        
        КОНЕЦ цикла по хабитатам
   
   2.4. МУТАЦИЯ (исследование новых решений):
        Для каждого хабитата Hi (кроме элитных):
        
        - Рассчитать скорость мутации: m_rate = m × (1 - вероятность_существования_i)
        
        ЕСЛИ случайное_число < m_rate ТО:
           - Выбрать случайную переменную j
           - Заменить её случайным значением из допустимого диапазона
        КОНЕЦ ЕСЛИ
        
        КОНЕЦ цикла по хабитатам
   
   2.5. ЗАМЕНА И ОБНОВЛЕНИЕ:
        - Вычислить новые значения HSI
        - Обновить лучшее найденное решение
        - Сохранить текущие значения fitness для следующей итерации

3. ВОЗВРАТ лучшего найденного решения

Теперь осталось совсем немного, напишем класс "C_AO_BBO", который будет являться наследником класса "C_AO" и будет предназначен для реализации алгоритма BBO. Наследование предполагает, что "C_AO_BBO" использует базовую функциональность для оптимизации, предоставляемую родительским классом.

Класс содержит набор параметров, размер популяции и специфичных для BBO, таких, как: максимальная скорость иммиграции/эмиграции (immigrationMax, emigrationMax), вероятность мутации (mutationProb), количество элитных решений, сохраняемых без изменений (elitismCount), и максимальное количество видов (speciesMax). Конструктор класса инициализирует параметры BBO значениями по умолчанию, присваивает имя, описание и ссылку на статью об алгоритме. Метод "SetParams ()" позволяет изменить значения параметров, используя данные из массива "params".

Основные методы:
  • Init () — инициализирует алгоритм, включая создание и инициализацию популяции, заданные диапазоны значений, шаг и количество эпох и инициализирует массивы для хранения данных о хабитатах.
  • Moving () — реализует основную логику перемещения (миграции) решений между хабитатами в соответствии с принципами BBO.
  • Revision () — включает в себя логику для пересмотра и корректировки решений (хабитатов). 
Внутренние структуры данных:
  • S_HabitatData — внутренняя структура, содержащая информацию о каждом хабитате (решении), включая количество видов (speciesCount), скорость иммиграции/эмиграции (immigration, emigration) и вероятность существования (probability).
  • habitatData — массив структур "S_HabitatData", хранящий данные для каждого хабитата в популяции.
  • probabilities — массив вероятностей, используемых для мутации.

Приватные методы содержат реализацию основных шагов алгоритма BBO, таких, как инициализация популяции, расчет скоростей миграции и мутация.

//——————————————————————————————————————————————————————————————————————————————
class C_AO_BBO : public C_AO
{
  public: //--------------------------------------------------------------------
  ~C_AO_BBO () { }
  C_AO_BBO ()
  {
    ao_name = "BBO";
    ao_desc = "Biogeography-Based Optimization";
    ao_link = "https://www.mql5.com/ru/articles/18354";

    popSize        = 50;     // размер популяции (количество хабитатов)
    immigrationMax = 1.0;    // максимальная скорость иммиграции
    emigrationMax  = 1.0;    // максимальная скорость эмиграции
    mutationProb   = 0.5;    // вероятность мутации
    elitismCount   = 2;      // количество элитных решений
    speciesMax     = 50;     // максимальное количество видов

    ArrayResize (params, 6);

    params [0].name = "popSize";        params [0].val = popSize;
    params [1].name = "immigrationMax"; params [1].val = immigrationMax;
    params [2].name = "emigrationMax";  params [2].val = emigrationMax;
    params [3].name = "mutationProb";   params [3].val = mutationProb;
    params [4].name = "elitismCount";   params [4].val = elitismCount;
    params [5].name = "speciesMax";     params [5].val = speciesMax;
  }

  void SetParams ()
  {
    popSize        = (int)params [0].val;
    immigrationMax = params      [1].val;
    emigrationMax  = params      [2].val;
    mutationProb   = params      [3].val;
    elitismCount   = (int)params [4].val;
    speciesMax     = (int)params [5].val;
  }

  bool Init (const double &rangeMinP  [],  // минимальные значения
             const double &rangeMaxP  [],  // максимальные значения
             const double &rangeStepP [],  // шаг изменения
             const int     epochsP = 0);   // количество эпох

  void Moving   ();
  void Revision ();

  //----------------------------------------------------------------------------
  double immigrationMax;    // максимальная скорость иммиграции
  double emigrationMax;     // максимальная скорость эмиграции
  double mutationProb;      // вероятность мутации
  int    elitismCount;      // количество элитных решений
  int    speciesMax;        // максимальное количество видов

  private: //-------------------------------------------------------------------
  struct S_HabitatData
  {
      int    speciesCount;     // количество видов в хабитате
      double immigration;      // скорость иммиграции
      double emigration;       // скорость эмиграции
      double probability;      // вероятность существования
  };

  S_HabitatData habitatData   [];  // данные для каждого хабитата
  double        probabilities [];  // вероятности для подсчета мутаций

  // Вспомогательные методы
  void   InitializePopulation ();
  void   CalculateRates       ();
  void   Migration            ();
  void   Mutation             ();
  double CalculateProbability (int speciesCount);
};
//——————————————————————————————————————————————————————————————————————————————

Метод "Init" конфигурирует алгоритм BBO перед началом работы. Он выполняет базовую инициализацию (проверки и настройки), выделяет память для хранения данных о "хабитатах" и вероятностей миграции. Затем, рассчитывает и нормализует вероятности миграции на основе количества видов в каждом хабитате. При успешном завершении возвращает "true".

//——————————————————————————————————————————————————————————————————————————————
bool C_AO_BBO::Init (const double &rangeMinP  [],  // минимальные значения
                     const double &rangeMaxP  [],  // максимальные значения
                     const double &rangeStepP [],  // шаг изменения
                     const int     epochsP = 0)    // количество эпох
{
  if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false;

  //----------------------------------------------------------------------------
  // Инициализация массивов для каждого хабитата
  ArrayResize (habitatData,   popSize);
  ArrayResize (probabilities, speciesMax + 1);

  // Расчет вероятностей для различного количества видов
  double sum = 0.0;
  for (int i = 0; i <= speciesMax; i++)
  {
    probabilities [i] = CalculateProbability (i);
    sum += probabilities [i];
  }

  // Нормализация вероятностей
  if (sum > 0)
  {
    for (int i = 0; i <= speciesMax; i++)
    {
      probabilities [i] /= sum;
    }
  }

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

Метод "Moving" реализует основной цикл оптимизации алгоритма BBO. При первом вызове метода проверяется флаг "revision". Если он установлен в значение, означающее, что популяция еще не создана, происходит её инициализация. Это включает создание случайных решений, оценку их пригодности и установление начальных параметров. После этого, флаг сбрасывается.

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

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

//+----------------------------------------------------------------------------+
//| Основной метод оптимизации                                                 |
//+----------------------------------------------------------------------------+
void C_AO_BBO::Moving ()
{
  // Первая итерация - инициализация начальной популяции
  if (!revision)
  {
    InitializePopulation ();
    revision = true;
    return;
  }

  // Основной процесс оптимизации
  // 1. Сортировка популяции по HSI (fitness)
  static S_AO_Agent aTemp []; ArrayResize (aTemp, popSize);
  u.Sorting (a, aTemp, popSize);

  // 2. Расчет скоростей иммиграции и эмиграции
  CalculateRates ();

  // 3. Миграция (обмен SIV между хабитатами)
  Migration ();

  // 4. Мутация на основе вероятностей
  Mutation ();

  // 5. Сохранение состояния для следующей итерации
  for (int i = 0; i < popSize; i++)
  {
    a [i].fP = a [i].f;
  }
}
//——————————————————————————————————————————————————————————————————————————————

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

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

//+----------------------------------------------------------------------------+
//| Обновление лучшего решения                                                 |
//+----------------------------------------------------------------------------+
void C_AO_BBO::Revision ()
{
  // Поиск лучшего решения в текущей популяции
  for (int i = 0; i < popSize; i++)
  {
    // Обновление лучшего решения
    if (a [i].f > fB)
    {
      fB = a [i].f;
      ArrayCopy (cB, a [i].c, 0, 0, WHOLE_ARRAY);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Метод "InitializePopulation" отвечает за создание начальной популяции решений для алгоритма BBO. Он создает "popSize" (размер популяции) особей (хабитатов), равномерно распределённых в пространстве поиска.

Для каждой особи метод генерирует случайные координаты (значения параметров решения) в пределах, заданных массивами "rangeMin" (минимальные границы) и "rangeMax" (максимальные границы) для каждой координаты "coords". Используется функция "u.RNDfromCI" для генерации случайного числа в заданном диапазоне.

Далее, метод округляет сгенерированные координаты до ближайшего допустимого шага, определенного массивом "rangeStep". Это гарантирует, что решения находятся в допустимом дискретном пространстве поиска. Для этого используется функция "SeInDiSp". После инициализации координат, метод инициализирует структуру данных "habitatData" для каждой особи, обнуляя значения "speciesCount", "immigration", "emigration" и "probability". Эти значения будут использоваться в процессе оптимизации для расчета скоростей иммиграции, эмиграции и вероятностей мутации.

//+----------------------------------------------------------------------------+
//| Инициализация начальной популяции                                          |
//+----------------------------------------------------------------------------+
void C_AO_BBO::InitializePopulation ()
{
  // Инициализация начальной популяции равномерно по всему пространству
  for (int i = 0; i < popSize; i++)
  {
    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]);
    }

    // Инициализация данных хабитата
    habitatData [i].speciesCount = 0;
    habitatData [i].immigration  = 0.0;
    habitatData [i].emigration   = 0.0;
    habitatData [i].probability  = 0.0;
  }
}
//——————————————————————————————————————————————————————————————————————————————

Метод "CalculateRates" предназначен для вычисления скоростей миграции (иммиграции и эмиграции) и вероятности существования каждого хабитата в популяции.

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

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

//+----------------------------------------------------------------------------+
//| Расчет скоростей иммиграции и эмиграции                                    |
//+----------------------------------------------------------------------------+
void C_AO_BBO::CalculateRates ()
{
  // Для линейной модели миграции
  for (int i = 0; i < popSize; i++)
  {
    // Количество видов обратно пропорционально рангу (лучшие решения имеют больше видов)
    habitatData [i].speciesCount = speciesMax - (i * speciesMax / popSize);

    // Скорость иммиграции уменьшается с увеличением количества видов
    habitatData [i].immigration = immigrationMax * (1.0 - (double)habitatData [i].speciesCount / speciesMax);

    // Скорость эмиграции увеличивается с увеличением количества видов
    habitatData [i].emigration = emigrationMax * (double)habitatData [i].speciesCount / speciesMax;

    // Вероятность существования хабитата
    if (habitatData [i].speciesCount <= speciesMax)
    {
      habitatData [i].probability = probabilities [habitatData [i].speciesCount];
    }
    else
    {
      habitatData [i].probability = 0.0;
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Метод "Migration" реализует процесс миграции (обмена SIV — Habitat Suitability Index Variables, т.е. значений координат) между хабитатами в популяции. Суть метода заключается в том, что хабитаты с высокими скоростями иммиграции (то есть те, у которых мало видов) могут "принимать" SIV из других хабитатов, обладающих высокими скоростями эмиграции (там где много видов).

Цикл перебирает все хабитаты в популяции, но пропускает первые "elitismCount" хабитатов, которые считаются "элитными" и не подлежат миграции. Для каждого хабитата (кроме элитных) случайным образом определяется, будет ли он модифицирован в текущей итерации. Вероятность модификации определяется значением "habitatData [i].immigration" (скоростью иммиграции текущего хабитата). Если хабитат выбран для миграции, начинается перебор всех его координат (SIV). Для каждой координаты снова случайным образом определяется, будет ли она модифицирована. Вероятность модификации также определяется значением "habitatData[i].immigration".

Если координата выбрана для модификации, определяется хабитат, из которого будет "позаимствовано" значение этой координаты. Этот выбор основан на рулеточном отборе (roulette wheel selection) пропорционально значениям "habitatData [j].emigration" (скоростям эмиграции других хабитатов). То есть, хабитаты с более высокими скоростями эмиграции имеют больше шансов стать источником миграции. При расчете вероятностей учитывается, чтобы текущий хабитат не был выбран в качестве источника для самого себя. Если источник миграции выбран, значение соответствующей координаты (SIV) копируется из хабитата-источника в текущий хабитат.

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

//+----------------------------------------------------------------------------+
//| Миграция (обмен SIV между хабитатами)                                      |
//+----------------------------------------------------------------------------+
void C_AO_BBO::Migration ()
{
  for (int i = 0; i < popSize; i++)
  {
    // Пропускаем элитные решения
    if (i < elitismCount) continue;

    // Определяем, будет ли хабитат модифицирован
    if (u.RNDprobab () < habitatData [i].immigration)
    {
      // Для каждой координаты (SIV)
      for (int c = 0; c < coords; c++)
      {
        // Определяем, будет ли эта координата модифицирована
        if (u.RNDprobab () < habitatData [i].immigration)
        {
          // Выбор источника миграции на основе скоростей эмиграции
          double sumEmigration = 0.0;
          for (int j = 0; j < popSize; j++)
          {
            if (j != i) sumEmigration += habitatData [j].emigration;
          }

          if (sumEmigration > 0)
          {
            // Рулеточная селекция источника
            double roulette = u.RNDprobab () * sumEmigration;
            double cumSum = 0.0;

            for (int j = 0; j < popSize; j++)
            {
              if (j != i)
              {
                cumSum += habitatData [j].emigration;
                if (roulette <= cumSum)
                {
                  // Копирование SIV из хабитата j в хабитат i
                  a [i].c [c] = a [j].c [c];
                  break;
                }
              }
            }
          }
        }
      }
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

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

Как и в методе миграции, элитные решения (первые "elitismCount" хабитатов) пропускаются и не подвергаются мутации. Это необходимо для сохранения лучших найденных решений. Для каждого оставшегося хабитата вычисляется вероятность мутации. Важно, что вероятность мутации обратно пропорциональна вероятности существования хабитата (habitatData [i].probability). Это означает, что хабитаты с низкой вероятностью существования (не самые удачные решения) будут мутировать чаще, чтобы способствовать исследованию новых областей.

Если сгенерированное случайное число меньше, чем рассчитанная "mutationRate", то происходит мутация. Случайным образом выбирается одна координата "mutateCoord" (SIV) для мутации из числа всех координат "coords". Для выбранной координаты генерируется новое случайное значение в пределах заданного диапазона. Далее новому значению применяется функция "SeInDiSp", ограничивая значение заданными пределами.

Таким образом, метод "Mutation" вносит элемент случайности в процесс поиска, позволяя алгоритму находить новые, потенциально лучшие решения, особенно в тех областях, которые еще недостаточно исследованы. Частота мутации регулируется вероятностью существования хабитата, чтобы сбалансировать исследование и использование (exploration vs. exploitation).

//+----------------------------------------------------------------------------+
//| Мутация на основе вероятностей                                             |
//+----------------------------------------------------------------------------+
void C_AO_BBO::Mutation ()
{
  for (int i = 0; i < popSize; i++)
  {
    // Пропускаем элитные решения
    if (i < elitismCount) continue;

    // Скорость мутации обратно пропорциональна вероятности существования
    double mutationRate = mutationProb * (1.0 - habitatData [i].probability);

    if (u.RNDprobab () < mutationRate)
    {
      // Выбираем случайную координату для мутации
      int mutateCoord = MathRand () % coords;

      // Генерируем новое значение для выбранной координаты
      a [i].c [mutateCoord] = u.RNDfromCI (rangeMin [mutateCoord], rangeMax [mutateCoord]);
      a [i].c [mutateCoord] = u.SeInDiSp (a [i].c [mutateCoord],
                                          rangeMin [mutateCoord],
                                          rangeMax [mutateCoord],
                                          rangeStep [mutateCoord]);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Метод "CalculateProbability" рассчитывает вероятность существования хабитата при заданном количестве видов. Метод использует упрощенную модель: максимальная вероятность достигается около равновесного значения видов (посередине диапазона), а при отклонении от него, вероятность быстро уменьшается по гауссовой кривой. Чем дальше "speciesCount" от "speciesMax/2", тем ниже вероятность.

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

//+----------------------------------------------------------------------------+
//| Расчет вероятности для заданного количества видов                          |
//+----------------------------------------------------------------------------+
double C_AO_BBO::CalculateProbability (int speciesCount)
{
  // Упрощенная модель вероятности
  // Максимальная вероятность в середине диапазона (равновесие)
  int equilibrium = speciesMax / 2;
  double distance = MathAbs (speciesCount - equilibrium);
  double probability = MathExp (-distance * distance / (2.0 * equilibrium * equilibrium));

  return probability;
}
//——————————————————————————————————————————————————————————————————————————————


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

Немного поэкспериментировав с параметрами, открылись прекрасные результаты работы алгоритма BBO.

BBO|Biogeography-Based Optimization|50.0|1.0|1.0|0.5|2.0|50.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.9491244808033844
25 Hilly's; Func runs: 10000; result: 0.6945610309062928
500 Hilly's; Func runs: 10000; result: 0.35031241665471596
=============================
5 Forest's; Func runs: 10000; result: 0.9381951766964413
25 Forest's; Func runs: 10000; result: 0.6736501622157315
500 Forest's; Func runs: 10000; result: 0.2568167323109364
=============================
5 Megacity's; Func runs: 10000; result: 0.7461538461538464
25 Megacity's; Func runs: 10000; result: 0.4827692307692309
500 Megacity's; Func runs: 10000; result: 0.17369230769230892
=============================
All score: 5.26528 (58.50%)

На визуализации видно, как замечательно работает алгоритм BBO. На труднейшей дискретной функции Megacity алгоритм показывает отличный результат.

Hilly

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

Forest

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

Megacity

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

По итогам тестирования элегантный алгоритм BBO занимает высокое 12 место в верхней части турнирной таблицы.

№ 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 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
13 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
14 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
15 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
16 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
17 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
18 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
19 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
20 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
21 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
22 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
23 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
24 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
25 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
26 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
27 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
28 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
29 (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
30 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
31 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
32 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
33 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
34 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
35 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
36 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
37 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
38 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
39 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
40 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
41 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
42 ADAMm adaptive moment estimation M 0,88635 0,44766 0,26613 1,60014 0,84497 0,38493 0,16889 1,39880 0,66154 0,27046 0,10594 1,03794 4,037 44,85
43 CGO chaos game optimization 0,57256 0,37158 0,32018 1,26432 0,61176 0,61931 0,62161 1,85267 0,37538 0,21923 0,19028 0,78490 3,902 43,35
44 CROm coral reefs optimization M 0,78512 0,46032 0,25958 1,50502 0,86688 0,35297 0,16267 1,38252 0,63231 0,26738 0,10734 1,00703 3,895 43,27
45 ATAm artificial tribe algorithm M 0,71771 0,55304 0,25235 1,52310 0,82491 0,55904 0,20473 1,58867 0,44000 0,18615 0,09411 0,72026 3,832 42,58
RW neuroboids optimization algorithm 2(joo) 0,48754 0,32159 0,25781 1,06694 0,37554 0,21944 0,15877 0,75375 0,27969 0,14917 0,09847 0,52734 2,348 26,09


Выводы

Алгоритм биогеографической оптимизации (BBO) продемонстрировал впечатляющие результаты в проведенных тестах, заняв 12-е место среди 45 лучших популяционных алгоритмов оптимизации с общим показателем эффективности 58.5 %. Это исключительный результат для алгоритма, основанного на столь элегантной и интуитивно понятной природной метафоре.

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

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

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

Алгоритм демонстрирует превосходную стабильность на различных типах ландшафтов: в цветах он равномерно зелёный на всех тестах и нигде не заваливается в результатах по сравнению с другими алгоритмами оптимизации.

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

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

tab

Рисунок 2. Цветовая градация алгоритмов по соответствующим тестам

chart

Рисунок 3. Гистограмма результатов тестирования алгоритмов (по шкале от 0 до 100, чем больше, тем лучше, где 100 — максимально возможный теоретический результат, в архиве скрипт для расчета рейтинговой таблицы)

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

Плюсы:

  1. Быстрый.
  2. Простая реализация.
  3. Хорошие результаты в широком диапазоне размерностей задач.

Минусы:

  1. Большое количество параметров.

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


Программы, используемые в статье

# Имя Тип Описание
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_BBO.mq5
 Скрипт Испытательный стенд для BBO
Прикрепленные файлы |
Загрузить ZIP
BBO.ZIP (285.34 KB)

Предупреждение: все права на данные материалы принадлежат MetaQuotes Ltd. Полная или частичная перепечатка запрещена.

Данная статья написана пользователем сайта и отражает его личную точку зрения. Компания MetaQuotes Ltd не несет ответственности за достоверность представленной информации, а также за возможные последствия использования описанных решений, стратегий или рекомендаций.

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

Перейти к обсуждению на форуме трейдеров
Создание торговой панели администратора на MQL5 (Часть VI): Мультифункциональный интерфейс (I) Создание торговой панели администратора на MQL5 (Часть VI): Мультифункциональный интерфейс (I)
Роль администратора выходит за рамки простого общения в Telegram; он также может заниматься различными видами контроля, включая управление ордерами, отслеживание позиций и настройку интерфейса. В этой статье мы поделимся практическими советами по расширению нашей программы для поддержки множества функций в MQL5. Это обновление направлено на преодоление ограничений текущей панели администратора, которая в первую очередь сосредоточена на общении.
Гауссовcкие процессы в машинном обучении: регрессионная модель в MQL5 Гауссовcкие процессы в машинном обучении: регрессионная модель в MQL5
В настоящей статье мы рассмотрим основы гауссовских процессов (ГП) как вероятностную модель машинного обучения и продемонстрируем ее применение в регрессионных задачах на примере синтетических данных.
Анализ нескольких символов с помощью Python и MQL5 (Часть II): Анализ главных компонентов для оптимизации портфеля Анализ нескольких символов с помощью Python и MQL5 (Часть II): Анализ главных компонентов для оптимизации портфеля
Управление рисками торгового счета является сложной задачей для всех трейдеров. Можем ли мы разработать торговые приложения, которые динамически изучают режимы высокого, среднего и низкого риска для различных символов в MetaTrader 5? Используя PCA, мы получаем лучший контроль над дисперсией портфеля. Я продемонстрирую, как создавать приложения, которые изучают эти три режима риска на основе рыночных данных, полученных из MetaTrader 5.
Нейросети в трейдинге: Интеллектуальный конвейер прогнозов (Time-MoE) Нейросети в трейдинге: Интеллектуальный конвейер прогнозов (Time-MoE)
Предлагаем познакомиться с современным фреймворком Time-MoE, адаптированным под задачи прогнозирования временных рядов. В статье мы пошагово реализуем ключевые компоненты архитектуры, сопровождая их объяснениями и практическими примерами. Такой подход позволит вам не только понять принципы работы модели, но и применить их в реальных торговых задачах.