Home > ソフトウエア | 技術 > NelderのSimplex法のクラスを書いてみた

NelderのSimplex法のクラスを書いてみた

自分が直面している問題の中に,最小二乗法のような最適化処理が含まれている場合,
それを解くための多くの真面目な(?)方法では
自分が最小化したい関数のGradient(関数を各パラメタで偏微分したもの)だとか
Hessian(それらをさらに偏微分したもの)だとかが必要になるので,
それらの大量の数式を計算するコードを用意せねばなりません.
そういった部分の実装は後でちゃんとやりたいという思いはあるのだけれども,
とりあえずまずは簡易的な実装で動きを見てみたい,ということが度々あります.

そんなときに使える方法として“Nelderの滑降シンプレックス法(Downhill Simplex Method)”があります.
この方法は,n次元のパラメタ空間の中に(n+1)個の頂点を持つSimplexとよばれる多面体みたいなものを用意して,これを頂点位置を変えながら変形させていくことでパラメタ値を更新していく,という探索法です.
他の方法と比べて遅いものの,
Gradient等を必要としないので比較的簡単に試してみることができるのが(+アルゴリズムが直感的に分かりやすいのも)利点です.
で,この滑降シンプレックス法を使う機会が結構でてきたりしたので,基本動作部分をクラスにまとめてみました.

適当に動かしてみたサンプルの動作が↓のグラフです.
Nelder_Simplex(クラスとそれを使う適当なサンプルのソースコード)

データ点群(青)に対してsin波形な関数の当てはめを行っています.
赤がてきとーに与えた初期値での関数の様子です.(本当は,初期値はてきとーではダメ.)
どう見てもデータ点群に対するまともな初期値とは言い難い状態ですが,
走らせてみるとそこそこ頑張ってくれて,オレンジ色のグラフのようになりました.
この結果は初期値と比べると断然良いですが,もう少し頑張れそうなのに途中で力尽きた感があります.
そこで,滑降Simplex法での探索を,この結果を新たな初期値として再出発させてみると,
今度は緑色のグラフの結果に収束しました.

このように,滑降Simplex法(に限らずだと思いますが)では探索途中で動けなくなってしまう場合があるため,
止まった地点でSimplexを再構築して再出発させてみる必要があります.

パラメタ個数が少なくて計算時間があまり問題にならない場合や,他の解き方があるのだけれどもその実装を用意するのがめんどくさい,とかいう場面では結構使えると思います.

y = A*sin(B*x+C)+D の当てはめ

y = A*sin(B*x+C)+D の当てはめ

by nakiusagi3

Home > ソフトウエア | 技術 > NelderのSimplex法のクラスを書いてみた

Search
Feeds
Meta

Return to page top