母集団最適化アルゴリズム：Stochastic Diffusion Search (SDS)

MetaTrader 5 — 例 | 2 4月 2024, 11:19

119

Andrey Dik

内容

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

1. はじめに

SDS（Stochastic Diffusion Search、確率的拡散探索）アルゴリズムは、1989年にJ. Bishopによって提案され、BishopとS.Nasutoによって積極的に開発されました。このアルゴリズムの特徴は、他の母集団アルゴリズムと比較して、数学的に深く正当化されていることです。SDSはもともと離散最適化のために開発されました。2011年には、大域的連続最適化のための改良が提案されました。

次は、興味深い事実です。

1. SDSは、最初の群知能メタヒューリスティックであり、群知能と自然探索最適化アルゴリズムのファミリーに属します。このようなアルゴリズムの他の例としては、蟻コロニー最適化、粒子群最適化、遺伝的アルゴリズムなどがあります。

2.スティグマジーコミュニケーションに基づく蟻コロニー最適化とは異なり、SDSはエージェント間の直接的なコミュニケーションを使用し、タカネムネボソアリが使用するタンデムコーリングの仕組みに似ています。

SDSアルゴリズムは、エージェントによる仮説（探索問題の解候補）の低コストの部分評価に基づいています。その後、エージェントは直接個人的なコミュニケーションを通じて、仮説に関する情報を交換します。拡散メカニズムによって、同じ仮説を持つエージェントのクラスタから質の高い解を特定することができます。

SDSアルゴリズムの動作をよりよく理解するために、レストランゲームという簡単な例えを使用することができます。

レストランゲームでは、参加者はエージェントの役割を演じ、レストランは仮説の役割を演じます。各エージェントは、自分の好みと他のエージェントから受け取った情報に基づいて、食事をするレストランを選択します。その後、エージェントは自分の選択と嗜好に関する情報を交換します。このプロセスの結果、同じレストランを選択したエージェントのクラスタが形成され、良い決断を下す可能性のあるエージェントとして識別されます。

SDSアルゴリズムにはいくつかの利点があります。第1に、エージェントが安価な部分仮説推定をおこなうことを可能にし、アルゴリズムの計算の複雑さを軽減します。第2に、エージェント間の直接的な個人的コミュニケーションを利用することで、効率的に情報を広めることができます。第3に、SDSは数学的根拠に基づいているため、信頼性と予測性が高くなります。

しかし、SDSアルゴリズムにも限界があります。第1に、仮説の概念が適用できる特定のタイプの問題でのみ有効です。第2に、エージェントが他の可能性を探索することなく、1つの仮説にあまりにも早く収束してしまう、早期収束の問題に悩まされる可能性があります。第3に、このアルゴリズムにはパラメータのチューニングが必要であり、これは複雑で時間のかかるプロセスです。何人かの作者からは制約の声が上がっています。それが正当なものかどうか調べてみましょう。

全体として、SDSは最適化問題を解くための興味深く効率的なアルゴリズムです。母集団アルゴリズムと数学的合理性の長所を兼ね備えており、様々な分野での研究や応用に魅力的です。

2.アルゴリズム

SDSアルゴリズムのより詳細な考察に移りましょう。

SDSは、2つの探索戦略のアイデアに基づく集団アルゴリズムです。

1. 解決策の部分的評価
2.有望な解決策を母集団全体に広める

SDSがどのように機能するかを簡単に説明する、2つの典型的なゲームがあります。
1. レストランゲーム
2.金採掘ゲーム

レストランゲーム

あるグループが見知らぬ街で長期出張しています。毎晩、グループは夕食のレストラン選びの問題に直面します。この街には、さまざまな料理を提供するレストランが数多くあります。グループの目標は、それぞれの個人が食事を楽しめる最高の店を見つけることです。しかし、ありとあらゆるレストランと料理の組み合わせを網羅的に検索するのは時間がかかりすぎます。この問題を解決するために、グループはSDSを使用することにします。

各個人は、街で一番おいしいレストランを選択するエージェントとして行動します。毎晩、グループはレストランを訪れ、そのレストランのメニューから無作為に1つを選び、仮説を検証します。翌朝の朝食時、前夜の夕食に不満のあった個人はそれぞれ、同僚に夕食の感想を聞きます。同僚の印象が良ければ、個人もそのレストランを選択します。そうでなければ、個人はその都市で利用可能なレストランのリストから無作為に別の場所を選択します。

こうして、この戦略のおかげで、かなりの数の個人が、市内で最高のレストランの周りに集まります。

このゲームにはいくつか面白い特徴があります。外部からのコントロールや管理がまったくない中で、個人がコミュニケーションをとりながら、独りではすぐに解決できない問題を解決していきます。現在のレストランのサービスやメニューが著しく低下したり、閉店したりした場合、個人は事実上、次に最高のレストランに移ります。主な条件は、レストラン、メニュー、個々の料理の比較可能性です。その経験が良かったかどうかは、各エージェントが自分で判断します。

グループは、市内のすべての場所のすべての料理が評価される前に、質の高いレストランで何度も夜を過ごします。
批評家は、個人の好む料理がそれぞれ異なる可能性が高いため、ある個人がすべての料理が気に入るレストランを見つける一方、グループは満足できないかもしれないと指摘します。もし、そのようなレストランに1人か少数だけが永続的に残っていたとしても、残りの人々はいつも通りに行動し続け、最終的に大多数はやはり最高のレストランに集まります。しかし、極端な場合、たとえグループの大多数を満足させるような素晴らしいレストランが1軒あったとしても、エージェント全員が独りで食事をすることになるかもしれません。このレストランが見つかることはないでしょう。個人は皆、現在の選択に満足しており、新しい場所を探そうとはしないからです。

私たちの実装では、検索戦略のロジックに小さな変更を加えています。そのおかげで、より良い経験を持つ個人がいない場合でも、グループはレストランの検索を継続することができます。したがって、レストランについての現在の意見を以前の意見から変更するという事実が重要である正規版とは異なり、レストランの検索は停止しません。グループの大多数が良い方向に意見を変えなければ、彼らは同じレストランに通い続けるでしょう。それは局所的最適解にはまってしまうことを意味します。

金採掘ゲーム

経験豊富な鉱夫で構成される仲間たちが、山脈の丘で金を採掘する可能性について知ります。しかし、最も豊かな場所がいったいどこにあるのかについての情報はありません。彼らの地図では、山脈はいくつかの丘に分かれており、それぞれに採掘が必要な地層が含まれています。時間をかけて金を発見する確率は、その富に比例します。

集団の富を最大化するために、鉱夫たちは金の層が最も豊富な丘を特定し、そこで最大数の鉱夫が採掘できるようにしなければなりません。しかし、この情報は事前に入手することはできません。この問題を解決するために、鉱夫は単純なSDSを使用することにします。

採掘プロセスは、各鉱夫が採掘する丘（カスタム丘仮説）を無作為に割り当てられることから始まります。毎日、各鉱夫は自分の丘のシームを無作為に選択して採掘します。

1日の終わりに鉱夫が幸せである確率は、見つけた金の量（適応度関数値）に比例します。
夕方、仕事を終えた坑夫たちは集まります。不幸せな鉱夫は、無作為に他の鉱夫を選択して話相手にします。選択された鉱夫が幸せである場合、喜んで同僚に自分が採掘している丘の名前を告げます。したがって、どちらの鉱夫も丘の仮説を支持することになります。選択された鉱夫が不幸せな場合、彼は何も言わず、元の鉱夫は再び新しい仮説を選ぶことを余儀なくされ、翌日採掘する丘を無作為に特定します。

SDS（自己組織化ダイナミックシステム）の文脈では、エージェントは鉱夫の役割を果たします。活動的なエージェントは「幸せな鉱夫」であり、活動的でないエージェントは「不幸せな鉱夫」です。各エージェントの仮説は、鉱夫の「丘の仮説」を表しています。このプロセスはSDSと同型であり、鉱夫たちは自然に自己組織化し、金が集中している山の尾根の丘に素早く集まることができます。

すべての鉱夫が毎日の終わりに幸せか不幸かのどちらかであると仮定すると、鉱夫の幸福度は、確率的に測定することもできるし、絶対的なブール値として表すこともできます。金が時間とともに減少する限られた資源としてモデル化された場合、探索は極めて適応的なものとなり、鉱夫は金の多い場所に移動します。

「幸せ」という言葉は食生活同様主観的なものですが、この場合は客観的な意味で使われています。鉱夫はみな同じプロセスを踏みます。1日にどれだけの金を見つけたかによって、1日の終わりに採掘している丘についての情報を共有する可能性のある場所に集まったときに、「ラッキー」と宣言する可能性が決まるのです。

鉱夫を「幸せな鉱夫」と「不幸な鉱夫」に分けることはしません。レストランゲームの概念の場合と同様に、これによってエージェントの新しい未踏の場所を探す活動を増やすことができます。

アルゴリズムを公式化するために、「候補者」という概念を使用します。これは、レストランゲームにおける代表者、金採掘ゲームにおける鉱夫に相当します。候補者は検索エージェントです。レストランや丘の本質をより簡単に理解するために、2つの座標を持つ空間を想像できますが、実際には、多次元の問題を解決するために無制限の数の座標を使用できます。図1において、C1、C2、C3はレストラン番号（検索フィールドの対応する空間）を格納する候補を示します。レストランに関する情報の拡散交換の過程で、候補者は、対話者の適応度関数の値が高ければ、無作為に選択された会議参加者からレストランの番号を借ります。各最適化パラメータ（探索空間座標）の範囲は、アルゴリズムの外部パラメータで指定されたレストランの数で割られます。例えば、アルゴリズムのパラメータに100軒のレストランが指定されている場合、これは各座標の範囲が100の部分に分割されることを意味します。

各レストランにはメニューがあります。メニューの各料理は、1つのレストラン内の探索空間の特定の座標です。このアルゴリズムは、候補者が無作為に選択されたレストランの料理を1品だけ味わうという方式を採用しています。

Cheme1

図1：レストラン情報交換の拡散原理を視覚的に表現したもの

SDSアルゴリズムの手順を疑似コードの形で見てみましょう。

1. 候補の初期化（無作為なレストランと料理を割り当てる）

2.0.仮説検証と候補者間の拡散交流

2.1.候補者の現在の経験と過去の経験の比較

2.1.1.体験がより良いものであれば、次の反復のための仮説としてレストランの住所を割り当てる

2.1.2.体験がより悪いものであれば、無作為に選択した候補者の意見を聞く

2.1.2.1.相手（候補者）の経験の方が良ければ、（現在の候補者にとって）有望なレストランの住所を取得する

2.1.2.2.相手（候補者）の経験の方が悪ければ、ある程度の確率で、無作為に選択されたレストランの住所を選ぶか、今のレストランを維持する

3.0.生成されたレストランリストから、次の反復のための仮説として料理を選択する

仮説検証の論理図を図2に示します。ほとんどの論理回路はレストランを選択するタスクを実行し、レストラン選択が完了した後、料理が無作為に選択されます。レストランの選択はアルゴリズムの主要なタスクですが、料理の選択は完全に無作為であり、以前の反復とは無関係です。

Cheme2

図2：仮説を検証するための論理的スキーム

SDSのコードを見て、アルゴリズムの中心であり、魂であるエージェント（別名候補者）から始めましょう。これは S_Candidate構造体で記述できます。以下のフィールドが含まれます。

1. raddr：レストランの住所を含む配列。配列の各要素は、レストラン1軒の住所を表します。
2. raddrPrev：前のレストランの住所を含む配列。配列の各要素は、レストラン1軒の住所を表します。
3.c：座標（料理）を含む配列。配列の各要素は、1つの料理の座標を表します。
4.cPrev：直前の座標（料理）を含む配列。配列の各要素は、1つの料理の座標を表します。
5. f：エージェントの現在の状態に対する適応度関数値
6. fPrev：エージェントの前の状態に対する適応度関数値

S_Candidate構造体にはInitメソッドがあり、coordsサイズ（最適化されるパラメータである座標の数）のすべての配列を初期化し、fとfPrevの初期値を「-DBL_MAX」に設定します。最初の反復では候補者の経験を比較するものは何もなく、誰も存在しないからです。

//——————————————————————————————————————————————————————————————————————————————
struct S_Candidate
{
  void Init (int coords)
  {
    ArrayResize (c,         coords);
    ArrayResize (cPrev,     coords);
    ArrayResize (raddr,     coords);
    ArrayResize (raddrPrev, coords);
    f        = -DBL_MAX;
    fPrev    = -DBL_MAX;
  }
  int    raddr     []; //restaurant address
  int    raddrPrev []; //previous restaurant address
  double c         []; //coordinates (dishes)
  double cPrev     []; //previous coordinates (dishes)
  double f;            //fitness
  double fPrev;        //previous fitness
};
//——————————————————————————————————————————————————————————————————————————————

以下を含むSDSアルゴリズムクラスを宣言します。

クラスのフィールド
cB：最適な座標を含む配列
fB：最適座標の適応度関数値
cands：最適な座標を見つけるための候補の配列
rangeMax：各座標の最大値を含む配列
rangeMin：各座標の最小値を含む配列
rangeStep：各座標の検索手順を含む配列

クラスのメソッド
Init：座標の数、母集団のサイズ、レストランの数、レストランを選ぶ確率などのアルゴリズムパラメータを初期化
Moving：アルゴリズムの手順を実行し、候補を新しい座標に移動
Revision：修正手順を実行し、最適な座標と適応度関数を更新
SeInDiSp：与えられた手順で、与えられた範囲の新しい座標を計算
RNDfromCI：与えられた間隔で乱数を生成

その他のクラスのフィールド
coords：座標の数
populationSize：母集団のサイズ
restNumb：レストランの数
probabRest：レストランを選ぶ確率
restSpace：レストラン空間
revision：改訂の必要性を示すフラグ

//——————————————————————————————————————————————————————————————————————————————
class C_AO_SDS
{
  //----------------------------------------------------------------------------
  public: double cB   [];       //best coordinates
  public: double fB;            //FF of the best coordinates
  public: S_Candidate cands []; //candidates

  public: double rangeMax  []; //maximum search range
  public: double rangeMin  []; //manimum search range
  public: double rangeStep []; //step search



  public: void Init (const int    coordinatesNumberP,   //coordinates number
                     const int    populationSizeP,      //population size
                     const int    restaurantsNumberP,   //restaurants number
                     const double probabRestP);         //probability restaurant choosing

  public: void Moving   ();
  public: void Revision ();

  //----------------------------------------------------------------------------
  private: int    coords;            //coordinates number
  private: int    populationSize;    //population size

  private: int    restNumb;          //restaurants number
  private: double probabRest;        //probability restaurant choosing
  private: double restSpace [];      //restaurants space

  private: bool   revision;

  private: double SeInDiSp  (double In, double InMin, double InMax, double Step);
  private: double RNDfromCI (double min, double max);
};
//——————————————————————————————————————————————————————————————————————————————

SDSアルゴリズムの初期化メソッドは、いくつかの変数と配列に初期値を設定することから始まります。

この方法の入力パラメータは以下の通りです。
coordinatesNumberP：座標の数（探索空間の次元）
opulationSizeP：母集団サイズ（候補者数）
restaurantsNumberP：レストランの数
probabRestP：レストランを選ぶ確率

まず、MathSrand関数を使用して乱数発生器をリセットし、現在のマイクロ秒の値を渡します。fB変数とrevision変数は、それぞれ初期値「-DBL_MAX」とfalseに初期化されます。
次に、coordinatesNumberPとopulationSizePの入力値が、cordsとopulationSizeの変数に代入されます。
restNumbとprobabRest変数はrestaurantsNumberPとprobabRestPの値で初期化されます。
coordsサイズのrestSpace配列は、ArrayResize関数を使用して作成されます。
次に、ArrayResize関数を使用して、opulationSizeサイズの配列candsを作成します。ループの中で、cands配列の各要素は、coordsパラメータを指定してInitメソッドを呼び出すことで初期化されます。
coordsサイズのrangeMax、rangeMin、rangeStep、cB配列もArrayResize関数を使用して作成されます。

//——————————————————————————————————————————————————————————————————————————————
void C_AO_SDS::Init (const int    coordinatesNumberP,   //coordinates number
                     const int    populationSizeP,      //population size
                     const int    restaurantsNumberP,   //restaurants number
                     const double probabRestP)          //probability restaurant choosing
{
  MathSrand ((int)GetMicrosecondCount ()); // reset of the generator
  fB       = -DBL_MAX;
  revision = false;

  coords         = coordinatesNumberP;
  populationSize = populationSizeP;

  restNumb   = restaurantsNumberP;
  probabRest = probabRestP;
  ArrayResize (restSpace, coords);

  ArrayResize (cands, populationSize);
  for (int i = 0; i < populationSize; i++) cands [i].Init (coords);

  ArrayResize (rangeMax,       coords);
  ArrayResize (rangeMin,       coords);
  ArrayResize (rangeStep,      coords);
  ArrayResize (cB,             coords);
}
//——————————————————————————————————————————————————————————————————————————————

Moving()メソッドは反復ごとに呼び出されますが、メソッドのメインロジックはrevisionフラグによって制御され、一度だけ実行されます。

関数の最初に、変数revisionが確認されます。falseの場合、変数と配列は初期化されます。
そして、空間上の点の座標に沿ってループが発生します。

このループの中で、restSpace[i]が計算されます。restSpace[i]は、各座標の区間の長さであり、範囲の最大値と最小値の差をrestNumbで割った値として定義されます。

次に、変数minとmaxが宣言され、特定のレストランの空間の値の範囲を決めるのに使用されます。

n変数とdish変数は、選択されたレストランの範囲内で無作為な値を決定するために使用されるように初期化されます。

次に、opulationSizeの母集団を通してループが実行され、その中で空間点の座標に対してループが実行されます。このループの中で、RNDfromCI()関数を使用して乱数nが生成され、restSpace配列のインデックスを決定するのに使用されます。結果の値nがrestNumb以上であれば、確率変数の一様分布を保証するために、restNumb-1が代入されます。最小値と最大値は、rangeMin、restSpace、nを用いて計算されます。

RNDfromCI()関数を使用して乱数'dish'を生成し、minからmaxまでの範囲（レストラン空間）とします。

次に、dishの値を使用して、SeInDiSp()関数によってc[i]の値を計算します。ここの関数では、rangeMin、rangeMax、rangeStepを使用して、最適化されたパラメータの正しい手順を確保します。

このアルゴリズムの結果、空間上の各点は、レストランの空間に応じて各座標の無作為な値を受け取り、料理の無作為な選択をシミュレーションします。

変数'revisionをtrueに設定することで、次にMoving()関数が呼ばれたとき、変数と配列は初期化されません。

//——————————————————————————————————————————————————————————————————————————————
void C_AO_SDS::Moving ()
{
  if (!revision)
  {
    for (int i = 0; i < coords; i++)
    {
      restSpace [i] = (rangeMax [i] - rangeMin [i]) / restNumb;
    }

    double min = 0.0;
    double max = 0.0;

    int    n   = 0;
    double dish = 0.0;

    for (int i = 0; i < populationSize; i++)
    {
      for (int c = 0; c < coords; c++)
      {
        n = (int)(RNDfromCI (0, restNumb));
        if (n >= restNumb) n = restNumb - 1;

        cands [i].raddr     [c] = n;
        cands [i].raddrPrev [c] = n;
        min = rangeMin [c] + restSpace [c] * n;
        max = min + restSpace [c];

        dish = RNDfromCI (min, max);

        cands [i].c [c] =  SeInDiSp (dish, rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }

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

SDSアルゴリズムのRevisionメソッドは、レストランとレストランの料理を選択するための基本的なロジックを実行します。これは、エージェントを移動するためのメインロジックがMovingメソッドに配置されていた前述のアルゴリズムでは典型的ではありませんが、アルゴリズムメソッドを呼び出す順序は同じであり、本連載の最初の記事で選択した概念に対応しています。アルゴリズムは以下の手順で構成されます。

1. fB適応度関数の最良の発見値と対応するcB座標セットを更新します。母集団内の各候補iについて比較がおこなわれ、f（関数推定値）の値がfBの現在のグローバル値より大きい場合、fBが更新され、iの候補からcBの最適グローバル座標セットにコピーされます。

2.各候補者の過去の評価とレストランセットを更新します。母集団内のiつ目候補について、fの値が以前のfPrevの値よりも大きい場合、fPrevが更新され、iつ目の候補のレストランcとraddrのセットが、対応する以前のcPrevとraddrPrevの値にコピーされます。

3.候補ごとに新しいレストランを選択します。母集団内の各i候補と各c座標に対して、0からopulationSizeの範囲で乱数nが選択されます。候補nのfPrevの値が候補iのfPrevの値より大きい場合、候補iのレストランraddrのセットは、候補nのraddrPrevの値で更新されます。そうでない場合は、乱数rndが0.0から1.0の範囲で生成されます。rndがprobabRestの確率より小さい場合、0からrestNumbの範囲内のn個の乱数が選択され、iつ目の候補のレストランraddrのセットがnの値で更新されます。そうでない場合、iつ目の候補者のレストランセットは変更されません。

4.各候補の新しい座標セットを生成します。最小値と最大値（minとmax）は、対応する座標のrangeMinとrestSpaceに基づいて、母集団の各i候補と各c座標について決定されます。次に、SeInDiSp関数を使用してminからmaxの範囲の乱数が生成され、その結果がiつ目の候補のcセットの対応するc座標に割り当てられます。

したがって、SDSアルゴリズムのRevisionメソッドは、候補の母集団を繰り返し、見つかった最良の値とレストランのセットを更新し、新しいレストランのセットを選択し、各候補の新しい座標のセットを生成します。

//——————————————————————————————————————————————————————————————————————————————
void C_AO_SDS::Revision ()
{
  //----------------------------------------------------------------------------
  for (int i = 0; i < populationSize; i++)
  {
    if (cands [i].f > fB)
    {
      fB = cands [i].f;
      ArrayCopy (cB, cands [i].c, 0, 0, WHOLE_ARRAY);
    }
  }

  //----------------------------------------------------------------------------
  double min = 0.0;
  double max = 0.0;
  double rnd = 0.0;
  int    n   = 0;

  for (int i = 0; i < populationSize; i++)
  {
    if (cands [i].f > cands [i].fPrev)
    {
      cands [i].fPrev = cands [i].f;
      ArrayCopy (cands [i].cPrev, cands [i].c, 0, 0, WHOLE_ARRAY);
      ArrayCopy (cands [i].raddrPrev, cands [i].raddr, 0, 0, WHOLE_ARRAY);
    }
  }

  for (int i = 0; i < populationSize; i++)
  {
    for (int c = 0; c < coords; c++)
    {
      n = (int)(RNDfromCI (0, populationSize));
      if (n >= populationSize) n = populationSize - 1;

      if (cands [n].fPrev > cands [i].fPrev)
      {
        cands [i].raddr [c] = cands [n].raddrPrev [c];
      }
      else
      {
        rnd = RNDfromCI (0.0, 1.0);

        if (rnd < probabRest)
        {
          n = (int)(RNDfromCI (0, restNumb));
          if (n >= restNumb) n = restNumb - 1;
          cands [i].raddr [c] = n;
        }
        else
        {
          cands [i].raddr [c] = cands [i].raddrPrev [c];
        }
      }

      min = rangeMin [c] + restSpace [c] * cands [i].raddr [c];
      max = min + restSpace [c];

      cands [i].c [c] = SeInDiSp (RNDfromCI (min, max), rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

3.テスト結果

次は、テストベンチでのSDSアルゴリズム動作の出力です。

C_AO_SDS:100;1000;0.1
=============================
5 Rastrigin's; Func runs 10000 result:80.64253803557851
Score:0.99921
25 Rastrigin's; Func runs 10000 result:79.00996143538204
Score:0.97898
500 Rastrigin's; Func runs 10000 result:54.31544686388126
Score:0.67300
=============================
5 Forest's; Func runs 10000 result:1.677891584229713
Score:0.94910
25 Forest's; Func runs 10000 result:1.4089003503272384
Score:0.79694
500 Forest's; Func runs 10000 result:0.2437939668372883
Score:0.13790
=============================
5 Megacity's; Func runs 10000 result:8.6
Score:0.71667
25 Megacity's; Func runs 10000 result:6.448
Score:0.53733
500 Megacity's; Func runs 10000 result:0.9551999999999999
Score:0.07960
=============================
All score:5.86873

アルゴリズム結果の出力を見るとすぐに、他のアルゴリズムと比較して信じられないほど高い結果に注目できます。詳細な比較は下表の通りです。

エージェントの動きを可視化する際のアルゴリズムの非定型的な挙動にご注目ください。エージェントの数は、適応度関数の丘の高さに比例して均等に分布しており、局所極値におけるクラスタリングの質の高さを示しています。アルゴリズムによって見逃される丘は1つもないようです。また、各反復において、アルゴリズムの収束がほぼ無段階に増加していることがわかりますが、これは極値で立ち往生する傾向が低いことを示しています。シャープな大域的極限を持つ最も複雑なForest関数でさえ、段階的収束は見られません。

rastrigin

Rastriginテスト関数のSDS

forest

Forestテスト関数のSDS

megacity

Megacityテスト関数のSDS

純粋なランダムウォークに基づく、このような非常にシンプルなアルゴリズムから驚くべき結果が出るとは思っていませんでした。SDSは、以前に検討されたすべてのアルゴリズムを（ほぼ13%）大幅に上回り、多くのテストで最高の結果を示しました（最大9のうち4つの1位）。唯一の分野は多変数のRastrigin関数で、この分野ではリーダー（EMアルゴリズム）が皆を大きく引き離しました。

非常に複雑なMegacity離散関数でも、SDSアルゴリズムはほとんどどこにも引っかかることなく、優れたパフォーマンスを発揮します。ForestとMegacityの1000変数を使ったテストでSDSを上回ったのは、Growing Trees (SSG)アルゴリズムだけです。

#	AO	詳細	Rastrigin			Rastrigin最終	Forest			Forest最終	Megacity（離散）			Megacity最終	最終結果
#	AO	詳細	10 p (5 F)	50 p (25 F)	1000 p (500 F)	Rastrigin最終	10 p (5 F)	50 p (25 F)	1000 p (500 F)	Forest最終	10 p (5 F)	50 p (25 F)	1000 p (500 F)	Megacity最終	最終結果
1	SDS	確率拡散探索	0.99737	1.00000	0.63507	2.63244	0.96893	1.00000	0.95092	2.91985	1.00000	1.00000	0.72149	2.72149	100.000
2	SSG	苗木の播種と育成	1.00000	0.95313	0.55665	2.50978	0.72740	0.69680	1.00000	2.42421	0.69612	0.65726	1.00000	2.35338	87.489
3	HS	ハーモニー検索	0.99676	0.90817	0.48178	2.38670	1.00000	0.72930	0.44806	2.17736	0.91159	0.76446	0.41537	2.09142	79.474
4	ACOm	蟻コロニー最適化M	0.34611	0.17142	0.17044	0.68797	0.86888	0.73719	0.77362	2.37968	0.91159	0.67983	0.05606	1.64749	54.863
5	IWO	侵入雑草最適化	0.95828	0.63939	0.29807	1.89575	0.70773	0.34168	0.31773	1.36714	0.72927	0.32158	0.33289	1.38375	53.994
6	MEC	mind evolutionary computation	0.99270	0.48648	0.22800	1.70718	0.60762	0.29973	0.25459	1.16194	0.85083	0.31594	0.26170	1.42847	49.567
7	COAm	カッコウ最適化アルゴリズムM	0.92400	0.44601	0.26004	1.63006	0.58378	0.25090	0.16526	0.99994	0.66298	0.25246	0.17083	1.08627	42.193
8	FAm	ホタルアルゴリズムM	0.59825	0.32387	0.17135	1.09348	0.51073	0.31182	0.49790	1.32045	0.31491	0.21438	0.35258	0.88188	36.860
9	ABC	人工蜂コロニー	0.78170	0.31182	0.20822	1.30174	0.53837	0.15816	0.13344	0.82998	0.51381	0.20311	0.13926	0.85617	32.954
10	BA	コウモリアルゴリズム	0.40526	0.60773	0.84451	1.85750	0.20841	0.12884	0.25989	0.59714	0.27073	0.07616	0.17371	0.52060	32.794
11	GSA	重力探索法	0.70167	0.43098	0.00000	1.13265	0.31660	0.26845	0.33204	0.91710	0.54144	0.26797	0.00000	0.80941	31.322
12	BFO	細菌採餌の最適化	0.67203	0.29511	0.11813	1.08528	0.39702	0.19626	0.20652	0.79980	0.47514	0.25388	0.18932	0.91834	30.615
13	EM	電磁気学的アルゴリズム	0.12235	0.44109	1.00000	1.56344	0.00000	0.02578	0.34880	0.37458	0.00000	0.00000	0.10924	0.10924	21.024
14	SFL	ShuffledFrog-Leaping	0.40072	0.22627	0.26548	0.89247	0.20153	0.03057	0.02652	0.25862	0.24862	0.04231	0.06639	0.35732	14.189
15	MA	モンキーアルゴリズム	0.33192	0.31883	0.14644	0.79719	0.10012	0.05817	0.08932	0.24762	0.19889	0.03243	0.10720	0.33853	12.603
16	FSS	魚群検索	0.46812	0.24149	0.11302	0.82264	0.12840	0.03696	0.06516	0.23052	0.15471	0.03666	0.08283	0.27420	11.893
17	PSO	粒子群最適化	0.20449	0.07816	0.07160	0.35425	0.18895	0.07730	0.21738	0.48363	0.21547	0.04513	0.01957	0.28016	9.238
18	RND	ランダム	0.16826	0.09287	0.08019	0.34132	0.13496	0.03546	0.04715	0.21757	0.15471	0.02962	0.04922	0.23354	5.108
19	GWO	灰色オオカミオプティマイザ	0.00000	0.00000	0.02256	0.02256	0.06570	0.00000	0.00000	0.06570	0.29834	0.05640	0.02557	0.38031	1.000

まとめ

SDSアルゴリズムは、与えられた関数の大域的最適解を見つけるために無作為なサンプルを使用する効率的な最適化手法です。
この記事では、SDSアルゴリズムの基本的な動作原理を紹介しました。これは、分割された探索空間内の点を無作為に選択するという考え方に基づいています。テストの結果、SDSは多数の局所極値を持つ複雑な関数でも大域的最適値を求めることができ、優れた収束性を示しました。SDSアルゴリズムの利点の1つは、そのシンプルさと実装の容易さです。計算量が少なくて済み、様々なタイプの最適化問題に適用できます。

個々のアルゴリズムの長所と短所をより視覚的に表現するために、上の表は図3のカラースケールを使用して表すことができます。

図3：関連テストによるアルゴリズムのカラーグラデーション

アルゴリズムのテスト結果のヒストグラムを以下に示します（0から100までのスケールで、多ければ多いほど良い。アーカイブには、この記事で説明した方法で格付け表を計算するスクリプトがある）。

チャート

図4：テストアルゴリズムの最終結果のヒストグラム

SDSアルゴリズムの長所と短所：

長所
1. 外部パラメータ数が最小
2.様々な問題を高い効率で解決
3.計算リソースへの負荷が低い
4.実装が容易
5.くっつきにくい
6.平滑離散関数と複雑な離散関数の両方で有望な結果
7.収束性が高い

短所
1. なし

各記事には、過去の記事のアルゴリズムコードを最新版に更新したアーカイブが用意されています。しかし、基準のアルゴリズムの記述における絶対的な正確さについては責任を負いませんのでご注意ください。私はしばしば、自分の経験や個人的な意見に基づいて、自分なりのアイデアや改良を加えます。記事に示された結論と判断は、実験結果に基づいています。

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

添付されたファイル |

ZIPをダウンロード

19_The_world_of_AO_SDS.zip (414.5 KB)

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

この著者による他の記事

ディスカッションに移動

リプレイシステムの開発（第31回）：エキスパートアドバイザープロジェクト - C_Mouseクラス(V)

リプレイ/シミュレーションの終了まで残り時間を表示できるタイマーが必要です。これは一見、シンプルで迅速な解決策に見えるかもしれません。多くの人は、取引サーバーが使用しているのと同じシステムを適応して使用しようとするだけです。しかし、この解決策を考えるとき、多くの人が考慮しないことがあります。リプレイでは、そしてシミュレーションではなおさら、時計の動きは異なるということです。こうしたことが、このようなシステムの構築を複雑にしています。

リプレイシステムの開発（第30回）：エキスパートアドバイザープロジェクト - C_Mouseクラス(IV)

今日は、プログラマーとしての職業生活のさまざまな段階で非常に役立つテクニックを学びます。多くの場合、制限されているのはプラットフォーム自体ではなく、制限について話す人の知識です。この記事では、常識と創造性があれば、クレイジーなプログラムなどを作成することなく、MetaTrader 5 プラットフォームをより面白くて多用途にし、シンプルでありながら安全で信頼性の高いコードを作成できることを説明します。創造力を駆使して、ソースコードを1行も削除したり追加したりすることなく、既存のコードを変更します。

リプレイシステムの開発（第32回）：受注システム(I)

これまで開発してきたものの中で、このシステムが最も複雑であることは、おそらく皆さんもお気づきでしょうし、最終的にはご納得いただけると思います。あとは非常に単純なことですが、取引サーバーの動作をシミュレーションするシステムを作る必要があります。取引サーバーの操作方法を正確に実装する必要性は、当然のことのように思えます。少なくとも言葉ではです。ただし、リプレイ/シミュレーションシステムのユーザーにとって、すべてがシームレスで透明なものとなるようにする必要があります。

リプレイシステムの開発（第29回）：エキスパートアドバイザープロジェクト - C_Mouseクラス(III)

C_Mouseクラスを改良した後は、分析のためのまったく新しいフレームワークを作るためのクラスを作ることに集中しましょう。この新しいクラスを作るのに、継承やポリモーフィズムは使用しません。その代わりに、価格線に新しいオブジェクトを追加します。それがこの記事でやろうとしていることです。次回は、分析結果を変更する方法について見るつもりです。これらはすべて、C_Mouseクラスのコードを変更することなくおこなわれます。実際には、継承やポリモーフィズムを使用すれば、もっと簡単に実現できるでしょう。しかし、同じ結果を得る方法は他にもあります。