代理最適化アルゴリズム

このページは機械翻訳を使用して翻訳されました。元の英語を参照するには、ここをクリックします。

シリアル`surrogateopt`アルゴリズム

シリアルsurrogateoptアルゴリズムの概要
代理最適化の定義
代理の詳細の構築
最小限の詳細を検索
メリット関数の定義

シリアル`surrogateopt`アルゴリズムの概要

代理最適化アルゴリズムは 2 つのフェーズを交互に実行します。

サロゲートの構築 — 境界内に options.MinSurrogatePoints 個のランダムなポイントを作成します。これらのポイントで (高価な) 目的関数を評価します。これらの点を通るラジアル基底関数を補間することによって、目的関数の代理関数を構築します。
最小値の探索 — 境界内で数千のランダムな点をサンプリングして、目的関数の最小値を検索します。これらのポイントでの代理値と、それらのポイントと（高価な）目的関数が評価されたポイント間の距離に基づいて、メリット関数を評価します。メリット関数によって測定された最適なポイントを候補として選択します。最適な候補ポイントで目的関数を評価します。この点は適応点と呼ばれます。この値を使用してサロゲートを更新し、再度検索します。

代理構築フェーズでは、アルゴリズムは準ランダムシーケンスからサンプルポイントを構築します。補間ラジアル基底関数の構築には、少なくとも nvars + 1 個のサンプルポイントが必要です。ここで、nvars は問題変数の数です。options.MinSurrogatePoints のデフォルト値は、2*nvars または 20 のいずれか大きい方になります。

アルゴリズムは、すべての検索ポイントが目的関数が以前に評価されたポイントに近すぎる場合 (オプション MinSampleDistance 未満)、最小値の検索フェーズを停止します。最小限の詳細を検索を参照してください。最小値検索フェーズからのこの切り替えは、サロゲートリセットと呼ばれます。

代理最適化の定義

代理最適化アルゴリズムの説明では、次の定義を使用します。

現在 — 目的関数が最後に評価されたポイント。
現職 — 最新のサロゲートリセット以降に評価されたすべてのポイントの中で目的関数の値が最小のポイント。
ベスト - これまでに評価されたすべてのポイントの中で目的関数の値が最小のポイント。
初期 — 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 は、変数をシームレスに管理します。したがって、たとえば、初期ポイントを渡す場合は、固定変数を含む完全なセットを渡します。

後続のサロゲート構築フェーズでは、アルゴリズムは 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
境界 + オプションの線形	ランダム	ランダム	オルソMADS	GPS
純粋なバイナリ	ランダム	ランダム	交叉	交叉
バイナリ + リニア	オルソMADS	オルソMADS	交叉	交叉
整数 + 線形	オルソMADS	交叉	オルソMADS	GPS

ランダム — サンプラーは、現職者を中心としたスケール内で、整数ポイントを均一にランダムに生成します。サンプラーは、平均がゼロのガウス分布に従って、現職者から連続したポイントを生成します。任意の整数点のサンプルの幅はスケールで乗算され、連続点の標準偏差も同様に乗算されます。
OrthoMADS — サンプラーは直交座標系を均一にランダムに選択します。次に、アルゴリズムは、座標系の各単位ベクトルに現在のスケールを加算および減算して、現職者の周囲にサンプルポイントを作成します。これにより、2N 個のサンプルが作成されます (一部の整数ポイントが現在の値に丸められない限り)。ここで、N は問題の次元の数です。OrthoMADS は、2N 固定方向よりも 2 つのポイント (1 つは [+1,+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)。

メリット関数の定義

メリット関数 f_merit(x) は、次の 2 つの項の重み付けされた組み合わせです。

スケールされた代理。s_min をサンプルポイント間の最小代替値、s_max を最大値、s(x) をポイント x における代替値として定義します。すると、スケールされたサロゲートS(x)は
$S (x) = \frac{s (x) - s_{\min}}{s_{\max} - s_{\min}} .$
s(x) は非負であり、サンプルポイントの中で最小の代理値を持つポイント x ではゼロになります。
スケールされた距離。x_j、j = 1、…、k を k 評価ポイントとして定義します。d_ij をサンプルポイント i から評価ポイント k までの距離として定義します。d_min = min(d_ij)、d_max = max(d_ij) と設定します。ここで、最小値と最大値は、すべての i と j にわたって取得されます。スケール距離D(x)は
$D (x) = \frac{d_{\max} - d (x)}{d_{\max} - d_{\min}},$
ここで、d(x) は、点 x から評価点までの最小距離です。D(x) は非負であり、評価点から最大限に離れた点 x ではゼロになります。したがって、D(x) を最小化すると、アルゴリズムは評価されたポイントから離れたポイントに導かれます。

メリット関数は、スケーリングされた代理関数とスケーリングされた距離の凸結合です。0 < w < 1の重みwの場合、メリット関数は

$f_{merit} (x) = w S (x) + (1 - w) D (x) .$

w の値が大きいと、代理値が重要視され、代理が最小化されるように検索が行われます。w の値が小さいと、評価されたポイントから遠いポイントが重要視され、新しい領域の検索が行われます。最小値の探索フェーズでは、Regis と Shoemaker [2] が示唆しているように、重み w は次の 4 つの値を循環します。0.3、0.5、0.8、0.95。

混合整数 `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 は前述のアルゴリズムをいくつかの方法で変更します。

最初と各サロゲートのリセット後に、アルゴリズムは目的関数と非線形制約関数のサロゲートを作成します。その後、アルゴリズムは、サロゲート構築フェーズで実行可能なポイントが見つかったかどうかによって異なります。実行可能なポイントを見つけることは、サロゲートが構築されたときに既存のポイントが実行可能であることと同じです。

現職者は実行不可能です — このケースはフェーズ 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.

参考

surrogateopt

外部の Web サイト

https://en.wikipedia.org/wiki/Radial_basis_function