(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111405874.1 (22)申请日 2021.11.24 (71)申请人 上海交通大 学 地址 200240 上海市闵行区东川路80 0号 (72)发明人 刘畅　汪润中　严骏驰　 (74)专利代理 机构 上海交达专利事务所 31201 代理人 王毓理　王锡麟 (51)Int.Cl. G06F 30/13(2020.01) G06F 30/27(2020.01) (54)发明名称 基于强化学习的设施 布局优化方法 (57)摘要 一种基于强化学习的设施布局优化方法， 通 过针对伴随图的图神经网络并与 深度双层优势Q 神经网络相结合， 利用强化学习进行优化。 本发 明尝试使用强化学习模型来设计设施布局方法， 采用无需标签的训练方式， 即在训练过程中无需 使用当前设施布局场景的最优解或次优解作为 标签， 从而在精度和效率中做出平衡 。 权利要求书2页 说明书6页 附图2页 CN 114139254 A 2022.03.04 CN 114139254 A 1.一种基于强化学习的设施布局优化方法， 其特征在于， 包括： 离线阶段和在线阶段， 其中： 离线阶段包括： 步骤1)从已有数据集中选择若干设施布局场景进行建模， 将其抽象为在伴随图上选择 节点； 步骤2)创建智能体与对应的神经网络， 并设定训练轮数； 步骤3)构建伴随图G， 每 个点均标为可 行； 步骤4)利用神经网络对伴随图G进行特征抽取， 对每个节点进行一个评估， 在此基础上 选择下一个可 行点， 作为动作； 步骤5)根据步骤4中选择的动作点， 更新伴随图， 标注已选择的动作点和由于限制无法 选择的点， 具体为： 通过神经网络估计选择每个动作可能获得的奖励， 以选择可能获得的奖 励值最高的动作， 当每选择一个动作后得到确定的奖励值； 通过与神经网络估计的Q值进 行 对比， 以更新神经网络； 步骤6)当还有点可选时 回到步骤4， 否则进入步骤7； 步骤7)计算本次得到的奖励值的估计， 即Q值， 更新选择智能体动作的策略并通过实际 获得的奖励值训练神经网络， 从而实现强化学习， 当训练未结束回到步骤3， 训练到达设定 的轮数则进入步骤8； 步骤8)预训练完成， 保存 模型参数， 离线阶段 结束； 在线阶段包括： 步骤a)对待优化的设施 布局场景进行建模， 将其抽象成在伴随图上选择节点； 步骤b)创建智能体与对应的神经网络， 并加载离线阶段保存的模型参数； 步骤c)构建伴随图G， 每 个点均标为可 行； 步骤d)通过对伴随图G的观察与特征抽取， 利用强化学习方法选择合适的可行点， 作为 动作； 步骤e)根据步骤d中选择的点， 更新伴随图， 标注已选择的点， 和由于限制无法选择的 点； 步骤f)当还有点可选时 回到步骤d， 否则进入步骤g； 步骤g)将所有已经选择的点整合， 即得到针对输入场景的布局方法； 所述的建模， 具体过程为： 将房间与候选位置作为节点， 利用三角 剖分建立房间拓扑图 和候选位置拓扑图， 然后将两张拓扑图融合为伴 随图， 图上 的每个节点表示将一个房间与 一个候选位置匹配， 从而将设施 布局问题建模为在伴随图上选择若干节点的问题。 2.根据权利要求1所述的基于强化学习的设施布局优化方法， 其特征是， 所述的更新选 择是指： 通过神经网络估计选择每个动作可能获得 的奖励， 以选择可能获得 的奖励值最高 的动作， 当每选择一个动作后， 得到确定的奖励值； 通过与神经网络估计的Q值进 行对比， 以 更新神经网络 。 3.根据权利要求1所述的基于强化学习的设施布局优化方法， 其特征是， 所述的特征提 取， 通过伴随 图特征抽取神经网络实现， 即根据相 邻特征提取顶点特征， 并在每次迭代中不 断地融合每个节点的自身 特征与邻居 特征， 使得每个点的特征会融合自身 特征， 邻居 特征， 与图几何结构信息， 具体为： Et + 1＝ReLU(h1+h2+h3+h4) ， 其中： h1＝X′·θ1，权　利　要　求　书 1/2 页 2 CN 114139254 A 2Et为在每次迭代中对伴随图 的嵌入为， h1， h2， h3， h4为的四个隐藏层， 分别为节点自身特征， 节点邻居特征， 图结构 中的 点权与边权； X ′为目前选择的点的矩阵为， 即当前的排列阵； F为伴随图中的点权矩阵， W为 伴随图中的边权矩阵， θ为神经网络中待学习的参数， n1， n2分别为原图中的点数； 图神经网 络在每次迭代中， 先计算出h1， h2， h3， h4四个隐藏层， 然后将其融合， 作为新的图嵌入为； 这 样的迭代会重复若干次， 最终使得图嵌入为能将图中所有的信息尽可能全面的融合； 伴 随 图的初始嵌入为E0规定为0， 同时使用ReLU作为神经网络的激 活函数； 在计算的过程中除以 (n1‑1)(n2‑1)是为计算所有节点的平均值。 4.根据权利要求1所述的基于强化学习的设施布局优化方法， 其特征是， 所述的奖励 值， 通过深度双层优势Q神经网络根据智能体的状态作为输入后估计得到， 具体为： 其中： h5＝ReLU(ET·θ6+b1)， ha＝h5·θ8+b3， ET是伴随图 特征抽取神经网络的最终输出， hv为状态价值函 数的隐藏层， ha为优势价值函数的隐藏层， Q 是最终输出的预测值， 即神经网络在当前状态下对每 个动作的价 值的估计值。 5.根据权利要求1所述的基于强化学习的设施布局优化方法， 其特征是， 所述的训练， 智能体由当前 的状态选择合适的动作， 环境会给智能体奖励作为反馈， 同时环境会转移到 下一状态； 这一过程会被不断重复， 在重复的过程中， 智能体会积累经验， 该经验为(s,a,r, s’)， 其中： s为当前状态， a为智能体选择的动作， r 为智能体得到的奖励， s ’为环境转移之后 的新状态； 将这些经验存储到经验池 中； 随着训练过程的进行， 会不断将新的经验存入 同时删除一 些旧的经验来保证 中的经验总数维持在定 值； 智能体会定期从经验池 中进行采样， 并使用采样到的经验来更新 其深度双 层优势Q神经网络fθ。 6.根据权利要求1或5所述的基于强化学习的设施布局优化方法， 其特征是， 所述的训 练， 使用梯度下降算法实现， 具体为： 损失函数 其中： γ是折扣因子， 用于反映未来的不确定性； (s,a,r, s’)为之前提到的 由状态， 动作， 奖励和下一 步的状态构成的智能体的经验。 7.根据权利要求6所述的基于强化学习的设施布局优化方法， 其特征是， 所述的损失函 数， 通过当前的Q值估算网络fθ选择下动作a ′， 但是使用目标Q网络fθ‑来预测这个动作对应 的Q值， 即当网络中被高估的Q值将在另一网络中在一定程度上得到缓解， 两个网络同时对 同动作产生过高估计的概率会更小， 修改后的损失函数为： 损失函 数 8.一种实现权利要求1～7中任一所述方法的基于强化学习的设施布局优化系统， 其特 征在于， 包括： 离线预训练模块和在线设施布局模块， 其中： 离线预训练模块根据已有的数 据集信息， 对智能体的神经网络进 行训练； 在线设施布局模块根据实际的应用场景， 利用训 练好的神经网络， 利用强化学习智能体输出一套设施 布局方案 。权　利　要　求　书 2/2 页 3 CN 114139254 A 3