【正文】 人工智能原理 第 2章 搜索技術(shù) （下） 1 本章內(nèi)容 搜索與問題求解 無信息搜索策略 啟發(fā)式搜索策略 局部搜索算法 約束滿足問題 博弈搜索 參考書目 附錄 A*算法可采納性的證明 第 2章 搜索技術(shù) 2 局部搜索算法 局部搜索與最優(yōu)化 爬山法搜索 模擬退火搜索 局部剪枝搜索 遺傳算法 第 2章 搜索技術(shù) 3 局部搜索算法 ? 前面的搜索算法都是保留搜索路徑的，到達(dá)目標(biāo)的路徑就是問題的解 — 然而許多問題中到達(dá)目標(biāo)的路徑是無關(guān)緊要的 ? 與系統(tǒng)地搜索狀態(tài)空間 (保留各種路徑 )相對，不關(guān)心路徑的搜索算法就是局部搜索算法 ? 局部搜索從一個單獨(dú)的當(dāng)前狀態(tài)出發(fā)，通常只移動到相鄰狀態(tài) ? 典型情況下搜索的路徑不保留 第 2章 搜索技術(shù) 4 局部搜索算法的應(yīng)用 ? 集成電路設(shè)計(jì) ? 工廠場地布局 ? 車間作業(yè)調(diào)度 ? 自動程序設(shè)計(jì) ? 電信網(wǎng)絡(luò)優(yōu)化 ? 車輛尋徑 ? 文件夾管理 第 2章 搜索技術(shù) 5 局部搜索與最優(yōu)化問題 ? 局部搜索算法的優(yōu)點(diǎn)： ? 只使用很少的內(nèi)存 (通常是一個常數(shù) ) ? 經(jīng)常能在不適合系統(tǒng)化算法的很大或無限的狀態(tài)空間中找到合理的解 ? 最優(yōu)化問題 — 根據(jù)一個目標(biāo)函數(shù)找到最佳狀態(tài) / 只有目標(biāo)函數(shù)，而不考慮 (沒有 )“目標(biāo)測試 ” 和“路徑耗散” ? 局部搜索算法適用于最優(yōu)化問題 第 2章 搜索技術(shù) 6 狀態(tài)空間地形圖 (1) 第 2章 搜索技術(shù) 山肩 目標(biāo)函數(shù) 全 局 最 大值 局 部 最 大值 “ 平坦 ” 局部最大值 狀態(tài)空間 當(dāng)前狀態(tài) 7 狀態(tài)空間地形圖 (2) ? 在狀態(tài)圖中，既有“位置” (用狀態(tài)表示 )又有“高度 ”( 用耗散值或目標(biāo)函數(shù)值表示 ) ? 如果高度對應(yīng)于耗散值，則目標(biāo)是找到全局最小值，即圖中最低點(diǎn) ? 如果高度對應(yīng)于目標(biāo)函數(shù)，則目標(biāo)是找到全局最大值，即圖中最高峰 ? 如果存在解，則完備的局部搜索算法能夠找到解 ? 而最優(yōu)的局部搜索算法能夠找到全局最大或最小值 第 2章 搜索技術(shù) 8 局部搜索算法 ? 本節(jié)簡要介紹以下 4種局部搜索算法 / 介紹其算法思想 ? 爬山法搜索 ? 模擬退火搜索 ? 局部剪枝搜索 ? 遺傳算法 ?從搜索的角度看遺傳算法也是搜索假設(shè)空間的一種方法 (學(xué)習(xí)問題歸結(jié)為搜索問題 )— 生成后繼假設(shè)的方式 第 2章 搜索技術(shù) 9 爬山法搜索 ? 爬山法 (hillclimbing)—就是向值增加的方向持續(xù)移動 —登高過程 / 如果相鄰狀態(tài)中沒有比它更高的值，則算法結(jié)束于頂峰 ? 爬山法搜索算法思想： (1)令初始狀態(tài) S0為當(dāng)前狀態(tài) (2)若當(dāng)前狀態(tài)已經(jīng)達(dá)標(biāo)，則算法運(yùn)行結(jié)束，搜索成功 (3)若存在一個動作可以作用于當(dāng)前狀態(tài)以產(chǎn)生一個新狀態(tài)，使新狀態(tài)的估計(jì)值優(yōu)于當(dāng)前狀態(tài)的估計(jì)值，則放棄當(dāng)前狀態(tài)，并令剛產(chǎn)生的新狀態(tài)為當(dāng)前狀態(tài)，轉(zhuǎn) (2) (4)取當(dāng)前狀態(tài)為相對最優(yōu)解，停止執(zhí)行算法 第 2章 搜索技術(shù) 10 爬山法搜索的局限 ? 爬山法是一種局部貪婪搜索，不是最優(yōu)解算法 (或是不完備的 ) / 其問題是： ? 局部極大值 —比其鄰居狀態(tài)都高的頂峰，但是小于全局最大值 (參照狀態(tài)空間地形圖 ) ? 山脊 —一系列的局部極大值 ? 高原 —評價(jià)函數(shù)平坦的一塊區(qū)域 (或者山肩 ) 第 2章 搜索技術(shù) 11 爬山法搜索的變形 ? 爬山法的變形 ? 隨機(jī)爬山法 —隨機(jī)選擇下一步 ? 首選爬山法 —隨機(jī)選擇直到有優(yōu)于當(dāng)前節(jié)點(diǎn)的下一步 ? 隨機(jī)重新開始爬山法 —隨機(jī)生成初始狀態(tài)，進(jìn)行一系列爬山法搜索 —這時算法是完備的概率接近 1 第 2章 搜索技術(shù) 12 模擬退火搜索 ? 將爬山法 (停留在局部山峰 )和隨機(jī)行走以某種方式結(jié)合，以同時獲得完備性和效率 ? 模擬退火的思想 ? 想象在不平的表面上如何使一個乒乓球掉到最深的裂縫中 — 如果只讓其在表面滾動，則它只會停留在局部極小點(diǎn) / 如果晃動平面，可以使乒乓球彈出局部極小點(diǎn) / 技巧是晃動足夠大使乒乓球彈出局部極小點(diǎn)，但又不能太大把它從全局極小點(diǎn)中趕出 第 2章 搜索技術(shù) 13 模擬退火的解決思路 (1) ? 思路 — 開始使勁晃動 (先高溫加熱 )然后慢慢降低搖晃的強(qiáng)度 (逐漸降溫 )[退火過程 ] ? 算法的核心 — 移動選擇 ? 選擇隨機(jī)移動，如果評價(jià)值改善，則移動被接受，否則以某個小于 1的概率接受 ? 概率按照移動評價(jià)值變壞的梯度 ΔE 而呈指數(shù)級下降 / 同時也會隨著作為控制的參數(shù) — “溫度 ”T 的降低 (數(shù)值減小 )而降低 ? 接受概率 =eΔE /T(注意此時 ΔE 0) 第 5章 搜索技術(shù) 14 模擬退火的解決思路 (2) ? 溫度 T是時間的函數(shù)，按照模擬退火的思想，數(shù)值應(yīng)該逐漸減小 (降溫 ) ? 因?yàn)?接受概率 =eΔE /T且 ΔE 0，所以當(dāng)溫度高時，接受概率較大 (接近 1) / 而 T越來越低時， ΔE /T變大，因而接受概率降低 ? 可以證明，如果 T下降得足夠慢，則算法找到全局最優(yōu)解的概率接近 1 第 5章 搜索技術(shù) 15 局部剪枝搜索 ? 基本思想 — 與 只從一個單獨(dú)的起始狀態(tài)出發(fā)不同，局部剪枝搜索從 k個隨機(jī)生成的狀態(tài)開始，每步生成全部 k個狀態(tài)的所有后繼狀態(tài) / 如果其中之一是目標(biāo)狀態(tài)，算法停止；否則從全部后繼狀態(tài)中選擇最佳的 k個狀態(tài)繼續(xù)搜索 ? 在局部剪枝搜索過程中，有用的信息在 k個并行的搜索線程之間傳遞 — 算法會很快放棄沒有成果的搜索而把資源放在取得最大進(jìn)展的搜索上 第 2章 搜索技術(shù) 16 隨機(jī)剪枝搜索 ? 如果 k個狀態(tài)缺乏多樣性，則局部剪枝搜索會受其影響，性能變差 ? 算法的變種 — 隨機(jī)剪枝搜索幫助緩解這一問題 — 隨機(jī)剪枝搜索不是選擇最好的 k個后代，而是按照一定概率隨機(jī)地選擇 k個后繼狀態(tài) / 選擇給定后繼狀態(tài)的概率是狀態(tài)值的遞增函數(shù) ? 類似于自然選擇過程 — 狀態(tài)對應(yīng)生物體，其值對應(yīng)于適應(yīng)性，后代就是后繼狀態(tài) 第 2章 搜索技術(shù) 17 遺傳算法 ? 遺傳算法 (generic algorithm/GA)是隨機(jī)剪枝的變種 —不是通過修改單一狀態(tài)而是通過把兩個父狀態(tài)結(jié)合以生成后繼狀態(tài) ? 與剪枝搜索一樣，遺傳算法也是從 k個隨機(jī)狀態(tài)開始 — 這 k個狀態(tài)稱為種群，每個狀態(tài)稱為個體 ? 個體用有限長的字符串 (通常為 0/1串 )表示 ? 每個狀態(tài)用其評價(jià)函數(shù) (適應(yīng)度函數(shù) )給出評價(jià)值 (適應(yīng)值 ) ? 隨后的操作包括 — 選擇 /雜交 /變異 第 2章 搜索技術(shù) 18 遺傳算法的操作 ? 選擇 (或者稱繁殖 )—按照一定概率隨機(jī)地選擇兩對個體進(jìn)行繁殖 (即生成后繼狀態(tài) ) ? 雜交 (或者稱交叉 )—雜交點(diǎn)是在表示狀態(tài)的字符串中隨機(jī)選擇的一個位置，以此形成新狀態(tài) —后代是父串在雜交點(diǎn)上進(jìn)行雜交 (各取一部分 )得來的 ? 變異 —在新生成的串中各個位置都會按照一個獨(dú)立的 小概率隨機(jī)變異 第 2章 搜索技術(shù) 19 遺傳算法簡要描述 (1)定義問題和目標(biāo)函數(shù) (2)選擇候選解作為初始種群，每個解作為個體用二進(jìn)制串表示 (個體相當(dāng)于染色體，其中的元素相當(dāng)于基因 ) (3)根據(jù)目標(biāo)函數(shù)，對于每個個體計(jì)算適應(yīng)函數(shù)值 (4)為每個個體指定一個與其適應(yīng)值成正比的被選擇概率 (繁殖概率 ) (5)根據(jù)概率選擇個體，所選個體通過交叉 /變異等操作產(chǎn)生新一代種群 (6)如果找到了解或者某種限制已到，則過程結(jié)束；否則轉(zhuǎn) (3) 第 2章 搜索技術(shù) 20