[人工智慧導論](https://app.notion.com/p/3e6fc631b0308131b213f0a3d93fe91d) › [W3（9/24）](https://app.notion.com/p/3e6fc631b0308137bbd8e73f5c6f1b62) › 02｜影片 [0:23:12–0:42:49](https://www.youtube.com/watch?v=S1km7opW6rw&t=1392s)｜投影片 Ch4 p.2–11（p.2–9 上週講過，本週快速複習）｜上一章 [01 下週預錄課與抽算力制度（0:09–0:23）](https://app.notion.com/p/3e6fc631b030813ebaaac6d55eece1b5)｜下一章 [03 局部束搜尋與基因演算法（0:42–1:10）](https://app.notion.com/p/3e6fc631b0308105a674c6e43a405835) 跳過提示：(0:35:55–0:39:40) 老師在推導模擬退火的接受機率公式(比較 e 的負次方大小)，聽不懂可以直接跳到 [0:39:40](https://www.youtube.com/watch?v=S1km7opW6rw&t=2380s)，接著講「溫度隨時間下降，越來越保守」的生活比喻。 跳過的這段在做什麼（白話）：老師用幾個數字比大小，說明「鄰居比目前差越多，換過去的機率就越小」。這個結論在下面「接受機率」那段已經用白話講完，跳過不會漏掉概念。 ## 重點 - 第四章換了一種問題：不在乎怎麼走到答案，只要找到讓目標函數（objective function，幫每個解打分數的函數）分數最高的解。局部搜尋（local search）只記住目前這一個解，看看鄰居、往好的方向走，幾乎不花記憶體。 - 爬山法（hill climbing）每一步都換到最好的鄰居，簡單又快，但會卡在小山頂（local maximum，區域最大值）。三種變形（stochastic、first-choice、random-restart）用不同方法減少卡住，但哪一版都還是可能卡住；stochastic 版也不保證比基本版好。 - 模擬退火（simulated annealing）允許偶爾往下走：鄰居比較好就一定走；比較差就用機率 e^(ΔE/T) 決定（ΔE＝鄰居分數減目前分數）。差越多、溫度 T 越低，越不肯走，所以它前期大膽亂逛、後期越來越保守。 ## Exam-ready - **Local search**: "Local search algorithms operate using a single current node and generally move only to neighbors of that node." "They use very little memory—usually a constant amount"（Ch4 p.3） - 中文：區域搜尋（local search）只記住「目前這一個節點（node，也就是一個候選解）」,每次只看它的鄰居就決定下一步,幾乎不用額外的記憶體。白話：不建整棵搜尋樹,只留一個現在的位置往外探。 - **Optimization problem**: "Local search algorithms are useful for solving pure optimization problems, in which the aim is to find the best state according to an objective function."（Ch4 p.3） - 中文：純最佳化問題（optimization problem）只在乎依照目標函數（objective function,幫每個解打分數的函數）找出分數最高的狀態,不管怎麼走到那裡。白話：像找山頂,只看誰站得最高,不管走哪條路上山。 - **Path is irrelevant**: "In many problems, however, the path to the goal is irrelevant. In the 8-queens problem, what matters is the final configuration of queens, not the order in which they are added."（Ch4 p.2） - 中文：很多問題裡,走到答案的路徑（path）根本不重要;八皇后問題只看最後皇后擺法對不對,不管是先放哪一個皇后。白話：答案本身才算分,過程不算分。 - **Hill climbing**: "The hill-climbing search algorithm (steepest-ascent version) is simply a loop that continually moves in the direction of increasing value. It terminates when it reaches a “peak”." "Does not maintain a search tree, so the data structure for the current node need only record the state and the value of the objective function."（Ch4 p.5） - 中文：爬山法（hill climbing,最陡上升版）就是不斷往分數變高的方向移動,直到到達「頂點（peak）」就停;它不用維護搜尋樹,只要記住現在的狀態跟它的目標函數值就好。白話：一直往高處走一步,走不動了就停。 - **Greedy local search**: "Hill climbing is sometimes called greedy local search because it grabs a good neighbor state without thinking ahead about where to go next." "It turns out that greedy algorithms often perform quite well" "Hill climbing often gets stuck for the following reasons: ... Local maxima ... Ridges (屋脊) ... Plateaux (can be flat local maximum or a shoulder)"（Ch4 p.7） - 中文：爬山法也叫貪婪區域搜尋（greedy local search）,因為它只抓眼前最好的鄰居,不會想後面幾步該怎麼走;但貪婪演算法通常表現不錯。它常卡住的三個原因是區域最大值（local maxima）、山脊（ridges）、平原（plateaux,可能是平的區域最大值,也可能是肩膀）。白話：貪心選最好的下一步,但容易被地形卡住。 - **8-queens result**: "steepest-ascent hill climbing gets stuck 86% of the time, solving only 14% of problem instances." Allowing "a sideways move ... raises the percentage of problem instances solved by hill climbing from 14% to 94%."（Ch4 p.8） - 中文：最陡上升版爬山法在八皇后問題裡,86% 的時候會卡住,只解出 14% 的題目;如果允許橫著走（sideways move,分數一樣也走過去）,成功率會從 14% 升到 94%。白話：加一點「賭一把」的彈性,成功率大幅提升。 - **Hill-climbing variants**: "Stochastic hill climbing chooses at random from among the uphill moves; the probability of selection can vary with the steepness of the uphill move." "First-choice hill climbing implements stochastic hill climbing by generating successors randomly until one is generated that is better than the current state." "Random-restart hill climbing conducts a series of hill-climbing searches from randomly generated initial states until a goal is found."（Ch4 p.9） - 中文：隨機爬山法（stochastic hill climbing）在所有「往上走」的鄰居裡隨機挑一個,坡度越陡越容易被挑到;先到先選（first-choice）版本是隨機產生鄰居,第一個比目前狀態好的就直接走;隨機重啟（random-restart）版本是從很多個隨機起點各跑一次爬山法,直到找到目標。白話：三種都是想辦法讓爬山法別老是卡在同一種困境。 - **Annealing**: "Annealing is the process used to temper or harden metals and glass by heating them to a high temperature and then gradually cooling them, thus allowing the material to reach a low-energy crystalline state."（Ch4 p.10） - 中文：退火（annealing）是金屬、玻璃加工用的技術：先加熱到高溫讓分子容易變形,再慢慢降溫,讓材料穩定成低能量的結晶狀態。白話：先讓它「鬆一鬆」,再慢慢「定型」。 - **Simulated annealing**: "Instead of picking the best move, however, it picks a random move. If the move improves the situation, it is always accepted. Otherwise, the algorithm accepts the move with some probability less than 1. The probability decreases exponentially with the “badness” of the move." "“bad” moves are more likely to be allowed at the start when T is high, and they become more unlikely as T decreases."（Ch4 p.11） - 中文：模擬退火（simulated annealing）不是每次都挑最好的鄰居,而是隨機挑一個;變好就一定接受,變差就用一個小於 1 的機率決定要不要接受,而且這個機率會隨著「變差的程度」呈指數下降。溫度高的時候（剛開始）比較容易接受變差的一步,溫度降下來後就越來越不容易接受。白話：一開始敢賭一把,後面越來越保守。 - **Acceptance rule: ΔE ← next.VALUE − current.VALUE; if ΔE > 0 accept next, else accept with probability e^(ΔE/T)**: "The simulated annealing algorithm, a version of stochastic hill climbing where some downhill moves are allowed. Downhill moves are accepted readily early in the annealing schedule and then less often as time goes on."（Ch4 p.10，Figure 4.5 虛擬碼與圖說） - 中文：接受規則是先算 ΔE（下一個狀態的分數減目前分數）,如果 ΔE 大於 0（變好）就直接換過去;否則就用機率 e^(ΔE/T) 決定要不要換。這是隨機爬山法的一種版本,允許偶爾往下走;退火時程（annealing schedule）一開始容易接受往下走的步伐,之後越來越少。白話：公式就是「變好就走,變差就看機率」。 ## [0:23:12](https://www.youtube.com/watch?v=S1km7opW6rw&t=1392s) 第四章在解什麼問題 第四章在做最佳化：在所有可能的解（解空間，solution space／state space）裡，找出讓目標函數值最大的那一個。跟第三章不同，這裡只管答案本身、不管怎麼走到，例如八皇后只要最後的擺法對就好。下圖把解畫成橫軸上的一個點，但老師提醒：實際上一個解常常是高維向量（很多個數字綁在一起），所以沒辦法一眼看出哪裡最高。 八皇后問題（8-queens，這章一直拿來舉例）：在 8×8 的西洋棋盤上擺 8 個皇后，讓它們互相吃不到。皇后可以橫走、直走、斜走任意格，所以任兩個皇后不能在同一列、同一欄或同一條斜線上。 第三章（第 2 週學過：[BFS](https://app.notion.com/p/3e6fc631b030811291c5ebaf18c949df)、[A*](https://app.notion.com/p/3e6fc631b03081f7acf6d56761c8225c) 這類搜尋會一層層展開所有走法，記住從起點到終點的整條路徑）。第四章不記路徑，只記現在站的位置。 [[IMG: C:\D槽\TAICA課程\_work\notes-v2\ai-w3\img\chapter_4_search_in_complex_environments_p004.png | 狀態空間地形圖（Ch4 p.4，Figure 4.1）：橫軸是所有可能的解，縱軸是目標函數值。最高峰是全域最大值，其他小山頂是區域最大值，平台分成平的區域最大值和肩膀（shoulder，旁邊還能再往上爬）]] 圖上重點： - objective function（目標函數）：縱軸，越高代表這個解越好。 - state space（狀態空間）：橫軸，所有可能的解排成一排。 - global maximum（全域最大值）：整張圖最高的山頂，就是我們要找的答案。 - local maximum、“flat” local maximum、shoulder（區域最大值、平的區域最大值、肩膀）：會讓爬山法卡住的小山頂和平台。 - current state（目前的狀態）：圓點和箭頭代表爬山法現在站的位置，正沿坡往上走；照這樣爬，它會停在右邊的小山頂，到不了最高峰。 這張圖在講：把每個解的分數畫成地形，找最佳解就是找最高峰；但地形上有很多會騙人的小山頂和平台。下方圖說（Figure 4.1）寫的是：這是一維的地形示意圖，高度就是目標函數，目標是找到全域最大值；爬山法沿著箭頭一步步改進目前的狀態。
要先懂什麼？解、目標函數、鄰居各是什麼？ - 解（state）：一個完整的候選答案。八皇后的一個解＝8 個數字，代表每一欄的皇后在第幾列，例如 (1, 5, 8, 6, 3, 7, 2, 4)。 - 解空間：所有可能的解。八皇后每欄 8 種放法、共 8 欄，有 8^8 = 16,777,216 個解（投影片 p.8 的 “8^8 ≈ 17 million states”）。一個解有 8 個維度，這就是老師說的高維，畫不成一條曲線。 - 目標函數：幫每個解打分數，越高越好。有時改用「成本」，越低越好（例如八皇后的 h＝互相攻擊的皇后對數）；成本加負號就變回越高越好，是同一件事。 - 鄰居（neighbor／successor）：從目前的解改一小步能到的解。怎麼算一小步，由問題決定。 - 跟第三章的差別：第三章的 BFS、A* 要建搜尋樹、記住路徑；局部搜尋只記目前的解和分數，記憶體是常數，所以能處理超大甚至連續的空間（p.3）。代價是不保證找到最好的解。
老師原話是什麼？ 「我們在整個 solution space 裡面，整個解空間裡面，我們希望能夠找到一個最佳解」(0:23:27) 「我們的這個 state space，可以是在一個非常高維的空間」(0:24:22)
## [0:24:58](https://www.youtube.com/watch?v=S1km7opW6rw&t=1498s) 複習爬山法 爬山法（hill climbing）是最典型、最簡單的局部搜尋：隨機挑一個起點，看它所有的鄰居，換成分數最高的那個，一直重複，直到沒有鄰居比自己好（到達山頂）就停。老師補充實務上的停法：跑固定步數（例如 1 萬步），或分數幾乎不再改善就停。這部分（投影片 p.2–9）上週 W2 已講過，這週只快速複習。 （第 2 週學過：[07 局部搜尋與爬山演算法](https://app.notion.com/p/3e6fc631b03081e896bdc677065a3376)，爬山法就是一直往比較高的鄰居走一步，走不動就停。） 下面第一個摺疊有兩樣東西：一是虛擬碼（pseudocode，用接近英文的句子寫出程式步驟，不能直接執行，只是讓人看懂邏輯）；二是用一條十格的小地形手算爬山法。算出來的結論是：同一個演算法，起點只差一格，可能找到最高峰，也可能卡在小山頂。
它到底怎麼運作？在小地形上手算一次 虛擬碼（Ch4 p.5，Figure 4.2）： ``` 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 ``` 設一個一維小地形：x = 0 到 9，分數 f(x) 依序是 1, 3, 6, 9, 7, 4, 5, 8, 6, 2；x 的鄰居是 x−1 和 x+1。最高分在 x=3（9 分），x=7（8 分）是小山頂。 - 從 x=5（4 分）出發：鄰居 x=4（7）、x=6（5）→ 走到 x=4；鄰居 x=3（9）、x=5（4）→ 走到 x=3；鄰居 x=2（6）、x=4（7）都不比 9 好 → 停。找到全域最大值。 - 從 x=6（5 分）出發：鄰居 x=5（4）、x=7（8）→ 走到 x=7；鄰居 x=6（5）、x=8（6）都不比 8 好 → 停。卡在區域最大值。 - 起點只差一格，答案就不一樣。這就是後面「隨機重啟」要解決的事。
「鄰居」到底怎麼定？ 老師用「方圓 5 公尺」比喻鄰居，並說明不同問題的鄰居定義不一樣。以八皇后為例（p.6）： - 鄰居＝把某個皇后移到同一欄的另一格：8 欄 × 每欄 7 個別的位置 = 56 個鄰居。 - 用成本 h（互相攻擊的皇后對數）時，要找 h 最低的鄰居（Figure 4.2 圖說）。 - 有好幾個鄰居一樣好時，通常從中隨機挑一個。 - p.6 的 Figure 4.3：(a) 盤面 h = 17，每格的數字是「把那一欄的皇后移到這格後的 h」，最小的 12 就是最好的鄰居；(b) 是區域最小值，h = 1 但每個鄰居的 h 都更高，爬山法停在這裡。
老師原話是什麼？ 「它是一個最典型，簡單的 local search 的演算法」(0:25:05) 「所謂的方圓 5 公尺，只是一個比喻」(0:26:38)
## [0:28:20](https://www.youtube.com/watch?v=S1km7opW6rw&t=1700s) 卡在區域最大值 爬山法只看得到身邊：走到小山頂時四周都比自己低，它就以為自己最高，停在區域最大值（local maximum）。我們看圖知道真正的最高點在別處，但那是上帝視角；真實問題的曲面在高維空間裡根本畫不出來，所以只能從局部一步一步探。投影片還列了另外兩種會卡住的地形：山脊（ridge）和平原（plateau）。 表格後面的摺疊在回答：這些地形真的常常讓它卡住嗎？答案是會。八皇后用最基本的爬山法，86% 的題目會卡住；只要允許「分數一樣也往旁邊走」，大部分題目就解得出來。
地形長什麼樣為什麼卡住
**Local maximum**（區域最大值）比所有鄰居高、但比全域最大值低的小山頂四周都比較低，沒有往上的一步
**Ridge**（山脊）斜斜往上的稜線，上面排著一串不相連的小山頂（p.7 Figure 4.4）從每個小山頂出發，能走的方向都是下坡
**Plateau**：flat local maximum一塊平地，四周都是下坡鄰居一樣高，沒有更好的一步
**Plateau**：shoulder（肩膀）一塊平地，另一頭還能往上爬看不出哪邊能爬；允許橫著走（sideways move）才過得去
八皇后實際上多常卡住？（p.8，上週講過） - 最陡上升版爬山法 86% 會卡住，只解出 14% 的題目；但很快，成功平均 4 步、卡住平均 3 步。 - 允許橫著走（分數一樣也走過去，賭平地其實是肩膀）：成功率從 14% 升到 94%，代價是成功平均 21 步、失敗平均 64 步。 - 橫著走要限制連續次數（例如最多 100 次），不然在真正的平頂上會一直走不完（我補充）。
老師原話是什麼？ 「當你實際的解一個真正的問題的時候，你根本就沒有上帝視角」(0:28:57)
## [0:29:26](https://www.youtube.com/watch?v=S1km7opW6rw&t=1766s) 爬山法的三種變形 為了少卡一點，爬山法有三種變形：stochastic（隨機）版在比自己好的鄰居裡隨機挑；first-choice（先到先選）版隨機產生鄰居，第一個比自己好的就走；random-restart（隨機重啟）版從不同的隨機起點重跑好幾次，留最好的。老師說明：stochastic 版不保證比基本版好，要看問題而定；而且不管哪一版都還是可能卡在區域最大值，會不會卡住除了演算法本身，也跟起點落在山脈的哪裡有關，所以才有換起點重跑的 random-restart。 「隨機」（stochastic、random）在這裡的意思是：帶有抽籤的成分，同一題每次跑，走的路可能不一樣。 表格後面有兩個算例摺疊。第一個用同一組鄰居分數，看四個版本各會挑哪一個，結論是隨機的版本不一定挑最好的那個；第二個在算隨機重啟平均要重跑幾次，結論是只要跑一次的成功率不要太低，重跑幾次就幾乎一定找得到。
版本下一步怎麼選好處代價
**Steepest-ascent**（基本版）看完全部鄰居，挑最好的每步進步最多每步要算全部鄰居；容易卡住
**Stochastic**在上坡的鄰居裡隨機挑，越陡越容易被挑中不走最貪婪的路；老師說第三好的鄰居說不定看到更好的風景通常爬得比較慢（我補充）
**First-choice**隨機產生鄰居，第一個比自己好的就走不用掃完全部鄰居；鄰居成千上萬時很省（我補充）還是會卡住
**Random-restart**從不同隨機起點重跑，直到找到目標（純最佳化就留最好的）起點夠多就會碰到對的山，找到目標的機率趨近 1（我補充）要重跑很多次
它到底怎麼運作？同一組鄰居，各版本怎麼選？ 目前 10 分，五個鄰居是 12、15、9、18、11。 - 基本版：直接挑 18。 - Stochastic：上坡的是 12、15、18、11，進步量 +2、+5、+8、+1，合計 16。照進步量分配機率：18 是 8/16 = 50%、15 是 5/16 ≈ 31%、12 是 2/16 = 12.5%、11 是 1/16 ≈ 6%。可能走到 15 而不是 18。 - First-choice：先抽到 9（比較差，丟掉），再抽到 12（比較好）→ 馬上走，根本沒看到 18。 - Random-restart（用上一段的一維地形）：從 x=6 出發停在 x=7（8 分）；從 x=9 出發經 x=8 停在 x=7（8 分）；從 x=1 出發經 x=2 到 x=3（9 分）。留最好的 → 9 分。
隨機重啟平均要跑幾次？ （我補充）跑一次成功的機率是 p，平均要跑 1/p 次；總步數 ≈ 成功那次的步數 ＋ (1−p)/p × 失敗一次的步數。 - 八皇后、不允許橫著走：p ≈ 0.14，平均 1/0.14 ≈ 7 次（約 6 敗 1 成）。總步數 ≈ 4 ＋ (0.86/0.14) × 3 ≈ 22 步。 - 允許橫著走：p ≈ 0.94，平均約 1.06 次，總步數 ≈ 21 ＋ (0.06/0.94) × 64 ≈ 25 步。 - 投影片 p.9：爬山法成不成功，很大程度取決於地形長什麼樣（the shape of the state-space landscape）。
老師原話是什麼？ 「你不要走那個貪婪的，最貪婪的路線」(0:30:09) 「並沒有保證說，這個 Stochastic Hill Climbing，表現的一定會比基礎的 Hill Climbing 來得好，不見得，要看問題而定」(0:30:39)
## [0:31:58](https://www.youtube.com/watch?v=S1km7opW6rw&t=1918s) 模擬退火的由來 模擬退火（simulated annealing）的名字來自打鐵、煉玻璃用的退火（annealing）：先加熱到高溫，分子鬆動、容易塑形；再慢慢冷卻，讓材料定型成穩定的結晶。演算法模仿這個過程：溫度高時允許亂動，溫度低時就定型。
用生活例子講？ （我補充）常見的比喻：凹凸不平的托盤上有一顆乒乓球，想讓它停在最深的洞。只讓它自己滾，會卡在最近的小洞；先用力搖（高溫），球會跳出小洞，再慢慢搖輕（降溫），球比較可能停在最深的洞。 物理退火求的是能量最低（p.10 的 low-energy crystalline state），所以虛擬碼的差值叫 ΔE（E＝energy）；投影片的演算法改成求分數最高，方向相反，概念一樣。
老師原話是什麼？ 「當溫度高的時候，分子之間比較容易變動，比較容易塑形，溫度低的時候，他的整個結構就固定了」(0:33:01)
## [0:33:12](https://www.youtube.com/watch?v=S1km7opW6rw&t=1992s) 模擬退火的流程 流程跟 first-choice 爬山法很像：每一輪隨機挑一個鄰居 next，算 ΔE ＝ next 的分數 − 目前的分數。ΔE > 0（鄰居比較好）就一定換過去；ΔE ≤ 0（鄰居比較差）也不直接拒絕，而是有一定的機率換過去。這就是它能跳出區域最大值的原因：先暫時退到比較差的位置，說不定從那邊能爬上更高的山。 ΔE 讀作「delta E」：Δ 是希臘字母，數學上習慣用它表示「差多少」，ΔE 就是「新的分數減舊的分數」。正的代表變好，負的代表變差。 下面第一個摺疊的虛擬碼，就是把上面這段話寫成程式步驟：每一輪先查現在的溫度，溫度降到 0 就停；否則抽一個鄰居、算 ΔE、決定換不換。
它到底怎麼運作？逐行看虛擬碼 虛擬碼（Ch4 p.10，Figure 4.5）： ``` current ← MAKE-NODE(problem.INITIAL-STATE) for t = 1 to ∞ do T ← schedule(t) if T = 0 then return current next ← a randomly selected successor of current ΔE ← next.VALUE − current.VALUE if ΔE > 0 then current ← next else current ← next only with probability e^(ΔE/T) ``` - 小寫 t 是第幾輪，大寫 T 是溫度。schedule 是事先定好的「時間 → 溫度」對照表；T 降到 0 就回傳目前的解。 - 每輪只抽一個鄰居。跟 first-choice 不同：first-choice 會一直抽到比較好的才走；模擬退火抽到比較差的也可能走過去。所以圖說把它定位成「允許某些下坡步的 stochastic hill climbing」。 - 細節：ΔE = 0 會走到 else，機率 e^0 = 1，所以一樣好的鄰居一定被接受。
要先懂什麼？「以某個機率接受」在程式裡怎麼做？ 抽一個 0 到 1 之間的隨機數 r，r 小於機率 p 就接受，否則留在原地。例如 p = 0.74，跑 100 次大約有 74 次接受。
用生活例子講？ 老師的比喻：畢業找第一份工作，不一定要挑薪水最高的。選薪水第二、第三高的小公司，說不定未來潛力更大。短期看起來比較差的一步，可能通往更好的地方，也就是「退一步海闊天空」。
老師原話是什麼？ 「我有可能用一個比較爛的解答，來取代掉，目前這個比較好的解答」(0:34:51) 「我退一步海闊天空嘛」(0:35:03)
## [0:35:53](https://www.youtube.com/watch?v=S1km7opW6rw&t=2153s) 接受機率 e^(ΔE/T) 比較差的鄰居被接受的機率是 e^(ΔE/T)。會走到這一行代表 ΔE ≤ 0，指數是負的，算出來一定在 0 到 1 之間。鄰居差越多（ΔE 越負），機率越小；只差一點點，機率接近 1。投影片的說法是：接受機率隨著這一步的「爛的程度」（badness）指數下降。 這條公式要解決的問題是：比較差的鄰居，到底要給它多少機會？算出來的數字就是「換過去的機率」，例如 0.6 代表大約十次會換六次。「指數下降」（exponentially）的意思不是一點一點變少，而是越差掉得越快，很快就接近 0。 下面摺疊先補指數的基本概念，再代幾個數字看機率怎麼變。
要先懂什麼？指數函數 e^x 老師說聽起來吃力就先複習指數的定義。短版： - e ≈ 2.718 是一個常數；e^0 = 1。 - 負的次方＝倒數：e^(−2) = 1 / e^2 = 1 / 7.389 ≈ 0.135（老師舉的例子）。 - 指數是負數時，結果一定在 0 和 1 之間，越負越接近 0。 - 所以 e^(負數) 天生就能當機率，而且「越差 → 越小」剛好是我們要的行為。
它到底怎麼運作？算幾個數字 固定 T = 1，只看 ΔE： - 只差一點點，ΔE = −0.001 → e^(−0.001) ≈ 0.999，幾乎一定接受。 - 差一些，ΔE = −0.5 → e^(−0.5) ≈ 0.607。 - 差很多，ΔE = −2 → e^(−2) ≈ 0.135，大部分時候拒絕。
老師原話是什麼？ 「如果鄰居比我爛很多，我用它來取代掉，我的機率就很低」(0:37:25)
## [0:38:35](https://www.youtube.com/watch?v=S1km7opW6rw&t=2315s) 溫度 T 逐漸下降 分母的 T 是溫度，由 schedule 決定：一開始高，隨著迭代次數增加慢慢降低。同樣的 ΔE，T 大時 ΔE/T 接近 0，機率接近 1；T 小時 ΔE/T 是很大的負數，機率接近 0。所以演算法前期願意接受爛的鄰居、到處探索，後期幾乎只往上爬，T 降到 0 就停。 迭代（iteration）就是演算法重複跑的「每一輪」，迭代次數增加＝跑了越多輪。下表的意思：同樣差一點或差很多，溫度越低，接受的機率掉得越兇。 後面「手算一次」的摺疊，用前面那條十格小地形實際跑五輪：前期溫度高，接受了變差的步，才從小山頂跳出來；後期溫度低，拒絕變差的步，才守住最高峰。
溫度 TΔE = −1（差一點）ΔE = −3（差很多）
T = 10（前期，很熱）e^(−0.1) ≈ 0.905e^(−0.3) ≈ 0.741
T = 1（中期）e^(−1) ≈ 0.368e^(−3) ≈ 0.050
T = 0.1（後期，很冷）e^(−10) ≈ 0.000045e^(−30) ≈ 9 × 10^(−14)，幾乎是 0
**注意：老師口頭說隨著迭代次數增加，溫度會「急劇的下降」(0:40:35)；投影片 p.10 寫的是 gradually cooling（慢慢冷卻），Figure 4.5 圖說也說變差的一步是早期容易被接受、之後越來越少。考試寫投影片的版本。**
它到底怎麼運作？在小地形上手算一次 沿用一維地形 f(x) = 1, 3, 6, 9, 7, 4, 5, 8, 6, 2（x = 0 到 9），從爬山法會卡住的 x=7（8 分）出發。溫度表 T = 10 × 0.5^(t−1)，也就是 10、5、2.5、1.25、0.625。r 是每輪抽的隨機數。 - t=1，T=10：抽到 x=6（5 分），ΔE = −3，機率 e^(−0.3) ≈ 0.741；r = 0.62 小於 0.741 → 接受。爬山法絕對不會走這一步。 - t=2，T=5：抽到 x=5（4 分），ΔE = −1，機率 e^(−0.2) ≈ 0.819；r = 0.35 → 接受，走到谷底。 - t=3，T=2.5：抽到 x=4（7 分），ΔE = +3 → 直接走。 - t=4，T=1.25：抽到 x=3（9 分），ΔE = +2 → 直接走，到達全域最大值。 - t=5，T=0.625：抽到 x=2（6 分），ΔE = −3，機率 e^(−4.8) ≈ 0.008；r = 0.47 → 拒絕，留在 x=3。 同樣是 ΔE = −3，熱的時候 74% 接受，冷的時候只剩 0.8%。前期敢下山，才跳出 x=7；後期不肯下山，才守住 x=3。
降溫降得夠慢會怎樣？ （我補充）schedule 把 T 降到 0 的速度夠慢，找到全域最大值的機率會趨近 1。降太快就太早變冷，跟爬山法一樣容易卡住；溫度很低時幾乎不接受變差的一步，行為接近 first-choice 爬山法。
用生活例子講？ 老師的比喻：年輕時不怕失敗，可以投資高風險的資產（高溫，願意接受變差）；快退休時改成低風險的資產，不能接受變差（低溫）。「蹲下是為了跳起來」。
別人怎麼教這個？ [Wikipedia：Simulated annealing](https://en.wikipedia.org/wiki/Simulated_annealing) 頁首有一段動畫：模擬退火在一條有很多小山頂的曲線上找最高點，前期跳來跳去，慢慢降溫後越來越穩，最後停在最高峰。
老師原話是什麼？ 「隨著 Iteration 數量增加，我的溫度就會急劇的下降」(0:40:33) 「我就越來越不願意，用比較爛的鄰居來取代掉我的意思」(0:41:07) 「因為蹲下是為了跳起來」(0:42:19) 講完後老師說「那這個請大家自己去看」(0:42:41)，指的應該是 p.10–11 投影片上的文字。
## Self-check
Q1. Why may hill climbing fail to find the global maximum? Name three landscape features that make it get stuck.（中文：為什麼爬山法可能找不到全域最大值？說出三種讓它卡住的地形。） **Answer**: Hill climbing is greedy local search: it only looks at the neighbors of the current state and stops when no neighbor is better. It gets stuck at local maxima (peaks higher than their neighbors but lower than the global maximum), ridges (a sequence of local maxima not directly connected to each other), and plateaux (a flat local maximum or a shoulder). 中文：爬山法只看現在這個狀態的鄰居,一旦沒有鄰居比自己好就停下來,所以它可能被困在三種地形——區域最大值（比周圍高、但比真正最高點低的小山頂）、山脊（一串沒有直接相連的小山頂,順著稜線走反而是下坡）、平原（一整塊分數一樣高的平地,可能是真正卡死的平頂,也可能是還能往上爬的肩膀）。
Q2. In simulated annealing, a move with ΔE = −2 is proposed. Compute its acceptance probability at T = 10 and at T = 0.5. What does this show?（中文：在模擬退火中,提出一個 ΔE = −2 的移動,分別算出 T = 10 與 T = 0.5 時的接受機率,這說明了什麼？） **Answer**: The probability is e^(ΔE/T). At T = 10: e^(−0.2) ≈ 0.819. At T = 0.5: e^(−4) ≈ 0.018. "Bad" moves are more likely to be allowed at the start when T is high, and become more unlikely as T decreases. 中文：算法是 e^(ΔE/T)。溫度高（T=10）時,e^(−0.2) ≈ 0.819,大約 82% 的機率會接受這個變差的移動;溫度低（T=0.5）時,e^(−4) ≈ 0.018,只剩不到 2% 的機率會接受。這說明同一個「壞」步伐,在演算法剛開始、溫度高的時候很容易被接受,隨著溫度降低,到後期幾乎不會再被接受——這就是模擬退火「先探索、後收斂」的行為。
Q3. Compare stochastic, first-choice, and random-restart hill climbing.（中文：比較隨機爬山法、先到先選爬山法、隨機重啟爬山法。） **Answer**: Stochastic hill climbing chooses at random among the uphill moves, with probability that can vary with steepness. First-choice generates successors randomly until one is better than the current state, which is good when a state has many successors. Random-restart conducts a series of hill-climbing searches from randomly generated initial states until a goal is found (for pure optimization, keep the best result). 中文：隨機爬山法是在所有「往上走」的鄰居裡隨機挑一個,坡度越陡被挑到的機率越高;先到先選版是隨機產生鄰居,一遇到比目前狀態好的就馬上走,鄰居很多時特別省時間;隨機重啟版是從很多個隨機起點各跑一次完整的爬山法,直到找到目標為止（如果只是要最佳化,就留下所有結果中最好的一個）。三種都是想辦法避開爬山法容易卡住的問題,但用的手段不同。
Q4. How does simulated annealing differ from hill climbing, and what is the role of the schedule?（中文：模擬退火跟爬山法有什麼不同？時程（schedule）扮演什麼角色？） **Answer**: Hill climbing only accepts improving moves. Simulated annealing picks a random successor, always accepts it if it is better, and otherwise accepts it with probability e^(ΔE/T), so it can escape local maxima. The schedule maps time t to temperature T; T starts high and is lowered gradually, and the algorithm returns the current state when T = 0. 中文：爬山法只接受讓分數變好的一步。模擬退火每次隨機挑一個鄰居,如果變好就一定接受,如果變差也不是直接拒絕,而是用機率 e^(ΔE/T) 決定要不要接受,所以它有機會跳出區域最大值。時程（schedule）負責把「第幾輪」對應到「溫度 T」：溫度一開始設得高、之後慢慢降低,溫度降到 0 時演算法就停下來,回傳目前的狀態。
讀完了嗎？下一章：[03 局部束搜尋與基因演算法（0:42–1:10）](https://app.notion.com/p/3e6fc631b0308105a674c6e43a405835)｜回到週頁：[W3（9/24）](https://app.notion.com/p/3e6fc631b0308137bbd8e73f5c6f1b62)