このページは機械翻訳を使用して翻訳されました。最新版の英語を参照するには、ここをクリックします。
サロゲート最適化アルゴリズム
シリアルsurrogateoptアルゴリズム
シリアルsurrogateoptアルゴリズムの概要
サロゲート最適化アルゴリズムは 2 つのフェーズを交互に実行します。
サロゲートの構築 — 境界内に
options.MinSurrogatePoints個のランダム ポイントを作成します。これらのポイントで (高価な) 目的関数を評価します。これらの点を通る ラジアル基底関数 を補間して、目的関数の代替関数を構築します。最小値の探索 — 境界内で数千個のランダムな点をサンプリングして、目的関数の最小値を探します。これらのポイントでのサロゲート値と、それらのポイントと（高価な）目的関数が評価されたポイント間の距離に基づいて、メリット関数を評価します。メリット関数によって測定された最適なポイントを候補として選択します。最適な候補ポイントで目的関数を評価します。この点は 適応点 と呼ばれます。この値を使用してサロゲートを更新し、再度探索します。
サロゲート構築フェーズでは、アルゴリズムは準ランダム シーケンスからサンプル ポイントを構築します。補間ラジアル基底関数の構築には、少なくとも nvars + 1 個のサンプル ポイントが必要です。ここで、nvars は問題の変数の数です。options.MinSurrogatePoints のデフォルト値は、2*nvars または 20 のいずれか大きい方になります。
アルゴリズムは、すべての探索ポイントが目的関数が以前に評価されたポイントに近すぎる場合 (オプション MinSampleDistance 未満)、最小値の探索フェーズを停止します。最小限の詳細を探索を参照してください。最小値探索フェーズからのこの切り替えは、サロゲート リセットと呼ばれます。
surrogateopt が目的関数または非線形制約関数を評価するときに NaN 値に遭遇すると、surrogateopt は評価ポイントを拒否して続行します。
サロゲート最適化の定義
サロゲート最適化アルゴリズムの説明では、次の定義を使用します。
現在 - 目的関数が最後に評価されたポイント。
現職 — 最新のサロゲート リセット以降に評価されたすべてのポイントの中で目的関数の値が最小のポイント。
最適 - これまでに評価されたすべてのポイントの中で目的関数の値が最小のポイント。
初期 —
InitialPointsオプションでソルバーに渡すポイント (ある場合)。ランダム ポイント - ソルバーが目的関数を評価するサロゲート構築フェーズのポイント。通常、ソルバーはこれらのポイントを準ランダム シーケンスから取得し、境界内に収まるようにスケーリングおよびシフトします。準ランダム シーケンスは、
randが返す疑似ランダム シーケンスに似ていますが、より均等に間隔が空いています。https://en.wikipedia.org/wiki/Low-discrepancy_sequenceを参照してください。ただし、変数の数が 500 を超える場合、ソルバーはラテン超方格シーケンスからポイントを取得します。https://en.wikipedia.org/wiki/Latin_hypercube_samplingを参照してください。適応ポイント - 最小値の探索フェーズでソルバーが目的関数を評価するポイント。
メリット関数 — メリット関数の定義 を参照してください。
評価ポイント - 目的関数の値がわかっているすべてのポイント。これらのポイントには、初期点、サロゲート構築ポイント、およびソルバーが目的関数を評価する最小値の探索ポイントが含まれます。
サンプルポイント。最小値の探索フェーズ中にソルバーがメリット関数を評価する疑似ランダム ポイント。これらのポイントは、最小限の詳細を探索 で説明されている場合を除き、ソルバーが目的関数を評価するポイントではありません。
サロゲートの詳細を構築する
サロゲートを構築するために、アルゴリズムは境界内の準ランダムなポイントを選択します。InitialPoints オプションでポイントの初期セットを渡すと、アルゴリズムはそれらのポイントと新しい準ランダム ポイント (必要な場合) を使用して合計 options.MinSurrogatePoints に到達します。
BatchUpdateInterval > 1 の場合、サロゲートを作成するために使用されるランダム サンプル ポイントの最小数は、 MinSurrogatePoints と BatchUpdateInterval のうち大きい方になります。
メモ
上限と下限が等しい場合、surrogateopt は代替変数を構築する前に、それらの「固定」変数を問題から削除します。surrogateopt は変数をシームレスに管理します。したがって、たとえば、初期点を渡す場合は、固定変数を含む完全なセットを渡します。
後続の Construct Surrogate フェーズでは、アルゴリズムは options.MinSurrogatePoints 準ランダム ポイントを使用します。アルゴリズムはこれらのポイントで目的関数を評価します。
このアルゴリズムは、ラジアル ベース ファンクション (RBF) 補間器を使用して、目的関数の補間としてサロゲート関数を構築します。RBF 補間には、サロゲートの構築に適した便利な特性がいくつかあります。
RBF 補間は、任意の次元数と任意の数のポイントで同じ式を使用して定義されます。
RBF 補間器は評価ポイントで規定の値を取得します。
RBF 補間器の評価にはほとんど時間がかかりません。
既存の補間にポイントを追加するのにかかる時間は比較的短くなります。
RBF 補間器を構築するには、N 行 N 列の線形方程式を解く必要があります。ここで、N は代替点の数です。Powell [1] が示したように、このシステムには多くの RBF に対する独自のソリューションがあります。
surrogateoptは線形テールを持つ 3 次 RBF を使用します。この RBF は凹凸の大きさを最小限に抑えます。Gutmann [4] を参照してください。
アルゴリズムは、最初の Construct Surrogate フェーズでは初期点とランダム ポイントのみを使用し、後続の Construct Surrogate フェーズではランダム ポイントのみを使用します。特に、このアルゴリズムでは、このサロゲートの最小値探索フェーズからの適応ポイントは使用されません。
最小限の詳細を探索
ソルバーは、局所的探索に関連する手順に従って目的関数の最小値を探索します。ソルバーは、探索の スケール を値 0.2 で初期化します。スケールは、パターン探索における探索領域の半径やメッシュ サイズのようなものです。ソルバーは、最後のサロゲート リセット以降の目的関数の値が最小のポイントである現時点から開始します。ソルバーは、サロゲートと既存の探索ポイントからの距離の両方に関連する メリット関数 の最小値を探索し、サロゲートの最小化と空間の探索のバランスを取ります。メリット関数の定義を参照してください。
ソルバーは、スケールされた長さを持つ数百または数千の疑似ランダム ベクトルを現行ポイントに追加して、サンプル ポイント を取得します。詳細については、サンプラーサイクル テーブルと関連する説明を参照してください。これらのベクトルは、各次元の境界によってシフトおよびスケーリングされ、スケールで乗算されます。必要に応じて、ソルバーはサンプル ポイントを境界内に収まるように変更します。ソルバーはサンプル ポイントでメリット関数を評価しますが、以前に評価されたポイントの options.MinSampleDistance 内のどのポイントでも評価しません。メリット関数の値が最も低い点は、適応点と呼ばれます。ソルバーは適応ポイントで目的関数の値を評価し、この値でサロゲートを更新します。適応点における目的関数の値が現職値よりも十分に低い場合、ソルバーは探索が成功したとみなし、適応点を現職として設定します。それ以外の場合、ソルバーは探索が失敗したと見なし、現職者を変更しません。
ソルバーは、次の条件の最初の条件が満たされたときにスケールを変更します。
最後のスケール変更以降、3 回の探索が成功しました。この場合、スケールは 2 倍になり、最大スケール長は境界で指定されたボックスのサイズの
0.8倍になります。最後のスケール変更以降、
max(5,nvar)回の失敗した探索が発生しました。ここで、nvarは問題変数の数です。この場合、スケールは半分に縮小され、境界で指定されたボックスのサイズの1e-5倍の最小スケール長になります。
このようにして、ランダム探索は最終的に、目的関数の値が小さい現在のポイントの近くに集中します。次に、ソルバーは最小スケール長に向かってスケールを幾何学的に縮小します。
surrogateopt がメリット関数の最小値を見つけようとする方法は、問題の種類によって異なります。問題の種類は、境界プラスオプションの線形制約、純粋なバイナリ、バイナリプラス線形制約、および線形制約付きの一般整数です。(非線形制約はこれらの問題タイプには影響しません。)各サンプラーは、現職者の周囲のスケール領域内のポイントをサンプリングします。整数ポイントのスケールは境界の幅の 1/2 倍から始まり、非整数ポイントとまったく同じように調整されます。ただし、幅が 1 を下回る場合は幅が 1 に増加されます。
それぞれの問題タイプについて、surrogateopt は次の表に従って重みに関連付けられたサイクル内のサンプラーを選択します。
サンプラーサイクル
| 重量 | 0.3 | 0.5 | 0.8 | 0.95 |
| 境界 + オプションの線形 | ランダム | ランダム | OrthoMADS | GPS |
| 純粋なバイナリ | ランダム | ランダム | 交叉 | 交叉 |
| バイナリ + リニア | OrthoMADS | OrthoMADS | 交叉 | 交叉 |
| 整数 + 線形 | OrthoMADS | 交叉 | OrthoMADS | GPS |
ランダム — サンプラーは、現職者を中心としたスケール内で、整数ポイントを均一にランダムに生成します。サンプラーは、平均ゼロのガウス分布に従って、現職者から連続したポイントを生成します。任意の整数点のサンプルの幅はスケールで乗算され、連続点の標準偏差も同様に乗算されます。
OrthoMADS — サンプラーは直交座標系を均一にランダムに選択します。次に、アルゴリズムは、座標系内の各単位ベクトルに現在のスケールを加算および減算して、現職者の周囲にサンプル ポイントを作成します。これにより、2N 個のサンプルが作成されます (一部の整数ポイントが現在の値に丸められない限り)。ここで、N は問題の次元の数です。OrthoMADS は、2N 固定方向よりも 2 つのポイント ([+1,+1,…,+1] と [–1,–1,…,–1]) を追加して、合計 2N+2 ポイントを使用します。次に、サンプラーは 2N + 2 ステップを繰り返し半分にし、現職者の周囲にさらに細かいポイント セットを作成します。十分なサンプルがある場合、このプロセスは終了します。整数値になるべきポイントは、最も近い実行可能な整数ポイントに丸められます。OrthoMADS アルゴリズムは論文 [6] に基づいています。その論文では、座標系を生成するために準乱数の集合を使用しています。対照的に、
surrogateoptは標準の MATLAB® 疑似乱数を使用し、直交座標はqrによって生成されます。GPS (一般化パターン探索) — サンプラーは OrthoMADS に似ていますが、ランダムな方向セットを選択する代わりに、GPS は回転しない座標系を使用します。GPS アルゴリズムは論文 [5] に基づいています。このアルゴリズムについては、パターン探索ポーリングの仕組み で詳しく説明されています。
交叉 — サンプラーは
ga'crossoverarithmetic'交叉関数 (交叉オプション を参照) を使用します。交叉の母集団はsurrogateoptが評価したポイントです。母集団は4 人のプレイヤーで'selectiontournament'選択関数 (選択オプション を参照) を使用して選択されます。サンプル内のポイントの数は信頼領域のサイズによって決まります。信頼領域の半径が小さいほど、メリット関数を評価するためにサンプリングされるポイントの数が多くなります。
ソルバーは、評価ポイントの options.MinSampleDistance 内のポイントではメリット関数を評価しません (サロゲート最適化の定義 を参照)。すべてのサンプル ポイントが評価ポイントの MinSampleDistance 以内にある場合、ソルバーは最小値の探索フェーズからサロゲートの構築フェーズに切り替わります (つまり、サロゲート リセットを実行します)。通常、このリセットは、ソルバーがスケールを縮小して、すべてのサンプル ポイントが現職の周囲に密集した後に発生します。
BatchUpdateInterval オプションが 1 より大きい場合、ソルバーはサロゲート モデルを更新したり現職者を変更したりする前に、BatchUpdateInterval 適応ポイントを生成します。アップデートにはすべての適応ポイントが含まれます。実際には、アルゴリズムは BatchUpdateInterval 適応ポイントを生成するまで新しい情報を使用せず、その後、すべての情報を使用してサロゲートを更新します。
問題に整数変数がなく、非線形制約がある場合、アルゴリズムは K ステップ (次に定義) ごとにメリット関数で MultiStart fmincon を使用して探索を実行します。これは、整数制約の問題に対する ツリー探索 アルゴリズムに似ています。この fmincon 呼び出しは時間がかかりますが、より実現可能な目的関数の値につながる可能性があります。Kの値はNに依存します。
N < 15 の場合、K = max(50,10*N)。
N≥15の場合、K = max(50, 2*N)。
メリット関数の定義
メリット関数 fmerit(x) は、次の 2 つの項の重み付けされた組み合わせです。
スケールされたサロゲート。smin をサンプル ポイントの最小代替値、smax を最大値、s(x) をポイント x における代替値として定義します。そして、スケールされたサロゲートS(x)は
s(x) は非負であり、サンプル ポイントの中で最小の代替値を持つポイント x ではゼロになります。
スケールされた距離。xj、j = 1、…、k を k 評価ポイントとして定義します。dij をサンプル ポイント i から評価ポイント k までの距離として定義します。dmin = min(dij)、dmax = max(dij) に設定します。ここで、最小値と最大値はすべての i と j にわたって取得されます。スケールされた距離D(x)は
ここで、d(x) は、点 x から評価点までの最小距離です。D(x) は非負であり、評価点から最大限遠い点 x ではゼロになります。したがって、D(x) を最小化すると、アルゴリズムは評価されたポイントから離れたポイントに導かれます。
メリット関数は、スケーリングされたサロゲート関数とスケーリングされた距離の凸結合です。0 < w < 1 の重みwの場合、メリット関数は
w の値が大きいと、サロゲート値が重要になり、探索でサロゲートが最小化されます。w の値が小さいと、評価対象のポイントから遠いポイントが重要視され、新しい領域の探索が行われます。最小値の探索フェーズでは、Regis と Shoemaker [2] が示唆しているように、重み w は次の 4 つの値を循環します。0.3、0.5、0.8、0.95。
混合整数surrogateoptアルゴリズム
混合整数 surrogateopt の概要
intcon 引数で指定されているように、変数の一部またはすべてが整数の場合、surrogateopt は シリアルsurrogateoptアルゴリズム のいくつかの側面を変更します。この説明は、アルゴリズム全体ではなく、主に変更点についてです。
アルゴリズム開始
必要に応じて、surrogateopt は intcon ポイントの指定された境界を整数になるように移動します。また、surrogateopt は、指定された初期点が整数実行可能であり、境界に関して実行可能であることを保証します。次に、アルゴリズムは非整数アルゴリズムと同様に準ランダム ポイントを生成し、整数ポイントを整数値に丸めます。このアルゴリズムは、非整数アルゴリズムとまったく同じようにサロゲートを生成します。
最小値を求める整数探索
アルゴリズムのこの部分は 最小限の詳細を探索 と同じです。整数制約の変更はそのセクションに表示されます。
ツリー探索
surrogateopt は通常、メリット関数の値を数百または数千サンプリングした後、最小点を選択し、目的関数を評価します。ただし、状況によっては、surrogateopt は目的を評価する前にツリー探索と呼ばれる別の探索を実行します。これらの状況は、純粋なバイナリ問題や、境界のみがあり変数が 15 個未満の問題には適用されません。該当する場合、
ケース A と呼ばれる最後のツリー探索以降、2N ステップが経過しました。
surrogateoptは、ケース B と呼ばれるサロゲートリセットを実行しようとしています。
ツリー探索は、分枝限定法 で説明されている intlinprog の手順と同様に、次のように進行します。アルゴリズムは、整数値を見つけて、この値より 1 つ大きいか小さい境界を持つ新しい問題を作成し、この新しい境界を使用してサブ問題を解決することでツリーを作成します。サブ問題を解決した後、アルゴリズムは 1 だけ上または下に境界が設定される別の整数を選択します。
ケースA:スケーリングされたサンプリング半径を全体の境界として使用し、最大 30 ステップの探索を実行します。
ケースB:元の問題境界を全体の境界として使用し、最大 60 ステップの探索を実行します。
この場合、サブ問題を解決するということは、指定された整数値を持つ現職者から始めて、連続変数に対して fmincon 'sqp' アルゴリズムを実行し、メリット関数の局所的最小値を探索することを意味します。
ツリー探索には時間がかかる場合があります。そのため、surrogateopt には、このステップで過剰な時間を回避するための内部反復制限があり、ケース A ステップとケース B ステップの両方の数を制限します。
ツリー探索の後、アルゴリズムは MultiStart の 20 ポイント (N ≤ 10 の場合は 5 ポイント) を使用して MultiStart fmincon 探索を実行します。
ツリー探索の最後に、アルゴリズムは、メリット関数によって測定された最小値を求めて、ツリー探索で見つかったポイントと、前の探索で見つかったポイントのうち、より良いほうのポイントを選択します。アルゴリズムはこの時点で目的関数を評価します。整数アルゴリズムの残りの部分は連続アルゴリズムとまったく同じです。
線形制約処理
問題に線形制約がある場合、アルゴリズムは、反復ごとにすべての点がこれらの制約および境界に関して実行可能になるように探索手順を変更します。構築フェーズと探索フェーズでは、アルゴリズムは patternsearch 'GSSPositiveBasis2N' ポーリング アルゴリズムに類似した手順によって線形に実行可能なポイントのみを作成します。
問題に整数制約と線形制約がある場合、アルゴリズムはまず線形に実行可能点を作成します。次に、アルゴリズムは、点を線形に実行可能なままにしようとするヒューリスティックを使用して、線形に実行可能点を整数に丸めるプロセスによって、整数制約を満たそうとします。このプロセスでサロゲートを構築するのに十分な実行可能なポイントを取得できなかった場合、アルゴリズムは intlinprog を呼び出して、境界、線形制約、および整数制約に関して実行可能なポイントをさらに見つけようとします。
非線形制約を伴うsurrogateoptアルゴリズム
問題に非線形制約がある場合、surrogateopt は前述のアルゴリズムをいくつかの方法で変更します。
最初と各サロゲートのリセット後に、アルゴリズムは目的関数と非線形制約関数のサロゲートを作成します。その後、アルゴリズムは、サロゲート構築フェーズで実行可能なポイントが見つかったかどうかによって異なります。実行可能なポイントを見つけることは、サロゲートが構築されたときに既存のポイントが実行可能であることと同じです。目的関数または非線形制約関数が、ある時点で NaN と評価された場合、surrogateopt はその時点での目的関数値と制約を破棄し、その点をサロゲートの作成または更新に使用しないことに注意してください。
現職者が実行不可能である - このケースはフェーズ 1 と呼ばれ、実行可能なポイントの探索が行われます。実行可能なポイントに遭遇する前の最小値の探索フェーズでは、
surrogateoptはメリット関数の定義を変更します。アルゴリズムは、各ポイントで違反されている制約の数をカウントし、違反されている制約の数が最も少ないポイントのみを考慮します。これらのポイントの中で、アルゴリズムは最大制約違反を最小化するポイントを最良 (最も低いメリット関数) ポイントとして選択します。この一番いいところは現職です。その後、アルゴリズムは実行可能なポイントに遭遇するまで、メリット関数のこの修正を使用します。surrogateoptがポイントを評価してそれが実行可能であると判断すると、実行可能なポイントが現行ポイントとなり、アルゴリズムはフェーズ 2 になります。現職者が実行可能 - このケースはフェーズ 2 と呼ばれ、標準アルゴリズムと同じように進行します。アルゴリズムは、メリット関数を計算する目的で実行不可能なポイントを無視します。
アルゴリズムは、次の変更を加えて 混合整数surrogateoptアルゴリズム に従って進行します。アルゴリズムが目的関数と非線形制約関数を評価するすべての 2*nvars ポイントの後で、surrogateopt は fmincon 関数を呼び出して、サロゲートの非線形制約と境界に従ってサロゲートを最小化します。境界は現在のスケール係数によってスケーリングされます。(既存の目標が実行不可能な場合、fmincon は目的を無視し、制約を満たすポイントを見つけようとします。)問題に整数制約と非線形制約の両方がある場合、surrogateopt は fmincon ではなく ツリー探索 を呼び出します。
問題が実現可能性の問題である場合、つまり目的関数がない場合、surrogateopt は実行可能なポイントを見つけるとすぐにサロゲートリセットを実行します。
並列surrogateoptアルゴリズム
並列 surrogateopt アルゴリズムは、シリアル アルゴリズムと次の点で異なります。
並列アルゴリズムは、目的関数を評価するためのポイントのキューを維持します。このキューは、並列ワーカーの数より 30% 大きくなります (切り上げ)。評価できるポイントがないためワーカーがアイドル状態になる可能性を最小限に抑えるために、キューはワーカー数よりも大きくなります。
スケジューラは FIFO 方式でキューからポイントを取得し、ワーカーがアイドル状態になると非同期的にポイントを割り当てます。
アルゴリズムがフェーズ (最小値の探索とサロゲートの構築) を切り替えると、評価中の既存のポイントは引き続き使用され、キュー内のその他のポイントはフラッシュされます (キューから破棄されます)。したがって、一般に、アルゴリズムがサロゲート構築フェーズで作成するランダム ポイントの数は最大で
options.MinSurrogatePoints + PoolSizeになります。ここで、PoolSizeは並列ワーカーの数です。同様に、サロゲートリセット後も、アルゴリズムにはワーカーが評価しているPoolSize - 1適応ポイントがまだ存在します。
メモ
現在、並列サロゲート最適化では、並列タイミングの再現性がないため、必ずしも再現可能な結果が得られるわけではなく、異なる実行パスが発生する可能性があります。
並列混合整数surrogateoptアルゴリズム
混合整数問題で並列実行する場合、surrogateopt は並列ワーカーではなくホスト上でツリー探索手順を実行します。surrogateopt は、最新のサロゲートを使用して、各ワーカーが適応ポイントを返した後に、サロゲートのより小さい値を探索します。
目的関数が高価ではない (時間がかからない) 場合、このツリー探索手順はホスト上のボトルネックになる可能性があります。対照的に、目的関数のコストが高い場合、ツリー探索手順は全体の計算時間のほんの一部を占め、ボトルネックにはなりません。
参照
[1] Powell, M. J. D. The Theory of Radial Basis Function Approximation in 1990. In Light, W. A. (editor), Advances in Numerical Analysis, Volume 2: Wavelets, Subdivision Algorithms, and Radial Basis Functions. Clarendon Press, 1992, pp. 105–210.
[2] Regis, R. G., and C. A. Shoemaker. A Stochastic Radial Basis Function Method for the Global Optimization of Expensive Functions. INFORMS J. Computing 19, 2007, pp. 497–509.
[3] Wang, Y., and C. A. Shoemaker. A General Stochastic Algorithm Framework for Minimizing Expensive Black Box Objective Functions Based on Surrogate Models and Sensitivity Analysis. arXiv:1410.6271v1 (2014). Available at https://arxiv.org/pdf/1410.6271.
[4] Gutmann, H.-M. A Radial Basis Function Method for Global Optimization. Journal of Global Optimization 19, March 2001, pp. 201–227.
[5] Audet, Charles, and J. E. Dennis Jr. “Analysis of Generalized Pattern Searches.” SIAM Journal on Optimization. Volume 13, Number 3, 2003, pp. 889–903.
[6] Abramson, Mark A., Charles Audet, J. E. Dennis, Jr., and Sebastien Le Digabel. “ORTHOMADS: A deterministic MADS instance with orthogonal directions.” SIAM Journal on Optimization. Volume 20, Number 2, 2009, pp. 948–966.
