湖南大學(xué)人工智能課件4

第四章超越經(jīng)典的搜索第四章超越經(jīng)典的搜索2015年1月湖南大學(xué)信息科學(xué)與工程學(xué)院內(nèi)容提要局部搜索算法不確定動作的搜索使用部分可觀察信息的搜索聯(lián)機(jī)搜索內(nèi)容提要局部搜索算法2局部搜索算法在許多最優(yōu)化問題中，我們不是要尋找到達(dá)目標(biāo)狀態(tài)的路徑，而是找到目標(biāo)狀態(tài)本身。N皇后問題：局部搜索算法在許多最優(yōu)化問題中，我們不是要尋找到達(dá)目標(biāo)狀態(tài)的3局部搜索算法局部搜索算法：從單個當(dāng)前結(jié)點(diǎn)出發(fā)，通常只移動到它的鄰近狀態(tài)而不保留搜索路徑優(yōu)點(diǎn)：很少的內(nèi)存能在很大的或者無限的狀態(tài)空間中找到合理的解局部搜索算法局部搜索算法：從單個當(dāng)前結(jié)點(diǎn)出發(fā)，通常只移動到它4爬山法爬山法5爬山法缺點(diǎn)?依據(jù)初始狀態(tài)，得到局部最大值爬山法缺點(diǎn)?6爬山法h=直接或者間接相互攻擊的皇后對數(shù)h=17(左圖)h=1(右圖)局部極小值爬山法h=直接或者間接相互攻擊的皇后對數(shù)局部極小值7模擬退火搜索爬山法不完備，隨機(jī)法效率低，考慮結(jié)合兩者產(chǎn)生了模擬退火搜索基本思想：允許算法向壞的方向移動以擺脫局部最大值，但這種移動隨著時間的推移概率逐步下降模擬退火搜索爬山法不完備，隨機(jī)法效率低，考慮結(jié)合兩者產(chǎn)生了模8模擬退火搜索如果時間下降得足夠的慢，那么模擬退火算法找到一個全局最優(yōu)值的概率接近于1模擬退火搜索如果時間下降得足夠的慢，那么模擬退火算法找到一個9局部束搜索隨機(jī)產(chǎn)生k個狀態(tài)，然后每一步從所有的后繼狀態(tài)中選擇k個最佳的后繼狀態(tài)直到找到目標(biāo)狀態(tài)。(內(nèi)存中保留K個狀態(tài))隨機(jī)束搜索：不是找到k個最佳，而是隨機(jī)找到k個后繼狀態(tài)，隨機(jī)概率與狀態(tài)值成正比。局部束搜索隨機(jī)產(chǎn)生k個狀態(tài)，然后每一步從所有的后繼狀態(tài)中選擇10遺傳算法一個后繼狀態(tài)由兩個父狀態(tài)決定以k個隨機(jī)產(chǎn)生的狀態(tài)開始(population)一個狀態(tài)表示成一個字符串定義一個健康度量函數(shù)用來評價狀態(tài)的好壞程度通過選擇，交叉，突變的操作產(chǎn)生下一輪狀態(tài)遺傳算法一個后繼狀態(tài)由兩個父狀態(tài)決定11遺傳算法健康度量函數(shù):非沖突的皇后數(shù)量(min=0,max=8×7/2=28)24/(24+23+20+11)=31%,23/(24+23+20+11)=29%遺傳算法健康度量函數(shù):非沖突的皇后數(shù)量(min=0,12遺傳算法樣本被選擇繁衍后代的概率正比于它的健康度函數(shù)值發(fā)生交叉操作的概率需要預(yù)先設(shè)定，交叉位置隨機(jī)產(chǎn)生發(fā)生突變操作的概率需要預(yù)先設(shè)定，通常遠(yuǎn)小于交叉概率遺傳算法樣本被選擇繁衍后代的概率正比于它的健康度函數(shù)值發(fā)生交13使用不確定性動作的搜索環(huán)境是完全可觀察的和確定的可以知道任何動作序列之后達(dá)到的狀態(tài)環(huán)境是部分可觀察或者是不確定的無法準(zhǔn)確預(yù)知未來狀態(tài)需根據(jù)未來感知信息制定相應(yīng)的行為

使用不確定性動作的搜索環(huán)境是完全可觀察的和確定的14使用不確定性動作的搜索例子：真空洗塵器世界的不穩(wěn)定行為在一塊臟區(qū)域洗塵可以使該區(qū)域干凈，有時也會清潔鄰近區(qū)域在干凈區(qū)域洗塵可能是該區(qū)域弄臟Suckwhenstate=1Ifstate=5then[right,suck]Elsedononthing使用不確定性動作的搜索例子：真空洗塵器世界的不穩(wěn)定行為15與或搜索樹或結(jié)點(diǎn)必須選擇行動在用圓圈表示的與結(jié)點(diǎn)上必須處理所有后繼解用粗黑線標(biāo)出Q:LOOP什么意思？與或搜索樹或結(jié)點(diǎn)必須選擇行動Q:LOOP什么意思？16無觀察信息的搜索Agent感知不到任何信息，稱為無傳感問題，也稱相容問題無傳感問題是可解的還是無解的？可解！真空吸塵器世界無傳感問題的可解性：初始狀態(tài)：｛1，2，3，4，5，6，7，8｝“向右”操作后:{2,4,6,8}“洗塵”操作后{4,8}“向左”操作后{1,7}“洗塵”操作后目標(biāo)狀態(tài){7}在信念狀態(tài)解無觀察信息的問題無觀察信息的搜索Agent感知不到任何信息，稱為無傳感問題17無觀察信息的搜索無觀察信息問題P的定義信念狀態(tài)：包含物理狀態(tài)中每個可能的集合，假定N個物理狀態(tài)，最多有2N個信念狀態(tài)初始狀態(tài)：所有物理狀態(tài)的集合行動：轉(zhuǎn)移模型：對于確定行動對于不確定行動目標(biāo)測試：信念狀態(tài)中的所有物理狀態(tài)都滿足目標(biāo)狀態(tài)路徑開銷：假定所有狀態(tài)下一個行動的開銷相同無觀察信息的搜索無觀察信息問題P的定義18無觀察信息的搜索256個可能的信念狀態(tài)只有12個可達(dá)；初始狀態(tài)出發(fā)的行動序列{S,L,S}與{R,L,S}達(dá)到相同的信念狀態(tài){5,7}如果一個行動序列是信念狀態(tài)b的解，那么它也是b的任何子集的解無觀察信息的搜索256個可能的信念狀態(tài)只有12個可達(dá)；19部分可觀察信息的搜索真空吸塵器世界問題的局部感知：位置傳感器和局部垃圾傳感器例如：狀態(tài)1的可觀察信息percept(s)=[A,dirty]一個信念狀態(tài)到另一個信念狀態(tài)的特定行動分三階段發(fā)生：預(yù)測階段:給定信念狀態(tài)b和行動a，預(yù)測信念狀態(tài)觀察預(yù)測階段:確定預(yù)測信念狀態(tài)中可觀察到的感知信息o:

更新階段：根據(jù)每個可能的感知信息得到信念狀態(tài)

部分可觀察信息的搜索真空吸塵器世界問題的局部感知：20部分可觀察信息的搜索部分可觀察信息的搜索21部分可觀察信息的搜索[Suck,Right,ifBstate={6}thenSuckelse[]]部分可觀察信息的搜索[Suck,Right,ifBstat22部分可觀察信息的搜索部分可觀察信息的搜索23部分可觀察信息的搜索部分可觀察環(huán)境中的問題求解Agent形式化，搜索算法，執(zhí)行解行動解是一個條件規(guī)劃不是一個序列if-then-elseAgent在完成行動和接收感知信息時維護(hù)自身的信念狀態(tài)部分可觀察信息的搜索部分可觀察環(huán)境中的問題求解Agent24部分可觀察信息的搜索UPDATE(PREDICT(UPDATE(b,NSW),Move),NS)部分可觀察信息的搜索UPDATE(PREDICT(UPDAT25聯(lián)機(jī)搜索Agent脫機(jī)搜索算法：在行動之間計算好完整的解決方案聯(lián)機(jī)搜索算法：行動，觀察環(huán)境，下一步行動聯(lián)機(jī)搜索Agent脫機(jī)搜索算法：在行動之間計算好完整的解決方26聯(lián)機(jī)搜索Agent：競爭比競爭比=實(shí)際代價/最小代價30/20=1.5競爭比越小越好競爭比可以是無窮大，比如達(dá)到某些狀態(tài)后無法達(dá)到目標(biāo)狀態(tài)(活動不可逆)可安全探索的狀態(tài)空間：每個可達(dá)到的狀態(tài)出發(fā)都有達(dá)到目標(biāo)狀態(tài)的行動，如迷宮問題，八數(shù)碼問題聯(lián)機(jī)搜索Agent：競爭比競爭比=實(shí)際代價/最小代價27總結(jié)局部搜索算法不確定動作的搜索使用部分可觀察信息的搜索聯(lián)機(jī)搜索總結(jié)局部搜索算法28Qa？

Qa？

第四章超越經(jīng)典的搜索第四章超越經(jīng)典的搜索2015年1月湖南大學(xué)信息科學(xué)與工程學(xué)院內(nèi)容提要局部搜索算法不確定動作的搜索使用部分可觀察信息的搜索聯(lián)機(jī)搜索內(nèi)容提要局部搜索算法31局部搜索算法在許多最優(yōu)化問題中，我們不是要尋找到達(dá)目標(biāo)狀態(tài)的路徑，而是找到目標(biāo)狀態(tài)本身。N皇后問題：局部搜索算法在許多最優(yōu)化問題中，我們不是要尋找到達(dá)目標(biāo)狀態(tài)的32局部搜索算法局部搜索算法：從單個當(dāng)前結(jié)點(diǎn)出發(fā)，通常只移動到它的鄰近狀態(tài)而不保留搜索路徑優(yōu)點(diǎn)：很少的內(nèi)存能在很大的或者無限的狀態(tài)空間中找到合理的解局部搜索算法局部搜索算法：從單個當(dāng)前結(jié)點(diǎn)出發(fā)，通常只移動到它33爬山法爬山法34爬山法缺點(diǎn)?依據(jù)初始狀態(tài)，得到局部最大值爬山法缺點(diǎn)?35爬山法h=直接或者間接相互攻擊的皇后對數(shù)h=17(左圖)h=1(右圖)局部極小值爬山法h=直接或者間接相互攻擊的皇后對數(shù)局部極小值36模擬退火搜索爬山法不完備，隨機(jī)法效率低，考慮結(jié)合兩者產(chǎn)生了模擬退火搜索基本思想：允許算法向壞的方向移動以擺脫局部最大值，但這種移動隨著時間的推移概率逐步下降模擬退火搜索爬山法不完備，隨機(jī)法效率低，考慮結(jié)合兩者產(chǎn)生了模37模擬退火搜索如果時間下降得足夠的慢，那么模擬退火算法找到一個全局最優(yōu)值的概率接近于1模擬退火搜索如果時間下降得足夠的慢，那么模擬退火算法找到一個38局部束搜索隨機(jī)產(chǎn)生k個狀態(tài)，然后每一步從所有的后繼狀態(tài)中選擇k個最佳的后繼狀態(tài)直到找到目標(biāo)狀態(tài)。(內(nèi)存中保留K個狀態(tài))隨機(jī)束搜索：不是找到k個最佳，而是隨機(jī)找到k個后繼狀態(tài)，隨機(jī)概率與狀態(tài)值成正比。局部束搜索隨機(jī)產(chǎn)生k個狀態(tài)，然后每一步從所有的后繼狀態(tài)中選擇39遺傳算法一個后繼狀態(tài)由兩個父狀態(tài)決定以k個隨機(jī)產(chǎn)生的狀態(tài)開始(population)一個狀態(tài)表示成一個字符串定義一個健康度量函數(shù)用來評價狀態(tài)的好壞程度通過選擇，交叉，突變的操作產(chǎn)生下一輪狀態(tài)遺傳算法一個后繼狀態(tài)由兩個父狀態(tài)決定40遺傳算法健康度量函數(shù):非沖突的皇后數(shù)量(min=0,max=8×7/2=28)24/(24+23+20+11)=31%,23/(24+23+20+11)=29%遺傳算法健康度量函數(shù):非沖突的皇后數(shù)量(min=0,41遺傳算法樣本被選擇繁衍后代的概率正比于它的健康度函數(shù)值發(fā)生交叉操作的概率需要預(yù)先設(shè)定，交叉位置隨機(jī)產(chǎn)生發(fā)生突變操作的概率需要預(yù)先設(shè)定，通常遠(yuǎn)小于交叉概率遺傳算法樣本被選擇繁衍后代的概率正比于它的健康度函數(shù)值發(fā)生交42使用不確定性動作的搜索環(huán)境是完全可觀察的和確定的可以知道任何動作序列之后達(dá)到的狀態(tài)環(huán)境是部分可觀察或者是不確定的無法準(zhǔn)確預(yù)知未來狀態(tài)需根據(jù)未來感知信息制定相應(yīng)的行為

使用不確定性動作的搜索環(huán)境是完全可觀察的和確定的43使用不確定性動作的搜索例子：真空洗塵器世界的不穩(wěn)定行為在一塊臟區(qū)域洗塵可以使該區(qū)域干凈，有時也會清潔鄰近區(qū)域在干凈區(qū)域洗塵可能是該區(qū)域弄臟Suckwhenstate=1Ifstate=5then[right,suck]Elsedononthing使用不確定性動作的搜索例子：真空洗塵器世界的不穩(wěn)定行為44與或搜索樹或結(jié)點(diǎn)必須選擇行動在用圓圈表示的與結(jié)點(diǎn)上必須處理所有后繼解用粗黑線標(biāo)出Q:LOOP什么意思？與或搜索樹或結(jié)點(diǎn)必須選擇行動Q:LOOP什么意思？45無觀察信息的搜索Agent感知不到任何信息，稱為無傳感問題，也稱相容問題無傳感問題是可解的還是無解的？可解！真空吸塵器世界無傳感問題的可解性：初始狀態(tài)：｛1，2，3，4，5，6，7，8｝“向右”操作后:{2,4,6,8}“洗塵”操作后{4,8}“向左”操作后{1,7}“洗塵”操作后目標(biāo)狀態(tài){7}在信念狀態(tài)解無觀察信息的問題無觀察信息的搜索Agent感知不到任何信息，稱為無傳感問題46無觀察信息的搜索無觀察信息問題P的定義信念狀態(tài)：包含物理狀態(tài)中每個可能的集合，假定N個物理狀態(tài)，最多有2N個信念狀態(tài)初始狀態(tài)：所有物理狀態(tài)的集合行動：轉(zhuǎn)移模型：對于確定行動對于不確定行動目標(biāo)測試：信念狀態(tài)中的所有物理狀態(tài)都滿足目標(biāo)狀態(tài)路徑開銷：假定所有狀態(tài)下一個行動的開銷相同無觀察信息的搜索無觀察信息問題P的定義47無觀察信息的搜索256個可能的信念狀態(tài)只有12個可達(dá)；初始狀態(tài)出發(fā)的行動序列{S,L,S}與{R,L,S}達(dá)到相同的信念狀態(tài){5,7}如果一個行動序列是信念狀態(tài)b的解，那么它也是b的任何子集的解無觀察信息的搜索256個可能的信念狀態(tài)只有12個可達(dá)；48部分可觀察信息的搜索真空吸塵器世界問題的局部感知：位置傳感器和局部垃圾傳感器例如：狀態(tài)1的可觀察信息percept(s)=[A,dirty]一個信念狀態(tài)到另一個信念狀態(tài)的特定行動分三階段發(fā)生：預(yù)測階段:給定信念狀態(tài)b和行動a，預(yù)測信念狀態(tài)觀察預(yù)測階段:確定預(yù)測信念狀態(tài)中可觀察到的感知信息o:

更新階段：根據(jù)每個可能的感知信息得到信念狀態(tài)

部分可觀察信息的搜索真空吸塵器世界問題的局部感知：49部分可觀察信息的搜索部分可觀察信息的搜索50部分可觀察信息的搜索[Suck,Right,ifBstate={6}the