ダウンヒルシンプレックス手順Wikipedia

Posted on February 9, 2022 by lordneo

before-content-x4

ダウンヒルシンプレックス手順 また ネルダーミードプロセス ^[初め]線形問題（シンプレックスアルゴリズム）の同名とは対照的に、いくつかのパラメーターの非線形関数を最適化する方法です。ヒルクライビングまたはダウンヒル検索手順のカテゴリに分類されます。使用できます。 B.コーナリングでも。

after-content-x4

1965年にジョンネルダーとロジャーミードによって紹介されました。

ローゼンブロック「バナナ機能」を含む

スカイブルー機能を備えた遠足

特別な機能として、このシンプレックスアルゴリズムは、関数を導き出すことなくパラメーターには適用されません。これは、合理的な努力で計算することはできません。パラメータールーム内のいくつかのポイントの機能値を賢明な比較により、値の幅を制御するレギュラファルシと同様に、値の傾向と最適性への勾配が近似されます。手順は非常に迅速に収束しませんが、シンプルで比較的堅牢です。

アルゴリズムはシンプレックスに基づいており、最も単純なボリューム

{displaystyle n}

$N$ – 次のパラメーター空間

{displaystyle n+1}

$N+1$ ポイントはクランプされています。数字の1次元では、これは2次元の三角形などのルートです。各ポイントは、パラメーターの（または変数）の（または変数）セットに対応し、各ポイントで、たとえば。 B.エラーまたはコスト値として。これらの下

after-content-x4

{displaystyle n+1}

$N+1$ その後、ポイントは「最悪」と「最高」を決定します。反復ステップから次のステップまで、これらのポイントの「最悪」は通常、新しいポイントに置き換えられます。「最良の」ポイントは、以前の最良の解決策として常に保持されています。

関数が最適化される高さのラインを備えた2つの次元の視覚化により、三角形（右側の写真）が表示されます。下部の図も参照してください。

派生がなければ、これらの派生性の病理学的挙動などのさまざまな転倒が不可能な場合、手順は一般に、派生物の最適化手順としてよりゆっくり（すなわち線形）収束しますが、はるかに堅牢です。ほとんどの最適化手順と同様に、シンプレックス手順の可能なトラップは、収束できる、または1つまたは複数のパラメーターに対して早すぎる値にプロセスが一定の値に収縮することを予想外に予想外の局所最小値（または-optima）です。

ダウンヒルシンプレックス手順のフローチャート

ダウンヒルシンプレックスプロセスは、関数のローカル最適な最適を見つけます

{displaystyle n}

$N$ 変数（パラメーター）。ターゲット関数があります

{displayStyle F：Mathbb {r} ^{n} rightArrow mathbb {r}}

$f: R^N rightarrow R$ ソリューション空間の各ポイントに値（ソリューションの品質）を割り当てます。

{displaystyle alpha、gamma、beta、sigma in mathbb {r}}

${displaystyle alpha ,gamma ,beta ,sigma in mathbb {R} }$ アルゴリズムのパラメーターです。

選ぶ ${displaystyle n+1}$
ターゲット関数の値に従ってポイントを並べ替えます ${displaystyle f}$
最悪のポイントを除くすべての人の焦点を形成します。 ${displaystyle m = {frac {1} {n}} sum nolimits _ {i = 0}^{n-1} x_ {i}}}}$
中央の最悪のポイントを反映してください： ${displaystyle r = m+alpha（m-x_ {n}）}$
もしも ${displaystyle r}$
もしも ${displaystyle r}$
多分 ${displaystyle h}$
もしも ${displaystyle c}$
シンプレックスを圧縮する：それぞれ ${displaystyle iin {1、cdots、n}}$
ステップ2に進みます

これらの規則によれば、収束基準が満たされるまで反復は継続されます。シンプレックスはローカルの最適にシフトし、最終的にその周りに収縮します。

{displaystyle n+1}

$N+1$ 最初のポイントを選択して、寸法の単純なものを持つようにする必要があります

{displaystyle n}

$N$ スパンであり、すべてがより小さな寸法の双曲線にあるわけではありません。 H.ベクトル

{displaystyle x_ {1} -x_ {0}、x_ {2} -x_ {0}、…、x_ {n} -x_ {0}}}}

${displaystyle x_{1}-x_{0},x_{2}-x_{0},...,x_{N}-x_{0}}$ 独立している必要があります。 zができます。 B.出発点としてポイントを選択します

{displaystyle n}

$N$ パラメーターのいずれかを1つの異なる係数のいずれか（パラメーターが0にできない場合）または0の異なるサマンドのいずれかによって増加することにより、さらに決定します。または、各パラメーターの2つの異なる値を指定し、すべての最初の値と他の値で最初のポイントを計算します

{displaystyle n}

$N$ また、初期値でポイントがあり、パラメーターの1つが2番目の値に置き換えられることのみです。
または、ソリューションスペースからランダムなポイントを選択します。

2Dでのネルダーミードアルゴリズムの反復。

Beispielergebnis

写真は、プログラムの実行の結果を示しています。赤と青の線は、谷や山のギャップラインを表しています。傾斜レベルの地区の溝です。ここで興味があります地元円内の最小。シンプレックスイーストレーションは、赤い線の交差点で最小値を見つけます。の

{displaystyle x}

$x$ – と

{displaystyle y}

$y$ 方向の範囲は0から4のグラフィックの範囲です。

他の手順と同様に、二次的な最適が収束されるというリスクが常にあります。
この危険は、いくつかの措置によって減少することができます。

特定の数の手順によると、セットアップされます。これを行うために、これまでの最良のポイントは維持され、パラメーターzの座標（のみ）がその周りに新しいスタートシンプレックスが構築されます。 Bは5％変化します。
まさに同じように、追加のシンプレックスポイントのみがランダムな値によってさらに柔軟です。
固定された数の手順に従ってそのような措置を講じる代わりに、時間はイテレーションの現在の状態に応じて依存することもできます。これを行うには、もちろん、問題はあなたがそれを確信できることをよりよく知られている必要があります。
または、新しい設定変数の時間をランダムにすることもできます。
追加のセキュリティの質問は、パラメーターの1つだけが時期尚早に到着したことを傍受する可能性があり、1つは特別な治療を受ける可能性があります。

これらのバリアントはすべて、それぞれの特定の問題に集中的な先入観を必要としますが、残念ながら、これに一般的に適用可能な調理レシピはありません。

単一の分析機能が必要ない場合

{displaystyle n}

$N$ パラメーターを最適化（座標）、
ただし、理論関数を測定曲線に調整することは、わずかな追加ステップにのみ必要です。
最適化される関数として、断層の正方形はしばしば使用されます。つまり、個々の測定値（曲線ポイント）と同じ違いの違いの正方形からの合計と、同じものの理論的機能値、それにより、片手の片手は

{displaystyle x}

$x$ – 測定曲線に依存し、さらに

{displaystyle n}

$N$ パラメーター。エラーの二乗量からルートを引き出しているかどうかは、シンプレックス手順には関係ありません。最小の正方形の方法も参照してください。

ただし、ダウンヒルシンプレックス手順は非常に柔軟です（Levenberg Marquardtアルゴリズムとは異なります）ため、状況に応じて最適化のために他の機能を使用することもできます。

pseudocode（c-like）：

//宣言

//ユーザー仕様、入力
int np = ...; // fqs（）に入るパラメーターの数
                     //また「パラメータールームの寸法」

double parp [np] = {...}; //プライマリパラメーターセット
double pars [np] = {...}; //セカンダリパラメーターセット、変動幅を指定します

double fqs（int pf）//最小化する機能、ハング
  {//パラメーターからpar0 [pf] [...]から。
    ... //問題に応じて作成する必要があります。
                     //パラメーターセット番号PFのためにそれらを書く
  } //計算され、最後にpar0 [pf] [0]（以下を参照）
                     //保存されます。

//エンドユーザー仕様

//初期化

//シンプレックスパラメーター
double na = 1、nb = .5、nc = 2; //アルファ、ベータ、ガンマ

//パラメーターセット、シンプレックス自体のnp+1ピースに加えて、さらに3個
double par0 [np+4] [np+1];
//この1番目のインデックスで：0..NP（NP+1）シンプレックスのパラメーターセット、
//常に0のシンプレックスの最悪のポイント、
//常に1のシンプレックスの最良のポイント
// np+1ポイントp*、uを参照してください。
// np+2ポイントp **、uを参照してください。
// np+3センターP-quer of the Simplex、uを参照してください。
// 2番目のインデックス：0この文のエラー値
// 1..NPこの文の個々のパラメーター値

//初期化

//一次値と二次値で作られたシンプレックス
パラメーターを公開して、プライマリ値で0からNPを設定します。
パラメーターでは、それぞれ1に1を設定します（i）
   パラメーター番号Iを二次値で公開します。

//初期エラー合計の計算
パラメーターの場合、0からNPを設定します：feh = fqs（i）; //結果をpar0 [i] [0]に保存します。

//イテレーション用のループ、メインループ
bool finish = false;
while（！done）
    NT ++; // Simplex-StepNo.NT

    //最悪のポイントと最良のポイント（最高または最低のエラー値）を決定する
    文番号0のエラー値の値fminおよびfmaxが先行します。
    1からNPまでのすべてのパラメーターについて：
       文番号のエラーがある場合、私はfmaxよりも大きい：
          さらに悪い点では、FMAXはこの値を交換し、No。0でポイントを交換しました
       文章のエラーがFMINよりも小さい場合：
          さらに良い点、この値のfmin、No。1との交換ポイント

    //収束クエリ、終了しましたか？
    //これは、問題に応じて個別に作成する必要があります。
    //ここで例として、すべてのパラメーターが残り1‰しかないという条件
    //変動します。

    完成= true;
    0からNPまでのすべてのパラメーターのすべてのパラメーターについて：
       パラメーターのみの場合、値の相対偏差
          0.001を超える最悪のポイントと最良のポイントの間、次のとおりです。
             終了= false; // まだ終わっていません

    //終了したら、アルゴリズムの結果として最良のPAR0 [1] [1..3]で終了します

    //インデックスNP+3に従ってシンプレックスの中央P QUER
    文の平均値1からNP（つまり、最悪のポイントなし0！）
       NP+3を文章として保存します。

    //最悪のポイントを反映してポイントP*
    //インデックスNP+1に従って、中央のP-quer（nelder/meadパラメーターalpha = na）で
    パラメーター文内：
       par0 [np+1] [i] =（1+na） * par0 [np+3] [i] -na * par0 [0] [i];
    fs = par0 [np+1] [0] = fqs（np+1）; //エラーを計算します

    //改善が達成されるかどうか、その後の開示
    fsの場合 = fmin //これまでのところ最良のポイントとの比較
    | //それ以上の改善はありません：index 0の後にp **、p*を破棄します、
    | | //これまでの最悪の値を新しい（わずかに優れた）に置き換える
    |コピーパラメーターセット番号NP+1 No. 0に従って。
    | else // fs> = fminから
    | //はい、改善も！
    | | // P*よりも優れていますか？
    | | fs> par0 [np+1] [0]の場合
    | | //いいえ、P*を使用し続けるため、インデックス0で最悪のものを置き換えます
    | |コピーパラメーターセット番号NP+1 No. 0に従って。
    | | else // by fs> par0 [np+1] [0]
    | | //はい、p **を使用し続けるので、インデックス0で最悪のものを置き換えます
          コピーパラメーターセット番号0に従ってNP+2。

    else // fsから fmax //これまでのところ最悪よりも悪いですか？
    | | //はい、最初に何もしません
    | | else // by fs> fmax
    | | //いいえ、だから少なくともこれまでのところ最悪のポイントを交換してください
    |コピーパラメーターセット番号NP+1 No. 0に従って。
    | //最悪のポイント間の収縮による新しいポイントp **（インデックス0）
    | //インデックスNP+2に従って（NELDER/MEADパラメーターベータ= nbを使用して、インデックスNP+3）（インデックスNP+3）
    |パラメーター文内：
    | par0 [np+2] [i] = nb * par0 [0] [i]+（1 -nb） * par0 [np+3] [i];
    | fs = par0 [np+2] [0] = fqs（np+2）; //エラーを計算します
    | // p **前の最悪のポイントよりも優れていますか？
    | fsの場合  ジョン・アシュワース・ネルダー、ロジャー・ミード： 機能最小化のためのシンプレックス方法 。 Computer Journal、1965、7、308–313（ PDFファイルとしての元のテキスト 、543 kb） 
 ウィリアム・H・プレス、サウル・A・テコルスキー、ウィリアム・T・ベッターリング、ブライアン・P・フラナリー： cの数値レシピ 。 Foundation Books 2007、ISBN 978-8185618166。 
 ジェフリー・C・ラガリアス、ジェームズ・A・リード、マーガレット・H・ライト、ポール・E・ライト： 低次元でのネルダーミードシンプレックス法の収束特性 。の： 最適化に関するサイアムジャーナル 。 バンド  9 、 いいえ。  初め 、1998、 S.  112–147 、doi： 10.1137/s1052623496303470 。  
 ラリー・ナザレ、ポール・ツェン： Gilding the Lily：ゴールデンセクション検索に基づくNelder-Meadアルゴリズムのバリアント 。計算最適化とアプリケーション、BD。 22（2002）、nr。 1、S。133–144 
 ササシンガー、サンジャシンガー： Nelder-Mead検索アルゴリズムの効率的な実装。 適用された数値分析と計算数学、BD。 1（2004）、nr。 2、S。524–534（Zusammenfassung） 
 マルコ・A・ルーザーセン、ロドルフ・ザ・リッチ： エンジニアリング最適化のためのグローバル化されたネルダー - メード方法。 コンピューターと構造82（2004）、S。2251–2260 
 AndrejPrša、TomažZwitter： アダプトされたNelder＆Meadのダウンヒルシンプレックス方法を、食い込めるバイナリの完全に自動化された分析に導入します。 In：C。Turon、K。S。O'Flaherty、M。A。C. Perryman（hrsg。）： ガイアとの三次元の宇宙 （ESA SP-576）。 Proc。ガイアシンポーズ。 2004、ESA Publications Division、Nordwijk 2005、S。611-614 
 デビッド・バイアット、イアン・クープ、クリス・プライス： Nelder-Meadアルゴリズムの40年 （PDFファイル; 3.46 MB） 
 フチャン・ガオ、リックス・ハン： 適応パラメーターを使用したNelder-Mead Simplexアルゴリズムの実装。 計算最適化とアプリケーション51（2012）、NR。 1、S。259–277 
 ジェフリー・C・ラガリアス、ビョルン・プーネン、マーガレット・H・ライト： 2次元での制限されたネルダーミードアルゴリズムの収束。 Siam J. Optimization 22（2012）、nr。 2、S。501–532 
 ↑  ネルダー、ミード 機能最小化のためのシンプレックス方法 、コンピュータージャーナル、バンド7、1965、S。308–313

after-content-x4

ダウンヒルシンプレックス手順Wikipedia

Recent Posts

Recent Comments

Archives

Categories

Meta