母集団最適化アルゴリズム:差分進化(DE)
内容
1. はじめに
メタヒューリスティック最適化法は、複雑な最適化問題を解くために発見的アプローチを使用するアルゴリズムのクラスです。数値最適化手法とは異なり、通常は数学的分析に基づき、目的関数の勾配や微分に関する知識を必要とします。メタヒューリスティック手法の主な違いは、関数が多くの局所最適値を持つ場合や連続微分可能でない場合でも、大きな探索空間を探索し、大域的最適値を見つける能力です。メタヒューリスティック手法の利点は、「ブラックボックス」、つまり解析的な解が存在しない関数を扱うことができる点です。確率論的な原理に基づいており、解の質が高くなります。
進化的アルゴリズム(EA)は、複雑な最適化問題を解くために自然進化のプロセスをシミュレーションするメタヒューリスティック最適化手法の別クラスです。遺伝、突然変異、交配、自然淘汰の原理に基づいています。進化的アルゴリズムにおける進化のプロセスは、自然淘汰をモデルにしており、適解が生き残りやすく、その特徴を次の世代に伝えます。こうして、母集団は徐々に最適解に収束していきます。最もよく知られた進化的アルゴリズムには、遺伝的アルゴリズム(GA)、進化的プログラミング(EP)、進化戦略(ES)、遺伝的プログラミング(GP)などがあります。これらのアルゴリズムにはそれぞれ特徴があり、様々な分野で利用されています。
一般に、進化的アルゴリズムは、特に解析的な関数式や勾配を利用できない場合に、複雑な最適化問題を解くための強力なツールです。探索空間を探索し、異なる個々の解からの情報を組み合わせて最適解を見つけることができます。
差分進化(DE)は、メタヒューリスティクス最適化手法の1つです。他の方法と異なるのは、そのシンプルさと効率性です。DEは、突然変異や交配によって新たな解決策を生み出すベクトルの集団を使用しています。勾配の知識を必要とせず、大域的な最適値を求めることができます。
DEアルゴリズムは、90年代にストーンとプライスによって開発され(「Differential Evolution - A Simple and Efficient Heuristic for global Optimization over Continuous Spaces」で発表)、以来、パラメータベクトルの母集団を用いて最適解を求める最も一般的な最適化手法の1つとなっています。
2.アルゴリズム
差分進化の考え方は、シンプルさと効率性を兼ね備えています。差分進化アルゴリズムは、潜在的な解を表すベクトルの集団を使用します。各ベクトルは、最適化問題の変数の値を表す成分で構成されます。
DEでは、ベクトルが探索エージェントの役割を果たします。このアルゴリズムは、無作為なベクトル集団を作成することから始まります。その後、各ベクトルが突然変異を起こし、集団内の他のベクトルと交配するという反復プロセスが起こります。突然変異は、母集団から無作為に選択された2つのベクトルの差を3番目のベクトルに加えることで達成されます。これにより、問題解決の可能性を示す新しいベクトルが作成されます。
変異後、変異ベクトルは元のベクトルと交配されます。交差は、2つのベクトルの情報を組み合わせ、新たな解決策を生み出すことを可能にします。得られた結果は、母集団における現在の最適解と比較されます。新しいベクトルが優れていれば、それは古いベクトルに取って代わり、母集団の一部となります。突然変異は探索空間の探索を可能にし、交差は異なるベクトルからの情報を組み合わせて新しい解を生み出します。
突然変異、交雑、置換は、所定の反復回数に達するか、必要な解の精度に達する(私たちの場合は10,000回の適応度関数の実行)といった停止条件に達するまで、数回の反復で繰り返されます。
DEは、最適化問題を解決するために広く使用されている進化的アルゴリズムの1つです。差分アルゴリズムは、差分演算子を使用して、現在の母集団に基づいて新しい候補を作成します。以下は、差分アルゴリズムで使用される基本方程式です。
1. 新しい候補を作る方程式(差分)
r = r1 + F * (r2 - r3)
ここで
- v:新しいベクトル成分
- r1、r2、r3:無作為に選択されたベクトル(母集団からの個々の解)の成分
- F:微分比。溶液のばらつき(得られた値のばらつき)の程度をコントロールします。デフォルトの範囲は(0.0;1.0)。
2.クロスオーバー方程式:
u = クロスオーバー (x, v)
式は、現在の解xと新しい候補vとの間のクロスオーバーを記述します。クロスオーバー演算子は、解のどの成分が新しい候補から取り出されるかを決定します。これは新しいベクトル成分が使われる確率であり、そうでなければ成分は変更されません。(0.0;1.0]が使用されます。
DEアルゴリズムの擬似コードを書いてみましょう。アルゴリズム自体が単純なので、単純で理解しやすいです(実際には、コードはその擬似コードよりほんの少し複雑になる)。
- ベクトルの無作為な母集団を作る
- 適応度関数を計算する
- 最適解を更新する
- 母集団を更新する(ベクトルをより良い変異体に置き換える)
- どちらがいいかに応じて、変異ベクトル成分を作成するまたは同じ成分のままにする
- 2から繰り返す
DEアルゴリズムでベクトルを記述するために、構造体を書き、それをS_Vectorと呼ぶことにします。この構造体には以下のフィールドがあります。
- Init (int coords):この関数は、指定された長さベクトルcoordsを初期化します。cとcPrevという2つの配列を作成し、それぞれベクトルの座標とその前の座標を表す。また、fとfPrevの初期値は「-DBL_MAX」に設定されています。
- c []:ベクトル座標を含む配列
- cPrev []:直前の反復におけるベクトル座標を含む配列
- f:現在のベクトルの適応度関数値
- fPrev:直前の反復におけるベクトル適応度関数の値
//—————————————————————————————————————————————————————————————————————————————— struct S_Vector { void Init (int coords) { ArrayResize (c, coords); ArrayResize (cPrev, coords); f = -DBL_MAX; fPrev = -DBL_MAX; } double c []; //coordinates double cPrev []; //previous coordinates double f; //fitness double fPrev; //previous fitness }; //——————————————————————————————————————————————————————————————————————————————
DEのような初歩的なアルゴリズムのクラス記述も非常にシンプルです。C_AO_DEクラスを宣言しましょう。C_AO_DEクラスのフィールドには、アルゴリズムの現在の状態とそのパラメータに関する情報が格納され、メソッドは関数の最適化に関連するさまざまな操作を実行します。
このクラスには以下のフィールドとメソッドがあります。
- cB []:アルゴリズムによって見つかった最良の座標を含む配列
- fB:最適座標の適応度関数値
- v []:ベクトルの集団を表す S_Vector 構造体の配列
- rangeMax[]:各ベクトル座標の最大値を格納する配列
- rangeMin[]:各ベクトル座標の最小値を含む配列
- rangeStep[]:各ベクトル座標のステップ値を含む配列
- Init (int coordsP, int popSizeP, double diffWeightP, double crossProbabP):アルゴリズムのパラメータを初期化する関数.座標数coordsP、母集団サイズpopSizeP、差分重みdiffWeightP、交叉確率crossProbabPを取ります。
- Moving():この関数は、差分進化アルゴリズムの1ステップを実行します。
- Revision ():この関数は、ベクトル母集団の修正をおこないます。
- SeInDiSp (double In, double InMin, double InMax, double Step):このメソッドは、指定されたステップで指定された範囲内の新しい座標値を計算します。
- RNDfromCI (double min, double max):この関数は、範囲 [min, max] 内の乱数を生成します。
//—————————————————————————————————————————————————————————————————————————————— class C_AO_DE { //---------------------------------------------------------------------------- public: double cB []; //best coordinates public: double fB; //FF of the best coordinates public: S_Vector v []; //vector public: double rangeMax []; //maximum search range public: double rangeMin []; //manimum search range public: double rangeStep []; //step search public: void Init (const int coordsP, //coordinates number const int popSizeP, //population size const double diffWeightP, //differential weight const double crossProbabP); //crossover robability public: void Moving (); public: void Revision (); //---------------------------------------------------------------------------- private: int coords; //coordinates number private: int popSize; //population size private: double diffWeight; //differential weight private: double crossProbab; //crossover robability private: bool revision; private: double SeInDiSp (double In, double InMin, double InMax, double Step); private: double RNDfromCI (double min, double max); }; //——————————————————————————————————————————————————————————————————————————————
C_AO_DEクラスのInitメソッドは、差分進化アルゴリズムのパラメータを初期化します。このメソッドは4つのパラメータを取ります。
- coordsP:座標の数
- popSizeP:母集団のサイズ
- diffWeightP:差分重量
- crossProbabP:交叉確率
最初に、このメソッドはMathSrand関数を使って乱数発生器をリセットします。これにより、アルゴリズムが起動するたびに、新しい乱数列が使用されることになります。
次に、このメソッドはfB変数とrevision変数を初期化します。fB変数には、アルゴリズムによって発見された最良の適応度関数値が格納されます。最初は「-DBL_MAX」、つまり非常に小さな数値に設定されています。変数revisionはfalseに設定されており、これはベクトル母集団がまだ修正されていないことを意味します。
このメソッドは次に、coords、popSize、diffWeight、crossProbab変数をパラメータとして渡された値で初期化します。
このメソッドは、次にベクトルの母集団を含むpopSizeサイズの配列vを作成します。
次に、このメソッドは、それぞれがcoordsサイズ(座標の数)のrangeMax、rangeMin、rangeStepの3つの配列を作成します。
最後に、このメソッドは、アルゴリズムによって見つかった最適な座標を含むcoordsサイズのcB配列を作成します。
//—————————————————————————————————————————————————————————————————————————————— void C_AO_DE::Init (const int coordsP, //coordinates number const int popSizeP, //population size const double diffWeightP, //differential weight const double crossProbabP) //crossover robability { MathSrand ((int)GetMicrosecondCount ()); // reset of the generator fB = -DBL_MAX; revision = false; coords = coordsP; popSize = popSizeP; diffWeight = diffWeightP; crossProbab = crossProbabP; ArrayResize (v, popSize); for (int i = 0; i < popSize; i++) v [i].Init (coords); ArrayResize (rangeMax, coords); ArrayResize (rangeMin, coords); ArrayResize (rangeStep, coords); ArrayResize (cB, coords); } //——————————————————————————————————————————————————————————————————————————————
探索空間の解ベクトルを変更するために、C_AO_DEクラスのMovingメソッドを書きます。この方法は、突然変異とクロスオーバーの演算子を適用して新しい候補ベクトルを生成し、適応度関数に基づいて最適解を選択します。
「if (!revision)」条件で始まるコードの最初のブロックは、Movingメソッドが最初に実行されたとき、またはInitメソッドが呼ばれた後にのみ実行されます。これは、指定された範囲内の無作為な値と、rangeStep配列で指定されたステップで、ベクトルの初期集団を初期化します。
その後、この方法はforループを使って母集団の各ベクトルを更新します。各ベクトルについて、この方法は母集団から現在のベクトル(i)と同じでない3つの異なる無作為なベクトル(r1、r2、r3)を選択し、突然変異とクロスオーバーの演算子を適用して新しい候補ベクトルを取ります。突然変異演算子は、ベクトルr2とr3の差に差分重みdiffWeightを乗じたものを計算し、その結果をr1ベクトルに加えます。クロスオーバー演算子はベクトル座標を選択し、crossProbab確率で新しい候補ベクトルの対応する座標と置き換えます。クロスオーバー確率が成立しない場合、現在のベクトル座標は変更されません。
以下のコードを解析すると、ベクトルを変更するMovingメソッドでは、既存のものから得られる座標以外の空間上の座標を作成することはできないことがわかります。従って、アルゴリズムの確率性は、交差のためのベクトルの選択にのみあり、新しいオリジナルのベクトルの生成にはありません。この特徴は、後述する広範囲に及ぶ結果を決定づけます。
//—————————————————————————————————————————————————————————————————————————————— void C_AO_DE::Moving () { //---------------------------------------------------------------------------- if (!revision) { for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { v [i].c [c] = RNDfromCI (rangeMin [c], rangeMax [c]); v [i].c [c] = SeInDiSp (v [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } revision = true; return; } //---------------------------------------------------------------------------- double rnd = 0.0; int r = 0; int r1 = 0; int r2 = 0; int r3 = 0; for (int i = 0; i < popSize; i++) { do { r = (int)RNDfromCI (0, popSize); if (r >= popSize) r = popSize - 1; r1 = r; } while (r1 == i); do { r = (int)RNDfromCI (0, popSize); if (r >= popSize) r = popSize - 1; r2 = r; } while (r2 == i || r2 == r1); do { r = (int)RNDfromCI (0, popSize); if (r >= popSize) r = popSize - 1; r3 = r; } while (r3 == i || r3 == r1 || r3 == r2); for (int c = 0; c < coords; c++) { rnd = RNDfromCI (0, 1.0); if (rnd < crossProbab) { v [i].c [c] = v [r1].cPrev [c] + diffWeight * (v [r2].cPrev [c] - v [r3].cPrev [c]); v [i].c [c] = SeInDiSp (v [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } else { v [i].c [c] = v [i].cPrev [c]; } } } } //——————————————————————————————————————————————————————————————————————————————
最後に、C_AO_DEクラスのRevisionメソッドが必要です。このメソッドは、母集団内の最適解を更新し、適応度関数とベクトル座標の以前の値を保存します。
まず、このメソッドは変数indを値「-1」で初期化します。そして、forループを使って、母集団内のすべてのベクトルを繰り返し処理します。もし現在のベクトルの適応度関数がfB(これまでに見つかった最高の適応度関数)より大きければ、そのベクトルのインデックスをind変数に格納します。
indが「-1」でなければ、このメソッドはfBの値をindインデックスを持つベクトルの適応度関数の値に更新し、その座標をcB配列に格納します。
その後、このメソッドは別のforループを使って、母集団内のすべてのベクトルを繰り返し処理します。現在のベクトルの適応度関数がその前の値よりも大きい場合、このメソッドは適応度関数の現在の値とベクトル座標を対応するv[i].fPrevフィールドとv[i].cPrevフィールドに格納します。
このメソッドによって、C_AO_DEクラスは母集団内の最良の解と、適応度関数の前の値とベクトル座標を保存し、後で適応度関数を最適化する際に使用することができます。
母集団は、元の(親)バージョンよりも優れたベクトルが見つかるまで、探索空間内をそれ以上移動しないことがわかります。この点は、上で述べたことをすべて補完するものです。
//—————————————————————————————————————————————————————————————————————————————— void C_AO_DE::Revision () { //---------------------------------------------------------------------------- int ind = -1; for (int i = 0; i < popSize; i++) { if (v [i].f > fB) ind = i; } if (ind != -1) { fB = v [ind].f; ArrayCopy (cB, v [ind].c, 0, 0, WHOLE_ARRAY); } //---------------------------------------------------------------------------- for (int i = 0; i < popSize; i++) { if (v [i].f > v [i].fPrev) { v [i].fPrev = v [i].f; ArrayCopy (v [i].cPrev, v [i].c, 0, 0, WHOLE_ARRAY); } } } //——————————————————————————————————————————————————————————————————————————————
3.テスト結果
DEテストスタンドの結果:
C_AO_DE:50;0.2;0.8
=============================
5 Rastrigin's; Func runs 10000 result:80.30183306326985
Score:0.99498
25 Rastrigin's; Func runs 10000 result:76.15178282331799
Score:0.94356
500 Rastrigin's; Func runs 10000 result:52.17316317703311
Score:0.64645
=============================
5 Forest's; Func runs 10000 result:1.7348423083855402
Score:0.98131
25 Forest's; Func runs 10000 result:1.28572746338484
Score:0.72727
500 Forest's; Func runs 10000 result:0.20833645141168078
Score:0.11785
=============================
5 Megacity's; Func runs 10000 result:9.640000000000002
Score:0.80333
25 Megacity's; Func runs 10000 result:3.9199999999999995
Score:0.32667
500 Megacity's; Func runs 10000 result:0.3548
Score:0.02957
=============================
All score:5.57100
アルゴリズムの出力値から、優れたテスト結果を見ることができます。
アルゴリズムの驚異的な収束を見ることができますが、MovingメソッドとRevisionメソッドの説明で前述した特徴にも気づくことができます。ビジュアライゼーションを作成する際、何度か試した後、特に最も成功したものを選択しました。実際、結果は必ずしもそれほど優れているわけではありません。これは母集団の退化によって説明されるもので、母集団全体、つまりすべてのベクトルが1つの極値に収束します。しかし、これは大域的最適解ではないかもしれません。上述したように、このアルゴリズムには、探索空間を探索し続け、新しいユニークなベクトルを作り出すメカニズムはありません。DEアルゴリズムは新しいベクトルを作るのではなく、既存のベクトルから組み合わせを生成するだけです。これで完全な退化が説明できます。人口の「遺伝子プール」を多様化するための「新しい血」は生まれません。
Rastriginテスト関数のDE
Forestテスト関数のDE。
Megacityテスト関数のDE
収束の巨大な広がり(特にForest関数とMegacity関数で顕著)
続いて、新たな参加者であるDEを加えて、最終的な格付けを考えてみましょう。このアルゴリズムは、10個の変数を使用したForestテストで、現在のリーダーであるSDSmからトップの座を奪い取ることができました。他のテストの結果も非常に良く、DEはSSGに次いで4位となりました。各テスト関数について、通常の5倍テスト実行の代わりに、10倍テストを実行しなければならなかったことは、Forst関数とMegacity関数で結果が大きくばらついたためです。平滑Rastrigin関数では、結果のばらつきはあまり目立ちません。
# | AO | 詳細 | Rastrigin | Rastrigin最終 | Forest | Forest最終 | Megacity(離散) | Megacity最終 | 最終結果 | ||||||
10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | |||||||
1 | SDSm | 確率的拡散探索M | 0.99809 | 1.00000 | 0.69149 | 2.68958 | 0.99265 | 1.00000 | 1.00000 | 2.99265 | 1.00000 | 1.00000 | 1.00000 | 3.00000 | 100.000 |
2 | SDS | Stochastic Diffusion Search | 0.99737 | 0.97322 | 0.58904 | 2.55963 | 0,96067 | 0.93572 | 0.79649 | 2.69288 | 0.78696 | 0.93815 | 0.71804 | 2.44315 | 88.201 |
3 | SSG | 苗木の播種と育成 | 1.00000 | 0.92761 | 0.51630 | 2.44391 | 0.72120 | 0.65201 | 0.83760 | 2.21081 | 0.54782 | 0.61841 | 0.99522 | 2.16146 | 77.683 |
4 | DE | 差分進化 | 0.98295 | 0.89236 | 0.51375 | 2.38906 | 1.00000 | 0.84602 | 0.65510 | 2.50112 | 0.90000 | 0.52237 | 0.12031 | 1.54268 | 73.099 |
5 | HS | ハーモニー検索 | 0.99676 | 0.88385 | 0.44686 | 2.32747 | 0.99148 | 0.68242 | 0.37529 | 2.04919 | 0.71739 | 0.71842 | 0.41338 | 1.84919 | 70.623 |
6 | IWO | 侵入雑草最適化 | 0.95828 | 0.62227 | 0.27647 | 1.85703 | 0.70170 | 0.31972 | 0.26613 | 1.28755 | 0.57391 | 0.30527 | 0.33130 | 1.21048 | 48.250 |
7 | ACOm | 蟻コロニー最適化M | 0.34611 | 0.16683 | 0.15808 | 0.67103 | 0.86147 | 0.68980 | 0.64798 | 2.19925 | 0.71739 | 0.63947 | 0.05579 | 1.41265 | 47.387 |
8 | MEC | Mind Evolutionary Computation | 0.99270 | 0.47345 | 0.21148 | 1.67763 | 0.60244 | 0.28046 | 0.21324 | 1.09615 | 0.66957 | 0.30000 | 0.26045 | 1.23002 | 44.049 |
9 | SDOm | 螺旋ダイナミクス最適化 M | 0.69840 | 0.52988 | 0.33168 | 1.55996 | 0.59818 | 0.38766 | 0.37600 | 1.36183 | 0.35653 | 0.15262 | 0.25842 | 0.76758 | 40.289 |
10 | COAm | カッコウ最適化アルゴリズムM | 0.92400 | 0.43407 | 0.24120 | 1.59927 | 0.57881 | 0.23477 | 0.13842 | 0.95200 | 0.52174 | 0.24079 | 0.17001 | 0.93254 | 37.830 |
11 | FAm | ホタルアルゴリズムM | 0.59825 | 0.31520 | 0.15893 | 1.07239 | 0.50637 | 0.29178 | 0.41704 | 1.21519 | 0.24783 | 0.20526 | 0.35090 | 0.80398 | 33.139 |
12 | ABC | 人工蜂コロニー | 0.78170 | 0.30347 | 0.19313 | 1.27829 | 0.53379 | 0.14799 | 0.11177 | 0.79355 | 0.40435 | 0.19474 | 0.13859 | 0.73768 | 29.766 |
13 | BA | コウモリアルゴリズム | 0.40526 | 0.59145 | 0.78330 | 1.78002 | 0.20664 | 0.12056 | 0.21769 | 0.54488 | 0.21305 | 0.07632 | 0.17288 | 0.46225 | 29.499 |
14 | CSS | 荷電系探索 | 0.56605 | 0.68683 | 1.00000 | 2.25289 | 0.13961 | 0.01853 | 0.13638 | 0.29452 | 0.07392 | 0.00000 | 0.03465 | 0.10856 | 27.930 |
15 | GSA | 重力探索法 | 0.70167 | 0.41944 | 0.00000 | 1.12111 | 0.31390 | 0.25120 | 0.27812 | 0.84322 | 0.42609 | 0.25525 | 0.00000 | 0.68134 | 27.807 |
16 | BFO | 細菌採餌の最適化 | 0.67203 | 0.28721 | 0.10957 | 1.06881 | 0.39364 | 0.18364 | 0.17298 | 0.75026 | 0.37392 | 0.24211 | 0.18841 | 0.80444 | 27.542 |
17 | EM | 電磁気学的アルゴリズム | 0.12235 | 0.42928 | 0.92752 | 1.47915 | 0.00000 | 0.02413 | 0.29215 | 0.31628 | 0.00000 | 0.00527 | 0.10872 | 0.11399 | 19.002 |
18 | SFL | ShuffledFrog-Leaping | 0.40072 | 0.22021 | 0.24624 | 0.86717 | 0.19981 | 0.02861 | 0.02221 | 0.25063 | 0.19565 | 0.04474 | 0.06607 | 0.30646 | 13.200 |
19 | MA | モンキーアルゴリズム | 0.33192 | 0.31029 | 0.13582 | 0.77804 | 0.09927 | 0.05443 | 0.07482 | 0.22852 | 0.15652 | 0.03553 | 0.10669 | 0.29874 | 11.777 |
20 | FSS | 魚群検索 | 0.46812 | 0.23502 | 0.10483 | 0.80798 | 0.12730 | 0.03458 | 0.05458 | 0.21647 | 0.12175 | 0.03947 | 0.08244 | 0.24366 | 11.332 |
21 | IWDm | インテリジェント水滴M | 0.26459 | 0.13013 | 0.07500 | 0.46972 | 0.28358 | 0.05445 | 0.05112 | 0.38916 | 0.22609 | 0.05659 | 0.05054 | 0.33322 | 10.423 |
22 | PSO | 粒子群最適化 | 0.20449 | 0.07607 | 0.06641 | 0.34696 | 0.18734 | 0.07233 | 0.18207 | 0.44175 | 0.16956 | 0.04737 | 0.01947 | 0.23641 | 8.426 |
23 | RND | ランダム | 0.16826 | 0.09038 | 0.07438 | 0.33302 | 0.13381 | 0.03318 | 0.03949 | 0.20648 | 0.12175 | 0.03290 | 0.04898 | 0.20363 | 5.054 |
24 | GWO | 灰色オオカミオプティマイザ | 0.00000 | 0.00000 | 0.02093 | 0.02093 | 0.06514 | 0.00000 | 0.00000 | 0.06514 | 0.23478 | 0.05789 | 0.02545 | 0.31812 | 1.000 |
まとめ
差分進化アルゴリズムは、個々のテストでは非常に平凡な結果であったにもかかわらず、非常に迅速に大域的最適値を見つけることができ、優れた収束性を持っています。DEは、モデルパラメータの最適化、ニューラルネットワークのチューニング、物理学や経済学における関数の最適化など、さまざまな分野で広く利用されています。結果は最初の反復における初期母集団に大きく左右されるため、このアルゴリズムで複数回の最適化を行うことをお勧めします。母集団のサイズを大きくし、同時に反復回数を増やすことは有益かもしれません。
差分進化アルゴリズムは、その単純さと演算速度にもかかわらず、母集団が退化し、その結果、局所極値から抜け出せなくなるといった明らかな欠点があります。最適化問題にDEを選択する際には、その点を考慮する必要があります。
この記事で取り上げたDEアルゴリズムは、いくつかの修正を加えるために使われる一種のテンプレートです。差分進化(DE)アルゴリズムを改善するための私の提案は以下の通りです。
1. 適応的パラメータ制御法を使用します。DEには、結果に大きな影響を与えるため、調整が必要なパラメータがいくつかあります。著者が推奨する差分の重みパラメータは0.2です。この値は、DEテストスクリプトで採用したデフォルト値です。このパラメータは、個体群の多様性に大きな影響を与えます。0.2より小さい値を選ぶと、アルゴリズムの収束はさらに良くなりますが、同時に結果のばらつきがさらに大きくなります。逆に、このパラメータの値を大きくすると、アルゴリズムは母集団の退化や局所極限でのスタックに耐性を持つようになりますが、同時に、テストによって制限された反復回数にわたって収束の質が急速に低下し、それに応じて探索時間も必然的に長くなります。
クロスオーバーの確率も最適化の質に影響します。筆者が推奨する値は0.9です。しかし、私の実験によれば、0.8がより適しています。
上記を考慮すると、アルゴリズムをタスクに応じて自動的に調整できるように、パラメータを制御し、動的に変更するために適応的な方法を使用することが望ましいと思われます。
2.突然変異とクロスオーバーの戦略を使い分けます。
3.ハイブリッドメソッドの使用:DEは、遺伝的アルゴリズム、勾配ベースの最適化手法、粒子群最適化手法など、他の最適化手法と組み合わせることができます。これはアルゴリズムの性能を向上させ、アルゴリズム全体の効率向上に役立ちます。
4.収束の改善:集団の多様性を高めるために無作為ベクトル生成を追加します。
5.突然変異のための個体選択に異なる戦略を用いる:このアルゴリズムでは、交叉のための個体選択に完全に無作為な方法を考慮します。しかし、この方法は、クロスオーバー/突然変異のために個体を選択するための他の異なる戦略、例えば適性に基づいて個体を選択する戦略を使用することによって、補うことも、完全に置き換えることもできます。これは、母集団の多様性を向上させ、アルゴリズムがスタックすることへの耐性を大幅に改善するのに役立ちます。
全体として、DEアルゴリズムはその性能について非常に良い印象を与えるが、この興味深いアルゴリズムの特徴を念頭に置くか、あるいは異なる戦略や手法を組み合わせて適用することで、差分進化を改善する試みが必要です。DEは、アルゴリズムが信じられないほどシンプルで高速でありながら、非常に効率的でありうることを確信を持って実証しました。差分進化アルゴリズムは、最適化されたパラメータの数が多い場合、進化中の多様性の減少の影響が顕著でなくなるため、高次元の複雑な最適化問題を解くのに推奨できます。
図1:関連テストによるアルゴリズムのカラーグラデーション
図2:アルゴリズムのテスト結果のヒストグラム(0から100までのスケールで、多ければ多いほど良いです。
アーカイブには、記事で適用されている方法で格付けを計算するためのスクリプトが含まれています)。
差分進化(DE)アルゴリズムの長所と短所
長所
- 外部パラメータが少ない
- 実装がシンプル
- 動作速度
- 優れたスケーラビリティ
- 様々な種類の機能で非常に優れた性能を発揮(欠点を考慮に入れて)
短所
- 結果のばらつきが大きい
- 局所的な極端な状況に陥る傾向
この記事には、過去の記事で説明したアルゴリズムコードの最新版を更新したアーカイブが添付されています。記事の著者は、正規アルゴリズムの説明の絶対的な正確さについて責任を負いません。検索機能を向上させるために、それらの多くに変更が加えられています。記事に示された結論と判断は、実験結果に基づいています。
MetaQuotes Ltdによってロシア語から翻訳されました。
元の記事: https://www.mql5.com/ru/articles/13781
- 無料取引アプリ
- 8千を超えるシグナルをコピー
- 金融ニュースで金融マーケットを探索