バックトラッキング探索アルゴリズム(BSA)

内容

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

はじめに

可能性が無限に広がる迷宮の中では、一歩ごとに成功にも行き止まりにもつながる可能性があります。そのような中で賢い探索者は、目に見えない痕跡を残します。それは儚いものでありながら、同時に最も信頼できるもの、すなわち、過去に通った経路の記憶です。この「過去を振り返ることで未来を見る」という考え方が、この最適化アルゴリズムの核心にあります。 未知への一歩は常に過去の経験を踏まえて行われ、歴史は羅針盤となり、記憶は地図となります。

本記事では、探索戦略の観点から特に興味深いと感じたアルゴリズムを取り上げます。バックトラッキング検索アルゴリズム(BSA)は、2013年にPinar Civiciogluによって提案された、実数値最適化問題を解くための新しい進化的アルゴリズムです。この手法は「過去の経験から学習する」ことで最適解を探索する方法の一つです。 

アルゴリズムの実装

BSAは進化的アルゴリズムの原理に基づいて動作しますが、独自の特徴として2つの集団を使用します。

• 現在の集団(P)：能動的に進化している集団
• 履歴集団(oldP)：過去の世代からランダムに選ばれた集団

BSAはランダムな突然変異戦略を用いており、各対象個体に対して、1つの方向づけられた候補解のみを生成します。突然変異の式は次の通りです。

Mutant = P + F × (oldP - P)

ここでFは探索のステップサイズを制御する振幅係数です。

BSAの交叉（クロスオーバー）プロセスは2段階で構成されています。第一の戦略ではmixrateが使用されます。第二の戦略では、試行ベクトルごとにランダムに選ばれた1つの座標のみが変更されます。あなたと友人たち（すなわち我々の集団）が、街で最も良いピッツェリアを探していると想像してください。 

初期状況

• あなたには10人の友人がいます（集団サイズ）。
• 全員が街のランダムなエリアから探索を開始します。
• 全員が過去の移動履歴を持つスマートフォン（履歴記憶）を持っています。

1日目：全員が街へ出発する。最初の友人は7/10の評価のピッツェリアを見つけ、2人目は5/10のピッツェリア、3人目は8/10のピッツェリアを発見する…というように続く。

2日目：蓄積された経験を活用する。

ステップ1：「履歴記憶」(Selection-I)。アルゴリズム：コインを投げる。表が出たら「昨日どこにいたかを思い出す」（履歴を更新）、裏が出たら「古い記憶を使う」（更新しない）、その後「記憶をシャッフルする」（トランプのように）。

ステップ2：軌跡をたどる（突然変異）。各友人はこう考える：「今どこにいるか？（現在位置）そして以前どこにいたか？（履歴位置）」。その移動式は「新しい場所 = 現在地 + ランダムなステップ × (以前の場所 - 現在地)」となります。たとえば、1人目の友人は現在A通り10にいて、「過去のゴースト」はB通り20にいたとします。ランダムステップが2の場合、「新しい位置 = A10 + 2 × (B20 − A10)」となり、B通り方向へ移動するが、その距離の2倍進むことになります。

「経路の修正」（交叉）。アルゴリズムはコインを投げて戦略を選択します。戦略A：部分変化。ある友人は特定の住所へ行く予定だったが、アルゴリズムは「通りだけ変更し、番地はそのままにする」と指示します。その結果、通りのみ変更され、番地は維持されます。戦略B：最小変更。ある友人は特定の住所へ行く予定だったが、アルゴリズムは「元の場所は維持し、番地だけ変更する」と指示します。その結果、番地のみ変更されます。

「全体結果の確認」(Selection-II)。友人1が新しい場所に到着する。

• 新しいピッツェリアの評価がより良い場合（9/10）：「素晴らしい、このままここにいる！」
• 悪い場合（4/10）：「いや、元に戻る！」

下の図はアルゴリズムの動作を示しています。

図1：BSAアルゴリズムのフェーズ

この図は、BSAアルゴリズムが2次元空間で最適解を探索する様子を示しています。上から地形図を見るように想像してください。目標は最も高い地点（赤い中心）を見つけることです。

図は3つのパネルに分かれ、探索の進化を示しています。反復処理1 – ランダム初期化。ランダム初期化 等高線を持つ正方形の探索空間の中央に赤い点（大域最適解）があり、4つの青い点（P1, P2, P3, P4）は「探索者」の初期ランダム位置を表します。この段階では、アルゴリズムは探索空間にランダムにエージェントを配置します。この時点ではoldP = Pであり、履歴は現在の集団をコピーしています。

反復処理2 - 突然変異ステップ：青い点は現在のエージェント位置、緑の半透明の点は履歴記憶の位置を表します。赤い矢印は変異による移動方向です。

主要要素：赤い矢印は変異式「M = P + F × (oldP - P)」を示しています。各エージェントは対応する履歴個体との相対関係に基づいて移動します。矢印の方向はFの値によって変化します（正負により変化）。赤い枠の式「F = 3 × randn(); M = P + F × (oldP - P)」は、BSAの中心的な変異式です。

反復処理3 - 交叉と選択後：紫の点は交叉後の新しい位置（試行集団）、薄い青の点は比較用の旧位置、緑の矢印は改善された移動のみを示します。交叉により変異個体と現在個体の情報が統合され、貪欲選択により、解を改善した移動のみが採用されます。集団は最適解（赤い中心）へと近づいています。

BSAプロセス概要：アルゴリズムの全サイクルを色付きの円のシーケンスで表したもの。

1. 初期化（青）：ランダムスタート
2. Select-I（緑）：50%の確率で記憶を更新
3. 突然変異（赤）：突然変異公式の適用
4. クロスオーバー（紫色）：複数解の組み合わせ
5. 評価（オレンジ色）：適応度計算
6. Select-II（ターコイズ）：最良解の貪欲選択

点線の矢印は、そのプロセスが収束するまで繰り返されることを示しています。この図は、BSAがなぜ効果的であるかを明確に示しています。BSAは、これまでにどこを探索したかを「記憶」し、その情報を利用することで、単純なランダムウォークよりも賢く探索を行います。

それでは、BSAの擬似コードに移りましょう。

実行準備

初期パラメータ

• 集団サイズを設定する 
• 交叉のミックスレートパラメータを設定する 
• 以下の用途向けに空のコンテナを作成する
  • 現在の集団
  • 履歴集団
  • 変異体集団
  • 試行集団
  • 各個体に対応する交叉用バイナリマップ

初期化

• 履歴集団のすべての個体を、探索空間内にランダムに配置する
• ステップが与えられている場合は、離散化を考慮する
• 「選択必須」フラグをfalseに設定する

アルゴリズムのメインループ

ステップ1：初回実行

これが最初の反復である場合：

• 現在の集団をランダムに配置する
• 座標に離散化を適用する
• 初期化が完了したことを記録する
• 終了し、適応度の計算を待つ

ステップ2：貪欲選択（必要な場合）

「選択必須」フラグが設定されている場合：

• 各個体について以下を比較する
  • 新しい解が保存されている解より悪い場合 → 旧座標と旧fitnessに戻す
  • 新しい解が良い場合 → そのまま新しい解を採用する
• 選択フラグをリセットする

ステップ3：現在状態の保存

各個体について：

• 現在の適応度を保存する
• 現在の座標のコピーを保存する

ステップ4：履歴記憶の更新(Selection-I)

• コインを投げる（確率50％）
• 表が出た場合：
  • 現在の集団全体を履歴記憶にコピーする
  • 適応度を維持する
• 履歴集団をトランプのデッキのようにシャッフルする：
  • 最後の個体から最初の個体へ向かって処理
  • 各個体についてランダムな交換位置を選ぶ
  • 交換する

ステップ5：突然変異

• 正規分布から移動係数Fを生成する
  • （平均0、範囲はおよそ -3 から +3）
  • サイコロを振るようなものだが、分布はベル型になる。
• 各個体および各座標について：
  • 新しいポジション = 現在 + F × (過去 - 現在)
  • Fが正の場合→履歴位置に近づく
  • Fが負の場合→履歴位置から離れる

ステップ6：交叉

• 突然変異集団をそのまま試行集団にコピーする
• 重み付きコインを投げる(40% / 60%)

40%が選ばれた場合（戦略1） 

各個体について：

• 変更する座標数を0〜全体からランダムに決定（mixrateを使用）
• 座標をランダムに選択する
• 選ばれた座標のみ現在集団から値を取得する
• それ以外は突然変異個体の値を維持する

60%が選ばれた場合（戦略2）

各個体について：

• ランダムな座標を1つだけ選択する
• 現在の集団から値を取り出して置き換える
• それ以外の座標はすべて突然変異個体の値のままとする

ステップ7：境界制御

試行集団の各個体について：

• 各座標を確認する
• もし境界を超えた場合：
  • コインを投げる(50/50)
  • 表 → 境界内でランダム値を生成する
  • 裏 → 最も近い境界値に配置する
• その後、必要であれば離散化を適用する

ステップ8：評価準備

• 試行集団をメイン集団にコピーし、評価用とする
• 「選択必須」フラグをtrueに設定する
• 適応度計算に制御を渡す

適応度を計算した後 

• 最良個体を見つける
• 大域記録より良い場合：
  • 大域記録を更新する
  • 最適解の座標を保存する

繰り返し

ステップ2に戻り、以下の条件のいずれかが満たされるまで繰り返す

• 収束に達した
• または反復回数の上限を超えた

主要なポイントを理解したところで、アルゴリズムのコードを書き始めましょう。C_AO_BSA_Backtracking クラスは、最適化問題を解くための BSA（Backtracking Search Algorithm：バックトラッキング探索アルゴリズム）を実装したクラスです。このクラスは、最適化アルゴリズム共通のインターフェースを定義する C_AO 基底クラスを継承します。 

主な特徴と目的

最適化パラメータ

• popSize：集団サイズです。同時に扱う「エージェント」または「解」の数を表します。 
• mixrate：交叉（クロスオーバー）率を制御するパラメータで、新しい解を生成する際にエージェント間で情報をどの程度「混合」するかを決定します。 

初期化

• クラスのコンストラクタでは、基本パラメータを初期化するとともに、popSizeとmixrateをparams配列に追加します。この配列はアルゴリズムの各種パラメータを管理するために使用されます。
• SetParamsメソッドでは、params配列から取得した値を基にアルゴリズム内部のパラメータを更新します。また、値が妥当であるかどうかの基本的なチェックもおこないます。

アルゴリズムのライフサイクル（メソッド）

• Init：初期設定をおこないます。変数の範囲（最小値・最大値・ステップ幅）や最適化エポック数を設定します。
• Moving：メインの反復処理を担当します。現在の集団を基に新しい候補解を生成し、解を更新します。
• Revision：生成された候補解を評価し、その品質に基づいて集団を更新します。

アルゴリズム内部で使用するデータ構造

• oldP：エージェント集団の過去（履歴）の状態を保持する配列です。
• M：突然変異によって生成された集団を保持する配列です。
• T：現在の集団との比較に用いる試行（Trial）集団を保持する配列です。
• F：突然変異の振幅係数であり、突然変異による変化量の大きさに影響します。
• needSelection：第2段階の選択処理を実行する必要があるかどうかを示すフラグです。
• prevFitness：前回反復時の各エージェントの適応度を保存する配列です。
• S_Map：交叉処理で使用する補助構造体で、どの変数を異なる親から受け継ぐかを決定するためのバイナリマップを保持します。
• map：各エージェントに対応するバイナリマップの配列です。

アルゴリズムの主な手順（内部メソッド）

• SelectionI：第1段階の選択処理を行い、新しい解を生成するためのエージェントを選択します。
• Mutation：選択されたエージェントに対して突然変異を適用します。
• Crossover：エージェント間で交叉（情報の組み合わせ）をおこない、新しい試行解を生成します。
• BoundaryControl：エージェントの各変数が指定された範囲（最小値～最大値）を超えないように補正します。
• ShufflePopulation：集団内のエージェントをランダムに並べ替えるメソッドです。

このように、C_AO_BSA_Backtrackingクラスは、集団・突然変異・交叉といった進化的最適化の基本概念に加え、BSA特有のバックトラッキング機構を利用して最適化問題を解くアルゴリズムを実装しています。

//————————————————————————————————————————————————————————————————————
class C_AO_BSA_Backtracking : public C_AO
{
  public: //----------------------------------------------------------
  ~C_AO_BSA_Backtracking () { }
  C_AO_BSA_Backtracking ()
  {
    ao_name = "BSA";
    ao_desc = "Backtracking Search Algorithm";
    ao_link = "https://www.mql5.com/ja/articles/18568";

    popSize = 10;     // population size
    mixrate = 1.0;    // crossover parameter

    ArrayResize (params, 2);

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

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

    // Check the parameters validity
    //if (popSize < 2) popSize = 2;
    if (mixrate < 0.0) mixrate = 0.0;
    if (mixrate > 1.0) mixrate = 1.0;
  }

  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 mixrate;        // crossover parameter

  private: //---------------------------------------------------------
  S_AO_Agent oldP [];    // historical population
  S_AO_Agent M    [];    // mutant population (Mutant)
  S_AO_Agent T    [];    // trial population (Trial)

  double F;              // amplitude factor for mutation
  bool   needSelection;  // flag for the necessity of executing Selection-II
  double prevFitness []; // array for storing previous fitness

  // Auxiliary structures for crossover
  struct S_Map
  {
      int val [];      // binary map for crossover

      void Init (int size)
      {
        ArrayResize (val, size);
        ArrayInitialize (val, 0);
      }
  };

  S_Map map [];        // array of binary maps for each agent

  // Algorithm methods
  void SelectionI        ();
  void Mutation          ();
  void Crossover         ();
  void BoundaryControl   (S_AO_Agent &agent);
  void ShufflePopulation (S_AO_Agent &pop []);
};
//————————————————————————————————————————————————————————————————————

Initメソッドは、最適化を開始する前にアルゴリズムを動作可能な状態に準備する役割を担います。まず、基本的な初期化関数が呼び出され、変数値の範囲（最小値、最大値、および変化ステップ）に関する基本パラメータが設定されます。この基本ステップが失敗した場合、メソッドは処理を中断し、失敗を返します。

次に、BSAアルゴリズム固有の内部データ構造が確保され、準備されます。具体的には、履歴集団oldP、突然変異集団M、試行集団T、交叉用のバイナリマップ配列map、および各エージェントの前回の適応度値を保存するためのprevFitness配列が作成され、必要なサイズに初期化されます。また、追加選択が必要かどうかを示すフラグは、初期状態でfalseに設定されます。

その後、集団内の各エージェントに対して初期化メソッドが呼び出され、問題のパラメータ数に応じて各エージェントの内部構造が準備されます。

続いて、履歴集団に初期値が設定されます。各エージェントおよびその各パラメータについて、指定された範囲内で乱数による値が生成され、その後、設定された変化ステップに合わせて値が調整されます。これらすべての処理が正常に完了すると、メソッドはアルゴリズムオブジェクトの初期化が成功し、最適化を実行する準備が整ったことを示す値を返します。

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

  //------------------------------------------------------------------
  // Initialize additional BSA structures
  ArrayResize (oldP, popSize);
  ArrayResize (M,    popSize);
  ArrayResize (T,    popSize);
  ArrayResize (map,  popSize);
  ArrayResize (prevFitness, popSize);

  needSelection = false;

  for (int i = 0; i < popSize; i++)
  {
    oldP [i].Init (coords);
    M    [i].Init (coords);
    T    [i].Init (coords);
    map  [i].Init (coords);
  }

  // Initialize oldP historical population
  for (int p = 0; p < popSize; p++)
  {
    for (int c = 0; c < coords; c++)
    {
      oldP [p].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]);
      oldP [p].c [c] = u.SeInDiSp (oldP [p].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }

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

Movingメソッドは、BSA最適化アルゴリズムの主要な処理を記述するものであり、集団内に新しい解候補を生成する役割を担います。メソッドが初めて呼び出され、「revision」フラグがfalseの場合、まずアクティブ集団aが初期化されます。集団内の各エージェントとその各パラメータについて、指定された範囲（最小値および最大値）内で乱数による値が生成されます。その後、この値は指定されたパラメータの変化ステップに合わせて調整されます。初期化が完了すると、revisionフラグはtrueに設定され（以降の呼び出しではこの初期化処理は実行されません）、needSelectionフラグはfalseにリセットされます。この時点でメソッドは終了します。

貪欲選択の実装(Selection-II)（必要に応じて実行）：needSelectionがtrueの場合、前回のステップで新しい集団が生成されており、その適応度を以前の解と比較する必要があることを意味します。集団内の各エージェントについて処理がおこなわれます。現在のエージェントa[i].f（trial解の適応度として計算された値）を、prevFitness[i]に保存されている前回の適応度と比較します。trial解であるa[i]の適応度が前回よりも悪い場合は、現在のエージェントa[i].cの座標をa[i].cP（前回ステップの座標）から復元し、適応度a[i].fもprevFitness[i]の値に戻します。これにより、集団の性能が悪化することを防ぎます。選択処理が終了すると、needSelectionフラグはfalseにリセットされます。

BSAアルゴリズムの基本手順（初期化またはSelection-IIの後）：新しい解を生成する前に、アクティブ集団aに属するすべてのエージェントの現在の適応度を、後続のSelection-IIで利用するためにprevFitnessへ保存します。また、各エージェントの現在の座標a[i].cをa[i].cPへコピーし、新しい解が劣っていた場合に元の状態へ戻せるようにします。

続いて、内部メソッドSelectionIが呼び出されます。このメソッドでは、突然変異に使用するアーカイブ集団oldPの選択または準備がおこなわれます。その後、内部メソッドMutationが呼び出されます。ここでは、アクティブ集団やアーカイブ集団を基に、突然変異集団Mが生成されます。さらに、内部メソッドCrossoverが呼び出されます。このメソッドでは、突然変異集団Mと現在のアクティブ集団aが交叉され、その結果として試行集団Tが生成されます。

生成された試行集団Tの各エージェントの座標は、アクティブ集団aへコピーされます。これにより、aには新たな試行解が格納され、その適応度を次に評価することになります。最後に、needSelectionフラグがtrueに設定されます。これは、新しい解の適応度が計算された次回のMovingメソッド呼び出し時に、貪欲選択(Selection-II)を実行する必要があることを示しています。

このように、Movingメソッドは、初期化、選択、突然変異、交叉、および結果比較の準備までを含む、BSAアルゴリズムの1回の完全な反復（エポック）を実装しています。

//————————————————————————————————————————————————————————————————————
//--- The main step of the algorithm
void C_AO_BSA_Backtracking::Moving ()
{
  // Initial population setup
  if (!revision)
  {
    for (int p = 0; p < popSize; p++)
    {
      for (int c = 0; c < coords; c++)
      {
        a [p].c  [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]);
        a [p].c  [c] = u.SeInDiSp (a [p].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }

    revision      = true;
    needSelection = false;
    return;
  }

  // If you want to perform greedy selection after calculating fitness
  if (needSelection)
  {
    // Selection-II: Greedy selection
    for (int i = 0; i < popSize; i++)
    {
      // If the current solution (from T) is worse than the previous one, return the previous one
      if (a [i].f < prevFitness [i])
      {
        ArrayCopy (a [i].c, a [i].cP, 0, 0, WHOLE_ARRAY);
        a [i].f = prevFitness [i];
      }
    }

    needSelection = false;
  }

  //--- BSA basic steps:

  // Save current fitness before generating a new population 
  for (int i = 0; i < popSize; i++)
  {
    prevFitness [i] = a [i].f;
    ArrayCopy (a [i].cP, a [i].c, 0, 0, WHOLE_ARRAY);
  }

  // 1. Selection-I
  SelectionI ();

  // 2. Mutation
  Mutation ();

  // 3. Crossover
  Crossover ();

  // 4. Copy the trial population T into the 'a' main population to calculate fitness
  for (int i = 0; i < popSize; i++)
  {
    ArrayCopy (a [i].c, T [i].c, 0, 0, WHOLE_ARRAY);
  }

  // Set the flag to execute Selection-II after calculating fitness
  needSelection = true;
}
//————————————————————————————————————————————————————————————————————

SelectionIメソッドは、BSAアルゴリズムにおける第1段階の選択処理を実装するものであり、その後の突然変異処理で使用される履歴集団を選択する役割を担います。

履歴集団の確率的な更新50％の確率（すなわち等確率）で、履歴集団oldPが現在の集団aによって更新されます。生成された乱数が所定の閾値（0.5）より小さい場合、現在の集団aに属する各エージェントの内容（座標c）が対応するoldP内のエージェントへコピーされます。同時に、各エージェントの適応度fもコピーされます。

履歴集団のシャッフル： 前段階で履歴集団が更新されたかどうかに関係なく、ShufflePopulation(oldP)メソッドが呼び出され、履歴集団内のエージェントがランダムに並べ替えられます。この処理は、突然変異にランダム性を導入するためにおこなわれます。シャッフルによって、履歴集団内のエージェントは元の配置順ではなく、ランダムな順序で選択されるようになります。

このように、SelectionIメソッドは、現在の候補解によってアーカイブ集団を更新するか、あるいは以前の状態を維持した上で、いずれの場合もアーカイブ集団内のエージェントをシャッフルします。これにより、後続の突然変異処理において探索の多様性が確保されます。

//————————————————————————————————————————————————————————————————————
//--- Selection-I: select a historical population
void C_AO_BSA_Backtracking::SelectionI ()
{
  // Update the historical population with a 50% probability 
  if (u.RNDprobab () < 0.5) // equivalent to if (a < b) where a,b ~ U(0,1)
  {
    // Copy the current population to the historical one
    for (int i = 0; i < popSize; i++)
    {
      ArrayCopy (oldP [i].c, a [i].c, 0, 0, WHOLE_ARRAY);
      oldP [i].f = a [i].f;
    }
  }

  // Shuffle the historical population
  ShufflePopulation (oldP);
}
//————————————————————————————————————————————————————————————————————

ShufflePopulationメソッドは、与えられたエージェント集団（S_AO_Agent構造体で表現される）内の要素をランダムにシャッフルするよう設計されています。このメソッドは入力としてpop[]配列を受け取り、インプレースでシャッフルを行います。つまり、渡された配列内の要素順序を直接変更します。

シャッフルアルゴリズム：このメソッドはFisher-Yatesシャッフルアルゴリズムを使用しており、集団内の要素をランダムに混合します。このアルゴリズムは、すべての要素の並び順（順列）が等しい確率で発生することを保証します。

forループは配列の最後の要素（popSize - 1）から開始し、逆順にインデックス1の要素まで処理を行います。インデックス0の要素は、アルゴリズムの過程で既に移動されているためシャッフルする必要はありません。各インデックスiの要素について、0からiまでの範囲でランダムなインデックスjが選択されます。これはu.RNDminusOne(i+1)関数によって行われ、この関数は指定範囲内の整数を返します（0以上i+1未満）。

インデックスiとjの要素は交換されます。その際、S_AO_Agent型の一時変数tempが使用されます。S_AO_Agentは座標配列cを含むため、その配列もコピーされます。また適応度fもコピーされます。まずpop[i]の座標と適応度が一時変数tempに保存され、pop[j]の座標と適応度がpop[i]にコピーされます。その後、tempに保存されていた元のpop[i]の値がpop[j]にコピーされます。この処理の結果、ループ終了後にはpop[]配列内の要素順序はランダムになります。

//————————————————————————————————————————————————————————————————————
//--- Shuffle population
void C_AO_BSA_Backtracking::ShufflePopulation (S_AO_Agent &pop [])
{
  for (int i = popSize - 1; i > 0; i--)
  {
    int j = u.RNDminusOne (i + 1);

    // Swap i and j elements
    S_AO_Agent temp;
    temp.Init (coords);

    ArrayCopy (temp.c, pop [i].c, 0, 0, WHOLE_ARRAY);
    temp.f = pop [i].f;

    ArrayCopy (pop [i].c, pop [j].c, 0, 0, WHOLE_ARRAY);
    pop [i].f = pop [j].f;

    ArrayCopy (pop [j].c, temp.c, 0, 0, WHOLE_ARRAY);
    pop [j].f = temp.f;
  }
}
//————————————————————————————————————————————————————————————————————

Mutationメソッドは、BSAアルゴリズムにおける重要なステップである突然変異集団を生成する役割を担います。この処理は、現在の集団と履歴集団との差分に基づいておこなわれます。

まず、ランダムな振幅係数Fが生成されます。このFは、履歴集団が現在の集団に与える影響の大きさを決定します。次に、集団内の各エージェントおよび各エージェント内の各座標について、突然変異集団における新しい座標値が計算されます。この計算は、現在の座標に対して、F振幅係数と「履歴集団の対応する座標と現在の座標との差」の積を加算することでおおなわれます。これにより、履歴集団によって定義される方向へ現在の集団をシフトさせ、そのシフト量はF係数によって決まる突然変異集団が生成されます。

//————————————————————————————————————————————————————————————————————
//--- Mutation: generation of a mutant population
void C_AO_BSA_Backtracking::Mutation ()
{
  // Generate the amplitude factor
  F = u.GaussDistribution (0.0, -3.0, 3.0, 2);

  // Apply mutation: M = P + F * (oldP - P)
  for (int i = 0; i < popSize; i++)
  {
    for (int j = 0; j < coords; j++)
    {
      M [i].c [j] = a [i].c [j] + F * (oldP [i].c [j] - a [i].c [j]);
    }
  }
}
//————————————————————————————————————————————————————————————————————

Crossoverメソッドは、選択された交叉戦略を用いて現在の突然変異集団に基づき試行集団を形成する処理に関与します。このプロセスは、継承された解の特徴を組み合わせることで、より最適な解を見つけることを目的としています。

まず、試行集団は突然変異集団からコピーされ、後続の変更のための基盤が作られます。その後、交叉戦略の選択が行われます。40％の確率で第1の戦略が使用され、それ以外の場合は第2の戦略が使用されます。

第1の戦略が選択された場合、mixrate戦略が実行されます。この場合、各エージェントについて、mixrate係数を考慮しながら、現在のエージェントから取得する要素（座標）の数が決定されます。これらの要素は重複なしでランダムに選択されます。その後、選択されたインデックスに対応する座標が、現在の解から試行集団のエージェントへコピーされます。

第2の戦略が選択された場合、各エージェントごとに1つのランダムな要素（座標）が選ばれ、試行集団内の対応する位置が現在の解の値に置き換えられます。

交叉処理が完了した後、試行集団内の各エージェントに対して境界チェックが行われ、すべての解が有効であり、範囲制約を満たしていることが保証されます。

//————————————————————————————————————————————————————————————————————
//--- Crossover: trial population generation
void C_AO_BSA_Backtracking::Crossover ()
{
  // Initialize the trial population as a copy of the mutant one
  for (int i = 0; i < popSize; i++)
  {
    ArrayCopy (T [i].c, M [i].c, 0, 0, WHOLE_ARRAY);
  }

  // Select a crossover strategy
  if (u.RNDprobab () < 0.4)
  {
    //--- STRATEGY 1: Using mixrate
    for (int i = 0; i < popSize; i++)
    {
      // Reset the map
      ArrayInitialize (map [i].val, 0);

      // Define the number of elements for the crossover
      int numElements = (int)MathCeil (mixrate * u.RNDprobab () * coords);

      // Generate unique indices for the crossover
      for (int n = 0; n < numElements; n++)
      {
        int idx;
        do
        {
          idx = u.RNDminusOne (coords);
        }
        while (map [i].val [idx] == 1); // until we find an unused index

        map [i].val [idx] = 1;
      }

      // Apply crossover
      for (int j = 0; j < coords; j++)
      {
        if (map [i].val [j] == 1)
        {
          T [i].c [j] = a [i].c [j];
        }
      }
    }
  }
  else
  {
    //--- STRATEGY 2: Mutation of only one element
    for (int i = 0; i < popSize; i++)
    {
      // Select one random element
      int randomIndex = u.RNDminusOne (coords);
      T [i].c [randomIndex] = a [i].c [randomIndex];
    }
  }

  // Boundary control for all agents in the trial population
  for (int i = 0; i < popSize; i++)
  {
    BoundaryControl (T [i]);
  }
}
//————————————————————————————————————————————————————————————————————

BoundaryControlメソッドは、エージェントのパラメータ値が許容範囲内に収まるように確認および調整するとともに、決定結果を所望の離散形式に変換するために設計されています。

各エージェントの座標の各要素について、値が事前に定められた最小値または最大値の範囲を超えていないかチェックが行われます。もし値が範囲外に出ている場合、その出力は選択された戦略に従って処理されます。確率的に50％未満の条件が選ばれた場合、許容範囲内でランダムに値を再生成します。それ以外の場合は、その値を最も近い境界値、すなわち最小値または最大値に設定します。

その後、各座標値は離散化されます。すなわち、指定された範囲および離散化ステップに対応する最も近い許容値へと変換されます。これにより、解がデータ型および範囲の要件を満たすことが保証されます。

//————————————————————————————————————————————————————————————————————
//--- Boundary control
void C_AO_BSA_Backtracking::BoundaryControl (S_AO_Agent &agent)
{
  for (int j = 0; j < coords; j++)
  {
    if (agent.c [j] < rangeMin [j] || agent.c [j] > rangeMax [j])
    {
      // Select a boundary handling strategy
      if (u.RNDprobab () < 0.5)
      {
        // Random regeneration
        agent.c [j] = u.RNDfromCI (rangeMin [j], rangeMax [j]);
      }
      else
      {
        // Set to the boundary
        if (agent.c [j] < rangeMin [j]) agent.c [j] = rangeMin [j];
        else agent.c [j] = rangeMax [j];
      }
    }

    // Discretization
    agent.c [j] = u.SeInDiSp (agent.c [j], rangeMin [j], rangeMax [j], rangeStep [j]);
  }
}
//————————————————————————————————————————————————————————————————————

Revisionメソッドは、現在の集団内で見つかった最良の解を選択し更新する役割を担います。すべての解を走査し、評価関数（適応度）が最大となる解を探索します。そのような解が見つかった場合、それは現在の最良結果として保存され、その座標は現在の最良解を保持するための別の配列にコピーされます。このメソッドにより、アルゴリズムの反復処理の中で見つかった最適解を継続的に追跡し更新することが可能になります。

//————————————————————————————————————————————————————————————————————
//--- Selection-II and updating the best solution
void C_AO_BSA_Backtracking::Revision ()
{
  int bestIND = -1;

  for (int i = 0; i < popSize; i++)
  {
    // Update the global best solution
    if (a [i].f > fB)
    {
      fB = a [i].f;
      bestIND = i;
    }
  }

  // Copy the coordinates of the best solution
  if (bestIND != -1)
  {
    ArrayCopy (cB, a [bestIND].c, 0, 0, WHOLE_ARRAY);
  }
}
//————————————————————————————————————————————————————————————————————

GaussDistributionメソッドは、与えられた入力値の周囲を中心とするガウス分布（正規分布）に従う乱数を生成するものであり、Box-Muller法を用いて正規分布に従う乱数を生成します。

まず、一様分布に従う2つの乱数が生成されます。その後、これらの値を基に標準正規分布に従う乱数が計算され、ガウス分布を得るために利用されます。

次に、生成された値がsigmaパラメータで定義された許容偏差範囲内にあるかどうかが確認されます。もし生成された値がこの範囲を外れている場合、許容範囲内に収まる値が得られるまで再帰的に再生成が行われます。

最後に、生成された正規分布に従う変動値は、入力値Inを中心として指定された出力範囲（outMinからoutMax）に収まるようにスケーリングされます。これにより、分布は目的のパラメータに合わせて平行移動およびスケーリングされます。結果として、入力値Inを中心としつつも、最小値および最大値の制約を持つガウス分布に従う数値が得られます。

//——————————————————————————————————————————————————————————————————————————————
double C_AO_Utilities :: GaussDistribution (const double In, const double outMin, const double outMax, const double sigma)
{
  double logN = 0.0;
  double u1   = 2.0 * MathRand () / 32767.0 - 1.0;//RNDfromCI (0.0, 1.0);
  double u2   = 2.0 * MathRand () / 32767.0 - 1.0;//RNDfromCI (0.0, 1.0);

  logN = u1 <= 0.0 ? 0.000000000000001 : u1;

  double z0 = sqrt (-2 * log (logN)) * cos (2 * M_PI * u2);

  double sigmaN = sigma > 8.583864105157389 ? 8.583864105157389 : sigma;
  
  // If z0 is outside the range [-sigmaN, sigmaN], generate anew
  if (z0 >= sigmaN || z0 <= -sigmaN) 
  {
    return GaussDistribution(In, outMin, outMax, sigma); // Recursive call
  }

  if (z0 >= 0.0) z0 =  Scale (z0,        0.0, sigmaN, 0.0, outMax - In, false);
  else           z0 = -Scale (fabs (z0), 0.0, sigmaN, 0.0, In - outMin, false);
  
  return In + z0;
}
//——————————————————————————————————————————————————————————————————————————————

テスト結果

BSAアルゴリズムは非常に良好な結果を示しました。

BSA|Backtracking Search Algorithm|10.0|1.0|
=============================
5 Hilly's; Func runs:10000; result:0.9730917210619289
25 Hilly's; Func runs:10000; result:0.5453406317593932
500 Hilly's; Func runs:10000; result:0.2909827609772065
=============================
5 Forest's; Func runs:10000; result:0.9999986842258451
25 Forest's; Func runs:10000; result:0.5854340780208712
500 Forest's; Func runs:10000; result:0.21747482800959225
=============================
5 Megacity's; Func runs:10000; result:0.8476923076923077
25 Megacity's; Func runs:10000; result:0.3695384615384615
500 Megacity's; Func runs:10000; result:0.12978461538461658
=============================
All score:4.95934 (55.10%)

BSAアルゴリズムの可視化において、小規模および中規模次元の関数に対する結果では値のばらつきが確認できます。しかし、集団サイズのパラメータを増加させるとそのばらつきは減少する一方で、より良い収束を得るためには反復回数を増やす必要があります。

Hillyテスト関数におけるBSA

Forestテスト関数におけるBSA

Megacityテスト関数におけるBSA

BSAアルゴリズムは、集団ベースの最適化アルゴリズムのランキング表で20位にランクインしています。

#	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	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	BSA	バックトラッキング探索アルゴリズム	0.97309	0.54534	0.29098	1.80941	0.99999	0.58543	0.21747	1.80289	0.84769	0.36953	0.12978	1.34700	4.959	55.10
21	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
22	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
23	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
24	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
25	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
26	DEA	イルカのエコーロケーションアルゴリズム	0.75995	0.67572	0.34171	1.77738	0.89582	0.64223	0.23941	1.77746	0.61538	0.44031	0.15115	1.20684	4.762	52.91
27	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
28	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
29	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
30	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
31	(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
32	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
33	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
34	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
35	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
36	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
37	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
38	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
39	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
40	CMAES	共分散行列適応進化戦略	0.76258	0.72089	0.00000	1.48347	0.82056	0.79616	0.00000	1.61672	0.75846	0.49077	0.00000	1.24923	4.349	48.33
41	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
42	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
43	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
44	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
45	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
	RW	ランダムウォーク	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

まとめ

BSAは、実装の容易さと探索効率の間の妥協点を表しており、集団ベース最適化アルゴリズムのランキング表において安定した中間的な位置を占めています。その主な利点は「履歴記憶」という興味深い概念であり、これによってアルゴリズムは計算スキームを複雑化することなく早期収束を回避できます。多くの現代的メタヒューリスティクスが多数のパラメータや複雑な演算子によって過度に肥大化しているのとは異なり、BSAは最小限の設定のみを必要とするため、外部パラメータのチューニングに時間を費やしたくない実務者にとって魅力的な選択肢となっています。

唯一の重要なパラメータであるmixrateは直感的であり、アルゴリズム内部のメカニズムを深く理解する必要はありません。同時にBSAは、単純な単峰関数から複数の局所最適解を持つ複雑な多峰性ランドスケープまで、幅広い問題に対して安定した性能を示します。このアルゴリズムは収束速度や解の精度において最高性能を主張するものではありませんが、その信頼性と予測可能性により「ワークホース」として機能します。特に重要なのは、集団サイズが増加してもBSAは停滞に対して弱くなりにくい点であり、履歴集団のランダム更新機構によって探索の後期段階においても継続的に多様性が供給されます。

ランキングの中間に位置することは平凡さの証ではなく、むしろその汎用性と実用性の証拠です。なぜなら、現実世界の問題解決において必ずしも最も複雑で最新のツールが必要とされるわけではないからです。時には、明確な動作原理を持ち、専門的なチューニングを必要とせずに良好な結果をもたらす堅牢なアルゴリズムで十分であり、BSAはそのニッチをうまく満たしています。

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

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

BSAの長所と短所

長所

1. テストした関数全体で良好な収束が得られた
2. 集団サイズ以外の外部パラメータは1つだけである

短所

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_BSA.mq5	スクリプト	BSAテストスタンド