フラクタルベースアルゴリズム(FBA)

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

Andrey Dik

内容

はじめに

メタヒューリスティックアルゴリズムは、妥当な時間内に実用的な解を発見できることから、複雑な最適化問題を解くための強力な手法として広く利用されています。過去数十年の間に、遺伝的アルゴリズム、粒子群最適化、差分進化、蟻コロニー最適化など、自然現象や社会的プロセスに着想を得た数多くのメタヒューリスティック手法が提案されてきました。これらについては、これまでの記事でも取り上げてきました。

本記事では、2017年にMarjan Kaediによって提案された、連続最適化問題向けの新しいメタヒューリスティック手法「Fractal-based Algorithm（FBA）」を紹介します。このアプローチはフラクタルの幾何学的性質に基づいており、自己相似性の概念を利用して探索空間を適応的に探索します。アルゴリズムの中核となるのは、探索空間内に存在する高品質な解の密度に基づき、各領域の有望性を評価する独自のヒューリスティックです。

提案手法の重要な特徴は、探索空間を反復的に部分空間へ分割し、その中から有望な領域を選別して重点的に探索する点にあります。アルゴリズムの進行に伴い、最適解へ向かう自己相似なフラクタル構造が形成され、探索空間全体の大域探索と、発見済み解の局所改善とのバランスを実現します。本記事では、アルゴリズムの理論的背景、実装上の詳細、主要パラメータの設定方法について詳しく解説するとともに、標準ベンチマーク関数を用いた他の代表的最適化手法との比較結果も紹介します。

アルゴリズムの実装

広大な野原で宝探しをしているところを想像してください。あなたならどのように探すでしょうか。おそらく、地面を1センチメートル残らず掘り返すことはしないでしょう。その方法では時間がかかりすぎるからです。フラクタルベースアルゴリズム(FBA)が解決するのは、まさにこの問題です。つまり、すべての点を調べることなく、広大な可能性空間の中から「宝」（最適解）を見つけ出すことです。

まず、探索領域全体をチェス盤のように等しい正方形へ分割します。次に、「探索者」（ランダムな点）を空間全体へ配置し、領域についての初期情報を取得します。各探索者は、自分が見つけた領域の品質を報告します。アルゴリズムは、最良の点（上位60%の点）を選択し、それらが集中している正方形を調べます。これらの正方形は「有望領域」（上位30%の正方形）としてマークされます。

次に、アルゴリズムは有望な領域へ探索を集中します。各有望領域はさらに小さな正方形へ分割され、フラクタル構造が形成されます。新しい探索者の大部分はこれらの有望領域へ向かいます。一方で、未探索領域に存在する宝を見逃さないようにするため、アルゴリズムは一部の探索者(5%)に対してランダム性を持たせた探索をおこなわせます。これらの探索者は現在位置からランダムな方向へ移動し、予想外の場所を探索します。

このプロセスは何度も繰り返されます。ステップを重ねるごとに、アルゴリズムは宝の存在する可能性が高い場所をより正確に特定し、より多くの探索者をそこへ送り込みます。やがて、異なるサイズの正方形からなる階層構造が形成され、フラクタルを思わせる構造となります。これがアルゴリズム名の由来です。

fba-space-partitioning

図1：FBAアルゴリズム動作の可視化

上図に示したFBAの基本的な考え方は、探索空間をフラクタル的に徐々に細かい領域へ分割しながら、計算資源を最も有望な領域へ集中させることです。これにより、解空間を探索する自己相似構造が形成されます。それでは、FBAアルゴリズムの疑似コードの作成へ進みましょう。

初期化

探索空間全体を等しい部分空間へ分割する
空間全体に一様に初期集団を生成する
各点の適応度を評価する

反復

有望点の特定：最良の適応度を持つ上位P1%の点を選択する
部分空間ランクの計算：各部分空間に含まれる有望点数を数える
有望部分空間の選択：最も高い有望ランクを持つ上位P2%の部分空間を選択する
有望部分空間の細分化：有望領域をさらに小さな部分空間へ分割する
新しい集団の生成：有望領域でより高密度となるように新しい点を生成する
突然変異の適用：P3%の点へガウスノイズを追加する（探索メカニズム）
集団の統合：現在の集団と新しい集団を統合し、最良の点を保持する

停止基準

停止条件（最大反復回数、適応度閾値など）に到達するまで継続する
発見された最良解を返す

アルゴリズムの概念を理解したところで、コードの実装へ進みます。C_AO_FBAクラスは、フラクタル原理に基づく最適化アルゴリズムの特殊化実装であり、汎用C_AOクラスから派生しています。

このクラスは、アルゴリズムの設定および中核処理を担当するpublicメソッドとパラメータを持っています。コンストラクタでは、集団サイズ、有望点および有望部分空間の割合、ランダム変動を適用する点の割合、各次元を分割する区間数などの初期パラメータを指定します。SetParamsメソッドは、外部ソースから実行中にパラメータを更新するために使用されます。Initメソッド、およびそれに続くMoving関数とRevision関数は、アルゴリズムの段階および反復を制御します。

また、このクラスでは、探索部分空間を記述するための内部構造表現S_Subspaceも宣言されています。各部分空間は、各次元における最小境界および最大境界、有望度、階層レベル、親部分空間との接続情報によって特徴付けられます。

クラス内の主要メソッドには、以下の機能が含まれます。

点が指定された部分空間内に存在するかを判定する
空間の初期分割およびその後の細分化を行う
有望点を特定し、そのランクを計算して、さらなる分割対象となる最良部分空間を選択する
組み合わせ、突然変異、効率または適応度基準によるソートを通じて、新しい集団を生成する

このように、C_AO_FBAクラスは、動的な空間分割、有望領域の評価、および探索効率を向上させるヒューリスティック演算子を用いて、複雑な多次元問題における適応型かつ階層型のフラクタルベースアルゴリズムを実装しています。

//——————————————————————————————————————————————————————————————————————————————
class C_AO_FBA : public C_AO
{
  public: //--------------------------------------------------------------------
  ~C_AO_FBA () { }
  C_AO_FBA ()
  {
    ao_name = "FBA";
    ao_desc = "Fractal-Based Algorithm";
    ao_link = "https://www.mql5.com/ja/articles/17458";

    popSize = 50;  // population size
    P1      = 60;  // percentage of promising points
    P2      = 30;  // percentage of promising subspaces
    P3      = 0.8; // percentage of points for random modification
    m_value = 10;  // number of intervals to split each dimension into

    ArrayResize (params, 5);

    params [0].name = "popSize"; params [0].val = popSize;
    params [1].name = "P1";      params [1].val = P1;
    params [2].name = "P2";      params [2].val = P2;
    params [3].name = "P3";      params [3].val = P3;
    params [4].name = "m_value"; params [4].val = m_value;
  }

  void SetParams ()
  {
    popSize = (int)params [0].val;
    P1      = (int)params [1].val;
    P2      = (int)params [2].val;
    P3      =      params [3].val;
    m_value = (int)params [4].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 ();

  //----------------------------------------------------------------------------
  int    P1;           // percentage of promising points
  int    P2;           // percentage of promising subspaces
  double P3;           // share of points for random modification
  int    m_value;      // number of intervals to split each dimension into

  private: //-------------------------------------------------------------------

  // Structure for representing a subspace
  struct S_Subspace
  {
      double min [];        // minimal boundaries of the subspace
      double max [];        // maximum boundaries of the subspace
      double promisingRank; // potential rank (normalized value)
      bool   isPromising;   // flag of potential
      int    parentIndex;   // index of the parent subspace (-1 for root ones) 
      int    level;         // level in hierarchy (0 for original space)

      void Init (int coords)
      {
        ArrayResize (min, coords);
        ArrayResize (max, coords);
        promisingRank = 0.0;
        isPromising   = false;
        parentIndex   = -1;
        level         = 0;
      }
  };

  S_Subspace subspaces     []; // array of subspaces

  // Auxiliary methods
  bool   IsPointInSubspace              (const double &point [], const S_Subspace &subspace);
  void   CreateInitialSpacePartitioning ();
  void   DivideSubspace                 (int subspaceIndex);
  void   IdentifyPromisingPoints        (int &promisingIndices []);
  void   CalculateSubspaceRanks         (const int &promisingIndices []);
  void   SelectPromisingSubspaces       ();
  void   DividePromisingSubspaces       ();
  void   GenerateNewPopulation          ();
  void   MutatePoints                   ();
  void   SortByFitness                  (double &values [], int &indices [], int size, bool ascending = false);
  void   QuickSort                      (double &values [], int &indices [], int low, int high, bool ascending);
  int    Partition                      (double &values [], int &indices [], int low, int high, bool ascending);
};
//——————————————————————————————————————————————————————————————————————————————

Init初期化メソッドは、アルゴリズムの動作に必要な初期条件を設定するためのものです。このメソッドは、各パラメータに対する変数の最小境界値・最大境界値・ステップサイズの配列、およびエポック数を受け取ります。メソッド内部では、まず基本初期化が呼び出され、その後、探索空間の初期分割が作成されます。つまり、指定された範囲とステップに基づいて、部分空間の初期構造が形成されます。すべての処理が正常に完了した場合、メソッドはtrueを返し、それ以外の場合はfalseを返します。

基本Movingメソッドは、連続した反復によって解探索ループを実行します。最初の反復では、探索空間全体にわたって初期点集団の初期化がおこなわれます。各変数値は、指定範囲内でランダムに選択され、指定ステップに合わせて調整されます。

その後、メイン処理ではいくつかのステップが実行されます。まず、適応度関数の値に基づいて、最も有望な点、すなわち最良点の一部が特定されます。次に、各部分空間に対するそれらの有望度に基づき、これらの点のランクが計算されます。これらのランクに基づいて、さらに細かい領域へ分割するための最も有望な部分空間が選択されます。その後、これらの有望領域が分割され、より精密な探索領域が生成されます。続いて、それらの有望度ランクを考慮して新しい点集団が形成され、これにより最も有望な領域へ探索を集中させることが可能になります。最後に、多様性を高め、局所解への停滞を回避するために、点へのランダム変異（突然変異）が実行されます。

//——————————————————————————————————————————————————————————————————————————————
bool C_AO_FBA::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;

  //----------------------------------------------------------------------------
  // Create an initial partition of the search space
  CreateInitialSpacePartitioning ();

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

//+----------------------------------------------------------------------------+
//| Basic optimization method                                                  |
//+----------------------------------------------------------------------------+
void C_AO_FBA::Moving ()
{
  // First iteration - initialization of the initial population
  if (!revision)
  {
    // Initialize the initial population uniformly throughout the space
    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]);
      }
    }

    revision = true;
    return;
  }

  // Main optimization

  // 1. Identifying promising points (P1% of points with the best function values)
  int promisingIndices [];
  IdentifyPromisingPoints (promisingIndices);

  // 2. Calculation of potential ranks for each subspace
  CalculateSubspaceRanks (promisingIndices);

  // 3. Selecting the P2% most promising subspaces
  SelectPromisingSubspaces ();

  // 4. Dividing promising subspaces into smaller ones
  DividePromisingSubspaces ();

  // 5. Generating new points taking into account potential ranks
  GenerateNewPopulation ();

  // 6. Random modification (mutation)
  MutatePoints ();
}
//——————————————————————————————————————————————————————————————————————————————

Revisionメソッドは、アルゴリズム実行中に発見された現在の最良解を更新する役割を担います。このメソッドは、現在の集団のすべての要素を走査し、各要素の目的関数値を現在の最良値と比較します。ある要素がより良い結果を持つ場合、最良結果を保持する変数が更新され、それに対応する変数配列（座標）がコピーされて、この最適解が記録されます。これにより、このメソッドは、その時点で発見されている最良結果の継続的な追跡および保存を保証します。

//+----------------------------------------------------------------------------+
//| Update the best solution                                                   |
//+----------------------------------------------------------------------------+
void C_AO_FBA::Revision ()
{
  // Search for the best solution
  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);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

このメソッドは、最適解探索を局所化するために使用される初期部分空間構造を生成します。このメソッドは、指定された分割次数および次元数に基づいて、部分空間の総数を決定します。次元数が非常に高い場合は、過剰なリソース消費を避けるため、事前設定された最大値によって制限されます。

その後、部分空間配列が初期化され、各部分空間に対して初期レベルおよび各座標の境界パラメータが割り当てられます。空間の次元数に応じて、適切な分割方法が選択されます。

一次元空間の場合、空間は均等な区間へ分割され、生成される各部分空間は範囲内の特定区間を占有します。
二次元空間の場合、空間は二つの軸に沿って分割され、矩形の格子状領域が形成されます。
高次元の場合には、反復的アプローチが使用されます。この方法では、カウンタシステムと同様の方法で各座標に対するインデックス組み合わせが生成され、生成された各領域について、対応する区間に基づいて境界が設定されます。

境界の計算は、各次元の範囲を均等に分割することで行われ、各部分空間に対して、現在のインデックスに対応した最小境界および最大境界が設定されます。反復は、必要なすべての部分空間が生成されるまで、または部分空間数の上限に達するまで継続されます。結果として、探索空間の初期分割を表す構造が形成され、さらなる分割および解探索の準備が整えられます。

//+----------------------------------------------------------------------------+
//| Create the initial partition of the search space                           |
//+----------------------------------------------------------------------------+
void C_AO_FBA::CreateInitialSpacePartitioning ()
{
  // Create an initial partition of space
  int totalSubspaces = (int)MathPow (m_value, coords);

  // For very large dimensions, limit the number of subspaces
  if (totalSubspaces > 10000) totalSubspaces = 10000;

  ArrayResize (subspaces, totalSubspaces);

  // Initialize all subspaces
  for (int i = 0; i < totalSubspaces; i++)
  {
    subspaces [i].Init (coords);
    subspaces [i].level = 0; // Initial level
  }

  // Divide the initial space into equal subspaces
  int index = 0;

  // Select the division method depending on the dimensionality of the space
  if (coords == 1)
  {
    // One-dimensional case
    double intervalSize = (rangeMax [0] - rangeMin [0]) / m_value;

    for (int i = 0; i < m_value && index < totalSubspaces; i++)
    {
      subspaces [index].min [0] = rangeMin [0] + i * intervalSize;
      subspaces [index].max [0] = rangeMin [0] + (i + 1) * intervalSize;
      index++;
    }
  }
  else
    if (coords == 2)
    {
      // Two-dimensional case
      double intervalSize0 = (rangeMax [0] - rangeMin [0]) / m_value;
      double intervalSize1 = (rangeMax [1] - rangeMin [1]) / m_value;

      for (int i = 0; i < m_value && index < totalSubspaces; i++)
      {
        for (int j = 0; j < m_value && index < totalSubspaces; j++)
        {
          subspaces [index].min [0] = rangeMin [0] + i * intervalSize0;
          subspaces [index].max [0] = rangeMin [0] + (i + 1) * intervalSize0;
          subspaces [index].min [1] = rangeMin [1] + j * intervalSize1;
          subspaces [index].max [1] = rangeMin [1] + (j + 1) * intervalSize1;
          index++;
        }
      }
    }
    else
    {
      // Multidimensional case - use an iterative approach
      int indices [];
      ArrayResize (indices, coords);
      for (int i = 0; i < coords; i++) indices [i] = 0;

      while (index < totalSubspaces)
      {
        // Calculate the boundaries of the current subspace
        for (int c = 0; c < coords; c++)
        {
          double intervalSize = (rangeMax [c] - rangeMin [c]) / m_value;
          subspaces [index].min [c] = rangeMin [c] + indices [c] * intervalSize;
          subspaces [index].max [c] = rangeMin [c] + (indices [c] + 1) * intervalSize;
        }

        // Move on to the next subspace
        int c = coords - 1;
        while (c >= 0)
        {
          indices [c]++;
          if (indices [c] < m_value) break;
          indices [c] = 0;
          c--;
        }

        // If the full loop completed, exit
        if (c < 0) break;

        index++;
      }
    }
}
//——————————————————————————————————————————————————————————————————————————————

次のメソッドは、与えられた点が特定の部分空間に属しているかどうかを判定するために設計されています。このメソッドは、点の各座標を順番に確認し、その値を対応する部分空間の境界と比較します。少なくとも1つの座標について、点が許可範囲外（最小値未満、または最大値以上）にある場合、メソッドはfalseを返します。これは、その点が指定された部分空間に含まれていないことを意味します。すべての座標が条件を満たしている場合、メソッドは点が指定された部分空間に属していることを確認し、trueを返します。

//+----------------------------------------------------------------------------+
//| Determine whether a point belongs to a subspace                            |
//+----------------------------------------------------------------------------+
bool C_AO_FBA::IsPointInSubspace (const double &point [], const S_Subspace &subspace)
{
  // Check if the point is in the specified subspace
  for (int c = 0; c < coords; c++)
  {
    if (point [c] < subspace.min [c] || point [c] >= subspace.max [c])
    {
      return false;
    }
  }

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

有望な点を特定するためのこのメソッドは、現在の集団から最も「有望」な解を選択するよう設計されています。まず、このメソッドは、各要素の適応度関数値およびそのインデックスを格納するための一時配列を作成します。次に、これらの配列に、集団内の対応する要素の値とインデックスを格納します。

その後、要素は適応度関数値の降順でソートされます。ソート完了後、P1%として指定された割合に基づき、最良解の一定割合が選択され、そこから有望な点を表すインデックスのリストが形成されます。選択される点の数は、少なくとも1つであることが保証され、集団全体のサイズを超えることはありません。結果として、この関数は有望な解のインデックス配列を返します。

//+----------------------------------------------------------------------------+
//| Identify promising points                                                  |
//+----------------------------------------------------------------------------+
void C_AO_FBA::IdentifyPromisingPoints (int &promisingIndices [])
{
  // Select P1% points with the best function values

  // Create arrays for sorting
  double values  [];
  int    indices [];

  ArrayResize (values,  popSize);
  ArrayResize (indices, popSize);

  // Fill in the arrays
  for (int i = 0; i < popSize; i++)
  {
    values  [i] = a [i].f;
    indices [i] = i;
  }

  // Sort in descending order (for the maximization problem)
  SortByFitness (values, indices, popSize);

  // Select P1% best points
  int numPromisingPoints = (int)MathRound (popSize * P1 / 100.0);
  numPromisingPoints = MathMax (1, MathMin (numPromisingPoints, popSize));

  ArrayResize (promisingIndices, numPromisingPoints);

  for (int i = 0; i < numPromisingPoints; i++)
  {
    promisingIndices [i] = indices [i];
  }
}
//——————————————————————————————————————————————————————————————————————————————

さらに、このメソッドは各部分空間の有望度に基づいて評価およびランク付けをおこなうために設計されています。まず、すべての部分空間に対して現在の評価値をリセットします。その後、各有望点の座標を各部分空間の境界と比較し、一致する場合に対応するカウンタを増加させることで、各部分空間に含まれる有望点の数を計算します。

ここで重要なのは、1つの点は必ず1つの部分空間のみに割り当てられるという点です。定量的指標を算出した後、各部分空間の順位は、有望な点の総数で割ることによって正規化されます。これにより、各部分空間の有望性の相対スコアが得られ、その値は0から1の範囲で変動し、各部分空間における有望な点の割合が、全体の有望な点の集合に対してどの程度を占めるかを表します。最終的に、この結果が各部分空間の評価値となります。

//+----------------------------------------------------------------------------+
//| Calculate potential ranks of subspaces                                     |
//+----------------------------------------------------------------------------+
void C_AO_FBA::CalculateSubspaceRanks (const int &promisingIndices [])
{
  // Reset the ranks of subspaces
  for (int i = 0; i < ArraySize (subspaces); i++)
  {
    subspaces [i].promisingRank = 0.0;
  }

  // Calculate promising points in each subspace
  for (int i = 0; i < ArraySize (promisingIndices); i++)
  {
    int pointIndex = promisingIndices [i];

    for (int j = 0; j < ArraySize (subspaces); j++)
    {
      if (IsPointInSubspace (a [pointIndex].c, subspaces [j]))
      {
        subspaces [j].promisingRank++;
        break; // A point can only be in one subspace
      }
    }
  }

  // Normalize the potential ranks according to the article
  // PromisingRank = Number of promising points in s / Total promising points
  int totalPromisingPoints = ArraySize (promisingIndices);
  if (totalPromisingPoints > 0)
  {
    for (int i = 0; i < ArraySize (subspaces); i++)
    {
      subspaces [i].promisingRank = subspaces [i].promisingRank / totalPromisingPoints;
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

SelectPromisingSubspacesメソッドは、そのランクに基づいてどの部分空間を有望とみなすかを決定します。まず、部分空間のランキングと対応するインデックスを保持するための一時的なranks配列およびindices配列が作成されます。評価値および部分空間のインデックスはこれらの一時配列にコピーされます。各部分空間について、isPromisingフラグは一度すべてfalseにリセットされます。これは、前回の反復結果を考慮せず、初期状態から再評価を行うために必要です。ranks配列は降順にソートされ、それに対応してindices配列も並び替えられ、インデックスと評価値の対応関係が維持されます。

これにより、ソート後のindicesには、評価値の高い順に並んだ部分空間のインデックスが格納されます。有望とみなされる部分空間の数は、P2パラメータ（最良部分空間の割合）に基づいて算出されます。この値は1以上、かつ全部分空間数以下の範囲に制限されます。次に、indices配列の先頭からnumPromisingSubspaces個の要素について反復処理をおこないます。各インデックスに対応する部分空間について、isPromisingフラグがtrueに設定されます。これはその部分空間が有望であることを意味します。

また、subspaces配列へのアクセス時のエラーを防ぐため、インデックスが許容範囲内であることもチェックされます。メソッド実行の結果として、最も高いランクを持つP2%の部分空間に対してisPromisingフラグがtrueに設定されます。

//+----------------------------------------------------------------------------+
//| Select promising subspaces                                                 |
//+----------------------------------------------------------------------------+
void C_AO_FBA::SelectPromisingSubspaces ()
{
  // Select P2% subspaces with the highest ranks as promising ones

  // Create arrays for sorting
  double ranks [];
  int indices [];

  int numSubspaces = ArraySize (subspaces);
  ArrayResize (ranks, numSubspaces);
  ArrayResize (indices, numSubspaces);

  // Fill in the arrays
  for (int i = 0; i < numSubspaces; i++)
  {
    ranks [i] = subspaces [i].promisingRank;
    indices [i] = i;
    // Reset the potential flag
    subspaces [i].isPromising = false;
  }

  // Sort by descending ranks
  SortByFitness (ranks, indices, numSubspaces);

  // Select P2% most promising subspaces
  int numPromisingSubspaces = (int)MathRound (numSubspaces * P2 / 100.0);
  numPromisingSubspaces = MathMax (1, MathMin (numPromisingSubspaces, numSubspaces));

  // Mark promising subspaces
  for (int i = 0; i < numPromisingSubspaces && i < ArraySize (indices); i++)
  {
    // Protection against exceeding the array size
    if (indices [i] >= 0 && indices [i] < ArraySize (subspaces))
    {
      subspaces [indices [i]].isPromising = true;
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

DividePromisingSubspacesメソッドは、有望な部分空間をより小さな領域へ分割するために設計されています。まず、isPromisingフラグを確認することで、有望とマークされているすべての部分空間を特定します。これらの部分空間のインデックスは、一時配列promisingIndicesに収集されます。その後、promisingIndices配列に含まれる各インデックスについて、その部分空間に対してDivideSubspace関数が呼び出され、当該部分空間のインデックスが渡されます。

このメソッドは見つかったすべての有望な部分空間を順次走査し、それぞれに対してDivideSubspace関数を用いた分割処理を適用します。

//+----------------------------------------------------------------------------+
//| Separate promising subspaces                                               |
//+----------------------------------------------------------------------------+
void C_AO_FBA::DividePromisingSubspaces ()
{
  // Collect indices of promising subspaces
  int promisingIndices [];
  int numPromising = 0;

  for (int i = 0; i < ArraySize (subspaces); i++)
  {
    if (subspaces [i].isPromising)
    {
      numPromising++;
      ArrayResize (promisingIndices, numPromising);
      promisingIndices [numPromising - 1] = i;
    }
  }

  // Divide each promising subspace
  for (int i = 0; i < numPromising; i++)
  {
    DivideSubspace (promisingIndices [i]);
  }
}
//——————————————————————————————————————————————————————————————————————————————

DivideSubspaceメソッドは、特定の部分空間をより小さな領域へ分割するために設計されています。まず、渡されたインデックスに基づいて親部分空間を選択します。次に、部分空間の総数が設定された上限(10,000)を超えないことを確認します。その後、各次元をm_value個に分割した結果として生成される新しい部分空間の総数を決定します。これは、m_valueを次元数と同じ指数で累乗した値になります。

すべての部分空間を格納する配列は、新しく生成される部分空間の数だけ拡張されます。各新規部分空間に対しては、レベル、親部分空間のインデックス、各座標の境界といった初期パラメータが設定されます。境界は親部分空間の境界と、等分割に基づいて計算されます。

各次元について区間サイズが決定され、現在のインデックスに基づいて該当する部分空間の境界が設定されます。新しい部分空間が生成されるたびに、次元ごとのインデックスがインクリメントされ、多次元インデックスシステムに従って次の分割へ移動します。ある次元のインデックスがm_valueに到達するとゼロにリセットされ、次の次元のインデックスがインクリメントされることで、すべての組み合わせが試行されます。

このプロセスは、すべての新規部分空間が生成されるか、あるいは上限に到達するまで継続されます。カウンタを用いてすべての組み合わせが網羅的に探索されると、自然に処理は終了します。このメソッドの結果として、親部分空間は多数のより小さな部分空間へと分割され、それぞれが元の範囲の対応する部分を各次元にわたってカバーする形となります。

//+----------------------------------------------------------------------------+
//| Partition a specific subspace                                              |
//+----------------------------------------------------------------------------+
void C_AO_FBA::DivideSubspace (int subspaceIndex)
{
  // Divide the specified subspace into m_value^coords subspaces

  S_Subspace parent = subspaces [subspaceIndex];

  // Limit the maximum number of subspaces
  if (ArraySize (subspaces) > 10000) return;

  // For each dimension, divide by m_value parts
  int totalNewSubspaces = (int)MathPow (m_value, coords);
  int currentSize = ArraySize (subspaces);
  ArrayResize (subspaces, currentSize + totalNewSubspaces);

  // Create new subspaces
  int newIndex = currentSize;
  int indices [];
  ArrayResize (indices, coords);
  for (int i = 0; i < coords; i++) indices [i] = 0;

  for (int idx = 0; idx < totalNewSubspaces && newIndex < ArraySize (subspaces); idx++)
  {
    subspaces [newIndex].Init (coords);
    subspaces [newIndex].level = parent.level + 1;
    subspaces [newIndex].parentIndex = subspaceIndex;

    // Calculate the boundaries of the current subspace
    for (int c = 0; c < coords; c++)
    {
      double intervalSize = (parent.max [c] - parent.min [c]) / m_value;
      subspaces [newIndex].min [c] = parent.min [c] + indices [c] * intervalSize;
      subspaces [newIndex].max [c] = parent.min [c] + (indices [c] + 1) * intervalSize;
    }

    // Move on to the next subspace
    int c = coords - 1;
    while (c >= 0)
    {
      indices [c]++;
      if (indices [c] < m_value) break;
      indices [c] = 0;
      c--;
    }

    // If the full loop completed, exit
    if (c < 0) break;

    newIndex++;
  }
}
//——————————————————————————————————————————————————————————————————————————————

GenerateNewPopulationメソッドは、各部分空間のpromisingRank値に応じて点の新しい集団を生成し、それらを分布させるために設計されています。

まず、すべての部分空間に対するpromisingRankの総和を計算します。この値は、各部分空間に生成すべき点の比例配分を決定するために使用されます。ランクの総和が0.0001未満と非常に小さい場合（すべての部分空間のランクが0の場合など）、点の均等分布を保証するために、すべての部分空間に対して最小の正のランク値1.0が割り当てられます。その後、各部分空間について、そのpromisingRankが総和に対して占める割合に基づき、生成すべき点の数が計算されます。

ここでは(subspaces[i].promisingRank / totalRank) * popSizeという式が用いられます。ここでpopSizeは必要な集団サイズです。結果は最も近い整数に丸められます。生成される点数はpopSizeを超えないよう上限が設定されます。各部分空間内では、計算された数の点が生成され、各点についてcoords座標が部分空間の境界内で一様分布に従って生成されます。各次元では、座標値は指定された最小値および最大値によって制約され、rangeStep[c]のステップを持つ格子として構築されます。

さらに、部分空間への点の分配後に生成点の総数がpopSizeに満たない場合、不足分の点は探索空間全体に対して一様に生成されます。このときrangeMin[c]およびrangeMax[c]による全体範囲が使用され、同様に制約条件とrangeStep[c]のステップに従って格子として形成されます。これにより、集団サイズは常にpopSizeに維持されます。

//+----------------------------------------------------------------------------+
//| Generate a new population                                                  |
//+----------------------------------------------------------------------------+
void C_AO_FBA::GenerateNewPopulation ()
{
  // Calculate the sum of the ranks of all subspaces
  double totalRank = 0.0;
  for (int i = 0; i < ArraySize (subspaces); i++)
  {
    totalRank += subspaces [i].promisingRank;
  }

  // If all ranks are 0, set the uniform distribution
  if (totalRank <= 0.0001) // Check for approximate equality to zero
  {
    for (int i = 0; i < ArraySize (subspaces); i++)
    {
      subspaces [i].promisingRank = 1.0;
    }
    totalRank = ArraySize (subspaces);
  }

  int points = 0;

  for (int i = 0; i < ArraySize (subspaces) && points < popSize; i++)
  {
    // Calculate the number of points for this subspace according to the equation
    int pointsToGenerate = (int)MathRound ((subspaces [i].promisingRank / totalRank) * popSize);

    // Limitation against exceeding the limits 
    pointsToGenerate = MathMin (pointsToGenerate, popSize - points);

    // Generate points in this subspace
    for (int j = 0; j < pointsToGenerate; j++)
    {
      // Create a new point uniformly within the subspace
      for (int c = 0; c < coords; c++)
      {
        a [points].c [c] = u.RNDfromCI (subspaces [i].min [c], subspaces [i].max [c]);
        a [points].c [c] = u.SeInDiSp (a [points].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      }

      points++;
      if (points >= popSize) break;
    }
  }

  // If not all points were generated, fill the remaining ones uniformly throughout the space
  while (points < popSize)
  {
    for (int c = 0; c < coords; c++)
    {
      a [points].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]);
      a [points].c [c] = u.SeInDiSp (a [points].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
    points++;
  }
}
//——————————————————————————————————————————————————————————————————————————————

MutatePointsメソッドは、C_AO_FBAクラスにおいて集団内の点に変異を適用するために設計されており、解の多様性を高め、局所解への停滞を防ぐためのアルゴリズム手順の一部です。

元の実装部分では、ランダムに選択された点の座標にガウスノイズを加えるというFBA本来のアイデアが用いられています。しかし、このような変異ではアルゴリズムの性能が低く、ランダムアルゴリズムの結果とほとんど差がないため、このブロックはコメントアウトされており、より良い実装に置き換えられています。

現在の主な実装部分では、まず集団全体を走査します。各エージェント（または点）および各座標について、確率条件がチェックされます。事前に設定された突然変異確率に基づいて条件が満たされた場合、その座標値は冪分布に基づく関数によって変化させられます。この関数は変動の度合いを制御できる指数を持っています。その後、更新された値は調整され、指定された範囲内に収まるよう制限されます。また、サンプリングステップrangeStepも考慮されます。

この結果として、このメソッドは集団内の個々の点に対して確率的な変異を与え、解の多様性を促進し、グローバル最適解を発見する能力を向上させます。

//+----------------------------------------------------------------------------+
//| Mutation of points in the population                                       |
//+----------------------------------------------------------------------------+
void C_AO_FBA::MutatePoints ()
{
  // Add Gaussian noise to P3% of randomly selected points from the new population
  /*
  int numToMutate = (int)MathRound (popSize * P3 / 100.0);
  numToMutate = MathMax (1, MathMin (numToMutate, popSize));

  for (int i = 0; i < numToMutate; i++)
  {
    int index = u.RNDminusOne (popSize);

    // Add noise to each coordinate
    for (int c = 0; c < coords; c++)
    {
      // Standard deviation of 10% of the range
      //double stdDev = (rangeMax [c] - rangeMin [c]) * 0.1;

      // Gaussian noise using the Box-Muller method
      //double noise = NormalRandom (0.0, stdDev);

      // Add noise and limit the value
      a [index].c [c] += noise;
      a [index].c [c] = u.SeInDiSp (a [index].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
  */

  for (int p = 0; p < popSize; p++)
  {
    for (int c = 0; c < coords; c++)
    {
      if (u.RNDprobab () < P3)
      {
        a [p].c [c] = u.PowerDistribution (cB [c], rangeMin [c], rangeMax [c], 20);
        a [p].c [c] = u.SeInDiSp (a [p].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

SortByFitnessメソッドは、2つの配列をソートするために設計されています。1つは適応度関数値を含む配列であり、もう1つは対応する要素のインデックスを含む配列です。このメソッドは、値の配列、インデックスの配列、配列のサイズ、およびソート順を指定するオプションフラグをパラメータとして受け取ります。

配列サイズが1より大きい場合、このメソッドは内部のQuickSort関数を呼び出し、要素に対してクイックソートを実行します。この際、値の配列とインデックスの配列は同時にソートされ、値とインデックスの対応関係が維持されます。その結果、メソッド実行後には、選択された順序に従って適応度関数値に基づく順序で要素が並び替えられます。

//+----------------------------------------------------------------------------+
//| Sort by fitness function value                                             |
//+----------------------------------------------------------------------------+
void C_AO_FBA::SortByFitness (double &values [], int &indices [], int size, bool ascending = false)
{
  if (size > 1) QuickSort (values, indices, 0, size - 1, ascending);
}
//——————————————————————————————————————————————————————————————————————————————

QuickSortメソッドは、valuesとindicesという2つの関連する配列に対してクイックソートアルゴリズムを実装しています。このメソッドは、valueとその元のインデックスとの対応関係を維持したまま、配列を再帰的に分割しながらソートします。パラメータとして、ソート対象の配列、ソート範囲の境界（lowおよびhigh）、およびソート順序を決定するascendingフラグを受け取ります。

//+----------------------------------------------------------------------------+
//| Quick sort algorithm                                                       |
//+----------------------------------------------------------------------------+
void C_AO_FBA::QuickSort (double &values [], int &indices [], int low, int high, bool ascending)
{
  if (low < high)
  {
    int pi = Partition (values, indices, low, high, ascending);

    QuickSort (values, indices, low, pi - 1, ascending);
    QuickSort (values, indices, pi + 1, high, ascending);
  }
}
//——————————————————————————————————————————————————————————————————————————————

Partitionメソッドはクイックソートアルゴリズムの主要な構成要素です。このメソッドの役割は、ピボット要素を選択し、indices配列の要素を再配置することです。これにより、ピボットより「小さい」要素（またはソート順に応じて「大きい」要素）はピボットの左側に配置され、「大きい」（または「小さい」）要素は右側に配置されます。ここでの「小さい」「大きい」は、indices内のインデックスが参照するvalues配列の値に基づいて定義されます。

//+----------------------------------------------------------------------------+
//| Partition function for QuickSort                                           |
//+----------------------------------------------------------------------------+
int C_AO_FBA::Partition (double &values [], int &indices [], int low, int high, bool ascending)
{
  double pivot = values [indices [high]];
  int i = low - 1;

  for (int j = low; j < high; j++)
  {
    bool condition = ascending ? (values [indices [j]] < pivot) : (values [indices [j]] > pivot);
    if (condition)
    {
      i++;
      // Exchange values
      int temp = indices [i];
      indices [i] = indices [j];
      indices [j] = temp;
    }
  }

  // Exchange values
  int temp = indices [i + 1];
  indices [i + 1] = indices [high];
  indices [high] = temp;

  return i + 1;
}
//——————————————————————————————————————————————————————————————————————————————

テスト結果

このアルゴリズムは全体的に良好な性能を発揮します。

FBA|Fractal-Based Algorithm|50.0|60.0|30.0|0.8|10.0|
=============================
5 Hilly's; Func runs:10000; result:0.7900044352090774
25 Hilly's; Func runs:10000; result:0.6513385092404853
500 Hilly's; Func runs:10000; result:0.2896548031738138
=============================
5 Forest's; Func runs:10000; result:0.8715768614282637
25 Forest's; Func runs:10000; result:0.5682316842631675
500 Forest's; Func runs:10000; result:0.18876552479611478
=============================
5 Megacity's; Func runs:10000; result:0.6107692307692306
25 Megacity's; Func runs:10000; result:0.46061538461538465
500 Megacity's; Func runs:10000; result:0.12398461538461655
=============================
All score:4.55494 (50.61%)

可視化は、アルゴリズムが探索空間をより小さな部分空間へ分解していく様子を示しています。また、結果は低次元関数において高い変動性を示しています。

Hilly

Hillyテスト関数のFBA

Forest

Forestテスト関数のFBA

Megacity

Megacityテスト関数のFBA

テスト結果に基づいて、FBAアルゴリズムは評価表で29位にランクされています。

#	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	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	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
30	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
31	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
32	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
33	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
34	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
35	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
36	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
37	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
38	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
39	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
40	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
41	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
42	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
43	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
44	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
45	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
	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

まとめ

突然変異を加えたFBAアルゴリズムの改良版は、結果として50.61%を示し、元のバージョンと比較して効率が2倍向上しています。

FBA|Fractal-Based Algorithm|50.0|60.0|30.0|5.0|
=============================
5 Hilly's; Func runs:10000; result:0.4780639253626462
25 Hilly's; Func runs:10000; result:0.3222029113692554
500 Hilly's; Func runs:10000; result:0.25720991988937014
=============================
5 Forest's; Func runs:10000; result:0.36567166223346415
25 Forest's; Func runs:10000; result:0.22043205527307377
500 Forest's; Func runs:10000; result:0.15869146061036057
=============================
5 Megacity's; Func runs:10000; result:0.2861538461538461
25 Megacity's; Func runs:10000; result:0.15015384615384622
500 Megacity's; Func runs:10000; result:0.09838461538461622
=============================
All score:2.33696 (25.97%)

突然変異メカニズムにおける根本的な変更により、新しいアプローチは探索空間のグローバルな探索と、発見された有望解の局所的な活用との間で、より合理的なバランスを提供します。

主な成果は、アルゴリズムが単なる完全にランダムな変更ではなく、探索地形に関する蓄積された知識を利用して突然変異を誘導するようになった点にあります。これは、ランダム性と決定論がバランスよく共存する自然な最適化プロセスとより整合しています。このアプローチにより、特に多数の局所極値を持つ複雑な多次元空間において、アルゴリズムがより速く大域的最適解へ収束することが可能となり、これが大幅な性能向上の理由となっています。

Tab

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

チャート

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

FBAの長所と短所

長所

中次元および高次元関数における安定した結果

短所

低次元関数では結果の散布度が高くなる
興味深いものの、アルゴリズムの基本的な考え方としてはやや「弱い」

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

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

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

添付されたファイル |

ZIPをダウンロード

FBA.zip (209.78 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.

この著者による他の記事

ディスカッションに移動

EAのサンプル

一般的なMACDを使ったEAを例として、MQL4開発の原則を紹介します。

市場シミュレーション（第19回）：SQL入門(II)

最初のSQLに関する記事でも説明したように、SQLにすでに組み込まれていることを実現するために、わざわざ時間をかけて手続きをプログラミングする意味はありません。しかし、基礎を理解していなければ、SQLを使って何かをおこなうことも、このツールが提供する機能を十分に活用することもできません。そこで今回の記事では、データベースにおける基本的な作業をどのようにおこなうかを見ていきます。

エラー 146 (「トレードコンテキストビジー」) と、その対処方法

この記事では、MT4において複数のEAの衝突をさける方法を扱います。ターミナルの操作、MQL4の基本的な使い方がわかる人にとって、役に立つでしょう。

初級から中級まで：構造体(VII)

本日の記事では、さまざまな要素の構造化に関する問題をどのように解決し、よりシンプルで魅力的な設計へと導くかについて解説します。内容は学習向けであり、そのため本番環境のコードを構成するものではありませんが、ここで扱う概念や知識を十分に理解することが極めて重要です。これにより、今後提示するコードをよりスムーズに追えるようになります。