算法背景
退火是指將固體加熱到足夠高的溫度，使分子呈隨機排列狀態(tài)晰韵，然后逐步降溫使之冷卻惹挟，最后分子以低能狀態(tài)排列，固體達到某種穩(wěn)定狀態(tài)气筋。物理退火包括一下3個過程：
1.加溫過程——增強粒子的熱運動拆内，消除系統(tǒng)原先可能存在的非均勻態(tài)；
2.等溫過程——對于與環(huán)境換熱而溫度不變的封閉系統(tǒng)宠默，系統(tǒng)狀態(tài)的自發(fā)變化總是朝自由能減少的方向進行麸恍，當自由能達到最小時，系統(tǒng)達到平衡態(tài)搀矫；
3.冷卻過程——使粒子熱運動減弱并漸趨有序抹沪，系統(tǒng)能量逐漸下降刻肄，從而得到低能的晶體結(jié)構(gòu)。
算法原理
基本原理
模擬退火算法分為三部分：初始解采够、解空間以及目標函數(shù)肄方，分別對應(yīng)物理退火過程中的初始溫度、降溫以及最終溫度蹬癌。
1.初始解：初始解釋算法迭代的起點权她，試驗表明，模擬退火算法是健壯的逝薪，即最終解的求得最優(yōu)解并不十分依賴初始解的選取隅要，從而可任意選擇一個初始解。當然董济，如果初始解選擇得當可以加快找到全局最優(yōu)解步清。
2.解空間：一般是離散的可行解的集合。
3.目標函數(shù)：對優(yōu)化目標的量化描述虏肾，是解空間到某個數(shù)集的一個映射廓啊，通常表示為若干優(yōu)化目標的一個和式，應(yīng)正確體現(xiàn)問題的整體優(yōu)化要求且較易計算封豪，當解空間包含不可行解時還應(yīng)包括罰函數(shù)谴轮。
4.算法從初始解或稱為初始狀態(tài)開始，在解空間中進行啟發(fā)式搜索（通常是隨機搜索的方式）吹埠，最終搜索到最優(yōu)的目標值第步。
基本過程
初始化：設(shè)定初始溫度T，初始解狀態(tài)S缘琅，終止溫度T0粘都；
降溫過程：如果T>T0，則循環(huán)執(zhí)行3至6步刷袍；
在解空間中隨機搜索一個新解S’;
計算增量ΔE=E(S′)-E(S)翩隧，其中C(S)為解S對應(yīng)的目標函數(shù)值或稱為評價函數(shù)；
若ΔE<0則接受S′作為新的當前解呻纹，否則以概率exp(-ΔE/T)接受S′作為新的當前解鸽心；
如果滿足終止條件則輸出當前解作為最優(yōu)解，結(jié)束程序居暖。終止條件可以有兩種情況顽频，一是溫度已經(jīng)達到了最低溫度T0；二是在連續(xù)的取若干個新解都沒有跳出當前最優(yōu)解太闺。
退火方式
模擬退火算法中糯景，退火方式對算法有很大影響。如果溫度下降過慢，算法的收斂速度會大大降低蟀淮。如果溫度下降過快最住，可能會丟失極值點。為了提高模擬退火算法的性能怠惶，許多學者提出了退火的各種方式涨缚，比較有代表性的有以下幾種：
- T(t) = T0/ln(1+t)
該方式的特點是溫度下降緩慢，算法收斂速度也較慢策治，但是最終達到全局最優(yōu)的可能性是最高的
- T(t) = T0/ln(1+at)
式中a為可調(diào)參數(shù)脓魏，可以改善退火曲線的形態(tài)。其特點是高溫區(qū)溫度下降比較快通惫，低溫區(qū)下降比較慢茂翔，這種退火方式主要期望在低溫區(qū)收斂到全局最優(yōu)。
- T(t) = T0a**t
式中a為可調(diào)參數(shù)履腋，其特點是溫度下降很快珊燎，算法的收斂速度快，但是帶來的損失是可能不能充分的收斂到全局最優(yōu)
以上三種退火方式各有優(yōu)缺點以及適用的場景遵湖，需針對具體的應(yīng)用進行選擇悔政。
算法框圖
源代碼
#!/usr/bin/env python
# -*- coding: UTF-8 -*-
import matplotlib.pyplot as plt
import math
import numpy as np
class SA():
def __init__ (self, max_steps):
self.T_max = 100 #最高溫度
self.T_min = 1 #最小溫度
self.T = self.T_max #溫度初始化
self.t=1 #初始化時間
self.max_steps = max_steps # 同一溫度下迭代次數(shù)
self.dim = 9 # 搜索空間的維度
self.x_bound_low = np.full(shape = self.dim, fill_value = -10) #變量取值下邊界
self.x_bound_high = np.full(shape = self.dim, fill_value = 10) #變量取值上邊界
def function_fitness (self, x):
return np.sum(np.square(x))
def update_value (self, x, y, new_x, new_y,best_x, best_y, flag):
"""要接受這個y_new為當前溫度下的理想值，要滿足y_new>y_old 或 math.exp(-(y - new_y) / self.T)>random.random()"""
if (new_y < y) or (math.exp(-(new_y - y) / self.T) > np.random.random()):
x = new_x.copy()
y = new_y
if new_y < best_y:
flag = 1
best_x = new_x.copy()
best_y = new_y
return x, y, new_x, new_y,best_x, best_y, flag
def solve (self):
x = np.random.uniform(self.x_bound_low, self.x_bound_high,size=(self.dim)) # 初始化自變量位置
y = self.function_fitness(x)
best_x = x.copy() #矩陣之間相互賦值需要特別注意延旧，賦值后兩者對應(yīng)的地址還是一樣的
best_y = y
new_x = x.copy()
new_y = y
while self.T > self.T_min:
flag = 0 #用以判斷有無新值被接受
for step in range(self.max_steps):
delta_x = np.random.uniform(low=-0.055,high=0.055,size=(self.dim))*self.T
middle_value = x+delta_x
for i in range(self.dim):
if (self.x_bound_low[i] <= middle_value[i]) and (middle_value[i] <= self.x_bound_high[i]):
new_x[i] = x[i] + delta_x[i]
new_y = self.function_fitness(new_x)
x, y, new_x, new_y, best_x, best_y, flag = self.update_value ( x, y, new_x, new_y, best_x, best_y, flag)
if flag == 1:
x = best_x
y = best_y
self.t += 1
self.T = self.T_max/(50+self.t)
print(best_x, best_y)
sa = SA(100)
sa.solve()
python tips
當對數(shù)組進行運算和操作時谋国，其數(shù)據(jù)有時會被拷貝到一個新的數(shù)組而有時又不會拷貝。對應(yīng)有三種情況:完全不拷貝（b=a垄潮，兩者對應(yīng)內(nèi)存地址相同）烹卒、視圖或淺拷貝（c = a.view()闷盔，c隨著a變弯洗，c不擁有數(shù)據(jù)，但改變其中任意一個值逢勾，兩者都會變牡整，矩陣切片是淺拷貝）、深拷貝（d=a.copy()溺拱，d和a已經(jīng)沒有任何關(guān)系了）逃贝！
本程序中的退火方式為T = T0/(a+t),與隨機梯度下降法的學習率取相同的變化規(guī)律，仍有比較好的效果迫摔。
python中支持函數(shù)中嵌套函數(shù)沐扳，此時嵌套函數(shù)在函數(shù)體外不能使用，即歸函數(shù)私有句占。
