一种差分演化Q表的改进Q-Learning方法.pdf
《一种差分演化Q表的改进Q-Learning方法.pdf》由会员分享,可在线阅读,更多相关《一种差分演化Q表的改进Q-Learning方法.pdf(14页珍藏版)》请在咨信网上搜索。
1、第43卷第4期2023年8 月DOI:10.16185/.2023.04.401一种差分演化Q表的改进Q-Learning方法西安工业大学学报Journal of Xian Technological UniversityVol.43 No.4Aug.2023http:/李骁,曹子建,贾浩文,郭瑞麒(西安工业大学计算机科学与工程学院,西安7 10 0 2 1)摘要:针对Q-Learning算法在路径搜索应用中的盲目性而导致收敛速度慢、回报效率低的问题,文中提出了一种差分演化Q表的改进Q-Learning方法(DE-Q-Learning)。改进算法利用差分演化算法的全局搜索优势,将由Q表个体组成
2、的演化种群通过变异、交叉和选择操作选择出较好的初始Q表,以此提升Q-Learning前期回报与探索能力。文中在OpenAI的Gym环境中验证了DE-Q-Learning方法的有效性,并进一步在复杂迷宫环境和强化学习环境Pacman中实验了其在复杂路径搜索和动态避障问题上的性能。实验结果表明,DE-Q-Learn-ing在Pacman环境中相比于改进算法Double-Q-Learning和SA-Q-Learning不仅在历史回报方面具有明显优势,而且收敛速度分别提升了42.16%和15.8 8%,这表明DE-Q-Learning能够显著提高历史累积回报和算法的收敛速度。关键词:强化学习;差分演化
3、;Q-Learning;Q表中图号:TP273Improved Q-Learning Method with Differential Evolution(School of Computer Science and Engineering,Xian Technological University,Xian 710021,China)Abstract:In response to the slow convergence and low return resulting from the limitations of Q-Learning algorithms when applied in
4、 path search,this paper proposes a path search method calledDifferential Evolution Q-Learning(DE-Q-Learning)that improves Q-Learning by optimizing Q-table.The proposed algorithm leverages the global optimality of the differential evolution algorithm,selectingan evolving population composed of Q-tabl
5、e individuals with excellent initial values through mutation,crossover,and selection operations to enhance the Q-Learning payoff and exploration ability.Firstly,theeffectiveness of the DE-Q-Learning method was verified in the Open AIs Gym environment.And thenits performance in complex path search an
6、d dynamic obstacle avoidance was further tested in a complex文献标志码:Aby Optimizing Q-TableLI Xiao,CAO Zijian,JIA Haowen,GUO Ruiqi文章编号:16 7 3-9 9 6 5(2 0 2 3)0 4-0 36 9-0 14*收稿日期:2 0 2 3-0 3-15基金资助:基础加强计划技术领域基金项目(2 0 2 1-JCJQ-J0513)。第一作者简介:李骁(19 9 8 一),男,西安工业大学硕士研究生。通信作者简介:曹子建(19 7 8 一),男,西安工业大学副教授,主要研
7、究方向为演化算法、机器学习、网络安全,E-mail:。引文格式:李,曹子建,贾浩文,等.一种差分演化Q表的改进Q-Learning方法 J.西安工业大学学报,2 0 2 3,43(4):36 9-38 2.LI Xiao,CAO Zijian,JIA Haowen,et al.Improved Q-Learning Method with Differential Evolution by Optimizing Q-TableJJ.Journal of Xian Technological University,2023,43(4):369-382.370maze environment an
8、d in the reinforcement learning environment of Pacman.The experimental resultsshow that DE-Q-Learning has notable advantages in historical returns over the improved algorithms(Double-Q-Learning and SA-Q-Learning)in the Pacman environment,with its convergence speedincreased by 42.16%and 15.88%,respec
9、tively.These findings indicate that DE-Q-Learning caneffectively enhance the historical cumulative return and accelerate the convergence speed.Key words:reinforcement learning;differential evolution;Q-Learning;Q-Table路径搜索是人工智能领域中的一个重要问题,涉及到诸如自动规划、运动控制、资源分配、游戏策略等诸多应用场景。在路径搜索问题中,通常需要在状态空间中找到一条最优路径,以满足
10、某些约束条件或优化目标。针对不同的问题,可以采用多种搜索算法进行求解,目前已有的路径搜索算法有很多,例如人工势场方法 1、蚁群算法 2 等,但这些传统搜索算法在实际应用中面临着挑战和限制。而强化学习类型的方法能够自主探索未知环境模型,以提高路径搜索问题的求解效率和精度,故该方向成为了近年来的研究热点。强化学习(Reinforcement Learning,RL)作为人工智能领域的一个重要分支,已经得到广大学者的高度认可,在解决序贯决策问题上,强化学习采用马尔可夫决策过程的方式,智能体通过与环境交互得到经验集于当前状态进行决策3。而Q-Learning作为一种经典的无模型强化学习方法 4非常适合
11、求解有限空间的路径搜索问题,其收敛能力主要取决于智能体对环境信息的探索与利用。而在优化Q-Learning探索能力方面,不同研究人员提出了多种改进方法。文献 5 引人了探索因子和深度学习因子来提高算法的探索效率,但忽略了算法的可拓展性和稳定性;文献 6 通过势场优化Q表初值,并采用多步长策略和动态调节贪婪因子来平衡探索与利用,但未考虑动态障碍物的避障策略;文献 7 提出了使用平均奖赏和相对值函数的值迭代方式来加速收敛,但计算复杂度较高且对奖励信号不敏感;文献 8 将资格迹概念融人Q-Learning中,提出了Q(a)-L e a r n i n g 算法,减少了Q值的计算量,但缺乏实验验证;文
12、献 9 提出了DoubleQ-Learning算法,通过使用两个估计器分离最优动作和最大Q值的选取,改善了收敛速度;同样,Speedy Q-Learning(SQ L)和 DoubleSpeedyQ-Learning也对Q值的更新方式进行了改进,提高了收敛能力 10-11,但这些方法通常需要更西安工业大学学报长的训练时间;除此之外,许多学者考虑Q-Learn-ing与演化算法结合优化的模式,将演化算法的思想融入Q-Learning中,并从多个角度对算法存在的问题进行了优化。文献 12 提出了一种结合退火算法(Simulated Annealing)中的Metropolis 准则的Q-Learn
13、ing改进算法(SA-Q-Learning),利用模拟退火的思想对的取值进行线性控制,从而保证算法更加快速找到最优策略,但并未发挥出演化算法的优势。文献13为了解决不确定性的POMDP近似最优解问题,在基于 SA-Q-Learning算法的基础上提出了一种有限步历史信息与状态信度概率分布相结合,提出了一种直接进化策略的新算法(MA-Q-Learning),该算法提高了算法的收敛速度,但存在Q值过估计的问题。在实际工程应用中,文献 14 针对虚拟作业中存在的不确定性问题,提出了一种遗传算法(Genetic Algorithm,GA)结合Q-Learning算法进行最优策略选择的策略规划模型(GA
14、-Q-Learning),该模型有效地避免了早期较大的Q值动作,但该模型鲁棒性较差,无法有效地解决行为空间较少的问题。上述改进算法能够提高Q-Learning算法的性能,但均未考虑Q-Learning算法在初始化时的盲目性,这会导致Q-Learning算法在前期路径搜索中长时间地无效探索,影响算法的收敛速度和平均回报。基于此,文中提出了一种利用差分演化(Differential Evolution,DE)算法对Q表进行优化来改进Q-Learning收敛能力的方法DE-Q-Learn-ing。该方法利用演化算法优化Q表的初始化,解决了Q-Learning算法在初始环境中的盲目性问题。通过使用差分
15、演化算法推动Q表的进化,DE-Q-Learning在时间和空间上提高了算法的探索效率。最后在复杂迷宫环境、实验环境Pacmman游戏和OpenAI的gym工具包中MountainCar上进行了仿真实验,实验结果显示DE-Q-Learning算法相比于Q-Learning及其改进算法具有优异的性能,并且能够在更短的时间内快速收敛。第43卷第4期1基础理论1.1Q-LearningQ-Learning是一种基于时序差分的无模型学习方法,其Q-Learning的核心是Q表,Q表的行和列分别表示State和Action的值,用Q表的值Q(s,a)来衡量当前状态采取动作a的价值,所以Q-Learning
16、只考虑当前状态s以及当前状态选择的行为,使Q(s,a)值最大即可,智能体采用Q-Learning算法与环境交互如图1所示。UpdateQ-tableQ(s,aQ(s,aQ(si,)Q(s,aQ(s,a)Q(s,a.)Q(smaQ(sma.)Q(Sma.)Q(State,Action)StateQ-valueActionaObervation(State)图1Q-Learning算法与环境交互过程Fig.1 Interaction between Q-Learning algorithmand environment通过这种局部映射的方式,无需充分地计算全局信息,只需通过局部选择的方式便可获得全
17、局最优动作序列,进而使智能体获取最大目标收益。Q-Learning的算法伪代码如算法1所示。算法 1 Q-Learning 伪代码初始化环境E,状态空间S,动作空间A,折扣因子,Q表Q-table初始化行为值函数Q(s,)=0,(a|s)=1A最小化问题。Fork=O,l,m do#agent的每条完整路径min f()初始化状态:s.t.aE Q E RDFor t=0,l,2,3,do#agent 的每一个训式中:D为目标解空间的维数;2 ERD则为可行解练步集。DE算法关键步骤为通过贪心策略of元在环境E中采取动作AStep1:变异r,s=Step(A)#执行下一个动作A产生0,=+F.
18、(ch2一r3)。奖励r和下一个状态s对于变异算子的设定,通过在t代随机取样三Q(s,a)Q(s,a)+r+maxQ(s,a)-个不同个体1,2,3来执行变异操作;F作为Q(s,a)#更新Q表Q-table变异因子,用来调控变异程度,代表第t代生成的变异个体。李骁,等:一种差分演化Q表的改进Q-Learning方法Q(s,a),式中:s为当前状态;为当前状态s所采取的动作;为学习率;r为在当前状态s下执行动作所得到的立即回报。为折扣因子,用来控制将来累积回报对当前状态所产生的影响。s表示当前状态s采取动作到达的后续状态,为在状态s下选择的动ChooseAction作,然后用新的Q值去更新Q表。
19、AgentQ-Learning分别采取两种不同的策略来进行介Q(s,aiQ(si,Q(s,aQ(s,a.)Q(ss,aQ(sm,a.)RewardAction=argmax(Q(State,Action)Chagne theActionEnvironmentEnvironment371end for s is terminatedend for元(s)=a r g m a x Q(s,a)#根据Q表更新策略Q-Learning 的状态行为值函数更新为Q(s,a)Q(s,a)+r+maxQ(s,a)-(1)Q(si,a)策略评估和更新。在策略更新上Q-Learning采用Q(s,a)Q(s.a)
20、贪心算法来选择动作,在更新Q表时则采用贪心算法,通过下一个状态的最大Q值来更新当前状态的值。而在动作选择中,Q-Learning采用贪心算法,其主要思想是在探索的同时也能同时进行一定的利用。在行为选择时采用的-贪心算法,其中值越大则探索的效果越好。反之,若值越小则更加注重利用。但正因为其取值的固定,往往不能更好地平衡其探索和利用的效率,取值的不合理同时也会使得算法的搜索效率大幅度下降,在实际案例中一般在 0,0.1 区间内取值。1.2差分演化算法差分演化(DE)算法自19 9 6 年由文献 15提出后,在解决优化问题上有着广泛的适用性。DE算法在遗传算法的启发下提出,其思想与传统演化算法保持一
21、致,主要由变异、交叉、选择这三个步骤所组成,在解决NP(Nondeterministic Polynominal)难问题上有着良好的适用性。对于求解以下形式的(2)(3)372Step2:交叉Ui.,if A U B一ci.j,otherwise其中,令 A为条件 rand(j)CR”,B为条件 j=random(i),且j=1,2,D,其中 rand(j)表示生成一个在 0,j)范围内的随机整数或随机浮点数,而random(i表示生成一个在O,i)范围内的随机浮点数,CR为交叉因子,u代表第t代经过交叉操作生成的个体。Step3:选择Jutiif(f(ult)f(i.,)通过选择操作将适应度
22、值较好的个体进行保留,并作为下一代种群的初始值。2演化优化Q表的改进Q-Learning方法马尔可夫模型作为强化学习与演化算法共同的理论基础,其定义如下:通过创建一个五元组并结合Bellamn方程构成一个基本的马尔可夫决策过程(MDP)问题模型,其中五元组中的元素分别表示为:S(有限的状态空间),A(有限的动作空间),P(状态-动作转移概率矩阵),R(奖励函数),(折扣因子)。MDP动态过程如图2 所示,智能体初始状态为So,从合法状态集A中挑选一个动作执行,得到回报ro,然后按照一定概率随机转移到下一个Si状态,如此往复直到到达终止状态。在这个过程中不同的状态动作影响着最优策略的搜索进度,因
23、此,可以使用演化算法来优化存储状态动作对的Q表,以加速Q-Learn-ing寻找最优策略的效率。演化算法由于其固有的并行性,能够不受问题性质的限制,有效地解决传统优化问题难以处理的复杂问题,加快了策略搜索速度。从而能够有效缓解Q-Learning在环境信息匮乏的情况下的盲目搜索性问题。S.S2aa2图2 MDP结构Fig.2The structure of MDP西安工业大学学报2.1时间复杂度分析(4)Q-Learning作为一种无模型算法,样本复杂性T决定了其时间复杂度O(T),空间复杂度O(SAH)更多取决于状态和动作的空间大小。其中S代表状态空间大小,A代表动作空间大小,H则表示为每一
24、次执行所走的步长 16 。而在解决无模型问题上,Q-Learning在已知状态空间和动作空间的前提下,如何有效地利用环境信息是提升算法收敛能力的关键。随着模型环境复杂度的提升,不仅状态、动作对的数量增加,而且智能体在每次探(5)索时所需的步长H也会随之增加。由此可以看出,环境信息对算法的运行效率起着至关重要的作用。演化算法作为一种解决复杂问题的有效手段,可以用于解决强化学习在算法初期的盲目探索性问题。DE具有较低的时间复杂度O(NP-D-Gmax)17-20,其中NP代表种群大小,D表示维度,Gmax为算法最大运行代数。对于复杂无模型问题,若将状态行为值函数Q作为NP的输人,S作为D的输入,步
25、长H则在搜索空间进行了提升。每当演化算法生成一代Q表种群作为NP输入时,步长H在空间上则扩展为NPH,由此便提高了算法的执行效率。由于DE算法具有控制参数少、收敛速度快、寻优精度高及鲁棒性强的优点,因此文中选用DE作为演化算法实例。当然任何其它演化算法都可以作为实例算法来对Q-Learning进行优化,文中主要侧重于DE-Q-Learning算法的原理。2.2算法的局限性在Q-Learning算法运行初期,Q表参数的初始化会导致采集到的数据往往是未经训练的样本集。如何更加有效地提升算法的执行效率,更多程度取决于算法前期的探索能力。另外,在算法前期的探索阶段,所获取到的立即回报值不一定对算法训练
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 一种 演化 改进 Learning 方法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。