人工智能 一種現代方法 第4章 超越經典搜索

2018.3.23

4.1局部搜索算法和最優化問題

很多現實生活中的最優化問題目標與路徑是不相關的，諸如布局問題、八皇后問題。

局部搜索算法對于解決純粹的最優化問題十分有效，根據目標函數找到全局最優狀態。

即代價的全局最小值，目標函數的全局最大值。

4.1.1爬山法

定義：不斷向值增大的方向移動，直到到達局部最優

也被稱為貪婪局部搜索，貪婪算法很容易改善一個壞的狀態，但卻經常陷入局部最優無法跳出。

局部極大值：比每個相鄰的節點都高，但比全局最大要小。

山脊：一系列局部極大值

高原：一塊平坦的局部極大值

• 優化算法

側向移動：允許連續側向移動

隨機爬山法：隨機的選擇下一步，被選中概率與斜率有關

首選爬山法：用隨機爬山法直到生成了一個優于當前節點的后繼

隨機重啟爬山法：隨機生成初始狀態來引導爬山法，直到找到目標。

4.1.2模擬退火搜索

結合了爬山法與隨機行走，開始是使勁晃動，慢慢降低搖晃的強度。

在開始時隨機移動，如果該移動使情況改善，該移動被接受；否則以后一個小于1的概率接受該移動，這個概率呈指數級下降。

4.1.3局部束搜索

記錄k個狀態，從k個隨機生成的狀態開始，k個狀態的全部后繼均被生成，如果其中一個是目標狀態則停止，否則從全部后繼中選取k個最佳的后繼重復這個過程。

4.1.4遺傳算法

種群按照適應度函數進行配對，通過雜交產生后代，通過基因突變進行變異。

總結

以上是生活随笔為你收集整理的人工智能 一种现代方法 第4章 超越经典搜索的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。