第三章 問(wèn)題求解方法

人工智能

(ArtificialIntelligence)第三章問(wèn)題求解方法Chapter3.ProblemsSolving本章教學(xué)計(jì)劃教學(xué)重點(diǎn)1.圖搜索策略2.搜索技術(shù)教學(xué)難點(diǎn)1.啟發(fā)式搜索算法2.模擬退火算法3.遺傳算法教學(xué)要求：了解和掌握各類常用的搜索算法，著重對(duì)適于AI的啟發(fā)式算法的理解。3.1圖搜索策略

(Strategiesforsearching)圖搜索策略在圖中尋找特定路徑的方法。圖中每個(gè)節(jié)點(diǎn)對(duì)應(yīng)于一個(gè)狀態(tài)，節(jié)點(diǎn)間的連接邊對(duì)應(yīng)于轉(zhuǎn)移函數(shù)。圖搜索策略即為選擇適合的搜索算法，可用于在狀態(tài)空間中找到能實(shí)現(xiàn)從初始狀態(tài)到目標(biāo)狀態(tài)的轉(zhuǎn)移路徑。*

3.1圖搜索策略

(Strategiesforsearching)3.2狀態(tài)空間搜索概述

(StateSpaceSearchingScheme)狀態(tài)圖狀態(tài)圖中的節(jié)點(diǎn)表示問(wèn)題的一種格局，轉(zhuǎn)移函數(shù)控制格局之間的轉(zhuǎn)換。當(dāng)目標(biāo)格局出現(xiàn)時(shí)，表示搜索成功。Question：Issearchingproceduredestinedfortermination?Why?3.2狀態(tài)空間搜索概述

(StateSpaceSearchingScheme)問(wèn)題求解與狀態(tài)空間搜索(1)將問(wèn)題形式化定義為四元組的狀態(tài)機(jī)(2)狀態(tài)空間法將求解過(guò)程定義為若干算子與搜索的有機(jī)結(jié)合體(3)狀態(tài)空間包含問(wèn)題相關(guān)對(duì)象的各種可能排列(4)定義出初始狀態(tài)和目標(biāo)狀態(tài)(5)使用規(guī)則對(duì)應(yīng)搜索操作3.2狀態(tài)空間搜索概述

(StateSpaceSearchingScheme)pp.55-56,eg.3.1,3.2pp.57-58,eg.3.3搜索的基本問(wèn)題：搜索過(guò)程是否一定有解？搜索過(guò)程是否可終止？搜索得到的解是否唯一？搜索得到的解是否最優(yōu)？搜索算法的空間和時(shí)間復(fù)雜性？3.2狀態(tài)空間搜索-盲目的圖搜索

(BruteForceSearching)搜索的概念與特點(diǎn)pp.58按固定算法進(jìn)行搜索，不針對(duì)特定問(wèn)題的信息條件pp.60,搜索代價(jià)主要類型回溯寬度優(yōu)先深度優(yōu)先圖搜索盲目的圖搜索-回溯(BackTracking)帶回溯策略的搜索是從初始狀態(tài)出發(fā)，試探性尋找路徑，直到達(dá)到目的狀態(tài)或得到不可解結(jié)論。該求解過(guò)程呈現(xiàn)遞歸性質(zhì)。pp.61.StepTrack()?pp.62.Figure3.6pp.63.Functionbacktrack3.2狀態(tài)空間搜索-盲目的圖搜索

(BruteForceSearching)特點(diǎn)按固定算法進(jìn)行搜索，不針對(duì)特定問(wèn)題的信息條件主要類型回溯寬度優(yōu)先深度優(yōu)先圖搜索盲目的圖搜索-寬度優(yōu)先(WFS)AlgorithmBreadth_First_Searchpp.64eg.3.4pp.65如何描述其狀態(tài)空間？3.2狀態(tài)空間搜索-盲目的圖搜索

(BruteForceSearching)特點(diǎn)按固定算法進(jìn)行搜索，不針對(duì)特定問(wèn)題的信息條件主要類型回溯寬度優(yōu)先深度優(yōu)先圖搜索盲目的圖搜索-深度優(yōu)先(DFS)定義：首先擴(kuò)展最新產(chǎn)生(深度)的節(jié)點(diǎn)算法為防止搜索沿?zé)o效路徑一直擴(kuò)展，通常會(huì)給出一個(gè)節(jié)點(diǎn)擴(kuò)展最大深度限制。盲目的圖搜索-深度優(yōu)先(DFS)pp.66.AlgorithmDescriptionpp.67.eg.3.53.2狀態(tài)空間搜索-盲目的圖搜索

(BruteForceSearching)特點(diǎn)按固定算法進(jìn)行搜索，不針對(duì)特定問(wèn)題的信息條件主要類型回溯寬度優(yōu)先深度優(yōu)先圖搜索盲目的圖搜索-圖搜索(GS)根據(jù)搜索路徑呈現(xiàn)出的圖特性來(lái)搜索其它搜索方法：等代價(jià)搜索是寬度優(yōu)先搜索的變形，不是沿等長(zhǎng)度路徑斷層進(jìn)行擴(kuò)展，而是沿連接弧線上相關(guān)代價(jià)，按等代價(jià)路徑斷層進(jìn)行擴(kuò)展。分支界限法pp.683.3啟發(fā)式搜索

(HeuristicSearching)概念和特點(diǎn)pp.69選擇最有希望的節(jié)點(diǎn)(目標(biāo))進(jìn)行搜索擴(kuò)展主要類型A算法A*算法3.3啟發(fā)式搜索

(HeuristicSearching)啟發(fā)式策略(HeuristicStrategy)啟發(fā)是針對(duì)發(fā)現(xiàn)操作算子啟發(fā)式信息是指用于加速搜索過(guò)程的有關(guān)問(wèn)題域所包含的特征信息啟發(fā)式策略的應(yīng)用場(chǎng)景(Context)問(wèn)題的陳述和數(shù)據(jù)獲取具有模糊性盲目搜索的時(shí)間代價(jià)太高*pp.70,eg.3.63.3啟發(fā)式搜索

(HeuristicSearching)啟發(fā)信息和估價(jià)函數(shù)pp.71-72為實(shí)現(xiàn)節(jié)點(diǎn)的啟發(fā)式信息目標(biāo)，提供對(duì)搜索算法新搜索路徑選擇的支持，使用量化的函數(shù)來(lái)評(píng)估搜索的有效性。啟發(fā)式信息(不完全/效率)：陳述型過(guò)程型控制型3.3啟發(fā)式搜索

(HeuristicSearching)啟發(fā)信息和估價(jià)函數(shù)pp.71-72啟發(fā)式函數(shù)f(n):

節(jié)點(diǎn)的評(píng)估函數(shù)f(n)=g(n)+h(n)//有記憶性g(n)g(n).vs.h(n)估價(jià)函數(shù)的設(shè)計(jì)將直接決定搜索算法的性能易于導(dǎo)致局部最優(yōu)過(guò)早收斂3.3啟發(fā)式搜索算法-A&A*算法

(HeuristicSearching)Procedureheuristic_searchpp.73Beginopen,close,f(s)=g(s)+h(s)//initWhile(!EMPTY(open))do…foreachsub-stateofndocase1:newstate;//intocandidatecase2:stateinOPEN;//updateactivetablecase3:stateinCLOSE;//updateinactivetable…endfor…endwhile//heretomeanfailureend3.3啟發(fā)式搜索算法-A&A*算法

(HeuristicSearching)pp.75,eg.3.8A算法求解八數(shù)碼問(wèn)題的搜索樹(shù)，估價(jià)函數(shù)定義為f(n)=d(n)+w(n)Keyproblemistochoosetheevaluationfunction.pp.76,figure3.163.3啟發(fā)式搜索算法-A&A*算法

(HeuristicSearching)A*搜索算法的討論可采納性，單調(diào)性，信息性1.可采納性當(dāng)一個(gè)搜索算法在最短路徑存在時(shí)能保證找到它，則稱為可采納的。pp.75f*(n)=g*(n)+h*(n)g(n)層數(shù)，h*(n)啟發(fā)函數(shù)該函數(shù)可作中間參照，一旦f超過(guò)f*可確定該節(jié)點(diǎn)n不是所需節(jié)點(diǎn)3.3啟發(fā)式搜索算法-A&A*算法

(HeuristicSearching)A*搜索算法的討論2.單調(diào)性對(duì)一個(gè)啟發(fā)式函數(shù)有：(1)對(duì)狀態(tài)ni和nj，nj是ni的后繼，滿足h(ni)-h(nj)<=cost(ni,nj)，其中cost(ni,nj)是從ni到nj的實(shí)際代價(jià)；(2)目的狀態(tài)的啟發(fā)函數(shù)值為0或h(Goal)=0；則稱該啟發(fā)函數(shù)h(n)是單調(diào)的。3.3啟發(fā)式搜索算法-A&A*算法

(HeuristicSearching)A*搜索算法的討論3.信息性h1(n1)<=h2(n2)，稱策略h2比h1具更多信息性。h(n)越大表示所搜索的狀態(tài)越少，因此搜索效果更好。3.4與/或圖搜索

(And/OrSearching)特點(diǎn)使用與/或表示事物間的聯(lián)系，對(duì)問(wèn)題進(jìn)行規(guī)約求解。主要類型AO算法AO*算法3.4與/或圖搜索-概念

(Conception)與/或圖的概念Reviewpp.20問(wèn)題求解的規(guī)約pp.78,figure3.17,figure3.18可解節(jié)點(diǎn)與非可解節(jié)點(diǎn)的遞歸定義pp.78可解圖定義pp.78-79可解圖擴(kuò)展的代價(jià)計(jì)算pp.793.4與/或圖搜索-AO,AO*算法

(And/OrAlgorithm)AOandAO*Algorithmpp.80-81書中的描述？Figure3.23(c)(d)OR(n5,n6)?算法是針對(duì)AO圖所表示的問(wèn)題進(jìn)行啟發(fā)式搜索求解，求得可能的解路徑(解圖)則為解決該問(wèn)題時(shí)的規(guī)約子問(wèn)題。3.4與/或圖搜索-博弈樹(shù)搜索

(GameSearching)pp.83,eg.3.10explanation盡量使游戲向有利于自己方發(fā)展局部狀態(tài)與全局狀態(tài)的考慮3.4與/或圖搜索-博弈樹(shù)搜索

(GameSearching)pp.85,eg.3.11一字棋游戲pp.89,eg.3.12

3.5局部搜索算法

(LocalSearching)特點(diǎn)沿梯度最大變化反方向選擇搜索路徑pp.90,procedurelocal_search…

while…iff(xn)<f(xb)thenxb=xn,P=N(xn)//若趨勢(shì)向好的方向發(fā)展，則重新選擇鄰域3.5局部搜索算法

(LocalSearching)pp.91,eg.3.13局部搜索的問(wèn)題：(1)局部最優(yōu)問(wèn)題？初始點(diǎn)的選擇對(duì)全局最優(yōu)點(diǎn)的影響多極值如何避免局部收斂？為什么不用定義域來(lái)表示該概率xi/∑(xi)3.5局部搜索算法

(LocalSearching)局部搜索的問(wèn)題：(2)步長(zhǎng)問(wèn)題對(duì)收斂速度的影響對(duì)全局收斂的影響可變步長(zhǎng)與動(dòng)量方法3.6模擬退火算法

(SimulatedAnnealingAlgorithm)概念是局部搜索算法的一種擴(kuò)展是對(duì)固體退火物理過(guò)程的模擬pp.93-94初始溫度必須足夠高每個(gè)溫度下，能量的轉(zhuǎn)換充分溫度的下降必須足夠緩慢最終溫度必須足夠低Simulatedannealing(SA)(/wiki/Simulated_annealing)3.6模擬退火算法

(SimulatedAnnealingAlgorithm)模擬退火算法

pp.94表3.2組合優(yōu)化問(wèn)題與固體退火過(guò)程的類比組合優(yōu)化問(wèn)題固體退火過(guò)程組合優(yōu)化問(wèn)題的解i(i∈D)物理系統(tǒng)中的一個(gè)狀態(tài)s(s∈S)解的指標(biāo)函數(shù)f(i)狀態(tài)的能量E(s)解在鄰域N中的交換X粒子的熱運(yùn)動(dòng)M最優(yōu)解fmin(i)能量最低狀態(tài)Emin(x)控制參數(shù)溫度T3.6模擬退火算法

(SimulatedAnnealingAlgorithm)類固體退火過(guò)程(1)設(shè)置較大溫度t(2)隨機(jī)設(shè)定一個(gè)初始解值i及領(lǐng)域N(i)(局部搜索)(3)求解轉(zhuǎn)移概率(4)若新解j被接受，則以j替代i，否則i不變。重復(fù)(3)~(4)，直到在控制參數(shù)t下達(dá)到平衡下調(diào)t重復(fù)上述過(guò)程，直到退火t穩(wěn)定3.6模擬退火算法

(SimulatedAnnealingAlgorithm)pp.95ProcedureSimulated-AnnealingBeginInitiation:t0,x0Loop1untiltislowenoughLoop2untilbanlanceattComputingf(x)|tendLoop2decreasetendLoop1end3.6模擬退火算法

(SimulatedAnnealingAlgorithm)局部搜索與模擬退火算法間的差異SA接受劣解見(jiàn)轉(zhuǎn)移函數(shù)PtPt是t的函數(shù)，當(dāng)t較大時(shí)，接受劣解的概率大這種差異設(shè)計(jì)有什么優(yōu)點(diǎn)？3.6模擬退火算法

(SimulatedAnnealingAlgorithm)控制參數(shù)的確定并不是任何一組參數(shù)都保證SA算法收斂于某一近似解；經(jīng)驗(yàn)表明，解質(zhì)量與算法的運(yùn)行時(shí)間成正比關(guān)系，因此結(jié)果取決于平衡選擇；pp.96控制參數(shù)包括:初始溫度參數(shù)t0溫度tk的衰減函數(shù)Drop(tk)，即溫度下降設(shè)計(jì)每一溫度tk下的停止準(zhǔn)則，即馬爾科夫長(zhǎng)度Lk算法的終止準(zhǔn)則3.6模擬退火算法-參數(shù)控制

(SA-ParameterSetting)1.初始溫度t0(1)給定一個(gè)希望的初始接受概率P0，給定一個(gè)較低的初始溫度t0，如t0=1(2)隨機(jī)產(chǎn)生狀態(tài)序列，接受概率計(jì)算公式為

接受概率=接受的狀態(tài)數(shù)/產(chǎn)生的狀態(tài)總數(shù)如果接受概率小于給定的初始概率P0，則提高溫度，更新t0，直至接受概率大于P03.6模擬退火算法-參數(shù)控制

(SA-ParameterSetting)2.溫度的下降方法為保證溫度盡可能緩慢下降，常用下述方法：(1)等比例下降

tk+1=a*tk(0<a<1)(2)等值下降

tk+1=tk-delta(t)(3)基于距離參數(shù)的下降法

pp.97,formula3.11,3.123.6模擬退火算法-參數(shù)控制

(SA-ParameterSetting)3