焼き鈍し法（Simulated Annealing：SA）の実装

OneMax問題（10ビット）を解いてみる。
温度を線形に減少する。

import numpy as np
import matplotlib.pyplot as plt

R = 10
T = 10

N_bit = 10
x = [np.random.randint(100)%2 for _ in range(N_bit)]
y = np.zeros_like(x)

def evalOneMax(x):
    return sum(x)

def mutate(x):
    idx = np.random.randint(N_bit)
    tmp = x.copy()
    tmp[idx] = 1-tmp[idx]
    return tmp

x_vals = []
deltas = []
while T>0:
    for gen in range(R):
        y = mutate(x)
        x_val = evalOneMax(x)
        y_val = evalOneMax(y)
        delta = x_val - y_val
        deltas.append(delta)
        if delta<=0:
            x = y.copy()
        if np.exp(-delta/T)>=np.random.rand():
            x = y.copy()
        print(x_val)
        x_vals.append(x_val)
    T -= 0.2

plt.plot(x_vals)
plt.show()

温度を指数的に減少

import numpy as np
import matplotlib.pyplot as plt
import pdb

R = 10
T = 10

N_bit = 10
x = [np.random.randint(100)%2 for _ in range(N_bit)]
y = np.zeros_like(x)

def evalOneMax(x):
    return sum(x)

def mutate(x):
    idx = np.random.randint(N_bit)
    tmp = x.copy()
    tmp[idx] = 1-tmp[idx]
    return tmp

x_vals = []
move_cnt = 0
Ts = []
x_aves = []
while T>1.0e-1:
    x_tmp = np.zeros(0)
    for gen in range(R):
        y = mutate(x)
        x_val = evalOneMax(x)
        y_val = evalOneMax(y)
        delta = x_val - y_val
        if delta<=0:
            x = y.copy()
            move_cnt += 1
        if np.exp(-delta/T)>=np.random.rand():
            x = y.copy()
            move_cnt += 1
        x_vals.append(x_val)
        eta = move_cnt/R
        x_tmp = np.append(x_tmp,x_val)
    x_ave = x_tmp.mean()
    T *= 0.99
    Ts.append(T) 
    x_aves.append(x_ave)


fig = plt.figure()
ax1 = fig.add_subplot(111)
ax1.plot(x_aves)
ax2 = ax1.twinx()
ax2.plot(Ts,'r')
fig.legend(['score','temperature'])
plt.show()