使用局部搜索算法可以解決大規?；屎髥栴}，但是局部搜索算法存在缺點，大多數時候只能得到局部最優，同時還要注意步長和起始點這兩個重要因素。

局部搜索應用：百萬皇后問題

皇后問題

皇后問題：

在一個 \(n\times n\) 的棋盤上，每行每列有且只有一個皇后棋子，每對角線至多一個皇后棋子。

如果使用回溯法，計算10皇后、20皇后問題還是可行的。

但是當皇后數增加到一百萬個時，又該如何求解呢？

局部搜索算法用于求解組合優化問題，而皇后問題是組合問題，和優化沒有關系，我們可以先將皇后問題轉化為最優化問題。

• 指標函數：棋盤上皇后的沖突數。

• 表示：

  \(S=\{S_i\}\)表示一個可能解，其中 \(S_i\) 表示在第 \(i\) 行，第 \(S_i\) 列有一個皇后。

  如四皇后問題的一個解：\(S=(2,4,1,3)\)

  

皇后搜索算法

1. 隨機地將 \(n\) 個皇后分布在棋盤上，使得棋盤的每行、每列只有一個皇后；
2. 計算皇后間的沖突數 \(c\) ；
3. 如果沖突數 \(c\) 等于0，則轉 (7)
4. 任選兩個皇后交換他們在序列中的位置；
5. 如果交換后的沖突數 \(c\) 減少，則接受這次交換，更新沖突數 \(c\) ，轉(3)；
6. 如果陷入了局部極小，即交換了所有的皇后后，沖突數仍然不能下降，則轉1；
7. 輸出結果；
8. 結束。

可以使用局部搜索算法解決大規?；屎髥栴}（并找到全局最優解）的關鍵在于：我們知道沖突數這個指標有最小值，并且最小值為0，從而我們可以判斷某一時刻是否陷入了局部極小，或者是否已到達最優解。

而對于另一個著名的組合問題，旅行商問題來說，我們也可以用局部搜索算法來求解，但是我們不知道指標（路徑長度）的最小值是多少，因此我們只能求得局部最優解，無法判斷求得的局部最優解是否全局最優。

大多數組合問題都和旅行商問題一樣，使用局部搜索算法往往是無法判斷全局最優的。

局部搜索算法存在的問題

局部最優問題

最明顯的問題是可能會得到局部最優解，如上圖的 \(B\) 和 \(C\)，而得不到 \(A\)。而這些最終結果與初始點有關，因此需要多次隨機地設置初始點，然后在得到的多個解中，找出相對較優的解。

解決思路

• 按概率接受解（在領域中尋找解的時候，并不是只接受最優解，而是為每個解計算概率，然后隨機走下一步）

• 從鄰域中隨機選擇一個解，如果該解的指標函數好于當前已知的最好解，則以大概率接受該解，否則就以小概率接受該解。

求最大值時

概率的計算方法根據不同算法有不同實現，這里只是一個簡單的例子。

即 指標 除以 鄰域內所有指標之和。

同理，求最小值時：

如何按概率接受一個解？

• 設 \(x_i\) 的接受概率為 \(P(x_i)\)，當 \(random(0,1)<P(x_i)\) 時接受 \(x_i\)

步長問題

如果步長大，而“山峰”尖，則可能最終像上圖中一樣，結果落在了半山腰。

解決思路

改變步長

• 如果步長太小，會導致計算效率降低。
• 如果步長太大，可能導致錯過最優解。

一種解決方法是，隨著迭代次數的增加，逐漸減小步長。

不同的算法有不同的改變步長的做法。

大多數情況下還是需要多次調整初始步長，然后執行程序，多次調整。

起始點問題

起始點不同，最終的結果可能不同?？赡艿玫饺肿畲笾担部赡艿玫骄植孔畲笾?。

解決思路

隨機產生多個起始點，從多次運行結果中選擇一個最好的結果。

綜合求解

面對局部搜索算法存在的問題，應綜合求解。

• 按概率接受解；
• 改變步長；
• 多次運行方法。

有一種特殊的局部搜索算法叫模擬退火算法，就是基于“按概率接受解”和“改變步長”這兩點的。