动态规划的单增量搜索算法

第 4 卷第 1期 l望巧. 3 运落与, 理 OPI 琅A 刀0 卜6 R] 图E A R CH AN D MA N A G E州正不汀 SC IE 刊rC卫 V 匕1 .4 Nb . 1 M肚 .l卯5 动态规划的单增量搜索算法 俞嘉第 陈继先 曾新云 (合肥工业大学系统 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 研究所 安徽合肥 2加朋匀 摘 要 本文首先对现有的三种动态规划迭代算法 : 徽分动态规划 、渐进优化算法 、状态增 t 动态规划作了简单评述 . 针对如何进一步减少计算工作t 和加快收救速度 . 提出单增 t 搜索算 法 . 通过理论阐述和实例分析 , 说明这种新的迭代算法优于上述三种常用方法 . 最后 , 本文把这 种方法推广到连续型动态规划间题 . 关 . 词 动态规划 ; 状态增t ; 单增t 搜索 O 引 言 与庞特里亚金极大值原理一样 , 动态规划最优性原则能有效地解决动态系统的最优控 制问题 . 动态规划算法原理直观 、计算机编程简单 , 人们在解决工程 、经济中的多阶段决策 过程问题以及可转化为多阶段决策过程的最优控制问题时 , 均可求助于这种方法 . 然而 , 随着对计算精度要求的提高和状态变量 、决策变量维数的上升 , 计算机内存容 量的不足和计算时间的增长均成为解决这类问题的极大障碍 . 这就是所谓的动态规划维数 灾 . 多年来 , 人们在解决这个间题方面做了大量 的研究 . 我们于 19 83 年研究我国南水北调 东线工程运行最优化问题时 , 针对离散时间多维动态规划问题 , 提出一种新的算法 , 名 为单 增量搜索算法 . 多年来在不少水资源优化利用的课题中应用了这种方法 , 实践证明在减少 计算步骤 , 节省计算时间方面比较有效 . 1 常用的解法 为了克服动态规划维数灾 , 拓宽动态规划的应用范围 , 已提 出的有效方法主要有如下三 类 : 微分动态规划 、渐进优化算法 、 状态增量动态规划 . L l 微分动态规划111 微分动态规划是为了解决多维动态规划和非线性二次型 目标函数连续最优控制问题而 提出的一种算法 。 这种算法的基本思想是设定一个标称决策序列 {xt }及其相应 的标称状 态轨迹{s k }, 由于状态 s ‘可在点 s、的邻域内变动 , 所 以把最优价值函数 F、(s k)在此邻域内 展成 Ta lo r 级数 , 略去其高阶项后代人动态规划基本方程 , 得出该级数的系数的递推关系 , 运筹与甘理 19外 年第4 卷(一) 然后 , 以标称状态轨迹为起点 , 逐次通近最优状态轨迹 , 得出相应的最优策略 . 此法大大减少了计算工作量和计算机的存贮盆 . 其不足之处是最优价值函数 Ft 侣J 必 须有良好的解析性质 , 使之可以用 T al o r 级数展开 , 而且程序设计较为复杂 . 12 渐进优化算法门 这是由 H o 职心o n 和 S a n比。提出的解决凸性约束条件下 多阶段决策的算法 . 它不同于 微分动态规划 , 不是从标称决策序列与标称状态轨迹着手 , 而是固定当前状态的前后状 态 , 在当前状态满足约束条件下 , 对目标函数求优 , 以此确定 当前最优状态 . 如此逐次求 优 , 即可得到本次迭代求出的状态轨迹 , 再以该轨迹作为新的初始迭代轨迹 , 重复以上过 程 , 直至达到规定精度 . 这种方法的优点是状态变量无须离散化 , 所以能得到较精确的全局最优解 . 但是 , 由于 每次迭代过程中 , 状态轨迹的取得是通过寻优求出的 , 且迭代次数较多 , 因而需要大量的计 算时间 . 13 状态增且动态规划日 状态增量动态规划方法的主要 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 是在状态可行域 S 内选定一个状态序列 {s , }作为初 始轨迹 , 然后应用变分原理 , 在状态可行域内对标称轨迹作上下变动 , 即加及减一个或几个 增量 , 形成上下状态增量轨迹 {s , 土占‘}, 再利用动态规划递推方程推求各轨迹所构成的网络 中的最优状态轨迹 , 然后以此作为新的初始轨迹 , 进一步求优 , 直到取得满意的精度 . 显然 , 这种方法原理清晰 , 编程简单 . 但是 , 其状态增量值伙}的选择具有较大的 随意 性 , 影响了收敛速度 , 而且这种方法对维数灾的克服没有上述方法有效 . 2 单增量搜索解法的原理 微分动态规划能降低维数灾的影响 , 渐进优化算法不仅能降低系统的维数灾 , 而且能取 得全局最优解 . 但它们的共同不足是迭代过程复杂 , 计算时间长 . 状态增量动态规划 方法 概念明了 , 迭代简单 , 但对维数灾的限制不甚有效 . 本文综合上述三类方法的优点 , 提出了 一种动态规划的单增量搜索解法 (以下简称搜索解法 ) . 2. 1 搜索解法的原理 单增量搜索动态规划 的基本思想是 : 在状态可行域 S 内选定一个标称状态向量序列 {S尸 lk = 0 , l , ⋯ , N }作为初始轨迹 , 由此取单向增量 {占‘}, 使{s尹+ 司k = 。, 1 , 一 N }‘s , 其中各状态分量 s礴 = 1 , 2 , ⋯ , m) 的增量值 占‘ 由进退搜索法 闷 确 定 . 然后在初始轨迹和增量 轨迹构成的广义单边状态廊道 中 , 运用动态规划最优化原则推求一个改进的状态轨迹 {s产 Ik = o , 1 , 一 研 。 再以此轨迹作为初始轨迹 , 重复上述迭代计算 , 直到求得满意解 (近似最优解 ) . 为了阐明这一算法 , 图 1 以一维状态问题为例 , 表示出初始状态轨迹 毛s、助}k = o , l , 2 , ⋯ , N }= {s。, s 卜 5 2 , 一 s N }。 图中状态维数 m 二 l, 每一阶段有 r 一 1 = 1 个增量 , 组成 r’n = 2 , = 2 个状态点 , 每个状态点 可有 严 = 2 个决策 (状态转移 ) , 故每一阶段须作 产 = 2 , , ’= 4 次计算 。 第 1 期 俞嘉第等 : 动态规划的单增童搜索算法 阶段 1的可行决策 xl 状态增t 执进演道边界 ) s : + 。: 1 , 尹卜、 , 态状s S2 + 入 气 + 人 53 + 占3。 几 一扩可一 ’‘、 改进后状态轨迹匆” 、 阶段 k 2. 2 动态规划模型及搜索解法 设多维多阶段决策模型为 : (l) -叫(3)M in艺又侣, , 长 , k) g k(S k , S卜 , , 凡)簇 o k = l, 2 , ⋯ , N S 。、 S 、 给定 式 中 : k 为阶段数 ; S k = (s k . , s 、2 , ⋯ , 气J 为第 k阶段 m 维状态向量 ; 长 = (xt . , 、 , ⋯ , 、。)T 为第 k 阶段 n 维决策向量 ; vt 为价值函数 (标量函数) ; ‘ = 德kl , & 2 , 一 & J 为矢值函数 , 表示约束条件 、 状态转移 、 s , 和 凡 的关系等 .动态规划的基本递推方程为 F邓‘)= M i川y‘侣‘ , 凡 , k) + 巩 _邓 ‘_ ,)] k = 1 , 2 , ⋯ , N (’) F声J给定 (5) 式中 瓦 为第 1 时段至第 k 时段的最优价值函数 . 多维动态规划 的单增量搜索解法如下 . (l) 建立初始状态向量轨迹 . 在第一次迭代计算时 , 可在状态可行域内选择 一个标称状态 向 量序 列 {S , 叫k = 0, 1 , ⋯ , N }作为状态向量的初始轨迹 。 在以后的第 i次迭代计算 中 , 其标称状态初始轨迹 采用第 i一 1 次迭代计算得出的改进的状态轨迹 {s k“一 ’)}。 (2 )确定各状态向量 s : 的增量 向量 占, 。 对初始轨迹 {S k吟. 其增量可在状态可行域内任选 。 但在第 ! 次迭代计算 中 , 各状态增 量 占, 的分量用进退搜索法确定 。 此法的基本原理是 : 当第 i一 1 次迭代计算得出的改进后状态轨迹经过增量点时 (如 图 1 运筹与甘理 1卯, 年第4卷(一) 中的 s : 十占, , s2 + 占: ) , 第 i次迭代时沿此增t 方向加大搜索步长 , (增 t 值加倍) , 反之 (如图 1中的 s3 , 幼 , 则沿反方向减小搜索步长 (增 t 值为原值的 114 ) . 其算法如下 : 劝了一” 当穿一裤心一刀 一青心一” 材一 I) 一材一 , 询 rlse才,esL 一一卿 (3 )组成各阶段的状态点 . 在第 i次迭代计算时 , 阶段 k 有一个标称 (初始 )状态 S , 和一个增童 爪. 在状态 向t 为 m 维时 , 增童值也有 m 个 , 所以 在 m 维状态空间可组合成 2- 个状态点 . 用矩阵玖叹护 x m) 表示第 k 阶段 妙个状态点 , 矩阵共 护行 , 其中每一行的 m 个元素表示一个状态点 . 甲 = 人 · B. + 人 · B2 . (7)式中 人及 人为 护 x m 阶 0一 1 组合矩阵 , 其元素值均为 0 或 1 . 人 与 人 相互倒置 , 即 A : 的第 1 行与 人 的末行 (第 2叫行)相等 , 并依此类推 . 例如 , 对于 m = 2 , 即状态为 2 维的问 题 , 00 {00” 了 /了‘|1.、、、、、 一一A B . 及 B : 为 二 维对角阵 . S 、 . S 一 : (8) S 七- ) // 口lwe‘11 、、、、 一一B (9) 、.、1 1 . ‘ 11/ k- 办+ . .主S / s k . 、一 。、, B Z 一 } ‘“2““2 ⋯ \ (4) 用 动态规划基本方程 (4) 推求 m 维 N 阶段 、每阶段有 2“ 个状态点的 拼 夕 祷 最优策 略 , 亦即第 i次迭代计算的改进轨迹 . (5) 重复上述迭代计算 , 直至求出符合林 :于要求的近似最优解 . 2 3 搜索解法的收敛性 由于 目标函数 卿 = M in 艺v ‘侣k , \ , k) 是 s‘ i 且在 S、 的可行域中一般 为非严 格凸函数 。 因此 , 在给定的初始条件 一F , 往往收敛刘 岛释炙优解 如欲求全 局最优解 , 可 以 第 1 期 俞嘉第等 : 动态规划的单增童搜索葬法 给出不同的初始条件 , 对 尸分别进行求解 , 得到多个局部最优解 , 再在其中选出全局近似 最优解 . 实例 : 一条有多座水库的河流 , 为了有效地利用水资源来发电和灌溉 , 应用动态规划法 来寻求其最优运行策略 . 本题共 12(X) 个时段 , 状态变量为 m = 3 维 , 决策变量为 n = 7 维 , 目标函数为经济效益 . 此题应用单增量搜索方法迭代 10 次后 , 收效到 111 00 精度 (见图 2) , 说明此法收敛 . 绷溯溯姗 10 迭代次数 3 单增量搜索解法的优点 3. 1 搜索解法的计算次数和计算时间 搜索解法的计算次数和计算时间少 , 其原因有二 : (l) 搜索解法的增量是单向的 。 当状态变量为 m 维 , 增量个数为 (r 一 l) 个时 , 每一个阶段的状态点有 r “个 , 如果每个状 态点都可取严 种决策 (状态转移 ) , 则在一个 阶段上须计算 产 次 。 由于本算法 的增量仅一 个 , 故每阶段只须计算 2恤 = 4m 次 . 前述状态增量动态规划的增量数为 2 , 因此 , 每 阶段的计算次数为 3加 = gm . 本法 与之 ~ 二 , , ~ “ 、 , ~ 。 : ~ ~ ⋯ 、 . _ 4 m , _ _ 、 ~ ~ ~ 一 , ‘ 一一 ~ , 。 . , . ~ . 一 ~ ~ ~相 比 , 所需的计算时间之 比为 T = 孕三 (= 0. 4 4 4 m) . 显然 , 随着状态变量维数增加 , 亦即问题一 ’ - - 一 - - - - 一 g m “ 一 ’ 一 产 - 一 ‘ ”” ’一 一 一 ’一 ’一一 -一一 一一 ’ 一 ’ 一 ” ‘ ’一 复杂程度 的提高 , 单增量搜索解法不仅降低 维数灾的困扰 , 而且戏剧性地减少了机 时 。 例 如 , 当 m = 5 时 , 本法计算时间不到增量动态规划法 的 1 . 7% . (2) 增量由进退搜索法确定 . 这种处理方法加快了收敛速度 。 减少 了计算次数和时间 。 在上节所举的水资源系统优化运行问题中 , 本拟采用状态增量动态规划法 , 当时估计在 V A X 一 1 1/7 8 0 小型计算机上运行时间将长达 5 小时 , 因而改用本方法 , 结果仅用 20 分钟 , 约 为前法的 l/ 1 5 。 32 搜索解法的精度 搜索解法收敛快 、 精度高 . 在相同的精度下 , 此法计算次数远 比常规动态规划 法为少 。 10 运筹与管理 1 9 9 5 年第 4卷(一) 在相同的计算次数下 , 此法所得的结果精度远高于常规方法 . 为了说明这一点 , 我们把搜 索解法用于一维动态规划计算实例 , 该问题中阶段数 26 , 状态变量的最大变幅 s( 状态可行 域 )为 0 至 4 60() , 采用初始标称轨迹为 23 加.0 , 初始状态增量为 23 00 :0 运算精度是 以最终 最大增量 占~ 与状态可行域的最大变幅 s 之比来计算 . 通过在 s正M王N ,S 一 757 0c 小 型机 上实验 , 得出下表数据 , 从表中结果看 出 , 这种方法不仅收敛速度快 , 而且能取得相 当讯。的 精度 . 最最终最大增盘盘 精度度 从开始起算的的 从开始起算的的 搜索解法与常规方法比较较 临临临 峪声声 计算时间间 迭代次数数数数数数数数数数数数数数数数数数数数数 搜搜搜搜搜搜索解法总总 常规方法总总 时间比比计计计计计计算次数数 计算次数数数 取取刃刀刀 0 . 111 4. 1翻222 3 lll 3刀444 314666 1 .0222 22230 .000 0.0555 4. 阅5888 3444 353666 11月肠肠 0. 3 111 夕夕之OOO 0. 0222 4. 67 1888 3555 3 34000 67丘场场 5 . 4 x 10 一222 肠肠刀刀 0.0 111 5 . 2《讨讨 3888 395222 公巧乞场场 l, s x lb 一222 2223 .000 0 .侧)555 5 . 3 1卯卯 3999 们肠肠 10又协2666 3 . 3 x 10 一 333 蛇蛇蛇 0 .(X) 222 5 .“龙龙 4222 4女沼沼 6 5火铆2666 6 . 7 x 10 一 444 444.666 0 .田lll 6 .抖2777 4777 4技粥粥 2印52() 肠肠 1. 8 x 10 一 444 4 单增量搜索解法的推广应用 首先 , 如上所述 , 搜索解法在确定增量时并未把状态变量离散化 , 而是作为连续变量来 处理的 , 相应的决策变量也是作为连续的 , 所 以可认为搜索解法可 以求解连续变量动态系 统的多阶段决策问题 . 其次 , 搜索解法不仅适用于多维问题 , 也适用于一维最优化问题 , 而且也可用 于连续时 间系统的寻优 . 此外 , 由于这种方法是一种数值解法 , 对目标函数 、 约束条件 、 价值函数等均无可微要 求 , 避免了前述微分动态规划的不足之处 , 使其应用范围较为宽广 . 5 结 论 综上所述 , 动态规划的单增量搜索解法具有广阔的应用范围 , 它明显地优越于现有文献 中介绍的算法 , 并能推广到连续型动态规划问题 . 参 考 文 献 [l1 伪记 H . Jaco 忱o n , E厄记 Q . Ma 孙犯 , D 江re 代泊t认I D 扒份 In犯 Pro gi 刊rn 川Lln g, An r d 以田 Eise 丫沁r Pu划比b加g 伪m Pa ny Inc . , N亡w yo 政, 197 0 . 冈 H o锵 o n . H . R , an d N . G . F . S 川d 扣 . A ne w al即ri thJ 爪 fo r 此 so lu t沁n of m ul 出ta 把 dyl 扭m 瓦 Pro gl 别肚m ln g Pro ble ms , M a th . Pro gl aJ 屁m in g , 8 , 1以 一 116 , 1975 . [31 L甘so n . R . E , S ta te In a 吧n 丫泪tal D ”皿m 吮 Pro 邵aJ 爪m in g , E址谁r No rth 一 H o lla 叱 , N七w yo 次 , 1968 l’l 【美 】D . A. W 污脱r , R . Q 坦批任口合著 , 邓乃扬 、刘宝光译 . 非线性最优化导论 , 北京工业学院出版社 , 198 7 年 . 第 1 期 俞嘉第等: 动态规划的单增量搜索葬法 1 1 一 T eses es一——‘ Sca re hi ng1 nYu 乃耐i Ch 翻 J认应闭 Z 曰呀 肠圳”(加位 u七 of 如匕留】Jd d U 苗说面勿 ‘H d 过 柳碱 En 乡加颐ngT ec bl 幻Io 口2艾日玲)A加比伐 hi the rns t part of th is a币de , 山获” co rD ID O吻 诏目 ite ra tiVe algo ri血圈 in d yna m ic运C八芝刀en 公d d yn a面c p ro g ra m m in g d 一。公例血血9 wo rk and to a a 芜Ie h te the 戊七。℃n 祀n t 15 p ut fo p 胃a吐. A“刀记吨 topra 改ica l c ase , 能 co ns 记er tha t this ne w 〕g la n 止田叮g , su a 羌SS ive o Ptim 访n g al g o ri th 叭 sta tea比 sim Pfy d is以璐曰 . hi 。月巴 to d。二七义祀 比cn ve 犯en Ce sP时 , a sea 代五运9 algo ri th m 袱th sing lethe th eo reti ca l ex p h na tio n a nd th e ana 协15 of aite ra tlv e a lg o ri thi m 15 be tt er th an th 众兄 co r Dr D o ul yu狱沮 algo ri th n 招 n ℃。tio n ed abo Ve ·K盯 w o心 d yn a mi c p ro g ra n 止山n g ; sta te i~ t; 戏曲Ing wi th si ng le 一 i~ t