###### tags: `計算智慧與規劃`
# 智慧計算與規劃 week16 - Tabu search

## 選鄰居策略 Low Level策略
- 單線型搜索
- 因為只有一條線，所以要多產生鄰居，盡量看到所有結果
- 選鄰居的方法↓

## Ejection chain
- 如果是線性規劃，最佳解會在線 (邊界) 上，不會在合理解的內部
- 如果不是是線性規劃，近似解會在線的周邊
> 曲線內為不合理解，搜索軌跡在曲線的附近搜尋
- 讓它的鄰居結構變得很複雜
### 做3種設定
1. 合理 -> 不合理
2. 不合理 -> 不合理
3. 不合理 -> 合理
- 不合理解的結構
- stem-and-cycle
> tip 頂端點
> root stem&cycle的交接點
- 合理解的結構
- 
#### 1. 合理 -> 不合理
> 合理解變不合理解的作法
- 把任何一個邊打掉
- tip 連到 cycle 任一個點，該點兩側任選一邊打掉

#### 2. 不合理 -> 不合理(trail move)
- 法一：連到樹枝(?)任意點，打掉該點旁邊的邊(??)
- 法二：tip 連到 cycle 任一個點，該點兩側任選一邊打掉

#### 3. 不合理 -> 合理
- tip連接到subroot 再把subroot的線打斷，如下圖

- 目的是為了讓鄰居的結構變複雜

## Filter and Fan
- 透過不斷的過濾和展開找鄰居
- 超參數
- 展開幾個 (一個做多有2個子代)
- 深度

## Path Relinking 路徑重建
- 本來是兩條不同的路互相連接
- 代表點:local output、影響最大的點 (可以自己設)
- 讓各個點彼此去建路徑連接
- 
- X 為起點，透過其他點的引導，盡量往 A or B or C 靠攏
- 舉例：已知最好的父母基因X, C，由 X 開始，往 C 邁進，過程中盡量找出所有的解 (接近窮舉)
- 不要把運氣放隨機產生亂數
- 5種實行方案
1. X -> X' 或 X' -> X 和怎麼挑鄰居相關，和走法不相關
2. 往前走、倒過來走、X, X' 各走一半，可自己設(結果不同)
3. 加入慣性
4. 融合不同產生鄰居的方法 (空間搜索不斷變化) => 交錯應用效果比較好
5. 本來應該是產生不合理&合理解後，對這些點打分數。而這個機制本身就可以將不合理解代到合理解，因為X和X'都是不合理解，所以中間過程雖然有走到不合理解，但最後都會走到合理解，所以他會一直會再合理解&不合理解之間反覆進出=>這樣更好，因為前面有講說最佳解會在合理解&不合理解中間的曲線附近
- 複雜鄰居結構
- 組合
- 0 和 1：投票
- 實數：線性組合

## Oscillation Strategic 策略震盪(High Level產生鄰居方法)
- 在合理解和不合理解之間來回震盪
- 邊界
- Feasibility boundary
- Neighborhoods boundary
- Quality boundary
- 透過p的改變產生新的鄰居(p 介於0 ~ 1 之間)

## 長期記憶體Long term memory LTM
- 著重在紀錄結構或變數出現的「頻率」上以及答案「分數」高低
- 如果某結構出現時分數較低 -> 處罰

## Multi-Start Tabu
- 讓restart 變成一定會發生的事
- 設定重來的點位置
- 1. 用grid 規定每次重來的點的位置(確保每個大範圍都有記錄到)
- 2. 拿之前結果好的解來當重來的位置
- 設定重來的Tabu List
- 1. 全部淨空
- 2. 保留之前
- 長期策略：各種策略組成不同組合

## Scatter Search
- 如何讓答案和答案去產生新的答案
- 父母不適合隨機選，要系統性選擇
- 流程圖
- 堆積木的方法，很彈性
- 積木們↓(有五個地方可以自行設定)
### 1. 差異性產生法(產生距離很遠的初代)
- 讓他們有一定的距離
- 棋盤法(grid)
- 田口正交法
### 2. Improvement method 改良法
- 算局部最佳解的方法(?)
- 如果答案是連續的可以用 : Nelder & Meed , PSO, Hooke & Jeeves

### 3. Reference set update method 更新法
- 2個過濾原則
- quality: 分數
- diversity: 離前幾名距離愈遠愈好(多樣性)
- quality & diversity 各拿一半
- two tier更新法 -> 更新人口
- 方法
- dymanic: 一個一個處理，像branch & bounds方式挑一個
- static: 一起處理(一次產生多個子代)

### 4. Multi-Type subset
- 產生父母的方法
- Type 1 to 5
> 總共有10對父母，要選3對父母，目前已經有2對父母了，剩下的一組父母就從剩下的8個，選分數最高的一個

- Type 1 : 10取2 種可能
- Type 2 : 在Type 1(10取2) 算完之後再加一個父母(剩下8個中分數最高的)
- Type 3 : 在Type 2 再加一個父母
- 以此類推

### 5. Solution combination method
- 產生孩子的方法
- Continuous case
紅色的那兩塊是用慣性走出去的

- 和 path relinking 有關

## GRAPS (reedy randomized adaptive search procedures)
- 貪婪←→隨機
- 貪婪: 很快就找到局部最佳解
- 隨機: 亂亂走
- 超參數 α: 調控要比較貪婪還是比較隨機的參數
- 透過超參數調控極值的震盪
- 透過restart找到最佳解
### 如何產生初始解restart (以TSP為例)
- 一直重複做restart
1. 隨機挑一個初始值
2. 設定一個超參數α
> α越接近 0，越接近Cmin
> α越接近 1，越接近Cmax
> 折衷Cmax-Cmin
3. 如果有 10 維，分開做 10 次
### local optimal
- 透過 local search 帶到局部最佳解

## 變動鄰居搜索法 Variable Neiborhood Search VNS
- 如果都用不同方式產生鄰居，結果可能不好，所以混合不同產生鄰居的方法
- tabo search 建議用 VNS
### 實際做法
- 產生最初的答案「x」
1. 先設Kmax
> Kmax:產生幾種鄰居的方法
2. 大範圍擾動 Shacking，就是「x'」
3. 走幾步(到局部最佳解) Local search 就是 「x''」和 x' 比較
4. 看他有沒有成功，如果x''有進步(成功)，失敗的話就換另外一種產生鄰居方式
5. 回到 2. (k 從1開始)