pythonでシミュレーテッドアニーリング(SA法)のシミュレーションをしてみた

公開日： 2014/06/08 : 未分類

どうも！　今回は、最近扱ったプログラミングについて紹介したいと思います。

数学や、統計や物流などでよく扱われる、「最適解」を求める方法はいくつかあります。

こういう問題は、グラフにすると一目瞭然なのですが、コンピュータに計算させるとなるとなかなか難しいものです。

SA法が出来る前に、山登り法（ヒルクライム法）という手法がありました。

図のように、このグラフの最大値を求めろという問題があったとします。

山登り法は、初期値がランダムで与えられて、そこからx軸の前後を比較し、良い解に進んでいくという手法です。

この山登り法では、局所解や、局所最適解、最適解どれかにはたどり着くことはできますが、最適解にたどり着く可能性は低いという問題点がありました。

そこで、局所解に陥ったとしても、なんとか抜け出して最適解に近づいていくアルゴリズムを持った手法が提案されました。　それが、シミュレーテッドアニーリング（以下SA法)という手法です。

SA（シミュレーテッド・アニーリング）法とは？

シミュレーテッド・アニーリング（Simulated Annealing：SA）は、Kirktpatrickらによって提案された組み合わせ最適化問題を解く汎用近似解法の一つである。
ほとんどの組み合わせ問題は、問題が大きくなると組み合わせ数が指数的に増大するために真の最適解を求めるのが実質的に不可能になってしまうのに対し、SAでは局所探索をランダムに繰り返し行うことで解を求める。更に解に改良が見られない場合でも確率的に改悪方向への移動を認めるために局所解に陥りにくく、良好な近似解を求めることができる。　参照(http://pure-tech.jp/delivery/sa/sa.html)

【長所】

1．局所解に陥りにくい

最急降下法といった古典的な最適化解法は、初期値の与え方によって往々にして局所最適解に陥りやすい。これに対し、SAでは解の改良方向を改悪方向へも探索を進めることで真の最適解に到達することが可能である。

【短所】

1．計算量が多い

最適解を得るのに非常に多くの計算量を要する。

2．個別にパラメータを設定する必要がある

汎用解法であるために、問題を解く場合には、配送経路であれば交通量や道路の広さといったパラメータチューニングなどを個別に行う必要がある。

簡単に言うと、、、

初めは大雑把な解を求めていって、徐々に細かい探索をしていくことで、局所解に陥りにくい探索が出来るというものです。

シミュレーションをしてみる

さて、どれほどのものなのかをシミュレーションしていきます。

の最小値を求めてみる。

作成したSA法のプログラムは以下の通り。

</p>

<pre class="code lang-python" style="color: #454545;" data-lang="python" data-unlink=""># -+- coding: utf-8 -*-
import random #ランダムモジュール
import math

def annealingoptimize(T=10000, cool=0.99, step=1):
 # ランダムな値で初期化
 vec = random.randint(-2,2)

 while T > 0.0001:
 # 変更する変数を一つ選ぶ。
 # 今回の場合は1次元なので選ぶ必要がない。
 # i = random.randint(0, dimmension-1)

 # 変数の値を増加させるか、減少させるかを決定する。
 dir = random.random()
 dir = (dir - 0.5) * step

 # 変数の値を変更する。
 newvec = vec + dir

 # 変更前と変更後のコストを計算する。
 newcost = costf(newvec)
 cost = costf(vec)

 # 温度から確率を定義する。
 p = pow(math.e, -abs(newcost - cost) / T)
 print (p)

 # 変更後のコストが小さければ採用する。
 # コストが大きい場合は確率的に採用する。
 if(newcost < cost or random.random() < p):
 vec = newvec

 # 温度を下げる
 T = T * cool

 return vec

def costf(x):
 return (3*(x**4)) - (5*(x**3)) + (2*(x**2))

if __name__ == '__main__':
 print (annealingoptimize())

if __name__ == '__main__':
 success, failure = 0,0
 for i in range(0, 1000):
 ans = annealingoptimize()
 if (ans >= -0.05 and ans <= 0.05):
 failure += 1
 if (ans > 0.8 and ans <= 0.9):
 success += 1

 print (success,failure)</pre>
</div>
<div style="color: #000000;">