接下來的專案是實作模擬退火法！

在最佳化演算法當中，梯度下降法（gradient descent method）是一個廣泛使用的演算法，主要他實作上不複雜，也有非常多的變體，不過梯度下降系列的演算法有個缺點就是他並不保證最佳化會收斂到全域最佳（global optimum），他有可能會落入區域最佳（local optimum）。

當然，local optimum等不等於global optimum就看你最佳化的目標函數是誰了。

當我們想要求取global optimum的時候我們就會往stochastic algorithm的方向去想。
在啟發式演算法當中有個相當有名的演算法是simulated annealing，當你搜尋的時間夠久，你就能找到愈接近global optimum的解。

概念

為什麼叫作模擬退火法呢？
其實他是模擬金屬加熱，在退火的過程中，金屬能夠不斷的去找到自己能量最低的狀態，擴大晶粒，降低缺陷，降溫的過程中還是有機會升溫再降溫，主要是為了找到所有狀態中能量最低的，藉由模擬這樣的過程來最佳化目標函數。

蒙地卡羅法

他其實是一種Markov chain Monte carlo(馬可夫蒙地卡羅)的延伸。
我們知道蒙地卡羅法是單純的隨機演算法，最常見到的例子就是拿他來估計pi的值，那跟馬可夫鍊有什麼關係呢？
我只能先敘述性的告訴大家，馬可夫鍊可以用來建構一個graph，而藉由在graph上狀態的轉移，可以把狀態的時間序列視為隨機的序列，而建構graph的時候馬可夫鍊可以去近似某個統計分佈。
總之，馬可夫鍊會把給定的資料視為學習對象，學習資料中的分佈，並創造出符合這個分佈的狀態序列，所以這個方法最常用來實作sampler，也就是抽樣器。

而Markov chain Monte carlo不是單一種演算法，他是一類方法，其中simulated annealing會用到的是Metropolis-Hasting algorithm。

演算法

上面講了這麼多名詞，大家不要害怕，可以聽聽就好XD

我們講解演算法可以不用用到這些名詞。

那我們直接進演算法的pseudo-code

T_MAX = 1000  # 初始溫度
T_MIN = 10  # 設定結束溫度
T = T_MAX  # 設定目前溫度
markov_step = 100  # 設定馬可夫鍊學習的次數

current_state = generate_init_state()  # 隨機產生初始狀態
current_energy = energy_function(current_state, T)  # 產生目前的能量

while T尚未到達T_MIN
    for i=1:markov_step
        new_state = generate_new_state(current_state)  # 依據目前的狀態產生新的狀態
        new_energy = energy_function(new_state, T)  # 計算新狀態的能量
        alpha = acceptance(new_energy, current_energy, T)  # 經由函數計算出一個接受的機率值
        if rand() <= alpha
            # 接受新的狀態
        else
            # 拒絕新的狀態
        end
        # 降溫
    end
end