パターン探索（直接探索、導関数フリー探索、ブラックボックス探索とも呼ばれる）は、勾配を必要としない数値最適化手法の一種です。そのため、連続関数や微分可能でない関数にも適用できます。そのようなパターン探索手法の一つに「収束」（下記参照）があり、これは正基底理論に基づいています。最適化は、多次元解析空間における可能性の中から最適な解（誤差値が最小となる解）を見つけようとします。
歴史
「パターン探索」という名称は、フックとジーヴスによって考案されました[ 1 ] 。初期の単純な変種は、ロスアラモス国立研究所で働いていたフェルミとメトロポリスによって考案されたとされています。ダビドン[ 2 ]はそれを以下のように説明しています。
彼らは、一度に 1 つの理論パラメータを同じ大きさのステップで変化させ、いずれのパラメータの増加または減少でも実験データへの適合がさらに改善されなかった場合は、ステップ サイズを半分にして、ステップが十分に小さくなるまでこのプロセスを繰り返しました。
収束
収束はYuによって提案されたパターン探索法であり、彼は正基底理論を用いて収束することを証明した。[ 3 ]その後、Torczon、Lagarias、および共著者[ 4 ] [ 5 ]は、正基底技術を用いて、特定の関数クラスにおける別のパターン探索法の収束を証明した。このようなクラス以外では、パターン探索は、いくつかの問題に対して有用な近似解を提供できるヒューリスティックであるが、他の問題では失敗する可能性がある。このようなクラス以外では、パターン探索は解に収束する反復法ではない。実際、パターン探索法は、比較的扱いやすい問題では非定常点に収束することがある。[ 6 ] [ 7 ]
参照
- 黄金分割検索は、概念的には PS と似ており、検索範囲を狭めますが、対象は 1 次元の検索空間のみです。
- ネルダー・ミード法（別名シンプレックス法）は、多次元検索空間の検索範囲を狭めるという点で PS と概念的に似ていますが、n次元検索空間に対してn + 1 点を維持することでこれを実現します。一方、PS 法では 2 n + 1 点（中心点と各次元の 2 点）を計算します。
- Luus–Jaakola は現在の位置を囲む均一分布からサンプリングし、サンプリング範囲を指数関数的に減少させる簡単な式を使用します。
- ランダム検索は、現在の位置を囲む超球面からサンプリングする最適化手法の関連ファミリーです。
- ランダム最適化は、現在の位置を囲む正規分布からサンプリングする、関連する最適化手法のグループです。
参考文献
- ^フック、R.;ジーブス、TA (1961)。」数値的および統計的問題の「直接探索」による解決法。ACMジャーナル。8 （ 2 ）：212-229。doi：10.1145/321062.321069。S2CID 10905054。
- ^ Davidon, WC (1991). 「最小化のための可変メトリック法」. SIAM Journal on Optimization . 1 (1): 1– 17. CiteSeerX 10.1.1.693.272 . doi : 10.1137/0801001 . S2CID 1819475 .
- ^ *ユウ、ウェンシー。 1979. 「肯定的な根拠と直接検索技術のクラス」。 Sinica [ Zhongguo Kexue ]: 53—68。
- ユウ、ウェン・シー。 1979. 「シンプレックス進化手法の収束特性」。Scientia Sinica [ Zhongguo Kexue ]: 69–77。
- ^ Torczon, VJ (1997). 「パターン探索アルゴリズムの収束について」(PDF) . SIAM Journal on Optimization . 7 (1): 1– 25. CiteSeerX 10.1.1.50.3173 . doi : 10.1137/S1052623493250780 .
- ^ Dolan, ED; Lewis, RM; Torczon, VJ (2003). 「パターン探索の局所収束について」(PDF) . SIAM Journal on Optimization . 14 (2): 567– 583. CiteSeerX 10.1.1.78.2407 . doi : 10.1137/S1052623400374495 . hdl : 2060/20000109966 . S2CID 4226940 .
- ^ * Powell, Michael JD 1973.「最小化アルゴリズムの探索方向について」数理計画4:193—201。
- ^ * McKinnon, KIM (1999). 「ネルダー・ミード単体法の非定常点への収束」. SIAM J. Optim . 9 : 148–158 . CiteSeerX 10.1.1.52.3900 . doi : 10.1137/S1052623496303482 . (アルゴリズムの概要はオンラインで参照できます)。
