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

第 2 9卷 第 1 期 2 0 0 9年 2月 桂林工学院学报 J o u rna l o f Gu i l i n U n i v e r s i t y o f T e c h n o l o g y V o L 2 9 No 1 F e b 2 0 o 9 文章编号 1 0 0 6 5 4 4 X 2 0 0 9 O 1 0 1 5 4 0 4 基于神经动态规划算法的最优路径选择 李 菲 肖洪祥 桂林工学院 电子与计算机系 广西 桂林5 4 1 0 0 4 摘要 针对传统动态规划算法在计算大规模路网的优化问题时所表现出来的计算时间长 存储空间 大等缺点 引入了一种神经动态规划算法 它将传统的动态规划和 B P神经网络结合起来 通过逼近 Q学习算法来寻求一种最优策略 最终达到路径优化的 目的 将此算法应用于一个交通路网 且用 M a t l a b 软件进行仿真 试验表明 该方法的实时性 并行性和全局性都优于传统动态规划 在城市交 通流系统中能切实起到路径诱导的作用 关键词 神经动态规划 最优路径 神经网络 逼近 Q学习 中图分类号 T P 1 8 3 U 4 9 1 文献标志码 A 为了缓解交通压力 智能交通系统 I T S 越来 越受到社会各界的关注 动态路径诱导系统 D R G S d y n a m i c r o u t e g u i d a n c e s y s t e m 是 I TS 的重要研究 内容 在国际交通研究上属于前沿领域 D R G S 根据 出行者的要求 向驾驶员提供实时交通信息和最优 路径诱导 通过路径诱 导来改善交通状况 防止交 通阻塞 最终实现交通流的合理动态分配 迄今为止 关于最优路径选择的算法 已经有很 多 如遗传算法 蚁群算法 模拟退火 动态规划等 但在求解一些大规模问题时 由于需要搜索的状态 空间太 大 传 统 的动 态规 划 很 难解 决 1 9 9 5年 B e r t s e k a s 和 T s i t s i k l i s首次提 出了神经动态规划概 念 通过对 系统 自身 的优化 解决 了大量的 维数 灾 问题 目前 已成功应用 于十五子棋 组 合优 化 电梯调度等问题 J 笔者将这种方法应用 于动 态路径选择系统中 在满足出行者要求的基 础上 准确 快速 实时的选择出最优路径 1 神经动态规划 动态规划是解决多 阶段决策过程最优化 问题 的一种方法 它把 比较复杂 的问题划分为若 干阶 段 然后通 过逐段求解 最终获得全 局最优解 多阶段决策问题具有很强的时序性 同时在各阶 段中所采取的决策也是随阶段而变动的 这就包 含了 动态 的意义 而交通 网中的最优路径选 择正是这样一个典型的多阶段决策问题 其 动态 规划的基本算法如下 按时间反向运行 对于每一个初始状态 基本 有限范围问题的最优代价 i i 且 i m in E g i i i 1 l i 1 i g 若策略 使得 i 对于任意 I 和i 为最小 那么策略7 r t o 二 是最 优的 虽然动态规划对于路径优化是很经典的算法 但应用到实际环境 中时 常会 遇到维数灾或缺乏 完全信息等问题 因此在动态规划 中引用神经网 络是极具实际意义的 神经动态规划是一种增强式学习的现代方法 它使一个系统通过观察 自身的行为来学会怎样做 出好的决策 并且使它能通过增 强式嵌入机制以 改进自己的行动 它把动态规划和神经网络结 合起来为需要规划的行为提供强有力的解决方案 收稿 日期 2 0 0 8 0 5 2 8 基金项目 广西教育厅科研项目 桂教科研 2 0 0 7 0 1 L X 3 3 6 作者简介 李菲 1 9 8 3 一 女 硕士研究生 研究方向 人工智能 神经网络 E m a i l l i f e i 0 7 3 9 2 0 0 1 s i n a c o m 通讯作者 肖洪祥 男 高级工程师 E m a i l x h x g l i t e e d u c n 第 1 期 李菲等 基于神经动态规划算法的最优路径选择 1 5 5 图 1中说明动态规划 为其提供理论基 础 络则为其提供学习能力 维数灾 神经动态规划 神经 网络 图 1 神经动态规划框图 Fi g 1 Di a g r a m o f n e u r o d y n a mi c p r o g r a mmi n g 神经 网继状态 2 3 逼近 0学习算法求解 2 最优路径的实例分析与算法实现 2 1 最优路径的选择 图 2所示为一交通路 网拓扑结构 图 中带箭 头的边线表示来 回路段 圆点表示交叉路 口节点 假定一出行者计划从节点 1到 l 0 以出行 时间最 短作为最优 目标 那么将如何选择 一条用时最短 的路是本文需解决 的问题 图 2中还 给 出了每条 路径时间策略的代价 即边线上的数字 出行者 将要选择的路线都是基于对该路线 时间代价 的评 估 搜索到具有最小时间代价 的路径时给予保 留 其余须舍弃 图 2 路 网拓扑结构 图 F i g 2 To p o l o g yma p o f r o u t e n e t wo r k 2 2 构造 0因子 Q因子的概念是 Wa t k i n s 于 1 9 8 9年提出来 的 对于任意状态行动对 f a Q i 口 c i 口 r 口 口 g a l J 任意的行动都须通过它来排序 上述路网是一个缺乏转移概率 完全可观察的 M a r k o v 链模型 j 可以构造其 Q因子的随机模式 并通过 B P神经网络得到它的另一个等价形式 Q i 口 g i a j r m i n Q j J 为 后 在神经动态规划过程 中 一 般有逼近策略迭 代和逼近 Q学 习两种方式 逼近策 略迭代是一 种 目标性很强的迭代算法 虽然 它使用神经网络 解决了维数危机 但这种 系统模 型是建立在已知 状态转移概率 p 口 和观察代价 g f a J 的基础 上的 由于上述 的路 网模 型 明显缺 乏转移 概率 因此笔者采用逼近 Q学习算 法来寻找最 优策略 并通过 B P神经 网络来实现函数的逼近 初步设此 B P神经网络有 2个输入节点 l O个 隐藏 神经元和 1个输 出神经元 网络结构 如图 3 所示 其 中一 个输入节点代表状态 另一个代表 从 当前状态到下一状态所采取的行动 杯 输出表示 网络计算 出来的 Q值 其算法流程如下 在 B P学 习的前 向通路 中先确定初始 权值 通过神经网络完成逼近 确定 目标 Q因子 即网络 的 目标 响应 Q 蚪 i a g i a r m i n Q i q 是 i 的后继状态 r 为折扣 因子 g a 为在行动 a的 作用下从状态f 到状态J 的代价函数 在最优路径策 略中 目标 Q值中的代价函数应为最优 状态 一行动对 f a 输入到神经网络 产生 实际响应 Q a w 把实际响应与目 标响应进行比较 产生误差 信号 误差信号反 向传播经过网络 在 B P 学习的反向通路中 轻微调整权值使 Q f 口 无限靠近 Q f a 直到 I Q f 口 一 Q f a w l s 算法结束 否则继续迭 代 其 中权值向量通过学习率参数 局部梯度和 当 前神经元的输入信号来校正 己 可见 权值向量 的微调在此算法中是一个 很重要环节 它关系到网络输出 Q值和目标 Q 值之间的误差 误差信号通过误差修正学习对神 桂林工学院学报 2 0 0 9 年 经元的权值进行步步逼 近调节 使 网络输 出的 Q 值逐渐向目标 Q值靠近 下面就两个不同的层次 进行分析 输出层 当神经元 处于输出层时 误差信号 e r 极易获得 e j n Q 7 蚪 J b 一Q U b l 由 D e l t a 法贝 可知 n n y 凡 贝 0 r t 1时间步时 n 1 W j i 凡 W j i n 隐藏层 当神经元J 处于隐藏层时 e r t 就 很难确定 它必须根据所有与其直接相连的神经元 的误差来递归决定 因此需要重新决定神经元的局 部梯度 定义局部梯度 分体现其实用价值 n 竹 w 则 F j g 4 n 6 n Y n 叩 n n Y i n 叼 n 几 6 n 蚵 n 逼近 Q学习算法在算法 的每一次迭代 中都支 持单个状态行动对的 Q因子 它并不是直接计算 最优策略 而是根据各种代价首先计算出迭代时 状态 i 的 c o s t t o g o函数 的最优集合 然后把该集 合的贪心策略作为最优策略 当所 有 口 的 学 习率 参 数 1 a 满 足 f 口 和 2 i 口 这两 个条 件 且迭代步数 n趋于无穷大时 由逼近 Q学习算法产 生的所有状态行动对 f a 的 Q因子序列 Q f a 将以概率 l 收敛于最优 Q值 Q f a w 在路 径优化问题中表示为状态 f 在时间步 n时的最优行 动 口 即口 m i n Q i a w 当最优行动 a 从 当 前状态到 目标状态都得以实现时 就可以获得一个 最优策略 这就是最优路径 2 4实验结果分析 采用 M a t l a b软件对 图 2中的路 网模 型进行仿 真实验 设 B P神经网络的学习参数 为 0 0 2 且 忽略其动量 仅 为了检验基于神经动态规划 的最优路径选择 算法在计算时间上的优越性 对多个 O D o r i g in d e s t i n a t i o n 对分别使用神经动态规划 和传统动态 规划来计算最优路径 图 4 由图 4可见 神经 动态规划 的计算 速度 在路 网节点 数越来 越 多时 如 2 0个节点时 会 明显优于传统动态规划 充 增强式学 习算法的性 能可通过算法的收敛性 和算法的收敛 速度这两方面来判定 从图 5中可 以看出 当迭代次数达到 7 0 0 0次后 算法就出现 收敛的趋势 在经过近万 次的迭代后 系统的误 差接近于 0 即可认为系统已经很好地收敛了 0 8 0 6 一 吾 o 4 0 2 O 0 2 0 4 0 6 0 8 1 0 迭代次数 1 0 次 图 5 迭代收敛图 Fi g 5 F i g u r e o fi B P神经 网络 在本质上 可以看作是 函数逼 近 器 大量的研究表明只要 在隐藏层 中有足够数量 的神经元 网络就可以被用来逼近几乎任何一个 的函数 但有时网络的响应不能精确地逼近所期 望的函数 这是因为网络的能力受到了隐藏神经 元数目的影响 图6 显示当隐藏神经元为5或9 时 都不能很好的逼近目标响应 当隐藏神经元为 l 0 时则能较好的逼近 所以在隐藏层中设计 1 0个神 经元是完全可行的 以出行时间最短为 目标 采用神经动态规划 算法分别求解不同 O D对间的最优路径 其部分结 果如表 1 所示 第 1 期 李菲等 基于神经动态规划算法的最优路径选择 l 5 7 图 6 隐藏神经元对 函数逼近的影响 Fi g 6 I mp a c t o f a p p r o x i ma t i o n f r o m t h e h i d i n g n e u r o n s 表 1 部分 OD间的最优路径 Ta b l e 1 Op t i ma l p a t h o f OD 由表 1可见 尽 管 出发点 和 目的地都 相 同 但如果其行驶方向不一致时 最优路线 也有可能 不一样 驾驶员可按不 同的行驶要求来搜 索最佳 路径 3 结论 神经动态规划是动态规划与神经网络相结合 的一种新型智能搜索方法 本文将其应用于智能 交通系统的路径优化 问题 中 实例证 明是有效可 行的 但为了保证逼近 Q学习算法 的收敛精度与 速度 仍需进一步讨论神经 网络 中各种参数变化 问题 参考文献 1 孙海鹏 翟传润 战兴群 等 基于实时交通信息的动态 路径规划技术 J 微计算机信息 2 0 0 7 2 3 8 1 7 7 1 7 8 2 金辉宇 于海斌 神经元动态规划综述 J 信息与控 制 2 0 0 1 3 0 4 3 4 3 3 5 1 3 郭跃 彭军 吴敏 增强 Q学习在非确定马尔可夫系统 寻优 问题中的应用 J 计算机工程与应用 2 0 0 5 4 1 1 3 3 6 3 8 4 唐吴 奚宏生 殷保群 M a r k o v控制过程基于神经动态 规划的优化算法 J 中国科学技术大学学报 2 0 0 1 3 1 5 5 4 9 5 5 7 5 王颖 基于仿真 的可重人生产系统的神经元动态规划调 度研究 D 厦门 厦门大学 2 0 0 7 6 蒋国光 吴沧浦 基于 Q学习算法和 B P神经网络的倒立 摆控制 J 自动化学报 1 9 9 8 2 4 5 6 6 2 6 6 6 7 H a y k i n S N e u r a l N e t w o r k s A C o m p r e h e n s i v e F o u n d a t i o n S e c o n d E d i t i o n M N e w Y o r k P r e n t i c e H a l l 1 9 9 9 Opt i ma l Ru t e Ch o i c e Ba s e d o n Ne ur o Dy na mi c Pr o g r a mmi ng LI Fe i XI AO Ho ng x i a n g D e p a r t m e n t o f E l e c t r o n i c a n d C o m p u t e r S c i e n c e G u i l i n U n i v e r s i t y of T e c h n o l o g y G u i l i n 5 4 1 0 0 4 C h i n a Ab s t r a c t Ne ur o d y n a mi c p r o g r am mi n g i s i n t r o du c e d t o d e a l wi t h t r a di t i o n al d y n a mi c p r o gra mmi n g wi t h l a r g e s t o r a g e s p a c e a n d l o n g c o mp u t i n g t i me f o r o p t i ma l r o u t e i n a g i g a n t i c t r al c n e t wo r k B y s y n t h e s i z i n g t h e d y n am i c p r o gra mm i n g a n d B P n e u r a l n e two r k t o s e e k a n