生物地理学に基づく最適化(BBO)

MetaTrader 5 — トレーディング | YYYY年06月DD日, 09:01

Andrey Dik

内容

はじめに

最適化アルゴリズムを調査している中で、2008年にダン・サイモン(Dan Simon)教授によって提案された生物地理学に基づく最適化(BBO, Biogeography-Based Optimization)に興味を持ちました。BBOは、生物地理学と呼ばれる、生物の地理的分布を研究する学問分野に着想を得ています。種の分布パターンを記述する数学モデルは、1960年代に初めて構築されました。遺伝的アルゴリズムが生物学的な遺伝の仕組みに、ニューラルネットワークが生物の神経細胞に着想を得ているのと同様に、BBOは生物地理学の数学的原理を最適化問題の解決に応用しています。

自然界では、生息環境適性指数(HSI, Habitat Suitability Index)が高い島ほど多くの種が生息し、他の島へ種が移出する割合が高くなります。一方で、環境条件の悪い島では生息種数が少なく、外部から種が流入する割合が高くなります。BBOの最適化メカニズムは、このような島々の間で発生する種の移住ダイナミクスをモデル化したものです。アルゴリズムは、解同士の特徴交換を種の移住として表現し、突然変異確率には理論的に裏付けられた種分布モデルを利用しています。また、優れた解は自身の特徴を積極的に共有しながらも、変化に対して高い安定性を維持します。この性質は、BBOを特徴づける重要な要素の一つです。

本記事では、この洗練されたアルゴリズムの基本的な考え方を解説し、実際にコードとして実装したうえで、その性能を評価していきます。

アルゴリズムの実装

群島に存在する島々を想像してみてください。それぞれの島には異なる種類の生物が生息しています。

1. 生息地 = 島 = 問題の解。アルゴリズムにおいて、各島は1つの候補解を表します。たとえば、50個の島が存在する場合、それは50個の異なる解を保持していることを意味します。

2. HSI（生息環境適性指数） = 島の生息適性 = 解の品質。豊富な水資源や果実に恵まれ、気候条件も良好な島は、生物にとって理想的な環境です。これは高品質な解（高いHSI）に相当します。一方、水もなく生物がほとんど生息できないような島は、低品質な解（低いHSI）に対応します。

3. 種 = 解の特徴。資源が豊富な島には多様な種が生息します。一方、環境の乏しい島では、生息できる種の数も限られます。

移住はどのように機能するのでしょうか。実世界の例として、ハワイのような豊かな島を考えてみましょう。多くの種が存在するため、他の島へ移動する生物は多くなります（高い移出率）。一方で、すでに種で飽和しているため、新たに流入する生物は比較的少なくなります（低い移入率）。反対に、ほとんど生物が存在しない無人島では、生物が外へ移動することはほとんどありません（低い移出率）。しかし、生息可能な空間が豊富に残されているため、新たな生物が流入しやすくなります（高い移入率）。

アルゴリズムでは、悪い解（種数が少ない）→ 移入率が高い → 良い解の特徴を取り込む、良い解（種数が多い）→ 移出率が高い → 自身の特徴を他の解へ共有する、となります。

より身近な例として、市内で最適な店舗立地を探す問題を考えてみます。ここで各「島」は店舗候補地を表します。まず、50個のランダムな候補地（島）を生成します。

島1：郊外の不利な立地
島2：中心部の優れた立地
島50：平均的に良好な立地

次に、それぞれの候補地を評価してHSIを算出します。たとえば、島2（中心部）：HSI = 95（来客数が多くアクセス性も高い）、島1（郊外）：HSI = 20（来客数が少ない）。この場合、島1は移入率が高いため、島2の特徴の一部を取り込みます。たとえば、島2が「地下鉄駅の近く」という特徴を持っている場合、島1も地下鉄駅周辺の候補地を探索する方向へ変化します。また、自然界では地震や津波などの災害が発生することがあります。アルゴリズムではこれが突然変異に相当します。突然変異によって、店舗候補地がまったく別の場所へ飛ぶことがあり、その結果として予想外に優れた解が発見される可能性があります。

なぜ平均的な解は突然変異しにくいのでしょうか。自然界では、非常に豊かな島もガラパゴス諸島のように非常に貧しい島も比較的まれであり、不安定な状態です。一方で、平均的な環境を持つ島は数が多く、安定しています。BBOではこの考え方を突然変異確率に反映しています。

非常に良い解(HSI = 95) → 高い突然変異確率
非常に悪い解(HSI = 5) → 高い突然変異確率
平均的な解(HSI = 50) → 低い突然変異確率

最良の2つの島（解）は変更から保護されます。これらは「保護区」として扱われます。せっかく発見した優れた解を失わないようにするためです。最終的な最適化プロセスは次のようになります。まず、50個のランダムな解（島）を生成し、その品質に基づいて最良のものから最悪のものまで並べ替えます。その後、品質の低い解は品質の高い解から有益な特徴を学習し、一部の解にはランダムな変化が加えられます。このようにしてBBOは、島々の間で種が移住・分布する自然のプロセスを模倣しながら、最適解を探索します。以下に、アルゴリズムの動作を示す概略図を掲載します。

BBO

図1：BBOアルゴリズムの動作イメージ

この図では次の要素が表現されています。

3種類の島（豊かな島・中程度の島・貧しい島）
移住（種の移動）
段階的な最適化（初期化から反復処理までの最適化手順）
主要概念（凡例およびアルゴリズムの基本概念）

図から分かるように、豊かな島（良い解）は高い移出率を持ち、貧しい島（悪い解）は高い移入率を持ちます。その結果、解同士の特徴交換がおこなわれ、最適化サイクル全体が機能します。それでは擬似コードを準備しましょう。

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 - rank_i) / N
-移入率を計算する：λi = I × (1 - Si/Smax)
- 移出率を計算する：μi = E × (Si/Smax)
- Siに基づく生息確率を求める

2.3. 移住（特性の交換）
エリート以外の各生息地Hiに対して：

もしrandom_number < λiなら

各決定変数(SIV) jに対して：

もしrandom_number < λiなら
- ドナー生息地を選択
* Hi以外の移出率の総和を計算
* μに基づくルーレット選択を実施
* μk / Σμの確率でHkを選択

- Hkのj番目の変数をHiにコピー

終了

終了（変数のループ）

終了

終了（生息地のループ）

2.4. 突然変異（新しい解の探索）
エリート以外の各生息地Hiに対して：

- 突然変異率を計算：m_rate = m × (1 - probability_of_existence_i)

もしrandom_number < m_rateなら
- ランダムな変数jを選択
許容範囲内のランダム値へ置換
終了

終了（生息地のループ）

2.5. 置換と更新
- 新しいHSI値を計算する
- 発見済みの最良解を更新する
- 次世代のために現在の適応度を保存する

3. 発見された最良解を返す

あとはBBOアルゴリズムを実装するためのC_AO_BBOクラスを作成するだけです。このクラスはC_AOクラスから派生します。継承によって、親クラスが提供する最適化機能を利用できます。

クラスには個体数などの一般的なパラメータに加え、BBO固有のパラメータも含まれています。具体的には、最大移入率を表すimmigrationMax、最大移出率を表すemigrationMax、突然変異確率を指定するmutationProb、変更を加えずに保持するエリート解の数を定義するelitismCount、そして生息地が持つ最大種数を表すspeciesMaxが用意されています。クラスコンストラクタでは、BBOパラメータのデフォルト値を初期化するとともに、アルゴリズム名、説明文、および関連解説記事へのリンクを設定します。SetParams()メソッドは、params配列からパラメータ値を読み取り、それらを更新するために使用されます。

主なメソッド

Init()：アルゴリズムの初期化を担当し、個体群の生成と初期化、探索変数の範囲設定、ステップ幅やエポック数の指定、さらに生息地データを格納する各種配列の初期化をおこないます。
Moving()：BBOの基本原理に従って、生息地間で解を移住させる主要な処理を実装しています。
Revision()：現在の最良解を更新するロジックが実装されています。

内部データ構造

S_HabitatData：各生息地（解）に関する情報を保持する内部構造体です。種数(speciesCount)、移入率および移出率（immigration、emigration）、生息確率(probability)などのデータを格納します。
habitatData：個体群内の各生息地に対応するS_HabitatData構造体を格納する配列です。
probabilities：突然変異処理で使用する確率値を格納する配列です。

privateメソッドには、個体群の初期化、移住率の計算、突然変異処理など、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/ja/articles/18354";

    popSize        = 50;     // population size (number of habitats)
    immigrationMax = 1.0;    // maximum immigration rate
    emigrationMax  = 1.0;    // maximum emigration rate
    mutationProb   = 0.5;    // mutation probability
    elitismCount   = 2;      // number of elite solutions
    speciesMax     = 50;     // maximum number of species

    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  [],  // minimum values
             const double &rangeMaxP  [],  // maximum values
             const double &rangeStepP [],  // step change
             const int     epochsP = 0);   // number of epochs

  void Moving   ();
  void Revision ();

  //----------------------------------------------------------------------------
  double immigrationMax;    // maximum immigration rate
  double emigrationMax;     // maximum emigration rate
  double mutationProb;      // mutation probability
  int    elitismCount;      // number of elite solutions
  int    speciesMax;        // maximum number of species

  private: //-------------------------------------------------------------------
  struct S_HabitatData
  {
      int    speciesCount;     // number of species in the habitat
      double immigration;      // immigration rate
      double emigration;       // emigration rate
      double probability;      // probability of existence
  };

  S_HabitatData habitatData   [];  // data for each habitat
  double        probabilities [];  // probabilities for counting mutations

  // Auxiliary methods
  void   InitializePopulation ();
  void   CalculateRates       ();
  void   Migration            ();
  void   Mutation             ();
  double CalculateProbability (int speciesCount);
};
//——————————————————————————————————————————————————————————————————————————————

Init()メソッドは、BBOアルゴリズムの実行開始前に必要な設定をおこないます。まず、各種チェックやパラメータ設定を含む基本的な初期化処理を実行し、その後、生息地データや、種数に応じた存在確率（突然変異計算に用いる確率）を格納するためのメモリを確保します。続いて、各生息地における種数に基づいて移住確率を計算し、それらを正規化します。処理が正常に完了した場合はtrueを返します。

//——————————————————————————————————————————————————————————————————————————————
bool C_AO_BBO::Init (const double &rangeMinP  [],  // minimum values
                     const double &rangeMaxP  [],  // maximum values
                     const double &rangeStepP [],  // step change
                     const int     epochsP = 0)    // number of epochs
{
  if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false;

  //----------------------------------------------------------------------------
  // Initialize arrays for each habitat
  ArrayResize (habitatData,   popSize);
  ArrayResize (probabilities, speciesMax + 1);

  // Calculate probabilities for different numbers of species
  double sum = 0.0;
  for (int i = 0; i <= speciesMax; i++)
  {
    probabilities [i] = CalculateProbability (i);
    sum += probabilities [i];
  }

  // Normalization of probabilities
  if (sum > 0)
  {
    for (int i = 0; i <= speciesMax; i++)
    {
      probabilities [i] /= sum;
    }
  }

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

Moving()メソッドは、BBOアルゴリズムの主要な最適化サイクルを実装しています。メソッドが初めて呼び出された際には、まずrevisionフラグの状態を確認します。このフラグが個体群がまだ生成されていない状態を示している場合は、個体群の初期化が実行されます。初期化では、ランダムな解の生成、適応度の評価、および各種初期パラメータの設定がおこなわれます。初期化後、このフラグは初期化済みを示す値に設定されます。

初期化が完了すると、アルゴリズムサイクルに特有の一連の処理が実行されます。まず、解の個体群を適応度の値に基づいてソートし、最良および最悪のエージェントを特定します。この処理は、後続の移住および突然変異を適切に制御するために必要です。続いて、各生息地の現在の状態と解の品質に基づいて、種の交換に関する確率および移住率を計算します。これらのパラメータは、種がどのように生息地間を「移住」するかを決定します。この段階で、生息地間におけるSIV (Suitability Index Variables)の交換が実行されます。

その結果、種数の少ない生息地は、より豊かな生息地から解の特徴(SIV)を受け取り、解空間の探索能力が向上します。移住処理の後には、多様性を維持するために解へランダムな変化を加える突然変異処理がおこなわれます。突然変異の発生確率は、解の現在の状態やアルゴリズムのパラメータに依存する場合があります。最後に、各解の現在の適応度値を保存します。これらの値は、次回の反復における個体群のソートや解析に利用されます。

//+----------------------------------------------------------------------------+
//| Basic optimization method                                                  |
//+----------------------------------------------------------------------------+
void C_AO_BBO::Moving ()
{
  // First iteration - initialization of the initial population
  if (!revision)
  {
    InitializePopulation ();
    revision = true;
    return;
  }

  // Main optimization
  // 1. Sort the population by HSI (fitness)
  static S_AO_Agent aTemp []; ArrayResize (aTemp, popSize);
  u.Sorting (a, aTemp, popSize);

  // 2. Calculate immigration and emigration rates
  CalculateRates ();

  // 3. Migration (exchange of SIVs between habitats)
  Migration ();

  // 4. Probability-based mutation
  Mutation ();

  // 5. Save state for the next iteration
  for (int i = 0; i < popSize; i++)
  {
    a [i].fP = a [i].f;
  }
}
//——————————————————————————————————————————————————————————————————————————————

Revision()メソッドは、個体群内における現在の最良解を更新するために使用されます。このメソッドは現在の個体群に含まれるすべてのエージェント（解）を走査し、それぞれの適応度値を、現時点での最良結果を保持している変数fBの値と比較します。

いずれかのエージェントがより高い適応度値を持っている場合、その値によってfBを更新するとともに、対応する解のパラメータを最良解格納用の変数へコピーします。その結果、このメソッドの実行後には、最良解を保持する変数には探索過程で発見された中で最も優れた解が常に格納されることになります。

//+----------------------------------------------------------------------------+
//| Update the best solution                                                   |
//+----------------------------------------------------------------------------+
void C_AO_BBO::Revision ()
{
  // Find the best solution in the current population
  for (int i = 0; i < popSize; i++)
  {
    // Update the best solution
    if (a [i].f > fB)
    {
      fB = a [i].f;
      ArrayCopy (cB, a [i].c, 0, 0, WHOLE_ARRAY);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

InitializePopulation()メソッドは、BBOアルゴリズムの初期個体群を生成する役割を担います。このメソッドは、探索空間全域に一様に配置されたpopSize個の個体（生息地）を生成します。

各個体について、coordsの各次元に対し、rangeMin配列で指定された下限値とrangeMax配列で指定された上限値の範囲内でランダムな座標値（解のパラメータ）を生成します。この処理には、指定された範囲内の乱数を生成するu.RNDfromCI()関数が使用されます。

続いて、生成された座標値をrangeStep配列で定義された有効なステップ幅に合わせて丸めます。これにより、解が実行可能な離散探索空間上に配置されることが保証されます。この処理にはSeInDiSp()関数が使用されます。座標の初期化が完了すると、各個体に対応するhabitatData構造体も初期化されます。具体的には、種数(speciesCount)、移入率(immigration)、移出率(emigration)、および生息確率(probability)をすべてゼロに設定します。これらの値は、その後の最適化処理において、移入率・移出率および突然変異確率の計算に使用されます。

//+----------------------------------------------------------------------------+
//| Initialize the initial population                                          |
//+----------------------------------------------------------------------------+
void C_AO_BBO::InitializePopulation ()
{
  // Initialize the initial population uniformly throughout the space
  for (int i = 0; i < popSize; i++)
  {
    for (int c = 0; c < coords; c++)
    {
      // Generate random coordinates within acceptable limits
      a [i].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]);
      // Round to the nearest acceptable step
      a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }

    // Initialize habitat data
    habitatData [i].speciesCount = 0;
    habitatData [i].immigration  = 0.0;
    habitatData [i].emigration   = 0.0;
    habitatData [i].probability  = 0.0;
  }
}
//——————————————————————————————————————————————————————————————————————————————

CalculateRates()メソッドは、各生息地における移入率(immigration)、移出率(emigration)、および生息確率(probability)を計算するために設計されています。

この処理では、ランクに比例した線形モデルが用いられます。具体的には、各解に割り当てられる種数はその順位に応じて決定され、より優れた解ほど多くの種を持つようにモデル化されます。移入率は種数の増加に伴って減少します。つまり、多くの種を持つ解ほど新たな個体を受け入れる確率は低くなります。一方で、移出率は種数の増加に伴って上昇し、種が多い解ほど他の解へ特徴を共有する可能性が高くなります。

生息地の生息確率は、あらかじめ定義された種数ごとの確率分布に基づいて設定されます。もし種数が許容される最大値を超えた場合、その生息地の生息確率はゼロに設定されます。

//+----------------------------------------------------------------------------+
//| Calculate immigration and emigration rates                                 |
//+----------------------------------------------------------------------------+
void C_AO_BBO::CalculateRates ()
{
  // For the linear migration model
  for (int i = 0; i < popSize; i++)
  {
    // The number of species is inversely proportional to the rank (the best solutions have more species)
    habitatData [i].speciesCount = speciesMax - (i * speciesMax / popSize);

    // The rate of immigration decreases as the number of species increases
    habitatData [i].immigration = immigrationMax * (1.0 - (double)habitatData [i].speciesCount / speciesMax);

    // The rate of emigration increases with the number of species
    habitatData [i].emigration = emigrationMax * (double)habitatData [i].speciesCount / speciesMax;

    // Probability of habitat existence
    if (habitatData [i].speciesCount <= speciesMax)
    {
      habitatData [i].probability = probabilities [habitatData [i].speciesCount];
    }
    else
    {
      habitatData [i].probability = 0.0;
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Migration()メソッドは、個体群内の生息地間でSIV（Suitability Index Variables：解を構成する各変数、すなわち座標値）の交換をおこなう移住プロセスを実装しています。この仕組みは、移入率が高い生息地（種数が少ない解）が、移出率の高い生息地（種数が多い解）からSIVを受け取るという考え方に基づいています。

処理はまず個体群全体を走査するループとして実行されますが、その際にelitismCountで指定された上位のエリート個体は移住対象から除外されます。これらの解は最良解として保持され、変更は加えられません。各生息地について、まずその生息地が今回の反復で移住対象となるかどうかが確率的に決定されます。この確率はhabitatData[i].immigration（当該生息地の移入率）に基づきます。移住対象として選ばれた場合、その生息地のすべての座標(SIV)について順に処理がおこなわれます。座標ごとに再び確率判定がおこなわれ、同様に移入率に基づいてその値が変更対象となるかどうかが決定されます。変更の確率はhabitatData[i].immigrationの値によっても決定されます。

変更対象となった場合、その座標値を取得する「供給元」となる生息地が選択されます。この選択にはルーレット選択が用いられ、各生息地のhabitatData[j].emigration（移出率）に比例した確率で決定されます。これにより、移出率の高い生息地ほど選ばれやすくなります。また、同一生息地が自身の供給元として選ばれないように考慮されます。供給元が決定されると、その生息地の対応するSIV値が現在の生息地へコピーされます。

最終的にこのメソッドは、種数の少ない生息地が情報を受け取り、種数の多い生息地が情報を提供するという制御された情報交換プロセスを実現します。これにより、優れた(SIV)解の特徴が個体群全体へ拡散される一方で、最良解そのものは保護される仕組みになっています。

//+----------------------------------------------------------------------------+
//| Migration (exchange of SIVs between habitats)                              |
//+----------------------------------------------------------------------------+
void C_AO_BBO::Migration ()
{
  for (int i = 0; i < popSize; i++)
  {
    // Skip elite solutions
    if (i < elitismCount) continue;

    // Determine whether the habitat will be modified
    if (u.RNDprobab () < habitatData [i].immigration)
    {
      // For each coordinate (SIV)
      for (int c = 0; c < coords; c++)
      {
        // Determine whether this coordinate will be modified
        if (u.RNDprobab () < habitatData [i].immigration)
        {
          // Select a migration source based on emigration rates 
          double sumEmigration = 0.0;
          for (int j = 0; j < popSize; j++)
          {
            if (j != i) sumEmigration += habitatData [j].emigration;
          }

          if (sumEmigration > 0)
          {
            // Roulette source selection
            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)
                {
                  // Copy SIV from habitat j to habitat i
                  a [i].c [c] = a [j].c [c];
                  break;
                }
              }
            }
          }
        }
      }
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Mutation()メソッドは、個体群内の生息地に対して突然変異を適用する処理を実装しています。この操作の目的は、解にランダムな変化を導入することで局所最適解への収束を回避し、未探索領域を探索する能力を高めることにあります。

Migration()メソッドと同様に、上位のエリート解（elitismCountで指定された先頭の生息地）は突然変異の対象から除外されます。これは、これまでに得られた最良解を保持するための重要な設計です。それ以外の各生息地については、まず突然変異確率が計算されます。この確率は生息地の生息確率(habitatData [i].probability)が高くなるほど低くなります。つまり、生息確率が低い生息地ほど突然変異が発生しやすくなり、これには非常に良い解や非常に悪い解といった極端な状態の解も含まれます。この仕組みにより、探索の多様性が確保されます。

乱数が計算された突然変異率を下回った場合、その生息地に対して突然変異が発生します。まず、すべての座標の中からランダムに1つのmutateCoord (SIV)座標が選択されます。その後、指定された範囲内で新しいランダム値が生成され、その値が選択された座標に代入されます。さらにSeInDiSp関数によって値が制約範囲内に収まるよう調整されます。

このようにMutation()メソッドは探索過程にランダム性を導入し、未探索領域における新たな有望解の発見を促進します。また、生息確率に基づいて突然変異率を調整することで、探索と活用のバランスが適切に維持されます。

//+----------------------------------------------------------------------------+
//| Probability-based mutation                                                 |
//+----------------------------------------------------------------------------+
void C_AO_BBO::Mutation ()
{
  for (int i = 0; i < popSize; i++)
  {
    // Skip elite solutions
    if (i < elitismCount) continue;

    // The mutation rate is inversely proportional to the probability of existence
    double mutationRate = mutationProb * (1.0 - habitatData [i].probability);

    if (u.RNDprobab () < mutationRate)
    {
      // Select a random coordinate for mutation
      int mutateCoord = MathRand () % coords;

      // Generate a new value for the selected coordinate
      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()メソッドは、種数に基づいて各生息地の生息確率を計算するために使用されます。このメソッドでは単純化されたモデルが採用されており、種数の平衡値付近で最大の確率が得られるようになっています。具体的には、種数が範囲の中央（speciesMax / 2）に近い場合に生息確率が最大となり、その値から離れるほど確率はガウス曲線に従って急速に減少します。つまり、speciesCountが平衡値から遠ざかるほど、生息地が存在する確率は低くなります。

この仕組みにより、本メソッドは生物多様性の観点から見た生息地の「適性」を簡略化してモデル化しています。結果として、種数が極端に偏った生息地よりも、適度な多様性を持つ生息地の方が高い生息確率を持つという分布が形成されます。これは、生物多様性に基づいた、簡略化されているが効果的な生息地の「適性」モデルを表しています。

//+----------------------------------------------------------------------------+
//| Calculate the probability for a given number of species                    |
//+----------------------------------------------------------------------------+
double C_AO_BBO::CalculateProbability (int speciesCount)
{
  // Simplified probability model
  // Maximum probability in the middle of the range (equilibrium)
  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

Hillyテスト関数のBBO

Forest

Forestテスト関数のBBO

Megacity

Megacityテスト関数のBBO

テスト結果に基づくと、この洗練されたBBOアルゴリズムはランキング表の上位に入っており、全体で12位という高い順位を獲得しています。

#	AO	詳細	Hilly			Hilly ファイナル	Forest			Forest ファイナル	Megacity（離散）			Megacity ファイナル	ファイナル結果	％ MAX
#	AO	詳細	10p(5F)	50p(25F)	1000p(500F)	Hilly ファイナル	10p(5F)	50p(25F)	1000p(500F)	Forest ファイナル	10p(5F)	50p(25F)	1000p(500F)	Megacity ファイナル	ファイナル結果	％ MAX
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	コードロックアルゴリズム(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	動物移動最適化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)進化戦略	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	彗星の尾アルゴリズム(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	時間進化移動アルゴリズム(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	確率的拡散探索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	ビリヤード最適化アルゴリズム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	アーチェリーアルゴリズム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	社会集団の進化(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	等方的焼きなまし(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	生物地理学に基づく最適化	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	人工協調探索	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	弁証法的アルゴリズム	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	ブラックホールアルゴリズム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	無政府社会最適化	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	ロイヤルフラッシュ最適化(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	原子軌道探索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	亀甲進化アルゴリズム(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	差分進化	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	レストラン経営達人アルゴリズム(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	化学反応の最適化	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	血液型遺伝最適化(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	鳥群アルゴリズム	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	ハーモニー検索	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	苗木の播種と育成	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	細菌走化性最適化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	アフリカ水牛の最適化	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)進化戦略	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	フラクタルベースのアルゴリズム	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	タブーサーチ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	ブレインストーム最適化	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	鯨最適化アルゴリズム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	人工電界アルゴリズム	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	人工生態系ベースの最適化アルゴリズム	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	ラクダアルゴリズム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	蟻コロニー最適化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	細菌採食の最適化：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	シンプル最適化アルゴリズム	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	人工蜂の巣アルゴリズム	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	大気雲モデルの最適化	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	適応モーメント推定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	カオスゲーム最適化	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	サンゴ礁最適化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	人工部族アルゴリズム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	ニューロボイド最適化アルゴリズム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アルゴリズムはテストにおいて優れた結果を示し、全45種類の集団ベース最適化アルゴリズムの中で総合12位、性能スコア58.5%という評価を獲得しました。これは、このようにエレガントかつ直感的な自然メタファーに基づくアルゴリズムとしては特筆すべき成果です。

特に注目すべき点は、BBOが中規模から高次元の問題を効率的に処理できる能力を持っていることであり、多くの最適化アルゴリズムが直面する「次元の呪い」に対して高い耐性を示しています。このスケーラビリティの高さは実用上の大きな利点となります。

BBOの概念的基盤である「島間の種の移住」は、単なる美しい比喩にとどまらず、探索と活用のバランスを取るための非常に効率的なメカニズムとして機能していることが確認されました。豊かな生息地が積極的に特徴を共有し、貧しい生息地がそれを受け入れるという線形移住モデルは、より良い解から劣った解へと情報が流れる自然な勾配を形成します。

また、BBOの突然変異オペレーターは特に重要であり、従来の手法とは本質的に異なります。固定的または完全にランダムな確率ではなく、生息地の生息確率に逆比例する理論的モデルに基づいています。これにより、平均的な種数を持つ安定した解は突然変異が起こりにくく、一方で非常に良い解や非常に悪い解といった極端な状態の解はより頻繁に変化します。この適応的な仕組みにより、探索空間の安定性と多様性が自動的に調整されます。

さらに、このアルゴリズムはさまざまな探索ランドスケープに対して優れた安定性を示しており、すべてのテストにおいて一貫して良好な性能を維持し、他の最適化アルゴリズムと比較して大きな性能低下は見られませんでした。

BBOの大きな利点の一つは、その概念的な単純さと高い効率性の両立です。多くの現代的なメタヒューリスティクス手法が多数のパラメータや複雑な演算子を必要とするのに対し、BBOは「移住」「種数」「生息地適性」といった直感的な概念のみで動作します。

これらのテスト結果は、BBOが単なる「もう一つの生物学的着想アルゴリズム」ではなく、既存の主要手法と競合可能な本格的な最適化アルゴリズムであることを示しています。理論的な整合性、計算効率、そして実用性のバランスにより、BBOは現代の大域的最適化手法群において有用な選択肢となります。

tab

図2：対応するテストに応じたアルゴリズムのカラーグラデーション

チャート

図3：アルゴリズムテスト結果のヒストグラム（0から100のスケール、高いほど良い）100は理論上の最大値であり、アーカイブには評価表を計算するためのスクリプトがあります。

BBOの長所と短所

長所

高速
実装がシンプル
幅広い問題次元にわたって良好な結果が得られた

短所

多数のパラメータ

この記事には、最新版のアルゴリズムコードを含むアーカイブが添付されています。記事の著者は、正規アルゴリズムの説明の絶対的な正確さについて責任を負いません。探索性能を向上させるために、それらの多くに変更が加えられています。記事に示された結論と判断は、実験結果に基づいています。

github：https://github.com/JQSakaJoo/Population-optimization-algorithms-MQL5

記事で使用されているプログラム

#	名前	種類	詳細
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テストスタンド

MetaQuotes Ltdによってロシア語から翻訳されました。
元の記事: https://www.mql5.com/ru/articles/18354

添付されたファイル |

ZIPをダウンロード

BBO.zip (219.47 KB)

警告: これらの資料についてのすべての権利はMetaQuotes Ltd.が保有しています。これらの資料の全部または一部の複製や再プリントは禁じられています。

この記事はサイトのユーザーによって執筆されたものであり、著者の個人的な見解を反映しています。MetaQuotes Ltdは、提示された情報の正確性や、記載されているソリューション、戦略、または推奨事項の使用によって生じたいかなる結果についても責任を負いません。

Andrey Dik

I WILL CONSIDER PROPOSALS FOR THE PUBLICATION OF A BOOK (TEXTBOOK) ON OPTIMIZATION ALGORITHMS.
A group for communication on optimization and free product testing://t.me/+vazsAAcney4zYmZi
Attention! My Telegram doppelgangers have appeared, my real nickname is @JQS_aka_Joo
My github with optimization algorithms: https://github.com/JQSakaJoo/Population-optimization-algorithms-MQL5
All my publications: https://www.mql5.com/en/users/joo/publications
I have been developing systems based on machine learning technologies since 2007 and in the field of artificial
intelligence, optimization and forecasting.

この著者による他の記事

ディスカッションに移動

Pythonを用いたIMFデータの取得

PythonでIMFデータを取得する：マクロ経済に基づく通貨戦略に活用するためのIMF（国際通貨基金）データマイニング。マクロ経済は、一般のトレーダーおよびアルゴリズムトレーダーにどのように役立つのでしょうか。

機械学習におけるガウス過程：MQL5による回帰モデル

確率的機械学習モデルとしてのガウス過程(GP)の基本を概説し、合成データを用いて回帰問題への応用例を示します。

PPPとIMFデータを用いた公正な為替レートの算出

Pythonを用いた購買力平価(PPP)ベースの為替レート分析システムの構築。IMFデータを用いて、5つの方法によって理論為替レートを計算するアルゴリズムを開発しました。本記事は、ファンダメンタルな通貨分析、経済データの処理、トレードシステムとの統合に関する実践的なガイドです。完全なコードはオープンソースとして公開されています。

金融時系列における共形予測の考察

共形予測(Conformal Prediction)と、それを実装するMAPIEライブラリについて考察します。このアプローチは機械学習における最も現代的な手法の一つであり、既存のさまざまな機械学習モデルに対するリスク管理に焦点を当てることを可能にします。共形予測それ自体は、データ内のパターンを見つける方法ではありません。これは、既存のモデルが個々のサンプルを予測する際の信頼度を判定するだけであり、信頼性の高い予測を選別できるようにします。