パターン検索ポーリングの仕組み

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

コンテキスト

patternsearch は、最適点に近づく一連の点、x0、x1、x2、... を見つけます。目的関数の値は、シーケンス内の各ポイントから次のポイントまで減少するか、同じままになります。このセクションでは、GPSアルゴリズムを使用して最適化するで説明されている関数のパターン検索がどのように機能するかについて説明します。

説明を簡略化するために、このセクションでは、デフォルトの最大正基底 2 N を使用し、ScaleMesh オプションを false に設定して、一般化パターン検索 (GPS) がどのように機能するかについて説明します。

このセクションでは、patternsearch アルゴリズムが境界または線形制約でどのように機能するかについては説明しません。境界と線形制約の場合、patternsearch は、すべての境界と線形制約を満たすように、すべての反復で実行可能になるようにポーリングポイントを変更します。

このセクションでは非線形制約は扱いません。patternsearch が非線形制約でどのように機能するかを理解するには、パターン探索のための非線形制約ソルバーアルゴリズムを参照してください。

成功した投票

パターン検索は、指定した初期ポイント x0 から始まります。この例では、x0 = [2.1 1.7] となります。

反復 1

最初の反復では、メッシュサイズは 1 であり、GPS アルゴリズムはパターンベクトルを初期ポイント x0 = [2.1 1.7] に追加して、次のメッシュポイントを計算します。

[1 0] + x0 = [3.1 1.7]
[0 1] + x0 = [2.1 2.7]
[-1 0] + x0 = [1.1 1.7]
[0 -1] + x0 = [2.1 0.7]

アルゴリズムは、上記の順序でメッシュポイントで目的関数を計算します。次の図は、初期点とメッシュ点における目的関数の値を示しています。

アルゴリズムは、メッシュポイントの目的関数値を計算して、その値が x0 の値である 4.6347 より小さいメッシュポイントが見つかるまでメッシュポイントをポーリングします。この場合、最初に見つかるポイントは [1.1 1.7] であり、目的関数の値は 4.5146 なので、反復 1 でのポーリングは成功です。アルゴリズムは、シーケンスの次の点を次のように設定します。

x1 = [1.1 1.7]

メモ

デフォルトでは、GPS パターン検索アルゴリズムは、現在のポイントよりも適合値が小さいメッシュポイントを見つけるとすぐに、現在の反復を停止します。その結果、アルゴリズムはすべてのメッシュポイントをポーリングしない可能性があります。UseCompletePoll オプションを true に設定することで、アルゴリズムですべてのメッシュポイントをポーリングできます。

反復 2

ポーリングが成功すると、アルゴリズムは現在のメッシュサイズを MeshExpansionFactor オプションのデフォルト値である 2 で乗算します。初期メッシュサイズは 1 なので、2 回目の反復ではメッシュサイズは 2 になります。反復 2 のメッシュには次の点が含まれます。

2*[1 0] + x1 = [3.1 1.7]
2*[0 1] + x1 = [1.1 3.7]
2*[-1 0] + x1 = [-0.9 1.7]
2*[0 -1] + x1 = [1.1 -0.3]

次の図は、点 x1 とメッシュポイント、および対応する目的関数の値を示しています。

アルゴリズムは、メッシュポイントをポーリングし、その値が x1 の値である 4.5146 より小さいものを見つけます。最初に見つかったポイントは [-0.9 1.7] で、ここで目的関数の値は 3.25 なので、反復 2 でのポーリングは再び成功します。アルゴリズムは、シーケンスの2番目のポイントを次のように設定します。

x2 = [-0.9 1.7]

ポーリングが成功したため、アルゴリズムは現在のメッシュサイズを 2 倍にして、3 回目の反復でメッシュサイズを 4 にします。

失敗した世論調査

4回目の反復では、現在のポイントは

x3 = [-4.9 1.7]

メッシュサイズは8なので、メッシュはポイントで構成されています

8*[1 0] + x3 = [3.1 1.7]
8*[0 1] + x3 = [-4.9 9.7]
8*[-1 0] + x3 = [-12.9 1.7]
8*[0 -1] + x3 = [-4.9 -1.3]

次の図は、メッシュポイントとその目的関数の値を示しています。

この反復では、メッシュポイントのいずれも x3 の値よりも小さい目的関数値を持たないため、ポーリングは失敗になります。この場合、アルゴリズムは次の反復で現在のポイントを変更しません。つまり、

x4 = x3;

次の反復では、アルゴリズムは現在のメッシュサイズに MeshContractionFactor オプションの既定値である 0.5 を掛けて、次の反復でのメッシュサイズが 4 になるようにします。次に、アルゴリズムはより小さなメッシュサイズでポーリングを行います。

MADS における成功した投票と失敗した投票

PollMethod オプションを 'MADSPositiveBasis2N' または 'MADSPositiveBasisNp1' に設定すると、patternsearch は異なるポーリングタイプを使用し、他のポーリングアルゴリズムとは異なる方法でポーリングに反応するようになります。

MADS ポーリングでは、各反復で新しく生成された疑似ランダムメッシュベクトルが使用されます。ベクトルは、ランダムな下三角行列の列からランダムにシャッフルされた要素です。行列の成分は 1/ $\sqrt{mesh size}$ までの整数サイズを持ちます。ポーリングでは、メッシュベクトルにメッシュサイズが掛けられるため、ポーリングポイントは現在のポイントから最大 $\sqrt{mesh size}$ になります。

失敗したポーリングは、MeshContractionFactor オプションを無視して、メッシュを 4 倍に縮小します。同様に、成功した投票では、MeshExpansionFactor オプションを無視して、メッシュが 4 倍に拡張されます。MaxMeshSize オプションの設定に関係なく、最大メッシュサイズは 1 です。

さらに、ポーリングが成功した場合、patternsearch は成功したポイントから開始して再度ポーリングを行います。この追加のポーリングでは、サイズ 1 未満のまま、係数 4 で拡張された同じメッシュベクトルが使用されます。追加の世論調査では、先ほど成功したのと同じ方向を再度調べます。

各反復での結果の表示

Display オプションを 'iter' に設定すると、各反復でのパターン検索の結果を表示できます。これにより、パターン検索の進行状況を評価し、必要に応じて options に変更を加えることができます。

この設定では、パターン検索によってコマンドラインに各反復に関する情報が表示されます。最初の4つの反復は

Iter     f-count          f(x)      MeshSize     Method
    0        1        4.63474             1      
    1        4        4.51464             2     Successful Poll
    2        7           3.25             4     Successful Poll
    3       10      -0.264905             8     Successful Poll
    4       14      -0.264905             4     Refine Mesh

Method の下のエントリ Successful Poll は、現在の反復が成功したことを示します。たとえば、反復 2 でのポーリングは成功します。その結果、f(x) の下に表示される反復 2 で計算されたポイントの目的関数値は、反復 1 の値よりも小さくなります。

反復 4 では、エントリ Refine Mesh は、投票が失敗したことを示します。その結果、反復 4 での関数値は反復 3 から変更されません。

デフォルトでは、パターン検索は、ポーリングが成功するたびにメッシュサイズを 2 倍にし、ポーリングが失敗するたびにメッシュサイズを半分にします。

さらなる反復

パターン検索は停止する前に 60 回の反復を実行します。次のプロットは、パターン検索の最初の 13 回の反復で計算されたシーケンス内のポイントを示しています。

ポイントの下の数字は、アルゴリズムがポイントを見つける最初の反復を示します。投票が失敗した後も最良のポイントは変わらないため、プロットには成功した投票に対応する反復回数のみが表示されます。たとえば、反復 4 回目と 5 回目の最適ポイントは、反復 3 回目と同じです。

投票方法

各反復で、パターン検索は現在のメッシュ内のポイントをポーリングします。つまり、メッシュポイントで目的関数を計算して、関数値が現在のポイントの関数値よりも小さい関数があるかどうかを確認します。パターン検索ポーリングの仕組みはポーリングの例を示しています。PollMethod オプションでメッシュを定義するパターンを指定できます。デフォルトのパターン 'GPSPositiveBasis2N' は、次の 2 つの N 方向で構成されます。ここで、N は目的関数の独立変数の数です。

[1 0 0...0]
[0 1 0...0]
...
[0 0 0...1]
[–1 0 0...0]
[0 –1 0...0]
[0 0 0...–1]。

たとえば、目的関数に 3 つの独立変数がある場合、GPS Positive basis 2N は次の 6 つのベクトルで構成されます。

[1 0 0]
[0 1 0]
[0 0 1]
[–1 0 0]
[0 –1 0]
[0 0 –1]。

あるいは、PollMethod オプションを 'GPSPositiveBasisNp1' に設定して、次の N + 1 方向で構成されるパターンを設定することもできます。

[1 0 0...0]
[0 1 0...0]
...
[0 0 0...1]
[–1 –1 –1...–1]。

たとえば、目的関数に 3 つの独立変数がある場合、'GPSPositiveBasisNp1' は次の 4 つのベクトルで構成されます。

[1 0 0]
[0 1 0]
[0 0 1]
[–1 –1 –1]。

パターン検索では、PollMethod として 'GPSPositiveBasis2N' ではなく 'GPSPositiveBasisNp1' を使用すると、アルゴリズムが各反復で検索するポイントが少なくなるため、実行速度が速くなることがあります。この例では説明されていませんが、'MADSPositiveBasis2N' ではなく 'MADSPositiveBasisNp1' を使用する場合も同様であり、GSS の場合も同様です。たとえば、patternsearch と Optimize を使用した制約付き最小化ライブエディタータスクの線形制約の例でパターン検索を実行すると、アルゴリズムは 'GPSPositiveBasis2N'、デフォルトの PollMethod を使用して 1588 回の関数評価を実行しますが、 'GPSPositiveBasisNp1' を使用した場合は 877 回の関数評価しか実行しません。詳細については、投票オプションの効率を比較するを参照してください。

ただし、目的関数に多数の局所最小値がある場合、'GPSPositiveBasis2N' を PollMethod として使用すると、各反復で現在のポイントの周囲のより多くのポイントが探索されるため、グローバル最小値ではない局所最小値を見つけることを回避できる可能性があります。

投票を完了する

デフォルトでは、パターン検索によって目的関数の値を改善するメッシュポイントが見つかった場合、ポーリングが停止され、そのポイントが次の反復の現在のポイントとして設定されます。この問題が発生すると、一部のメッシュポイントがポーリングされない可能性があります。これらのポーリングされていないポイントの中には、パターン検索で最初に見つかった目的関数の値よりもさらに低い目的関数の値を持つものがある可能性があります。

複数の局所最小値がある問題の場合、パターン検索で各反復で すべてのメッシュポイントをポーリングし、目的関数値が最適なものを選択することが望ましい場合があります。これにより、パターン検索では各反復でより多くのポイントを探索できるようになり、グローバル最小値ではないローカル最小値を回避できる可能性があります。UseCompletePoll オプションを true に設定して、パターン検索でメッシュ全体をポーリングします。

パターン検索の停止条件

次のいずれかの条件が発生すると、アルゴリズムは停止します。

メッシュサイズは MeshTolerance オプションよりも小さくなります。
アルゴリズムによって実行される反復回数が、MaxIterations オプションの値に達します。
アルゴリズムによって実行される目的関数評価の合計数は、MaxFunctionEvaluations オプションの値に達します。
MaxTime オプションの値に達するまでアルゴリズムが実行される時間 (秒単位)。
ポーリングが成功すると、前の 2 回の反復で見つかったポイント間の距離とメッシュサイズは両方とも StepTolerance オプションよりも小さくなります。
ポーリングが成功すると、前の 2 回の反復における目的関数の変化は FunctionTolerance オプションよりも小さくなり、メッシュサイズは StepTolerance オプションよりも小さくなります。

ConstraintTolerance オプションは停止基準として使用されません。非線形制約に関する実現可能性を決定します。

MADS アルゴリズムは、メッシュサイズ停止基準で、ポールパラメーター Δ_p と呼ばれる追加のパラメーターを使用します。

$Δ_{p} = {\begin{array}{l} N \sqrt{Δ_{m}} & for positive basis N + 1 poll \\ \sqrt{Δ_{m}} & for positive basis 2 N poll, \end{array}$

ここでΔ_mはメッシュサイズです。MADS 停止基準は次のとおりです。

Δ_p ≤ MeshTolerance .

パターン検索の堅牢性

パターン検索アルゴリズムは、目的関数の障害に対して堅牢です。つまり、patternsearch は、NaN、Inf、または複素数値になる関数評価を許容します。初期ポイント x0 の目的関数が実数の有限値である場合、patternsearch はポーリングポイントの失敗を目的関数の値が大きいものとして扱い、無視します。

たとえば、ポーリング内のすべてのポイントが NaN と評価された場合、patternsearch はポーリングが失敗したと見なし、メッシュを縮小して再評価します。投票内の 1 つのポイントでも、これまでに確認されたどのポイントよりも小さい値と評価された場合、patternsearch は投票が成功したと見なし、メッシュを拡張します。