【CN109816115A】一种基于改进Q-learning算法的最短路径问题的解决方法【专利】

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号(43)申请公布日(21)申请号201910011319.7(22)申请日2019.01.07(71)申请人南京航空航天大学地址210016江苏省南京市秦淮区御道街29号(72)发明人魏小辉　廖玮　李旭波　高天驰　李龙　(74)专利代理机构南京经纬专利商标代理有限公司32200代理人姜慧勤(51)Int.Cl.G06N20/00(2019.01)(54)发明名称一种基于改进Q-learning算法的最短路径问题的解决方法(57)摘要本发明公开了一种基于改进Q-learning算法的最短路径问题的解决方法，具体包括：建立位置-动作的价值表格，将Q表全部初始化为0，选择合适的更新步长、贪婪参数、奖赏折扣及平滑参数；根据最短路径问题的要求设置初始位置记作x0，目标位置记作xtf；将当前位置记作X，并将初始位置赋值给当前位置，用epsilon-greedy方法选取动作，记为A；在X处采取动作A，并记录获得的收益r和采取动作A后转移到的位置X’，若X’等于目标位置xtf，则将初始位置x0赋值给X，否则将X’赋值给X；更新Q表；取位置X邻近的所有位置将其记作X1,X2,…,Xn，并更新Q表；重复上述步骤直到Q表收敛。本发明缓解了目前已有的使用Q-learning解决最短路径问题问题时Q表格收敛时间长的问题。权利要求书1页说明书5页附图2页CN109816115A2019.05.28CN109816115A1.一种基于改进Q-learning算法的最短路径问题的解决方法，其特征在于，包括如下步骤：步骤1，建立位置-动作的价值表格，即Q表，将Q表全部初始化为0，并设置如下参数：更新步长α、贪婪参数ε、奖赏折扣γ及平滑参数s；步骤2，将最短路径问题的初始位置记为x0，目标位置记为xtf；步骤3，将当前位置记为X，并将初始位置赋值给当前位置，用ε-greedy方法选取动作，将这个被选取的动作记为A；步骤4，在位置X处采取动作A，并记录获取的收益r和采取动作A后转移到的位置X′，若位置X′等于目标位置xtf，则将初始位置x0赋值给X，否则将X′赋值给X；步骤5，更新Q表，将Q(X,A)更新为Q(X,A)+α[r+γmaxaQ(X′,a)-Q(X,A)]，其中，Q(X,A)表示在位置X处采取动作A所能获得的价值，maxaQ(X′,a)表示在位置X′处采取使Q(X′,a)最大的动作a所获得的价值；步骤6，将位置X邻近的所有位置记为X1,X2,…,Xn，其中，n＝2N，N为最短路径问题所在空间的维数，并将Q(Xi,A)更新为Q(Xi,A)+sα[r+γmaxaQ(X′,a)-Q(X,A)]，i＝1,2,…,n；步骤7，重复步骤3-步骤6直至Q表收敛，当Q表收敛后，在当前位置采取Q值最大的动作，即可从初始位置一步一步移动到目标位置。2.根据权利要求1所述基于改进Q-learning算法的最短路径问题的解决方法，其特征在于，步骤3所述用ε-greedy方法选取动作，将这个被选取的动作记为A，具体为：以概率ε随机选取动作，将这个被选取的动作记为A；或者以概率1-ε选取在位置X处Q值最大的动作，将Q值最大的动作记为A。3.根据权利要求1所述基于改进Q-learning算法的最短路径问题的解决方法，其特征在于，步骤6所述位置X邻近的所有位置X1,X2,…,Xn，按照以下方法选取：X1＝(X1-1,X2,…,XN)，X2＝(X1+1,X2,…,XN)，X3＝(X1,X2-1,…,XN)，X4＝(X1,X2+1,…,XN)，……，Xn-1＝(X1,X2,…,XN-1)，Xn＝(X1,X2,…,XN+1)，其中，(X1,X2,…,XN)表示位置X在N维空间中的坐标。4.根据权利要求1所述基于改进Q-learning算法的最短路径问题的解决方法，其特征在于，所述贪婪参数ε为0.1。5.根据权利要求1所述基于改进Q-learning算法的最短路径问题的解决方法，其特征在于，所述奖赏折扣γ为0.9。6.根据权利要求1所述基于改进Q-learning算法的最短路径问题的解决方法，其特征在于，所述平滑参数s为0.3。权　利　要　求　书1/1页2CN109816115A2一种基于改进Q-learning算法的最短路径问题的解决方法技术领域[0001]本发明涉及一种基于改进Q-learning算法的最短路径问题的解决方法，属于强化学习技术领域。背景技术[0002]最短路径问题广泛存在于导航、城市规划、电子游戏等领域。传统的最短路径问题的解决方法一般依赖于最短路径算法，例如Floyd算法、Dijkstra算法、或者A*算法等搜索算法。近年来，随着强化学习的兴起，强化学习在最短路径问题中的运用也越来越广泛。Q-Learning算法是一种经典的强化学习算法，最早于20世纪90年代初提出，最早的Q-Learning是基于Q表格的，即一张表格，表格中记录了在任一状态下采取任一动作的价值，这个价值一般记作Q(x,a)，其中，x表示状态，a表示所采取的动作。虽然Q-Learning的提出距今已经很多年了，但是这种算法依然没有过时，许多改进过的Q-Learning算法大放异彩，例如2013年研究人员将Q-Learning与人工神经网络相结合提出了Deep Q-Learning(DQN)算法；2015年Google公司旗下的DeepMind团队继续改进了DQN算法，将改进后的算法用于玩Atari游戏，并在很多款游戏中取得了超越人类的好成绩。[0003]尽管DQN算法非常强大，但是现实中依旧有一些问题需要使用Q表格来解决，而Q表格有一种缺陷——它没有考虑到不同状态之间的相似程度，而且，当状态的数量比较多时，Q表难以收敛甚至无法收敛。对于很多工程问题而言，有一些状态比较相似，有一些状态不那么相似，在相似的状态上采取的动作也应该是相似的。发明内容[0004]本发明所要解决的技术问题是：提供一种基于改进Q-learning算法的最短路径问题的解决方法，该方法解决了在使用Q-Learning算法寻找最短路径过程中Q表格难以收敛的问题。[0005]本发明为解决上述技术问题采用以下技术方案：[0006]一种基于改进Q-learning算法的最短路径问题的解决方法，包括如下步骤：[0007]步骤1，建立位置-动作的价值表格，即Q表，将Q表全部初始化为0，并设置如下参数：更新步长α、贪婪参数ε、奖赏折扣γ及平滑参数s；[0008]步骤2，将最短路径问题的初始位置记为x0，目标位置记为xtf；[0009]步骤3，将当前位置记为X，并将初始位置赋值给当前位置，用ε-greedy方法选取动作，将这个被选取的动作记为A；[0010]步骤4，在位置X处采取动作A，并记录获取的收益r和采取动作A后转移到的位置X′，若位置X′等于目标位置xtf，则将初始位置x0赋值给X，否则将X′赋值给X；[0011]步骤5，更新Q表，将Q(X,A)更新为Q(X,A)+α[r+γmaxa Q(X′,a)-Q(X,A)]，其中，Q(X,A)表示在位置X处采取动作A所能获得的价值，maxa Q(X′,a)表示在位置X′处采取使Q(X′,a)最大的动作a所获得的价值；说　明　书1/5页3CN109816115A3[0012]步骤6，将位置X邻近的所有位置记为X1,X2,…,Xn，其中，n＝2N，N为最短路径问题所在空间的维数，并将Q(Xi,A)更新为Q(Xi,A)+sα[r+γmaxa Q(X′,a)-Q(X,A)]，i＝1,2,…,n；[0013]步骤7，重复步骤3-步骤6直至Q表收敛，当Q表收敛后，在当前位置采取Q值最大的动作，即可从初始位置一步一步移动到目标位置。[0014]作为本发明的一种优选方案，步骤3所述用ε-greedy方法选取动作，将这个被选取的动作记为A，具体为：以概率ε随机选取动作，将这个被选取的动作记为A；或者以概率1-ε选取在位置X处Q值最大的动作，将Q值最大的动作记为A。[0015]作为本发明的一种优选方案，步骤6所述位置X邻近的所有位置X1,X2,…,Xn，按照以下方法选取：[0016]X1＝(X1-1,X2,…,XN)，X2＝(X1+1,X2,…,XN)，X3＝(X1,X2-1,…,XN)，[0017]X4＝(X1,X2+1,…,XN)，……，Xn-1＝(X1,X2,…,XN-1)，Xn＝(X1,X2,…,XN+1)，[0018]其中，(X1,X2,…,XN)表示位置X在N维空间中的坐标。[0019]作为本发明的一种优选方案，所述贪婪参数ε为0.1。[0020]作为本发明的一种优选方案，所述奖赏折扣γ为0.9。[0021]作为本发明的一种优选方案，所述平滑参数s为0.3。[0022]本发明采用以上技术方案与现有技术相比，具有以下技术效果：[0023]1、本发明除了更新状态X处的Q值外，还更新了状态X附近的所有状态的Q值，这样做体现了状态空间的连续性，可以加速Q-Learning的收敛。[0024]2、本发明方法能够缓减目前已有的最短路径问题的解决方法收敛时间长的问题。附图说明[0025]图1是本发明一种基于改进Q-learning算法的最短路径问题的解决方法的流程图。[0026]图2是最短路径问题示意图。[0027]图3是本发明方法与经典Q-learning算法的计算结果对比图。具体实施方式[0028]下面详细描述本发明的实施方式，所述实施方式的示例在附图中示出。下面通过参考附图描述的实施方式是示例性的，仅用于解释本发明，而不能解释为对本发明的限制。[0029]如图1所示，为本发明一种基于改进Q-learning算法的最短路径问题的解决方法的流程图，具体步骤为：[0030]步骤1、建立位置-动作的价值表格，位置指的是智能体在空间中的位置，动作指的是智能体的移动方向，以下简称Q表。Q(x,a)表示在位置x处采取动作a所能获得的价值，将Q表全部初始化为0，选择合适的更新步长α、贪婪参数ε、奖赏折扣γ及平滑参数s；[0031]步骤2、根据最短路径问题的要求设置初始位置，将初始位置记作x0，将目标位置记作xtf；[0032]步骤3、将当前位置记作X，并将初始位置赋值给当前位置，用ε-greedy方法选取动作，即以概率ε随机选取动作，将这个被选中的动作记作A，或者以概率1-ε选取在位置X处Q说　明　书2/5页4CN109816115A4值最大的动作，将这个被选中的动作记作A；[0033]步骤4、在X处采取动作A，并记录获得的收益r和采取动作A后转移到的位置X′，若X′等于目标位置xtf，则将初始位置x0赋值给X，否则将X′赋值给X；[0034]步骤5、更新Q表，将Q(X,A)更新为Q(X,A)+α[r+γmaxa Q(X′,a)-Q(X,A)]；[0035]步骤6、取位置X邻近的所有位置将其记作X1,X2,…,Xn，并将Q(Xi,A)更新为Q(Xi,A)+sα[r+γmaxa Q(X′,a)-Q(X,A)]，其中，i＝1,2,…,n；[0036]选取与位置X临近的所有位置记作X1,X2,…,Xn按照以下方法选取：X1＝(X1-1,X2,…,XN)，X2＝(X1+1,X2,…,XN)，X3＝(X1,X2-1,…,XN)，X4＝(X1,X2+1,…,XN)，……，Xn-1＝(X1,X2,…,XN-1)，Xn＝(X1,X2,…,XN+1)。[0037]步骤7、重复步骤3到6直到Q表收敛。[0038]在Q表收敛之后，只需要在当前位置采取Q值最高的动作，即可从初始位置一步一步移动到目标位置。[0039]Q表的形式由问题的具体形式而定，若待解决的问题是N维空间中的最短路径问题，则Q表是一个N+1维的数组，其中前N维表示位置，第N+1维表示动作，N维空间中的位置X用一个元组表示：(X1,X2,…,XN)。[0040]下面以本发明方法解决一个在32*32的网格中寻找最短路径的问题，如图2所示：将一个agent的初始位置设置为左下角的“x”形标记处，坐标是(1,