Nelder–Mead法 (ネルダーミードほう、英 : Nelder–Mead method )や滑降シンプレックス法 (英 : downhill simplex method )やアメーバ法 (英 : amoeba method )は、最適化問題 のアルゴリズム 。導関数は不要。1965年 に John A. Nelder と Roger Mead が発表した[1] 。
概要 n + 1 個の頂点からなる n 次元の単体 (シンプレックス)をアメーバのように動かしながら関数の最小値を探索する。反射、膨張、収縮の3種類を使い分けながら探索する。
R の汎用的最適化の optim() のデフォルトのアルゴリズムとしても使われている。
線形計画法の1つであるシンプレックス法 と名前はまぎらわしいが、基本的に無関係である。
擬似コード f ( x ) {\displaystyle f({\textbf {x}})} の最小化を行う。 x {\displaystyle {\textbf {x}}} は n 次元のベクトル 。関数の引数は探索開始点。定数は一般的には α = 1 , γ = 2 , ρ = 1 / 2 , σ = 1 / 2 {\displaystyle \alpha =1,\gamma =2,\rho =1/2,\sigma =1/2} を使用する。 e i {\displaystyle {\textbf {e}}_{i}} は単位ベクトル。
function nelderMead( x 1 {\displaystyle {\textbf {x}}_{1}} ) { x i + 1 = x 1 + λ e i for all i ∈ { 1 , … , n } {\displaystyle {\textbf {x}}_{i+1}={\textbf {x}}_{1}+\lambda {\textbf {e}}_{i}{\text{ for all i }}\in \{1,\dots ,n\}} while (所定のループ回数 や 値の改善が小さくなった) { f ( x 1 ) ≤ f ( x 2 ) ≤ ⋯ ≤ f ( x n + 1 ) {\displaystyle f({\textbf {x}}_{1})\leq f({\textbf {x}}_{2})\leq \cdots \leq f({\textbf {x}}_{n+1})} となるようにソートする。 // 重心( x n + 1 {\displaystyle {\textbf {x}}_{n+1}} は除外) x 0 = 1 n ∑ i = 1 n x i {\displaystyle {\textbf {x}}_{0}={\frac {1}{n}}\sum _{i=1}^{n}{\textbf {x}}_{i}} x r = x o + α ( x o − x n + 1 ) {\displaystyle {\textbf {x}}_{r}={\textbf {x}}_{o}+\alpha ({\textbf {x}}_{o}-{\textbf {x}}_{n+1})} if ( f ( x 1 ) ≤ f ( x r ) < f ( x n ) ) {\displaystyle (f({\textbf {x}}_{1})\leq f({\textbf {x}}_{r})<f({\textbf {x}}_{n}))} { // 反射 x n + 1 = x r {\displaystyle {\textbf {x}}_{n+1}={\textbf {x}}_{r}} } else if ( f ( x r ) < f ( x 1 ) ) {\displaystyle (f({\textbf {x}}_{r})<f({\textbf {x}}_{1}))} { // 膨張 x e = x o + γ ( x r − x o ) {\displaystyle {\textbf {x}}_{e}={\textbf {x}}_{o}+\gamma ({\textbf {x}}_{r}-{\textbf {x}}_{o})} if ( f ( x e ) < f ( x r ) ) {\displaystyle (f({\textbf {x}}_{e})<f({\textbf {x}}_{r}))} { x n + 1 = x e {\displaystyle {\textbf {x}}_{n+1}={\textbf {x}}_{e}} } else { x n + 1 = x r {\displaystyle {\textbf {x}}_{n+1}={\textbf {x}}_{r}} } } else { // 収縮 x c = x o + ρ ( x n + 1 − x o ) {\displaystyle {\textbf {x}}_{c}={\textbf {x}}_{o}+\rho ({\textbf {x}}_{n+1}-{\textbf {x}}_{o})} if ( f ( x c ) < f ( x n + 1 ) ) {\displaystyle (f({\textbf {x}}_{c})<f({\textbf {x}}_{n+1}))} { x n + 1 = x c {\displaystyle {\textbf {x}}_{n+1}={\textbf {x}}_{c}} } else { x i = x 1 + σ ( x i − x 1 ) for all i ∈ { 2 , … , n + 1 } {\displaystyle {\textbf {x}}_{i}={\textbf {x}}_{1}+\sigma ({\textbf {x}}_{i}-{\textbf {x}}_{1}){\text{ for all i }}\in \{2,\dots ,n+1\}} } } } }
脚注 ^ Nelder, John A.; R. Mead (1965). “A simplex method for function minimization”. Computer Journal 7 : 308–313. doi :10.1093/comjnl/7.4.308. ウィキペディア、ウィキ、本、library、論文、読んだ、ダウンロード、自由、無料ダウンロード、mp3、video、mp4、3gp、 jpg、jpeg、gif、png、画像、音楽、歌、映画、本、ゲーム、ゲーム。