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

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

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

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

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

Qa？

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

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

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

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