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