模拟退火是种寻找全局最优解的过程,在逐步寻找更优的时候按某种概率接受变差一点的情况,而且开始的时候探索的步子比较大,容忍变差的概率也大,最后步子变小,容忍变差的概率也变小。
import random
import math
import matplotlib.pyplot as plt
import matplotlib.animation as animation
LIMIT = 100000
def func(x):
return -math.sin((4 * math.pi / LIMIT) * x) * math.sin((3 * math.pi / LIMIT) * x + math.pi / 1.5)
def initialize(L):
return map(func, range(0, L))
def update_temperature(T, k):
return T - 0.001
def make_move(x, A, T):
nhb = random.choice(range(0, len(A))) # choose from all points
delta = A[nhb] - A[x]
if delta < 0:
return nhb
else:
p = math.exp(-delta / T)
return nhb if random.random() < p else x
def simulated_annealing(A):
L = len(A)
x0 = random.choice(range(0, L))
T = 1.
k = 1
x = x0
x_best = x0
while T > 1e-3:
yield x, T, x_best, x0
x = make_move(x, A, T)
if(A[x] < A[x_best]):
x_best = x
T = update_temperature(T, k)
k += 1
print("iterations:", k)
while True:
yield x, T, x_best, x0
#动画模拟
A = list(initialize(LIMIT))
sa = simulated_annealing(A)
x, T, x_best, x0 = next(sa)
def update_animation(frame_number):
x, T, x_best, x0 = next(sa)
line.set_data([x,x], [0,A[x]])
text.set_text('T:'+str(round(T,3)))
fig = plt.figure(figsize=(7,7))
plt.plot(A)
plt.plot([0,LIMIT], [0,0], c='r')
line, = plt.plot([x0, x0], [0, A[x0]], c='r', marker='+')
text = plt.text(LIMIT*.8,max(A)*0.9,'T:'+str(round(T,3)))
animation = animation.FuncAnimation(fig, update_animation, interval=1)
plt.show()