基于神经动态规划算法的最优路径选择探讨.docx

基于神经动态规划算法的最优路径选择探讨神经动态规划算法在处理复杂的决策问题时非常有效它可将我们所遇到的问题分成若干子问题然后再寻找每个子问题合理的处理方法最后从这些子问题的处理方法中找到以前问题的最优处理方法。在最优路径选择问题中通过Matlab仿真得出神经动态规划算法比传统方法更容易找到答案使运行效率得到了提高。【关键词】神经动态规划最优路径子问题Matlab仿真为了减轻交通压力人们越来越关心交通系统的智能化进程。智能交通系统主要的研究方向之一就是动态路径诱导系统它可根据外出的人们的需求为驾驶员提供最新的路况信息和最佳路径选择以此避免交通拥堵现象的发生从而优化交通状况最终使交通时时地保持一个合理的动态分配。目前最优路径选择的方法有很多但是真正需要解决大型问题时计算机需要搜索的选择范围太大传统的动态算法基本上无法处理。1995年神经动态规划算法被提出该算法把复杂的问题分成若干子问题这些子问题被拆分后更容易解决使计算过程大幅简化且更容易被计算机处理。采用这种方法可准确、快速、实时、稳定地选择出最优路径值得推广。1神经动态规划概述与核心思想在解决多阶段决策问题时动态规划大致思想为：将非常繁琐的原始问题分解为若干个阶段这些阶段看似不相关却是相互联系的子阶段在找到上一阶段的解决方法以后才能处理下一个阶段依次求出每个阶段的解最后得到全局最佳的解。多阶段决策问题具备很强的顺序性同时每个阶段所使用的解决方法也是随着阶段的变化而变化所以“动态”意义就得以体现。其中交通网中最佳路径的求解就是典型的多阶段决策问题。在路径优化中动态规划是一种非常经典的计算方法但在处理实际问题的时我们肯定会遇到缺少一个完整信息或者维数灾等一系列问题所以引进神经网络对动态规划具有较大的解决实际问题的意义。神经动态规划如图1所示。2基于神经动态规划算法的最优路径实现（1）将原来的问题分解成很多个小问题即子阶段并且找到每个子阶段的最优解决办法。求解多级问题的步骤为：根据每个问题的特点划分子阶段。在划分子阶段时必须按照一定的规则比如根据执行决策的时间、空间的顺序等。本文用x来表示子阶段变量。（2）求解状态和状态变量。每个子阶段具体的起始位置可以依靠自然状态来指导其中客观条件阶段性数目的状态是自然状态中的一种它传达每个子阶段的关键信息此外一组或者无后效性的变量同样可以用来表示状态变量。本文用Hx来表示第x级的状态变量。（3）求解原问题决策变量和集合。从目前阶段到下一个阶段状态选择时决策者需要做出恰当的决策决策变量的范围称为集合。本文用Dx表示决策集合用Ux表示决策变量。（4）研究状态转移的方程。假设状态转移方程是：Hx+1=Tx（HxUx）。次方程式中Tx不定根据具体问题才能确定如果Hx确定一旦变量Ux确定那么第x+1阶段状态变量（Hx+1）也将确定。（5）研究指标函数。因为n和vi的递进性和可分离性所以很容易找到指标函数n和vi之间的关系显然指标函数的求解也相对简单化。（6）动态规划函数的基本方程。边界条件为；第x-m阶的最优动态规划函数是。3仿真结果将上述模型在Matlab仿真软件上进行模拟仿真分解原始问题并确定各个子阶段的最佳方案将这个问题用网格的形式如图2进行表示：A为起始地点E为目标地点从起始地点到目标终点有很多路径假设经过每个节点需要一定的运输成本在Matlab仿真软件上进行仿真后依据动态规则算法的要求设定好相应的算法模型以及相应的计算公式这样便可以找到最优路径。由图2可以非常清楚的看出成本最低的路线为：或者或者成本都是110。仿真结果可以看出神经动态规划算法具有较多优点：得到清晰运算结果；很容易找到全局的最优路径；可以找到一组完善的解有利进一步的分析。4结语我们在使用神经动态规划算法来探索最优路径的时候具有很多优势首先其具有稳定、可靠的步骤过程并不复杂但是给予我们的结果十分清晰明确且适用于现实生活。使用这种动态规划算法解决复杂的问题时可以非常容易找到解决方案而且效率很高。当然该算法也有一定的局限但只要我们不断地改进完善日后继续研究神经动态规划算法相信一定可以攻克更多的局限能够使其更好地被应用。参考文献[1]谬慧芬邵小兵.动态规划算法的原理及应用[J].中国科技信息2006（23）：32.[2]杨琰廖伟志李文敬杨文李杰.基于Petri网的顾及转向延误的最优路径算法[J].计算机工程与设计2013（10）.作者简介杨超（1994-）男广东省吴川市人。现在就读于长沙理工大学计算机科学与技术系。