计算与人工智能概论（第2版）（微课版）课件 第8章 智能决策

计算与人工智能概论第8章智能决策目录搜索策略群体智能31强化学习13223搜索策略1PART搜索策略八皇后问题八数码问题非结构化问题求解方法搜索搜索问题搜索策略搜索策略——策

略

分

类搜索策略盲目搜索启发式搜索依照预先确定的规则进行搜索利用已知信息，动态地调整搜索规则代表算法：深度优先搜索DFS宽度优先搜索BFS代表算法：A*搜索算法搜索策略——深

度

优

先

搜

索深度优先搜索（DepthFirstSearch，DFS）搜索次序搜索方向：纵向优先扩展深度最深的结点添加深度限制，降低试错成本目标状态深度限制示例：八数码问题搜索策略——深

度

优

先

搜

索搜索方向：横向宽度优先搜索（Breadth

FirstSearch，BFS）搜索次序优先扩展层数较低的结点必能找到存在的最优解搜索策略——宽

度

优

先

搜

索目标状态示例：八数码问题搜索策略——宽

度

优

先

搜

索A搜索算法

待评价的结点从结点s到结点x的实际代价从x到达结点t的最优路径的代价估计值评价函数启发函数：反映问题的特征；

根据不同的具体问题进行定义exp.路径长度、走完路径所需时间、金钱开销…A*搜索算法h(x)≤h*(x)满足

的A搜索算法

结点x到目标结点的最小代价搜索策略——A*

搜

索示例：八数码问题目标状态h(x)=与目标状态的布局不一致的棋子的个数g(x)=当前状态的结点x在整个搜索图中的深度搜索策略——A*

搜

索搜索策略——算

法

对

比优点缺点时间复杂度空间复杂度DFS当目标结点处于搜索所进入的分支上时，可以较快地得到解若目标结点不在搜索所进入的分支上，且分支具有无穷多结点时，则无法得到解O(bm)O(b·m)BFS只要问题有解，则总能得到解，并且该解必为问题的最优解当目标结点距离初始结点较远时，搜索效率会明显下降，产生的冗余结点较多O(bd+1)O(bd+1)A*搜索只需要扩展最有希望到达目标的结点，而无须扩展每一层的所有结点启发函数的选择与搜索效率直接相关与启发函数的选择有关无人驾驶自动寻路机器人规避障碍物游戏编程AI训练导航APP规划最优路线求解最优路径搜索策略——应

用

场

景强化学习2PART强化

学

习2016年AlphaGo击败世界顶级棋手2017年AlphaGoZero以100比0击败了上一版本的AlphaGo核心技术：强化学习强化

学

习——基

本

思

路智能体环境环境状态采取动作奖励强化学习的目标：最大化累计奖励强化学习的本质：奖惩和试错强化

学

习——基

本

要

素环境模型奖励价值函数策略从状态到动作的映射，定义了智能体的行为。对智能体的序列决策的长期收益的衡量。环境对智能体当前行为的即时反馈，反映了任务的目标。对环境的建模，定义在不同状态之间的转移概率。强化

学

习——案

例

分

析机器人寻宝问题：如何训练一个机器人学会在游戏中收集宝藏并避免踏入火坑？问题分解：机器人对环境的感知和记忆机器人在环境中面对各种情况的决策模式识别感知环境：人类用眼睛-->机器人通过传感器探索环境：人类四处行走-->机器人移动问题抽象——序列决策问题环境抽象为网格世界，以颜色区分不同的对象算法设计——强化学习算法强化

学

习——案

例

分

析-10踏入火坑机器人通过不断地与环境进行交互，从错误中学习适应环境，依据环境的反馈来学习最优策略。+10收集宝藏强化

学

习——与

其

他

学

习

范

式

的

区

别强化

学

习——应

用

场

景无人驾驶游戏机器人货物运输智能推荐汽车装配群体智能3PART群体

智

能蚁群搭桥跨越有缺口的地形蚁群造木筏渡过水面蜂群构造巢穴个体行为简单；群体相互协作时，表现出复杂的行为特征群体

智

能——TSP问

题路线规划问题旅行商问题（TravellingSalesmanProblem，TSP）群体智能算法exp.蚁群算法

人工蜂群算法求解简化群体

智

能——蚁

群

算

法蚁群算法分泌信息素

找到食物与巢穴之间的最短路径启发最初觅食，四处随机探索，沿途分泌信息素蚁群找到多条路径到达食物源随时间的推进，相同时间内短路径上通过的蚂蚁数量更多，累积的信息素也越多最终，所有蚂蚁都聚集到短路径上群体

智

能——蚁

群

算

法分工活动，交流信息

找到最优蜜源人工蜂群算法启发群体

智

能——人

工

蜂

群

算

法组成要素食物源雇佣蜂雇佣蜂非雇佣蜂侦察蜂跟随蜂找到食物并分享信息搜寻食物源等待并跟随侦察蜂群体

智

能——人

工

蜂

群

算

法蜂巢卸蜜房舞蹈区(1)侦察食物源(2)被招募搜索对应食物源周围并采蜜(1)放弃(2)招募(3)返回继续采蜜(4)采蜜结束侦察蜂出去四处寻找食物源当侦察蜂找到食物源时，就转换为雇佣蜂雇佣蜂将蜜卸载后有三种选择：1、放弃蜜源，重新成为侦察蜂2、招募跟随蜂3、不招募跟随蜂，返回采蜜当食物源浓度连续一定次数没有更新时结束采蜜，放弃该食物源食物源群体

智

能——人

工

蜂

群

算

法案例分析4PARTQ-Learning算法：用Q值表来记录每个状态下采取每个动作的预期回报，智能体在环境中不断试错，通过执行动作、观察奖励和新状态来更新Q值表，以逼近最优策略。DQN（深度Q网络）算法：Q-Learning算法的改进算法，使用深度神经网络来近似Q值函数，解决Q-Learning算法在状态空间较大时计算量过大的问题。用强化学习求解机器人寻宝问题Q-Learning算法与DQN算法问题分解：

机器人寻宝问题被分解为多个子问题，包括环境定义、网络结构定义、动作选择策略、训练过程和主函数。模式识别

运用了强化学习问题的基本模式，即智能体与环境交互，通过试错学习来优化策略。

使用神经网络来近似Q值函数，并使用经验回放技术来稳定训练。用强化学习求解机器人寻宝问题抽象

环境类被抽象为一个简单的游戏环境，只包含宝藏和火坑的位置，状态的初始化和更新。

网络结构被抽象为一个简单的全连接神经网络，用于近似Q值函数。

动作选择策略被抽象为ε-greedy算法，用于平衡探索和利用。

训练过程被抽象为一个包含状态转移、奖励计算、目标Q值计算、梯度下降更新网络参数等步骤的循环。求解寻宝问题的计算思维方法用强化学习求解机器人寻宝问题核心算法--网络结构定义defcreate_q_network(state_dim,action_dim):

net=nn.Cell()

#定义网络层

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方法绑定到网络上

net.construct=construct.__get__(net)

returnnet用强化学习求解机器人寻宝问题核心算法--动作选择策略#选择动作的策略（ε-greedy）defchoose_action(q_values,epsilon):ifnp.random.rand()<epsilon:#随机选择动作returnnp.random.choice(len(q_values))else:#选择Q值最大的动作returnnp.argmax(q_values.asnumpy())用强化学习求解机器人寻宝问题核心算法--训练函数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):#创建Q网络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()#假设env有reset方法返回初始状态state=Tensor(state,mindspore.float32)total_reward=0whileTrue:#选择动作q_values=q_network(state)action=choose_action(q_values,epsilon)#执行动作，获取新的状态和奖励next_state,reward,done=env.step(action)#假设env有step方法next_state=Tensor(next_state,mindspore.float32)reward=Tensor(reward,mindspore.float32)

用强化学习求解机器人寻宝问题核心算法--训练函数（续）#计算目标Q值next_q_values=q_network(next_state)target_q_value=reward+gamma*np.max(next_q_values.asnumpy())*(1-done)#done为True时，目标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()))#更新状态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}")用强化学习求解机器人寻宝问题核心算法--环境类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):#根据动作更新智能体的位置，并检查地图边界x,y=self.agent_positionreward=0done=False#根据动作更新位置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