母集団最適化アルゴリズム

MetaTrader 5 — 例 | 8 12月 2022, 14:11

234

Andrey Dik

「極大極小の法則が現れないものが
宇宙で起ることはない」
レオンハルト・オイラー（18世紀）

内容:

1.歴史的な視点

最適化アルゴリズムとは、関数が最小値または最大値になるような、定義域の極限点を見つけることができるアルゴリズムです。

古代ギリシャの識者たちは、すでに次を知っていました。

- 同じ周囲長を持つすべての図形の中で、円は最も大きな面積を持つ

- 同じ辺の数と同じ周囲長を持つすべての多角形の中で、正多角形は最も大きな面積を持つ

- 同じ面積を持つすべての立体図形の中で、球体は最も大きな体積を持つ

変分解を持つ最初の問題も、同じ時期に提案されました。伝説によると、これは紀元前825年頃の出来事だといいます。ティアのフェニキアの王の妹であるディドは、地中海の南岸に移り住み、地元の部族に牛の皮で覆うことができるだけの土地をくれるように頼みました。現地の人が彼女に皮を与えました。機転を利かせた少女は、それを細いベルト状に切り、結んでロープにしました。そして、このロープで沿岸の土地をカバーし、そこにカルタゴの都市を築きました。

問題は、与えられた長さの閉じた平面曲線の中から、最も効率よく、最大の表面積をカバーする曲線を見つけることにあります。この問題における最大面積は、半円に外接する面積で表されます。

ディドナ1

ここで、地中海の古代文化、異端審問による弾圧、中世の偽医療、そしてルネサンスの自由な思想と新しい理論までの歴史の大部分を飛ばしてみましょう。1696年6月、ヨハン・ベルヌーイは『Acta Eruditorum』の読者に向けて次のような文章を発表しています。「私、ヨハン・ベルヌーイは、世界で最も優秀な数学者たちに語りかけます。知的な人々にとって、正直で困難な問題ほど魅力的なものはありません。その可能な解決策は、名声を与え、永遠の記念碑として残るでしょう。パスカルやフェルマーに倣って、私は現代の最も優れた数学者たちの前に、彼らの方法と知性の強さを試すような問題を置き、科学界全体から感謝されることを望んでいます。もし、誰かが提案した問題の解決策を私に伝えたら、私はその人を賞賛に値すると公言するでしょう」。

以下は、ヨハン・ベルヌーイの最速降下曲線問題です。

「鉛直面に2点A、Bがあるとき、重力のみ作用する点がAから出発してBに最短時間で到達する曲線は何か」驚くべきことに、ガリレオはベルヌーイの発表よりずっと前の1638年に同様の問題を解こうとしたのです。答え：ある点から別の点への、最も速い道は、一見したところ最短の道ではなく、直線でもなく、曲線、つまり各点で曲率を決めるサイクロイドです。

ブラキストクローネ9

最速降下曲線

ニュートンを含め、他のすべての解法は（当時は明らかにされていませんでしたが）、各点での勾配を求めることに基づいています。アイザック・ニュートンが提案した解法の背後にある方法は、変分計算の基礎を形成しています。変分計算の方法は通常、最適性基準が汎関数の形で提示され、その解が未知の関数である問題を解決する際に適用されます。このような問題は、通常、パラメータが分散したプロセスの静的最適化、あるいは動的最適化の問題で発生します。

変分問題における一次の極限条件は、レオンハルト・オイラーとジョゼフ＝ルイ・ラグランジュによって得られました（オイラー＝ラグランジュ方程式）。これらの方程式は、最適化問題に広く用いられ、最小作用の原理とともに、力学の軌道計算に応用されています。しかし間もなく、これらの方程式の解が必ずしも実の極限を与えるとは限らないことが明らかになり、その発見を保証する十分な条件が求められるようになりました。その後も研究は続けられ、ルジャンドルとヤコビ、そして後者の弟子であるヘッセによって2次の極限条件が導き出されました。変分計算における解の存在の問題は、19世紀後半にワイエルシュトラスによって初めて提起されました。

18世紀後半になると、問題に対する最適解の探索が、最適化の数学的基礎と原理を形成するようになりました。残念ながら、最適化手法は、数学的手法を実用化するためには膨大な計算資源を必要とするため、20世紀後半までは、実は科学技術の多くの分野でほとんど利用されていなかったのです。現代は新しいコンピュータ技術の登場により、複雑な最適化手法の実装が可能になり、多種多様なアルゴリズムが利用できるようになりました。

1980年代には、自然界から借用したモデル化によって、確率的最適化アルゴリズムのクラスが集中的に開発されるようになりました。

2.OAの分類

クラス

分類AO

取引システムの最適化において、最もエキサイティングなのは、メタヒューリスティック最適化アルゴリズムです。最適化される関数の式の知識は必要ありません。大域的最適解への収束性は証明されていないが、ほとんどの場合、かなり良い解が得られることが実験的に確立されており、多くの問題でこれで十分です。

自然界から借用したモデルとして、多くのOAが登場しました。このようなモデルは、行動、群れ、集団とも呼ばれ、例えば鳥の群れの行動（粒子群アルゴリズム）、蟻のコロニーの行動原理（蟻アルゴリズム）などがあります。

ポピュレーションアルゴリズムは、最適化問題を解くために複数の選択肢を同時に扱うもので、問題を解く際に探索領域が1つの候補しか進化しない運動軌道に基づく古典的なアルゴリズムに代わるものです。

3.収束と収束率、収束安定性、最適化アルゴリズムの拡張性

効率、速度、収束、および問題条件とアルゴリズムパラメータの影響については、各アルゴリズムの実装と最適化問題のクラスごとに慎重に分析する必要があります。

3.1) 収束と収束率

反復アルゴリズムが有限回のステップで目的関数の最適値に到達する、またはそれに十分近づく性質です。上のスクリーンショットの右側には、計算されたテスト関数がもたらす結果を反復して構築したグラフが表示されています。この2つの画像から、収束は関数の曲面の複雑さに影響されると結論付けることができます。複雑であればあるほど、大域的な極限を見つけるのは難しくなります。

アルゴリズムの収束率は、最適化アルゴリズムの品質を示す最も重要な指標の1つであり、最適化手法の大きな特徴の1つです。あるアルゴリズムが他のアルゴリズムより速いと聞いたとき、ほとんどの場合、これは収束速度を意味します。このパラメータは，結果が大域的極限に近く，かつ高速に得られるほど（つまりアルゴリズムの反復が早いほど）高くなります。なお、通常、手法の収束率は2次式を超えることはありません。まれに、この手法の収束率は3乗になることがあります。

3.2) 収束安定性

結果を得るために必要な反復回数は、アルゴリズム自体の探索能力だけでなく、対象となる関数にも依存します。関数が曲面の高い複雑性（鋭い曲がり、離散性、不連続性の存在）によって特徴付けられる場合、アルゴリズムは不安定になり、許容できる精度を全く提供できないことが判明するかもしれません。また、収束の安定性は、何度か連続してテストをおこなったときの最適化結果の再現性として理解することができます。その結果、値のばらつきが大きい場合は、アルゴリズムの安定性が低いと考えられます。

3.3) 最適化アルゴリズムの拡張性

収束7 収束6

最適化アルゴリズムの拡張性とは、問題の次元が大きくなっても収束を維持できる能力のことです。つまり、最適化関数の変数数を増やしても、実用上問題ないレベルに収束する必要があります。探索最適化のポピュレーションアルゴリズムは、特に高次元で形式化されていない問題を解く場合、古典的なアルゴリズムと比較して否定できない利点があります。このような条件下では、母集団アルゴリズムは、最適化される関数の大域的極限を高い確率で局在化させることができます。

滑らかで単峰性の最適化関数の場合、一般に母集団アルゴリズムは古典的な勾配法よりも効率が悪くなります。また、母集団アルゴリズムの欠点として、自由度（チューニングパラメータの数）に効率が強く依存することが挙げられます。ほとんどのアルゴリズムで自由度は非常に多くなります。

4.テスト関数、複合OA評価基準の構築

最適化アルゴリズムをテストし、比較するための一般に認められた方法論はありません。ただし、研究者によって提案されたテスト関数は、年代によって多数存在します。第1稿を発表する前に作成した関数を使用することにします。これらの関数は、ターミナルフォルダ\MQL5\Experts\Examples\Math 3D\Functions.mqh and \MQL5\Experts\Examples\Math 3D Morpher\Functions.mqhにあります。これらの関数は、OAテストの複雑さの基準をすべて満たしています。さらに、Forest関数とMegacity関数を開発し、より包括的にOA検索関数を検討できるようになりました。

以下はSkinテスト関数です。

この関数は領域全体が滑らかで、局所的な最大値/最小値が無意味に多く異なり（収束の罠）、大域的極限に達しないアルゴリズムが行き詰まる原因となっています。

Skin

以下はForestテスト関数です。

この関数は、その点に微分を持たないいくつかの最大値を表しています。そのため、対象関数の滑らかさにロバスト性が決定的に依存する最適化アルゴリズムでは、困難なことが判明するかもしれません。

Forest

以下はMegacityテスト関数です。

「領域」を形成する離散関数 (変数を変更しても、関数の値が大幅に変化しない場合)です。そのため、勾配を必要とするアルゴリズムには難点があります。

Chinatown

Megacity

5.テストスタンド

最適化アルゴリズムの包括的な比較のために、一般的な評価基準の作成が試みられました。このアイデアの複雑さは、対応する問題のクラスに対してそれぞれのアルゴリズムが独自の方法で優れているため、アルゴリズムを比較する方法が明確でないことにあります。例えば、あるアルゴリズムは収束は早いが拡張性が悪く、別のアルゴリズムは拡張性は良いが不安定です。

収束：収束を調べるために、上で紹介した3つの関数を使用します。その最大値と最小値を0.0（最悪の結果）から1.0（最良の結果）の範囲に変換し、異なるタイプの問題に対するアルゴリズムの収束を確保する能力を評価することができるようになります。
収束率：アルゴリズムの最良の結果は、テストされた関数の1000回目と1万回目の実行で測定されています。こうして、OAの収束の速さを見ることができます。収束が早いほど、収束グラフは最大値に向かって湾曲していくことになります。
安定性：各関数について最適化を5回実行し，0.0から1.0までの範囲の平均値を計算します。アルゴリズムによっては実行ごとに結果が大きく異なることがあるため、これは必要なことです。5つのテストそれぞれで収束性が高いほど、安定性が高いと言えます。
拡張性：OAによっては、例えば2つ以下の少ない数の変数を持つ関数でしか実用的な結果を示すことができないものもあります。さらに、1000個の変数を持つ関数を扱うことができるアルゴリズムもあります。このような最適化アルゴリズムは、ニューラルネットワークのOAとして利用することができます。

テスト関数を使うときの利便性を考えて、親クラスと、将来対応するテスト関数の子クラスのオブジェクトを選択できるような列挙子を書いておきましょう。

//——————————————————————————————————————————————————————————————————————————————
class C_Function
{
  public: //====================================================================
  double CalcFunc (double &args [], //function arguments
                   int     amount)  //amount of runs functions
  {
    double x, y;
    double sum = 0.0;
    for (int i = 0; i < amount; i++)
    {
      x = args [i * 2];
      y = args [i * 2 + 1];

      sum += Core (x, y);
    }

    sum /= amount;

    return sum;
  }
  double GetMinArg () { return minArg;}
  double GetMaxArg () { return maxArg;}
  double GetMinFun () { return minFun;}
  double GetMaxFun () { return maxFun;}
  string GetNamFun () { return fuName;}

  protected: //==================================================================
  void SetMinArg (double min) { minArg = min;}
  void SetMaxArg (double max) { maxArg = max;}
  void SetMinFun (double min) { minFun = min;}
  void SetMaxFun (double max) { maxFun = max;}
  void SetNamFun (string nam) { fuName = nam;}

  private: //====================================================================
  virtual double Core (double x, double y) { return 0.0;}
  
  double minArg;
  double maxArg;
  double minFun;
  double maxFun;
  string fuName;
};
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
enum EFunc
{
  Skin,
  Forest,
  Megacity,
  
};
C_Function *SelectFunction (EFunc f)
{
  C_Function *func;
  switch (f)
  {
    case  Skin:
      func = new C_Skin (); return (GetPointer (func));
    case  Forest:
      func = new C_Forest (); return (GetPointer (func));
    case  Megacity:
      func = new C_Megacity (); return (GetPointer (func));
    
    default:
      func = new C_Skin (); return (GetPointer (func));
  }
}
//——————————————————————————————————————————————————————————————————————————————

そうすると、子クラスは次のようになります。

//——————————————————————————————————————————————————————————————————————————————
class C_Skin : public C_Function
{
  public: //===================================================================
  C_Skin ()
  {
    SetNamFun ("Skin");
    SetMinArg (-5.0);
    SetMaxArg (5.0);
    SetMinFun (-4.3182);  //[x=3.07021;y=3.315935] 1 point
    SetMaxFun (14.0606);  //[x=-3.315699;y=-3.072485] 1 point
  }

  private: //===================================================================
  double Core (double x, double y)
  {
    double a1=2*x*x;
    double a2=2*y*y;
    double b1=MathCos(a1)-1.1;
    b1=b1*b1;
    double c1=MathSin(0.5*x)-1.2;
    c1=c1*c1;
    double d1=MathCos(a2)-1.1;
    d1=d1*d1;
    double e1=MathSin(0.5*y)-1.2;
    e1=e1*e1;

   double res=b1+c1-d1+e1;
   return(res);
  }
};
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
class C_Forest : public C_Function
{
  public: //===================================================================
  C_Forest ()
  {
    SetNamFun ("Forest");
    SetMinArg (-50.0);
    SetMaxArg (-18.0);
    SetMinFun (0.0);             //many points
    SetMaxFun (15.95123239744);  //[x=-25.132741228718345;y=-32.55751918948773] 1 point
  }

  private: //===================================================================
  double Core (double x, double y)
  {
    double a = MathSin (MathSqrt (MathAbs (x - 1.13) + MathAbs (y - 2.0)));
    double b = MathCos (MathSqrt (MathAbs (MathSin (x))) + MathSqrt (MathAbs (MathSin (y - 2.0))));
    double f = a + b;

    double res = MathPow (f, 4);
    if (res < 0.0) res = 0.0;
    return (res);
  }
};
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
class C_Megacity : public C_Function
{
  public: //===================================================================
  C_Megacity ()
  {
    SetNamFun ("Megacity");
    SetMinArg (-15.0);
    SetMaxArg (15.0);
    SetMinFun (0.0);   //many points
    SetMaxFun (15.0);  //[x=`3.16;y=1.990] 1 point
  }

  private: //===================================================================
  double Core (double x, double y)
  {
    double a = MathSin (MathSqrt (MathAbs (x - 1.13) + MathAbs (y - 2.0)));
    double b = MathCos (MathSqrt (MathAbs (MathSin (x))) + MathSqrt (MathAbs (MathSin (y - 2.0))));
    double f = a + b;

    double res = floor (MathPow (f, 4));
    return (res);
  }
};
//——————————————————————————————————————————————————————————————————————————————

テストスタンドで得られたOAテストの結果の妥当性を確認するために、X関数とY関数をStepのステップサイズで列挙するスクリプトを使用することができます。ステップの大きさをあまり小さくすると、計算に時間がかかりすぎるため、ステップの選択には注意が必要です。例えば、Skin関数の引数の範囲は[-5;5]です。X軸に沿って0.00001のステップを使用すれば、ステップ数は(-5))/0.00001=1,000,000（百万）になります。Ｙ軸に沿って同じステップを使用すると、各点における値を計算するテスト関数の実行回数の合計は、1,000,000 * 1,000,000 = 1,000,000,000(=10^12=10億）に等しいことになります。

わずか1万ステップ（MetaTrader 5のオプティマイザではおよそこの値が使われる）で最大値を求めなければいけないため、OAがいかに大変な作業であるかを理解する必要があります。なお、この計算は2変数関数に対しておこなわれており、テストに使用される変数の最大数は1000です。

この記事のアルゴリズムテストでは、0.0!または対応するOAの特定の実装で可能な最小のステップを使用していることに留意してください。

//——————————————————————————————————————————————————————————————————————————————
input EFunc  Function          = Skin;
input double Step              = 0.01;

//——————————————————————————————————————————————————————————————————————————————
void OnStart ()
{
  C_Function *TestFunc = SelectFunction (Function);

  double argMin = TestFunc.GetMinArg ();
  double argMax = TestFunc.GetMaxArg ();

  double maxFuncValue = 0;
  double xMaxFunc     = 0.0;
  double yMaxFunc     = 0.0;
  
  double minFuncValue = 0;
  double xMinFunc     = 0.0;
  double yMinFunc     = 0.0;
  
  double fValue       = 0.0;

  double arg [2];

  arg [0] = argMin;
  arg [1] = argMin;

  long cnt = 0;

  while (arg [1] <= argMax && !IsStopped ())
  {
    arg [0] = argMin;

    while (arg [0] <= argMax && !IsStopped ())
    {
      cnt++;

      fValue = TestFunc.CalcFunc (arg, 1);

      if (fValue > maxFuncValue)
      {
        maxFuncValue = fValue;
        xMaxFunc = arg [0];
        yMaxFunc = arg [1];
      }
      if (fValue < minFuncValue)
      {
        minFuncValue = fValue;
        xMinFunc = arg [0];
        yMinFunc = arg [1];
      }

      arg [0] += Step;
      
      if (cnt == 1)
      {
       maxFuncValue = fValue;
       minFuncValue = fValue;
      }
    }

    arg [1] += Step;
  }
  
  Print ("======", TestFunc.GetNamFun (), ", launch counter: ", cnt);
  Print ("MaxFuncValue: ", DoubleToString (maxFuncValue, 16), " X: ", DoubleToString (xMaxFunc, 16), " Y: ", DoubleToString (yMaxFunc, 16));
  Print ("MinFuncValue: ", DoubleToString (minFuncValue, 16), " X: ", DoubleToString (xMinFunc, 16), " Y: ", DoubleToString (yMinFunc, 16));
         
  delete TestFunc;
}

//——————————————————————————————————————————————————————————————————————————————

テストスタンドを書いてみましょう。

#include <Canvas\Canvas.mqh>
#include <\Math\Functions.mqh>
#include "AO_RND.mqh"

//——————————————————————————————————————————————————————————————————————————————
input int    Population_P       = 50;
input double ArgumentStep_P     = 0.0;
input int    Test1FuncRuns_P    = 1;
input int    Test2FuncRuns_P    = 20;
input int    Test3FuncRuns_P    = 500;
input int    Measur1FuncValue_P = 1000;
input int    Measur2FuncValue_P = 10000;
input int    NumberRepetTest_P  = 5;
input int    RenderSleepMsc_P   = 0;

//——————————————————————————————————————————————————————————————————————————————
int WidthMonitor = 750;  //monitor screen width
int HeighMonitor = 375;  //monitor screen height

int WidthScrFunc = 375 - 2;  //test function screen width
int HeighScrFunc = 375 - 2;  //test function screen height

CCanvas Canvas;  //drawing table
C_AO_RND AO;     //AO object

C_Skin       SkiF;
C_Forest     ForF;
C_Megacity  ChiF;

struct S_CLR
{
    color clr [];
};

S_CLR FunctScrin []; //two-dimensional matrix of colors
double ScoreAll = 0.0;

//——————————————————————————————————————————————————————————————————————————————
void OnStart ()
{
  //creating a table -----------------------------------------------------------
  string canvasName = "AO_Test_Func_Canvas";
  if (!Canvas.CreateBitmapLabel (canvasName, 5, 30, WidthMonitor, HeighMonitor, COLOR_FORMAT_ARGB_RAW))
  {
    Print ("Error creating Canvas: ", GetLastError ());
    return;
  }
  ObjectSetInteger (0, canvasName, OBJPROP_HIDDEN, false);
  ObjectSetInteger (0, canvasName, OBJPROP_SELECTABLE, true);

  ArrayResize (FunctScrin, HeighScrFunc);
  for (int i = 0; i < HeighScrFunc; i++)
  {
    ArrayResize (FunctScrin [i].clr, HeighScrFunc);
  }
  
  //============================================================================
  //Test Skin###################################################################
  Print ("=============================");
  CanvasErase ();
  FuncTests (SkiF, Test1FuncRuns_P, SkiF.GetMinFun (), SkiF.GetMaxFun (), -3.315699, -3.072485, clrLime);
  FuncTests (SkiF, Test2FuncRuns_P, SkiF.GetMinFun (), SkiF.GetMaxFun (), -3.315699, -3.072485, clrAqua);
  FuncTests (SkiF, Test3FuncRuns_P, SkiF.GetMinFun (), SkiF.GetMaxFun (), -3.315699, -3.072485, clrOrangeRed);
  
  //Test Forest#################################################################
  Print ("=============================");
  CanvasErase ();
  FuncTests (ForF, Test1FuncRuns_P, ForF.GetMinFun (), ForF.GetMaxFun (), -25.132741228718345, -32.55751918948773, clrLime);
  FuncTests (ForF, Test2FuncRuns_P, ForF.GetMinFun (), ForF.GetMaxFun (), -25.132741228718345, -32.55751918948773, clrAqua);
  FuncTests (ForF, Test3FuncRuns_P, ForF.GetMinFun (), ForF.GetMaxFun (), -25.132741228718345, -32.55751918948773, clrOrangeRed);
  
  //Test Megacity#############################################################
  Print ("=============================");
  CanvasErase ();
  FuncTests (ChiF, Test1FuncRuns_P, ChiF.GetMinFun (), ChiF.GetMaxFun (), 3.16, 1.990, clrLime);
  FuncTests (ChiF, Test2FuncRuns_P, ChiF.GetMinFun (), ChiF.GetMaxFun (), 3.16, 1.990, clrAqua);
  FuncTests (ChiF, Test3FuncRuns_P, ChiF.GetMinFun (), ChiF.GetMaxFun (), 3.16, 1.990, clrOrangeRed);
  
  Print ("All score for C_AO_RND: ", ScoreAll / 18.0);
}
//——————————————————————————————————————————————————————————————————————————————

void CanvasErase ()
{
  Canvas.Erase (XRGB (0, 0, 0));
  Canvas.FillRectangle (1,                1, HeighMonitor - 2, HeighMonitor - 2, COLOR2RGB (clrWhite));
  Canvas.FillRectangle (HeighMonitor + 1, 1, WidthMonitor - 2, HeighMonitor - 2, COLOR2RGB (clrWhite));
}

//——————————————————————————————————————————————————————————————————————————————
void FuncTests (C_Function &f,
                int        funcCount,
                double     minFuncVal,
                double     maxFuncVal,
                double     xBest,
                double     yBest,
                color      clrConv)
{
  DrawFunctionGraph (f.GetMinArg (), f.GetMaxArg (), minFuncVal, maxFuncVal, f);
  SendGraphToCanvas (1, 1);
  int x = (int)Scale (xBest, f.GetMinArg (), f.GetMaxArg (), 0, WidthScrFunc - 1, false);
  int y = (int)Scale (yBest, f.GetMinArg (), f.GetMaxArg (), 0, HeighScrFunc - 1, false);
  Canvas.Circle (x + 1, y + 1, 10, COLOR2RGB (clrBlack));
  Canvas.Circle (x + 1, y + 1, 11, COLOR2RGB (clrBlack));
  Canvas.Update ();
  Sleep (1000);

  int xConv = 0.0;
  int yConv = 0.0;

  int EpochCmidl = 0;
  int EpochCount = 0;

  double aveMid = 0.0;
  double aveEnd = 0.0;

  //----------------------------------------------------------------------------
  for (int test = 0; test < NumberRepetTest_P; test++)
  {
    InitAO (funcCount * 2, f.GetMaxArg (), f.GetMinArg (), ArgumentStep_P);

    EpochCmidl = Measur1FuncValue_P / (ArraySize (AO.S_Colony));
    EpochCount = Measur2FuncValue_P / (ArraySize (AO.S_Colony));

    // Optimization-------------------------------------------------------------
    AO.F_EpochReset ();


    for (int epochCNT = 1; epochCNT <= EpochCount && !IsStopped (); epochCNT++)
    {
      AO.F_Preparation ();

      for (int set = 0; set < ArraySize (AO.S_Colony); set++)
      {
        AO.A_FFcol [set] = f.CalcFunc (AO.S_Colony [set].args, funcCount);
      }

      AO.F_Sorting ();

      if (epochCNT == EpochCmidl) aveMid += AO.A_FFpop [0];

      SendGraphToCanvas  (1, 1);

      //draw a population on canvas
      for (int i = 0; i < ArraySize (AO.S_Population); i++)
      {
        if (i > 0) PointDr (AO.S_Population [i].args, f.GetMinArg (), f.GetMaxArg (), clrWhite, 1, 1, funcCount);
      }
      PointDr (AO.S_Population [0].args, f.GetMinArg (), f.GetMaxArg (), clrBlack, 1, 1, funcCount);

      Canvas.Circle (x + 1, y + 1, 10, COLOR2RGB (clrBlack));
      Canvas.Circle (x + 1, y + 1, 11, COLOR2RGB (clrBlack));

      xConv = (int)Scale (epochCNT,       1,          EpochCount, 2, WidthScrFunc - 2, false);
      yConv = (int)Scale (AO.A_FFpop [0], minFuncVal, maxFuncVal, 1, HeighScrFunc - 2, true);

      Canvas.FillCircle (xConv + HeighMonitor + 1, yConv + 1, 1, COLOR2RGB (clrConv));

      Canvas.Update ();
      Sleep (RenderSleepMsc_P);
    }

    aveEnd += AO.A_FFpop [0];

    Sleep (1000);
  }

  aveMid /= (double)NumberRepetTest_P;
  aveEnd /= (double)NumberRepetTest_P;

  double score1 = Scale (aveMid, minFuncVal, maxFuncVal, 0.0, 1.0, false);
  double score2 = Scale (aveEnd, minFuncVal, maxFuncVal, 0.0, 1.0, false);
  
  ScoreAll += score1 + score2;

  Print (funcCount, " ", f.GetNamFun (), "'s; Func runs ", Measur1FuncValue_P, " result: ", aveMid, "; Func runs ", Measur2FuncValue_P, " result: ", aveEnd);
  Print ("Score1: ", DoubleToString (score1, 5), "; Score2: ", DoubleToString (score2, 5));
}
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
void InitAO (const int    params,  //amount of the optimized arguments
             const double max,     //maximum of the optimized argument
             const double min,     //minimum of the optimized argument
             const double step)    //step of the optimized argument
{
  AO.F_Init (params, Population_P);
  for (int idx = 0; idx < params; idx++)
  {
    AO.A_RangeMax  [idx] = max;
    AO.A_RangeMin  [idx] = min;
    AO.A_RangeStep [idx] = step;
  }
}
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
void PointDr (double &args [], double Min, double Max, color clr, int shiftX, int shiftY, int count)
{
  double x = 0.0;
  double y = 0.0;
  
  double xAve = 0.0;
  double yAve = 0.0;
  
  int width  = 0;
  int height = 0;
  
  color clrF = clrNONE;
  
  for (int i = 0; i < count; i++)
  {
    xAve += args [i * 2];
    yAve += args [i * 2 + 1];
       
    x = args [i * 2];
    y = args [i * 2 + 1];
    
    width  = (int)Scale (x, Min, Max, 0, WidthScrFunc - 1, false);
    height = (int)Scale (y, Min, Max, 0, HeighScrFunc - 1, false);
    
    clrF = DoubleToColor (i, 0, count - 1, 0, 360);
    Canvas.FillCircle (width + shiftX, height + shiftY, 1, COLOR2RGB (clrF));
  }
  
  xAve /= (double)count;
  yAve /= (double)count;

  width  = (int)Scale (xAve, Min, Max, 0, WidthScrFunc - 1, false);
  height = (int)Scale (yAve, Min, Max, 0, HeighScrFunc - 1, false);

  Canvas.FillCircle (width + shiftX, height + shiftY, 3, COLOR2RGB (clrBlack));
  Canvas.FillCircle (width + shiftX, height + shiftY, 2, COLOR2RGB (clr));
}
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
void SendGraphToCanvas (int shiftX, int shiftY)
{
  for (int w = 0; w < HeighScrFunc; w++)
  {
    for (int h = 0; h < HeighScrFunc; h++)
    {
      Canvas.PixelSet (w + shiftX, h + shiftY, COLOR2RGB (FunctScrin [w].clr [h]));
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
void DrawFunctionGraph (double     min,
                        double     max,
                        double     fMin,
                        double     fMax,
                        C_Function &f)
{
  double ar [2];
  double fV;

  for (int w = 0; w < HeighScrFunc; w++)
  {
    ar [0] = Scale (w, 0, HeighScrFunc, min, max, false);
    for (int h = 0; h < HeighScrFunc; h++)
    {
      ar [1] = Scale (h, 0, HeighScrFunc, min, max, false);
      fV = f.CalcFunc (ar, 1);
      FunctScrin [w].clr [h] = DoubleToColor (fV, fMin, fMax, 0, 250);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
//Scaling a number from a range to a specified range
double Scale (double In, double InMIN, double InMAX, double OutMIN, double OutMAX, bool Revers = false)
{
  if (OutMIN == OutMAX) return (OutMIN);
  if (InMIN == InMAX) return ((OutMIN + OutMAX) / 2.0);
  else
  {
    if (Revers)
    {
      if (In < InMIN) return (OutMAX);
      if (In > InMAX) return (OutMIN);
      return (((InMAX - In) * (OutMAX - OutMIN) / (InMAX - InMIN)) + OutMIN);
    }
    else
    {
      if (In < InMIN) return (OutMIN);
      if (In > InMAX) return (OutMAX);
      return (((In - InMIN) * (OutMAX - OutMIN) / (InMAX - InMIN)) + OutMIN);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
color DoubleToColor (const double in,    //input value
                     const double inMin, //minimum of input values
                     const double inMax, //maximum of input values
                     const int    loH,   //lower bound of HSL range values
                     const int    upH)   //upper bound of HSL range values
{
  int h = (int)Scale (in, inMin, inMax, loH, upH, true);
  return HSLtoRGB (h, 1.0, 0.5);
}
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
color HSLtoRGB (const int    h, //0   ... 360
                const double s, //0.0 ... 1.0
                const double l) //0.0 ... 1.0
{
  int r;
  int g;
  int b;
  if (s == 0.0)
  {
    r = g = b = (unsigned char)(l * 255);
    return StringToColor ((string)r + "," + (string)g + "," + (string)b);
  }
  else
  {
    double v1, v2;
    double hue = (double)h / 360.0;
    v2 = (l < 0.5) ? (l * (1.0 + s)) : ((l + s) - (l * s));
    v1 = 2.0 * l - v2;
    r = (unsigned char)(255 * HueToRGB (v1, v2, hue + (1.0 / 3.0)));
    g = (unsigned char)(255 * HueToRGB (v1, v2, hue));
    b = (unsigned char)(255 * HueToRGB (v1, v2, hue - (1.0 / 3.0)));
    return StringToColor ((string)r + "," + (string)g + "," + (string)b);
  }
}
//——————————————————————————————————————————————————————————————————————————————
//——————————————————————————————————————————————————————————————————————————————
double HueToRGB (double v1, double v2, double vH)
{
  if (vH < 0) vH += 1;
  if (vH > 1) vH -= 1;
  if ((6 * vH) < 1) return (v1 + (v2 - v1) * 6 * vH);
  if ((2 * vH) < 1) return v2;
  if ((3 * vH) < 2) return (v1 + (v2 - v1) * ((2.0f / 3) - vH) * 6);
  return v1;
}
//——————————————————————————————————————————————————————————————————————————————

double値を範囲から色に変換するために、HSLをRGBに変換するアルゴリズム（MetaTrader 5のカラーシステム）が使用されました。

テストスタンドは、グラフ上に画像を表示します。半分に分かれています。

左側にはテスト関数が表示されます。その3次元グラフを平面に投影し、赤は最大、青は最小を意味します。母集団における点の位置を表示し（色は変数の数40と1000のテスト関数の序数に対応し、2変数の関数では色付けはおこなわれません）、座標が平均化された点は白、最良の点は黒で示されます。
右側には収束グラフが表示され、2変数のテストは緑、40変数のテストは青、1000変数のテストは赤で示されます。各テストは5回ずつ実行されます（各色の収束グラフを5個）。ここでは、変数の数の増加に伴い、OAの収束性がどの程度悪化しているかを観察することができます。

6.RNGを用いた簡易OA

テスト例として、最もシンプルな検索方法を実装してみましょう。実用的な価値はないが、最適化アルゴリズムを比較するための何らかの基準になるでしょう。このストラテジーでは、新しい関数変数のセットを50/50のランダムな選択で生成します。母集団からランダムに選ばれた親セットから変数をコピーするか、最小/最大範囲から変数を生成するかです。テスト関数の値を受け取った後、得られた新しい変数セットを母集団の後半にコピーし、並び替えます。そのため、常に新しいセットが母集団の半分を占め、もう一方に最適なセットが集中します。

以下は、RNGを基盤とにしたOAコードです。

//+————————————————————————————————————————————————————————————————————————————+
class C_AO_RND
{
  public: //||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

  struct ArrColony
  {
      double args [];
  };

  //----------------------------------------------------------------------------
  double    A_RangeStep []; //Step ranges of genes
  double    A_RangeMin  []; //Min ranges of genes
  double    A_RangeMax  []; //Max ranges of genes

  ArrColony S_Population []; //Population
  ArrColony S_Colony     []; //Colony

  double    A_FFpop [];      //Values of fitness of individuals in population
  double    A_FFcol [];      //Values of fitness of individuals in colony

  //----------------------------------------------------------------------------
  // Initialization of algorithm
  void F_Init (int argCount,       //Number of arguments

               int populationSize) //Population size
  {
    MathSrand ((int)GetMicrosecondCount ()); //reset of the generator

    p_argCount  = argCount;
    p_sizeOfPop = populationSize;
    p_sizeOfCol = populationSize / 2;

    p_dwelling  = false;

    f_arrayInitResize (A_RangeStep, argCount, 0.0);
    f_arrayInitResize (A_RangeMin,  argCount, 0.0);
    f_arrayInitResize (A_RangeMax,  argCount, 0.0);

    ArrayResize (S_Population, p_sizeOfPop);
    ArrayResize (s_populTemp, p_sizeOfPop);
    for (int i = 0; i < p_sizeOfPop; i++)
    {
      f_arrayInitResize (S_Population [i].args, argCount, 0.0);
      f_arrayInitResize (s_populTemp [i].args, argCount, 0.0);
    }

    ArrayResize (S_Colony, p_sizeOfCol);
    for (int i = 0; i < p_sizeOfCol; i++)
    {
      f_arrayInitResize (S_Colony [i].args, argCount, 0.0);
    }

    f_arrayInitResize (A_FFpop, p_sizeOfPop, -DBL_MAX);
    f_arrayInitResize (A_FFcol, p_sizeOfCol, -DBL_MAX);

    f_arrayInitResize (a_indexes, p_sizeOfPop, 0);
    f_arrayInitResize (a_valueOnIndexes, p_sizeOfPop, 0.0);
  }

  //----------------------------------------------------------------------------
  void F_EpochReset ()   //Reset of epoch, allows to begin evolution again without initial initialization of variables
  {
    p_dwelling = false;
    ArrayInitialize (A_FFpop, -DBL_MAX);
    ArrayInitialize (A_FFcol, -DBL_MAX);
  }
  //----------------------------------------------------------------------------
  void F_Preparation ();  //Preparation
  //----------------------------------------------------------------------------
  void F_Sorting ();      //The settling of a colony in population and the subsequent sorting of population

  private: //|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
  //----------------------------------------------------------------------------
  void F_PopulSorting ();

  //----------------------------------------------------------------------------
  ArrColony          s_populTemp      []; //Temporal population
  int                a_indexes        []; //Indexes of chromosomes
  double             a_valueOnIndexes []; //VFF of the appropriate indexes of chromosomes

  //----------------------------------------------------------------------------
  template <typename T1>
  void f_arrayInitResize (T1 &arr [], const int size, const T1 value)
  {
    ArrayResize     (arr, size);
    ArrayInitialize (arr, value);
  }

  //----------------------------------------------------------------------------
  double f_seInDiSp         (double In, double InMin, double InMax, double step);
  double f_RNDfromCI        (double min, double max);
  double f_scale            (double In, double InMIN, double InMAX, double OutMIN, double OutMAX);

  //---Constants----------------------------------------------------------------
  int  p_argCount;   //Quantity of arguments in a set of arguments
  int  p_sizeOfCol;  //Quantity of set in a colony
  int  p_sizeOfPop;  //Quantity of set in population
  bool p_dwelling;   //Flag of the first settling of a colony in population
};
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
void C_AO_RND::F_Preparation ()
{
  //if starts of algorithm weren't yet - generate a colony with random arguments
  if (!p_dwelling)
  {
    for (int person = 0; person < p_sizeOfCol; person++)
    {
      for (int arg = 0; arg < p_argCount; arg++)
      {
        S_Colony [person].args [arg] = f_seInDiSp (f_RNDfromCI (A_RangeMin [arg], A_RangeMax [arg]),
                                                    A_RangeMin  [arg],
                                                    A_RangeMax  [arg],
                                                    A_RangeStep [arg]);
      }
    }

    p_dwelling = true;
  }
  //generation of a colony using with copying arguments from parent sets--------
  else
  {
    int parentAdress = 0;
    double rnd       = 0.0;
    double argVal    = 0.0;

    for (int setArg = 0; setArg < p_sizeOfCol; setArg++)
    {
      //get a random address of the parent set
      parentAdress = (int)f_RNDfromCI (0, p_sizeOfPop - 1);

      for (int arg = 0; arg < p_argCount; arg++)
      {
        if (A_RangeMin [arg] == A_RangeMax [arg]) continue;

        rnd = f_RNDfromCI (0.0, 1.0);

        if (rnd < 0.5)
        {
          S_Colony [setArg].args [arg] = S_Population [parentAdress].args [arg];
        }
        else
        {
          argVal = f_RNDfromCI (A_RangeMin [arg], A_RangeMax [arg]);
          argVal = f_seInDiSp (argVal, A_RangeMin [arg], A_RangeMax [arg], A_RangeStep [arg]);

          S_Colony [setArg].args [arg] = argVal;
        }
      }
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
void C_AO_RND::F_Sorting ()
{
  for (int person = 0; person < p_sizeOfCol; person++)
  {
    ArrayCopy (S_Population [person + p_sizeOfCol].args, S_Colony [person].args, 0, 0, WHOLE_ARRAY);
  }
  ArrayCopy (A_FFpop, A_FFcol, p_sizeOfCol, 0, WHOLE_ARRAY);

  F_PopulSorting ();
}
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
// Ranging of population.
void C_AO_RND::F_PopulSorting ()
{
  //----------------------------------------------------------------------------
  int   cnt = 1, i = 0, u = 0;
  int   t0 = 0;
  double t1 = 0.0;
  //----------------------------------------------------------------------------

  // We will put indexes in the temporary array
  for (i = 0; i < p_sizeOfPop; i++)
  {
    a_indexes [i] = i;
    a_valueOnIndexes [i] = A_FFpop [i];
  }
  while (cnt > 0)
  {
    cnt = 0;
    for (i = 0; i < p_sizeOfPop - 1; i++)
    {
      if (a_valueOnIndexes [i] < a_valueOnIndexes [i + 1])
      {
        //-----------------------
        t0 = a_indexes [i + 1];
        t1 = a_valueOnIndexes [i + 1];
        a_indexes [i + 1] = a_indexes [i];
        a_valueOnIndexes [i + 1] = a_valueOnIndexes [i];
        a_indexes [i] = t0;
        a_valueOnIndexes [i] = t1;
        //-----------------------
        cnt++;
      }
    }
  }

  // On the received indexes create the sorted temporary population
  for (u = 0; u < p_sizeOfPop; u++) ArrayCopy (s_populTemp [u].args, S_Population [a_indexes [u]].args, 0, 0, WHOLE_ARRAY);

  // Copy the sorted array back
  for (u = 0; u < p_sizeOfPop; u++) ArrayCopy (S_Population [u].args, s_populTemp [u].args, 0, 0, WHOLE_ARRAY);

  ArrayCopy (A_FFpop, a_valueOnIndexes, 0, 0, WHOLE_ARRAY);
}
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
// Choice in discrete space
double C_AO_RND::f_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));
}
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
// Random number generator in the custom interval.
double C_AO_RND::f_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)));
}
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
double C_AO_RND::f_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);
  }
}
//——————————————————————————————————————————————————————————————————————————————

7.結果

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

テストスタンドでテストした結果、RND OAの結果はかなり予想外のものです。ことがわかりました。このアルゴリズムは、2変数の関数の最適値を非常に高い精度で求めることができるが、ForestとMegacityの場合は、明らかに結果が悪くなっています。一方、多変数を持つ関数の弱い探索特性については、私の仮定を確認することができました。40引数ですでに非常に平凡な結果になっています。最終的な累積値は0.51254です。

次回以降も、よく知られ、広く使われている最適化アルゴリズムを分析・検証し、OAの評価を構成する結果表を埋めていく予定です。

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

添付されたファイル |

ZIPをダウンロード

MQL5.zip (9.71 KB)

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

この著者による他の記事

ディスカッションに移動

一からの取引エキスパートアドバイザーの開発（第29部）：おしゃべりプラットフォーム

この記事では、MetaTrader 5プラットフォームをしゃべらせる方法を学びます。EAをもっと楽しくしたらどうでしょうか。金融市場の取引は退屈で単調すぎることがよくありますが、私たちはこの仕事の疲れを軽減することができます。依存症などの問題を経験している方にとってはこのプロジェクトは危険な場合があるのでご注意ください。ただし、一般的には、それは退屈を軽減するだけです。

ニューラルネットワークが簡単に（第27部）：DQN (Deep Q-Learning)

強化学習の研究を続けます。今回は、「Deep Q-Learning」という手法に触れてみましょう。この手法を用いることで、DeepMindチームはアタリ社のコンピューターゲームのプレイで人間を凌駕するモデルを作成することができました。取引上の問題を解決するための技術の可能性を評価するのに役立つと思います。