焼きなまし法

最近加速アルゴリズムや最大値発見アルゴリズムを勉強しているのですが、ちょっと思い立って、Haskellで焼きなまし法を書いてみた。

とはいえ、動作を確認したかっただけなので、
こちらのブログを参考にさせてもらい、そのまま書き下しただけですが。
ソースコードはAnnealing.hsに置いてます

適当にコードを書いて走らせた結果、-1.21付近に値が収束しました。
探索中の値は初期条件によって変わりますが、確かに最大値に収束しています。
関数値は、

f(-1.21) = 29.99555..
f(-1.92) = 9.061711..

となり、グラフを描いてみても実際正しそう。

まあただ、ものすごく適当に書いたのもあり、速度が非常に遅いです...

これを高速化するにはどうすればいいのだろう...

今回は計測する温度値を500個とってきてますが、実際には200回や150回でも十分に収束します。
開始温度点は今回は関係ないデスが、冷却状態によって収束を判断する場合には初期温度も重要な決定項目になり、
また、ある温度での反復探索処理回数も大きく効いてきます。
上のデータは、反復回数100回、温度開始点1000、サンプル温度数500で計測したものですが、
反復回数は本ケースでは60回もあれば欲しい値を得られます。

ここまでくると大分速度は向上しましたが、
他にも温度低下率の調整や計算途中での低下率操作などを加えることでより高速な収束状態を導けるかもしれません。

対象とするデータによって変わってきますが、個人的には設計項目が多くて楽しい問題だと感じました