はすけるとぱいそん

アニーリングアルゴリズム（改）。

Python

前回のアニーリングアルゴリズムの記事はサンプルデータがアレでした。
というわけでちょっと書き換えました。

#coding:shift-jis

import numpy as np
from pylab import *
import random
import math

data = [0]
for i in range(1000):
	a = random.randint(1,100)
	if (a==1):
		b = random.randint(100,200)
		for i in range(b):
			data += [data[-1]-3]
	else:
		data += [data[-1]+3]

# データを青でプロット。
for (x,y)in zip(range(len(data)),data):
	plot(x,y,'bo')

# アニーリングアルゴリズム。
def annealing(data,T=10000,p=0.95):
	r = random.randint(0,len(data)-1) #初期値をランダムに選択。
	plot(r,data[r],'yo') #初期値を黄色でプロット。
	while True:
		cost_now = data[r] #現時点でのコスト。
		cost_new = data[r+1] #次点でのコスト。
		
		if (T >= 0.1): #高コストの解も受け入れる時。
			p = e**(-abs(cost_now-cost_new)/T) #高コストの解を受け入れる確率。
			if (cost_now > cost_new) or (p > random.random()):
				r = r+1 #次点へ移動。。
			else :
				r = r-1 #逆のr-1の点へ移動。
			
			T *= 0.95 #Tを小さくする。
		
		elif (T < 0.1): #Tが十分小さくなったら（高コストの解を受け入れなくなったら）、ヒルクライムで局所最小解を出す。
			if((data[r-1]) > cost_now < cost_new):
				break #最終的にループを抜け出す。
			elif (cost_now > cost_new): #次点へ。
				r = r+1
			else :
				r = r-1
	return ([r,data[r]])

#アニーリングアルゴリズムによる最小解を赤でプロット。
a = annealing(data)
plot(a[0],(a[1]),'ro')

show()

結果は以下の通りです。
データは青線、初期値は黄点、結果は赤点で示しています。





普通のヒルクライムなら初期値の黄点から下降して初めて行き着いた底が赤点になるはずですが、
アニーリングなのでそうなってないですね。一応成功です。

ふぇぇ〜
　
　

ツイートする

Permalink | コメント(0) | トラックバック(1) | 13:40