时间枚举论文

时间枚举论文（共6篇）

时间枚举论文 篇1

最差情况执行时间 (Worst-case Execution Time, WCET) 分析通常被分为动态、静态和混合3种方法。其中, 静态方法通常要经过:控制流分析;处理器建模;WCET计算3个处理环节。隐藏路径枚举技术 (Implicit Path Enumeration Technique, IPET) 是静态WCET分析方法在计算环节最常用的技术。

1基本原理

该方法的基本思想是在分析程序控制流图的基础上, 使用整数线性规划求解最长执行路径。为了进一步说明隐藏路径枚举法的基本原理, 首先介绍基本块的定义。

定义1基本块[1]是目标程序中这样的连续语句序列: (1) 只有第一条语句可以有多个入口; (2) 只有最后一条语句可以有多个出口; (3) 内部不含分支、跳转语句。

2举例分析

下面以程序“insertsort.c”为例介绍IPET方法。首先对源程序 (图1 (a) 所示) 进行编译生成可执行程序, 然后对可执行程序反汇编, 并生成控制流图如图2 (a) 所示。

该控制流图的字符表达形式如图1 (b) 所示, 其中“3:400358:[4, 3]”的含义是基本块3的起始地址是400358, 可以到达基本块4和基本块3。在获得控制流图的基础上, 针对基本块的执行次数 (即, 循环上界、不可行路径) 添加约束, 其字符表达形式如图1 (c) 所示。例如, “c0.0=1”的含义是过程P0中的基本块B0的执行次数是1次。接下来需要根据控制流图和约束生成整数线性规划所需的计算表达式。这里需要用到以下定理[2]:

定理1基本块的执行次数等于流入该基本块的所有边的执行次数, 也等于从该基本块流出的所有边的执行次数。即:

其中, NB表示基本块B的执行次数。BB"EBB"表示从基本块B流出的所有边的执行次数。B'BEB'B表示流入到基本块B的所有边的执行次数[2]。

为了计算图1 (a) 中程序的最差执行时间, 需要使用整数线性规划求解基本块B2的执行次数NB2, 以使WCET最大化, 即:

其中, NBi是基本块Bi的执行次数。Ci为基本块Bi的执行时间, 利用指令模型、Cache模型、流水线模型及分支预测模型计算得到。

除了图2中已知和推理出来的表达式以外, 还可以利用定理1从图2 (c) 得到以下表达式:

显然, 由于基本块NB2的执行时间有C2>0, 在其他基本块的执行次数已经确定的情况下, NB2越大, 整个程序的执行时间越长。因此, 整数线性规划求解的结果必然是NB2=9。至此, 所有基本块的执行次数都已确定, 利用公式2即可获得程序的WCET估计值。

综上所述, 隐藏路径枚举技术在实际应用中表现出了比较好的求解效率。尽管如此, 由于其基于整数线性规划, 而整数线性规划的描述能力并非是最强的, 依然无法描述复杂的程序控制流程信息。同时, 整数线性规划问题的求解效率会随着程序复杂度的提高而大幅增加。

参考文献

[1]孙昌爱, 金茂忠, 刘超, 等.程序执行时间的静态预估与可视化分析方法[J].软件学报, 2003, 14 (1) :68-75.

[2]Li X, Liang Y, Mitra T, et al.Chronos:A timing analyzer for embedded software[J].Science of Computer Programming, 2007, 69 (1) :56-67.

时间枚举论文 篇2

关键词：俄罗斯方块游戏,基本型方块,旋转型方块,枚举,算法

1“枚举算法”概述

本文则提出了所谓枚举算法,就是直接枚举出游戏中方块的基本形状和它们的旋转形状,然后控制每一种不同形状的方块在游戏中的产生、移动、旋转、落下、清除填满行等游戏过程。

1.1 方块基本形状和种类

根据分析,“俄罗斯方块游戏”中的方块,共有七种基本形状,它们分别是“I型”、“L型”、“反L型”、“Z型”、“反Z型”、“口型”、“T型”,如图1。

1.2 方块的旋转形状

游戏过程中,每一种基本方块都要做旋转控制,于是就产生了旋转后的方块形状,本文将其称为“旋转型”。

基本型中的“I型”、只有一种旋转型,即由竖直旋转90°后成为水平。因此,基本型加上一种旋转型,共有两种形状。

基本型中的“L型”和“反L型”有三种旋转型,将它按顺时针每旋转一个90°就产生

一种旋转型,它可以旋转三次,得到三种不同的旋转型,因此,它的三种旋转型加上其基本型,“L型”和“反L型”方块分别有四种形状。

基本型中的“Z型”和“反Z型”可以顺时针旋转一次90°,加上他们的基本型分别有两种形状。

基本型中的“T型”有三种旋转型,将他按顺时针旋转一个90°就产生一种旋转型,它可以旋转三次,得到三种不同的旋转型,因此,它的三种旋转型加上其基本型,“T型”方块共有四种形状。

基本型中的“口型”方块没有旋转型,在游戏中只有一种形状。

经前面的分析得知,七种基本型方块,因旋转产生了不同的旋转型,这些旋转型加上他们的基本型,整个游戏中,共有19种不同的方块形状。

2 基本型方块的构成和控制

每一种基本型方块都由4个正方形小方块构成,利用小方块不同摆的放位置,产生19种旋转型。利用随机函数在一个预览窗中提前展示形状供用户参考,然后将展示的形状复制到游戏主窗口中进行摆放,在游戏主窗口中用户就可以使用键盘的方向键来控制方块的运动。然后对每一行进行判断,如果有某行的方块是满的,则消除这行的方块,并且使上面的方块自由下落,其中,方块向下的速度是有时钟控件控制的,在游戏中,用户也可以使用“向下光标键”加快下落速度,定义一个变量,对消除的函数进行记录,最后就可以得出用户的分数,用if语句对分数判断,达到一定的积分就可以升级到下一个档次。

2.1 基本型方块的够成

所谓“基本型方块”是指每新产生的,没有经过旋转的方块形状(如图1),基本型方块是有4个正方形的小方块拼接而成。在程序实现过程中,可以使用4个正方形控件来构成每一种基本型方块。

2.2 主游戏界面与数据结构设计

为了能实现控制方块的旋转、平移、下落等操作。需要构造一个游戏主窗口和一个二维矩阵数据结构。

2.2.1 主游戏界面

在主窗口中按照9X15,将小方块(控件)进行排列,每一个控件的Visible属性设置成“False———不可见”,表示在开始游戏之前,主界面中没有任何方块。左上角作为坐标起始点,为了在程序中,对主窗口中的每一个小方块(正方形控件)进行遍历,用数字字符给控件按照一定的规则进行命名如图2。

正方形控件的名称=行坐标*每行控件的数量+列坐标=行坐标*9+列坐标

2.2.2 构造一个大小为9X15的二维数组

用来保存对应主界面中的每一个方块位置是否被填充,已经被填充的为“1”,未填入的为“0”。通过这样的方法,即可简单地将数据结构映射到由小方块(正方形控件)组成的图形界面上。

2.2.3 小方块的初始化显示

在游戏开始或者前一个方块已经不能继续下落的时候,需要在主界面的第一行(行坐标为0)、第五列(列坐标为4)的位置显示某一个基本型方块。这个功能由计算机产生一个1~7随机数,表示7中基本型方块的某一种,然后枚举出基本型方块初始时,在主界面中的位置,并把主界面中,对应的小方块(正方形控件)的Visible的值修改成“True(可见)”。例如:随机数为2,对应“L型”方块,它对应坐标为(0,4),(1,4),(2,4),(2,5),根据控件命名规则,可以计算出主界面中需要修改的控件名称分别为“4”、“13”、“22”、“23”。如图3。

小方块初始化算法:

3 方块的下移、平移、旋转

基本型方块初始化产生后,还需要用变量保存它的形状代码shape、旋转型rot和在主界面中的起始行坐标row和列坐标column,例如图3中的“L型”方块:

3.1 方块的下移

1)下移的合法性判断:方块下移的前提是,方块没有到达最底部,这可以通过行坐标row<14来判断,方块下移时要通过的位置没有被前面的方块填充,这个需要通过与主界面一一映射的二维数组相对应的单元是否为“1”来判断,如果以上条件合法,则,方块下移。

2)下移的实现:方块下移也是通过修改主界面上的小方块(控件)的Visible属性来实现的。例如图3中的“L型”方块下移一格,需要修改控件:

控件4.visible=false;控件23.visible=false;

控件31.visible=true;控件32.visible=true;如图4。

3.2 方块平移

方块的平移包括左移和右移两种情况,无论那种情况都要首先进行合法性判断。

1)合法判断,平移的合法性判断比较简单,只需判断它旁边相邻位置是否被填充为,可以通过对映射二维数组中相对应的单元是否为“1”来实现,同时也要判断是否已经到了左右边界。

2)平移实现,方块平移也是通过修改主界面上的小方块(控件)的Visible属性来实现的。例如图4中的方块左移一格,需要将“13”、“22”、“32”控件的visible=false;“12”、“21”、“30”控件的visible=true即可。

3.3 方块旋转

1)合法性判断,在游戏中,方块做顺时针旋转,每次旋转90°,方块旋转前的合法性检查稍微要复杂一些,主要涉及到它旋转所要经过的位置不能有已经填充的方块。

例如图4中的“L型”方块旋转前(顺时针90°),必须检查“21”、“30”、“14”、“23”处没有被填充方块,这个检查也是通过对二维数组中相对应的单元是否为“1”。来判断。

2)旋转的实现,当合法性检查后,就可以通过修改相关位置的控件visible值来实现旋转。方法和平移、下落一样。

3.4 算法实现

从前述所知,游戏中7种基本型方块加上他们的旋转型方块总共有19种类型,程序算法只需要根据他们的形状代码shape、旋转型rot,在主界面中的行坐标row和列坐标column,每做一次平移、下落、旋转,要跟踪修改他的shape、rot、row,column等值,为下一次操作提供枚举依据,然后用代码对每一种情况进行处理即可。

由于篇幅有限,这儿没有给出全部源代码,有兴趣的读者可以与本文作者联系索取完全编译通过的源代码

参考文献

[1]唐凯军,汤惠莉.80例上手VB6编程[M].济南:山东电子音像出版社,2004.

[2]韦纲.FlashMX2004多媒体课件制作教程[M].北京:海洋出版社,2005.

时间枚举论文 篇3

为了确保电网在各种事故发生时均能够安全稳定运行,形成了电网三道防线[1,2,3]的概念,其中的第二道防线指出,在发生严重故障时允许采取有效的切机措施来维持电力系统的稳定运行[4,5]。在电网承受第Ⅱ类大扰动时,电力系统将会进入紧急状态,此时电网第二道防线将发挥作用,针对预先考虑的故障形式和运行方式,按预定的控制策略,采用安全稳定控制系统(装置)实施切机、切负荷、局部解列等控制措施,防止系统失去稳定[6,7,8,9,10]。所谓预定的控制策略,就是预先对电网进行稳定分析计算,计算在所有运行方式下各种可能发生的故障,采取哪些控制措施,多少控制量可以保持电网稳定,也就是常说的“策略表”。对于机组在电网中的位置,或者说各个不同机组对稳定的影响程度,需要在策略表中加以考虑。对于区域电网的频率稳定问题,一般来说切除该区域的任何一台机组对频率稳定的影响没有差别;而对于暂态稳定或电压稳定问题,切除哪里的机组则存在一定的差别,若差别大,在制定策略表时就必须将切机对象分群,若差别不大则可纳入同一群,但无论如何,制定切机量均需要考虑一定的裕度。本文主要研究被选择的切机对象对电网稳定影响差别不大,且在控制措施裕度范围内时进行优化计算的问题。

事故发生后,稳定控制系统识别出故障形式和类型后,根据离线制定好的控制策略表,计算出所需要的切机量,再将实时记录的事故前0.2s的所有可切机组功率值进行优化计算,匹配一个切机组合,其切机总量和需要切机量符合预先设定的原则,如最接近、最小过切、最小欠切等。

对于最优切机组合的计算问题,目前稳定控制系统大多采用穷举法。穷举法在计算过程中需要对每一种切机组合进行计算,若备选切机对象个数为n,则需要进行计算的切机组合数就为2n个。随着当今电网规模的迅速发展,故障紧急情况下备选切机对象的数目不断增加,应用穷举法所需的计算时间已超过了大规模电网稳定控制系统快速切机切负荷的要求,这对于故障紧急情况下保持电网的安全稳定运行而言,存在着很大的安全隐患。而对于遗传算法等智能优化算法,采用概率化的寻优方法,能自动获取和指导优化的搜索空间,自适应地调整搜索方向,不需要确定的规则,已被广泛应用于组合优化、自适应控制等领域;但遗传算法最大的缺陷在于很短时间内运行结果的稳定性较差,这就使其实际应用受到一定的限制。

针对上述算法中存在的隐患,提出一种基于隐枚举法的优化切机方案。该方案利用优化切机问题所蕴含的启发性信息,在计算过程中只对那些可能是最优解的切机组合进行计算,从而减少计算量,快速完成优化切机问题的求解。通过切机实例的仿真结果表明,隐枚举法在提高优化切机问题的求解效率上效果显著。

1 稳定控制系统中的优化切机问题

1.1 优化切机问题概述

当电网发生低概率的严重故障后,稳定控制系统可综合电网实时运行情况,根据稳定控制策略确定需要切除的功率额以及能够进行切除的切机对象(简称备选切机对象),然后按切机容量与需切容量接近的原则,快速、准确地在备选切机对象中选择出最优切机组合进行切除。

优化切机问题是一个典型的0-1规划问题。通常用0-1变量来描述备选切机对象切除与否,0-1变量的个数则代表备选切机对象的个数。对于优化切机问题的数学模型,根据电网紧急运行情况的不同将其分为过切模型和欠切模型。

1.2 优化切机问题的数学模型

电网发生严重故障时,可能会出现不同的稳定问题,如功角稳定、热稳定、频率稳定问题,此时需要稳定控制系统在短时间内采取有效的切机措施。为了确保电力系统的稳定运行,对于功角稳定或热稳定问题,一般采用过切方式,且过切量不能偏离过大;对于频率稳定问题,一般采用欠切方式,且欠切量不能过大。

功角稳定或热稳定问题的优化过切模型如下:

频率稳定问题的优化欠切模型如下:

式中:Ci为表示第i号备选切机对象是否进行切除的0-1变量,为1时表示切除第i号机,为0时表示保留第i号机;Pi为稳定控制系统实时采集的第i号备选切机对象的出力值;PC为需要切除的功率额。

2 基于隐枚举法的优化切机方案

2.1 0?1线性规划隐枚举法

在求解0-1线性规划问题时,若通过问题本身所蕴含的信息或是在求解过程中所取得的信息,就能够隐含地判别出某一变量值组合的可行性及其最优性,则可以称该组合被隐枚举。利用这种隐枚举的方式,只需要计算一部分的变量值组合就能求得问题的最优解,这种计算方法就称为隐枚举法[11,12,13]。

在隐枚举法中,能够指导枚举过程使之加速取得最优解的信息称为启发性信息[14,15]。启发性信息主要通过两个方面来获取:①问题本身所蕴含的信息,往往从目标函数以及约束条件中可以获取启发性信息;②在求解过程中所取得的信息,往往是指在枚举过程中所获得的有关最优解的约束信息。

在0-1规划问题中每个变量的取值只能是0或1,故在求解0-1规划问题的过程中可以采用一种二元搜索树[14]来描述隐枚举法的枚举过程,或称为搜索过程。包含三变量X1,X2,X3的二元搜索树如图1所示,搜索树中的小圆圈称为节点,节点与节点间的每一层都对应着一个0-1变量,相应的两个分支则代表变量的取值,通常规定左分支为1,右分支为0,从而树上的每一个节点就表示一种固定解。

应用隐枚举法求解0-1规划问题的过程中,首先根据问题的启发性信息制定搜索策略、剪枝策略及终止策略,然后根据所制定的策略沿着二元搜索树按从上到下、从左到右的顺序进行搜索,不断地逼近于最优解,当满足终止准则时,即完成求解过程。

2.2 隐枚举法求解优化切机问题的基本思路

从优化切机问题的数学模型中,可以总结出一些启发性信息:①只有一个不等式约束条件;②在目标函数与不等式约束条件中,对应变量的系数Pi(i=1,2,…,n)固定;③ 变量的系数Pi(i=1,2,…,n)为正数。利用这些启发性信息对优化切机的数学模型进行变换。对于稳定控制系统实时采集的n个备选切机对象,优化切机的数学模型可以转换如下。

优化过切模型:

优化欠切模型:

要求过量切机时,需满足约束条件 ΔP≥0,求解min ΔP;要求欠量切机时,需满足约束条件ΔP≤0,求解maxΔP。

从变换后的数学模型可见,无论对于过量切机还是欠量切机,ΔP的值越接近于零,相应的切机组合就越佳。根据上述启发性信息,制定应用隐枚举法求解优化切机问题的搜索策略、剪枝策略以及终止策略。

搜索策略可描述为:将所有变量按系数值从大到小的次序逐层排列在二元搜索树上,在枚举过程中沿着搜索树从上到下、从左到右的次序对每一个节点进行计算。剪枝策略可描述为:如果当前节点的计算结果满足 ΔP≥0,则该节点以下节点的 ΔP值就越大,故不再需要对该节点以下的节点进行计算。终止策略可描述为:完成二元搜索树上所有节点的检验后,终止计算,完成求解过程。

应用隐枚举法求解优化切机问题的枚举过程中,从搜索树的树根开始按从上到下、从左到右的顺序进行搜索,若当前节点符合剪枝策略则进行剪枝,否则对当前节点进行分支,继续搜索下一层节点,直到满足终止准则后停止计算。隐枚举法通过利用有效的剪枝策略,减少了所需要计算的解的数量,从而只需要检验其中一部分切机组合就能得到最优切机组合,提高了计算效率。

2.3 隐枚举法求解优化切机问题的计算流程

基于隐枚举法求解优化切机问题的计算流程如图2所示。

图2隐枚举法求解优化切机问题的流程Fig.2 Flow chart of solving optimal problem of generator tripping based on implicit enumeration method

其中,若是求解过量切机的最优组合,则只对满足 ΔP ≥0 的节点进行比较,最优解即为能取得minΔP的节点;若是求解欠量切机的最优组合,则只对满足 ΔP≤0的节点进行比较,最优解即为能取得maxΔP的节点。

3 算例分析

3.1 计算机仿真计算分析

为了验证本文所提出的隐枚举法在求解优化切机问题上的高效性,采用MATLAB2013软件编写计算程序,对切机实例进行仿真计算。切机实例的数据来自国内某区域电网的真实数据,如表1所示,共有16个备选的切机对象。分别应用穷举法和隐枚举法,对优化切机问题中备选切机对象数目为8个至16个时的情况进行计算,其中,若备选切机对象为8个时,对应表1中的对象1至对象8;若为9个时,则对应对象1至对象9,以此类推。考虑不同需切机量对计算时间有一定影响,本案例中备选切机对象的出力总和为2 724 MW。实际切机量有大有小,故按切机量为小、中、大的程度,分别选择了423,722,2 000 MW这3个程度不同的需切机量进行仿真试验。

在同一参数下,优化过切模型和优化欠切模型的计算时间基本一致,故只列出在优化过切模型下的仿真结果,如表2至表4所示。对比穷举法与隐枚举法的仿真计算结果可见,在同一运行条件下两种方法计算的切机结果基本一致,但在运行时间上,隐枚举法的运行时间要明显少于穷举法的运行时间。

为了更进一步比较隐枚举法与穷举法以及智能遗传算法的运行效果,本文对遗传算法也进行了编程和仿真。这三种方法在优化切机效果相同的情况下,运行时间曲线如图3至图5所示。

从曲线图中可以观察到,随着备选切机对象数目的增加,穷举法的计算时间呈指数增长,当备选切机对象数目较多时,穷举法在计算时间上就难以被接受,而隐枚举法在备选切机对象数目较多的情况下,仍能在短时间内完成优化切机问题的计算。遗传算法在切机对象个数较少(8~12个)时,运行时间明显要长于穷举法和隐枚举法,而切机对象个数增多(12个以上)时,遗传算法的运行时间低于穷举法而高于隐枚举法的运行时间,这说明遗传算法在求解多个切机对象时也没有较大优势。另外,遗传算法的优化结果也不如隐枚举法的结果稳定。总之,相比于现有的穷举法和智能遗传算法,隐枚举法具有明显的优势,而且隐枚举法相对于穷举法能减少约70%的计算时间。

图3需切机量为423 MW时过量切机的仿真运行时间对比Fig.3 Contrastive curves of simulation time of excessive tripping in the case of removing 423 MW

3.2 嵌入式装置的运行分析

为了进一步验证本文提出的隐枚举法在解优化切机问题上的高效性,在嵌入式装置中进行运行测试。装置测试平台使用国内主流分布式稳定控制装置,测试算法采用C语言作为编程语言。

为确保可靠性,该装置要求在一个采样周期(0.833ms)内完成所有站间的通信、采样、故障判别、执行控制措施。在该嵌入式装置中对优化过切模型进行测试,测试算例同3.1节中的仿真算例。

图4需切机量为722 MW时过量切机的仿真运行时间对比Fig.4 Contrastive curves of simulation time of excessive tripping in the case of removing 722 MW

图5需切机量为2 000 MW时过量切机的仿真运行时间对比Fig.5 Contrastive curves of simulation time of excessive tripping in the case of removing 2 000 MW

应用穷举法的装置测试运行时间如表5所示。在测试过程中,当备选对象达到12个时,程序耗时的峰值已超过装置的中断时间0.833ms,程序已无法稳定运行。故应用穷举法求解优化切机问题时,装置最多只能考虑11个备选切机对象。

应用隐枚举法的装置测试运行时间如表6 所示。在测试过程中,当备选对象达到14个时,程序耗时的峰值超过装置的中断时间0.833 ms。故应用隐枚举法求解优化切机问题时,装置最多只能考虑13个备选切机对象。

对比装置的测试情况可以发现,隐枚举法的运行时间要明显少于穷举法的运行时间,并且应用隐枚举法能使装置的备选切机对象从11 个提高到13个。通过稳定控制装置的测试结果进一步验证,相比于穷举法,本文所提出的隐枚举法提高了优化切机问题的求解效率。

4 结语

本文结合优化切机问题的特点以及隐枚举法的基本思想,提出了应用隐枚举法求解优化切机问题的新方法。该方法通过设定合理的搜索顺序以及有效的剪枝策略,使最优切机组合的搜索计算量大大下降,从而能够快速完成优化切机问题的求解。通过对切机实例的计算结果表明,该方法在保证切机结果准确的前提下,使得优化切机问题的求解效率提升了70%。

本文所提出的基于隐枚举法的优化切机方法,已应用于稳定控制装置中。该方法能够扩大装置所能考虑的备选切机对象数目,并同理适用于优化切负荷。在电网规模不断扩大、备选切机对象不断增加的情况下,该方案利于保证安全稳定装置进行切机、切负荷的快速性和有效性。

摘要：由于电网规模的迅速发展,故障紧急情况下稳定控制系统切机对象数目的增加,传统基于穷举法的优化切机方法已经不能满足大规模电网稳定控制系统快速切机的要求。为了提高优化切机问题的求解效率,文中提出了基于隐枚举法的优化切机方法。该方法根据优化切机问题的特点制定剪枝策略,能够有效减少枚举过程中需要计算的切机组合数,从而提高了计算效率。切机实例的计算和实际装置的仿真结果表明,文中所述方法能够减少约70%的优化计算时间,实现稳定控制系统的快速切机。

时间枚举论文 篇4

对于有n个变量的0-1规划问题, 由于每个变量只取0、1两个值, 故n个变量所有可能的0-1组合数有2n个。在现实生活中, 很多问题都可以转换成0-1规划问题, 比如席位分配问题、排序问题、资源配置问题等, 而对于0-1规划的问题, 目前最普遍的解法就是枚举法, 即检查变量取值为0或1的每一种组合, 比较目标函数值以求得最优解。在此基础上人们采用了隐枚举法、遗传算法、动态规划法等方法, 虽然在一定程度上加快了求解速度、缩短了问题的解决时间, 但这些方法都是基于串行计算来实现的, 只能当变量较小时来达到优化的目的。但是当n较大时, 比如:当n=64时, 264≈1.845×1019, 以每秒解决107种状态的速度, 则需要5.85×104年, 用串行计算根本是不可能的。并行计算能同时使用多种计算资源解决计算问题, 能快速解决大型且复杂的计算问题, 是当前世界上主要用于解决大规模、高精度问题的方法, 它能解决很多串行计算不能解决的问题。目前国内外对用并行算法来解决0-1规划问题的研究并不多, 基于0-1规划问题在生活中的重要性以及并行算法的高效性, 本文对用并行隐枚举法来解决0-1规划的问题进行了一定的探讨。

1 并行计算与隐枚举法

并行计算是指同时使用多种计算资源解决计算问题的过程。它是相对于串行计算而言的, 所谓的并行计算分为时间上的并行和空间上的并行, 时间上的并行就是指流水线技术, 而空间上的并行则是指用多个处理器并发的执行计算。集群系统逐渐成为高性能并行计算的主要硬件平台, 它是将一组相互独立的计算机通过高速的通信网络而组成的一个单一的计算机系统, 并以单一系统的模式进行管理[1]。并行计算的主要目的:一是为了提供比传统计算机快的计算速度;二是解决传统计算机无法解决的问题。

MPI (Message Passing Interface) 是消息传递并行程序设计的标准之一, 是目前最主要的并行环境。它适用于基于分布内存的并行计算机系统的消息传递模型, 具有移植性好、功能强大、效率高等多种特点, 而且有多种不同的免费、高效、实用的实现版本, 几乎所有的并行计算机厂商都提供对它的支持, 这是其他并行环境无法比拟的[2,3]。

隐枚举法 (Implicit Enumeration Method) 是Balas E 在1965年提出的, 是以0-1整数规划为背景建立的。它只检查一部分变量组合, 在这过程中根据已有信息自动舍弃许多不可能成为最优解的组合, 求得最优解, 从而大大减少了工作量[4,5]。隐枚举法只需比较目标函数在一小部分组合点上的取值大小就能求得最优解和最优值。弥补了完全枚举法迭代次数过大的缺点。

2 0-1规划问题并行算法设计

2.1 算法设计基本原理

0-1规划问题中各个状态的处理计算是唯一的, 本文中以各个状态为对象, 每个节点 (或从进程) 处理等量的状态数。假设有n个变量, 即个2n状态, 有m+1个进程。

算法基本原理如下:

1) 程序初始化生成m+1个进程, 每个进程ID号分别为0, 1, …, m-1, m。

2) 进程0作为主处理器, 其操作包括两个方面的内容:①将2n个状态划分为m个状态组, 并且将这m个状态组分配给m个相应的从进程;②检查是否有从进程向其发送满足条件的局部最优解, 若有则接受消息, 并且与当前的全局最优解进行比较。

3) 进程1, 2, …, m, 作为从进程, 其操作包括两个方面的内容:①接受主进程发送来的状态组, 在局部区域内进行搜索, 得到一个局部最优解;②将局部最优解发送给主进程, 等待新的任务。

4) 直到所有的从进程计算完毕, 将局部最优解发送给主进程, 主进程得到最后的全局最优解。

2.2 算法具体实现

设有2n个状态, m个从进程, glo_best为主进程中记录全局最优解的变量, part_best[i] (i=1 to m) 为相对应的m个从进程中的记录局部最优解的变量, state[i] (i=1 to m) 记录从进程的状态, state[i]=0表示从进程i空闲, group[i]记录从进程i中所接受到需要处理的状态。假设所需要求的最优解是极大值问题。

核心算法如下:

初始化:将2n个状态划分成m个状态组, 并分配给各个从进程, state[i]=1

试探性求一个满足约束条件的可行解, 计算出相应的目标函数值为Z

While (存在state[i]==1)

{

对于从进程i, 寻找局部最优解

For (j=1;j<=2n/m;j++)

{

求出所有状态的目标值z[j];

If (状态j的目标函数值小于Z) {删除相应的状态;}

}

将目标函数值大于等于Z的状态数按照目标值进行从大到小排序

For (j=1;j<=s;j++)

{ //s为目标函数值大于等于Z的状态数

If (状态j满足约束条件)

{ part_best[i]=z[k]; break; }

}

state[i]=0;

If (part_best[i]>glo_best) glo_best=part_best[i];//将局部最优解和全局最优解进行比较

}

主进程输出最后结果, 程序结束。

3 应用实例

一个旅行者有一个最多能装15公斤的背包, 现在有6件物品, 它们的重量分别是3, 6, 2, 3, 7, 1;它们的价值分别为4, 7, 5, 7, 8, 15;若每种物品只有一件, 求旅行者能获得最大总价值Z。

分析:这个问题转换成数学模型为:

M=3x1+6x2+2x3+3x4+7x5+x6≤15

求:

Z=Max{4x1+7x2+5x3+7x4+8x5+15x6}

式中, x1, x2, x3, x4, x5, x6的取值为0或1。

这个实例中一共有6个变量, 共有64个状态。

(1) 用串行完全枚举法求解

目标函数需要计算64次, 约束条件需要计算64次, 总共需要计算128次。当{x1, x2, x3, x4, x5, x6}={1 1 1 1 0 1}时, m=15, Z=38。

(2) 用并行隐枚举法进行求解

设从处理器数目为4。

Step 1 将状态数进行分组, 先试探性求一个可行解, 易看出{x1, x2, x3, x4, x5, x6}={0, 0, 0, 0, 0, 1}满足约束条件, 故为一个可行解, 且相应的目标函数值为Z=15, 将4x1+7x2+5x3+7x4+8x5+15x6≥15作为过滤条件, 在从进程中计算出每个状态的目标函数值, 如表1所示。

Step 2 在各个从进程中根据过滤条件删除目标函数值小于15的状态, 然后按照目标函数值从大到小将状态进行排序 (各从进程最终结果数如表2所示) , 并且计算约束条件, 如表3所示。

由上述例子和结果可得, 用串行完全枚举的方法, 需要计算128次, 且每个状态都需要枚举, 假设计算机处理每个状态的时间为t秒, 则方法 (1) 中一共需要128t秒的时间, 而用本文的算法, 由上述表2和表3可知, 每个从进程需要计算16次目标函数值, 排序后, 从进程对于约束条件的计算最多需要4次, 即总共需要时间20t秒的时间就可以得到最大值38。利用串行枚举法所需时间是本文算法的6倍多, 可见利用本文中的算法节省了大量的时间, 提高了运算效率。

4 结 论

0-1规划问题中, 变量数目较大时, 用串行计算是很难解决, 甚至不能得到解决。本文结合高性能并行计算和隐枚举法来解决这个问题, 并对隐枚举法进行了改进, 即按照目标函数值的大小进行排序, 每个从进程只需要按照顺序检查其变量组合的可行性, 得到的第一个可行解就是局部最优解, 然后局部最优解和全局最优解进行比较, 最终得到全局最优解。从上述实例中可以看到, 本文的算法确实提高了解题速度, 对于计算较大规模的题目具有一定的应用价值。但由于排序本身需要耗费一定的时间, 当规模较小时, 并不一定能够达到优化的目的, 而且对于规模较大时, 如何减少排序花费的时间仍然是一个值得探讨的问题。

摘要：0-1规划中, 当变量较大时, 状态数过多、时间耗费较大, 隐枚举法是目前解决0-1规划问题最有效的方法, 并行计算的特点是快速解决大型且复杂的计算问题。结合并行计算和隐枚举法来解决这个问题, 并且对隐枚举法做了一定的改进, 使得在串行计算中难以实现的问题在并行计算机上得到了解决, 并用实例验证了算法的可行性和优越性。

关键词：0-1规划,并行计算,隐枚举法

参考文献

[1]JIAMei-li.Master-Slave Parallel Mind Evolutionar Computation Basedon MPI[J].Joutnal of North University of china (Natural Science EDItion) , 2007, 28.

[2]罗省贤, 何大可.基于MPI的网络并行计算环境及应用[M].成都:西南交通大学出版社, 2001:104-197.

[3]黄旭东, 林鹭.基于Linux集群的并行环境简单架设[J].计算机应用研究, 2004 (11) :254-256.

[4]Qin Taigui, Zhu Hanye.An Improves Implicit Enumeration Method[J].三峡大学学报, 2007, 29 (6) .

求解0-1规划的一种新隐枚举法 篇5

0-1规划是一种特殊形式的整数规划.这种规划的决策变量仅取值0或1, 故称为0-1变量或二进制变量.0-1变量可以数量化地描述诸如开与关、取与弃、有与无等现象所反映的离散变量间的逻辑关系、顺序关系以及互斥的约束条件, 因此主要用于求解互斥的计划问题、约束条件互斥问题、固定费用问题和分派问题等方面.用于求解0-1规划的主要方法有穷举法和隐枚举法.采用隐枚举法解0-1规划问题时要根据目标函数的性质增加一个相应的不等式作为附加约束条件, 称为过滤条件, 以减少运算次数.一般还要按目标函数中的系数递增的顺序, 重新排列目标函数和约束条件中的次序, 以简化计算.本文从约束条件对应的系数矩阵入手来判断问题的最优解, 通过算例证实具有可行性, 有效性.

2算法

考虑如下的0-1线性规划模型:

max Z=CX,

其中A=[aij]∈Rm×n, X= (x1, x2, …, xn) T, b= (b1, b2, …, bm) T, C= (c1, c2, …, cn) .不妨设0≤c1≤c2≤…≤cn, 如果目标函数有负价值系数的可以通过变换化为正系数, 则可知决策变量都取1时, 目标函数肯定最大, 但是不一定满足约束条件, 所以我们先可以让价值系数小的决策变量取0试探, 让目标函数逐次减小, 直到找到最优解.计算步骤如下:

第1步, 计算系数矩阵A=[aij]∈Rm×n的每一行的和:

第2步, 计算:

Q (1) i=bi-S (1) i, i=1, 2, …, m.

第3步, 如果Q (1) i≥0, i=1, 2, …, m, 说明X= (1, 1, …, 1) T就是0-1规划的最优解, 否则计算

和Q (2) i=bi-S (2) i, i=1, 2, …, m.

如果Q (2) i≥0, i=1, 2, …, m, 说明X= (0, 1, …, 1) T就是0-1规划的最优解, 依次类推, 直到找到0-1规划的最优解.

3算例

例1求解0-1整数规划问题:

解由于目标函数的价值系数有负的, 作变换令x2=1-y2, 原题化为:

由上式可知

第1步, 计算系数矩阵A=[aij]∈R4×3的每一行的和:

S (1) 1=-2, S (1) 2=-2, S (1) 3=0, S (1) 4=5.

第2步, 计算:

Q (1) 1=2, Q (1) 2=2, Q (1) 3=2, Q (1) 4=1.

所以Q (1) i>0, i=1, 2, 3, 4, 说明 (y2, x1, x3) T= (1, 1, 1) T就是0-1规划的最优解, 通过变换x2=1-y2, 可知原0-1规划的最优解为 (x1, x2, x3) T= (1, 0, 1) T.

该方法相比其他方法[1,2,3,4,5]较简单明了, 具有可行性, 也便于程序化设计.

例2求解0-1整数规划问题:

解由于目标函数的价值系数有负的, 作变换令x2=1-y2, 原题化为:

由上式可知

第1步, 计算系数矩阵A=[aij]∈R3×3的每一行的和:

第2步, 计算:

所以Q (1) i>0, i=1, 2, 3, 说明 (y2, x3, x1) T= (1, 1, 1) T就是0-1规划的最优解, 通过变换x2=1-y2, 可知原0-1规划的最优解为 (x1, x2, x3) T= (1, 0, 1) T.

由以上两个算例可知, 该方法比一般的隐枚举法[1,2,3,4,5]更加直观, 思路简捷, 具有可行性和有效性.

摘要：求解0-1规划问题一般采用增加过滤条件的思路, 本文根据约束条件AX≤b对应的系数矩阵各行之和来判断0-1规划的最优解, 通过算例证实具有可行性.

关键词：隐枚举法,线性规划,最优解

参考文献

[1]教材编写组.运筹学[M].北京:清华大学出版社, 2005.

[2]卢向华, 等.运筹学教程[M].北京:高等教育出版社, 1992.

[3]胡运权.运筹学基础及应用[M].哈尔滨:哈尔滨工业大学出版社, 1993.

[4]牟世超.隐枚举法的改进及应用[J].预测, 1997 (6) :54-55.

时间枚举论文 篇6

在整数规划中, 隐枚举法 (Implicit enumeration algorithm) 是用于求解“0-1整数规划问题”的常见方法, 其基本思想是通过增加“过滤约束”舍弃一定不最优解的解组合以求得最优解[1]。在教学过程中发现, 许多学生存在这样的疑问:过滤约束应如何添加?作用何在?为此, 本文通过实例阐述隐枚举法的求解步骤、过滤约束的作用及“隐”字的含义, 帮助学生更好地掌握隐枚举法。

2 目标函数求max的0-1规划问题求解

[例1]求以下0-1整数规划问题的最优解?

求解步骤[2]:

(1) 寻找目标函数值下界。可以判断, 当可行解X= (0, 1, 0) T时, 该问题的目标函数值 (-2) 最小, 因此可以确定目标函数值下界, 即3x1-2x2+5x3≥-2。

(2) 构造过滤约束, 并将其加入到原约束条件中。

因函数函数值大于等于“-2”, 因此可能是0[X= (0, 0, 0) T) ]、3[X= (1, 0, 0) T) ]和5[X= (0, 0, 1) T) ]等, 可先构造过滤约束“3x1-2x2+5x3≥0”, 则原模型变为:

(3) 写出所有解组合, 比较目标函数值Z, 并检查是否满足约束条件和过滤条件, 得出最优解。过滤约束为“3x1-2x2+5x3≥0”的求解过程如表1所示:

当X= (0, 0, 0) T时, 满足所有约束条件 (包括过滤约束) , 因此在表中对应位置添入“√”, 此时目标函数值Z为“0”。当X= (0, 0, 1) T时, 满足所有约束条件, 因此在表中对应位置添入“√”, 此时目标函数值Z为“5”。当X= (0, 1, 0) T、 (0, 1, 1) T和 (1, 0, 0) T时, Z值分别为“-2”、“3”和“3”, 均小于“5”, 由于目标函数求最大值, 因此无须再去考虑X是否满足约束条件。当X= (1, 0, 1) T时, 满足所有约束条件, 因此在表中对应位置添入“√”, 此时目标函数值Z为“8”。当X= (1, 1, 0) T和 (1, 1, 1) T时, Z值分别为“1”和“6”, 均小于“8”, 因此可求得该问题的最优解为:X*= (1, 0, 1) T, Z*=8。

可见, 添加过滤约束可以加快筛选过程, “隐”去不可能成为最优解的解组合 (见表1加粗部分, 下同) , 以简化求解过程。但需注意, 过滤约束一定要选满足原约束条件。同时, 为保证解组合不遗漏, 可参照“二进制”的表达方法, 将所有解依次列出, 本题因有三个变量, 故解组合的数量为:23=8, 详见表1。

同理, 可构造过滤约束“3x1-2x2+5x3≥3”[X= (1, 0, 0) T]和“3x1-2x2+5x3≥5”[X= (0, 0, 1) T], 求解过程见表2。

当然, 对于本题如果构造过滤约束“3x1-2x2+5x3≥8”[X= (1, 0, 1) T], 求解过程将更加快捷。因此, 在求解目标函数求最大值的“0-1整数规划问题”时, 为使求解过程更加简捷, 应在多个过滤约束中选取右端常数较大的过滤约束, 过滤约束右端项越大求解越方便。

常见求解错误举例:

[例2]求以下0-1整数规划问题的最优解?[3]

许多学生首先构造过滤约束“4x1+3x2+2x3≥0”[X= (0, 0, 0) T], 然后按步骤求解, 过程如表3所示, 求解结果为:X*= (1, 1, 1) T, Z*=9。虽然求解结果正确, 但却犯了一个概念性错误, 即X= (0, 0, 0) T并不满足原模型约束条件 (“4x1+x2+3x3≥3”和“x2+x3≥1”) , 不能作为过滤约束。同时, 求解顺序是从Z值最小开始依次判断, 过程较为复杂。说明, 学生并没有掌握隐枚举法的解题技巧。更好的解法是:构造过滤约束“4x1+3x2+2x3≥9”[X= (1, 1, 1) T], 按Z值从大到小的顺序进行求解, 即优先考查Z值较大的解组合, 则很快得到最优, 过程见表4所示。

3 目标函数求min的“0-1整数规划问题”

对于目标函数求最小值的“0-1整数规划问题”, 求解步骤与求最大值时有所区别, 应首先寻找目标函数值上界, 其它步骤则与求最大值相同。主要技巧是:在可能构造的多个过滤约束中选取右端常数较小的过滤约束, 过滤约束右端项越小求解越方便。

[例3]求以下0-1整数规划问题的最优解?[4]

对于本题 (解组合数量为24=16) , 可构造过滤约束“2x1+5x2+3x3+4x4≤4”[X= (0, 0, 0, 1) T], 求解过程如表5所示, 求解结果:X*= (0, 0, 0, 1) T, Z*=4。

4 教学体会

对于决策变量较少 (如不超过4个) 的“0-1整数规划问题”来说, 隐枚举法是比较有效的求解方法, 其中“隐”字的含义是通过构造过滤约束排除不可能成为最优解的解组合, 减少求解过程, 快速得到最优解。在使用该方法的时候, 需要注意以下三点:首先, 判断目标函数“求最大值”还是“求最小值”, 以此确定求解顺序是从Z值“最大”还是“最小”开始;其次, 辨别所构造的过滤约束是否满足原模型的约束条件;最后, 应按“二进制”顺序写出所有解组合, 避免遗漏。在初学时, 学生可选择两道典型习题 (目标函数求“最大和最小”) 进行反复练习, 以掌握隐枚举法的求解思路和技巧。

参考文献

[1]王耀辉, 陈超, 孙鹏.0-1整数规划及隐枚举法在学生面试问题中的应用[J].中国科教创新导刊, 2011, (22) :89.

[2]常大勇.运筹学[M].北京:中国物资出版社, 2010.

[3]谢家平.管理运筹学[M].北京:中国人民大学出版社, 2010.