---
title: AI Ch.X
---
# Artificial Intelligence
NTNU 人工智慧
##### [Back to Note Overview](https://reurl.cc/XXeYaE)
##### [Back to Artificial Intelligence](https://hackmd.io/@NTNUCSIE112/AI110-2)
{%hackmd @sophie8909/pink_theme %}
###### tags: `AI` `110-2` `CSIE` `選修` `NTNU`
<!-- tag順序 [學校] [系 必選] or [學程 學程名(不含學程的 e.g. 大師創業)] [課程] [開課學期]-->
<!-- 網址名稱 AI110-1_[] -->
## Ch.04 Beyond Classical Search
### 4.1 Local Search & Optimization
- 在許多最佳化問題中，到最終解的 path 是無關緊要的
- e.g. 8-queen
- goal state 本身就是 solution
- state place 是一個完整的配置
- 這時候就適合使用 local search algorithm
- 從一個 complete conf 開始
- 做更改以增進品質
#### 4.1.1 Hill-Climbing Search (greedy local search)
- "Like climbing Everest in the thick fog with amnesia"（健忘症）
- Choose any successor with a higher value (of objective or heuristic functions) than current state
選擇比當前更高價值的下個狀態
- Choose `neighbor.VALUE > current.VALUE`

function HILL-CLIMBING(problem) return a state that is a local maximum
    current ← MAKE-NODE(problem.INITIAL-STATE)
    loop do
        neighbor ← a highest valued successor of current
        if neighbor.VALUE <= current.VALUE then return current.STATE
        current ← neighbor

- Stochastic hill-climbing
- 從 uphill 的動作中隨機選擇
- First-choice hill-climbing
- 隨機生成 successors 直到有比當前狀況更好的
- 一種 Stochastic hill climbing
- Random-restart hill climbing
- 隨機產生一個初始狀態
- 重複做 hill-climbing
- 直到找到目標
#### 4.1.2 Simulated Annealing Search
- 隨便找一個 move
- 看比較好比較差
- 比較好：採用
- 比較差：有 $e^{\Delta E/T}$ 的機率會採用
-
#### 4.1.3 Local Beam Search
- 持續追蹤 k 個 state
- 從 k 個隨機生成的狀態開始
- 所有 k 個 state 的 successors
- 如果為 goal > 回傳
- 從中選擇 k 個最好的 successor
- 資訊在這 k 個 states 中交換
- 跟 random-restart 相比
- 每個 process 都獨立運行
#### 4.1.4 Genetic Algorithms (GAs)
- Developed and pattern after biological evolution
- Formally introduced in the US in the 70s by John Holland
- Also regarded as a variant of stochastic beam search
- Successors are generated from multiple current states
- A population of potential solutions are maintained
- States are often described by bit string (like chromosomes（染色體）) whose interpretation depends on the applications
- alphabet or binary-coded (11, 6, 9) → (101101101001)
- Search begins with a population of randomly generated initial states

<!-- 0425 -->