計(jì)算與人工智能概論第8章智能決策目錄搜索策略群體智能31強(qiáng)化學(xué)習(xí)13223搜索策略1PART搜索策略八皇后問(wèn)題八數(shù)碼問(wèn)題非結(jié)構(gòu)化問(wèn)題求解方法搜索搜索問(wèn)題搜索策略搜索策略——策

略

分

類(lèi)搜索策略盲目搜索啟發(fā)式搜索依照預(yù)先確定的規(guī)則進(jìn)行搜索利用已知信息，動(dòng)態(tài)地調(diào)整搜索規(guī)則代表算法：深度優(yōu)先搜索DFS寬度優(yōu)先搜索BFS代表算法：A*搜索算法搜索策略——深

度

優(yōu)

先

搜

索深度優(yōu)先搜索（DepthFirstSearch，DFS）搜索次序搜索方向：縱向優(yōu)先擴(kuò)展深度最深的結(jié)點(diǎn)添加深度限制，降低試錯(cuò)成本目標(biāo)狀態(tài)深度限制示例：八數(shù)碼問(wèn)題搜索策略——深

度

優(yōu)

先

搜

索搜索方向：橫向?qū)挾葍?yōu)先搜索（Breadth

FirstSearch，BFS）搜索次序優(yōu)先擴(kuò)展層數(shù)較低的結(jié)點(diǎn)必能找到存在的最優(yōu)解搜索策略——寬

度

優(yōu)

先

搜

索目標(biāo)狀態(tài)示例：八數(shù)碼問(wèn)題搜索策略——寬

度

優(yōu)

先

搜

索A搜索算法

待評(píng)價(jià)的結(jié)點(diǎn)從結(jié)點(diǎn)s到結(jié)點(diǎn)x的實(shí)際代價(jià)從x到達(dá)結(jié)點(diǎn)t的最優(yōu)路徑的代價(jià)估計(jì)值評(píng)價(jià)函數(shù)啟發(fā)函數(shù)：反映問(wèn)題的特征；

根據(jù)不同的具體問(wèn)題進(jìn)行定義exp.路徑長(zhǎng)度、走完路徑所需時(shí)間、金錢(qián)開(kāi)銷(xiāo)…A*搜索算法h(x)≤h*(x)滿(mǎn)足

的A搜索算法

結(jié)點(diǎn)x到目標(biāo)結(jié)點(diǎn)的最小代價(jià)搜索策略——A*

搜

索示例：八數(shù)碼問(wèn)題目標(biāo)狀態(tài)h(x)=與目標(biāo)狀態(tài)的布局不一致的棋子的個(gè)數(shù)g(x)=當(dāng)前狀態(tài)的結(jié)點(diǎn)x在整個(gè)搜索圖中的深度搜索策略——A*

搜

索搜索策略——算

法

對(duì)

比優(yōu)點(diǎn)缺點(diǎn)時(shí)間復(fù)雜度空間復(fù)雜度DFS當(dāng)目標(biāo)結(jié)點(diǎn)處于搜索所進(jìn)入的分支上時(shí)，可以較快地得到解若目標(biāo)結(jié)點(diǎn)不在搜索所進(jìn)入的分支上，且分支具有無(wú)窮多結(jié)點(diǎn)時(shí)，則無(wú)法得到解O(bm)O(b·m)BFS只要問(wèn)題有解，則總能得到解，并且該解必為問(wèn)題的最優(yōu)解當(dāng)目標(biāo)結(jié)點(diǎn)距離初始結(jié)點(diǎn)較遠(yuǎn)時(shí)，搜索效率會(huì)明顯下降，產(chǎn)生的冗余結(jié)點(diǎn)較多O(bd+1)O(bd+1)A*搜索只需要擴(kuò)展最有希望到達(dá)目標(biāo)的結(jié)點(diǎn)，而無(wú)須擴(kuò)展每一層的所有結(jié)點(diǎn)啟發(fā)函數(shù)的選擇與搜索效率直接相關(guān)與啟發(fā)函數(shù)的選擇有關(guān)無(wú)人駕駛自動(dòng)尋路機(jī)器人規(guī)避障礙物游戲編程AI訓(xùn)練導(dǎo)航APP規(guī)劃最優(yōu)路線求解最優(yōu)路徑搜索策略——應(yīng)

用

場(chǎng)

景強(qiáng)化學(xué)習(xí)2PART強(qiáng)化

學(xué)

習(xí)2016年AlphaGo擊敗世界頂級(jí)棋手2017年AlphaGoZero以100比0擊敗了上一版本的AlphaGo核心技術(shù)：強(qiáng)化學(xué)習(xí)強(qiáng)化

學(xué)

習(xí)——基

本

思

路智能體環(huán)境環(huán)境狀態(tài)采取動(dòng)作獎(jiǎng)勵(lì)強(qiáng)化學(xué)習(xí)的目標(biāo)：最大化累計(jì)獎(jiǎng)勵(lì)強(qiáng)化學(xué)習(xí)的本質(zhì)：獎(jiǎng)懲和試錯(cuò)強(qiáng)化

學(xué)

習(xí)——基

本

要

素環(huán)境模型獎(jiǎng)勵(lì)價(jià)值函數(shù)策略從狀態(tài)到動(dòng)作的映射，定義了智能體的行為。對(duì)智能體的序列決策的長(zhǎng)期收益的衡量。環(huán)境對(duì)智能體當(dāng)前行為的即時(shí)反饋，反映了任務(wù)的目標(biāo)。對(duì)環(huán)境的建模，定義在不同狀態(tài)之間的轉(zhuǎn)移概率。強(qiáng)化

學(xué)

習(xí)——案

例

分

析機(jī)器人尋寶問(wèn)題：如何訓(xùn)練一個(gè)機(jī)器人學(xué)會(huì)在游戲中收集寶藏并避免踏入火坑？問(wèn)題分解：機(jī)器人對(duì)環(huán)境的感知和記憶機(jī)器人在環(huán)境中面對(duì)各種情況的決策模式識(shí)別感知環(huán)境：人類(lèi)用眼睛-->機(jī)器人通過(guò)傳感器探索環(huán)境：人類(lèi)四處行走-->機(jī)器人移動(dòng)問(wèn)題抽象——序列決策問(wèn)題環(huán)境抽象為網(wǎng)格世界，以顏色區(qū)分不同的對(duì)象算法設(shè)計(jì)——強(qiáng)化學(xué)習(xí)算法強(qiáng)化

學(xué)

習(xí)——案

例

分

析-10踏入火坑機(jī)器人通過(guò)不斷地與環(huán)境進(jìn)行交互，從錯(cuò)誤中學(xué)習(xí)適應(yīng)環(huán)境，依據(jù)環(huán)境的反饋來(lái)學(xué)習(xí)最優(yōu)策略。+10收集寶藏強(qiáng)化

學(xué)

習(xí)——與

其

他

學(xué)

習(xí)

范

式

的

區(qū)

別強(qiáng)化

學(xué)

習(xí)——應(yīng)

用

場(chǎng)

景無(wú)人駕駛游戲機(jī)器人貨物運(yùn)輸智能推薦汽車(chē)裝配群體智能3PART群體

智

能蟻群搭橋跨越有缺口的地形蟻群造木筏渡過(guò)水面蜂群構(gòu)造巢穴個(gè)體行為簡(jiǎn)單；群體相互協(xié)作時(shí)，表現(xiàn)出復(fù)雜的行為特征群體

智

能——TSP問(wèn)

題路線規(guī)劃問(wèn)題旅行商問(wèn)題（TravellingSalesmanProblem，TSP）群體智能算法exp.蟻群算法

人工蜂群算法求解簡(jiǎn)化群體

智

能——蟻

群

算

法蟻群算法分泌信息素

找到食物與巢穴之間的最短路徑啟發(fā)最初覓食，四處隨機(jī)探索，沿途分泌信息素蟻群找到多條路徑到達(dá)食物源隨時(shí)間的推進(jìn)，相同時(shí)間內(nèi)短路徑上通過(guò)的螞蟻數(shù)量更多，累積的信息素也越多最終，所有螞蟻都聚集到短路徑上群體

智

能——蟻

群

算

法分工活動(dòng)，交流信息

找到最優(yōu)蜜源人工蜂群算法啟發(fā)群體

智

能——人

工

蜂

群

算

法組成要素食物源雇傭蜂雇傭蜂非雇傭蜂偵察蜂跟隨蜂找到食物并分享信息搜尋食物源等待并跟隨偵察蜂群體

智

能——人

工

蜂

群

算

法蜂巢卸蜜房舞蹈區(qū)(1)偵察食物源(2)被招募搜索對(duì)應(yīng)食物源周?chē)⒉擅?1)放棄(2)招募(3)返回繼續(xù)采蜜(4)采蜜結(jié)束偵察蜂出去四處尋找食物源當(dāng)偵察蜂找到食物源時(shí)，就轉(zhuǎn)換為雇傭蜂雇傭蜂將蜜卸載后有三種選擇：1、放棄蜜源，重新成為偵察蜂2、招募跟隨蜂3、不招募跟隨蜂，返回采蜜當(dāng)食物源濃度連續(xù)一定次數(shù)沒(méi)有更新時(shí)結(jié)束采蜜，放棄該食物源食物源群體

智

能——人

工

蜂

群

算

法案例分析4PARTQ-Learning算法：用Q值表來(lái)記錄每個(gè)狀態(tài)下采取每個(gè)動(dòng)作的預(yù)期回報(bào)，智能體在環(huán)境中不斷試錯(cuò)，通過(guò)執(zhí)行動(dòng)作、觀察獎(jiǎng)勵(lì)和新?tīng)顟B(tài)來(lái)更新Q值表，以逼近最優(yōu)策略。DQN（深度Q網(wǎng)絡(luò)）算法：Q-Learning算法的改進(jìn)算法，使用深度神經(jīng)網(wǎng)絡(luò)來(lái)近似Q值函數(shù)，解決Q-Learning算法在狀態(tài)空間較大時(shí)計(jì)算量過(guò)大的問(wèn)題。用強(qiáng)化學(xué)習(xí)求解機(jī)器人尋寶問(wèn)題Q-Learning算法與DQN算法問(wèn)題分解：

機(jī)器人尋寶問(wèn)題被分解為多個(gè)子問(wèn)題，包括環(huán)境定義、網(wǎng)絡(luò)結(jié)構(gòu)定義、動(dòng)作選擇策略、訓(xùn)練過(guò)程和主函數(shù)。模式識(shí)別

運(yùn)用了強(qiáng)化學(xué)習(xí)問(wèn)題的基本模式，即智能體與環(huán)境交互，通過(guò)試錯(cuò)學(xué)習(xí)來(lái)優(yōu)化策略。

使用神經(jīng)網(wǎng)絡(luò)來(lái)近似Q值函數(shù)，并使用經(jīng)驗(yàn)回放技術(shù)來(lái)穩(wěn)定訓(xùn)練。用強(qiáng)化學(xué)習(xí)求解機(jī)器人尋寶問(wèn)題抽象

環(huán)境類(lèi)被抽象為一個(gè)簡(jiǎn)單的游戲環(huán)境，只包含寶藏和火坑的位置，狀態(tài)的初始化和更新。

網(wǎng)絡(luò)結(jié)構(gòu)被抽象為一個(gè)簡(jiǎn)單的全連接神經(jīng)網(wǎng)絡(luò)，用于近似Q值函數(shù)。

動(dòng)作選擇策略被抽象為ε-greedy算法，用于平衡探索和利用。

訓(xùn)練過(guò)程被抽象為一個(gè)包含狀態(tài)轉(zhuǎn)移、獎(jiǎng)勵(lì)計(jì)算、目標(biāo)Q值計(jì)算、梯度下降更新網(wǎng)絡(luò)參數(shù)等步驟的循環(huán)。求解尋寶問(wèn)題的計(jì)算思維方法用強(qiáng)化學(xué)習(xí)求解機(jī)器人尋寶問(wèn)題核心算法--網(wǎng)絡(luò)結(jié)構(gòu)定義defcreate_q_network(state_dim,action_dim):

net=nn.Cell()

#定義網(wǎng)絡(luò)層

net.dense1=nn.Dense(state_dim,128)

net.relu=nn.ReLU()

net.dense2=nn.Dense(128,action_dim)

#定義前向傳播

defconstruct(self,x):

x=self.dense1(x)

x=self.relu(x)

x=self.dense2(x)

returnx

#將construct方法綁定到網(wǎng)絡(luò)上

net.construct=construct.__get__(net)

returnnet用強(qiáng)化學(xué)習(xí)求解機(jī)器人尋寶問(wèn)題核心算法--動(dòng)作選擇策略#選擇動(dòng)作的策略（ε-greedy）defchoose_action(q_values,epsilon):ifnp.random.rand()<epsilon:#隨機(jī)選擇動(dòng)作returnnp.random.choice(len(q_values))else:#選擇Q值最大的動(dòng)作returnnp.argmax(q_values.asnumpy())用強(qiáng)化學(xué)習(xí)求解機(jī)器人尋寶問(wèn)題核心算法--訓(xùn)練函數(shù)deftrain_dqn(env,state_dim,action_dim,episodes=1000,gamma=0.99,epsilon_start=1.0,epsilon_end=0.01,epsilon_decay=0.995,lr=0.001):#創(chuàng)建Q網(wǎng)絡(luò)q_network=create_q_network(state_dim,action_dim)optimizer=optim.Adam(q_network.trainable_params(),lr)criterion=nn.MSELoss()#初始化ε(epsilon)epsilon=epsilon_startforepisodeinrange(episodes):state=env.reset()#假設(shè)env有reset方法返回初始狀態(tài)state=Tensor(state,mindspore.float32)total_reward=0whileTrue:#選擇動(dòng)作q_values=q_network(state)action=choose_action(q_values,epsilon)#執(zhí)行動(dòng)作，獲取新的狀態(tài)和獎(jiǎng)勵(lì)next_state,reward,done=env.step(action)#假設(shè)env有step方法next_state=Tensor(next_state,mindspore.float32)reward=Tensor(reward,mindspore.float32)

用強(qiáng)化學(xué)習(xí)求解機(jī)器人尋寶問(wèn)題核心算法--訓(xùn)練函數(shù)（續(xù)）#計(jì)算目標(biāo)Q值next_q_values=q_network(next_state)target_q_value=reward+gamma*np.max(next_q_values.asnumpy())*(1-done)#done為T(mén)rue時(shí)，目標(biāo)Q值僅為reward#更新Q值withmindspore.GradientTape()astape:q_value=q_network(state)[action]loss=criterion(q_value,Tensor(target_q_value,mindspore.float32))grads=tape.grad(loss,q_network.trainable_params())optimizer.apply_gradients(zip(grads,q_network.trainable_params()))#更新?tīng)顟B(tài)state=next_statetotal_reward+=reward.asnumpy()ifdone:break#衰減epsilonepsilon=max(epsilon_end,epsilon*epsilon_decay)if(episode+1)%100==0:print(f"Episode:{episode+1},TotalReward:{total_reward},ε:{epsilon}")用強(qiáng)化學(xué)習(xí)求解機(jī)器人尋寶問(wèn)題核心算法--環(huán)境類(lèi)classEnv:def__init__(self):self.map_size=(5,5)#地圖大小為5x5self.treasure_position=(3,3)#寶藏位置self.trap_position=(2,1)#火坑位置self.agent_position=(0,0)#初始位置defstep(self,action):#根據(jù)動(dòng)作更新智能體的位置，并檢查地圖邊界x,y=self.agent_positionreward=0done=False#根據(jù)動(dòng)作更新位置ifaction=='up':x-=1elifaction=='down':x+=1elifaction=='left':y-=1elifaction=='right':y+=1#檢查地圖邊界ifnot(0<=x<self.map_size[0]and0<=y<self.map_size[1]):x,y=self