母集団最適化アルゴリズム：粒子群(PSO)

MetaTrader 5 — 例 | 12 1月 2023, 11:42

327

Andrey Dik

彼らは、太陽の光の中を浮遊したり雷雲を追ったりするために、

明確な群れを形成する。大気中の放電からエネルギーを引き出している可能性がある。

しかし、危機の瞬間、またはより広く言えば、自分たちの存在を脅かす突然の変化の瞬間に、彼らは団結する...

スタニスワフ・レム「砂漠の惑星」より

内容

1.はじめに

スタニスワフ・レムのすばらしいSFベストセラー『砂漠の惑星』を読んだことのある方は、おそらくかなりの数いらっしゃるでしょう。驚くべきことに、「群知能」についての最初の記述の1つは、まさにこのSF小説の発表とともに生まれました。この物語は、集中管理なしで生き残ったロボットについてです。特に、最も複雑で知的で強力な標本ではなく、最も単純で最も数の多い標本が生き残ったのです。

何千年にもわたるネクロエボリューションの過程で、これらのマシンは、知性とエネルギーの利用可能性の両方で彼らを凌駕する競争相手に効果的に対処することを学びました。彼らは他のロボットだけでなく、地球の生物世界とも戦わなければなりませんでした。この作品のファンタジーの要素は、進化と自然そのものと確実に比較できます。

はるかに昔の古代から、人はグループ内の動物の行動（いわゆる群行動）に関心を持ってきました。鳥の群れが温暖な国に渡るときに鳥がどのように機能するか、ミツバチの群れがどのように食物を生産するか、アリのコロニーがどのように複雑な構造を作りながら生き残るか、魚が堤防でどのように行動し、それらの行動が非常に同期しているのは何故なのか...うまく調整された一体的な有機体のいくつかのパターンを示す、社会における個人の組織化は、アルゴリズム最適化の分野で新しいアイデアを奨励するものです。

群知能によって、自己組織化システムの集団行動のシミュレーションが記述されます。そのようなアルゴリズムはかなり多数あります。1995年にJ. KennedyとR .Eberhartによって書かれた正規版では、この手法の基礎となるモデルは、レイノルズ平均モデルを単純化することによって得られました。この単純化の結果として、個体群の個別の個人が、サイズはありませんが速度を持つ個別のオブジェクトとして表示されるようになりました。

物質粒子と非常に似ているため、結果として得られる単純なオブジェクトは粒子と呼ばれ、その集団は群と呼ばれました。各瞬間（各反復）で、粒子は空間内の位置と速度ベクトルを持ちます。粒子の位置ごとに、目的関数の対応する値が計算され、これに基づいて、特定のルールに従って、粒子は検索空間内の位置と速度を変更します。粒子の次の位置を決定するとき、適合度関数のタスクに対応する、他のすべての隣接粒子の中からの最良の位置に関する情報が考慮されます。

群れアルゴリズムの例:

粒子群最適化
アリのアルゴリズム
ハチのアルゴリズム
人工免疫システム
灰色オオカミのアルゴリズム
コウモリのアルゴリズム
重力探索アルゴリズム
利他主義アルゴリズム
その他多数

集団行動のモデル化から集団最適化への移行は、生物はコロニーで団結して生活条件を改善するという生物学的考え方に基づいています。コロニー内の各生物は、平均して、捕食者との戦いで生き残る可能性が高く、コロニーは個々の生物と比較してより効率的に食物を検索、処理、保存することができます。言い換えれば、生物のコロニーは、その存在の全期間にわたって、さまざまな程度の効率でさまざまな最適化問題を解決します。例は、捕食者からの損失を最小限に抑えながら食物の量を最大化することです。これらの考慮事項は、さまざまな数学的最適化手法の構築の基礎を形成しました。

粒子群は、その開始以来、最も有名で人気のある最適化アルゴリズムの1つです。そのさまざまな実装の多くの作成者は、アルゴリズムが多くの引数を持つ複雑な関数を最適化するのに非常に効果的であり、ニューラルネットワークの訓練にも適していると主張しています。

この記事では、このアルゴリズムが実際に複雑な問題を解決するのに適しているかどうかを調べます。アルゴリズムの古典的なバージョンとその修正版の多くでは、最適化された関数が滑らかで連続的でなければならないという事実に関連する重大な制限があります。つまり、離散関数にはまったく適していません。ただし、一連の記事に沿って、検討中のすべてのアルゴリズムは、少なくともアルゴリズムが純粋に技術的に機能するように、欠点を排除するために（制限がある場合）そのような方法で変更されます。言い換えれば、すべてのアルゴリズムは、関数の滑らかさ（トレーダーの問題など）に無関心である必要があり、引数のステップに制限があってはなりません。

2.アルゴリズムの原則

前回の記事では最適化の世界を紹介しましたが、メインプログラム（EA、スクリプト、指標）と最適化アルゴリズムコアとの相互作用の原則については説明しませんでした。これには注意を払うことが重要です。いずれにせよ、注意深い読者は、なぜアルゴリズムとサンプルプログラムがそのように書かれているのかという疑問を抱くでしょう。最適化アルゴリズムの既存のバージョンは、アルゴリズムがメインの実行可能プログラムである一方で、アルゴリズムが外部オブジェクトに関する適合度関数を参照するように構築されています。

下の図1では、アルゴリズムが最適化されたパラメータを適合度関数に渡し、適合度値（評価基準）を取得することを示しています。このシステムは、トレーダーを含むユーザーの問題を解決するためのプログラムを構築するのには不便です。なぜ不便なのでしょうか。たとえば、履歴全体で実行されたテスターを呼び出すことはできません。

古典的スキーム

図1：PSOと適合度関数の相互作用

図2に表示されている構造は、はるかに便利です。ここでの最適化アルゴリズムは独立したプログラムではなく、別々のモジュールまたは「ブラックボックス」です。このモジュールには、最適化された引数ごとに「min」、「max」、「step」パラメータがあります。MQLプログラムは、要求に応じて最適化された引数を受け取り、適合度値、つまり適合度関数値を返します。この構造により、EAでの自動最適化の使用からカスタム最適化マネージャーの作成まで、さまざまな非常に柔軟なソリューションを構築できます。

MQL5スキーム

図2：MQLプログラムとPSOの間の相互作用

また、最適化アルゴリズム（図2のMQLブロック）のメソッド呼び出しの構成は、すべての最適化アルゴリズム(AO)で同じ一般的なスキームで表すことができることにも言及する価値があります。

Initialization_АО_0

反復のサイクル（エポック）
{
1）Method_АО_1
2）最適化されたパラメータのバリエーションごとに適合値を取得する
3）Method_АО_2
}

したがって、3つのpublicメソッド（Initialization_АО_0、Method_АО_1、Method_АО_2）のみが使用されていることがわかります。これは、複雑なユーザープロジェクトの最適化プロセスを整理するのに十分です。

PSOワークフロー自体を図3に示します。これには、次の論理ステップが含まれています。

ランダムに粒子を生成する（最初の反復）
各粒子の適合度を取得する
一般的にすべての粒子の適合値を取得する
粒子速度を調整する
ブレークポイントまたはステップ2へ
プログラムの完成

PSOスキーム

図3：PSOワークフロー

粒子群アルゴリズムについてさらに詳しく考えてみましょう。

群知能システムは、相互に、また環境と相互作用する多くの粒子で構成されています。各粒子は単純なルールに従いますが、それぞれに何をすべきかを指示する集中型の動作制御システムはありません。それらの間の局所的およびランダムな相互作用は、個人によって制御されないインテリジェントなグループ行動の出現につながります。
群れとの類似性を引き出すと、すべての粒子は次の単純なタスクを実行する必要があると言えます。

他の粒子との交差を避ける
周囲の粒子の速度に応じて速度を調整する
自分自身と環境との間にかなり小さな距離を保つようにする

PSOアルゴリズムは、母集団の初期化から始まります。2番目のステップは、各粒子の適応度値を計算することです。その後、個々のベストスコアとグローバルベストスコアが更新され、次に粒子の速度と位置が更新されます。PSOを使用する場合、数値最適化問題の可能な解は、粒子の位置によって表されます。さらに、各粒子には、その絶対的な大きさと方向を反映した現在の速度があり、新しい、おそらくより適切な解/位置に向かいます。

粒子には、その適応度値、現在の位置、既知の最適な位置（既知の最適な適応度を持つ以前の位置）、および既知の最適な位置の適応度も格納されます。完了条件が満たされるまで、ステップ2から4が繰り返されます。最初の反復では、すべての粒子を分散させて最適な解を見つけます（探索）。すべての粒子が評価されます。近傍トポロジーの最適解が検出され、群れの各メンバーの個別および全体的な最適粒子が更新されます。収束は、すべての粒子を最適な解を持つ粒子に引き付けることによって達成されます。

PSOアルゴリズムの核心は非常にシンプルですが、この記事のコードをニーズに合わせて変更できるようにするには、それを理解する必要があります。PSOは反復プロセスです。メイン処理ループの各反復で、各粒子の現在の速度が最初に更新されます。粒子の現在の速度、その局地的情報、および群れのグローバルな情報が考慮されます。各粒子の位置は、その粒子の新しい速度の値を使用して更新されます。

数学的には、これら2つの粒子座標更新式は次のようになります。

v(t+1) = w * v(t) + c1 * rp * (p(t) – x(t)) + (c2 * rg * (g(t) – x(t))
x(t+1) = x(t) + v(t+1)

位置更新プロセスは、提案された式よりも実際にははるかに簡単です。最初の方程式は、粒子の速度を更新するためのものです。

項v（t+1）は、時刻t+1での速度を示します。新しい速度は3つの項に依存します。

第1項：w * v(t).w係数は慣性の重み付け率と呼ばれ、単なる定数です。v(t) は、時刻tにおける現在の速度です。
第2項：c1 * rp * (p(t) – x(t)).c1係数は、認知（または個人、またはローカル）重み付け率と呼ばれる定数です。rp乗数は[0, 1]の範囲の確率変数です。p(t)ベクトル量はこれまでに見つかった粒子の最適な位置であり、x(t)ベクトル量は粒子の現在の位置です。
第3項：速度更新c2 * rg * (g(t) – x(t)。c2係数は、社会的（またはグローバル）重み付け率と呼ばれる定数です。rg乗数は、[0,1]の範囲の確率変数です。g(t)ベクトルの値は、これまでに発見された群内の粒子の中で最もよく知られている位置です。新しい速度v(t+1)が決定されると、それを使用して粒子の新しい位置x(t+1)が計算されます。

3.古典的な実装

空間内の一連の座標（最適化されたパラメータ）を記述する論理単位は粒子であり、構造体として表すことができます。ここで、c[]は粒子の座標、cB[]はすべての反復における粒子の最適な座標です。v[]は粒子の各座標の速度、ffは粒子の現在の適応度値、ffBはすべての反復に対する粒子の最適な適応度値です。粒子構造体のコンストラクタで、double型で表現できる最小値を使用してffとffBの値を初期化します。アルゴリズムは関数の最大値を見つけるように設計されているため (最小値を見つけるには、結果の適応度値の前に「-」記号を追加するだけで十分です)。

//——————————————————————————————————————————————————————————————————————————————
struct S_Particles
{
  public:
    double c  []; //coordinates
    double cB []; //best coordinates
    double v  []; //velocity

    double ff;    //the value of the fitness function
    double ffB;   //best value fitness function

    S_Particles ()
    {
      ff  = -DBL_MAX;
      ffB = -DBL_MAX;
    }
};
//——————————————————————————————————————————————————————————————————————————————

PSOアルゴリズムを、3つのpublicメソッド InitPS ()、Preparation ()、Dwelling ()（Initialization_АО_0、Method_АО_1、Method_АО_2）のみを特徴とするクラスとして実装しましょう。privateメソッドのうち、GenerateRNDparticles ()とParticleMovement ()はPSOに固有のものですが、残りは前回の記事で既に検討済みです。p[]構造体配列は粒子の群れです。各粒子が適応度値、独自の座標、および最適な座標を持っているという事実に加えて、群れは全体として、最適な座標cBと最適な適応度値ffBを持っています。

//——————————————————————————————————————————————————————————————————————————————
class C_AO_PSO
{
  public:
  //----------------------------------------------------------------------------
  S_Particles p    []; //particles
  double rangeMax  []; //maximum search range
  double rangeMin  []; //manimum search range
  double rangeStep []; //step search
  double cB        []; //best coordinates
  double ffB;          //FF of the best coordinates

  void InitPS (const int    params,       //number of opt. parameters
               const int    size,         //swarm size
               const double inertiaP,     //inertia
               const double selfBoostP,   //boost
               const double groupBoostP); //group boost

  void Preparation ();
  void Dwelling ();

  private:
  //----------------------------------------------------------------------------
  int swarmSize; //swarm size
  int parameters;//number of optimized parameters

  double inertia;
  double selfBoost;
  double groupBoost;
  bool   dwelling;

  void   GenerateRNDparticles ();
  void   ParticleMovement     ();
  double SeInDiSp             (double in, double inMin, double inMax, double step);
  double RNDfromCI            (double min, double max);
};
//——————————————————————————————————————————————————————————————————————————————

InitPS ()メソッドは、最適化を開始する前にアルゴリズムを初期化するためのものです(Initialization_АО_0)。メソッドの引数の値は、メソッド内のprivateメンバーに割り当てられ、サイズは、群れ内の各粒子の群れおよび内部パラメータに割り当てられます。

//——————————————————————————————————————————————————————————————————————————————
void C_AO_PSO::InitPS (const int    paramsP,
                       const int    sizeP,
                       const double inertiaP,
                       const double selfBoostP,
                       const double groupBoostP)
{
  ffB = -DBL_MAX;

  parameters = paramsP;
  swarmSize  = sizeP;

  ArrayResize (rangeMax,  parameters);
  ArrayResize (rangeMin,  parameters);
  ArrayResize (rangeStep, parameters);

  dwelling = false;

  inertia    = inertiaP;
  selfBoost  = selfBoostP;
  groupBoost = groupBoostP;

  ArrayResize (p, swarmSize);

  for (int i = 0; i < swarmSize; i++)
  {
    ArrayResize (p [i].c,  parameters);
    ArrayResize (p [i].cB, parameters);
    ArrayResize (p [i].v,  parameters);
  }

  ArrayResize (cB, parameters);
}
//——————————————————————————————————————————————————————————————————————————————

Preparation ()メソッドは、各反復（エポック）で最初に呼び出されます(Method_АО_1)。このメソッドは簡単ですが、とても重要です。メソッドが最初のエポックで呼び出されるか、後続のエポックで呼び出されるか（dwellingフラグによって決定される）に応じて、群れの適応度値がリセットされ、ランダムな群れの集団が作成されるか、粒子が新しい座標に移動します。

//——————————————————————————————————————————————————————————————————————————————
void C_AO_PSO::Preparation ()
{
  if (!dwelling)
  {
    ffB = -DBL_MAX;
    GenerateRNDparticles ();
    dwelling = true;
  }
  else ParticleMovement ();
}
//——————————————————————————————————————————————————————————————————————————————

GenerateRNDparticles ()メソッドで、ランダムな群集団が生成されます。粒子は、それぞれに指定された範囲内のランダムな座標と、各座標のランダムな速度を持ちます。

//——————————————————————————————————————————————————————————————————————————————
void C_AO_PSO::GenerateRNDparticles ()
{
  for (int s = 0; s < swarmSize; s++)
  {
    for (int k = 0; k < parameters; k++)
    {
      p [s].c  [k] = RNDfromCI (rangeMin [k], rangeMax [k]);
      p [s].c  [k] = SeInDiSp (p [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);
      p [s].cB [k] = p [s].c [k];
      p [s].v  [k] = RNDfromCI (0.0, (rangeMax [k] - rangeMin [k]) * 0.5);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

ParticleMovement ()メソッドは、粒子を新しい位置に移動するためのアルゴリズムをトリガーします。これを実現するには、上記の式に従って各座標の速度を計算する必要があります。これは基本的に変位値、つまり、粒子が現在位置する場所と移動する必要がある場所との差であるため、何故「速度」という用語が使用されるのかはわかりません。座標ごとにこの差を計算したら、単純に現在の値を加算します。その後、特定のステップで最適化されたパラメータ（粒子の場合は座標）の最小/最大境界を超えることが許容できないかどうかを確認します。

//——————————————————————————————————————————————————————————————————————————————
void C_AO_PSO::ParticleMovement ()
{
  double rp;       //random component of particle movement
  double rg;
  double velocity;
  double posit;
  double positBest;
  double groupBest;

  for (int i = 0; i < swarmSize; i++)
  {
    for (int k = 0; k < parameters; k++)
    {
      rp = RNDfromCI (0.0, 1.0);
      rg = RNDfromCI (0.0, 1.0);
      
      velocity  = p [i].v  [k];
      posit     = p [i].c  [k];
      positBest = p [i].cB [k];
      groupBest = cB [k];

      p [i].v [k] = inertia * velocity + selfBoost * rp * (positBest - posit) + groupBoost * rg * (groupBest - posit);
      p [i].c [k] = posit + p [i].v [k];

      p [i].c [k] = SeInDiSp (p [i].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Dwelling ()メソッドは、最適化に使用されるアルゴリズム(Method_АО_2)の3番目のpublicメソッドです。このメソッドの目的は、各粒子の以前のパフォーマンスに対する最適な座標と適合度の値を更新し、必要に応じて群れの適合度と群れの最適な座標を更新することです。このメソッドは、反復ループで適応度値を取得した後に呼び出されます。

//——————————————————————————————————————————————————————————————————————————————
void C_AO_PSO::Dwelling ()
{
  for (int i = 0; i < swarmSize; i++)
  {
    //remember the best position for the particle
    if (p [i].ff > p [i].ffB)
    {
      p [i].ffB = p [i].ff;
      for (int k = 0; k < parameters; k++) p [i].cB [k] = p [i].c [k];
    }

    if (p [i].ff > ffB)
    {
      ffB = p [i].ff;
      for (int k = 0; k < parameters; k++) cB [k] = p [i].c [k];
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

以下は、指定された範囲内の特定のステップでdouble数を離散化する関数です。

//——————————————————————————————————————————————————————————————————————————————
// Choice in discrete space
double C_AO_PSO::SeInDiSp (double in, double inMin, double inMax, double step)
{
  if (in <= inMin) return (inMin);
  if (in >= inMax) return (inMax);
  if (step == 0.0) return (in);
  else return (inMin + step * (double)MathRound ((in - inMin) / step));
}
//——————————————————————————————————————————————————————————————————————————————

以下は、指定された範囲でランダムなdouble数を取得する関数です。

//——————————————————————————————————————————————————————————————————————————————
// Random number generator in the custom interval
double C_AO_PSO::RNDfromCI (double min, double max)
{
  if (min == max) return (min);
  double Min, Max;
  if (min > max)
  {
    Min = max;
    Max = min;
  }
  else
  {
    Min = min;
    Max = max;
  }
  return (double(Min + ((Max - Min) * (double)MathRand () / 32767.0)));
}
//——————————————————————————————————————————————————————————————————————————————

理論はこれで終わりです。練習に取り掛かりましょう。

図2で説明した、連載の最初の記事と同じ構造をアルゴリズムの構築に使用しているため（今後もこれを継続します）、アルゴリズムをテストスタンドに接続することは難しくありません。.

スタンドを実行すると、以下に示すようなアニメーションが表示されます。この場合、粒子の群れがどのように振る舞うかをはっきりと見ることができます。群れは本質的に群れのように振る舞います。関数のヒートマップ上では、密な雲の形で移動します。

覚えていらっしゃるかもしれませんが、黒い円は関数の大域的最適値（最大値）を表し、黒い点は現在の反復時に取得された検索アルゴリズムの最適な平均座標を表します。平均値がどこから来るのか説明しましょう。ヒートマップは2次元の座標であり、最適化される関数には数百の変数（測定値）が含まれる場合があります。したがって、結果は座標によって平均化されます。

Skinテスト関数のPSO

Forestテスト関数のPSO

Megacityテスト関数のPSO

アニメーションでわかるように、テストでは、PSOがスムーズな最初の関数に非常にうまく対処できることが示されましたが、それは2つの変数を最適化する場合のみです。検索空間の次元が増加すると、アルゴリズムの効率は急激に低下します。これは、2番目と離散的な3番目の関数で特に顕著です。結果は、前回の記事で説明したランダムアルゴリズムよりも著しく悪いものです。結果に戻り、結果の比較表を作成する際に詳しく説明します。

有名なPSOアルゴリズムが恥ずかしくもランダムアルゴリズムに負ける様子を見ると、アルゴリズムにもう一度チャンスを与えたいと思うかもしれません。次のセクションでは、PSOアルゴリズムを変更してみます。

4.修正版

私の意見では、PSOの弱点は次のとおりです。

1）各座標は、ほぼ1の確率で必然的に変更される：これは、反復ごとに群れの各粒子が、せいぜいグローバル領域の極値（ローカル）のどこかで振動することを意味しますが、最悪の場合、最大値/最小値（グローバル）の点に正確に到達することはありません。これは、アルゴリズムの特徴的な機能を意味します。極値（ローカル）で行き詰まる、つまり悪い収束です。

2）アルゴリズムは離散関数ではうまく機能しない：最初の欠陥は原因の1つです。粒子座標は、最適化されている関数の表面の最も近い「領域」にジャンプし、極値（ローカル）の近傍を詳細に調べることができません。

3）新しい領域を探索するアルゴリズムの能力が弱い：群れは、局所的な「穴」から逃れようとせずに、どこか一箇所に集中します。一部の著者は、マルチスウォーム修正の実装を作成する試みについて言及していますが、複雑な多変数関数を最適化する問題は未解決のままです。相互距離の原則が不明であるため、関節の動きの原則が満たされなければならないだけでなく、相互反発の可能性もあるからです。そうしないと、個々の群れが単に1つの領域または点に収束するため、そのような実装には意味がありません。同時に、単純な1変数または2変数関数の最適化は、優れた収束性を備えた最も単純な手法によって実行されます。

では、アルゴリズムを改善するにはどうすればよいでしょうか。

個々の最適な座標を他の粒子から粒子に渡す必要があることは明らか（必ずしもそうではありませんが）です。「ドナー」粒子の全体的な座標が優れているほど、座標を通過する確率が高くなります。粒子を選択する確率の変化を図4に模式的に示します。0から1までの乱数を生成し、結果の数値を放物線関数で変換してから、0からSwarmSize-1までの群内の粒子のシリアル番号の範囲にスケーリングします。これをおこなうには、PSOm（修正されたアルゴリズム）に追加のパラメータ（座標をコピーする確率）を導入する必要があります。また、粒子が優れているほど、インデックス0に近づくように群れを並べ替える必要があります。

ParabProbab

図4：シフトされた粒子選択確率

ParticleMovement ()メソッドを少し変更してみましょう。乱数[0;1]を生成します。数値が「copy」パラメータより大きいことが判明した場合は、上記で詳細に説明した粒子を使用して通常の操作を実行します。それ以外の場合は、図4にグラフで示されている規則に従って選択されたインデックスを使用して、別の粒子の座標をコピーします。

//——————————————————————————————————————————————————————————————————————————————
void C_AO_PSOm::ParticleMovement ()
{
  double rp;       //random component of particle movement
  double rg;
  double velocity;
  double posit;
  double positBest;
  double groupBest;

  for (int i = 0; i < swarmSize; i++)
  {
    for (int k = 0; k < parameters; k++)
    {
      rp = RNDfromCI (0.0, 1.0);
      rg = RNDfromCI (0.0, 1.0);

      double rC = RNDfromCI (0.0, 1.0);

      if (rC > copy)
      {
        velocity  = p [i].v  [k];
        posit     = p [i].c  [k];
        positBest = p [i].cB [k];
        groupBest = cB [k];

        p [i].v [k] = inertia * velocity + selfBoost * rp * (positBest - posit) + groupBoost * rg * (groupBest - posit);
        p [i].c [k] = posit + p [i].v [k];

        p [i].c [k] = SeInDiSp (p [i].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);
      }
      else p [i].c [k] = p [GetPartcileAdress ()].cB [k];
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Dwelling ()メソッドも変更する必要があります。SortParticles ()並び替え関数の呼び出しを追加します。

//——————————————————————————————————————————————————————————————————————————————
void C_AO_PSOm::Dwelling ()
{
  for (int i = 0; i < swarmSize; i++)
  {
    //remember the best position for the particle
    if (p [i].ff > p [i].ffB)
    {
      p [i].ffB = p [i].ff;
      for (int k = 0; k < parameters; k++) p [i].cB [k] = p [i].c [k];
    }

    if (p [i].ff > ffB)
    {
      ffB = p [i].ff;
      for (int k = 0; k < parameters; k++) cB [k] = p [i].c [k];
    }
  }

  SortParticles ();
}
//——————————————————————————————————————————————————————————————————————————————

GetParticleAdress ()関数は、最良の粒子に向かってシフトされた確率を持つ粒子のアドレスの選択を提供します。

//——————————————————————————————————————————————————————————————————————————————
//shift of probability in the smaller party (to an index 0)
int C_AO_PSOm::GetParticleAdress ()
{
  double x = RNDfromCI (-1.0, 0.0);
  x = x * x;
  x = Scale (x, 0.0, 1.0, 0, swarmSize - 1);
  x = SeInDiSp (x, 0, swarmSize - 1, 1);
  return ((int)x);
}
//——————————————————————————————————————————————————————————————————————————————

SortParticles ()関数は、従来のバブルソートです。

//——————————————————————————————————————————————————————————————————————————————
//Sorting of particles
void C_AO_PSOm::SortParticles ()
{
  //----------------------------------------------------------------------------
  int   cnt = 1;
  int   t0 = 0;
  double t1 = 0.0;
  //----------------------------------------------------------------------------

  // We will put indexes in the temporary array
  for (int i = 0; i < swarmSize; i++)
  {
    ind [i] = i;
    val [i] = p [i].ffB; //ffPop [i];
  }

  while (cnt > 0)
  {

    cnt = 0;
    for (int i = 0; i < swarmSize - 1; i++)
    {
      if (val [i] < val [i + 1])
      {
        t0 = ind [i + 1];
        t1 = val [i + 1];
        ind [i + 1] = ind [i];
        val [i + 1] = val [i];
        ind [i] = t0;
        val [i] = t1;

        cnt++;
      }
    }
  }

  // On the received indexes create the sorted temporary population
  for (int u = 0; u < swarmSize; u++) pT [u] = p [ind [u]];

  // Copy the sorted array back
  for (int u = 0; u < swarmSize; u++) p [u] = pT [u];
}
//——————————————————————————————————————————————————————————————————————————————

以下は、ある数値範囲から別の数値範囲に数値をスケーリングする関数です。

//——————————————————————————————————————————————————————————————————————————————
double C_AO_PSOm::Scale (double In, double InMIN, double InMAX, double OutMIN, double OutMAX)
{
  if (OutMIN == OutMAX) return (OutMIN);
  if (InMIN == InMAX) return (double((OutMIN + OutMAX) / 2.0));
  else
  {
    if (In < InMIN) return (OutMIN);
    if (In > InMAX) return (OutMAX);
    return (((In - InMIN) * (OutMAX - OutMIN) / (InMAX - InMIN)) + OutMIN);
  }
}
//——————————————————————————————————————————————————————————————————————————————

5.テスト結果

最後に、これまでの研究成果をまとめておきましょう。残念ながら、PSOアルゴリズムは、私がどれだけ良い結果を望んでいても、それ自体を正当化するものではありませんでした。研究は、ブレークと多数の引数を持つ離散関数の弱い収束を示しました。アルゴリズムを変更する試みは成功しませんでした。結果は、従来の実装よりもさらに悪いことが判明しました。

copyパラメータを0.8に近い値に増やしても、即時の収束を示すことができますが、これはテストの最初の滑らかな関数に対してのみで、引数が2つしかありません。他のテストでは、このパラメータは結果を悪化させるだけです。PSOの従来の実装では、1000個の引数を持つSkin関数でのみ興味深い結果が得られました。他のテストは普通であることが判明しました。

最終的なテスト結果は、それぞれ従来のアルゴリズムで0.47695、修正されたアルゴリズムで0.45144です。テスト結果を表に示します。テストスタンドでは、設定でテスト実行の数を選択できます（デフォルトは5）。そのため、コンピュータの処理能力が許す場合は、このパラメータを高く設定することで、統計的により正確な結果を得ることができます。

AO	実行	Skin			Forest			Megacity（discrete）			最終結果
AO	実行	2パラメータ（1F）	40パラメータ（20F）	1000パラメータ（500F）	2パラメータ（1F）	40パラメータ（20F）	1000パラメータ（500F）	2パラメータ（1F）	40パラメータ（20F）	1000パラメータ（500F）	最終結果
RND	1000	0.98744	0.61852	0.49408	0.89582	0.19645	0.14042	0.77333	0.19000	0.14283	0.51254
RND	10,000	0.99977	0.69448	0.50188	0.98181	0.24433	0.14042	0.88000	0.20133	0.14283	0.51254
PSO	1000	0.98436	0.72243	0.65483	0.71122	0.15603	0.08727	0.53333	0.08000	0.04085	0.47695
PSO	10,000	0.99836	0.72329	0.65483	0.97615	0.19640	0.09219	0.82667	0.10600	0.04085	0.47695
PSOm	1000	0.96678	0.64727	0.57654	0.80616	0.13388	0.06800	0.53333	0.08067	0.04211	0.45144
PSOm	10,000	0.99505	0.64986	0.57654	0.90401	0.18194	0.07104	0.74667	0.10400	0.04211	0.45144

上記のすべてを要約すると、PSOは、洗練された検索領域での収束が遅いことに加えて、平均的な最適点での高速で時期尚早の収束につながる傾向があります（局地的な検索能力が低い）。簡単に言えば、このアルゴリズムは非常に脆弱であり、複雑でさらに離散的な関数、特に複数の引数を持つ関数の最適化には適していません。

PSO全般を改善するために使用できる方法がいくつかあります。群れのサイズは重要な要素の1つです。群れのサイズが大きいほど、より高速で正確な収束の可能性が高くなります。ただし、実際の問題では、適合度関数の実行回数にしきい値があることが多く、群れのサイズを大きくしてもエポック数が比例して減少するだけなので、群れが進化する可能性が低くなります。

2つ目の方法は、探索と搾取のバランスを取ることです。反復の開始時には、高度な探索により、大域的最適に近い解を見つける可能性が高くなります。一方、反復の終わりまでに、高度な利用により、有望な領域で最も正確な解を見つける機会が粒子に与えられます。他の手法によるswarmステージの前の事前最適化は、PSOの基本的なパフォーマンスを改善するために使用できる別の手法であり、現在では非常に一般的に使用されています。各サブグループに異なるタスクまたは目標を割り当てることで、マルチタスクの問題におけるPSOの有効性を高めることもできます。

PSOの性能を向上させるもう1つの方法は、速度方程式の構成要素を確立することです（動的速度制御）。このような方法は、粒子をさまざまな方向に送り、大域的最適への収束を早めることができますが、これは単なる仮定にすぎません。

賛成：

アルゴリズムは非常に単純で、コンピューティングリソースを必要とせず、コードは非常に高速に動作します。これは、従来の実装では配列の並べ替えさえ行わないためです。
このアルゴリズムは、滑らかな関数でうまく機能します。これまでのところ、複数の引数を持つ滑らかな関数を最適化するためのテーブルでは、PSOが明らかにリーダーです。

反対：

最適化された機能研究の質の低さ - このアルゴリズムは、いくつかの一意のソリューションのセットが必要な問題の解決には適用できない。
速度と収束精度が低い。
離散関数の最適化には不向き。
ほぼ完全な非スケーラビリティ。

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

添付されたファイル |

ZIPをダウンロード

r2_The_world_of_AO_4PSOf.zip (22.47 KB)

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

この著者による他の記事

ディスカッションに移動

DoEasy-コントロール（第24部）：ヒント補助WinFormsオブジェクト

今回は、すべてのWinFormsライブラリオブジェクトの基本オブジェクトとメインオブジェクトを指定するロジックを見直し、新しいヒント基本オブジェクトとその派生クラスのいくつかを開発して、区切りの移動可能な方向を示すことにします。

DoEasy - コントロール（第23部）：TabControlおよびSplitContainer WinFormsオブジェクトの改善

今回は、WinFormsオブジェクトの作業領域の境界線に関連する新しいマウスイベントを追加し、TabControlとSplitContainerコントロールの機能に関するいくつかの欠点を修正することにします。

データサイエンスと機械学習（第08回）：:簡単なMQL5でのK平均法

データサイエンティストやトレーダーにとってデータマイニングは非常に重要です。多くの場合、データは私たちが思っているほど単純ではありません。人間の目は、データセット内のささいな基本パターンと関係を理解できません。k平均法アルゴリズムがその助けになるかもしれません。調べてみましょう...

マウンテンチャートとアイスバーグチャート

MetaTrader 5プラットフォームに新しいチャートタイプを追加するというアイデアはいかがでしょうか。このプラットフォームには他のプラットフォームにあるものがいくつかないという声もあります。しかし、実際のところ、MetaTrader 5は他の多くのプラットフォームではできないこと（少なくとも簡単にはできないこと）ができる、非常に実用的なプラットフォームです。