[人工智慧導論](https://app.notion.com/p/3e6fc631b0308131b213f0a3d93fe91d) › [W3（9/24）](https://app.notion.com/p/3e6fc631b0308137bbd8e73f5c6f1b62) › 03｜影片 [0:42:49–1:10:01](https://www.youtube.com/watch?v=S1km7opW6rw&t=2569s)｜投影片 Ch4 p.12–15｜上一章 [02 爬山法複習與模擬退火（0:23–0:42）](https://app.notion.com/p/3e6fc631b03081a79865f701c688c1c4)｜下一章 [04 連續空間的梯度上升（1:21–1:40）](https://app.notion.com/p/3e6fc631b030812a99d4eb793b437690) ## 重點 - Local beam search（局部束搜尋）一次拿著 k 個解：每一步把 k 個解的鄰居全部倒進同一個池子，只留最好的 k 個。它不等於「同時跑 k 次 random restart」，因為 k 條搜尋線會互相傳遞資訊，好的區域可以把名額全部搶走。 - Stochastic beam search（隨機束搜尋）改成依機率抽 k 個，分數越高越容易被抽中。Genetic algorithm（基因演算法，GA）是它的變形：新解不是改動一個舊解，而是把兩個「父母」解組合起來。 - GA 每一代做三件事：依 fitness（適應度）按比例挑父母 → crossover（交配：隨機切一刀，前後段對接）→ mutation（突變：每個位置有很小的機率被亂改）。繁衍很多代後回傳最好的個體；能不能用 GA，關鍵在能不能把問題寫成一串「染色體」。 ## Exam-ready - **Local beam search**: "The local beam search algorithm keeps track of k states rather than just one."（Ch4 p.12） - 中文：Local beam search 不像爬山法只顧一個解，而是同時抓著 k 個解一起搜尋。白話：不是一個人找路，是一次派 k 個人一起找。 - **Local beam search (steps)**: "It begins with k randomly generated states. At each step, all the successors of all k states are generated. If any one is a goal, the algorithm halts. Otherwise, it selects the k best successors from the complete list and repeats."（Ch4 p.12） - 中文：一開始隨機生出 k 個解；每一步把這 k 個解的所有鄰居（successors）都生出來，只要裡面有一個是目標就停，否則從全部鄰居裡選出最好的 k 個，再重複。白話：每一輪把大家的鄰居全部攤開來比，只留分數最高的 k 個繼續走。 - **Beam search vs. random restart**: "A local beam search seem to be nothing more than running k random restarts in parallel instead of in sequence. In a random-restart search, each search process runs independently of the others. In a local beam search, useful information is passed among the parallel search threads."（Ch4 p.12）【老師強調】(0:45:14) - 中文：乍看 local beam search 只是把 k 次 random restart（隨機重新起跑）改成同時跑而不是依序跑，其實不一樣：random restart 每條搜尋線各自獨立，互不知道對方進度；local beam search 的 k 條搜尋線之間會互相傳遞「哪裡分數高」的資訊。白話：random restart 是各自找路、互不通報；local beam search 是大家會互相報路況，好路線可以把名額全部搶走。 - **Stochastic beam search**: "Stochastic beam search chooses k successors at random, with the probability of choosing a given successor being an increasing function of its value."（Ch4 p.12） - 中文：Stochastic beam search（隨機束搜尋）不再固定挑最好的 k 個，而是隨機抽 k 個，分數越高的解被抽中的機率越大（機率是分數的遞增函數）。白話：分數高的人中獎機率比較大，但分數低的人還是有機會，不會全部被淘汰。 - **Genetic algorithm**: "A genetic algorithm (or GA) is a variant of stochastic beam search in which successor states are generated by combining two parent states rather than by modifying a single state."（Ch4 p.13） - 中文：基因演算法（GA）是 stochastic beam search 的一種變形：新的解不是從一個舊解改一點點得到，而是把兩個「父母」解組合起來產生。白話：不是自己突變出新解，而是跟另一個解「生小孩」。 - **Population / individual**: "GAs begin with a set of k randomly generated states, called the population. Each state, or individual, is represented as a string over a finite alphabet—most commonly, a string of 0s and 1s."（Ch4 p.13） - 中文：GA 一開始也是隨機生出 k 個解，這一整組合稱 population（族群），其中每一個解叫 individual（個體），通常寫成由有限字母組成的字串，最常見是 0 和 1。白話：population 是這一代全部的解，individual 是裡面單獨一個解。 - **Fitness function**: "A fitness function should return higher values for better states. The probability of being chosen for reproducing is directly proportional to the fitness score."（Ch4 p.14） - 中文：fitness function（適應度函數）幫每個解打分數，分數越高代表這個解越好；被挑去繁殖下一代的機率，直接跟這個分數成正比。白話：分數愈高，越容易被選去當爸媽生小孩。 - **Crossover**: "For each pair to be mated, a crossover point is chosen randomly from the positions in the string."（Ch4 p.14） - 中文：交配（crossover）時，每一對要配對的父母會隨機選一個切點（crossover point），把兩個字串都從那個位置切開再重新拼接。白話：兩個解各切一刀，前段和後段互相交換接起來，變成新的解。 - **Mutation**: "Finally, each location is subject to random mutation with a small independent probability. In the 8-queens problem, this corresponds to choosing a queen at random and moving it to a random square in its column."（Ch4 p.15） - 中文：交配完之後，字串裡的每一個位置都有一個很小、彼此獨立的機率被隨機改掉，這就是突變（mutation）；在八皇后問題裡，做法是隨機挑一個皇后，把它移到同一欄裡的隨機一格。白話：用很小的機率亂改一個數字，替族群製造新的可能性。 - **GA loop (Figure 4.8)**: "until some individual is fit enough, or enough time has elapsed … return the best individual in population, according to FITNESS-FN"（Ch4 p.15） - 中文：這段虛擬碼是說：不斷繁殖新一代，直到有個體夠好、或時間用完為止，最後回傳目前族群裡 fitness 最高的那一個個體。白話：一直生小孩、選最強的留下來，直到夠好或時間到，交出當前最強的答案。 ## [0:42:49](https://www.youtube.com/watch?v=S1km7opW6rw&t=2569s) 局部束搜尋：一次追蹤 k 個解 爬山法和模擬退火一次只拿著「一個」解，看它的鄰居再決定要不要換過去。Local beam search 改成一開始在 state space（狀態空間：所有可能的解）裡隨機撒 k 個解；每一步把這 k 個解的鄰居（successors）全部產生出來、放進同一張清單，只留分數最好的 k 個，然後重複，清單裡只要出現目標就停。老師的例子：撒 10 個解、每個看 10 個鄰居，總共 100 個鄰居，再從這 100 個裡挑最好的 10 個 (0:44:07)。 模擬退火是上一章 [02 爬山法複習與模擬退火](https://app.notion.com/p/3e6fc631b03081a79865f701c688c1c4) 教的：跟爬山法一樣看鄰居，但偶爾願意往下坡走一步，越到後面越不肯，用來逃出小山頭。這裡的「解」課本叫 state（狀態），就是問題的一種可能樣子，例如八皇后的一個盤面（[第 2 週](https://app.notion.com/p/3e6fc631b0308175a433e5fa4bc500df)學過：搜尋就是在一堆 state 之間移動，直到找到目標 state）。 下面「手算一次」在做什麼：用一條只有 12 格的小山路，實際跑三輪 k = 2 的 local beam search。要看的是兩條搜尋線怎麼互搶名額，以及為什麼最後兩個名額都跑到比較高的那座山。
要先懂什麼？ - **Objective function（目標函數）**：幫每個解打分數，越高越好；鄰居（neighbor／successor）是把目前的解改一點點得到的解。 - **Hill climbing（爬山法）**：永遠往最好的鄰居走，所以會卡在 local maximum（局部最大值：附近最高、但不是全世界最高）；**random restart** 就是卡住換起點重爬。細節見上一章。
它到底怎麼運作？手算一次 一條一維的小地形：x = 0 到 11 的分數依序是 1、2、3、4、3、2、5、6、8、10、7、5。左邊小山頂在 x = 3（f = 4，local maximum），右邊大山頂在 x = 9（f = 10，全域最大值）。鄰居＝左右各一格，k = 2，一開始隨機撒在 x = 1 和 x = 6，目標是 f ≥ 10。
步驟目前的 2 個解所有鄰居（括號是分數）留下最好的 2 個
1x=1、x=6x=0 (1)、x=2 (3)、x=5 (2)、x=7 (6)x=7 (6)、x=2 (3)
2x=7、x=2x=1 (2)、x=3 (4)、x=6 (5)、x=8 (8)x=8 (8)、x=6 (5)
3x=8、x=6x=5 (2)、x=7 (6)、x=9 (10)x=9 是目標，停
看第 2 步：左邊那條線最好的鄰居是 x = 3（f = 4），但它輸給右邊的 x = 6（f = 5），名額被搶走。從此兩個名額都在右邊的大山上，第 3 步就到山頂。
## [0:44:42](https://www.youtube.com/watch?v=S1km7opW6rw&t=2682s) 跟 random restart 差在哪 聽起來 local beam search 只是「同時跑 k 次 random restart」，其實不一樣。Random restart 每一次重跑都是獨立的開始 (0:47:06)，彼此不知道對方找到什麼；local beam search 把 k 條線的鄰居放在一起 PK，好的區域可以把 k 個名額全部拿走，等於資訊在平行的搜尋線之間流動。【老師強調】(0:45:14) 老師的例子：撒 5 個解、每個看 10 個鄰居，50 個鄰居裡挑最好的 5 個，有可能 5 個全部來自第 1 個解的鄰居，也可能是 2、1、2 這樣分散 (0:45:54)。回到上一段的手算：random restart 從 x = 1 出發會爬到 x = 3 就卡住、白走一趟才重來；local beam search 在第 2 步就把左邊那條淘汰了。
用生活例子講？ 十支探勘隊找金礦。Random restart：十隊各自挖、彼此不通電話，挖到空礦也要挖到底才換地方。Local beam search：每天晚上十隊把今天看到的 100 個點全部回報，隔天只派人去最有希望的 10 個點；好礦都在東邊的話，十隊隔天就全部移到東邊。好處是不浪費人力；壞處是大家都擠到東邊，西邊萬一有更大的礦就沒人看了（課本說這叫缺乏多樣性，k 個解擠在同一小區）。
老師原話是什麼？ 「差別在於 Local Beam Search，它其實有不同 Solution 之間的溝通，再講一次，再講一次」(0:45:14) 「這五十個裡面，我要挑最好的五個出來，有可能喔，有可能我挑出來的這五個，全部來自剛剛的第一個 Solution 的那十個鄰居裡面」(0:45:54)
## [0:47:22](https://www.youtube.com/watch?v=S1km7opW6rw&t=2842s) 它是一種策略，也有隨機版 老師說嚴格來講，local beam search 不是一個固定的演算法，而是一種搜尋策略：撒出 k 個解之後，可以搭配爬山法往前走，也可以搭配模擬退火 (0:47:23)。Stochastic beam search 不再固定挑最好的 k 個，而是隨機挑 k 個，但分數越高、被挑中的機率越高。這樣分數普通的解也有機會活下來，k 個解比較不會全部擠在同一座山上，正好補上一段講的缺點。 **注意：老師口頭說的是「跟我目前現有的 Solution 差不多的，我挑的機率就越高」(0:48:23)，跟投影片不同。考試寫投影片的版本：被挑中的機率是該 successor 分數（value）的遞增函數，分數越高越容易被挑。** 遞增函數（increasing function）白話就是「輸入越大、輸出就越大」的規則；放在這裡，就是分數越高、被抽中的機率越高。 下面「手算一次」在做什麼：把四個鄰居的分數換算成被抽中的機率（自己的分數 ÷ 全部分數加總）。結論是左邊小山的解加起來還有約三成機會被留下，這就是「隨機版比較不會全部擠在同一座山」的原因。
它到底怎麼運作？手算一次 接第一段手算的第 2 步，四個鄰居是 x = 1、3、6、8。用最簡單的遞增函數「機率跟分數成正比」，總分 2 + 4 + 5 + 8 = 19。
鄰居分數每抽一次被抽中的機率
x=1（左邊小山）22/19 ≈ 10.5%
x=3（左邊小山）44/19 ≈ 21.1%
x=6（右邊大山）55/19 ≈ 26.3%
x=8（右邊大山）88/19 ≈ 42.1%
普通 local beam search 在這一步一定丟掉左邊小山；stochastic 版每抽一次，仍有 6/19 ≈ 31.6% 的機會抽到左邊，保留了多樣性。
深度學習裡哪裡會看到 beam search？ 老師提醒 beam search 不是老古董，訓練深度學習模型時也會看到 (0:48:48)。老師用中文的「一束」來記：一次看一堆解，像把稻草捆成一束 (0:48:58)。 以下是我補充：最常見的是模型「產生句子」的時候（decoding，解碼：一個字一個字生出輸出），例如機器翻譯、語言模型：每一步把留著的 k 句各自接上所有可能的下一個字，只留整句機率最高的 k 句。這個 k 叫 beam width（束寬）；英文 beam 原意是「光束」，像手電筒只照亮最有希望的一小束路線。
## [0:49:17](https://www.youtube.com/watch?v=S1km7opW6rw&t=2957s) 基因演算法的名詞 GA 是 stochastic beam search 的變形，靈感來自演化論的「適者生存」。它一樣從 k 個隨機產生的解出發，這 k 個解合稱 population（族群），每一個解叫 individual（個體）。跟 beam search 最大的不同是：新的解不是「改動一個舊解」，而是「把兩個父母解組合起來」。為了能組合，每個解都要寫成由有限字母組成的字串，最常見的是 0 和 1 組成的 binary string，例如 01101010。 兩個名詞補充：finite alphabet（有限字母）是說字串裡能用的符號種類只有固定幾種，例如只能用 0 和 1，或只能用 1 到 8；binary string（二進位字串）就是只用 0 和 1 寫成的一串，像電腦存資料的方式。
GA 的名詞換成搜尋的說法八皇后的例子
population（族群）目前手上的 k 個解4 個盤面
individual（個體）一個解（state）一個盤面
chromosome（染色體）把一個解寫成的字串32752411
gene（基因）字串裡的一個位置第 3 個數字 7：第 3 欄的皇后在第 7 列
fitness function（適應度函數）目標函數，越大越好互不攻擊的皇后有幾對
generation（世代）一輪迭代第 1 代、第 2 代……
老師原話是什麼？ 「基因演算法，它其實是 Stochastic Beam Search 的一個變形」(0:49:36) 「這個群體裡面有一個個個體，每一個個體，其實就是一個解的意思」(0:50:37)
## [0:51:36](https://www.youtube.com/watch?v=S1km7opW6rw&t=3096s) 八皇后：染色體與適應度 八皇后問題：在 8×8 棋盤放 8 個皇后，任兩個不能互相攻擊（同一列、同一欄、同一條斜線都算）。規定每一欄只放一個，所以一個盤面只要記「每一欄的皇后在由下往上數第幾列」：32752411 就是第 1 欄在第 3 列、第 2 欄在第 2 列、第 3 欄在第 7 列……這一串就是 chromosome（染色體），每個數字是一個 gene（基因）(0:53:18)。接著用 fitness（適應度）幫每個盤面打分數，數字越大表示越好；投影片的四個盤面分別是 24、23、20、11 分 (0:54:59)。 老師說八皇后的 fitness 可以從皇后之間的衝突來設計 (0:54:07)，這個標準也可以自己定 (0:55:09)。課本用的定義是「互不攻擊的皇后有幾對」，下面照這個算。 下面「手算一次 fitness」在做什麼：一對一對數出盤面上有幾對皇后會互相攻擊，再用滿分 28 減掉。算出來正好是投影片上的 24、23、20、11，目的是讓你知道這些分數怎麼來的；考試能說出「fitness 是互不攻擊的皇后對數，越高越好」就夠。 [[IMG: C:\D槽\TAICA課程\_work\notes-v2\ai-w3\img\ai_w3_ch03_p014.png | Ch4 p.14 圖 4.7：左邊是 32752411、中間是 24748552，切在第 3 欄後面，接成右邊的子代 32748552；灰色欄位是交配時被丟掉的部分]] 圖上重點：這張是投影片 Ch4 p.14，用真的棋盤畫出交配。 - 上方兩行英文：fitness function 要讓越好的盤面分數越高；被選去繁殖的機率跟分數成正比。每一對要交配的父母，隨機選一個切點（crossover point）。 - 「+」左右兩個棋盤是父母 32752411 和 24748552，粗黑直線是切點，在第 3 欄後面。 - 「=」右邊是生出的小孩 32748552：前 3 欄來自左邊父母，後 5 欄來自中間父母。 - 下方 Figure 4.7 的英文：這是圖 4.6(c) 前兩個父母和 (d) 第一個小孩的盤面；灰色（shaded）欄位在交配時被丟掉，白色（unshaded）欄位被保留。
它到底怎麼運作？手算一次 fitness 課本的八皇后 fitness＝互不攻擊的皇后「對數」。8 個皇后兩兩配對共 8 × 7 ÷ 2 = 28 對，所以 28 分就是完美解。兩個皇后會互相攻擊的條件：在同一列（數字相同），或在同一條斜線（兩欄的距離＝兩列的距離）；同一欄不會發生，因為編碼時每欄只放一個。以 24748552 為例，互相攻擊的有 4 對： - 第 1 欄和第 8 欄：都在第 2 列（同一列） - 第 2 欄和第 4 欄：都在第 4 列（同一列） - 第 6 欄和第 7 欄：都在第 5 列（同一列） - 第 3 欄（第 7 列）和第 8 欄（第 2 列）：欄差 5、列差 5（同一斜線） 所以 fitness = 28 − 4 = 24。同樣算法，32752411 有 5 對攻擊 → 23，24415124 有 8 對 → 20，32543213 有 17 對 → 11，正好是投影片的 24、23、20、11。課本在爬山法用的 h（互相攻擊的對數，越小越好）跟它的關係就是 fitness = 28 − h。
老師原話是什麼？ 「這一串，就代表，那個 8 皇后的那個盤面」(0:53:07) 「一串基因串起來，變成一個染色體」(0:53:36) 「分數數字越大的就代表表現越好」(0:55:05)
## [0:55:39](https://www.youtube.com/watch?v=S1km7opW6rw&t=3339s) 選擇、交配、突變 GA 每一代做三件事。第一是 selection（選擇）：被挑去繁殖的機率跟 fitness 成正比，24、23、20、11 分（總和 78）對應 31%、29%、26%、14%，表現超好的可能被挑好幾次，最爛的可能一次都沒被挑到 (0:56:46)。第二是 crossover（交配）：每一對父母隨機選一個切點，爸爸的前段接媽媽的後段、媽媽的前段接爸爸的後段，生出兩個小孩，也就是兩個新的解 (0:57:06)。第三是 mutation（突變）：每個位置都有一個很小、各自獨立的機率被隨機改掉；在八皇后裡就是隨機挑一個皇后，把它移到同一欄的隨機一格 (0:58:16)。 **注意：老師把「分數越高越容易被挑」叫做「菁英原則」(0:56:31)。英文一般叫 fitness-proportionate selection（依適應度比例選擇，也叫 roulette-wheel selection 輪盤法），不要跟 elitism（菁英保留：最強的個體原封不動進下一代，下一段會講）搞混。** 「成正比」白話是：你的分數是別人的兩倍，被挑中的機會也是別人的兩倍。換算方法就是自己的分數 ÷ 全部分數加總，例如 24 ÷ 78 ≈ 31%。 [[IMG: C:\D槽\TAICA課程\_work\notes-v2\ai-w3\img\ai_w3_ch03_p013.png | Ch4 p.13 圖 4.6：(a) 初始族群 → (b) 算 fitness 與被選機率 → (c) 選出兩對父母 → (d) 交配 → (e) 突變（框起來的數字）]] 圖上重點：這張是投影片 Ch4 p.13，上方兩句是 GA 的定義（跟 Exam-ready 同兩句），下方課本圖 4.6 從左到右是一整代的流程。 - (a) Initial Population（初始族群）：隨機產生的 4 個盤面字串。 - (b) Fitness Function（適應度函數）：每個盤面的分數 24、23、20、11，和換算出的被選機率 31%、29%、26%、14%。 - (c) Selection（選擇）：依機率挑出兩對父母，中間的虛線是每一對的切點。 - (d) Crossover（交配）：前後段交換，灰底是從另一個父母拿來的部分；(e) Mutation（突變）：框起來的數字就是被隨機改掉的基因。 下面「手算一整代」在做什麼：用投影片的四個盤面真的跑一次選擇、交配、突變。結果新一代的平均分數從 19.5 升到 21.5，讓你看到「一代比一代好」是怎麼發生的；單一個小孩可能變差，但整群平均會變好。
它到底怎麼運作？手算一整代 選擇：把 0 到 1 切成四段，每段長度就是被選機率：[0, 0.308) 給 24748552、[0.308, 0.603) 給 32752411、[0.603, 0.859) 給 24415124、[0.859, 1) 給 32543213。擲 4 次亂數，假設是 0.40、0.10、0.55、0.70，就選到 32752411、24748552、32752411、24415124，正好是圖 (c)：23 分的被選了兩次，11 分的一次都沒有。 交配：第一對切在第 3 位後面，327|52411 和 247|48552 交換後段 → 32748552、24752411。第二對切在第 5 位後面，32752|411 和 24415|124 → 32752124、24415411。 突變： - 32748552 第 6 位 5 → 1，變 32748152（fitness 23 → 24，變好） - 24752411 沒有突變（22） - 32752124 第 3 位 7 → 2，變 32252124（21 → 18，變差） - 24415411 第 8 位 1 → 7，變 24415417（20 → 22，變好） 新一代平均 fitness 是 (24 + 22 + 18 + 22) ÷ 4 = 21.5，比上一代的 78 ÷ 4 = 19.5 高。單次突變不一定變好，但整群會慢慢往好的方向走。
為什麼交配會有用？ 交配能把兩個父母各自演化出來的「好區塊」拼在一起：爸爸前 3 欄排得好、媽媽後 5 欄排得好，切在第 3 欄就拿到兩邊的優點。一開始族群差異大，交配常一步跳很遠；後期大家越來越像，步伐就變小（課本補充）。所以「怎麼把解寫成字串」很重要，編碼不好，交配容易把好區塊切壞。
老師原話是什麼？ 「同一個 Chromosome 可能被挑很多次，如果它表現超優秀的話」(0:56:46) 「這個其實就是新的 Solution 的意思」(0:57:50) 「每一個 Individual，都有可能有一個很小的機率，可能某一個基因會變」(0:58:16)
## [1:00:39](https://www.youtube.com/watch?v=S1km7opW6rw&t=3639s) 繁衍多代與各種變形 生出新一代之後，重新算每個新解的 fitness，再挑父母、交配、突變，一代一代做下去 (0:59:48)。最後的答案有兩種取法：直接拿最後一代（例如第 100 代）最好的那個，或是把每一代的冠軍都留下來，最後讓歷代冠軍再 PK 一次 (1:00:20)。老師說 GA 所屬的 evolutionary computation（演化式計算）本身就是一門課，大方向就是這三頁投影片，細節變形很多：怎麼挑父母、讓超級優秀的個體「長生不老」一定進下一代（課本叫 elitism，菁英保留）(1:01:38)、染色體不一定是 0/1，也可以是實數 (1:02:12)。只要你想求的解能寫成染色體的形式，就可能用 GA 來解 (1:02:16)。 兩個名詞：實數就是可以有小數點的數字（例如 3.7）；虛擬碼（pseudocode）不是真的程式語言，而是用接近英文的句子寫出演算法步驟，給人看的，不能拿去執行。 下面「投影片的虛擬碼」在做什麼：把「選父母 → 交配 → 突變 → 換下一代，直到夠好或時間到」寫成步驟格式。看懂它，考試要你用文字描述 GA 流程時就寫得出來；不必看懂每個英文字，看摺疊裡最後那段白話就好。
它到底怎麼運作？投影片的虛擬碼 ``` function GENETIC-ALGORITHM(population, FITNESS-FN) returns an individual repeat new_population ← empty set for i = 1 to SIZE(population) do x ← RANDOM-SELECTION(population, FITNESS-FN) y ← RANDOM-SELECTION(population, FITNESS-FN) child ← REPRODUCE(x, y) if (small random probability) then child ← MUTATE(child) add child to new_population population ← new_population until some individual is fit enough, or enough time has elapsed return the best individual in population, according to FITNESS-FN function REPRODUCE(x, y) returns an individual n ← LENGTH(x); c ← random number from 1 to n return APPEND(SUBSTRING(x, 1, c), SUBSTRING(y, c + 1, n)) ``` 白話：外圈 repeat 的一圈就是「一代」。內圈要生出跟原族群一樣多的小孩：每次依 fitness 比例抽兩個父母 x、y（同一個可能被抽中兩次），REPRODUCE 在隨機位置 c 切開，拿 x 的前 c 位接 y 的後段，再以很小的機率突變。直到有個體夠好、或時間用完，就回傳族群裡 fitness 最高的那個。 **注意：這個虛擬碼每對父母只生一個小孩（圖 4.8 說這是比較常見的版本），圖 4.6 則是每對生兩個。**
怎麼把一個問題寫成染色體？ - 背包問題（10 樣東西，每樣帶或不帶）：10 位的 0/1 字串，例如 1011000010＝帶第 1、3、4、9 樣。 - 八皇后：8 個 1 到 8 的數字，每個數字是一欄皇后的位置（本章）。 - 連續問題：用實數當基因，例如下一章「在羅馬尼亞蓋 3 座機場」可以寫成 6 個實數 (x1, y1, x2, y2, x3, y3)。 - 老師的實驗室曾用 GA 做棒球影片分析；期末專題想用 GA，重點是怎麼把問題轉成染色體 (1:02:56)。
老師原話是什麼？ 「這就是基因演算法的最核心的概念」(1:00:46) 「你可以給它一個特權，就是長生不老」(1:01:38) 「重點在於說你如何把那個問題，轉化成 chromosome 的形式」(1:02:56)
## [1:03:18](https://www.youtube.com/watch?v=S1km7opW6rw&t=3798s) 課堂問答：會不會越走越爛？找不到最佳解怎麼辦？ 第一個問題是模擬退火接受了比較爛的解之後會不會一路爛下去：老師說溫度只會一路下降，溫度越低越不容易接受爛的解，所以最後越走越爛的機率非常非常低 (1:05:51)。第二個問題是找不到全域最大值怎麼辦：現實中通常根本不知道最大值在哪，找到的多半只是 local maxima，連最強的 GPT 也一樣；實務上就用 random restart 多跑幾次取最好的，解「夠好就好」，而且沒有公認最好的最佳化方法 (1:09:55)。下課時有同學追問能不能把歷史上最好的解記下來，老師說實務上的確可以 (1:10:55)。 **注意：模擬退火會收斂到好解的數學證明，本課略過不講 (1:06:10)。** 全域最大值（global maximum）是整張地圖上最高的那一點；local maxima 是 local maximum（局部最大值：附近最高、但不是全世界最高）的複數。 下面「手算一次」在做什麼：用三個不同溫度，算出模擬退火「願意接受一個變爛 2 分的解」的機率。公式裡的 e 是一個固定的數字（約 2.718），你不用會算，只要看結果：溫度越低，機率越接近 0，所以模擬退火到後期幾乎只往上走，不會一路爛下去。
模擬退火為什麼不太會一路爛下去？手算一次 複習：模擬退火遇到比較爛的鄰居，以機率 e^(ΔE/T) 接受。ΔE＝新解分數 − 舊解分數（變爛時是負的），T 是溫度。假設新解比舊解少 2 分（ΔE = −2）： - T = 10：e^(−0.2) ≈ 0.82，很容易接受 - T = 1：e^(−2) ≈ 0.14 - T = 0.1：e^(−20) ≈ 0.000000002，幾乎不可能 溫度只降不升，所以越到後面越不肯往下走，最後就跟爬山法一樣只往上爬。課本另外提到：只要溫度降得夠慢，找到全域最大值的機率會趨近 1（課本補充，本課沒證明）。實務上再多記一個「目前為止最好的解」，就不怕最後停在比較差的地方。
這章和上一章的方法怎麼比？
方法同時拿幾個解新的解怎麼來怎麼挑怎麼對付 local maximum
Hill climbing1目前解的鄰居最好的鄰居不能，會卡住
Random-restart hill climbing1（重跑很多次）同上同上換起點重跑，每次獨立
Simulated annealing1隨機一個鄰居變好必收，變差以 e^(ΔE/T) 收高溫時允許走下坡
Local beam searchkk 個解的所有鄰居一起比，留最好的 k 個k 條線互相傳資訊
Stochastic beam searchk同上依機率抽 k 個保留多樣性
Genetic algorithmk兩個父母交配＋突變依 fitness 比例挑父母交配跳得遠，突變帶來新變化
老師原話是什麼？ 「溫度一定不會越來越高，因為根據定義溫度一定是一開始最高溫，然後溫度會一路下降」(1:04:20) 「但是你可能永遠都無法保證，你找到的是數學上的最佳解」(1:08:42) 「很多時候在人類的真正的應用上，你找到的解，只要夠好就行了」(1:09:04)
## Self-check
Q1. Explain why local beam search is not the same as running k random restarts in parallel.（中文：為什麼 local beam search 不等於同時跑 k 次 random restart？） **Answer**: In a random-restart search, each search process runs independently. In local beam search, the successors of all k states are pooled and the k best are selected from the complete list, so useful information is passed among the parallel search threads: a promising region can take all k slots, and unpromising threads are dropped. 中文：Random restart 是 k 條搜尋線各自獨立地跑，彼此不知道對方進度如何。Local beam search 不一樣：每一步會把這 k 個解的所有鄰居全部倒進同一個池子裡，再從全部鄰居中挑出最好的 k 個，等於好的資訊會在這 k 條平行搜尋線之間互相流動——分數好的那個區域可以把 k 個名額全部搶走，表現不好的搜尋線就會被直接淘汰，不會像 random restart 那樣繼續獨立爬到底才換地方。
Q2. In a GA for 8-queens, four individuals have fitness 24, 23, 20 and 11. What is the fitness function, and what is each one's probability of being selected?（中文：GA 裡四個個體的適應度分別是 24、23、20、11，適應度函數是什麼？每個被選中的機率是多少？） **Answer**: Fitness = number of non-attacking pairs of queens (a solution scores 8 × 7 / 2 = 28). Selection probability is directly proportional to fitness: total 78, so 24/78 ≈ 31%, 23/78 ≈ 29%, 20/78 ≈ 26%, 11/78 ≈ 14%. An individual may be selected more than once. 中文：八皇后的 fitness function 是「互不攻擊的皇后有幾對」，8 個皇后兩兩配對最多 8 × 7 ÷ 2 = 28 對，所以滿分是 28。被選中去繁殖下一代的機率，直接跟自己的分數占全部分數的比例成正比：四個分數加起來是 24 + 23 + 20 + 11 = 78，所以被選機率分別是 24/78 ≈ 31%、23/78 ≈ 29%、20/78 ≈ 26%、11/78 ≈ 14%。分數最高的那個不是保證一定被選中，只是機率比較大，同一個個體也可能被連續抽中好幾次，分數最低的可能一次都抽不到。
Q3. Parents x = 32752411 and y = 24748552 are mated with crossover point c = 3. What child does REPRODUCE(x, y) return? What does mutation mean in 8-queens?（中文：父母 x=32752411、y=24748552 在切點 c=3 交配，REPRODUCE(x, y) 會產生什麼小孩？八皇后裡的突變是什麼意思？） **Answer**: APPEND(SUBSTRING(x, 1, 3), SUBSTRING(y, 4, 8)) = "327" + "48552" = 32748552. Mutation: each location changes at random with a small independent probability; in 8-queens, a random queen moves to a random square in its column (e.g., 32748552 → 32748152). 中文：REPRODUCE 的做法是取父親 x 字串的前 c 位、接上母親 y 字串從第 c+1 位到最後的部分。這裡 c=3，所以拿 x 的前 3 位「327」，接上 y 的第 4 位到第 8 位「48552」，拼起來就是小孩 32748552。突變則是交配完之後，字串裡每一個位置都有一個很小、彼此獨立的機率被隨機改掉；在八皇后問題裡，具體做法是隨機挑一個皇后，把它移到同一欄裡的隨機一列，例如把 32748552 的第 6 位從 5 改成 1，變成 32748152。
讀完了嗎？下一章：[04 連續空間的梯度上升（1:21–1:40）](https://app.notion.com/p/3e6fc631b030812a99d4eb793b437690)｜回到週頁：[W3（9/24）](https://app.notion.com/p/3e6fc631b0308137bbd8e73f5c6f1b62)