动态规划算法实验报告

动态规划算法实验报告（共7篇）

动态规划算法实验报告 篇1

算法实验报告二 动态规划法

一、实验目的：用动态规划的思想实现动态投资问题。

二、实验要求：掌握动态规划算法设计的基本策略。

三、实验内容：m元钱，n项投资，fi(x)将x元投入第i项项目的效益，目标函数max {f1(x1)+ f2(x2)+ … + fn(xn)}

约束条件x1 + x2 + … + xn = m，xi ∈ N

设Fk(x)表示x元钱投给前k个项目的最大效益 算法实现：投资第k个项目p元钱的效益可表示为Project[k][p],其中0<=k<=n,0<=p<=m;设投资给前k个项目p元 钱的最终总效益为用Benefit[k][p]，其中0<=k<=n,0<=p<=m。设allot[k][p]表示在总投资为p元钱时候，最终分配给第k个项目的钱数解。

四、实验心得：在调试过程中出现了好多小问题，一开始结果不对，我通过单步调试一步步的看待填的二维表中的数据。发现大部分V[i][j]对了，但是有极小数的不对。故而我的结果出现了问题。通过本次实验加深了我对动态规划算法的理解。而且对动态规范编写代码解决一个实际问题有了进一步的认识。即当算法考虑的原问题的每一个子问题，算法都需要计算一个最优解。换句话说，所有算法生成的表项表示算法考虑的子问题的最优解。这时候用动态规范把每一个最优解求出来（利用递归公式），就能够保证最后求得的一定是最优解。而且动态规划有个特点，即它是由底向上，它实现起来就是利用循环，有时用到一层循环即可，有时要用到两层for循环即可以求解出问题。

五：附录：程序代码及结果

#include

void main(){

void jie(int,int,int d[][9]);

void Invest(int m,int n,int f[][9],int g[][9],int d[][9]);

int m=8,n=3,f[4][9],d[4][9];int

g[4][9]={{0},{0,5,15,40,80,90,95,98,100},{0,5,15,40,60,70,73,74,75},{0,4,26,40,45,50,51,53,53}};

Invest(m,n,f,g,d);

printf(“可获得的最大收益为：%dn”,f[3][8]);

jie(m,n,d);} void Invest(int m,int n,int f[][9],int g[][9],int d[][9]){ int i,j,k,s;for(j=0;j<=m;j++)

{

f[1][j]=g[1][j];d[1][j]=j;}

for(i=2;i<=n;i++)

for(j=0;j<=m;j++)

{

f[i][j]=0;

for(k=0;k<=j;k++)

{

s=f[i-1][j-k]+g[i][k];

if(s>f[i][j])

{

f[i][j]=s;d[i][j]=k;}

}

}

} void jie(int m,int n,int d[][9]){ int s=m;int k[4];int i;k[n]=d[n][m];for(i=n-1;i>0;i--){

s = s-k[i+1];

k[i] = d[i][s];} for(i=1;i<=3;i++)

} printf(“%5d”,k[i]);printf(“n”);

动态规划算法实验报告 篇2

在现实生活中, 有一类活动的过程, 由于它的特殊性, 可将过程分成若干个互相联系的阶段, 在它的每一阶段都需要做出决策, 从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定, 它依赖于当前面临的状态, 又影响以后的发展。当各个阶段决策确定后, 就组成一个决策序列, 因而也就确定了整个过程的一条活动路线。这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程, 这种问题称为多阶段决策最优化问题。这种多阶段最优化决策解决问题的过程就称为动态规划。

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.

动态规划算法实验报告 篇3

关键词：通信与信息系统；跨层动态带宽分配；非线性规划；卫星通信

中图分类号：TN927+.21

文献标识码：A

DOI：10.3969/j.issn.1003-6970.2015.09.023

0 引言

卫星通信网络的快速发展使得系统服务的用户数量、数据流量大幅增加，系统承载的业务也更多样化。基于这一发展趋势，欧洲电信标准化协会（EuropeanTelecommumcations Standards Institute. ETSI）制定了卫星通信系统DVB-RCS（Digital Video Broadcasting-Retum Channel via Satellite）标准，对卫星通信系统的物理层技术参数进行了规范化设计。DVB-RCS协议规定了编码调制方式、帧结构等内容，但未对资源管理方式进行统一规定，卫星系统可以根据需要采取灵活的资源管理措施。因此，在星上带宽资源有限、用户对带宽需求量大、需求多样化、用户链路传输速率不同的情况下，如何更加合理的分配带宽资源成为卫星通信中的研究热点。

经典的带宽分配算法只考虑用户请求的带宽资源数量，不能综合考虑用户服务类型和物理层信道特征，其分配结果往往很难达到较高的公平性和效用，导致系统吞吐量较低。跨层设计思想打破层间的信息阻碍，将用户请求带宽资源数量、用户服务类型和物理层编码调制方式信息进行综合考虑，得到效用更高的分配结果，提升系统的吞吐量。跨层设计思想在地面无线通信网络中的应用较为广泛，而由于卫星通信环境的特殊性，地面通信中的跨层带宽分配算法不适用于卫星通信，相关研究还未完善。早期研究引入效用函数的思想，根据通信环境的变化，对带宽进行实时的分配。在卫星通信领域，DVB-RCS卫星通信系统带宽分配模型可以应用跨层公平注水算法求解。使用请求时隙数量和最小保证时隙数量建立新的效用函数模型，也可以在一定程度上提升系统吞吐量。

本文在分析了多种动态带宽分配（dynamicbandwidth allocation，DBA）策略流程和性能的基础上，对常用的跨层效用函数进行了改进，提出新的跨层效用DBA模型，并设计其计算流程。本算法提升了DVB-RCS系统的吞吐量、绝对公平性和用户满意度，同时计算复杂度低，节约计算资源。

l DVB-RCS系统

如图1所示，DVB-RCS系统由网络控制中心（Network Control Center，NCC）、转发卫星和用户终端组成。在带宽请求的过程中，用户终端根据需求向卫星发送带宽请求，该请求通过反向链路由卫星和信关站传递给NCC，由NCC根据系统带宽资源分配算法执行分配功能，分配结果通过前向链路回传给用户终端，用户终端根据收到的分配结果进行数据传输。

DVB-RCS标准根据用户请求的优先级定义了以下五种带宽请求类型。

恒定速率分配（Constant Rate Assignment，CRA）：用户终端与NCC进行协商，确定一个固定速率，用户终端以此速率进行传输。

基于速率的动态容量（Rate Based DynamicCapacity，RBDC）：根据业务速率进行带宽请求，可以在传输过程中进行协商调整，有最大速率限制。

基于容量的动态容量（Volume Based DynamicCapacity，VBDC）：根据节点的缓存数量进行带宽请求，数量是积累性的。

绝对基于容量的动态容量（Absolutely VolumeBased Dynamic Capacity，AVDBC）：请求数量是绝对的，每次发送请求代替上一次的带宽请求。

自由容量分配（Free Capacity Assignment，FCA）：系统将剩余未使用的带宽非配给用户终端。

上述五种带宽请求类型中，CRA属于固定带宽分配（Fixed Bandwidth Assignment，FBA），其他四种属于动态带宽分配。由于FBA的带宽不能根据业务动态改变，会引起资源浪费，而卫星系统用户多，带宽资源有限，因此卫星通信系统中适合采用DBA的分配方式。

DBA根据业务状态对带宽资源进行实时分配，保证每一时刻带宽资源都能得到高效利用，从而大幅提高信道利用率，保证更多用户的通信需求，提升系统的吞吐量。但是经典的DBA算法计算复杂度较高，尤其在用户较多的情况下，会占用大量的计算资源，因此需要在保证分配性能的同时对经典算法进行简化，使其更加适用于卫星通信系统。

DVB-RCS系统采用时分多址的接入方式，有研究论证了卫星通信系统中时分多址接入的优越性，因此本文的带宽分配算法针对时分多址方式建立模型，即把带宽的分配看作时隙数量的分配。

2 基于非线性规划的跨层DBA

卫星通信的DBA模型通常考虑系统吞吐量、绝对公平性和用户满意度这三个指标。提升系统吞吐量可以增加带宽资源的利用率，提升卫星通信系统性能，为更多的用户提供通信服务；从用户角度来看，每个用户分配到的带宽与用户业务优先级、对带宽数量需求的符合程度是衡量系统通信服务质量的标准，体现在数值上就是绝对公平性和用户满意度。由于系统带宽资源有限，保证系统性能的同时必然会降低单个用户的服务质量，因此吞吐量与公平性、满意度之间存在着根本矛盾。DBA的主要工作就是在这三个指标之间寻找一个平衡点，兼顾系统性能与用户QoS。

本文在经典带宽分配思路中引入跨层设计思想，建立简化的跨层DBA模型，设计了非线性规划和贪婪算法相结合的求解算法，并通过仿真证明其性能。

2.1 基于非线性规划的跨层DBA模型

卫星通信中的DBA模型通常使用效用函数的形式。综合考虑多放面因素建立效用函数，求其最优解，即可得到带宽分配结果。

由于卫星通信中用户请求业务的优先级、请求带宽大小、保证服务的最小带宽大小、终端的链路状态都会对分配结果的性能产生影响，因此引入跨层设计的思想，将应用层的业务优先级信息和物理层的信道状态信息传输到链路层，建立统一的效用函数。假设有N个用户参与时隙分配，常用跨层效用函数形式如式（1）。

上述效用函数有需要完善的地方，本文考虑如下四点对效用函数进行了修改。

（l）由于效用函数中包含两个不同的对数项且代表链路状态的系数是随机的，其求解过程通常需要使用复杂的非线性整数规划或迭代算法（如贪婪算法等），计算复杂度很高且与用户数的平方正相关，当系统容纳用户较多时，很难保证实时的带宽分配。本文对DBA模型进行细微调整，以减少计算量。

（2）由于卫星通信环境较差，通常采用BPSK或QPSK的固定调制方式，因此经典跨层效用函数中只考虑低阶调制方式的影响。随着卫星通信系统性能的增强和对星地信道研究的深入，现有的传输技术已经能够在保证误码性能的同时提升调制阶数，因此本文将调制阶数M，引入效用函数。

（3）在用户业务优先级普遍较高时，优先级绝对值高并不会使用户获得更多的时隙，因此使用优先级相对值代替优先级绝对值。同样的，为了平衡优先级和链路状态之间的关系，对链路状态也采用相对值系数进行处理。

（4）为了保证用户的基本通信服务，优先为每位用户分配最小保证时隙，剩余时隙按效用函数最大化原则讲行分配。

对效用增量进行由大到小排序。

为效用增量最大的用户分配一个时隙并更新此用户的效用增量值。每分配一次都计算该用户的已分配时隙数是否等于其请求时隙数，若相等，则下次分配不再考虑该用户，以此来保证式（4）的约束条件成立。重复此分配过程，每一次只为效用增量值最大的用户分配，直至将所有剩余时隙分配完毕，算法结束。

算法完整流程图如下。

3 算法仿真与性能分析

3.1 仿真场景

本文通过仿真验证基于非线性规划的跨层DBA算法性能。论文选取传统跨层效用函数DBA算法和跨层公平注水算法作为对比，分析本文算法的改进。

仿真场景中使用的调制阶数根据DVB-RCS2协议规定的四种调制方式进行映射，如表l。

3.2 仿真结果及分析

在上述的仿真场景中，当可分配时隙数为100时，对三种算法进行仿真，得到的时隙分配结果如图3。

如表4所示，本文提出的跨层非线性规划DBA算法与跨层效用函数DBA算法和跨层公平注水算法相比，吞吐量分别提升了17.80和20.87个等效时隙，公平性提升了0.2696和0.0450；用户满意度提升了0.0259和0.0118。

通常系统的总时隙数是变化的，因此本文对不同时隙数的情况进行了仿真，结果如图4、图5、图6。

由图4可以看出，本文提出的基于非线性规划的跨层DBA算法在带宽资源很少的情况下效用值较低，这是由于在保证用户最小保证时隙的情况下，每个用户平均只能分到1-2个时隙，而算法中需要对非线性规划的小数进行省略，因此对效用值产生了较大影响，但在大部分情况下，本算法的效用值明显高于另外两种算法。

从图5上看，由于跨层非线性规划算法在系统模型上增加了调制阶数这一参数，并且使用现有卫星通信系统中的多种调制编码方式进行仿真，更加接近现阶段卫星通信系统的真实情况，因此与跨层效用函数算法和跨层公平注水算法相比，其系统吞吐量有较大提升。

由图6可以看出，本文所提算法综合考虑业务优先级、物理层信道状态和用户需求量，平衡各用户之间的竞争关系，使用户满意度得到较高的保证。

另外，在计算方法上使用非线性规划与贪婪算法相结合的方式，与常用的基于整数规划、动态规划等计算方法的DBA算法相比，可以在保证求得最优解的同时有效减少计算量，降低对系统计算资源的消耗。

4 结束语

页面置换算法实验报告 篇4

实验报告

班级：计科姓名：张华敏学号：

0902班

0909090814

FIFU算法

一，实验内容：

编写一段程序来模拟页面置换算法中的FIFU算法的实现 二，算法设计：

设置一个产生随机数的函数rand()产生随机数来模拟程序所需访问的页面的标号，如果页面需要被访问则把页面中的一个标志位设为in表示他已经被调入内存，如果再次需要访问此页面是只需检查此页面的标志位是否为in就可判断它是否已经存在在内存中了，如果已经存在则可直接使用，如果不存在则需调入，在调入新页面是先检查内存空间是否已满，如果未满则直接调入，如果已经满了则需选择一个页面将其调出，调出时就把页面的标志位设为out。选择页面的规则是：将进入内存时间最久的页面调出去，为了达到这一目的，在页面中设置一个计数器，每当有新页面调入内存时则将内存中已经存在的页面计数器自动加一，调出页面时就选择那个计数器最大值的页面，调出后重新将计数器设为零。三，遇到的问题及解决方案：

在做此实验时遇到了一些小问题,如在C语言中函数名定义为export()则会报错。在调用有返回值的函数是如果直接int s=use(pag)则会运行出错,要先分开写如：int s,s=use(pag).四，源代码 头文件.cpp #include #include

int t;//全局变量，用来盛放rand()函数产生的随机数

enum boolean{in,out};//定义一个枚举类型 /////////如果把in，out换成 true,false则会处错误

typedef struct { int num;//页面编号 char content;//页面内容

enum boolean flog;//判断此页面是否页调入，调入为true,否则为false;int count;//页面计数器

int usebit;//使用位，被使用过值为1，否则为0 }page;

FIFU.cpp #include #include #include #include“头文件.cpp”

int capacity=3;//设置内存最多可以容纳的页面数

void initialize(page p[])//初始化页面函数 { for(int i=0;i<5;i++)//初始化页面，页面内容分别为小写字母 abcde,计数器全部为0 {p[i].num=i;p[i].content=i+97;p[i].flog=out;p[i].count=0;} }

int use(page p[]){ t=rand()%5;//产生一个0-5的随机数，if(p[t].flog==in){ printf(“tt%d页面命中n”,t);//for(int i=0;i<5;i++)//调入此页面后其他以在内存中存在的页面计数器加1 // { // if(p[i].flog==in)// p[i].count++;// } return(1);} else return(0);}

void import(page p[])//调入页面的函数 { /* int t=rand()%5;//产生一个0-5的随机数，if(p[t].flog==in)printf(“tt%d页面命中n”,t);*/ // if(p[t].flog==out)//如果此页面未被调入内存则立即调入 p[t].flog=in;capacity--;//调入后内存空间减少一叶

for(int i=0;i<5;i++)//调入此页面后其他以在内存中存在的页面计数器加1 { if(p[i].flog==in&&p[i].num!=t)p[i].count++;} printf(“页面%d被调入内存n”,t);}

void port(page p[])//调出页面的函数，，，，，，，，，，，如果函数名定义为export则处错误 { int x=0,y;//x用来暂时存放计数器 中的最大值，y存放此页面的页面号 for(int i=0;i<5;i++)//寻找计数器值最大的 页面 { if(p[i].count>x){ x=p[i].count;y=i;} }

p[y].flog=out;//修改调入符号 p[y].count=0;capacity++;//调入后内存空间增加一叶 printf(“ttt页面%d被调出内存n”,y);}

main(){ int s;long t3,t1,t2;page pag[5];//定义五个页面，，，，，，，，，，，如果这个定义在子函数之前那么不用通过参数 子函数便可以直接访问 t3=time(NULL);initialize(pag);do { t1=time(NULL);s=use(pag);//，，，，，，，，，，，，，，如果这里写成int s=use(pag)则会运行出错

//printf(“s=%d capacity=%dn”,s,capacity);if(capacity>0&&s==0)import(pag);else { if(capacity==0&&s==0){ port(pag);import(pag);} } t2=time(NULL);while(t2-t1<1){ t2=time(NULL);} }while(t2-t3<20);system(“pause”);}

五，测试结果：

LFU算法

一,实验内容：

编写一段程序来模拟页面置换算法中的LFU算法的实现 二,算法设计：

设置一个产生随机数的函数rand()产生随机数来模拟程序所需访问的页面的标号，如果页面需要被访问则把页面中的一个标志位设为in表示他已经被调入内存，如果再次需要访问此页面是只需检查此页面的标志位是否为in就可判断它是否已经存在在内存中了，如果已经存在则可直接使用，如果不存在则需调入，在调入新页面是先检查内存空间是否已满，如果未满则直接调入，如果已经满了则需选择一个页面将其调出，调出时就把页面的标志位设为out。选择页面的规则是：将最近一段时间未被访问过的页面调出。为了达到这一目的在页面中设置一个标志位，如果页面在近期只要被访问过则将该标志位设置为1（默认为0），在选择调出页面时只需将标志位为0的页面调出即可。三,遇到的问题及解决方案： 未遇到什么问题

四,实验感悟：

遇到问题后上网查资料和有效,及时查不到自己想要的但是也可从相关结果中获得启发给自己灵感来想到解决问题的方法.四，源代码

FLU.cpp #include #include #include #include“头文件.cpp”

int capacity=3;

//设置内存最多可以容纳的页面数

void initialize(page p[])

//初始化页面函数

{

for(int i=0;i<5;i++)

//初始化页面，页面内容分别为小写字母 abcde,计数器全部为0

{p[i].num=i;

p[i].content=i+97;

p[i].flog=out;

p[i].count=0;

p[i].usebit=0;

}

}

int use(page p[]){

t=rand()%5;

//产生一个0-5的随机数，if(p[t].flog==in)

{

printf(“tt%d页面命中n”,t);

p[t].usebit=1;

//for(int i=0;i<5;i++)//调入此页面后其他以在内存中存在的页面计数器加1

//

{

//

if(p[i].flog==in)

//

p[i].count++;

//

}

return(1);

}

else

return(0);

}

void import(page p[])//调入页面的函数

{

int t=rand()%5;

//产生一个0-5的随机数，//if(p[t].flog==in)

// {

//

printf(“tt%d页面命中n”,t);

//

p[t].usebit=1;

// }

// if(p[t].flog==out)

//如果此页面未被调入内存则立即调入

p[t].flog=in;

capacity--;

//调入后内存空间减少一叶

for(int i=0;i<5;i++)//调入此页面后其他以在内存中存在的页面计数器加1

{

if(p[i].flog==in&&p[i].num!=t)

p[i].count++;

}

printf(“页面%d被调入内存n”,t);

}

void port(page p[])

//调出页面的函数

////////////////////////////////如果函数名定义为export则处错误

{

int x=0,y;//x用来暂时存放计数器 中的最大值，y存放此页面的页面号

int z=-1;

//用来判断近期是否有未被访问过的页面

int g=0;

for(int i=0;i<5;i++)//寻找计数器值最大的 页面

{

if(p[i].count>x)

{

x=p[i].count;

y=i;

}

}

for(int i=0;i<5;i++)

{

if(p[i].flog==in&&p[i].usebit==0)

{

z=i;

g++;

}

}

if(z==-1||g==3)//如果所有页面均为1则按照FIFO算法置换页面 //如果g=3则表明页面使用位全为零，此时也按照FIFO算法置换页面

{

p[y].flog=out;//修改调入符号

p[y].count=0;

capacity++;

//调入后内存空间增加一叶

p[y].usebit=0;

for(int i=0;i<5;i++)//将所有页面置0

p[i].usebit=0;

printf(“ttt页面%d被调出内存n”,y);

}

else

//如果有页面为0则将此页面置换出来

{

p[z].flog=out;//修改调入符号

p[z].count=0;

capacity++;

//调入后内存空间增加一叶

printf(“ttt页面%d被调出内存n”,z);

}

}

main(){

int s;

long t3,t1,t2;

page pag[5];//定义五个页面

///////////////////如果这个定义在子函数之前那么不用通过参数 子函数便可以直接访问

t3=time(NULL);

initialize(pag);

do

{

t1=time(NULL);

s=use(pag);

if(capacity>0&&s==0)

import(pag);

else

{

if(capacity==0&&s==0)

{

port(pag);

import(pag);

}

}

t2=time(NULL);

while(t2-t1<1)

{

t2=time(NULL);

}

}while(t2-t3<20);

system(“pause”);}

六,实验结果

总结

银行家算法实验报告 篇5

（1）死锁产生的原因和必要条件是什么？ 原因：

a)系统资源不足；

b)进程运行推进的顺序不合适； c)资源分配不当。

如果系统资源充足，进程的资源请求都能够得到满足，死锁出现的可能性就很低，否则就会因争夺战、有限的资源而陷入死锁。其次，进程运行推进顺序与速度不同，也可能产生死锁。

必要条件：

a)互斥条件：一个资源每次只能被一个进程使用；

b)请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放； c)不剥夺条件：进程已获得的资源，在未使用完之前，不能强行剥夺； d)循环等待条件：若干进程之间形成一种头尾相接的循环等待资源关系。

（2）银行家算法中的安全性检查时，Work[j]+Allocation[i,j]的含义是什么？

work[j]表示当前系统可用的第j类资源，Allocation[i][j]表示当前已经分配给进程i使用的第j类资源数量。Work[j]= Work[j]+ Allocation[i，j]这句的意思是目前进程已经利用手上资源完成相关工作了，这些已分配的资源可以重新归还系统了，所以系统可用的第j类资源work[j]就增加了，增加量就是当前进程想要归还的资源量Allocation[i][j]。

（3）为什么银行家算法能有效避免死锁的发生？算法的主要思想是什么？

操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配。

银行家算法的基本思想是分配资源之前，判断系统是否是安全的；若是，才分配。

（4）补全Bank()和Safe()函数； void Bank()//银行家算法 { int q;bool flag = true;printf(“请输入请求的进程向量n”);scanf(“%d”,&q);printf(“请输入%d个资源的请求资源数n”,n);for(int i=0;ineed[q][j]){ flag=false;} } if(flag){ for(int j=0;i

int Safe()//安全性算法 { //返回1表示安全，返回0表示不安全 int tp=1;int i;int Work[20];int tmp=0,t=0;for(i=0;i

for(i=0;iWork[j]){ flag = false;} } //所有资源小于需求，允许分配 if(flag){ for(int j=0;j

for(i=0;i

银行家算法的模拟【实验报告】 篇6

银行家算法的模拟

专业：信息管理与信息系统 学号：2014****** 姓名：陈* 实验日期：2016年12月20日

一、实验目的

银行家算法是一种最具有代表性的避免死锁的算法。

要解释银行家算法，必须先解释操作系统的安全状态和不安全状态。所谓安全状态，是指系统能按照某种进程顺序{P1,P2,…，Pn}（称{P1,P2,…，Pn }序列为安全序列），来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可以顺利完成。安全状态一定没有死锁发生。

如果系统无法找到这样一个安全序列，则称系统处于不安全状态。那么，什么是安全序列呢？

如果对每一个进程Pi(1

利用银行家算法，我们可以来检测CPU为进程分配资源的情况，决定CPU是否响应某进程的的请求并为其分配资源，从而很好避免了死锁的产生。通过编写一个模拟动态资源分配的银行家算法程序，进一步深入理解死锁、产生死锁的必要条件、安全状态等重要概念，并掌握避免死锁的具体实施方法

二、实验要求

用高级语言编写和调试一个动态资源分配（银行家算法）的模拟程序，以加深对避免死锁算法的理解。

三、实验方法内容

1.算法设计思路（流程图）2.算法中用到的数据结构 最大需求矩阵Max[][] 已分配矩阵Allocation[][] 仍需求矩阵Need[][]=Max[][]-Allocation[][] 可利用资源向量Available[] 申请各类资源向量Request[] 工作向量 work[] , Finish[]

3.主要模块（函数名）

（1）int getRequest();获取用户输入的进程和对应请求的资源（2）int checkNeed(int no)检查用户的请求是否大于还需要的资源（3）int checkAvailable()检查用户的请求是否大于现有的可利用的资源（4）int isSafe(int proNo)安全性算法，检查预分配资源后系统是否安全（5）int Bank(int proNo)银行家算法

四、实验结果

1.执行结果

2.结果分析

（1）当输入的进程请求的资源超过该进程还需要的资源时，该请求不合法；（2）当输入的进程请求的资源大于系统当前可利用的资源时，该请求不合法，需等待；

（3）当输入的进程请求合法，且分配资源后系统处于安全状态，则分配资源给该进程；

（4）当输入的进程请求合法，但分配资源后系统处于不安求状态，则不分配资源，需等待；

五、实验总结

（1）通过此次试验，我对死锁、产生死锁的必要条件、安全状态灯概念有了进一步的了解；

动态规划算法实验报告 篇7

随着全球能源和环境问题的日益突出,风能等可再生能源发电技术得到迅速发展,风电并网的规模也越来越大[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台常规机组的燃料耗量,

,其中,Pi,t为第i台常规机组在时段t的发电功率,Ai,2,Ai,1,Ai,0为第i台常规机组的耗量特性系数,对于水电机组,有Ai,2=Ai,1=Ai,0=0;E{·}为期望函数;Πt为xt的可行域。

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模型的求解速度。以某一实际省级电网为算例,通过与场景法和鲁棒优化调度方法的比较验证了所提出模型和求解方法的正确有效性。