Nelder-Mead法
[Wikipedia|▼Menu]

ネルダー?ミード法(ネルダー?ミードほう、: 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\}} } } }}


次ページ
記事の検索
おまかせリスト
▼オプションを表示
ブックマーク登録
mixiチェック!
Twitterに投稿
オプション/リンク一覧
話題のニュース
列車運行情報
暇つぶしWikipedia

Size:23 KB
出典: フリー百科事典『ウィキペディア(Wikipedia)
担当:undef