パターン検索用語

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

パターン

パターン は、パターン検索アルゴリズムが各反復で検索するポイントを決定するために使用するベクトルのセット {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 アルゴリズムよりも効率的です。効率向上の例については、投票オプションの効率を比較するを参照してください。

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

参照

[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]

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

投票

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

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

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

拡大と縮小

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