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

## 估算 T0
### 溫度
1. 一開始給他很高的溫度
> 避免溫度不夠，導致問題的最佳解無法找到
2. 這個方法分下面4種 但我不知道名字叫甚麼
### 法1 : 直接設定
### 法2
- 先去計算T0 下100次中可以順利跳過去(?)的比例
- 我們希望比例是100%，但100% 可能太花時間
- 所以可能超過80% ，我們就拿來當 T0
### 法3
- 一樣先去計算T0 下100次中，FITNESS(我筆記寫 : 沒次序，但我忘記什麼意思了) 的最大最小，拿來算(?)
### 法4
- 疊代式，小樣本逐步逼近答案
- 有次序
- 產生R (10) 個樣本，兩兩相差是樓梯高度 (往上 or 往下)
- 接受率 A
- 做很多次 (10) 次疊代
- A 如果到達門檻，一次疊代停止
- 回推T0

## 降溫
### 法1 降溫曲線
- 根據曲率算公式
- sigma 事先寫死
### 法2 調變式
- adaptive：根據當下 sigma 決定

## 補充：SA & Direct的兩種方法結合
- 在降溫之前先做 direct search

# Chapter 5 AMP 調變式記憶體規劃
- 演算法大致分兩類
- AI -> 近似解 (Ch1~Ch4)
- OR -> 最佳解、絕對解 (Ch5)
- Adaptive Memory Programming(AMP)= Adaptive mwmory structrue+Responsive strategies
- 程式語言 = 資料結構 + 演算法
- 演算法：流程 (用虛擬碼表示)
- 資料結構：細項怎麼做
- adaptive: 根據不同目的有不同方式做運算(ex:變數、function..)
- memory: 記錄過去的狀態 (ex.變數)，用以比較
## 記憶體
1. 沒有記憶體：GA (存在buffer)
2. 硬式記憶體
3. 軟式記憶體:調變式記憶體
### 調變式記憶體
- 變數種類：
- fitness
- influence (影響力)：用於 responsive strategies
- frequency (頻率)
- influence：進步幾次退步幾次
- 答案種類
- 全部存? 過門檻再存?
- 只存合理解? 不合理解也存?
> 傳統OR用合理理解用於不合理解
- feasibility.......
- 紀錄移動向量(前後2個差)?直接存值?

## 演算法
### Tabu Search
- 傳統OR model會有一個限制式
- 滿足限制式 -> 合理解

- OR 和 AI做結合(1986年)
- OR整數規劃
- 提出"tabu search" & "metaheuristic"
- 線索式搜索：手頭上只有一個答案，一次產生下一個，ex:退火煉鋼SA、Tabu Search
- 搜索式:手上有很~多解，ex. GA、螞蟻演算法、鳥群算法
- 從目前的解產生一群有可能的解，找最好的 (非紅燈) 走，然後相反方向亮燈(被 Tabu) (不要再走回來)
> 紅燈：不能走 or 扣分 -> 有可能是因為距離本來的位置很近或是往回走
- memory存**前n (3) 步**方向，隔了 3 步就會忘記，到時就有可能走回同方向
- 控制 Tabu List 長度
- exploitation
- exploration
- Tabu：Taboo，聲音詞，這是一顆神聖的石頭 (東西) -> 禁忌的話題
- 名詞
- configuration：答案，從鄰居找出最好的答案
- stopping criterion：終止條件 (IMAX or 最多步數 or 時間)
- candidate moves：產生鄰居
> 步驟
> 1. 產生鄰居的方法
> 2. 要產生多少個鄰居
- neiborhood：鄰居範圍
- 方法
- 亮燈(硬性):亮燈就不能去
- 扣分(軟性):如果去了就扣分
- 產生鄰居的方法
- best move
- first move
- aspiration criterion 勇氣程度
> 本來是1->2->3，1跟2會亮紅燈不能走，但是走到3的時候發現2的結果更好，所以2就會亮綠燈讓3可以往回走
> 
- aspiration by defalt：若 10 個方向都是紅燈，放出關最久的
- aspiration by objective：機率決定要不要走 (可以和 SA 結合)
- aspiration by influence：影響力高的結構留久一點
- aspiration by search direction：慣性，若是好的方向就往這個方向走
- aspiration by minimun exposure：最短曝光時間，任何元素一進來至少要留一段時間
- aspiration by intensification：任何元素一進來至少要鑽研到一定深度

## 流程圖
- Zc: 目前解
- Zb: 最佳解
- 產生NH個鄰居
- J1~Jn做排序比較
- k:第幾次產生鄰居
- IMAX:最多可以產生幾次失敗鄰居的門檻值 -> 不一定要，只是可以有一個條件停止讓他繼續跑
> 假設IMAX = 10，因為有可能找鄰居失敗，如果這一次全部沒找到，那就再產生一次鄰居，IMAX = IMAX-1
> 如果在IMAX範圍內成功走一步了，k要重置重新計算 -> k = 1
> IMAX只是控制 Tabu 停止的方式之一，不是 Tabu 的重點