Main Content

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

パターン検索がワシントン山を登る

ライブ スクリプトを開く

この例では、パターン検索によって関数が最適化される様子を視覚的に示します。この関数は、x-y 位置の関数として、ワシントン山付近の地形の高さを表します。ワシントン山の頂上を見つけるには、高さの負の数である目的関数を最小化します。(この例のワシントン山は、米国北東部の最高峰です。)

米国地質調査所は、グリッド上の x-y 位置の関数として地形の高さに関するデータを提供しています。任意のポイントでの高さを評価できるように、目的関数は近くのグリッド ポイントから高さを補間します。

もちろん、max 関数を使用して、グリッド上で指定された高さの最大値を単純に見つける方が速くなります。この例のポイントは、パターン検索アルゴリズムがどのように動作するかを示すことです。このアルゴリズムは、グリッド ポイントだけでなく、連続領域上で定義された関数に対しても機能します。また、目的関数を評価するのに計算コストがかかる場合は、max 関数で要求されるように完全なグリッドでこの評価を実行すると、グリッド ポイントの小さなサブセットをサンプリングするパターン検索アルゴリズムを使用するよりもはるかに効率が悪くなります。

パターン検索の仕組み

パターン検索は、ポーリングと呼ばれる次の方法で目的関数の局所最小値を見つけます。この説明では、パターン検索量を説明する単語は太字で表記されています。検索は最初のポイントから始まり、最初のステップでは 現在のポイント として取得されます。

1.通常は座標方向のプラスとマイナスに メッシュ サイズ を掛けた点の パターン を生成し、このパターンを 現在の点 の中央に配置します。

2.パターン のすべてのポイントで目的関数を評価します。

3.パターン の最小目標が 現在のポイント の値よりも低い場合、ポーリングは 成功 となり、次の処理が行われます。

3a.見つかった最小のポイントが 現在のポイント になります。

3b.メッシュ サイズ が 2 倍になります。

3c.アルゴリズムはステップ 1 に進みます。

4.投票が 成功 しなかった場合、次のことが起こります。

4a.メッシュ サイズ が半分になります。

4b.メッシュ サイズがしきい値を下回ると、反復は停止します。

4c.それ以外の場合は、現在のポイントが保持され、アルゴリズムはステップ 1 に進みます。

この単純なアルゴリズムは、いくつかの小さな変更を加えることで、最適化のための堅牢で簡単な方法を提供します。目的関数の勾配は必要ありません。制約にも適していますが、この例と説明では制約のない問題のみを扱います。

パターン検索の準備

パターン検索を準備するには、472 x 345 グリッドの USGS データを含む mtWashington.mat にデータをロードします。標高 Z はフィートで表されます。ベクトル x と y には、それぞれ東方向と北方向のグリッド間隔の基本値が含まれます。データ ファイルには、検索の開始点 X0 も含まれています。

load mtWashington

目的関数の計算とプロット ルーチンを実行する 3 つの MATLAB® ファイルがあります。内容は以下のとおりです。

1. terrainfun は、任意の x-y 位置で高さの負の値を評価します。terrainfun は、MATLAB 関数 interp2 を使用して 2 次元線形補間を実行します。Z データを取得し、すべての x-y ポイントでの高さの負数を評価できます。

2. psoutputwashington は、ワシントン山の 3D レンダリングを描画します。さらに、実行が進むにつれて、各ポイントの周囲に、以前訪れたポイントよりも良い (高い) 球が描画されます。

3. psplotwashington は、ワシントン山の等高線地図を描き、走行速度を制御するスライダーを監視します。パターン検索アルゴリズムが最適値を探す場所を、そのポイントに + 記号を描画することで示します。また、各ポイントの周囲に、以前に訪れたポイントよりも優れた球体を描画します。

この例では、patternsearch は terrainfun を目的関数として使用し、psoutputwashington を出力関数として使用し、psplotwashington をプロット関数として使用します。patternsearch に渡す関数を匿名関数構文で準備します。

mtWashObjectiveFcn = @(xx) terrainfun(xx, x, y, Z);
mtWashOutputFcn    = @(xx,arg1,arg2) psoutputwashington(xx,arg1,arg2, x, y, Z);
mtWashPlotFcn      = @(xx,arg1) psplotwashington(xx,arg1, x, y, Z);

パターン検索オプション設定

次に、パターン検索のオプションを作成します。このオプション セットでは、メッシュ サイズが 1 未満に縮小するとアルゴリズムが停止し、メッシュはスケールされず (各方向で同じサイズ)、初期メッシュ サイズが 10 に設定され、出力関数とプロット関数が設定されます。

options = optimoptions(@patternsearch,'MeshTolerance',1,'ScaleMesh',false, ...
    'InitialMeshSize',10,'UseCompletePoll',true,'PlotFcn',mtWashPlotFcn, ...
    'OutputFcn',mtWashOutputFcn,'UseVectorized',true);

パターン検索の進行を観察する

この例を実行すると、2 つのウィンドウが表示されます。1 つは、ワシントン山の 2 次元等高線マップ上でパターン検索アルゴリズムが選択したポイントを示しています。このウィンドウには、アルゴリズムの反復間の遅延 (パターン検索の仕組みの説明のステップ 1 に戻るとき) を制御するスライダーがあります。実行速度を速くするにはスライダーを低い位置に設定し、実行速度を遅くするにはスライダーを高い位置に設定してください。

もう一方のウィンドウには、ワシントン山の 3 次元プロットと、パターン検索アルゴリズムが実行する手順が表示されます。実行中にこのプロットを回転させて、さまざまなビューを取得できます。

[xfinal ffinal] = patternsearch(mtWashObjectiveFcn,X0,[],[],[],[],[], ...
    [],[],options)
patternsearch stopped because the mesh size was less than options.MeshTolerance.


xfinal = 1×2

      316130     4904295


ffinal = -6280

最後のポイント xfinal は、パターン検索アルゴリズムが終了した場所を示します。これは、ワシントン山の頂上の x-y 位置です。最終的な目的関数 ffinal は、ワシントン山の高さ 6280 フィートの負の値です。（ワシントン山天文台によれば、これは 6,288 フィートになるはずです）。

ファイル terrainfun.m、psoutputwashington.m、psplotwashington.m を調べて、補間とグラフィックスがどのように機能するかを確認します。

パターン検索アルゴリズムには多くのオプションが用意されています。たとえば、アルゴリズムは、パターン内のすべてのポイントをポーリングするのではなく、改善点として見つかった最初のポイントを取得できます。さまざまな順序でポイントをポーリングできます。また、投票には決定論的パターンとランダムパターンの両方を使用できます。詳細については、Global Optimization Toolbox ユーザーズ ガイドを参照してください。

関連するトピック