模拟退火示例

原

模拟退火是种寻找全局最优解的过程，在逐步寻找更优的时候按某种概率接受变差一点的情况，而且开始的时候探索的步子比较大，容忍变差的概率也大，最后步子变小，容忍变差的概率也变小。

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()