逐步修改候選解
假設一份時間表已滿足所有限制,但仍可改善其評分。局部搜尋每次修改一個候選解,不必建立從起點到目標的完整路徑。方法是否有效取決於容許的操作:交換兩個安排可能帶來改善,單獨修改一個安排卻未必能做到。評分、表示方式和鄰域都是算法的一部分。
定義 19.1.1
(鄰域與局部極大值)
令 是非空有限可行狀態集合, 是要最大化的評分, 是從 容許到達的鄰居。鄰域不必對稱。若對每個 都有 ,稱 為嚴格局部極大值點;若只有 ,則稱為弱局部極大值點。若 為空,兩個條件都自然成立。全域極大值則要與整個 比較。弱局部極大值點未必是全域極大值點;存在相同評分時,全域極大值點也未必是嚴格局部極大值點。
定義 19.1.2
(攀山法的變體)
嚴格改善的攀山法反覆把 換成任意滿足 的鄰居 ,找不到便停止。最陡上升法選擇評分最高的鄰居,若並列則按指定規則處理。首次改善法則按指定順序檢查鄰居,選第一個改善者。選法不同可能到達不同終點。此處因 ,每次移動仍可行;實作時必須確保產生鄰居的程式確實滿足此條件。
定理 19.1.3
(終止性及停機的含義)
在有限 上,不論如何選擇改善鄰居,每次嚴格改善的執行都會在最多 次移動後停止。終點是所指定鄰域下的弱局部極大值點,但未必是 上的全域極大值點。
證明與界限
證明
(沒有狀態會被重訪)
每一步評分均嚴格上升,故不可能重訪某狀態:若重訪,其評分應與之前相同,卻與中間每步嚴格上升矛盾。執行最多經過 個不同狀態,故最多移動 次。停止時沒有評分更高的鄰居,正是弱局部極大值的條件。這個證明既不保證 指數龐大時運算快速,也不提供全域最優證明;評估鄰居本身亦可能昂貴。
證明透視
有限性和嚴格性的作用
有限性限制不同狀態的數目;嚴格改善防止重訪。缺少任何一項都不能沿用此論證。例如非負整數 只有鄰居 ,而 ,則嚴格改善永不停止。
完整計算吸引域
例題 19.1.4
(五狀態鏈上的最陡上升)
考慮無向鏈 ––––,各狀態評分依次為 。從 或 出發,最陡上升停在 。從 出發,鄰居 得 分,高於 的 分,所以路徑經 走到 。完整路徑為 、、、、。 是評分為 的嚴格局部極大值點, 才是唯一的全域極大值點,得 分。此確定性算法中,兩個吸引域分別為 和 。在其他圖上,不同移動規則可能產生不同吸引域;吸引域屬於一個算法,而不單由評分函數決定。
反例模式
局部最優是關於鄰域的陳述
的相鄰狀態都沒有較高評分,雖然 評分更高。若新增容許邊 –,最陡上升就可立即離開 。即使每個候選解的評分不變,改變容許移動也會改變搜尋問題。
同分和平移
即使沿同分狀態前進後可以改善,嚴格改善法仍會在平臺停止。平移是移到評分相同的鄰居,我們只在沒有鄰居能改善評分時才容許。
命題 19.1.5
(平移上限恢復終止性)
設 有限,一次執行在有改善時作嚴格改善,否則作平移,連續平移最多 次,每次嚴格改善後重新計數。則該執行最多有 次嚴格改善及 次平移,所以最多在 次移動後停止。
證明
(計算嚴格移動與平移)
嚴格移動令評分嚴格上升,平移則評分不變,所以評分沿執行不會下降。嚴格移動之後不可能重訪某狀態,否則評分得回落。因此嚴格移動依序經過評分遞增的不同狀態,最多 次。第一次嚴格移動之前、相鄰兩次嚴格移動之間,以及最終停止之前,共至多有 段平移,每段長度至多 ,所以平移至多 次,相加即得總數。
例題 19.1.6
(藏有出口的平臺與沒有出口的平臺)
鏈 –– 的評分是 。由 出發,嚴格規則會立即停止,因為 與 同分,沒有鄰居能改善。取 ,容許從 平移到 ,然後 有嚴格更佳的鄰居 ,於是經一次平移和一次嚴格移動到達 。
再看只有兩個同分狀態的鏈 –。沒有限制的平移規則可以無限交替 。取 ,則從 移到 後已用完唯一容許的連續平移,便在 停止。達到上限時的終點仍可能有未試過的同分出口;它不代表整個平臺已被探索。
另一方法是系統地搜尋可到達的同分區域,尋找改善出口,但這需要儲存已訪問的狀態,記憶體可能遠多於只保留當前候選解。若鄰域有方向,就要使用有向可達性:可從 到 的同分邊未必可反向走。
獨立重啟及其成本
固定一個單次執行方法,包括停止規則、成功判準及其中可能的隨機選擇。若返回全域極大值點便稱成功;對指定的起點分布及執行內的所有隨機選擇,令成功概率為 。
定理 19.1.7
(獨立重啟下的成功概率)
若各次執行獨立且同分布, 次內至少成功一次的概率是
當 , 趨大時此概率趨近一,而直到首次成功(包括成功的一次)所需執行次數 的期望為 。若 ,重啟永不成功;若 ,有限的 不能保證成功。
證明
(補事件與等比級數)
由獨立性, 次均失敗的概率為 ,而「全部失敗」的補事件就是「至少成功一次」。單單把方法稱為「隨機重啟」並不足以推出公式:若重用有依賴的隨機選擇,或改變起點分布,公式可能失效。
至於期望,對 有 ,因為前 次都必須失敗。把這些尾概率相加,等比級數給出 。這計算的是執行次數而非鄰居評估次數;各次執行成本可以不同。
例題 19.1.8
(五狀態鏈上的重啟)
在上述五狀態例子中,均勻隨機選起點,並用確定性最陡上升,執行恰在起點屬於 時成功,所以 。三次獨立起點至少成功一次的概率為 ,直到首次成功的期望執行次數為 。極端情況也與定理一致:若起點永遠是 ,則 ,重啟多少次都沒有用;若起點永遠是 ,則 ,一次執行便足夠。
概念視角結構
優化評分與達成目標
局部極大值只證明沒有容許的改善步驟,不能證明沒有更好的狀態。重啟概率量化固定分布下的重複執行,不能證明某個特定輸出是全域最優。兩者均取決於移動和成功的精確定義。
常見錯誤
常見錯誤
(以為先前的失敗會提高下一次的成功概率)
在五狀態例子中,前兩次獨立失敗後,第三次成功概率仍是 ;過往失敗不會提高這概率。至少成功一次的概率隨 上升,只是因為給了更多獨立機會,並不是前面的執行「欠」一次成功。
常見錯誤
(靠檢查終點是否全域最優來量度 )
真實問題的全域最優值可能未知,因此一般無法靠檢查終點是否全域最優來量度 。已知目標分數可以定義另一個可觀察的成功事件,但其概率須重新定義。
練習
練習 19.1.9
(鏈 ––– 的評分依次為 。列出由各狀態出發的嚴格最陡上升終點,並分辨弱與嚴格局部極大值點。)
核心
解答(3)
- 1
追蹤各狀態的嚴格最陡上升
由 出發,唯一鄰居 得 ,所以移到 。在 ,鄰居評分為 和 ,都不嚴格大於 ,所以停止。由 出發,鄰居 得 ,所以移到 並停止。終點為 、、、。
- 2
分類局部極大值點
關鍵一步
的鄰居評分為 和 ,所以 與 均成立:它是弱局部極大值點,但因 與它同分,不是嚴格的。 有鄰居 得 ,所以不是局部極大值點。 勝過唯一的鄰居,是嚴格局部極大值點。
依據: 弱局部極大值要求對每個鄰居都有 ,嚴格者要求 。
- 3
寫出結論
弱局部極大值點為 和 ;嚴格局部極大值點只有 。儘管平臺 有出口,從 無法只靠嚴格改善到達更好的 。
練習 19.1.10
(同一鏈上,規定沒有改善鄰居時可平移一次,然後恢復嚴格上升;最多容許連續一次平移。由 出發寫出一條可行路徑,並解釋 的同分處理為何重要。)
核心
解答(2)
- 1
追蹤這次執行
是嚴格移動。在 沒有鄰居能改善,所以適用平移規則,並取唯一的同分鄰居 。由 出發,鄰居 能改善,所以 是嚴格移動。路徑為 。
- 2
解釋同分處理
此鏈中 只有一個同分鄰居 ,但規則仍須說明是選它還是停止。較大的平臺中,選擇哪個同分鄰居可以影響結果。平移上限避免無限連續平移,卻不保證找出所有出口。
依據: 規則必須說明是否作平移,以及選哪個同分鄰居。
練習 19.1.11
(單次執行成功概率是 。求四次獨立執行至少一次成功的概率,以及截至首次成功(包括成功的那一次)所需執行次數的期望。若所有起點都重用同一次隨機抽樣,還能套用相同公式嗎?)
核心
解答(2)
- 1
套用重啟公式
至少成功一次的概率為 。首次成功的平均等待次數為 。
- 2
檢視重用同一次隨機抽樣
若重用同一隨機起點,結果可完全相依。例如確定性方法恰好在同一組四分之一的起點成功,則四次同時成功或同時失敗,至少一次成功的概率仍為 ,公式並不適用。
依據: 公式需要各次執行相互獨立。
練習 19.1.12
(有限有向圖有評分 、、,及邊 、、。求由 開始的嚴格上升終點,並說明為何不違反終止定理。)
基礎
解答(2)
- 1
追蹤由 開始的執行
由 出發,唯一的出鄰居是 ,且 ,所以移到 。 唯一的出鄰居 評分為 ,沒有改善移動,於是在 停止。
- 2
與定理比較
評分更高的 不是 的出鄰居,因此無法到達。有限性及嚴格上升仍保證終止,而且 是此有向鄰域下的弱局部極大值點。定理從未保證全域最優或邊的對稱性。