动态规划算法综述（精选7篇）
动态规划算法综述 篇1
1 动态规划基本概念
在现实生活中, 有一类活动的过程, 由于它的特殊性, 可将过程分成若干个互相联系的阶段, 在它的每一阶段都需要做出决策, 从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定, 它依赖于当前面临的状态, 又影响以后的发展。当各个阶段决策确定后, 就组成一个决策序列, 因而也就确定了整个过程的一条活动路线。这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程, 这种问题称为多阶段决策最优化问题。这种多阶段最优化决策解决问题的过程就称为动态规划。
2 动态规划基本思想
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中, 可能会有许多可行解。每一个解都对应于一个值, 我们希望找到具有最优值的解。动态规划算法与分治法类似, 其基本思想也是将待求解问题分解成若干个子问题, 先求解子问题, 然后从这些子问题的解得到原问题的解。与分治法不同的是, 适合于用动态规划求解的问题, 经分解得到子问题往往不是互相独立的。若用分治法来解这类问题, 则分解得到的子问题数目太多, 有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案, 而在需要时再找出已求得的答案, 这样就可以避免大量的重复计算, 节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到, 只要它被计算过, 就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样, 但它们具有相同的填表格式。
3 动态规划适用的情况
任何思想方法都有一定的局限性, 超出了特定条件, 它就失去了作用。同样, 动态规划也并不是万能的。适用动态规划的问题必须满足以下三点:
3.1 最优化原理 (最优子结构性质)
一个最优化策略具有这样的性质, 不论过去状态和决策如何, 对前面的决策所形成的状态而言, 余下的诸决策必须构成最优策略。简而言之, 一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。
3.2 无后向性
将各阶段按照一定的次序排列好之后, 对于某个给定的阶段状态, 它以前各阶段的状态无法直接影响它未来的决策, 而只能通过当前的这个状态。换句话说, 每个状态都是过去历史的一个完整总结。这就是无后向性, 又称为无后效性。
3.3 子问题的重叠性
动态规划算法的关键在于解决冗余, 这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术, 它在实现的过程中, 不得不存储产生过程中的各种状态, 所以它的空间复杂度要大于其它的算法。选择动态规划算法是因为动态规划算法在空间上可以承受, 而搜索算法在时间上却无法承受, 所以舍空间而取时间。
4 求解的基本步骤
动态规划所处理的问题是一个多阶段决策问题, 一般由初始状态开始, 通过对中间阶段决策的选择, 达到结束状态。这些决策形成了一个决策序列, 同时确定了完成整个过程的一条活动路线 (通常是求最优的活动路线) 。动态规划的设计都有着一定的模式, 一般要经历以下几个步骤:初始状态—决策1—决策2—……—决策n—结束状态。
4.1 划分阶段
按照问题的时间或空间特征, 把问题分为若干个阶段。在划分阶段时, 注意划分后的阶段一定要是有序的或者是可排序的, 否则问题就无法求解。
4.2 确定状态和状态变量
将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然, 状态的选择要满足无后效性。
4.3 确定决策并写出状态转移方程
因为决策和状态转移有着天然的联系, 状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策, 状态转移方程也就可写出。但事实上常常是反过来做, 根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
4.4 寻找边界条件
给出的状态转移方程是一个递推式, 需要一个递推的终止条件或边界条件。
一般, 只要解决问题的阶段、状态和状态转移决策确定了, 就可以写出状态转移方程 (包括边界条件) 。实际应用中可以按以下几个简化的步骤进行设计:
(1) 分析最优解的性质, 并刻画其结构特征。
(2) 递归的定义最优解。
(3) 以自底向上或自顶向下的记忆化方式 (备忘录法) 计算出最优值。
(4) 根据计算最优值时得到的信息, 构造问题的最优解。
5 动态规划实现的说明
动态规划的主要难点在于理论上的设计, 也就是上面4个步骤的确定, 一旦设计完成, 实现部分就会非常简单。使用动态规划求解问题, 最重要的就是确定动态规划三要素:
(1) 问题的阶段。
(2) 每个阶段的状态。
(3) 从前一个阶段转化到后一个阶段之间的递推关系。
递推关系必须是从次小的问题开始到较大的问题之间的转化, 从这个角度来说, 动态规划往往可以用递归程序来实现, 不过因为递推可以充分利用前面保存的子问题的解来减少重复计算, 所以对于大规模问题来说, 有递归不可比拟的优势, 这也是动态规划算法的核心之处。
确定了动态规划的这三要素, 整个求解过程就可以用一个最优决策表来描述, 最优决策表是一个二维表, 其中行表示决策的阶段, 列表示问题状态, 表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值 (如最短路径, 最长公共子序列, 最大价值等) , 填表的过程就是根据递推关系, 从1行1列开始, 以行或者列优先的顺序, 依次填写表格, 最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。
6 动态规划算法基本框架
代码如下所示:
摘要：本文通过系统的介绍动态规划算法的基本概念、基本思想、适用情况分析、基础求解步骤、实现的说明和算法的基本框架, 对动态规划算法进行了总结和概述。
关键词：算法,动态规划,最长公共子序列
参考文献
[1]网上的文献 (举例:最长公共子序列-动态规划-算法导论实践[EB/OL].http://hi.baidu.com/jiaxiaobosuper/item/5f0e7510979bb0413b176e4b, 2011-03-27.
[2]Wang Xiaodong.Design and analysis of computer algorithms[Z].Beijing:Publishing House of electronics industry, 2012.王晓东.计算机算法设计与分析.北京:电子工业出版社, 2012.
动态系统中粒子群优化算法综述 篇2
粒子群算法(Particle Swarm Optimization,PSO)是由生物学家Kennedy和Eberhart于1995年提出的进化计算技术,该算法通过对鸟类觅食行为的模拟,从而实现对实际问题的优化。
PSO算法在高维空间函数寻优方面具有解质量高、鲁棒性好、收敛速度快的优点,因而在神经网络训练、函数优化、模糊系统控制、模式分类领域得到广泛应用。同时,PSO算法具有程序简单、设置参数少、收敛速度快、实现容易等特点,目前已被广泛应用于静态问题优化中。然而,直接利用PSO算法跟踪动态系统,其效果不佳,因此动态系统中PSO算法的改进尤为必要。本文主要对PSO算法在动态系统中的改进方法进行总结。
1 基本粒子群算法
PSO算法中每一个潜在的解都被称为一个“粒子”,粒子在解空间内“飞行”,并且具有速度和位置两种属性,粒子的位置受自身运动经验的影响(个体最优位置)以及所有粒子运动经验的影响(全局最优位置),在飞行过程中其速度和位置按照下式进行更新:
式(1)、式(2)中,vid(t)、xid(t)分别代表第i个粒子目前的速度和位置,yid(t)是粒子自身的最优位置,y(t)是粒子的全局最优位置,ω是惯性权重,c1、c2是学习因子,r1、r2是在[0,1]之间均匀分布的随机值,式(1)的第一部分代表了粒子对速度的记忆,第二部分是自我认知部分,引导粒子群飞向自身经过的最好位置,第三部分是社会部分,代表了粒子间的信息共享和相互合作,具体算法流程如图1所示。
2 动态优化问题
现实生活中许多优化问题都是动态的,例如,城市交通状况由于不同交叉口红绿灯的转换,可以连续地动态改变,这就可以看成动态优化交通问题。动态系统可以分为以下几种:(1)最优值不变,取得最优值时对应的位置发生改变;(2)保持位置不变,最优值改变;(3)最优值以及取得最优值时对应的位置均发生改变;(4)在多维系统中,这些改变可以同时或独立地发生在同一维或多维上[6]。
与静态优化不同,动态优化不仅需要达到最优值,而且还需要能够跟踪最优值的轨迹变化。近年来,人们越来越关注进化算法在动态系统中的优化问题,动态优化问题可以被描述为如下形式:
式(3)中,目标函数f由向量和时间t决定。
已有许多研究者对进化过程和进化算法做了研究,大多是从基准函数(三维Parabolic函数)中创建动态环境,文献和文献则详细提供了创建动态环境的一系列方法,并给出了具体应用。三维Parabolic基准函数如式(4),在(0,0,0)处取得最小值0。
对式(4)中的x增加偏移量Offset,即在一定的更新频率(每隔多少代)下,对基准函数在每一维上进行线性、环形、随机处理,即能够产生3种类型的动态轨迹:线性、环形、随机轨迹,其具体函数表达式如式(5):
然而,现实生活中的许多问题更加复杂多维且变化多端,因此,一个可以涵盖各种各样变化类型的测试函数应运而生,文献提供了该测试函数的表达式,见式(6):
式(6)中,N代表该动态系统中有多少个峰,并且每个峰在位置(Xi,Yi)上独立,其高度为Hi,倾斜为Ri,这些峰用Max函数混合起来,每一次生成器f(X,Y)被调用时,基于式(7)、式(8)作改变,就会产生新的随机的形态学类型。
该测试函数具有以下优点:(1)易生成较为复杂的问题;(2)适应值可以方便设置为所希望的数据;(3)可以扩展到高维空间;(4)函数提供了3种可以生成动态环境的特征(高度、位置、倾斜度)。当需要生成较为复杂的动态环境时,只需改变以下参数:N(峰的数目)、Rbase(倾斜度可控变量的最小值)、Rrange(允许的变化)、Hbase(斜坡高度的最小值)、Hrange(允许的变化值),简单易行。同时,文献则对两种动态环境作对比,动态函数DF1更能代表一些复杂多维的环境。
3 动态系统PSO优化方法
许多优化问题是动态的、时变的,它们的最优解将会随着时间的改变而改变。对于这种时变优化问题,优化算法不仅要迅速检测到环境的改变,同时,还要对改变作出相应的应对策略。Eberhart首先将基本PSO算法应用到动态系统中,结果显示当环境改变,频率、步长较小时,基本PSO能够及时跟踪动态极值。然而,当动态系统变化较大时,基本PSO算法检测和跟踪效果不好。因此,为了更好地适应动态环境变化,提出了一些经典的优化PSO算法以实时检测环境变化,并及时针对改变调整寻优策略。
3.1 检测、响应动态系统的PSO算法
Hu and Eberhart通过检测“固定的”最优值以及“改变的”最优值来判断环境的改变,“固定的”最优值即找到最优值后经过一定的代数,再次检测最优值,看其是否发生明显改变;“改变的”最优值[13]即每一代最优值的位置将会被重新计算,如果最优值改变,则说明环境发生了动态改变。针对这两种改变,本文给出了多种响应方法,可根据不同的应用,选择不同的响应方法。
Carlisle[14]提出了一种“哨兵”粒子群优化器,在解空间内用一个固定的点来检测环境的改变,在每一次迭代前,“哨兵”将会重新计算适应值,并与之前进化的值作对比,由于“哨兵”所在的位置是固定的,如果适应值发生较大改变,则说明环境发生了改变,“哨兵”将会提醒种群更新最优位置记忆;文献[15]同样是利用了“哨兵”的思维,但是由于Carlisle[14]的固定粒子改为一个或多个随机选择的粒子,这样就可以检测到全局的环境变化;文献[16]则在文献优化器的基础上,作出以下优化:当环境发生改变时,不是盲目取代最优值的位置,而是利用目前最优值的位置重新计算环境改变后的适应值,如果此时的适应值优于之前的最优值,则保留此处信息,这样就大大提高了寻优准确性。
3.2 自适应PSO算法
文献不需要实时检测环境的改变,它是基于传统的PSO算法,提出了一种新的粒子群最优适应值更新机制,传统的最优值更新公式如式(9):
当t+1时,比较最优值与f(Xi(t+1))的大小,保留最大值,自适应PSO算法更新公式如式(10):
在式(10)中,引入衰减常量T,T∈[0,1],个体最优值以及全局最优值将会以一定的速率随着时间衰减,目前位置的适应值将会高于衰减的适应值,并取代之前的适应值。尽管所有的粒子具有相同的衰减常量,但每一个粒子的更新频率也是不同的,当f(X)越来越大,f(P)越来越小,粒子将会频繁更新最优值,直至达到循环迭代次数,寻优停止。
Shimin引入了“活跃因子(Activity Factor,AF)”来评价粒子群搜索全局最优值的能力,可以被用来检测粒子的搜索状态并评价整个种群的收敛情况。在搜索空间里,AF可以定义如式(11):
式(11)中,Ai(t)是第i个粒子在时间t时的活跃度,wd是聚合粒子AF的惯性权重,Aid(t)是第i个粒子在第d维时的活跃度,它可以由式(12)获得:
其中,vid(t)是第i个粒子在时间为t、维度为d时的速度,Rd是在d维上的搜索范围,c是调谐变量。
根据AF的定义可知,当粒子运动缓慢时,AF的值很小。同时可以认为,整个种群达到最优值时,粒子才会保持缓慢运动的状态,这里将AF作为粒子群运动状态的评价标准,同时,在复杂的动态环境中,需要随机选取一部分粒子群为“活跃粒子”。当粒子群运动缓慢时,活跃粒子将会检测移动状态并且重新初始化,然后通过粒子群更好地搜索全局最优值。
3.3 混合PSO算法
Dianmin引进混沌变化技术,当环境发生动态改变时,由粒子群多样性引导的混沌技术进行响应,提高响应效率。目前,对混沌没有严格的定义,一般而言,混沌状态可以通过式(13)的logistic映射得到。
式(13)中,μ是控制因子,当μ=4时,处于完全混沌状态。
此处响应政策可以被描述为以下方式:当环境发生改变时,选择要被处理的粒子i,它目前的位置为xij(t),范围为[aj,bj],基于文献、文献,将粒子i的每一维映射到[-1,1],映射方法是:
式(16)将i映射到搜索空间:
这使得个体粒子具有智能的混沌变化,每个粒子不仅能通过个体极值点和全局极值点调整自身的位置,还可以通过混沌变异,调整粒子群的多样性,促进了粒子群搜索整个解空间。
粒子的多样性可以由式(17)描述:
式(17)中,diversity(s(t))是粒子群在t代时多样性的值,s(t)代表粒子群种群,|s(t)|是粒子群的大小,|L|是搜索空间最长的半径,N是维数,pij(t)是粒子i在j维上的最优位置,是所有粒子在j维上的最优值位置的平均值。在搜索过程中,如果粒子的多样性较高,并且diversity(s(t))≥h×diversity(s(0)),则不需要处理粒子;如果粒子的多样性较低,diversity(s(t))≤h×diversity(s(0)),粒子分布集中,需要对粒子进行处理,即引入上述混沌变异技术,这里h是多样性的控制因子,不同的h会使算法效果不同。
4 结语
在现实生活中,许多系统状态的改变,如目标、优先性、资源等的改变会导致一些再优化问题。例如,自动集装箱制造商进行船对岸起重时,应该保证在5~10分钟内对于整个接口设施实施一个新的设备安排表;当给某地区提供药物时,如果该地区突然急需药物,则针对这一优先性的改变,一个新的安排表应该快速可得,改进的粒子群算法可以有效且快速解决这些优化问题。
动态规划算法综述 篇3
随着信息科技与互联网的高速发展,各个应用领域的信息量都呈现了爆炸性的增长趋势。因此,不同应用领域各自关注的实体对象之间的关系也变得愈加庞大和复杂。在这些复杂关系的背后,往往蕴含着巨大的科学价值和商业价值。由此,吸引了诸多领域的研究者都开始专注于实体对象之间关系的研究,如计算生物学领域中,蛋白质和酶之间所发生的复杂的交互、调控与代谢关系的研究;社会学领域中,对不同社交网络中人与人之间交际关系的研究;商业领域中,对金融网络和货币流通网络中商业关系的研究;以及互联网搜索领域中,不同网页之间超链接关系的研究。在这些领域中,如果采用传统的关系数据库来管理数据对象之间的这些错综复杂的关系,会用到巨量且昂贵的连接操作。因此,利用传统的关系数据库来研究复杂的结构化数据并不具备现实可行性。“图”作为离散数学和计算机科学中基本的数据结构,可以有效地表示存在多种关联的数据以及内部具有一般性结构的数据。图中,每个顶点代表现实世界中的实体对象;两个不同顶点之间则可能会存在一条或多条边,由其代表不同实体之间存在的某种关系。针对这种形式的结构化的数据,研究者们将其称作“图数据”。
近年来,图数据已广泛地用于刻画现实世界中各类实体间的复杂关系。例如,传感器网络中的节点拓扑结构图;互联网领域中的页面超链接关系图;计算生物学中的蛋白质交互和基因调控网络;社交网络中(如新浪微博、微信等)用户之间交互关系图及～Email～通信关系图;物流学领域中的交通网络、物流网络等等。这些例子清楚地表示,图数据现已无处不在,因此,对图数据进行管理则成为一个迫切重要的问题。由于图数据具有的重大科学意义和巨大社会价值,数据领域内的顶级学术会议SIGMOD、VLDB、ICDE、KDD以及重要学术会议CIKM、EDBT、ICDM等均设有与图数据管理有关的研讨议程。
然而,在现实世界中,实体对象间的关系却每时每刻都在发生着变化。以社交网络为例,根据Facebook网站2010年的Yearbook报告,仅仅2010一年间,其用户就从3.37亿人增至5.85亿人,平均每秒新增7.9位用户,同时,平均每分钟,会发生47 553个好友关系的建立或解除。2011年,Google+在上线后的两周时间内,增长了1 000万的用户。同年,Twitter～平均每天都活跃着2亿的用户,并且发生着超过16亿次的交互。这些数据无不在显示与说明,现实世界中实体对象间的关系都无时无刻地经历着变化。因此,描述实体对象的图数据的结构和内容往往不是固定不变的,而是会随着时间的推移发生各种演绎与进化的。
动态图,又称为演绎图(evolving graph),是指会随时间而发生变化的图模型或者图数据。动态图可以根据其变化的形式分为两类:
(1) 图中拓扑结构关系发生变化;
(2) 图中顶点和边所代表数据对象内容、或者图中某一特定对象的评价方式发生变化。
由此,可将这两种情况分别简称为图的结构变化和图的内容变化。在第一种情况中, 图中的顶点和边会随着时间发生插入和删除,从而导致图的结构发生变化。在第二种情况下,顶点或者边上的权值会随着时间发生数值上的改变,或者对图中某一特定对象的评价方式会随着时间变化。比如,对图中每条路径,存在一个评分函数随时给出该路径的得分。对一组固定的起点和终点,评分函数不同,其评分最优路径也就不同。因此,当评分函数随时间发生变化时,同一对起点和终点间的评分最优路径也会随着时间发生相应的变化。
动态图数据在现实生活中的广泛存在,比如:在蛋白质交互网络中,各类蛋白质分子的相互作用有着队列顺序,这使得整个蛋白质交互过程要随着时间而顺序进行;在社会关系网络中,各类人群和各类团体之间的相互关系也会随着时间发生变化;在交通网络中,通过每条公路的时间和费用因交通堵塞的发生均会随着时间发生变化。因此,对动态图数据的管理就有着重要的实践研究意义,主要体现为:在计算生物学领域中,研究基因组结构和功能的协同进化关系;在社会学领域中,通过从动态图数据挖掘知识,发现各类社会团体之间关系的演变规律和原因;在交通网络中,通过交通网络拓扑结构的变化,研究网络中某区域变化对全局网络的影响等等。
尽管如此,传统静态图数据上各类问题的解决算法却无法应用于动态图数据上各类问题的高效解决,主要有以下几个原因:第一,传统的静态图模型无法描述图数据随时间发生演绎与进化的情况;第二,传统的静态图模型上的各类问题的定义在动态图数据模型上不再适用;第三,图数据的动态性使得各类问题的计算复杂性大大增加,原有静态图上的各类方法将无法有效地解决这些问题。此外,现有的动态数据管理的研究主要集中于数据流和传统关系数据的动态维护,但却无法处理结构复杂的图数据。因此,必须提出更为优质的方法能够随着时间变化高效地维护图结构,并且能够实时返回用户所需要的结果或者从动态图数据中挖掘得到更加实用的知识。
2 动态图上的查询与挖掘算法的研究工作
相比传统静态图数据上的研究,动态图数据上的研究工作才刚刚起步。但在较近的几年,越来越多的成果开始在动态图数据管理研究方面得以展现。在本节中,将对动态图上的相关工作进行简单的介绍,包括基于结构变化的动态图上的研究工作和基于内容变化的动态图上的研究工作。
2.1 基于结构变化的动态图上的研究工作
过去几年间,研究者们对拓扑结构关系变化的动态图相关研究开展了大量效果卓著的工作。这些工作主要集中在以下三个方面:
(1) 图上经典问题在动态图上的研究;
(2) 动态图上子图模式的研究;
(3) 动态图上变化探测相关问题的研究。
现在,将在下面几个专题中对这三方面工作进行分别的讨论剖析。
2.1.1 图上经典问题在动态图上的研究
图上经典问题主要包括:最短路径问题、可达性查询问题、最小生成树问题和连通分支问题等等。目前,已经见到很多的工作对这些问题进行了研究并取得了颇丰的研究成果。但在动态图上,这些问题则变得更加复杂。下面,将对动态图上重要的图经典问题的相关工作分别加以介绍。
(1)动态图上最短路径问题的研究
最短路径查询是图上一个基础性的查询问题,其应用十分广泛。当图的拓扑结构关系随时间发生变化时,两点间的最短路径也会发生相应的变化。动态图上最短路径问题相关工作主要表现在:当图的拓扑结构发生变化,即顶点和边发生插入和删除时,如何维护指定的顶点之间的最短路径;以及当图的拓扑结构发生变化,如何为任意图中两个顶点实时并迅速地找到两者之间的最短路径。其中,某些工作要求动态图必须满足一定的性质,如:文献[1,2]研究了平面图 (planar graph) 上的最短路径维护问题,文献[3]和文献[4]研究了非加权图上最短路径的维护问题等等。近几年来,研究者们相继提出一些新方法,但这些方法均未对图性质做任何要求[5,6,7,8,9,10,11]。下面,即将对其中标志性的工作进行讨论与分析。
文献[5]给出一个全局动态的算法FMN来计算动态图上的单源最短路径问题,全局动态 (fully dynamic) 是指图中的顶点和边允许发生删除与插入。与全局动态对应的是衰减动态 (decremental dynamic),却只是允许图中发生顶点和边的删除操作。给定一个顶点s,该工作的目标是维护顶点s到图中所有其他顶点的最短距离和最短路径。在研究中,构建了一棵以s为根的最短路径树T,当图中顶点和边发生插入和删除时,算法就对最短路径树T进行相应的更新。同时,又定义了边上“层次”的概念。文献[5]表明每次更新T需要O(klogn)的平均时间,其中,n为图中顶点个数,k为图中边的最大层次数。此外,文献[5]也表明,完成最短距离查询和最短路径查询分别需要O(1)和O(L)的时间,这里,L表示最短路径上边的数量。尽管FMN 算法回答查询的时间很短,但是却需要维护复杂的最短路径树结构,这就使得其算法效率并不高超。如文献[6]中所示,动态算法SWSF-FP 在很多情况下都要优于FMN 算法。
文献[6]中给出了一个全局动态算法SWSF-FP 来维护动态图上的最短路径,该工作要解决的是和文献[5]中相同的问题。SWSF-FP 算法的主要思想是:为图中每个顶点维护一个值rhs(v),该值记录了起点s到顶点v的最短距离。当图中发生边的增加和减少时,算法逐步地更新受到这条变化边影响的顶点上的rhs(v)取值。SWSF-FP算法的缺点是需要频繁地计算rhs(v),这将导致较高的时间开销。文献[7]中对SWSF-F算法进行了改进,并提出一个基于Dijkstra的算法的更新最短路径树,使得SWSF-FP算法可以用于具有多重边的动态图上。
文献[8]中提出了一个为图序列中每一个快照计算两点间最短路径的基本框架FVF。该文献假定在图的动态演绎过程中,会有一些历史信息得到保存。该文献中,动态图序列根据其相似性可划分为若干个图快照的集合。FVF方法为每一个集合保存一个并集图和一个交集图,通过并集图和交集图上保留的两点间的最短路径信息,可以快速回答每个图快照中两点间的最短路径。FVF的方法也存在着不足,其缺点是:通过并集图和交集图上的信息,只能找到图快照上一部分顶点对间的最短路径。当并集图和交集图上的信息不能帮助回答某一对顶点间的最短路径时,FVF 需要调用静态图上的最短路径算法为该图快照上的这一对顶点计算彼此之间的最短路径。
此外,文献[9]中首次给出了计算动态图中所有顶点对之间最短路径的全局动态算法。文献[10]中则给出了一个改进的算法用于维护动态图中所有顶点对的最短路径。
(2)动态图上最小生成树问题的研究
文献[11]中给出了一个全局动态的算法来维护动态图上的最小生成树,该方法利用了图分解理论将图划分成一组连通图的集合。当图中的边发生动态更新时(插入或者删除),只有集合中的一部分连通图会受到影响。因此,算法将这部分连通图在最小生成树上的对应部分更新即可。文献[11]证明了:对每一次边的更新,算法维护最小生成树的时间复杂度均为O(m1/2) ,其中,m表示图中边的数量。特别地,当动态图是一个平面图时,算法的时间复杂度还可进一步降低为O((log m)2)。
文献[12] 采用Sparsification技术对文献[11] 中的工作进行了改进,使得对每次边的更新,维护最小生成树的时间复杂度能够降至O(n1/2)。文献[12] 表明,当只允许图中的边进行插入更新操作时,可以利用Sleator-Tarja 动态树来维护动态图的最小生成树。此时,对每一次边的更新,算法均需要O(log n)的时间完成最小生成树的更新。当只允许图中的边进行删除更新操作时,文献[12]表明,并不存在全局动态的算法能比O(log n)更快。进一步地,文献[13]给出了一个最坏情况下时间复杂度为O(log n)的全局动态算法,当动态图中的边每次发生更新时(插入或者删除),该算法用于维护最小生成树的平摊时间即为O(n1/3 log n) ,而回答最小生成树的查询却只需要O(1)的时间。
(3)动态图上k连通分支问题的研究
文献[14]首次研究了动态图上连通分支(k = 1)的动态维护问题,其中给出一个时间复杂度为O(q+|V ||E|) 的算法,可以实时回答所要查询的q个顶点是否在同一连通分支中。然而,该工作只能对k=1的连通分支进行动态维护,且只能允许动态图中发生边的删除。
文献[15]首次提出了一个部分动态算法用于维护2-顶点连通分支。该研究假设动态图中只会发生顶点和边的插入更新操作。文中对Sleator-Tarja动态树结构进行了改进,使其可以适用于文中给出的递归算法。文献[15]表明:对每一次顶点或边的更新,其维护连通分支的时间复杂度为O(nlog n+m),空间复杂度为O(n)。即便如此,该工作提出的算法也不是全局动态算法,即其仅能处理动态图中只发生顶点或边插入更新操作的情况。
文献[16] 中研究了并行环境下动态图上对k=2和k=3的k连通分支的维护问题,并给出一系列的理论结果。文献[17]中提出一个抽象化模型用于描述图的连通结构,该模型能够有效地反应动态图中连通结构的变化,并能回答图中任意两个顶点是否属于同一个5-连通分支。文献[17]中的方法仍然不是全局动态的,即仅能解决图中边只发送插入更新的情况。
目前,在动态图上,关于图经典问题的研究工作主要集中在最短路径维护,最小生成树维护和k-连通分支维护等问题方面。这些工作只是讨论了动态图上对某些特殊性质进行动态维护的复杂度,以及给出一些理论结果,却不曾关注图中“何时”并且“何处”发生了显著的变化。
2.1.2 动态图上子图模式挖掘的研究
子图模式挖掘是图挖掘中一类十分重要的问题。针对静态图上的子图模式挖掘已经开展了大量深入的研究工作并取得了不俗的研究成果。然而,动态图上的子图模式挖掘问题的研究却只是刚刚开始。目前,动态图上关于子图模式的研究主要集中两方面:动态图上频繁子图模式挖掘和动态图上紧密子图挖掘。
动态图上的频繁子图模式挖掘是指在一个图的演绎过程中(或者演绎图序列中)找到具有相同变化过程的子图。目前关于动态图上的频繁子图模式挖掘已经取得了一定的进展,其研究目的都是从动态演绎图序列中找到一组子图序列,使得其满足:
(1) 这些子图在动态图序列中的出现是频繁的;
(2) 这些子图的图序列随时间变化的情况保持一致。
文献[18]将图中每一个顶点上或者每一条边上的一次变化称为一次“原子操作”,图序列中任意两个连续子图之间的变化可用一系列的原子操作来表达。文中定义了原子操作表达的文法规则,因此,对动态图上频繁子图模式的挖掘等价于在原子操作序列上的频繁项集的挖掘问题。文献[18]提出了名为GTRACE 方法来计算序列中具有相同操作顺序的原子操作序列,并将其转化为动态图上的频繁子图模式。
文献[19]提出一种基于约束的挖掘算法来计算动态图上具有相同进化模式的频繁子图,其目的是根据用户给出的两种约束参数:紧密度参数和频繁度参数,在动态图序列中找到足够紧密并且足够频繁的具有相同变化模式的子图。文献[20]提出了在动态图序列中寻找一种新的模式,即图中的某几部分区域会以一定相关的方式发生进化。文献[21]研究了如何在动态图集合中挖掘频繁子图模式。在该问题中,动态图集合是指一些图的集合,集合中的每一张图均会随时间发生变化。文献[21]的目的是在这些动态图集合中找到一组具有相同演变模式的频繁子图。该问题与图数据库中频繁子图模式挖掘的问题相类似。文献[21]对现有静态图数据库中的频繁子图模式挖掘算法进行了改进,使其可以适用于动态图集合上的频繁子图模式挖掘问题。文献[22]研究了在动态图序列中挖掘具有相同变化模式的频繁树结构的问题。文献[23]中考虑了如何在多项式时间内计算得到周期性或者近似周期性的子图变化模式。文献[24,25]则研究了如何在社会网络的进化过程中找到满足一定进化规律的团体组织(community) 。
2.1.3 动态图上变化探测相关问题的研究
文献[26]和文献[27]利用熵等信息论方法,适当分割图流,并在每一个流片段中发现相对高度互连的结点社团(community)。文献[26]提出了一种动态张量分析的方法,将图的动态演变抽象为一个较小核心张量流和其对应图的映射矩阵。GraphScope方法[27]用于在大规模的动态演变图上发现联系紧密的社团(community),并探测这些社团发生显著变化的时间。文献[28,29]提出了三种不同的代价函数,如最大公共子图,来检测图数据流在何时发生了显著改变。文献[30]提出了在图数据流中计算图与图之间距离的优化方法。该文定义了图与图之间距离的概念,并设计了一个算法,仅需要有限的内存开销,即能以任意顺序处理图数据流中发生变化的边。这些方法都提出了各自的目标函数来定义动态图数据发生显著变化的概念,但这些代价函数都是落定于动态图整体来进行考虑的。而在现实世界中,计算动态图序列中所有子图的代价函数值却是不切实际的,因此这些方法都不能发现并确定动态图中的哪一子部分发生了显著变化。
2.2 基于内容变化的动态图上的研究工作
基于内容变化的动态图是指:图上顶点和边上的权值会随着时间发生变化。目前,关于内容变化的动态图方面的探讨主要集中于时间依赖图上最短路径的研究。时间依赖图上边的代价权值被刻画为一个会随着时间的变化而变动的函数。目前,关于时间依赖图上的最短路径查询问题(TDSP)的研究工作已经获得了长足的进步。然而,这些工作主要解决了最短旅行时间问题,即在时间依赖图模型上找到一条起点到终点的路径,使得该路径的时间代价总和最小。相应工作主要分为两类,一类是基于离散的时间模型,另一类则基于连续的时间模型。文献[31,32,33]研究了离散时间模型下的时间依赖最短路径查询。文献[33]将出发时间区间平滑地离散为多个时间点,并依据这这些时间点将图中顶点和边复制多次。因此,时间依赖图就转化为一个规模增大的静态图。文献[31]给出方法如何在这个静态图上完成最短路径查询。只是这一基于离散时间模型的方法并不能回答连续时间模型下的最短路径查询问题。文献[32]中,图上每一条边均被赋予一组聚集属性,该聚集属性表示了这条边在不同时刻呈现的状态。文献[34,35,36,37,38]研究了连续时间模型下的最短路径查询问题。文献[34]提出了一种基于Bellman-Ford算法思想的求解方法。对图中任意顶点,该方法迭代计算到达该顶点的最早时刻,并利用这些中间结果,最终计算可得到达终点的最早时刻。最后,根据该时刻找到旅行时间最短的结果路径。文献[35]提出了道路网中的速度流模型,该模型下,图中每条边的通过速度可以用一个分段线性的函数表示。该文提出一个基于Dijkstra算法思想的方法计算速度流模型下的最快路径查询问题。文献[36]则给出了一种基于A*算法的扩展算法。该算法的主要思想是用一个优先队列维护所有待扩展的路径。对任意一个顶点,起点到这个顶点的最早到达时间函数就维护在优先队列中,该算法通过该顶点到终点的欧氏距离和网络中的最大速度,实现从顶点到终点的时间预估。算法根据预估时间弹出队列元素,并找到起点到终点的最短旅行时间路径。文献[37]介绍了如何应用数据挖掘的方法找到各种条件下描述道路通过速度的模型。文献[38]是目前最有效的解决TDSP问题的方法。该方法采用两阶段搜索策略。第一阶段,用优先队列更新图中所有顶点最早到达的时间函数,并最终计算出终点的最早到达时间函数。第二阶段,根据终点的最早到达时间函数找到旅行时间最小的路径。文献[39]研究了时间依赖图下,具有时间限制的代价最优路径的查询问题,并给出了一个有效的两阶段算法计算时间限制下的代价最优路径。
3 结束语
动态图作为现实世界中广泛存在的结构化数据,已经引起人们越来越多的关注。对动态图数据管理方面的研究,具有十分重要的学术意义和广阔的应用前景。本文总结了动态图数据上查询与挖掘算法的主要工作,并对未来的研究方向进行了简要的分析,希望能够借此推动国内对动态图数据开展更系统且深入的研究。
摘要：近年来,图数据模型被广泛地用于刻画现实世界中各种各样的实体间的复杂关系。然而,在现实世界中,描述实体对象的图数据的结构和内容往往不是固定不变的,而是会随着时间的推移发生演绎与进化。目前,越来越多的研究者开始关注动态图数据方面的研究问题,也涌现除了很多优秀的研究工作。总结了近年来动态图上查询算法与挖掘算法方面的基础性研究工作,讨论了现有的工作和动态图研究的发展方向。
动态规划算法分析与研究 篇4
动态规划算法是运筹学的一个分支, 是求解决策过程最优化的一种数学方法, 也是解决NP问题行之有效的解决方案之一。动态规划算法将一个复杂的多阶段问题转换为一系列单阶段问题, 利用各阶段之间的关系, 逐个求解, 由美国数学家R.E.Bellman等[1]最早提出。
动态规划算法是以牺牲存储空间换取计算效率的算法。在实际应用中, 可将某活动过程分成若干个相关联的阶段, 每一阶段都需要作出决策, 从而使整个过程达到最优效果。本文就动态规划算法进行综述, 并就0-1背包问题展开探讨, 具体分析动态规划算法的思想。
1 基本原理
1.1 动态规划算法分类
动态规划一般可分为线性动态规划、区域动态规划、树形动态规划、背包动态规划等4类。如导弹拦截问题是线性动态规划算法的典型应用;统计单词个数等问题是区域动态规划的典型应用;二分查找树问题是树形动态规划的典型应用;0-1背包问题是背包类动态规划算法应用。
1.2 动态规划算法基本原理
动态规划算法的基本思想是将问题分解成若干互相关联的阶段, 将子问题在各阶段按照一定的次序排列, 对某个给定的阶段状态先求解子问题, 然后从子问题的解中得到原问题的解。对于重复出现的子问题, 只在第一次遇到时对它进行求解, 并将求得的解保存起来, 以备后续状态中再次使用。如图1所示, 即解决A问题;依赖于解决阶段B的若干个子问题, 解决B阶段问题依赖于解决C阶段的若干个问题, 以此类推直至所有问题解决。
从基本原理可知, 每一次新的“特例”问题的求解结果都需要保存在临时表中, 因而耗费一定计算空间;另一方面, 由于新的计算过程可通过已经存在的结果加以计算, 从而降低了计算的时间复杂度, 也符合发现问题、求解问题、知识积累学习、知识再利用的基本思想。
1.3 适用范围
动态规划算法适用一定的范围和前提约束, 超出了特定条件, 便失去了作用。动态规划的问题必须满足最优化原理和无后效性。具体如下: (1) 最优化原理。一个最优化策略不论过去状态和决策, 对前面决策所形成的状态而言, 余下的各决策必须构成最优策略, 是典型的局部最优化; (2) 无后效性。将各阶段按照一定的次序排列后, 对于某个给定的阶段状态, 此前各阶段的状态无法影响未来的决策。即对于已经解决的子问题, 不会被后续问题所改变, 又称为无后效性; (3) 子问题的重叠性。动态规划将原来具有指数级时间复杂度的搜索算法改进成具有多项式时间复杂度的算法。其中的关键在于利用空间冗余保存过程知识, 这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术, 在实现过程中, 不得不存储产生过程中的各种状态, 所以其空间复杂度要大于其它算法。
2 动态规划算法应用实例———0-1背包问题
用动态规划算法求解实际问题时, 首先要建立动态规划模型, 一般需要进行如下几个步骤: (1) 分析问题, 界定最优解的特征; (2) 划分问题阶段, 定义阶段计算目标; (3) 求解阶段结论, 形成决策机制, 存储知识集; (4) 根据计算最优值时得到的信息, 构造出一个最优解; (5) 设计程序, 编写相应代码[2]。
例如0-1背包问题, 空间复杂度O (S) =N*C, N=物品个数、C=背包容量, 最优解为选取n件物品 (0≤n≤N) , 使得V最大;背包问题是N阶段问题, 每个阶段有j个子问题, 状态定义为在C=j, N=i的状态如何决策的过程, 决策函数为f (i, j) , 分析可知f (i, j) 决策如式 (1) 所示, 其中v (i) 是第i个背包的V值, 此为决策的核心算法[3]:
当v (i) ≤j时, f (i, j) 取f (i-1, j-v (i) ) +v (i) 和f (i-1, j) 的最大值;当v (i) >j时, 第i个背包无法放入, 因而求解f (i, j) =f (i-1, j) 。
式 (1) 中, f (i-1, j) , f (i-1, j-v (i) ) 都已求解, 因而f (i, j) 可以计算出来。
3 动态规划算法与贪心算法比较
动态规划算法和贪心算法都是解决最优问题的递推类经典算法, 均由局部最优解来推导全局最优解, 因而这两个算法具有相似性。但两者之间也有着显著差异。
贪心算法每步决策都无法改变, 且成为最终决策方案中的一个确定步骤, 其每一步均是在已经抉择的结果集外的最优选择, 前面决策结果不保存并为后续决策的过程引用, 如式 (2) 所示。
动态规划算法全局最优解中一定包含某些局部最优解, 但当前状态的最优解不一定包含前一个状态的局部最优解, 因而它和贪心算法不一样, 需要计算出每个状态 (每一步) 最优解, 并保存起来备后续状态计算引用。
贪心算法在时间复杂度、空间复杂度方面优于动态规划算法, 但“贪心”判定规则 (决策依据) 却难以确定, 即V (x) 函数的选取, 使不同的决策依据得出的结论可能不一致, 影响最优解的生成。
利用动态规划算法解决符合条件的问题时, 一般可以在有限时间内解决问题, 但该算法需要暂存已经计算的结果, 因而动态规划需要很大空间。虽然可以使包含同一个子问题的所有问题共用一个子问题解, 从而体现动态规划的优越性, 但是以牺牲空间为代价的。为了有效访问已有结果, 加上数据不易压缩存储, 因而空间矛盾比较突出。动态规划的高时效性往往要通过大的测试数据体现出来。因而, 如何在不影响运行速度的条件下, 解决空间溢出问题, 是动态规划需要解决的, 也是今后研究的热点问题[4]。
4 结语
本文就动态规划算法的基本概念、应用场景、适用范围、基本原理进行阐述, 并结合0-1背包动态规划法具体求解过程、思路进行分析, 比较动态规划算法和贪心算法的异同点, 指出规划法存在的空间复杂度大等问题, 对理解动态规划法的意义提供参考和指导。
参考文献
[1]百度百科.动态规划[EB/OL].http://baike.baidu.com/view/28146.htm, 2013-12-06.
[2]周佳, 蒋玉明.遗传算法和动态规划综述[J].2009, 16 (2) :18-19.
[3]孙建中.0/1背包问题动态规划算法的探讨[J].现代计算机, 2005, 12 (4) :106-107.
动态规划算法综述 篇5
随着全球能源和环境问题的日益突出,风能等可再生能源发电技术得到迅速发展,风电并网的规模也越来越大[1,2]。由于风电出力具有很强的不确定性,含风电场的电网日前发电调度问题常描述成为一个含有随机变量的动态经济调度(DED)问题[3,4]。为了使获得的发电调度计划对于风电场出力不确定性具有适应性,通常采用场景法,通过对风电场出力随机变量进行抽样模拟,进而将随机模型转换为确定性DED模型[5,6,7,8,9,10]。由于随着抽样的场景数目的增多,场景法求解随机DED问题的模型维数将快速增大,直接求解非常费时,因而目前该方法主要应用于中小型系统的优化调度,应用于实际大型电网将面临模型维数太大、求解时间太长的问题。
另一方面,由于发电机组相邻时段出力的变化量存在爬坡率的限制,含风电场的电网日前发电调度问题是一个含有一天所有时段变量的联合优化模型,所有时段变量的同时求解是导致问题维数太大的另一个关键因素。动态规划(DP)法根据最优性原理,即Bellman方程可实现对于日前发电优化调度问题各个时段决策量的解耦求解[11,12]。然而,实际大电网机组众多,每个时段各个机组出力组成的状态维数非常之大,DP法应用于大电网发电调度问题将不可避免地面临着“维数灾”难题。
近似动态规划(ADP)理论通过近似描述值函数与状态量之间的关系来克服“维数灾”难题,文献[13,14]应用ADP理论求解大规模机组组合(UC)问题,不过没有考虑风电随机性对于电网UC的影响。文献[15,16]将ADP理论应用于含风电和储能装置的小型系统优化调度。文献[17]将含有单一风电场和抽水蓄能电站的电力系统随机DED问题描述为随机型存储模型,以抽水蓄能电站水库的储水电量作为系统的存储水平,并采用ADP算法克服随机规划问题中目标函数含有数学期望计算的难题。然而,所提方法只适用于必须含有抽水蓄能电站的电网调度问题;且建立的模型中并没有考虑网络安全约束,获得的调度计划无法满足工程应用需求;另外,目标函数采用机组出力的一次函数,能否适应于DED问题通常采用的二次目标函数还有待进一步验证。
由于目前国内大部分省级电网中不含有抽水蓄能电站,对于不含有抽蓄电站的大型电网,如何应用ADP算法求解其随机DED问题,同时考虑网络安全约束的影响,对于扩大ADP算法在求解随机优化调度问题方面的适用范围,无疑具有重要的实用意义。因而,本文以系统中多个风电场出力的日前预测曲线为基础场景,借助拉丁超立方抽样生成风电场出力误差场景。以当前时段的系统正旋转备用容量作为资源存储量,列写了相邻时段关系的系统状态转移方程,从而建立了不含抽水蓄能电站电网的随机DED问题的随机型虚拟存储器模型(VSM)。在考虑网络安全约束的条件下利用误差场景对随机DED问题各个时段的值函数进行训练,利用训练得到的值函数对预测场景下的VSM进行求解,得到考虑风电出力随机性影响的常规机组日前发电出力计划。
1 随机型VSM描述
存储模型通过设置一个表示系统资源存储量的变量作为系统的状态变量,很好地解决动态规划问题状态的“维数灾”。由文献[17]可知,对于含有抽水蓄能电站的电网,可以方便地以抽水蓄能电站水库的储水电量作为系统的资源存储量,但对不含抽水蓄能电站的电网,在系统中难以找到可直接表示系统资源存储量的变量,因此如何选取系统的资源存储量,成为此类系统存储模型构建的难点和应用ADP算法求解该类系统随机DED问题的关键。
由于在一般电力系统中,系统的旋转备用容量反映了系统的可调控发电能力,相当于存储在系统中可用于平衡风电场出力随机波动和负荷需求变化的容量,由于存储模型只设置一个表示资源存储量的变量,故本文选取系统的正旋转备用容量作为系统的资源存储量,并根据相邻时段的系统正旋转备用容量的变化关系,列写出系统的状态转移方程,从而建立适用于一般电力系统随机DED问题的VSM,并采用ADP算法求解。
1.1 目标函数
优化目标取常规机组总发电燃料耗量最小,由于风电出力的随机性,目标函数应表示为风电的各种可能出力下对应的常规机组总发电燃料耗量的期望值最小,如式(1)所示。
式中:T为调度周期总的时段数,本文取T=96;ΔT为每个时段的持续时间,即15min;St为t时段系统所处状态;xt为决策变量向量;Ct(St,xt)为时段t所有NgNg台常规机组的燃料耗量,
1.2 约束条件
1)基本约束
式中:Ploadj,t为负荷节点j在时段t的功率预测值;Nd为负荷节点数;Pwk,t为风电场k在时段t的出力值,为随机变量;Pi-和P-i分别为机组i的有功出力上、下限;rdi和rui分别为机组i的向下、上爬坡率。
其中,第1个式子为功率平衡方程,第2个式子为常规机组的有功出力上、下限约束,第3个式子为常规机组的爬坡约束。
2)网络安全约束
式中:Fl,t为时段t第l条支路的传输功率;Flmin和Flmax分别为第l条支路传输功率的下限和上限,一般Flmin直接取Flmax的负值;Fij,t为第i个安全断面中第j条支路在时段t的传输功率;Ωi为第i个断面包含的支路集合;FΩimin和FΩimax分别为第i个断面的安全下限和上限。
其中,第1个式子为输电线路安全约束,第2个式子为断面安全约束。支路传输功率Fl,t可由直流潮流模型近似表示为:
式中:Gl,i,Dl,j,Wl,k分别为第i台常规机组、第j个负荷和第k个风电场对支路l的功率转移分布因子,其值由网络结构和支路参数确定[18]。
由于实际大电网支路数众多,若在模型中加入所有的支路安全约束,优化模型的规模会大幅度增加,进而导致求解速度的快速下降。本文采用“求解→安全校验→添加越限支路约束再求解”循环的方法,直至所有支路功率都通过安全校验,这样可加快求解速度,并得到满足所有支路安全约束的最优解[19]。
3)旋转备用约束
为应对风电出力的不确定性和负荷预测误差,系统中应保留一定的旋转备用容量以保证系统安全可靠运行。系统及各常规机组备用约束如下:
式中:sui,t和sdi,t分别为机组i在时段t能够提供的正旋转备用容量和负旋转备用容量;T10为要求的机组旋转备用响应时间,取10min;Su,t和Sd,t分别为系统在时段t的正、负旋转备用容量;Lu和Ld分别为负荷对系统正、负旋转备用的需求系数,通常设定为2%~5%;wu和wd分别为风电场出力对系统正、负旋转备用的需求系数,根据目前国内风电功率预测系统的预测误差范围,可设定为10%~25%;P-wk为风电场k的额定出力。
4)状态转移方程约束
通过将系统正旋转备用容量Su,t设置为系统在时段t的资源存储量,取系统时段t的状态向量为St=(Su,t,Pw,t),则系统的状态转移方程如下:
式中:Ps,t为时段t系统正旋转备用容量相对上一时段的变化量;Pw,t为时段t所有风电场出力组成的向量。Ps,t既与时段t风电场出力随机变量Pw,t有关,又与时段t常规机组出力决策变量xt有关。该方程的物理意义是系统状态在随机变量和决策变量共同作用下的演化形式,体现了相邻两个时段系统正旋转备用容量之间的耦合关系。
5)系统旋转备用变化量约束
每一时段系统正旋转备用容量相对上一时段的变化量有一定的范围限制,这个范围可由风电出力变化量与负荷变化量确定。当风电出力增加大于负荷增长时,系统正旋转备用变化量应满足:
当风电出力增加小于负荷增长时,系统正旋转备用变化量应满足:
2 ADP思想与模型处理
2.1 DP的局限性
基于Bellman的最优性原理,求解多阶段决策问题时,严格意义上DP可以求得全局最优解[20]。对初值问题DP的求解决策过程如图1所示。图中:Jt为时段t的收益;St=fs(St-1,xt)为时段t-1到时段t的状态转移方程。令xt*为时段t的最优决策,求解时先从最后时段开始往前逐一时段递推,依次得到各时段最优决策和值函数与状态关系xT*(ST),VT(ST),x*T-1(ST-1),VT-1(ST-1),…,x1*(S1),V1(S1)的表达式,其中,Vt为时段t的值函数,即从时段t到末时段T内所有阶段收益总和的最优值,然后代入初始状态S0并结合状态转移方程,从前往后逐一求得各时段的最优决策和值函数。
由DP的求解过程可以看出,应用DP求解DED问题,当机组出力连续时,由于爬坡率约束的存在,相邻时段之间的决策变量具有耦合,机组出力可行域也是随不同时段变化的,难以用解析表达式描述决策、收益与状态之间的关系;当机组出力离散时,可以对所有的机组出力组合情况进行评估,但随着机组数、时段数、状态变量数的增加,组合情况呈指数式增长,将面临“维数灾”问题。
2.2 ADP思想
由DP的决策过程可知,DP在求解DED问题时虽然能够求得全局最优解,但对于实际大型电网来说其推导过程过于繁琐,求解的复杂程度难以接受。近年来,Powell等人将ADP方法运用到具有随机性可再生能源接入的电力系统调度中,很好地克服了DP求解DED问题的局限性。
由2.1节可知,DP在决策前需从后往前逐一推导每一状态St对应的值函数Vt(St)的表达式,这是DP求解的关键和难点。如果假定各时段值函数的表达式Vt(St)已知,则在求解当前时段t时,只需在St-1的基础上结合状态转移方程St=fs(St-1,xt)和当前时段值函数Vt(St),即可求得当前时段t的最优决策xt*。但各时段值函数的精确表达式Vt(St)事先无法预知,这为模型的解耦求解带来困难,ADP的思想就是通过采用近似值函数来逼近描述时段t的值函数与状态St的关系,从而实现模型的时段解耦求解,进而可依次求得各时段的近似最优决策xt。由此可以看出,ADP算法的关键就是近似值函数的合理表示。
2.3 模型处理
为了方便应用ADP对随机DED问题的VSM进行求解,需对模型进行一些必要的处理。为此将每个时段假想成两个阶段,分别对应决策前状态(Su,t,Pw,t)和决策后状态(Sxu,t,Pw,t)[21],并定义S^u,t(Pw,t)为时段t观察到随机变量的实现值后状态的变化量。其中,决策前状态(Su,t,Pw,t)表示仅考虑随机变量引起的状态变化量S^u,t(Pw,t)的作用,而未做出决策前的系统状态;决策后状态(Sxu,t,Pw,t)表示做出最优决策后系统的状态。因此系统状态转移方程转化为:
式(9)表示假定时段t观察到的风电变化量直接作用于系统正旋转备用容量,由Sxu,t-1增加演化为Su,t;式(10)表示做出决策得到常规机组出力值xt后,Su,t加上系统正旋转备用容量的实际变化量Ps,t(xt),并扣除没有实际作用效果的后,最终得到决策后系统正旋转备用容量Sxu,t。引入决策前状态和决策后状态后,可得时段t的决策前状态值函数Vt*(Su,t,Pw,t)和决策后状态值函数Vtx(Sxu,t,Pw,t)如下:
此处Πt为由式(2)至式(5)和式(7)、式(8)所确定的xt的可行域。
由式(9)可知,从时段t的决策后状态到时段t+1的决策前状态,仅考虑随机因素的作用,所以式(12)中含期望计算,这给求解带来不便。因此在应用ADP算法求解随机DED问题时,除了要解决近似值函数的合理描述问题,还要处理好系统中随机因素引起的期望计算。
根据文献[21]可知,对于资源分配问题,对于没有明显特性的值函数,可以通过查表与聚类、参数模型、非参数模型等一般工具获得近似值函数;而对于值函数相对资源存储量具有连续、线性或近似线性、非线性(凹性或凸性)性质的,可以采用接近其特性的函数对值函数进行近似。文献[22]给出了对于线性目标函数存储模型采用满足凸性的分段线性函数近似值函数的收敛证明,由于上述VSM的目标函数是二次函数,和线性函数一样具有凸函数特性,因而本文采用满足凸性的分段线性函数来逼近其决策后状态的值函数Vtx(Sxu,t,Pw,t)。因此,通过在决策后状态Sux,t的取值区间上取离散断点R=ρ,2ρ,…,mρ,令vt(Pw,t)=[vt(Pw,t,ρ),vt(Pw,t,2ρ),…,vt(Pw,t,mρ)]T为时段t值函数的斜率向量,其中,m为存储量的所有分段数,ρ为每段长度,则t时段决策后状态的近似值函数可表示如下:
式中:Vtb为时段t值函数的截距;ytr为第r段的存储量。
将式(13)代入式(11),则随机DED问题的VSM可转化为如下不含期望运算的确定性二次规划模型:
3 VSM的ADP求解
3.1 近似值函数的求取
应用ADP求解VSM时,近似值函数t(Sxu,t,Pw,t)对精确值函数Vtx(Sxu,t,Pw,t)的近似精度越高,则近似最优决策xt越接近xt*。为获得高质量的近似值函数,首先根据确定性优化模型求解结果对近似值函数的斜率向量和截距进行初始化,然后扫描误差场景,在每个场景下逐个时间段求解二次规划问题(式(14)),并根据求解结果采用逐次投影近似路径(SPAR)算法[16]修正每次迭代的近似斜率值vtn(Pw,t)和截距值Vntb,直到得到收敛的近似值函数tn(Sxu,t,Pw,t)。SPAR算法对近似值函数的求取过程如图2所示。图中,tn(Sxu,t,Pw,t)为第n次迭代所得近似值函数,Vtx(Sxu,t,Pw,t)为事先未知的精确值函数,和vtx分别为第n次迭代时段t值函数的斜率近似值和时段t值函数斜率的精确值。
斜率向量和截距初始化时,首先根据确定性优化模型的决策结果,获得各时段的资源存储水平Sux,,t0及相应时段的值函数值Vt0。斜率初值设定时以(Sux,,t0,Vt0)作为该时段值函数的极小值点,且其两边各段的斜率符号相反,与极小值点相邻的两段关键点的斜率初始值可根据优化目标的物理意义合理设定,本文主要根据常规机组的煤耗特性系数确定,其余段的斜率根据满足值函数凸性的斜率单调递增特性依次设定。在初始斜率向量给定后,初始截距V0tb根据式(15)确定。
式中:为时段t值函数的斜率初始值。
给定初始斜率向量和截距后,依次在每个场景下逐个时段求解二次规划模型(式(14)),再进行斜率和截距修正,斜率修正过程参见文献[17],得到第n个场景迭代的近似斜率分量和近似值函数值tn(·,Pnw,t)后,根据式(16)计算截距修正值Vntb为:
实际计算中,可只对图2所示关键区域的两段斜率进行修正,再结合截距修正,以节省值函数训练时间,提高计算速度。
3.2 ADP求解过程
ADP求解随机DED问题VSM的步骤如下。
步骤1:求解预测场景对应的确定性经济调度模型,得到各时段决策xt0、存储量和值函数值Vt0。
步骤2:初始化各时段的近似斜率向量,根据初始斜率值和来确定初始截距V0tb。
步骤3:借助拉丁超立方抽样生成基于预测场景P0w,1,P0w,2,…,P0w,T的误差场景样本,获得N个误差场景Pnw,1,Pnw,2,…,Pnw,T(n=1,2,…,N)[23];令n=1,t=1。
步骤4:若n>N则转步骤11,否则继续。
步骤5:若t>T则转步骤9;若t=1,则令的上限和下限设置为;否则计算决策前的资源存储量
步骤6:求解式(14)的二次规划模型,得到最优决策xtn,并计算得到决策后的资源存储量
步骤7:若t<T,则进行斜率和截距修正。
步骤8:t增加1,转步骤5。
步骤9:对场景n的求解结果进行网络安全校验,若存在支路越限,则将越限支路的安全约束加到式(14)所示模型,令t=1,转步骤5;若不存在支路越限,则转步骤10。
步骤10:n增加1,转步骤4。
步骤11:求解预测场景的VSM,获得调度计划。
4 算例分析
为验证本文所建立的随机DED问题的VSM和ADP求解算法的有效性,对某个不含抽水蓄能电站省级电网的发电调度进行建模和求解。以该省网2015年1月5号的数据为例,共有85台常规机组,其中火电机组46台,装机容量为14 560 MW;水电机组39台,装机容量为8 208 MW。风电场5座,额定容量分别为3 958.5,1 140,192,99,49.6 MW,其并网站点见附录A图A1,其中前两个风电场的出力预测曲线,以及系统日前负荷预测曲线和外送功率曲线见附录A图A2和图A3。系统共有线路498条,3个安全断面,各断面数据见附录A表A1。
假定风电出力预测误差服从正态分布,数学期望为各时刻的风电出力预测值,标准差为预测值的20%,借助拉丁超立方抽样方法分别生成20,50,100,200个误差场景进行求解。以20个场景的求解为例,训练过程中值函数变化如图3所示。可以看出,训练刚开始时误差场景的值函数与由确定性模型优化结果反推的值函数非常接近,随着训练的进行,后面误差场景求解得到的值函数慢慢趋向收敛,整个训练过程耗时198.39s。
本文构建的随机VSM和ADP算法求解结果与场景法求解结果的值函数对比见附录A图A4。采用本文模型和ADP算法求得的一天总发电燃料耗量为7.572 027万t,场景法求得的总发电燃料耗量为7.487 056万t,且由附录A图A4中各时段的值函数比较可以看出,ADP算法与场景法求得的燃料耗量结果十分接近。以上比较充分说明了本文建立的不含抽水蓄能电站的随机DED问题的VSM及ADP算法求解的正确有效性。
ADP算法求得的系统正旋转备用与场景法优化结果比较如图4所示。可以看出,两种方法得到的系统正旋转备用的整体变化趋势也基本一致,只是ADP算法得到的系统正旋转备用整体上比场景法略微大一些。
两种方法得到的机组出力计划比较如图5和图6所示。由图5可以看出,两种方法得到的火电机组的出力计划基本一致,部分机组在某些时段出力存在微小偏差。由图6可以看出,场景法得到的水电机组出力存在很大的跳跃,而ADP算法得到的水电机组出力则变化比较缓慢,这是由于水电机组功率调节速度快,每个时段可调节功率范围较大,因此场景法求解时在满足各种约束的条件下为了优化目标函数而使得机组出力会有较大的波动跳跃,这与水电机组自身的调节特性相吻合,而在采用VSM和ADP算法求解时由于式(6)至式(8)的约束,限制了系统正旋转备用的变化,使得备用响应容量较大的水电机组的出力变化也较为缓慢,这更符合实际电网运行调度中对机组出力的调控要求。
同时,由于模型中添加了断面安全约束,能够保证所获得调度方案下系统的安全运行。以20个误差场景的优化为例,与不含断面安全约束求解结果对应的安全断面2的输电功率对比如表1所示。可以看到,在未加断面约束时优化得到的总燃料耗量为75 706.61t,但断面2在某些时段存在功率越限;加入断面约束后,总燃料耗量为75 720.27t,比不加断面约束时增加了13.66t,但断面2功率都小于安全极限。因此,在模型中加入网络安全约束后,为了使系统的关键线路和断面的输送功率在限定范围内,机组的出力安排可能会使得系统总的燃料耗量有所增加,这在一定程度上使得系统的经济效益有所下降,但却避免了系统运行在不安全状态,对系统的安全可靠运行具有重要意义。
接下来分别将该算法与场景法在20,50,100,200个场景的情况下进行比较,验证该算法的计算性能。使用计算机为Intel(R)Core(TM)i7-4900MQ CPU 2.80GHz/32GB内存,计算结果如表2所示。由表2可见,场景法在场景数较少时具有较快的计算速度,但随着场景数的增加,计算所需内存和时间都大幅增长,这在很大程度上限制了场景法的应用,尤其是对于风电场数目多需要抽样很多个场景来准确模拟风电出力特性的大型电网调度问题,场景法求解将会受到计算机内存容量限制。而ADP算法由于实现了对各个场景和各个时段的解耦求解,将大规模优化问题分解成若干个小规模优化问题逐个求解,所以随着场景数的增加,所需内存无明显增长,求解时间也基本只增加了新增加场景进行值函数训练所增加的时间。对于100个场景求解时间只有16min左右,约为场景法的1/12;即使对于200个场景求解时间也只有33min左右,计算速度明显提高。
同时,将所提出算法与基于极限场景集的鲁棒优化调度(RS)方法比较[24]。为保证极限场景能覆盖95%的可能风电出力,取风电功率的变化范围为[μ-2σ,μ+2σ],其中,μ为期望值,σ为标准差值,由于系统中含有5个风电场,故共有25即32个极限场景,RS方法求解总耗时6 378.83s,优化结果的总燃料耗量为75 654.04t。
由此可以看出,虽然RS方法比场景法更能保证对风电出力大范围波动的适应性,但其目标函数值也更大,且在极限场景只有32个的情况下,其求解时间已经分别达到50个场景下场景法和ADP算法的3.3倍和12.9倍,当系统中风电场数目增大时,其求解时间将增加得更为明显。因此,ADP算法与RS方法比较同样能够大幅提高计算速度。
另外,由于极限场景的数目与风电场数目呈指数关系增长,随着风电场数目的增大,RS方法和场景法一样会面临由于问题规模过大超出计算机内存容量限制进而无法求解的问题。因此,ADP算法对于含多个风电场的大型电网随机优化调度问题具有更好的适应性,在求解速度上相对RS方法及场景法具有明显的优势,能够很好地满足应用于实际大型电网日前发电调度的要求。
5 结语
本文将ADP理论推广应用于不含抽水蓄能电站的电网随机DED问题,以正旋转备用容量为存储量,建立不含抽水蓄能电站的电网安全约束随机DED问题的VSM,并通过与场景法和鲁棒优化调度方法求解结果的比较分析验证了所建模型和求解算法的正确有效性,为ADP理论应用于快速求解一般大型电网的随机DED问题提供了新途径。ADP算法实现了对随机优化调度模型各个场景和各个时段的解耦求解,将一个大规模优化问题分解为一系列小规模优化问题,有效提高了对大电网随机优化调度模型的求解速度。采用ADP算法求解随机型VSM的优化结果中对应的水电机组出力变化比场景法更加合理,符合实际电网运行调度中对机组出力的调控要求。另外,对于含有抽水蓄能电站的电网调度问题,也可以采用本文提出的VSM建模方法并通过ADP算法快速求解;即便是对于含有多个抽水蓄能电站的电网调度问题,文献[17]的建模方法由于只适用于含单一抽水蓄能电站的电网,会存在建模困难,而本文的VSM建模方法同样能够适用。
本文研究中采用分段线性函数对值函数进行近似,所得调度方案对应的目标函数值比场景法的结果有所增大,如何提高值函数的近似精度,以获得更优的调度方案是本文下一步工作重点;同时,本文建立模型中未考虑不同时段机组启停状态的变化,如何应用ADP算法求解随机机组组合问题是本文的进一步研究方向。
附录见本刊网络版(http://www.aeps-info.com/aeps/ch/index.aspx)。
摘要：针对大电网安全约束随机动态经济调度(DED)问题的求解时间太长,提出了应用近似动态规划算法快速求解不含抽水蓄能电站电网的安全约束随机DED问题的方法。建立了随机DED问题的虚拟存储器模型,以系统的正旋转备用容量作为存储变量,构建系统相邻时段的状态转移方程,并考虑了各输电线路和断面的安全约束。以风电场日前功率预测曲线为基础,通过拉丁超立方抽样产生风电场出力的误差场景,并逐一场景递推求解每个时段的二次规划模型以对各个时段的值函数进行训练,形成收敛的值函数,再代入预测场景求解以获得最终的优化调度方案。该方法实现了对随机DED模型各个场景和各个时段的解耦求解,将一个大规模优化问题分解为一系列的小规模优化问题,有效提高了对大电网随机DED模型的求解速度。以某一实际省级电网为算例,通过与场景法和鲁棒优化调度方法的比较验证了所提出模型和求解方法的正确有效性。
动态规划算法综述 篇6
动态规划策略是一种将复杂的问题分解为更小的、相似的子问题, 并存储子问题的解而避免计算重复的子问题, 以解决最优化问题的算法策略。
动态规划主要应用于最优化问题, 这类问题会有多种可能的解, 每个解都有一个值, 而动态规划找出其中最优解。在求解的过程中, 动态规划也是通过求解局部子问题的解达到全局最优解, 允许这些子问题不独立, 也允许其通过自身子问题的解作出选择, 对每一个子问题只解一次, 而且把结果保存起来, 避免重复计算来提高效率。即动态规划算法的有效性依赖于问题本身具有的两个重要性质:最优子结构性质和子问题重叠性质。
动态规划策略解决问题的基本步骤:
1) 找出最优解的性质, 并刻划其结构特征;
2) 递归地定义最优值;
3) 以自底向上的方式计算出最优值;
4) 根据计算最优值时得到的信息, 构造最优解。
2. 动态规划方法解决英文文档排版问题
2.1 英文文档排版问题
给定有n个英文单词组成的一篇文章, 每个单词的长度 (即字符个数) 分别为l1, l2, ……ln。现要将该段文章“漂亮”地排版出来。排版规则:排版时每行最多打印M个字符;每一行行首不得留空格;单词与单词之间至少有一个空格;单词不允许被打破。
解决方法:如果在某一行中安排单词i到单词j, 则按排版规则, 这一行中恰好打印个字符 (包括这j-i+1个单词间的j-i个空格) 。多余的空格数为。除文章最后一行外, 希望每行多余的空格数尽可能少。本算法中, 以各行 (最后一行除外) 的多余空格数的立方和达到最小作为“漂亮”的标准。
2.2 最优解的结构
记s (i) 为由单词i到单词n所组成的文章的各行 (除最后一行) 的多余空格数的立方和, b (i) 记载单词的前进位置。例如对由单词3到单词n所组成文章的排版, 若b (3) =10, 单词3到单词10构成一行, 单词11到单词b (11) 构成一行……。
s (i) 的计算方式如下:假定单词i最多可与单词j构成一行 (j>=i) , t为i到j间的任意整数, 如果从t位置分割, 即单词i到单词t作文一行, 而从单词t+1到单词n构成文章的剩余行。
可以证明, 问题的关键在于:如果计算出的s (i) 是单词i到单词n漂亮排版的各行 (除最后一行) 的多余空格数的立方和, 则s (t+1) 是单词t+1到单词n漂亮排版的立方和。因而文章排版问题的最优解包含着其自身子问题的最优解。这种最优子结构性质是问题可以用动态规划方法来求解的最重要特征。
2.3 利用递归来定义最优值
若计算s (i) (1<=i<=n) 的最小值为c[i], 则原问题的最优值为c[1]。显然, 如果单词Fi (1<=Fi<=n) 到单词n可以构成一行, 而单词Fi-1到单词n则超过一行, 显然c[i]=0 (Fi<=i<=n) ;对于1<=i<=Fi-1, 若单词i最多可与单词j构成一行 (j>=i) , t为i到j的任意整数, 如果从t位置分割, 即单词i到单词t作文一行, 而从单词t+1到单词n构成文章的剩余行。c (i) 为所有t取值的的立方和最小者。递归式如下:
另外, 用p[i]记载每次c[i]断开的位置, 求出c[1]后, 从p[1]向后退, 就可以知道漂亮排版中每行单词的开始位置和结束位置, 从而能够实现漂亮的排版。
2.4 计算最优值
如果直接用c[i]的计算公式, 进行递归计算需要耗费指数计算时间。然而不同的子问题的个数只是n的线性次。用动态规划方法求解, 可按照其递归式以自底向上的方式来计算。在计算过程中, 保存已解决的子问题解。因而每个子问题只计算一次, 在后面需要时只要查找一下, 通过这种方法避免了大量的重复计算, 因而得到多项式时间的算法。下面给出计算c[i]的动态规划算法:
经过分析可以得出, 算法的空间复杂度为用O (n) , 时间复杂度O (n2) 。
2.5 构造最优解
通过上面算法, c[1]保存了单词1到单词n所组成的文章的各行 (除最后一行) 的多余空格数的最小立方和。还有一个问题, 这些单词怎样分行, 构成一片漂亮文章呢?p[i]中已经保存了构造最优解所需要的信息, 从p[1]出发, 单词1到单词p[1]构成一行, 单词p[1]+1到单词p[p[1]+1]构成一行……即得出问题的一个最优解。算法描述如下:
2.6 进一步讨论
如果希望排版的效果不仅是各行 (最后一行除外) 的多余空格数的立方和达到最小, 还能够实现如同中文排版的两端对齐效果。只需要增设一个Space数组, Space[i]保存的是在漂亮排版下, 单词i所在行的多余空格数。这样, 在漂亮排版时, 只要将每行的多余空格均匀分配在该行的若干单词间。
3. 结束语
算法在c语言环境下得到验证, 运行结果证明了算法设计是可行的, 正确的获得了漂亮的排版效果。
动态规划方法中, 每步所作的选择往往依赖于相关子问题的解。因而只有在解出相关子问题后, 才能做出选择, 所以动态规划算法通常是以自底向上的方式解各子问题的解, 进而求出原问题的解。实际求解过程中, 子问题会有大量的重复, 而动态规划就是对重复出现的子问题, 只在第一次遇到时进行求解, 并把解保存起来, 让以后再遇到时直接引用, 不必重新求解。
摘要：动态规划策略是求解最优化问题的一种方法, 该文主要研究其求解问题的基本思想及具体步骤, 详细分析其用于英文文档的排版问题上的算法设计, 并给出其算法实现。
关键词：动态规划,漂亮排版,最优子结构
参考文献
[1] (美) Cormen T.H..算法导论[M].北京:机械工业出版社, 2006.
[2]王晓东.计算机算法设计与分析[M].北京:清华大学出版社, 2010.
[3] (沙特) M.H.Alsuwaiyel.算法设计技巧与分析[M].北京:电子工业出版社, 2004.
[4] (美) Kleinberg J..算法设计[M].北京:清华大学出版社, 2007.
动态规划算法综述 篇7
但是，大部分DP算法有一个较为明显的不足，即视差图容易出现横向的“条纹”瑕疵，究其原因是缺少行、列方向上连续视差结果的融合。针对上述问题，诸多学者做了一些有建设性的研究。Birchfield等人[13]提出将竖直方向匹配度较高的区域视差拓展到低可信度区域的做法，该算法虽然实现了较快的运行速率，但扫描线间的视差结果较差，另外在算法优化部分可能会造成错误视差扩散到全局的不利影响;Gong and Yang[14]则提出了一种提高二通道DP算法可靠性的做法，即通过在垂直和水平两个方向上分别进行动态规划计算搜索路径，该算法确保了较高的匹配精度，但要借助编程图形显示卡来获取视差图的实时效果;另外Leung等人[15]提出了一种迭代动态规划(Iterative Dynamic Programming,IDP)算法，其通过多次迭代算法，来增强视差图的连续性，而导致的较长运行时间不利于实验操作。
鉴于此，本文提出一种基于改进双向动态规划的视差图获取算法，以修正后的ASCF为代价函数，并构建新的全局能量函数，通过改进双向动态规划寻径来得到最终的稠密视差图。经验证，所提算法的匹配效果良好，并获得了稠密视差图。
1 新型视差图获取算法的研究
DP算法的实质是将对应点的匹配问题转化为寻找某一能量函数的全局最优解，而构造出合适的像素间匹配的代价函数是构建全局能量函数的重要前提，所构建的代价函数优劣与否直接影响着立体匹配算法的运行速率和精确度，其中代价函数主要包含有差值绝对值和函数(Sum of Absolute Differences,SAD)、差值绝对值(Absolute Difference,AD)、差值平方(Squared Differences,SD)等，此类代价函数在算法构造上相对简单、易于操作，但由于忽视了不同区域间跃变的影响，会产生较高的误匹配率。为了克服在交叉深度不连续区域的匹配问题，学者们在不连续区域为每一个像素选择自适应匹配窗口，其中Yoon等人[16]将几何数学的邻近性和像素色度空间融入到权值计算当中，此举有效地抑制了立体匹配中的不确定性，但在构建ASCF的过程中，导致视差非连续区域的误匹配率有所增加。
针对这一问题，提出了一种新型视差图获取算法即改进动态规划双向约束算法，即采用修正后的ASCF，进一步增强原始代价值在视差非连续区域的比重，以确保这一区域的误匹配率有所降低，从而改变构建ASCF的传统方法所导致总体误匹配率高的状况，并参照经典Potts模型[17]构建全局能量函数，考虑到相邻像素视差值保持的一致性准则，增加了视差平滑约束项的比重，提高所构建的全局能量函数的精确度。由于传统的DP算法在求取全局能量函数最优解时存在一个很大的局限性，即易出现“条纹”瑕疵的现象。为了克服这一问题，此算法提出采用扫描线行列双向动态规划来寻找最小匹配代价路径，并对初始视差图的数据项和平滑约束项分别制定了相应的奖励策略。最后，针对出现的错误孤立视差点，通过简单的滤波方法和遵循相关的3个准则予以消除。此算法流程如图1所示。
1.1 修正后的ASCF
Yoon等人[16]基于空间几何距离的相关性和像素间颜色相似性对ASCF进行了详细分析，即将几何数学的邻近性和像素色度空间融入到权值计算当中，其计算公式为
式中:γc和γp分别为控制权值的参数;Δgpq为对应像素的空间几何距离的相关性，即窗口中心像素p和匹配窗口中像素q之间空间坐标的欧几里德距离。
许多学者提出了不同的Δcpq构造方法，其中Salmen等人[18]根据像素点RGB值的内在联系，将Δcpq设定为窗口中心像素p与匹配窗口像素q的RGB值的加权欧几里德距离。由于获得该参数需要通过实验反复测试，以致代价函数的精确度相对较差，图像对的误匹配率也不低。Yang等人[19]对两像素点彩色差值求平均，尽管该构造方法在一定程度上减轻了算法的运算量，但由于忽略了像素点间彩色像素值的相关性，导致代价函数的自适应约束能力减弱，视差保持特性有所降低。
本算法仍采用将图像像素点的彩色像素值转化为CIELab值，Δcpq为窗口中心像素p和像素q的CIELab值的欧几里德距离。另外，对应像素为，待匹配像素为p，相应的代价函数的计算公式为
式中:为目标图像窗口的代价权值;w(p,q)为参考图像窗口的代价权值;为两个匹配窗口视差为d的对应像素的原始代价函数，截断绝对值的计算式如下
式中:Ic为RGB颜色空间的亮度值;Ti为截断门限值，即当亮度值之差大于门限值时取值为门限值。为了减少视差非连续区域的“条纹”瑕疵和错误匹配点，该算法对式(3)做了以下改进，即增加原始代价值在这区域的比重，新的原始代价函数的计算公式为
式中:Ti为截断门限值;Td为视差非连续区域的判断门限，当对应像素的彩色像素值差值的绝对值之和大于或等于在非连续区域的截断门限值时，原始代价值取为截断门限值，反之，取值为差值的绝对值与截断门限值之和中的最小值。
1.2 构建新的全局能量函数
本文构建的全局能量函数仍然只包含平滑项和数据项，其计算表达式如下
式中:为数据项，该代价函数采用的是式(2)中的ASCF，选取最小的视差值为其代价值。其中V(dp,dq)为视差平滑约束项，用来确保相邻像素视差值的一致性，该算法构建新的全局能量函数的思路是在参照经典Potts模型[17]，即
式中:ρI(ΔI)为相邻像素p与q之间的视差值。
梯度ΔI的函数ρI(ΔI)表达式为
式中:s为惩罚项;T为阈值;P是用来增大梯度处的惩罚项。
在构建的新的全局能量函数中，针对平滑约束项作了以下修正
式中:p1为小于p的常参数。
1.3 改进双向动态规划寻径
由式(5)构建的新的全局能量函数可知，立体匹配问题转化为求解一个视差分配d*，即使能量函数E(d)的取值最小
d*=arg min E(d)(9)
求解式(9)所述的能量最小化问题，传统的DP算法忽略了核线间的影响，致使核线与核线间的约束不够，即只是进行单一的行方向上的DP运算，如图1所示为在行方向上进行DP求解示意图，其中图2a是以x,y分别为横、纵坐标，视差搜索范围为d的视差空间图像(DSI)，图2b为只在行方向DP求解的示意图，其目的是为了搜索得到一条从左至右的最小代价路径，而每条路径的长度[20]为。
显然，这种缺少行、列方向上连续视差结果融合的DP算法不能保证全局最优，为了增强纵向像素间视差的约束项，以确保视差图横向条纹“瑕疵”的减少，故提出基于行、列双向的动态规划算法，具体过程如图3所示。
本算法提出了一种由行匹配初试结果来确定相应的奖励策略，即通过减小d*所对应代价函数的比重，以提高其在列匹配中被选中的可能性，初始匹配结果依靠第一次行DP求解得到，同时需在确定的窗口区间内，对数据项制定了合理的奖励策略:情况1，若列方向初始视差梯度变化出现明显错误的视差值点时，其用原来的代价值来赋值;情况2，若在列方向初始视差梯度未出现异常的情况下，而在行动态规划中能够得到匹配的视差值点，那么其值应该赋予较大的奖励值;情况3，其他视差值点则使用较小的奖励值。其表达式为
式中:Ti为截断门限值，如式(4)所述;r一般取相对较小的正数，当r取值过小时，奖励值过小，会造成行方向上的DP效果不明显;当r取值过大时，会使得列方向上的视差值点被选中的概率过大，导致列方向上的DP失去了意义。经过多次实验测试得知，r取值为7时，所得匹配结果较为理想。另外，能量函数的数据项的计算方法与上述平滑项一致，这里就不再累述。
1.4 去除孤立的错误视差点
针对所获取视差图中出现的一些较为明显的噪声点，该算法采用易于操作的滤波方法来去掉孤立点。一般遵循以下3个可靠性准则:1)若该像素点上下邻域像素的视差值相等，则赋予该点视差值与上下邻域点一致;2)若该像素点左右邻域像素的视差值相等，则赋予该点视差值与左右邻域点一致;3)若该像素点周围邻域点的视差值都不相等，则赋予该点视差值为其邻域所有点的视差值均值。
2 实验结果
本算法的实验平台和参考图像来自于Middlebury大学数据库，对其中的Cones,Venus,Tsukuba,Teddy这4幅图像进行了测试，实验中的各个参数k，γc，γp,Ti,Td,T,p,r,s分别取值1,5,19,25,30,5,3,10,3。实验结果如图4所示。此算法以修正后的ASCF为代价函数，并构建新的全局能量函数，通过改进双向动态规划寻径来得到最终的稠密视差图，分别与以ASCF作为代价函数、基于行列双向动态规划(DoubleDP)算法和以SAD作为代价函数的DP算法所获取视差图进行比较。实验视差图在所有区域(All)、非遮挡区域(Non_occ)、视差非连续区域(disc)的错误率做了记录，实验结果如表1所示。从表中分析可知，在优化策略一致的情况下，相较于SAD，采用ASCF来获取视差图误匹配率要低很多，而此算法相对于其他3种算法，误匹配率最低，“条纹”瑕疵方面最少，所获得的视差图效果最好。
%
3 小结
提出一种基于改进双向动态规划的视差图获取算法，以修正后的ASCF为代价函数，并构建新的全局能量函数，通过改进双向动态规划寻径来得到最终的稠密视差图。实验结果表明，该算法能够取得较为理想的效果，与其他3种DP算法相比明显降低了误匹配率，减少了图像中的“条纹”瑕疵。
虽然该算法在降低误匹配率和减少“条纹”瑕疵方面有显著的改善效果，但由于需要计算每个像素在确定窗口的自适应代价值，以致执行时间较长。故今后将使用GPU[21]和多线程[22]的处理方式，以便大幅度地提高算法运行速度，满足实际应用的要求。
摘要：提出一种基于改进双向动态规划的立体图像匹配算法,选用修正后的自适应加权代价函数(Adaptive Support Weight Cost Function,ASCF),然后构建新的全局能量函数,并通过改进双向动态规划来寻径,最后采用简单的滤波方法和遵循3个可靠性准则去除孤立的错误视差点,以获得稠密视差图。实验结果表明,该算法在降低误匹配率和减少“条纹”瑕疵方面有显著的改善效果。