パターン探索用語

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

パターン

パターン は、パターン探索アルゴリズムが各反復で探索するポイントを決定するために使用するベクトルのセット {v _i} です。セット {v _i} は、目的関数の独立変数の数、N、および正の基底セットによって定義されます。パターン探索アルゴリズムで一般的に使用される 2 つの正の基底セットは、2 つの N ベクトルを持つ最大基底と、N+1 ベクトルを持つ最小基底です。

GPS では、パターンを形成するベクトルの集合は固定方向のベクトルです。たとえば、最適化問題に 3 つの独立変数がある場合、2 N 正基底のデフォルトは、次のパターンベクトルで構成されます:

$\begin{matrix} v_{1} = [\begin{matrix} 1 & 0 & 0 \end{matrix}] & v_{2} = [\begin{matrix} 0 & 1 & 0 \end{matrix}] & v_{3} = [\begin{matrix} 0 & 0 & 1 \end{matrix}] \\ v_{4} = [\begin{matrix} - 1 & 0 & 0 \end{matrix}] & v_{5} = [\begin{matrix} 0 & - 1 & 0 \end{matrix}] & v_{6} = [\begin{matrix} 0 & 0 & - 1 \end{matrix}] \end{matrix}$

N+1 正基底は、次のデフォルトパターンベクトルで構成されます。

GSS では、線形制約があり、現在のポイントが制約境界の近くにある場合を除き、パターンは GPS パターンと同一です。GSS が線形制約を持つパターンを形成する方法の説明については、Kolda、Lewis、および Torczon [1] を参照してください。線形制約がある場合、GSS アルゴリズムは GPS アルゴリズムよりも効率的です。効率性の向上を示す例については、patternsearch を用いた大域的最小値の探索を参照してください。

MADS では、パターンを形成するベクトルのコレクションがアルゴリズムによってランダムに選択されます。ポーリング方法の選択に応じて、選択されるベクトルの数は 2 N または N+1 になります。GPS と同様に、2 つの N ベクトルは N ベクトルとその N 負で構成され、N+1 ベクトルは N ベクトルと他のベクトルの合計の負で構成されます。

参照

[1] Kolda, Tamara G., Robert Michael Lewis, and Virginia Torczon. “A generating set direct search augmented Lagrangian algorithm for optimization with a combination of general and linear constraints.” Technical Report SAND2006-5315, Sandia National Laboratories, August 2006.

メッシュ

各ステップで、patternsearchはメッシュと呼ばれる点の集合を探索し、目的関数を改善する点を探します。patternsearchは次のようにメッシュを形成します。

各パターンベクトル v _i にスカラー Δ ^m を乗算して、ベクトルセット {d _i} を生成します。Δ ^m は メッシュサイズ と呼ばれます。
${d_{i}}$ を 現在のポイント (前のステップで見つかった最適な目的関数値を持つポイント) に追加します。

たとえば、GPS アルゴリズムを使用するとします。次の場合を考えます。

現在のポイントは[1.6 3.4]です。
パターンはベクトルから構成されます
$\begin{array}{l} v_{1} = [\begin{matrix} 1 & 0 \end{matrix}] \\ v_{2} = [\begin{matrix} 0 & 1 \end{matrix}] \\ v_{3} = [\begin{matrix} - 1 & 0 \end{matrix}] \\ v_{4} = [\begin{matrix} 0 & - 1 \end{matrix}] \end{array}$
現在のメッシュサイズ Δ ^m は 4 です。

アルゴリズムはパターンベクトルを 4 で乗算し、それを現在のポイントに追加して次のメッシュを取得します。

[1.6 3.4] + 4*[1 0] = [5.6 3.4] 
[1.6 3.4] + 4*[0 1] = [1.6 7.4] 
[1.6 3.4] + 4*[-1 0] = [-2.4 3.4] 
[1.6 3.4] + 4*[0 -1] = [1.6 -0.6]

メッシュポイントを生成するパターンベクトルは、方向と呼ばれます。

ポーリング

各ステップで、アルゴリズムは目的関数値を計算して現在のメッシュ内のポイントをポーリングします。完全なポーリング オプションが (デフォルトの) Off に設定されている場合、アルゴリズムは、目的関数の値が現在のポイントの値よりも小さいポイントを見つけるとすぐにメッシュポイントのポーリングを停止します。これが起こると、ポーリングは成功と呼ばれ、見つかったポイントが次の反復での現在のポイントになります。

アルゴリズムは、ポーリングを停止する時点までのメッシュポイントとその目的関数の値のみを計算します。アルゴリズムが目的関数を改善するポイントを見つけられなかった場合、ポーリングは失敗と呼ばれ、現在のポイントは次の反復でも同じままになります。

完全なポーリング オプションが On に設定されている場合、アルゴリズムはすべてのメッシュポイントで目的関数値を計算します。次に、アルゴリズムは最小の目的関数値を持つメッシュポイントを現在のポイントと比較します。そのメッシュポイントの値が現在のポイントよりも小さい場合、ポーリングは成功します。

拡大と縮小

ポーリング後、アルゴリズムはメッシュサイズ Δ ^m の値を変更します。デフォルトでは、ポーリングが成功した場合は Δ ^m を 2 倍にし、ポーリングが失敗した場合は 0.5 倍にします。