--- # System prepended metadata title: Search in Complex Environments 重點整理筆記 --- 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低(方向選項簡單) - 在很大或是無限大的空間，可以找到不錯的解 適合用來解純的最佳化問題 ![](https://i.imgur.com/Oh59BsX.png) 在電腦中無法看到整個全貌，往往只能找到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 可以隨自己的設定下降，看自己目標 ![](https://i.imgur.com/BsdEV95.png) ``` 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最佳解的狀況。 ![](https://i.imgur.com/buVEg5K.png)