Search in Complex Environments 重點整理筆記
==

在前面可以知道用tree可以找到最佳解，但是現實中很多問題都不能用tree來表達

## Local Search Algorithms and Optimization Algorithms

Search algo 如過可以建成一個tree得時候$\equiv$它可以系統化，只要找到goal就可以找到相對應的路徑，但是在很多問題，ex:八皇后(八隻皇后不互相攻擊
) -> **順序對他來說沒有影響**

-> **尋找不在意收尋路徑的algo以解決一般化問題**

### Local Search
Local Search -> 以一單一currnt node，只能移動到相鄰的node
- 所以memory低(方向選項簡單)
- 在很大或是無限大的空間，可以找到不錯的解
適合用來解純的最佳化問題


在電腦中無法看到整個全貌，往往只能找到local最佳解，也很難探測到非常精細的最佳解

有許多algo可以協助找到不錯的解

### Hill Climbing Search
可以用來找最高峰(最低)，**不需要建search tree**，每次找**最棒的鄰居**，只需要跑loop變可以找到local 最佳解

Hillclimbing()
current
loop do
    neighbor = 選一個最高value的鄰居
    if neighbor.value <= current.value \\currrnt是鄰居中最大的
        return current.state
    current = neighbor

所以也叫做**greedy local search**，簡單效果不錯，但是爾偶會卡住在local maximum, Ridges, Plateaux....

以八皇后的問題：
- 大約14%可以solve，86%會卡在local maximum(很看運氣...)
- 執行速度很快，只需4 steps當走對時，3 steps當卡住時，在$8^8$的stae space中，算是很快

如果不每次找最佳的的鄰居，反而更有機會跳出local maximum，找到解的機率14% -> 94%，21 steps 當走對時，64 steps當走錯時，但是**所需花費時間會變多**

#### Stochastic Hill Climbing
拜訪過所有鄰居，不用找最強的鄰居，**隨機**在**比current 強**的鄰居中挑一格出來

#### First Choice Climbing
依序visit 鄰居，找到並選擇第一個比current 強的鄰居，而不是拜訪過所有鄰居

#### Random Restart Hill Climbing
隨機跑很多次(因為他速度蠻快的)找很多組解，再從很多組解中挑出最好的

找出的解好不好與state-space, landscape有很大的關聯

### Simulated Annealing模擬退火

Annealing -> 退火
先把鐵加熱，再把鐵遡行，再冷卻
- 溫度高->好改變
- 溫度低->不好改變

**一開始高溫然後一路往低溫的過程**
一開始在探索，比較可以接受較差的解，隨著不斷重複function，可以接受較差解的機率降低

不是永遠取最佳鄰居，而是**隨機**取周圍鄰居

T = schedule(t) //T會隨著t變大T會越來越小
schedule 可以隨自己的設定下降，看自己目標

if(deltaE > 0(鄰居條件比current好)    選鄰居
else if(current條件比鄰居好)    還是有一定機率選鄰居

所以可以說是當
$\Delta$ E越大(鄰居差current很多)，其選鄰居的機率越小
$\Delta$ E越小(鄰居差current差不多)，其選鄰居的機率越大
又T在一開始很大，在逐漸變小
T 越大，選到差鄰居的機率越大
T 越小，選到差鄰居的機率越小
設定$e^{\Delta E/T}$是為了讓他機率在指數計算可以快速下降，可以在前幾步容錯率高，後面容錯率低

冷卻時程是SA的核心之一，不同的冷卻時程會導致不同的尋優績效， 但目前並沒有一個設計準則可供依循。

由於SA是由現有状態推演出下一状態，一次僅探討一個可行解。因此
在求解大規模問題時，通常需要耗費相當大的電腦執行時間。

### Local Beam Search(一次處理多個解)
一次處理k個解，每個都去找他們的successor（鄰居），再從這些可能state中挑出最佳的successor（天女散花的感覺）（資訊會傳到彼此）

隨機選k個states
while(1)
    if(找到goal)    return solution
    else    再選k個best successors

跟一次跑一個解跑k次的差別？一次一次跑很容易被一團很強的鄰居吸引（像是idependent跑k次沒有特別意義），但是Local Beam search可以比較全面的去找

**Stochastic Beam Search**不是永遠挑最佳的successor，而是隨機挑successor，多了隨機性

### Genetic Algo
是Stochastic Beam Search的一種

步驟：
1. Initial Population:先確定大小
2. Fitness funtion:適應函數用來計算染色體( chromosome )好壞的標準，用來篩選出適應程度較佳的個體(染色體)。
3. Selection：想像是我們要做基因改造，會把比較好的基因給留下來，不好的基因給去除這樣的概念。
4. Crossover：兩兩基因進行交配進而產生出新的染色體。而兩兩染色體是否交配也會透過交配機率進行控制，切分有很多切法，看目標自己調配。
5. Mutation：針對單一的染色體，會根據突變機率來改變，這是因為避免最後的結果陷入local最佳解的狀況。