バトルロイヤル最適化(BRO)

内容

1. はじめに
2. アルゴリズムの実装
3. テスト結果

はじめに

メタヒューリスティック最適化の分野では、自然現象や物理法則、進化過程などを模倣したアルゴリズムが多く提案されてきました。その中で近年、新たな着想源として「ビデオゲーム」が登場しています。Battle Royale Optimizer （BRO、バトルロイヤル最適化アルゴリズム）は、Taymaz Rahkar Farshiによって開発された革新的な最適化アルゴリズムであり、PlayerUnknown's Battlegrounds (PUBG)などのバトルロイヤルゲームの仕組みに着想を得ています。

BROは、進化計算、群知能、物理現象ベースの手法に加えて、「ゲームベース」という新たな最適化手法のカテゴリを切り開くものです。これらは広義の集団ベース最適化アルゴリズムに分類されます。従来の群知能アルゴリズムでは、エージェント同士が協力して共通の目的を達成しますが、BROでは各個体は互いに競争し、探索空間内で生存しながら最良の位置を獲得しようとします。

BROの大きな特徴は、「競争」と「ダメージ蓄積」に基づく独自の仕組みです。各解は最近傍解と比較され、敗者はダメージを受けます。一方、勝者のダメージはリセットされます。ダメージが一定の閾値を超えた解は個体群から削除され、新しいランダム解に置き換えられます。これは、PUBGにおいてプレイヤーが致命的なダメージを受けると試合から排除される仕組みに類似しています。この仕組みにより、探索空間を探索するためのメカニズムが提供されます。

アルゴリズムの実装

Battle Royale Optimizer (BRO)アルゴリズムは、多くのプレイヤーが戦場に降り立ち、最終的に1人だけが生き残る仮想世界を比喩的に表現しています。これはバトルロイヤルゲームの本質そのものです。このコンセプトを、最適化問題の解法へと置き換えます。

アルゴリズムの開始時には、探索空間全体にランダムに分布した解の集団を生成します。各解は固有の「プレイヤー」として扱われ、それぞれ位置とその位置における品質（適応度）を持ちます。その後、メインとなる競争サイクルが始まり、各解は最近傍解と比較されます。これは、プレイヤー同士が戦闘で対峙する状況に相当します。

2つの解が「遭遇」すると、それぞれの品質が比較されます。より優れた解は勝者とされ、ダメージは0になります。一方、劣る解は敗者となり、1のダメージを受けます。このダメージカウンタは本アルゴリズムの重要な特徴です。敗者となった解はダメージを受けるだけでなく、集団内で既知の最良解へ向かって自身の位置を移動させることで改善を試みます。この移動は、より安全で有利な場所を見つけて生存しようとする行動を模倣しています。

ある解のダメージが一定の閾値を超えた場合、その解は「ゲームから脱落」し、集団から削除され、新たなランダム解と置き換えられます。これはバトルロイヤルにおいてプレイヤーが脱落し、次の試合で新たなプレイヤーが登場する仕組みに相当します。この仕組みにより、集団の継続的な更新が保証され、解の多様性が維持されます。

さらにアルゴリズムは定期的に探索空間を縮小します。これはバトルロイヤルにおけるプレイエリアの縮小に相当し、プレイヤー同士の距離を強制的に近づけます。探索範囲は現在の最良解の周囲に絞られ、より有望な領域へ集団が集中するようになります。

このアプローチにより、BROアルゴリズムは新しい領域の探索と、既に得られた良い解の活用とのバランスを取ります。敗者はより優れた解へと引き寄せられることで改善傾向を維持し、大きく劣る解は新しいランダム解へ置き換えられることで探索空間に探索の多様性をもたらします。同時に、周期的な境界縮小が有望な領域における局所探索を強化します。

図1：BROアルゴリズムの動作

この図は、Battle Royale Optimizer (BRO)アルゴリズムの主要構成要素を示しています。探索空間は2次元領域として表現され、等高線は最適化関数の地形を示しています（明るい領域ほど良い解を表します）。大域最良解は、最も高い「山」の中心にある赤い星で示されています。勝者は緑の点で示されます。これらは近傍解との比較でダメージ0の解です。敗北した解は黄色（ダメージ1）およびオレンジ（ダメージ2）の点で表されます。新たなランダム解は青い点で示され、ダメージが閾値を超えた際に出現します。敗者となった解は最良解へ向かって移動し（破線矢印で示されます）、探索空間の縮小は最良解を中心としたオレンジ色の点線枠として表現されています。

アルゴリズムの主要ステージは、初期化、近傍との比較、より優れた解への移動、そして探索空間の縮小です。

BROアルゴリズムでは解同士が競争し、敗者は「ダメージ」を受けます。ダメージが一定値を超えた解は新しいランダム解に置き換えられます。アルゴリズムの原理が明確になったところで、疑似コードの記述へ進みます。

初期化

1. popSize（集団サイズ）の解を生成します
2. 各解のダメージカウンタを0に初期化します
3. 最大ダメージ閾値maxDamageを設定します
4. エポック数（反復回数）を設定します
5. 探索空間を周期的に縮小するための初期デルタ値を計算します

基本アルゴリズム

1. 初期集団の生成
   • 各解について、以下を実行します
     • 与えられた探索空間内でランダムに座標を生成します
2. 各エポックにおいて、以下を実行します
   • より優れた解が見つかった場合は、大域最良解を更新します
   • 解同士の「バトル」
     • 各解について、以下を実行します
       • 最近傍解（距離が最小の解）を探索します
       • 現在の解と近傍解の品質を比較します
         • 現在の解の方が良い場合
           • 現在の解のダメージカウンタをリセットします
           • 近傍解のダメージカウンタを1増加させます
           • 敗者（近傍解）は最良解へ向かって移動します
         • 近傍解の方が良い場合
           • 現在の解のダメージカウンタを1増加させます
           • 近傍解のダメージカウンタをリセットします
           • 敗者（現在の解）は最良解へ向かって移動します
   • ダメージが大きい解の処理
     • 各解について、以下を実行します
       • ダメージカウンタ ≥ maxDamage の場合
         • ダメージカウンタをリセットします
         • その解を新しいランダム解に置き換えます
   • 探索空間の周期的縮小
     • 現在のエポック番号がdeltaで割り切れる場合
       • 集団全体の座標分布に対する標準偏差を計算します
       • 最良解の周囲に探索空間を縮小します
       • deltaを更新します
3. 発見された最良解を返します

本アルゴリズムでは、以下の数式が使用されます。

• 探索空間を縮小するための初期デルタ値：delta = ⌊epochs / log₁₀(epochs)⌋
• 解同士のユークリッド距離： distance = √(∑(a[idx1][c] - a[idx2][c])²)
• 劣る解のグローバル最良解への移動： a[i][c] = a[i][c] + r × (cB[c] - a[i][c])
• 各座標における平均値：mean[c] = (∑a[i][c]) / popSize
• 各座標における標準偏差： sdValues[c] = √(∑(a[i][c] - mean[c])² / popSize)
• 探索空間縮小のための境界更新： newMin[c] = cB[c] - sdValues[c] newMax[c] = cB[c] + sdValues[c]
• 縮小後のデルタ更新： delta = delta + ⌊delta / 2⌉

著者は、探索空間を周期的に縮小するためのデルタパラメータとして次の式を提案しています：Δ (delta) = maxEpochs / log₁₀(maxEpochs)。グラフは以下のとおりです。

図2：エポック数に対するデルタ値の依存性

delta = epochs/log₁₀(epochs)は、BROアルゴリズムの動作において重要な役割を持ちます。デルタは探索空間を何回の反復ごとに縮小するかを決定します。グラフから分かるように、デルタ値はエポック数の増加とともに増加しますが、対数で割られるため、その増加速度はエポック数そのものよりも緩やかになります。このため非線形な関係が生じ、いくつかの利点が得られます。すなわち、最適化の初期段階（エポック数が少ない場合）では探索空間の縮小が比較的頻繁に発生し、アルゴリズムは早い段階で有望な領域へ集中しやすくなります。一方で後期段階（エポック数が多い場合）では縮小の頻度が低下し、すでに見つかった有望領域をより詳細かつ精密に探索することが可能になります。

私は実験において、デルタパラメータの式に対して対数を二重に適用する修正を加えました。このバージョンは、元の式よりも良好な性能を示しました。

// Calculate the initial delta to narrow the search space
  delta = (int)MathFloor(epochs / MathLog(MathLog(epochs)));

では、コーディングに進みます。ここではカスタムクラスC_AO_BROを実装します。このクラスは基盤クラスC_AOを継承しており、これはC_AOクラスのすべてのpublicおよびprotectedメンバーを引き継ぎ、それらの振る舞いをオーバーライドできることを意味します。本クラスは、バトルロイヤルのコンセプトに基づく最適化アルゴリズムの実装となります。

1. クラスのpublicメンバー

• popSize：集団サイズを設定します。
• maxDamage：最大ダメージ閾値を設定します。これは、解が「敗退」するまでに耐えられるヒット数を表します。
• SetParams()：params配列に格納された値をもとにpopSizeとmaxDamageを更新します。これにより、実行時にアルゴリズムのパラメータを変更できます。
• Init()：アルゴリズムの初期化メソッドです。以下のパラメータを受け取ります。
  • rangeMinP []：各変数の探索範囲の最小値
  • rangeMaxP []：各変数の探索範囲の最大値
  • rangeStepP []：各変数の探索ステップ
  • epochsP：アルゴリズムのエポック（反復回数）。デフォルトは0
• Moving ()：探索空間内で解を移動・更新する基本ロジックを実装します。
• Revision ()：現在の解を評価・修正するロジックを実装します。この処理では各解が受けた「ダメージ」が評価されます。
• maxDamage：各解が耐えられる最大ダメージ閾値を保持するpublicメンバー

2. クラスのprivateメンバー

• delta：探索空間を縮小するための間隔。最適化の過程で探索ステップサイズを適応的に調整するために使用されます。
• damages []：各解が受けた「ダメージ」の累積値を保持する配列 
• epoch：現在のエポック
• epochs：アルゴリズムの最大エポック数

3. 補助メソッド

• FindNearestNeighbor()：指定されたインデックスの解に対して最近傍解を探索します。解同士の相互作用に使用されます。
• CalculateDistance()：2つの解間の距離を計算します（インデックスで指定）。
• CalculateStandardDeviations ()：集団内の解の標準偏差を計算します。これは集団の多様性を評価し、探索パラメータの調整に使用されます。
• ShrinkSearchSpace()：探索空間を縮小する処理をおこないます。これはアルゴリズムを最適解へ収束させるための標準的な手法です。

全体の考え方

C_AO_BROクラスはバトルロイヤル最適化アルゴリズムを実装したものであり、その基本的な考え方は以下の通りです。

1. 初期化：与えられた探索空間内にランダムな解の集団を生成します。
2. 評価：各解を目的関数（適応度関数）で評価します。
3. バトルロイヤル：解同士が互いに競争し、目的関数値に基づいて比較されます。
4. ダメージ：バトルの結果に応じて一部の解が「ダメージ」を受けます。
5. 排除：ダメージがmaxDamageを超えた解は集団から削除されます。
6. 再生成（置換）：削除された解は新しいランダムな解に置き換えられます。
7. 探索範囲の縮小：探索を有望領域に集中させるため、空間が周期的に縮小されます。
8. 反復：ステップ2〜7を指定されたエポック数だけ繰り返します。

//——————————————————————————————————————————————————————————————————————————————
class C_AO_BRO : public C_AO
{
  public: //--------------------------------------------------------------------
  ~C_AO_BRO () { }
  C_AO_BRO ()
  {
    ao_name = "BRO";
    ao_desc = "Battle Royale Optimizer";
    ao_link = "https://www.mql5.com/ja/articles/17688";

    popSize   = 100;    // population size
    maxDamage = 3;      // maximum damage threshold

    ArrayResize (params, 2);

    params [0].name = "popSize";   params [0].val = popSize;
    params [1].name = "maxDamage"; params [1].val = maxDamage;
  }

  void SetParams ()
  {
    popSize   = (int)params [0].val;
    maxDamage = (int)params [1].val;
  }

  bool Init (constdouble &rangeMinP [],// minimum search range
             const double &rangeMaxP [],  // maximum search range
             const double &rangeStepP [], // search step
             const int     epochsP = 0);  // number of epochs

  void Moving ();
  void Revision ();

  //----------------------------------------------------------------------------
  int maxDamage;    // maximum damage threshold

  private: //-------------------------------------------------------------------
  int    delta;      // interval for shrinking the search space
  int    damages []; // amount of damage for each solution
  int    epoch;      // current epoch
  int    epochs;     // maximum number of epochs

  // Auxiliary methods
  int    FindNearestNeighbor (int index);
  double CalculateDistance (int idx1, int idx2);
  void   CalculateStandardDeviations (double &sdValues []);
  void   ShrinkSearchSpace ();
};
//——————————————————————————————————————————————————————————————————————————————

Init()メソッドはBROアルゴリズムの初期化をおこないます。まず、渡された探索範囲およびステップ幅を用いて標準初期化をおこなうためにStandardInit()を呼び出します。StandardInitがfalseを返した場合、Init()もfalseを返し、初期化エラーであることを示します。次に、damages配列を初期化します。これはpopSize分の各解に対してメモリを確保し、各解の初期ダメージ値を0に設定する処理です。その後、アルゴリズムの総エポック数epochsを設定し、現在のエポックepochを0にリセットします。

さらに、探索空間を段階的に縮小するために、総エポック数に基づいてdeltaの値を計算します。deltaが0以下になった場合は、deltaを1に設定します。総じてこのメソッドは、アルゴリズムの実行に必要な基本パラメータおよびデータ構造を動作可能な状態に初期化します。

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

  //----------------------------------------------------------------------------
  // Initialize damage counters for each solution
  ArrayResize (damages, popSize);
  ArrayInitialize (damages, 0);

  // Set epochs
  epochs = epochsP;
  epoch  = 0;

  // Calculate the initial 'delta' to narrow the search space
  delta = (int)MathFloor (epochs / MathLog10 (epochs));
  if (delta <= 0) delta = 1;

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

Moving()メソッドは、解集団の初期化処理を実装します。各解の各座標は、rangeMinとrangeMaxで指定された範囲内でランダムに生成され、さらに一定のrangeStepに従って離散化されます。本メソッドは、集団の初期化が一度だけ実行されることを保証します。 

/——————————————————————————————————————————————————————————————————————————————
void C_AO_BRO::Moving ()
{
  if (!revision)
  {
    // Initialize the population with random decisions
    for (int i = 0; i < popSize; i++)
    {
      for (int c = 0; c < coords; c++)
      {
        double coordinate = u.RNDfromCI (rangeMin [c], rangeMax [c]);
        a [i].c [c] = u.SeInDiSp (coordinate, rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }

    revision = true;
  }
}
//——————————————————————————————————————————————————————————————————————————————

Revision()メソッドは、BRO最適化アルゴリズムにおける重要な処理ステップです。本メソッドの各反復では、まず現在の集団内において、現在の大域最良解よりも優れた解が存在する場合、その解を新たな大域最良解として更新します。

次に、各解について近傍解との比較をおこないます。各解に対して集団内で最近傍解を探索し、その後、両者の目的関数値を比較します。このペアの中でより優れた解は勝者とされ、ダメージカウンタがリセットされます。一方で劣る解はダメージカウンタが増加します。また、ペア内のより劣る解は、大域最良解の方向へと移動します。

続いて、「ダメージ」が蓄積された解の置換処理がおこなわれます。ある解のダメージが maxDamage に達した場合、その解は集団から削除され、新たにランダム生成された解に置き換えられます。さらに、delta 変数に応じて探索領域の縮小が周期的に実行されます。この処理は複数回のアルゴリズム反復の中で繰り返されます。このように、解は近傍解との比較を通じてより良い探索領域へと移動しながら、有望な領域へ徐々に収束していきます。

//——————————————————————————————————————————————————————————————————————————————
void C_AO_BRO::Revision ()
{
  epoch++;

  // Update the global best solution
  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);
    }
  }

  // Compare each solution with its nearest neighbor and update damage counters
  for (int i = 0; i < popSize; i++)
  {
    int neighbor = FindNearestNeighbor (i);

    if (neighbor != -1)
    {
      if (a [i].f >= a [neighbor].f)
      {
        // Solution i wins
        damages [i] = 0;
        damages [neighbor]++;

        // The loser (neighbor) moves toward the best solution
        for (int c = 0; c < coords; c++)
        {
          double r = u.RNDfromCI (0, 1);
          a [neighbor].c [c] = a [neighbor].c [c] + r * (cB [c] - a [neighbor].c [c]);
          a [neighbor].c [c] = u.SeInDiSp (a [neighbor].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
        }
      }
      else
      {
        // Solution i loses
        damages [i]++;
        damages [neighbor] = 0;

        // The loser (i) moves to the best solution
        for (int c = 0; c < coords; c++)
        {
          double r = u.RNDfromCI (0, 1);
          a [i].c [c] = a [i].c [c] + r * (cB [c] - a [i].c [c]);
          a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
        }
      }
    }
  }

  // Check if any solution has reached maximum damage and replace it
  for (int i = 0; i < popSize; i++)
  {
    if (damages [i] >= maxDamage)
    {
      // Reset the damage counter
      damages [i] = 0;

      // Generate a new random solution
      for (int c = 0; c < coords; c++)
      {
        double coordinate = u.RNDfromCI (rangeMin [c], rangeMax [c]);
        a [i].c [c] = u.SeInDiSp (coordinate, rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }
  }

  // Periodic narrowing of the search space
  if (epochs > 0 && epoch % delta == 0)
  {
    ShrinkSearchSpace ();
    // Update delta
    delta = delta + (int)MathRound (delta / 2);
  }
}
//——————————————————————————————————————————————————————————————————————————————

FindNearestNeighbor()メソッドは、集団内において指定されたindexの解に対する最近傍解のインデックスを探索します。本メソッドは全ての解を順に走査し、対象となる解（インデックス）自身を除外したうえで、それぞれとの距離を計算します。そして、最も距離が小さい解のインデックスを返します。近傍解を見つけることができない場合（集団内に解が1つしか存在しない場合など）は-1を返します。要するに本メソッドは、与えられた解に対して最近傍解を求める処理をおこないます。

//——————————————————————————————————————————————————————————————————————————————
int C_AO_BRO::FindNearestNeighbor (int index)
{
  double minDistance = DBL_MAX;
  int nearestIndex = -1;

  for (int i = 0; i < popSize; i++)
  {
    if (i == index) continue;

    double distance = CalculateDistance (index, i);
    if (distance < minDistance)
    {
      minDistance = distance;
      nearestIndex = i;
    }
  }

  return nearestIndex;
}
//——————————————————————————————————————————————————————————————————————————————

CalculateDistance()メソッドは、idx1とidx2で指定された2つの解の間のユークリッド距離を計算します。まず distanceSum変数を0で初期化し、この変数に各座標差の二乗和を蓄積していきます。次にforループですべての次元（座標）を順に走査します。各反復において、idx1とidx2に対応する解の同一インデックスの座標同士の差を計算し、その差を二乗した値をdistanceSumに加算します。

ループ終了後、distanceSumの平方根を返します。これが2つの解間のユークリッド距離となります。最終的に本メソッドは、探索空間内における2つの解の「距離」を数値として返します。この値が大きいほど、2つの解は探索空間上で離れていることを意味します。

//——————————————————————————————————————————————————————————————————————————————
double C_AO_BRO::CalculateDistance (int idx1, int idx2)
{
  double distanceSum = 0.0;

  for (int c = 0; c < coords; c++)
  {
    double diff = a [idx1].c [c] - a [idx2].c [c];
    distanceSum += diff * diff;
  }

  return MathSqrt (distanceSum);
}
//——————————————————————————————————————————————————————————————————————————————

CalculateStandardDeviations()メソッドは、集団内の各解の各座標に対する標準偏差を計算し、その結果をsdValues配列に格納します。まず、入力配列sdValuesは、各coords座標ごとの標準偏差を格納できるようにサイズ変更されます。次に、ループは各解の各座標を順に走査し、標準偏差を計算します。本メソッドでは、現在の座標に対する偏差平方和を保持する変数がリセットされ、同時にその平均値もリセットされます。その後、集団内のすべての解について、現在のc座標の値を合計し、座標ごとの平均値を算出します。 

偏差平方和の計算：ループは集団内のすべての解を走査し、現在の座標における平均値からの偏差平方和を計算します。各反復において、i番目の解の c 座標の値とその平均値との差を求め、その差の二乗を偏差平方和に加算します。標準偏差は、この偏差平方和を集団サイズで割った値の平方根として計算されます。最終的に得られた値は、対応するsdValues配列の要素に格納されます。

最終的に本メソッドは、集団内の各解の各座標における値のばらつきを示す指標を計算し、その結果を渡されたsdValues配列に格納します。また、標準偏差は各座標の値が平均値の周囲でどの程度変動しているかを示す尺度となります。

//——————————————————————————————————————————————————————————————————————————————
void C_AO_BRO::CalculateStandardDeviations (double &sdValues [])
{
  ArrayResize (sdValues, coords);

  for (int c = 0; c < coords; c++)
  {
    double sum = 0.0;
    double mean = 0.0;

    // Calculate the average
    for (int i = 0; i < popSize; i++) mean += a [i].c [c];

    mean /= popSize;

    // Calculate the sum of squared deviations
    for (int i = 0; i < popSize; i++)
    {
      double diff = a [i].c [c] - mean;
      sum += diff * diff;
    }

    sdValues [c] = MathSqrt (sum / popSize);
  }
}
//——————————————————————————————————————————————————————————————————————————————

ShrinkSearchSpace()メソッドは、各座標の標準偏差およびこれまでに発見された最良解の位置に基づいて探索空間を縮小します。言い換えると、すでに良好な解が存在するより有望な領域へ探索を集中させる処理です。

まず、標準偏差を計算します。これは CalculateStandardDeviations()メソッドを呼び出すことで実行され、集団内の各解の各座標に対する標準偏差が算出され、その結果が sdValues 配列に格納されます。これにより、各座標値が集団全体でどの程度ばらついているかが把握できます。 次に、新しい探索範囲の境界を計算します。新しい境界は最良解を中心として設定され、その幅は標準偏差によって決定されます。標準偏差が小さい場合は最良解の周辺に探索が集中し、標準偏差が大きい場合はより広い範囲で探索が維持されます。 最後に、探索範囲が元の許容可能な解空間を超えないように範囲チェックをおこないます。

//——————————————————————————————————————————————————————————————————————————————
void C_AO_BRO::ShrinkSearchSpace ()
{
  double sdValues [];
  CalculateStandardDeviations (sdValues);

  for (int c = 0; c < coords; c++)
  {
    // The new boundaries are centered around the best solution with a standard deviation width
    double newMin = cB [c] - sdValues [c];
    double newMax = cB [c] + sdValues [c];

    // Make sure the new bounds are within the original constraints
    if (newMin < rangeMin [c]) newMin = rangeMin [c];
    if (newMax > rangeMax [c]) newMax = rangeMax [c];

    // Update the boundaries
    rangeMin [c] = newMin;
    rangeMax [c] = newMax;
  }
}
//——————————————————————————————————————————————————————————————————————————————

テスト結果

テストの結果、アルゴリズムはHilly関数およびForest関数に対してはかなり良好に動作することが確認できます。しかしながら、離散的なMegacity関数においては、収束性能が大幅に弱くなることが分かりました。

BRO|Battle Royale Optimizer|50.0|3.0|
=============================
5 Hilly's; Func runs:10000; result:0.7494493002235458
25 Hilly's; Func runs:10000; result:0.4983307394255448
500 Hilly's; Func runs:10000; result:0.27994639979348446
=============================
5 Forest's; Func runs:10000; result:0.6962444245506945
25 Forest's; Func runs:10000; result:0.3845619185097379
500 Forest's; Func runs:10000; result:0.20427058729050862
=============================
5 Megacity's; Func runs:10000; result:0.3815384615384616
25 Megacity's; Func runs:10000; result:0.21107692307692308
500 Megacity's; Func runs:10000; result:0.10607692307692404
=============================
All score:3.51150 (39.02%)

この可視化は、結果値のばらつきと、離散的なMegacity関数における探索性能の弱さを示しています。

Hillyテスト関数のBRO

Forestテスト関数のBRO

Megacityテスト関数のBRO

テスト結果に基づくと、BROアルゴリズムは集団ベース最適化アルゴリズムのランキング表において最下位となっています。

#	AO	詳細	Hilly			Hilly ファイナル	Forest			Forest ファイナル	Megacity（離散）			Megacity ファイナル	ファイナル 結果	% MAX
			10p(5F)	50p(25F)	1000p(500F)		10p(5F)	50p(25F)	1000p(500F)		10p(5F)	50p(25F)	1000p(500F)
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	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
13	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
14	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
15	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
16	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
17	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
18	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
19	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
20	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
21	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
22	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
23	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
24	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
25	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
26	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
27	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
28	(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
29	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
30	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
31	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
32	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
33	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
34	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
35	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
36	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
37	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
38	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
39	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
40	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
41	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
42	CFO	中心力最適化	0.60961	0.54958	0.27831	1.43750	0.63418	0.46833	0.22541	1.32792	0.57231	0.23477	0.09586	0.90294	3.668	40.76
43	ASHA	人工シャワーアルゴリズム	0.89686	0.40433	0.25617	1.55737	0.80360	0.35526	0.19160	1.35046	0.47692	0.18123	0.09774	0.75589	3.664	40.71
44	ASBO	適応型社会行動最適化(ASBO)	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
45	BRO	バトルロイヤル最適化	0.74945	0.49833	0.27995	1.52773	0.69624	0.38456	0.20427	1.28507	0.38154	0.21108	0.10608	0.69870	3.512	39.02
	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

まとめ

BROアルゴリズムは、メタヒューリスティック最適化において興味深いアプローチを示しており、解同士が競い合うというバトルロイヤルのメタファーを用いた「ゲームベース」手法への道を開くものです。本アルゴリズムの強みとしては、概念的なシンプルさ、直感的な理解のしやすさ、実装の比較的容易さ、集団の統計的特性に基づく探索空間の自動的な縮小、そして局所的な競争における最近傍概念の活用が挙げられます。BROアルゴリズムは非常に有望な最適化手法であり、その潜在能力はまだ十分に引き出されていない段階にあります。

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

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

BROの長所と短所

長所

1. 興味深いアイディア
   
2. 実装がシンプル
3. 将来的な発展性が期待できる

短所

1. 離散関数に関する結果が弱い
   

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

• 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_BRO.mq5	スクリプト	BROテストスタンド