###### tags: `計算智慧與規劃`
# 計算智慧與規劃Week14 - 退火煉鋼SA

## 退火煉鋼 Simulated Annealing (SA)
- 描述煉鋼過程中分子的碰撞情況 => 是**二維**的
- Statistial mechi
- Markov chain (馬可夫鏈) and Boltzmann machine (波次曼機)
- 退火：加熱後分子變的很不穩定，經過冷卻溫度下降
- 以 雪花結晶 為例
- 退火 (Annealing) 方法:加冷水、空氣接觸
- 降溫過程 => 收斂
- 設**Y軸**由上開始，溫度越高
- 熱平衡(thermal equilibrium)
- 設**X軸**代表能源流動，最右邊熱平衡
- 熱移動:高能往低能移動
- **水晶結晶體** 表示 最佳解

### 名詞解釋
- State：能源位階，每一個分子都具備一個能源state => Solution
- Energy：因相對位置不同而有不同的位能，能源要越小越好 => fitness
- temperature：溫度，要告訴他溫度幾度，每次升幾度或每次降幾度 => SA 特有的超參數, 調控退火速度
- thermal equilibrium：熱平衡
- Annealing：退火
- Crystalline：結晶度 => global optimum

## 原型：Metropolis algorithm 馬可夫鏈
### 機率
- E(i)、E(j)、E(k)：一個分子(狀態)的能量
> - 狀態:粒子分布、顏色
- E(i) : 現在 (時間=t) 分子狀態有的能量
- E(j) : 下一秒分子狀態的能量
- E(k) : 再下一秒分子狀態的能量
- E(....)： ...
- 達到熱平衡後，就要降溫
- K：波次曼常數
- T：溫度
- 位能的變化
- E(j) >= E(i) -> 100%
- E(j) < E(i) -> 有機率
- 
- K:常數(可以不用管)
- T:溫度
- **E(j) - E(i)** -> 差值愈高發生機率愈低
> 差值越大所需的能量就要越多，發生的機率就越低
- **T**愈高： 發生機率越高
> 溫度越高就有越多能量爬上去
- 最後能量狀態會停在哪個地方不一定
### 夠熱原則
- 
- T0 > 最大所需能量
- 對這個問題而言每一個粒子機率都一樣
1. 溫度非~常高 -> 因為能量太多，要爬多高都可以，所有機率相等
2. 接近 0 度 -> 溫度太低，幾乎沒有能量往上爬，機率為 0
### Entropy
- 理論:描述資訊系統裡面的資訊量
- 以上面為例子
> **X軸**當作熱平衡
> **Y軸**當作機率
> 過程中高高低低代表能量大小，也可以代表Entropy的大小
> 發現收斂的過程當中，Entropy越來越小，最後低到接近0，就是一個結晶
### 圖例
- 虛線：能源範圍
- Annealing：讓虛線一直往下降，最後會找到最深的波谷

## Simulated Annealing 煉鋼
- 左：描述退火鍊鋼；右：最佳化演算法 (可以找最小值最大值)
- 產生碰撞，讓分子狀態改變
- 這邊利用突變或晃動
- 
- 解決真正的問題 -> 不描述問題，所以不需要K
- s(k)：現在的狀態
- s'(k)：下一個的狀態
### 找鄰居的方法
1. 平行式：若現在答案為狀態 I，透過**擾動I的變數**產生 m(已知) 個下個狀態，再分別計算這 m 種可能會發生的機率，射飛鏢決定下一個狀態
> 突變的方法
> 1. 排列問題 -> 位置交換
> 2. 實數問題 -> 依比例取亂數做擾動
> ex:假設有一個實數為350，350 +- 350*(0~1取亂數)
> 鄰居數量少 => m < 5
2. 循序式：一次產生一個鄰居，檢驗它是否會發生
- 溫度T的情況下，停在某狀態的機率
### 演算法流程
- T0:一開始的溫度，每增加一次溫度就k = k+1
- k: 目前加了幾次溫度
- A: 答案
- J: 分數
- c: current
- b: best
- l: 走幾步 (事先設定)
- μ: 用於調整溫度的超參數 (事先設定, 0~1)
- ε: 溫度低於多少可以停止 (事先設定, 很接近 0)
1. 初始答案
2. 找鄰居比較
> 分數低 -> 一定發生，發生機率一樣，每一個人都是100%
> 分數高 -> 再檢驗爬上去的機率，射飛鏢
3. 碰撞 -> 產生隨機亂數
4. 算機率
5. 更新最佳解
6. 降溫
7. 檢查溫度是否低於最低標準，是就停止，否則回2.
8. 輸出 Ab, Jb