求全域最小點，
每次隨機出一個新解，如果這個解更優，則采納它；否則以一定概率采納它，
設這個新的解與上一個解的差為ΔE，溫度為T，k 為一個亂數，離子趨于平衡的概率（即可采納的概率）為:
\[P_k=e^{-\frac{\Delta E}{kT}} \]
可見，ΔE/kT越小，溫度T越高(此時的迭代次數越少)，k越大(人工設定,影響較差解的采納概率)，ΔE越小(這個較差解與上一個解的差越小)，被采納的概率也就越大，
ΔE<0，新解更小，采納它；否則，從(0,1)中隨機一個數R，若R<P\(_k\)，則采納它，
(這個圖是求最大)
求函式
在[0,9]之間的最大值：
import math
import random
def y(x): # 函式y即能量E
return x + 10 * math.sin(5 * x) + 7 * math.cos(4 * x)
def is_acceptable(delta_E,tmp,k=1): # 是否可采納
if delta_E<0: # ΔE<0，直接采納
return True
p=math.exp(-delta_E/(k*tmp)) # 求概率
if random.random()<p:
return True
else:
return False
left = 0 # 左邊界
right = 9 # 右邊界
tmp = math.e**5 # 初始溫度
tmp_min = math.e**-3 # 停止溫度
alpha = 0.98 # 降溫系數
x_old = left + random.random() * (right-left) # 生成初始隨機解
E_old = y(x_old)
counter = 0 # 生成更差解的次數
while tmp > tmp_min:
t = (random.random() - 0.5) * 3 # 生成隨機解
x_new= x_old + t
if x_new<left or x_new>right:
x_new = x_new - 2*t
E_new = y(x_new)
delta_E = -(E_new - E_old)
if is_acceptable(delta_E,tmp): # 可采納
x_old = x_new
E_old = E_new
if delta_E<0: # ΔE<0，生成更優解，降溫
tmp = tmp * alpha
else:
counter += 1
if counter > 10000:
break
print('y(' + str(x_old) + ') = ' + str(E_old))
TSP問題：
import math
import random
#############################################
def get_all_dist(): # 每兩個城市間的距離
for i in range(len(cities)):
for j in range(i,len(cities)):
d[(i,j)] = d[(j,i)] = math.sqrt((cities[i][0]-cities[j][0])**2 + (cities[i][1]-cities[j][1])**2)
def create_new_route(a): # 產生新路徑
i = random.randint(0,len(a)-1)
j = random.randint(0,len(a)-1)
a[i],a[j] = a[j],a[i]
def get_route_dist(a): # 路徑長度即能量E
dist = 0
for i in range(len(a)-1):
dist += d[(a[i],a[i+1])]
return dist
def is_acceptable(delta_E,tmp,k=1): # 是否可采納
if delta_E<0: # ΔE<0，直接采納
return True
p=math.exp(-delta_E/(k*tmp)) # 求概率
if random.random()<p:
return True
else:
return False
#############################################
# 城市坐標
cities = [[1304,2312],[3639,1315],[4177,2244],[3712,1399],[3488,1535],[3326,1556],[3238,1229],[4196,1004],[4312,790],[4386,570],
[3007,1970],[2562,1756],[2788,1491],[2381,1676],[1332,695],[3715,1678],[3918,2179],[4061,2370],[3780,2212],[3676,2578],[4029,2838],
[4263,2931],[3429,1908],[3507,2367],[3394,2643],[3439,3201],[2935,3240],[3140,3550],[2545,2357],[2778,2826],[2370,2975]]
d = dict() # 每兩個城市間的距離
get_all_dist()
route_old = list(range(len(cities))) # 初始路徑
E_old = get_route_dist(route_old) # 初始路徑長度
tmp = math.exp(3) # 初始溫度
tmp_min = math.exp(-8) # 停止溫度
alpha = 0.98 # 降溫系數
counter = 0 # 生成更差解的次數
#############################################
while tmp > tmp_min:
route_new = route_old
create_new_route(route_new) # 生成隨機解
E_new = get_route_dist(route_new)
delta_E = E_new - E_old
if is_acceptable(delta_E,tmp): # 可采納
route_old = route_new
E_old = E_new
if delta_E<0: # ΔE<0，生成更優解，降溫
tmp = tmp * alpha
else:
counter += 1
if counter > 10000:
break
print(route_old)
print(E_old)
參考：
- https://zhuanlan.zhihu.com/p/33184423
- https://www.luogu.com.cn/blog/m-sea/qian-tan-SA
- https://www.cnblogs.com/sench/p/9427193.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/47702.html
標籤：其他
上一篇：決策樹詳解
下一篇：變分推斷與變分自編碼器