偏序规划

偏序规划（共6篇）

偏序规划 篇1

摘要：本文从“木块移动”问题引入人工智能领域的规划问题的解决方法, 比较了各种规划问题求解算法, 选择偏序规划算法来解决“木块移动”问题, 在介绍STRIPS表示法的同时分析了问题中的状态和动作, 研究了偏序规划算法中动作产生的过程, 讨论算法实现过程中数据存储和处理方法, 最后实现了“木块移动”问题的规划算法解决方案。

关键词：木块移动,状态,动作,偏序规划

1 问题的描述

人工智能领域规划问题的求解就是要寻找一个动作序列, 可以使问题从起始状态到达目标状态。“木块移动”问题就是其中的一个经典问题, 问题描述如下:

如图1所示, 在台子 (TABLE) 上放着A, B, C三个木块, 初始状态下A在TABLE上, C在A上, B在TABLE上;目标状态下, C在TABLE上, B在C上, A在B上。要求机器人在一次只能移动一个木块的前提下完成从初始状态到目标状态问题的求解, 也就是要找到一个动作序列, 使TABLE、A、B、C四者的状态从初始状态转化为目标状态[1]。

2 规划问题求解算法的比较

在“木块移动”此类问题的求解过程中, 找到达到一定目标的动作序列的过程称之为规划。可以将规划问题转换为“问题求解”问题:已知初始状态, 在可以选择的动作序列树上进行搜索去发现一条较短的路径来解决问题, 但是这种解决方式不是最好的方法。逻辑为规划问题的求解提供了一个很好的描述状态集合的方法, 这样就可以使用状态相关集合的逻辑描述明确地表达规划问题, 使用一阶逻辑机制来进行规划处理, 这是一种经典的规划方法——情景演算。然而在情景演算中将特定的规划问题转换为定理证明问题效率很低。

在实际应用中, 规划问题被限定在一定范围内, 如子问题独立性假设即问题是可以分解的, 因此可以利用规划问题的特殊性来寻求一个更为专用的解决方法——偏序规划算法。在这种解决方法中寻找状态描述和动作描述的联合, 以任意的顺序向规划中添加顺序, 并假设子问题独立性, 同时限制描述目标、动作和状态的表示方法——STRIPS表示法。

3 STRIPS表示法和偏序规划

在STRIPS表示法中, 状态采用常数文字的合取;目标采用文字的合取;动作是由前提和效果来表示, 其中前提指能够采用这个动作的条件, 效果指动作发生后状态的变化。

在“木块移动”问题中, 对象有木块A、B、C、TABLE, STRIPS表示:

初始状态:on (A, T) ∧on (C, A) ∧on (B, T) ∧clear (C) ∧clear (B)

目标状态:on (A, B) ∧on (B, C) ∧on (C, T) ∧clear (A)

动作:

Move (b, x, y) :将木块b从x上移到y上。

前提:on (b, x) , clear (b) , clear (y) , block (y)

效果:on (b, y) , clear (x) , -on (b, x) , -clear (y)

Move T (b, x) :将木块b从x上移到TABLE上

前提:on (b, x) , clear (b)

效果:on (b, Table) , clear (x) , -on (b, x)

其中谓词on (x, y) 表示对象x在对象y上, 谓词clear (x) 表示对象x上没有其他对象, 谓词block (y) 表示y不是TABLE对象。

规划算法求解过程中就是添加动作的过程。偏序规划算法从目标状态开始采用逆向搜索方式进行动作的添加;添加的动作所产生的效果是可以达到部分目标或者可以达到其它动作的前提条件, 同时判断选取的动作是否造成冲突, 并通过升级或降级的方式来解决冲突, 若冲突无法解决则选择其他动作。由于在动作选择过程中已经加入了解决了冲突保持了一致性, 因此判断算法结束的条件为目标状态是否全部满足。具体算法描述如下:

首先构造初始规划, 初始规划包含两个初始动作, 分别称为Start和Finish动作。其中, 初始状态是Start动作的效果, 目标状态是Finish动作的前提条件, 将目标状态作为所有的开放前提。然后选择一个尚未满足的前提条件C作为子目标, 在规划中选择一个Si或找到一个效果中包含条件C的新步骤Si, 如果不存在这样的步骤Si, 则算法失败;为了进行扩展和保持一致性采取以下的方式:将因果链和序约束添加到规划中, 如果动作Si不在规划中, 则将Si添加到规划中, 同时添加序约束和。在这个过程中, 添加一个动作S可能对原有的因果链造成威胁, 因此需要排除威胁, 而排除威胁的方法有两种提升动作S或降低动作S, 即通过添加序约束或添加序约束来解决, 如果两种方法都导致规划失败, 则选择其他的动作C。循环上述过程直到所有的开放前提都满足。

4 问题的偏序规划算法实现

实现此类算法首先需要解决状态数据的存储然后是规划动作的存储, 本文中采用单链表结构存储各种数据。从上节分析中可以看到状态数据、动作中的前提、效果数据均采用的谓词表示, 因此这类数据的存储可以统一处处理为基本谓词的存储。如主要谓词结构On数据结构设计如下:

该结构中包含m_x和m_y两个数据域, 分别存放谓词中的两个变量, 程序中使用On作为此结构的数据类型。

规划动作结构定义中包含m_operator、m_x、m_y、m_z四个数据域, 存放步骤集合中的每一个动作, 如:Move (x, y, z) 或Move T (x, y) , 其中m_operator存放动作名称”Move”或”Move T”, m_x、m_y、m_z存放动作中的变量, 如果步骤为”Move T”则m_z中存放非法变量’*’, 程序中使用Result作为此结构的数据类型其定义如下:

在算法实现过程中使用数据实体On Sorce On, Goal On;分别描述初始规划中Start中的的On谓词集合以及Finish中On谓词集合;使用Clear Sorce Clear, Goal Clear;分别描述初始规划中Start中的的Clear谓词集合以及Finish中Clear谓词集合;使用Result result;描述规划中的动作集合。

在规划算法中主要选择动作过程的实现, 根据上节对于算法的描述, 使用Choose Operator函数实现选择动作操作, 算法部分主要代码实现如下:

使用Visual C++6.0实现, 对于本文第一节描述的初始状态和目标状态, 程序运行时, 分别输入初始状态下各个谓词实体中的前提条件和目标状态下各个谓词实体中的子目标, 通过计算规划中的动作实现结果如下图所示, 此结果和预期结果一致:

在实验中, 验证各种测试数据的输入, 从输出结果看不仅给出了规划中所需的动作, 而且还按照移动顺序给出了规划动作的输出, 测试结果与预期结果一致。但是在数据输入时需要明确写出初始与目标之间显著的不同, 若给出的目标谓词过少, 体现不了前后的变化, 会导致程序无结果输出, 如初始化谓词On集合有On (c, b) 、On (b, a) 、On (a, T) , 初始化谓词Clear集合有Clear (c) 、Clear (T) ;目标谓词On集合只给出On (c, b) , 则程序无结果, 此类情况需要改进输入数据, 增加On (b, T) 谓词, 则可以给出正确的输出结果, 实现了“木块移动”问题的求解。

5 结论

本文以“木块移动”问题的解决需求为基础介绍了人工智能中规划问题的求解, 研究了该问题的偏序规划问题的求解, 分析并实现了规划求解过程中的状态和动作数据结构的存储, 同时实现了规划动作选择算法, 通过数据验证了算法的实现, 达到了预期效果。

参考文献

[1]赵丹青, 胡宝玉.状态空间搜索算法的几种讨论[J].中南民族学院学报:自然科学版, 2001, 20 (3) :46-49.

基于偏序简化的并发系统验证 篇2

在基于构件的软件开发CBSD(Component Based Software Development)中,需要对构件交互协议进行形式化描述和验证。而构件交互协议是一种典型的分布式并发系统模式。上世纪七十年代末,R.Milner和C.A.R.Hoare分别提出了CCS(Calculus of Communicating Systems)和CSP(Communication Sequential Processes),共同开创了用进程代数研究通信并发系统的先河。之后基于进程代数模型检测技术就成为分布并发系统模型检测的热点。目前对协议模型的验证和检查主要采用进程代数方法。

在并发系统中,子系统间互补的迁移同步,其余的迁移是交错进行。这是引起模型状态空间爆炸的主要原因。提出组合可达性分析(Compositional reachability analysis)算法,通过弱等价关系缩小模型规模,但该算法首先需要遍历组合模型的所有状态,所以并未彻底解决问题。

状态爆炸问题往往出现在进程并发合成环节上,若能限制与子系统交互的环境就能控制其状态规模。普度大学的Wei Jen Yeh[2]提出通过改造并发模型进程代数的定义来控制进程组合中间过程的状态爆炸技术。

上述多种并发模型检测技术都有各自的优势,然而它们仅仅是去除模型组合中间过程出现的冗余状态,还不能够有效解决状态爆炸问题。Bell实验室的Patrice Godefroid[3]仔细研究了并发模型中迁移的依赖关系,提出针对状态爆炸的偏序简化技术,在Petri网描述的并发模型上得到了很好的应用,但至今还未在进程代数描述的模型上得以应用。

而以通信系统演算CCS为代表的进程代数,因其概念简洁,可用的数学工具丰富,在并发分布式系统的规范、分析、设计和验证方面获得了广泛应用。所以,本文提出基于进程代数的偏序简化算法,通过引入迁移交织执行顺序的表示,即迹(trace)的概念[3,4]达到对状态空间简化的目的,从而缩小了组合模型的规模,减少了验证算法所需遍历的状态数,提高了验证效率。

1迹与偏序

偏序技术(partial order technique)是一种基于迹的状态化简技术[6],可实施迁移之间的偏序关系准确地表示了系统迁移之间的相互独立或依赖关系。这种技术能有效地减少模型检测过程中需要被搜索的状态空间数量。偏序简化技术(partial order reduction)通过消除迹中的冗余迁移序列来对状态迁移图进行化简,主要有稳固集技术和睡眠集技术[3]。与偏序简化技术密切相关的两个基本概念是迁移的独立性和迹。

偏序与迹的对应关系是:迹中的迁移序列就是其迁移偏序经线性化的所有全序集合。如图1中T={t1,t2,t3,t4}。迁移t1分别与t2和t3相依赖(用从t1指向t2和t3的弧表示),迁移t4分别与t2和t3相依赖,t2和t3相互独立。所以:

D={(t1,t1),(t2,t2),(t3,t3),(t4,t4),(t1,t2),(t2,t1),(t1,t3),(t3,t1),(t2,t4),(t4,t2),(t3,t4),(t4,t3)}

那么迁移序列ω=t1t2t3t1就代表了迹[ω]={t1t2t3t1,t1t3t2t1}。因为t1t3t2t1中迁移t2和t3相毗邻且相互独立,交换位置后就可得到新的迁移序列t1t2t3t1。

稳固集是定义在每个状态上的可实施迁移集合。在每个状态中,应该能够选择与其他可实施迁移子集相互独立的迁移子集予以实施。

稳固集的选择—搜索算法如下所示。该算法遍历到某一状态时,只沿着该状态稳固集中的迁移继续遍历。算法中用到栈与哈希表这两个数据结构。栈用来暂存需要遍历的状态,哈希表保存遍历过的状态。初始情况下把起始状态入栈,进入循环从起始状态沿其稳固集遍历其余的状态,直到栈空为止。

1 Initialize: Stack is empty:H is empty;

2 pash (s0) onto Stack;

3 Loop:while Stack≠ϕ do{

4 pop (s) from Stack;

5 if s is NOT already in H then {

6 enter s in H;

7 T=Persistent_Set(s);

8 for all t in T do {

9 s′=succ(s) after t:/* t is executed */

10 push (s′) outo Stack;

11 }

12 }

13 }

2偏序简化及其算法

在进程代数模型中,本文认为在动作前缀前后的迁移有相互依赖关系,如P=a.b.c.d中a与b相依赖,b与c相依赖。试想若a迁移不能执行,那么后续迁移都无法执行,所以依赖关系可以是传递的,即a与c也相依赖。有了依赖关系不难得出独立关系的定义,独立关系也可应用稳固集定义得到。顽固集定义是计算稳固集的有效算法,为了定义顽固集节,首先提出迁移冲突定义:

定义1 在状态s的迁移集合中,迁移t1和t2冲突,当且仅当,参与在s状态下并发合成的进程中,存在P=t1.P1+t1.P2,即t1和t2分别是进程P非确定选择项的首动作。

定义2Ts是状态s的顽固集,若Ts包含至少一个状态s的可实施迁移,并且∀t∈Ts,下面两条成立:

若迁移t在状态s不可实施,即参与在状态s并发合成的进程中,存在进程P拥有与t互补的迁移t′,但在状态s下还不可实施。那么从进程P当前状态出发到迁移t′可实施的所有前缀中的迁移也在Ts中。

若迁移t在状态s可实施,那么所有与t相冲突的迁移也在Ts中。

根据定义2可以得出顽固集算法,至此在进程代数模型上,已经定义了有效计算稳固集的算法。用稳固集简化模型状态迁移图后,再配合睡眠集去除稳固集中冗余迁移,之前定义的利用稳固集和睡眠集的选择—搜索算法在进程代数模型上完全适用,而且该算法也是有效的。所以我们就得出了如下的基于CCS的偏序简化算法。

1 Initialize: Stack is empty:H is empty;

2 pash (s0) onto Stack;

3 Loop:while Stack≠ϕ do{

4 pop (s) from Stack;

5 if s is NOT already in H then {

6 enter s in H;

7 T=Persistent_Set(s);

8 for all t in T do {

9 s′=succ(s) after t:/* t is execnted */

10 push (s′) outo Stack;

11 }

12 } else {

13 Iad=Adjust_per Set(s);

14 for all t∈Tad do {

15 s′=succ(s) after t:/*t is executed*/

16 push(s) onto stack

17 }

18 }

19 }

3基于偏序简化的并发系统安全性验证

传统的偏序简化算法仅针对于死锁的检查,并没有涉及安全性验证。下面给出利用偏序简化验证模型安全性的方法。

进程代数中进程是参与并发合成的实体,仔细分析参与并发合成的进程,首先分为递归形式和非递归形式两种,其下层又可分为确定形式与非确定形式。这两层分类直接影响进程并发合成的结果。如设参与并发合成的进程为P和Q,那么若P和Q都是递归形式就如图2所示。

根据基于进程代数的偏序简化算法对图4进行化简:首先选择c.d进行迁移,沿迁移序列c.d从(0,2)状态出发又返回到它,此时可以考虑再往状态(0,2)的稳固集中增加迁移集合Tad,然后再沿Tad中的迁移继续遍历。对于遍历过的状态再继续遍历的条件是该状态还有未遍历过的迁移。图2中在第二次遍历状态(0,2)时,函数Adjust_PerSet(s)向状态(0,2)稳固集增加迁移集合Tad={a},此时算法沿a遍历到状态(1,2),再沿b回到状态(0,2),此时(0,2)状态的所有迁移都已遍历过,且它的稳固集就是它的所有迁移集合,算法终止。

图2中的右侧子图就是经过偏序简化后的状态迁移图,虚线弧和虚线圆表示被删减的迁移和状态。由迹的定义,被删减掉的迁移都可以由相独立相毗邻的迁移互换位置而扩展出来。所以在验证模型的安全性质时,首先判断该性质定义的状态迁移图是否指定了模型中相互独立迁移的顺序,如性质P = a.c,即a与c相依赖。但在模型中a与c相独立,所以模型肯定不满足性质P。此时不能仅给出简化后的图的违反性质的路径,要考虑所有可能违反性质的路径,因为这样才能为开发者提供全面的信息。所以当模型不满足性质时,按照组合可达性分析安全性验证算法给出结论。如果模型满足性质,就给出偏序简化后的结果。

4结束语

本文将偏序规约应用于进程代数模型,给出了进程代数模型的偏序简化算法,并且提出验证安全性的方法。算法基于在并发模型验证中没有必要计算所有的迁移交织,而是由任一迁移交织来代替与其在同一迹中的其余迁移交织的思想提出的,从而达到对状态空间简化的目的,有助于提高验证效率,便于对并发系统进行安全性验证。

摘要：构件交互风格和交互协议的描述与验证是基于构件的分布式系统开发的基础和关键,而构件交互协议是一种典型的分布式并发系统。传统的方法难以解决系统建模和验证中的所谓的状态爆炸问题。偏序简化是应用迹的概念,对模型进行化简并且对模型进行死锁验证。但这样的验证重点放在了Petri网模型上,而没有涉及进程代数模型,所验证的只是模型是否有死锁状态。而以通信系统演算CCS为代表的进程代数,因其概念简洁,可用的数学工具丰富,在分布式并发系统的规范、分析、设计和验证方面获得了广泛应用。对此,提出将偏序规约应用于进程代数模型,给出基于进程代数模型的偏序简化算法,并提出利用进程代数模型偏序简化算法来验证安全性的方法。

关键词：分布式系统,并发系统,偏序简化,进程代数,安全性

参考文献

[1] Cheung S C,Kramer J.Checking Safety Properties Using Compositional Reachability Analysis. ACM Transactions on Software Engineering and Methodology (TOSEM), New York, NY: ACM Press,1999,8(1):49-78.

[2]Yeh W J.Controlling State Explosion In Reachability Analysis.SERC Technical Reports.SERC-TR-147-P,Purdue University West Lafa-yette,IN,USA:1993.

[3] Godefroid P.Partial-order Methods for the Verification of Concurrent Systems——An Approach to the State-Explosion Problem. Lecture Notes in Computer Science, Secaucus, NJ, USA: Springer-Verlag New York,1996,1032:142.

[4]Godefroid P,Wolper P.A Partial Approach to Model Checking.Papers presented at the IEEE symposium on Logic in computer science,Orlan-do,FL,USA:Academic Press,1994:305-326.

[5]Wolper P,Godefroid P.Partial-Order Methods for Temporal Verifica-tion.Lecture Notes In Computer Science,London,UK:Springer-Ver-lag,1993,715:233-246.

偏序规划 篇3

关键词：模糊偏序,人力资源风险决策,物流企业

物流企业作为高速发展的生产性服务业, 其行业具有较高的风险特点, 尤其是企业的人力资源风险。在物流企业的运用过程中存在很多风险, 事物可以计算得很准确, 而人力资本却很难量化。人力资本对物流企业而言是一把双刃剑, 在给企业带来竞争优势的同时, 也带来了很多风险问题, 这些不确定的风险问题主要是有物流企业内部和外部诸多因素造成的。目前, 我国物流企业95%以上都属于中小企业, 虽然发展速度较快但是起步较晚, 因此我国物流产业仍处于粗放型的发展阶段。物流企业如何从粗放型发展阶段向集约型发展阶段转变, 其最主要的发展对策就是依赖于人力资本, 如何衡量物流企业内部人力资源管理的风险决策问题也是目前物流企业发展中亟待解决的重要问题之一。而利用模糊偏序方法研究企业人力资源管理决策是物流企业采取风险决策的重要依据。

物流企业人力资源的风险管理者主要包括三种类型, 分别是风险爱好者、风险回避者和风险中立者。对于风险决策管理主要包括风险控制、风险回避和风险预防等方法, 对于不可避免的风险, 物流企业需要根据自身的承担能力和投资收益率来进行取舍。本文从物流企业人力资源的风险管理出发, 为了将企业人力资源风险进行量化, 利用模糊偏序理论和方法建立物流企业人力资源风险决策的虚拟模型, 为企业人力资源风险的分析、评价和决策等提供一定的参考价值。

1 模糊偏序理论及相关说明

1.1 本文研究目的和总体研究思路

一般而言, 物流企业人力资源风险投资决策存在不同程度的风险, 需要以针对性的措施加以应对。然而又可知物流企业人力资源风险投资的风险具有不确定性, 因此很多经典领域在此往往已不再适用。然而庆幸的是, 模糊数学理论的推广为研究不确定性提供了有效的思路, 模糊数学理论包含很多分支, 如模糊推理、模糊控制、模糊专家系统、模糊偏序等。本文尝试采用模糊偏序理论对物流企业人力资源的风险决策进行着重分析:首先明确模糊偏序理论的相关概念;其次提出具体的研究方法, 并利用数理模型解析模糊偏序理论在人力资源风险决策中的应用;然后通过实例加以分析。所谓模糊偏序理论, 就是将模糊数学知识与偏序理论结合起来进行研究, 此时特征值已不再全部是1, 而是[0, 1]中的某个值, 并含有隶属度。

1.2 模糊偏序理论与偏序集

首先定义一个在论域U上的模糊映射关系R: (1) 如果对任意的元素u属于论域U, 都有R (u, u) =1, 则定义模糊关系R具有模糊自反性。 (2) 如果对任意的元素u和v属于论域U, 都有R (u, v) =R (v, u) , 则定义模糊关系R具有模糊对称性。 (3) 如果对任意的元素u、v属于论域U, 当R (u, v) “与”R (v, u) 的值不等于零, 即R (u, v) ∧R (v, u) ≠0时, 必有u=v, 则定义模糊关系R具有模糊反对称性。其中, 第三种映射关系等价于对任意的元素u和v属于论域U, 如果u与v不相等, 则必有R (u, v) ∧R (v, u) ≠0, 此时R (u, v) 和R (v, u) 中至少存在一个是零。 (4) 如果对任意的元素u和v属于论域U, 都有模糊关系R2 (u, v) 包含于模糊关系R (u, v) , 则定义模糊关系R具有模糊传递性。若一个模糊关系具有模糊自反性和模糊传递性, 则称模糊关系为预序关系;若模糊关系模糊具有模糊自反性、模糊反对称性和模糊传递性, 则称模糊关系为偏序关系[1]。

偏序理论具有以下两个定理:

定理1:对于论域U上的模糊偏序关系R与论域U上的任意非空子集合V, 取任意的元素v1和v2属于论域V, 如果满足S在模糊关系F上的隶属函数都有S (v1, v2) 与R (v1, v2) 相等, 则S为论域V上的F偏序关系。

定理2:假定R是论域U上的一个F偏序关系, 如果满足|U|=-n, 而且R又具有F自反性, 那么就有R传递性, 即对于n, 都有成立。

1.3 模糊偏序关系分析

先来定义模糊偏序关系:设 (U, ≤) 是上述定义的一个偏序集, 如果R符合下面全部条件: (1) 对任意元素u, v属于论域U, 都有R (u, v) 在0与1之间; (2) 当u大于v时, 有R (u, v) 大于R (v, u) ; (3) 当u大于v时, 有R (u, s) 大于R (v, s) ; (4) 当u大于v大于s时, 有R (s, v) 大于R (s, u) , 则认为R是一个模糊偏序关系。

假定 (U, ≤) 是论域U在模糊关系上的一个偏序集, 且以分别表示比模糊元素xi更劣势的劣态集和比模糊元素xi更优势的优态集。其中, 具体的优态关系可由下式来表示:

或者:

实质上就是偏序集 (U, ≤) 上的一个模糊偏序关系。

下面根据这种模糊偏序关系推广到一般的模糊评估模型中, 假设 (U, Y, F) 是一个评估模型, 现对于一个映射F满足:

且对于论域中的元素, 有:

这里, y是集合A中元素的总个数。于是, 就是一个模糊偏序关系。这是用来判定一个模糊关系是否偏序关系的重要准则。

模糊偏序理论反映了模糊现象之间存在的一种关系, 结合模糊优劣态关系 (即式1) 和模糊偏序关系 (即式2) , 便可构造一个反映模糊关系的模糊偏序关系决策模型。

2 基于模糊偏序理论的物流企业人力资源风险决策实例分析

2.1 企业人力资源风险决策的不确定性说明

企业的人力资源管理存在不确定性风险, 因此管理过程显得非常复杂, 这极可能使企业监督管理层对人力资源风险事件的产生和可能导致的后果都无法预先确定, 于是也就很难进行风险决策。在这种不确定性风险决策中, 一般企业决策者都无法明确知晓风险事件发生的概率以及产生后果的严重程度, 所以只能靠主观的猜测进行经验判断[2]。在人力资源风险决策中, 一般如果风险事件的结果概率容易得知, 于是企业决策者也可以根据风险事件的期望值进行决策, 遗憾的是实际操作过程中风险事件产生结果的概率分布非常复杂, 而且一般都难以精确获得。人力资源内部结构关系非常复杂, 因此不确定的因素相对绩效管理等而言就显得较多, 因此企业决策者应试图从其他途径出发而寻找有利方案。

而模糊偏序理论恰为企业人力资源管理风险决策提供新的视野, 这种方法通过结合企业风险指标的优劣性顺序和全序来进行比较, 并得到风险决策方案。模糊偏序理论可以说是将决策方案的同比性和异类性有效结合起来, 本文的具体研究方法为: (1) 根据物流企业人力资源风险决策目标, 对相关信息进行指标设定, 并建立知识库收集资料; (2) 构建决策方案, 并根据模糊偏序理论得到最优解; (3) 通过专家审定, 对结果进行分析。

2.2 物流企业人力资源风险决策实例分析

为更好地分析模糊偏序理论在物流企业人力资源风险决策中的应用, 本文选取某物流企业A进行实例分析。首先, 根据该物流企业人力资源风险决策目标, 设定其人力资源风险管理的备选方案集为:, 其中, x1代表工资水平提高25%, 工资水平将高于在本物流企业三年以上专业技术人员的收入水平;x2职位升级到技术主管人员, 主要管理物流企业的各种高级业务;x3是物流企业新增若干工程师, 从事研究中心的主要任务, 其待遇水平将与规定的工程师待遇水平相当;x4是派出若干名精英至国外进行合作交流一定时间, 并安排学习, 完成后担任物流企业相关职务。

为清晰地反映物流企业人力资源风险决策的各种因素, 根据物流企业的实际情况, 构建如下因素评估指标集:

其中, 元素y1表示物流企业主要人员的满意度, 该指标考察风险决策方案的实施使企业主管人员的接受程度;y2表示物流企业主管人员的忠诚度, 主要通过方案的实施来考察企业主管人员的忠诚度对物流企业的影响;y3是方案的可行程度, 考察物流企业对该方案的接受度和方案的实际可行程度;y4是相关程度, 考察该方案的实施与物流企业主管人员发展之间的相关程度;y5是反映程度, 考察物流企业其他主要人员对该方案的反馈程度[3]。

根据物流企业高层管理人员、有关专家的咨询意见, 本文设定物流企业A的人力资源风险决策数据如表1所示。

根据模型 (2) , 可以得到表1对应的模糊偏序关系为:R=[1, 0.4, 0.6, 0.5;0.5, 1, 0.6, 0.6;0.8, 0.4, 1, 0.7;0.6, 0.4, 0.6, 1], 根据模糊偏序公式[4]:

得到论域U上的一个全序为:。根据前面的定理2, 可知R的传递闭包R’=[1, 0.4, 0.6, 0.4;0.6, 1, 0.5, 0.6;0.4, 0.5, 1, 0.6;0.6, 0.4, 0.7, 1]。根据R’可得到物流企业风险决策方案的全序优劣态为:, 偏序优劣态为:或者。由此可见, 由模糊偏序理论得到的偏序优劣态中, 不可比较的方案是x3和x4, 但x2的优态和x1的劣态是显然的, 而至于x3和x4, 物流企业的风险决策者可以根据自己的决策目标和实践经验加以选择。尤其是物流企业风险决策者在给出备选方案的时候, 往往对备选方案的权重具有一定的设置, 因此当x3和x4不可比较时, 决策者可以根据两者的权重进行取舍;或者决策者可以通过专家咨询等途径, 对x3和x4的重要性有充分深入了解, 然后进行决策。根据实证结果可知, 该物流企业应在派员工去国外学习这方面加以引导, 而至于给员工加薪就不太有效了, 可能其他物流企业愿意以更高的工资待遇聘请员工。

3 结语

本文主要应用模糊偏序理论, 对物流企业人力资源的风险决策进行探讨。在分析过程中, 首先引入模糊偏序理论并对其加以说明, 然后应用该理论进行实例分析。实例分析表明, 模糊偏序理论应用于物流企业人力资源风险决策的可行性较高, 并且能发挥一定的优势。通过模糊偏序理论可得到人力资源风险决策备选指标的优先顺序, 为物流企业管理者提供理论证据。利用模糊偏序理论进行分析, 不但能够通过指标的关系计算备选方案的可比性和异类性, 还能充分反映指标数值的变化, 这是一种较全面和有效的分析方法。

参考文献

[1]李柏年.模糊数学及其应用[M].安徽:合肥工业大学出版社, 2007.

[2]刘建, 李莉, 关宇航, 苑德江.物流企业经营风险预警模型构建及其实证研究[J].物流技术, 2010 (12) .

[3]曾捷英, 邹燕.企业人力资源供应链管理的风险管理研究[J].物流技术, 2010 (11) .

[4]杨健鑫, 周石鹏.人力资源风险中的产权因素浅析[J].现代管理科学, 2003 (05) .

[5]张亚莉, 杨乃定.企业内部人力资源风险防范[J].科学学与科学技术管理, 2001 (11) .

偏序规划 篇4

弗朗西斯曾经说过：“你可以买到一个人的时间，你可以雇到一个人到指定的工作岗位，你可以买到按时或按日计算的技术操作，但你买不到热情，买不到创造性，买不到全身心的投入，你不得不设法争取这些。”这句话生动地道出了激励的重要性。激励在人力资源中主要的作用是激发员工的潜力、提高员工的绩效、增强组织的凝聚力，是企业挖掘人力资源的重要内容。由于企业在拟定激励方案时要必须考虑员工配备与岗位设置、员工报酬与激励模式、工作计划与设计流程、培训模式与方法设计、员工考核与绩效评价等各个方面，此外，各评估对象及激励方案之间的关系也是模糊的，这些就决定了其激励评估的复杂性和特殊性。因此，将模糊优选法与偏序关系结合起来，提出了企业员工激励评估模型，能够真实的反映了激励评估对象之间相互比较的不确定性，满足了多方案、多指标的综合性分析与评价需要。

建立激励评估模型的目的主要在于以下三方面：首先是激励因素的识别与筛选。人力资源激励因素识别主要有全面检视激励的范围与内容，查找激励的可能性与可行性;研究某一重要或高级管理人员及团队可行的激励方式;根据企业自身的情况，建立激励评估指标体系。其次是激励因素的分析与评价。主要包括激励因素的影响分析与评价;存在和发生的时间分析与评价;影响级别的分析与评价;起因和可控性的分析与评价。再次是激励效果的评估与考核。通过激励效果分析，为拟定激励计划提供数据与信息支持;能够准确的预测与决策，实现对计划的动态更新;确定员工激励的关键点，从而采取积极有效的措施与策略。

2 模糊关系的排序法

2.1 模糊偏序

定义1：设是偏序集(∪，≤)，称关系模型为模糊偏序模型，若R是模糊偏序关系，且(xi, xj, xR∈∪)，即满足以下条件：

(1) 0≤R (xi, xj) ≤1 (xi, xj∈∪) ;

(2) 当xi≥xj时R (xi, x) j≥R (xj, xi) ;

(3) 当xi≥xj时R (xi, xk) ≥R (xj, xk) ;

(4)当xi≥xj≥xk时R (xk, xi)≥R (xk, xj) ;。

2.2 评估决策的模糊偏序模型

设(∪，A, F)为评估值模型, 其中, ∪={x1, x2……xn}为评估对象或方案集, xi为第i个评估对象;A={a1, a2……am}为评估属性集, al为第l个评估属性;F={fl：∪→V1 (l≤m)}为评估对象与评估属性之间的关系集, 其中, fl (xi)表示评估对象xi关于评估属性a1的测定值, Vl为属性al的可能取值的全体, 称为评估属性al的取值域, V1=[0, 1], 记

F (x) i= (f (1x) i, f (2x) i, …fm (x) i) ;xi∈∪.

引入下面记号:

xi≥xjF (x) i≥F (x) jf (1x) i≥f (1x) j;1≤m.

则{∪, ≤}为偏序集, 称关系模型 (∪, ≤, R) 为模糊偏序集模型。

设 (∪, A, F) 为评估模型

F={f1:∪→[0, 1], (l≤m) },

式中m为集合A中的元素个数, 则R (Xi, Xj)为模糊偏序关系[7]。

2.3 求出R的传递闭包

R的传递闭包为:是具有模糊自反性和模糊传递性的模糊关系，因此，是∪上的模糊预序关系。

2.4 确定优越元

定义2：给定论域∪上F偏序关系R，对xi∈∪，若对∪中其它元xj，都有R (xi, xj)=0，则称xi为R的优越元;并称D(∪)={xi|xi∈∪}为∪对R的优越集，若R是有限论域∪上F偏序关系，则对R，∪中必存在优越元。

2.5 模糊次序确定

对于连续值信息系统, 建立偏序关系后, 再利用公式

即可得到U上的全序。

根据有限论域U上的F预序关系，确定元素优越次序, 当xi, xj∈∪时，运用公式(3)对F偏序关系下元素优越次序对Q进行排序[5]，

3 建立基于模糊偏序的人力资源激励评估模型

某公司人力资源管理部门针对某骨干的自身专业水平、工作业绩、发展规划等，会同有关领导、专家建立了激励评估系统，拟定了备选方案集，x1为加薪15%;x2为奖励3000股企业内部股份;x3公司聘任其工程师，x4为派到韩国的合作方学习一年;x5为升技术主管。并建设了评估指标集，其中，a1为忠诚度;a2为可行度;a3为相关度;a4反应度，设等级{强，较强，中等，一般，差}，分别赋值为{0.9, 0.7, 0.6, 0.5, 0.4}

3.1 建立模糊评估信息系统

调查结果如下表1所示

则建立模糊评估信息系统(∪，A, F)如表2

再利用式 (1) 得到∪上模糊偏序关系R:

由，得传递闭包为

根据公式(2)计算出∪上的全序R (x1)=3.25;R (x2)=4.5;R (x3) =3.25;R (x4) =3.5;R (x5) =5;得到顺序为:根据公式 (3) 的Q:

根据上述优越元的确定得：第一优越元为x5，借助Q确定出∪的元素的优越次序，结果显示不可比较的方案为(x1, x3)，相对优方案为x5，相对劣方案为x1和x3。

3.2 结果分析

由上述模型可知，最好的激励模型为升为技术主管，最劣的激励模型为加薪15%和公司聘任其为工程师，所以专家、领导应选的对该骨干的激励措施为升其为技术主管。

4 结论

激励创造供给。在人力资源管理中，激励的作用是十分明显的, 是人员提供追求与达到目标的手段, 同时激励对组织的生存和发展有着非常重要的作用，从过去的靠精神激励，到近年来的靠以金钱为代表的物资激励。通过模糊偏序分析方法找出目前激励机制所存在的问题, 引出现代完善激励机制的几种主要途径，其中激励评估模型的建立和完善对完善激励机制具有重要的意义，将指标优越次序和全序结合起来比较方案，融合了两者的长处，既能体现方案的可比性和差异性，反映各因素指标之间的变化，能够满足多指标、多属性的方案比较和择优，具有一定的合理性、实用性。

参考文献

[1]Senqupta K.Choice rules with fuzzy preferences, some characterizations[J].Social Choice and Welfare, 1999;16:259-272.

[2]Pattanaik P K, Sengupta K.On the structure of simple preference-based choice function[J].Social Choice and Welfare, 2000;17:33-43.

[3]陈明立.人力资源通论[M].四川:西南财经大学出版社, 2004:137-148.

[4]苏东斌.激励创造供给:高兴技术产业中的人力资本[J].经济动态, 2000 (, 7) :2-3.

[5]王祖成.世界上最有效的管理——激励[M].北京:中国统计出版社, 2002:46-67.

[6]于桂兰, 魏海燕.人力资源管理[M].北京:清华大学出版社, 2004:332-363.

[7]陈启浩.模糊值及其在模糊推理中的应用[M].北京:北京师范大学出版社, 2000:57-97.

偏序规划 篇5

体量(Volume)大、增长迅速(Velocity)、类别(Variety)多、价值(Value)密度稀是大数据的“4V”特征[1]。而电力大数据的特征可以进一步概括为“3V3E”,其中“3V”分别是体量(Volume)大、类型(Variety)多和速度快(Velocity),3E分别是数据即能量(Energy)、数据即交互(Exchange)、数据即共情(Empathy)[2]。随着智能电网建设和物联网技术在电力行业中的广泛应用,电力系统的运行、检修和管理过程中产生了全景的海量状态数据,它们具有多态和异构形态,即呈现出大数据特征[3]。这类大数据根据其表示形式大致可划分为:能够存储于关系数据库中的结构化数据,各类能够以电子文件形式存储的文档、信息等广义数据,以及视频监控、图像处理产生的非结构化数据等[4]。在这些电力大数据中尤其是非结构化数据增长势头最快,其体量远远超过了结构化数据,体现出了大数据的 “3V”特征,又因为这些大数据中夹杂着大量的噪声数据,这同时体现了大数据的价值密度稀的特征。例如,某电力数据中心在2011年产生的数据记录日均增量就已经超过了5 000多万条,这还不完全包括诸如状态监测、空间地理信息以及其他一些系统所产生的大量数据[5]。按照这个爆炸性的增长趋势,电力大数据中隐藏的价值也会逐渐增加,对这些海量数据进行有价值的信息挖掘的需求也迫在眉睫[6]。如未来智能电网自愈性的前提条件就是实现故障诊断与预测[7],为了从这些海量数据中挖掘出对电网管控起决定性作用的信息,也同样需要对这些海量数据进行层层筛选,但这类操作需要耗费大量的时间。行之有效的方法就是对这些海量数据进行预处理,例如,文献[8]通过对输变电设备状态大数据进行预处理环节之一的数据清洗,从而提高了数据质量。又因为属性约简是其中一个重要环节,因此,本文在分析大数据属性特征的基础上,重点研究电力大数据预处理中的属性约简方法。

现有的启发式属性约简诸如基于正区域的、基于边界域的、基于信息熵等算法都是在计算出属性核后,把余下的属性根据其重要程度从高到低依次添加到属性核中;或者从所有属性中依次去掉重要性比较低的冗余属性[9]。这些启发式算法虽然在约简效率方面相当显著,但由于其在约简过程中容易删除一些重要性比较低的属性,这可能造成决策表的部分有价值信息丢失。文献[10-14]给出的都是传统的启发式属性约简算法,它们把要处理的数据一次性装入内存,在属性约简方面表现出了优良性能,但只适合于处理小规模数据集。文献[15-18]通过把粗糙集理论与其他一些算法进行结合使用,来改善粗糙集的属性约简难题,相对于传统的启发式属性约简算法,效率有所提升,但同样也只适合于处理小规模数据集。文献[19]给出的是大数据环境下多决策表的区间值全局近似约简,相对于上述文献,约简的效率有了进一步提升,但其并行化程度较低,不完全适用于电力大数据的处理过程。文献[20]在文献[10-14]的基础上结合MapReduce框架,把上述处理小规模数据集的约简算法在MapReduce框架下运行,虽然克服了其在处理大规模数据集时所面临的内存瓶颈问题,但由于启发式算法本身固有的缺陷,依旧存在决策表部分信息易丢失的问题。文献[21]在文献[20]的基础上对基于正区域的算法进行改进,结合MapReduce模型给出了一种并行计算电力大数据集相对正域势的属性约简算法,虽然相对于文献[20],算法的效率有所提升,但依旧避免不了决策表部分信息易丢失的问题。文献[9]将遗传算法在MapReduce框架下运行,虽然在处理大规模数据集时具有可行性,但由于遗传算法本身的复杂度,导致约简的效率偏低。

通过上述对约简算法的分析可知,传统约简算法存在容易导致信息丢失、效率偏低等不足。而电力系统的运行、监测信息具有显著的并行性,传统约简方法不能完全解决电力大数据属性约简的预处理问题,需要引入新的适应并行化处理的方法。而在并发软件的处理方法中有一种交叉模型,即独立发生的所有事件被排列成一个称为交叉序列的线性序列,而比较有效的方法是偏序理论模型,依据该模型,并发事件不需要排序,每一个偏序执行都对应多个交叉序列。如果性质刻画不能区分这样的序列,那么选择其中之一就足够了。可见,偏序约简技术对于等价的行为序列在约简图中只需保留一个即可;而且,由于程序执行的独立性,使得偏序约简技术具备了并行化特征;又因为偏序约简方法是根据决策属性的值对电力数据集进行定性分析,能够确保电力数据集的原有信息得以保持。

在上述背景下,本文通过引入偏序约简方法,建立一种基于偏序的电力大数据属性约简方法。首先概述了启发式约简算法的求核过程,并为说明偏序约简方法在电力大数据预处理中的适用性,介绍了偏序约简方法的相关概念。然后,给出了偏序约简方法在处理电力大数据属性约简时的建模过程,并通过仿真实验说明了该算法的可行性。最后,对该算法的性能进行了总结,并对未来的研究工作进行了展望。

1 启发式约简算法的求核过程

以附录A表A1 所列出的某光伏发电系统在30d内每天24h的光能辐照度数据为例对传统启发式约简算法的求核过程进行说明。由于智能电网大数据类型多、数量大、增长迅速、价值密度稀,需要进行处理才能从中获取有利于电网决策的有价值信息。启发式约简算法都是基于粗糙集理论的,而粗糙集理论是一种用于从不完整数据和不精确的知识表达中挖掘知识的重要工具,并行化的启发式约简算法具有并行化处理模式,因此,并行化启发式约简算法在一定程度上可以解决智能电网大数据类型多、数量大,价值密度稀的难题。以下给出电力系统中电力大数据应用启发式约简算法的求核过程。

1)把上述光能辐照度数据看作一个电力系统信息决策表(U,A,B,C),U表示全体数据对象的集合,A表示全部属性的集合,B和C为A的子集,且A和B中不存在相同属性;C的B正域是U中所有根据分类U/B的信息可以准确地划分到关系C的等价类中去的对象的集合。

2)若b为B中的一个属性,如果C的B正域和C的B-{b}正域相等,那么b为B中C不必要的,否则b为B中C必要的,B中所有C必要的属性集合则构成了B的C核。

3)如果把B看作电力系统信息决策表中所有条件属性构成的集合,C看作电力系统信息决策表中所有决策属性构成的集合,那么由此就得到了上述光能辐照度数据所构成的信息决策表的属性核。

2 偏序约简方法的适用性

2.1 偏序约简的相关概念

某独立事件的发生相对于其他独立事件是随意的,但大多数刻画并发系统的逻辑都对应不同顺序发生的独立事件分别考虑,即对所有独立事件的交叉发生都予以考虑,这就导致了一个极大的状态空间。偏序约简方法通过着眼于并发事件间的独立性,即当两个事件以任意顺序发生均导致若干相同的全局状态时,称这两个事件是等价的,那么,对于这两个事件可以选择仅处理其中之一即可。

偏序约简方法致力于减少必须考虑的交叉序列数目,从而可以约简模型的状态空间。文献[22-24]是国外学者通过使用偏序约简方法解决软件状态空间爆炸问题上的应用研究,并通过仿真实验,取得了令人满意的结果。但对于电力大数据的属性约简,偏序方法还不能直接使用,需要对其进行适应性改进。为便于理解偏序约简方法在电力大数据预处理过程中的应用,下面给出适应电力系统大数据属性偏序约简的相关概念[25]。

1)给定一个四元组的初始状态变迁系统(S,T,S0,L),其中S为所有状态的集合,S0为初始状态的集合,L为标记函数,T为变迁的集合,对于每一个α∈T,都有α⊆S×S。对于变迁α∈T,如果有一个状态S′,使得α(S,S′)成立,则α 在S′处是激活的,反之,则称α 在S′处是非激活的,在S′处所有激活的变迁集合记为Senabled。对于每一个状态S′,只选择所有激活变迁的集合Senabled的一个子集———充足集Sample,而非整个Senabled,这是因为从Senabled出发将构建全状态图,而非约简状态图。

2)若两条无限路径和是Sstuttering等价的,当且仅当它们满足条件:存在两个无限的正整数序列0=i0<i1<…和0=j0<j1<…使得对于每一个k≥0,都有记为σ~stρ。称具有相同标记集合的连续状态序列为块,在两条路径被划分为无限个块后,如果其中一条路径的第k块的标记集合和另一条路径第k块的标记集合相同,则称这两条路径是Sstuttering等价的。

3)若独立关系I⊆T×T是一个对称的、反自反的关系,对于任意的状态s∈S(每一个(α,β)∈I),满足下面两个条件。

激活性 如果(α,β)∈Senabled,那么α∈(β(s)enabled)。

交换性 如果(α,β)∈Senabled,那么α(β(s))=β(β(α))。

依赖关系D是独立关系I的补,表示为D =(T×T)I。

4)用L:表示将状态映射到原子命题集合上的标记函数;给定一个命题集合和一个变迁α∈T,如果对于每一对s,s′∈S,都有s′=(α(s)),L(s)∩Ap′=L(s′)∩Ap′,则称变迁α∈T是不可见的。

当给定的刻画在Sstuttering下不变时,利用交换性和不可见性可以避免生成一些状态,基于这个原理可以得到任意状态的充足集Aample,偏序约简算法利用这些Aample集来构建约简的状态图,因此,对于每一条没有被偏序约简算法考虑的路径,在约简图内都有一条路径与之Sstuttering等价,这就确保了约简状态图和全状态图是Sstuttering等价的。 以下给出4个选择Aample集的限制条件。

条件C0Sample=Ø当且仅当Senabled=Ø。

条件C1在全状态图中,每一条从S出发的路径,都有下面的条件成立:一个变迁与Sample中的某个变迁具有依赖关系,那么这个变迁不能在Sample中的那个变迁之前执行。

条件C2如果s不是完全展开的,那么每一个α∈Sample都是不可见的。

条件C3如果一个回路包含一个状态,在这个状态上的某个变迁α 是激活的,但是在这个回路上的所有状态s都没有包含在Sample中,这个回路是不存在的。

2.2 电力大数据属性偏序约简的形式化描述

偏序约简算法的初衷是通过减少系统模型中的状态数目,以降低模型检测算法所搜索的状态空间规模[25]。其依据是系统中可并发执行的变迁关系具有交换性,即当这些变迁关系以不同的顺序执行时,都会到达一个相同的状态,对于这些不同组合顺序的变迁关系组只需选择其中之一即可。例如判断变压器故障的一种重要方法是通过分析油中溶解气体的组分、含量及产气速率,诸如甲烷(CH4)、乙烷(C2H6)、乙烯(C2H4)、乙炔(C2H2)、一氧化碳(CO)、二氧化碳(CO2)、氢气(H2)及一些其他气体等属性信息;智能变电站的网络运行状态可以通过对其可用性(Availability)、响应时间(Response Time)、 丢包率(Loss Tolerance)、 吞吐率(Throughput Rate)、准确度(Accuracy)、利用率(Utilization Ratio)、冲突率(Conflict Rate)、广播率(Broadcast Rate)、组播率(Multicast Rate)等指标属性进行判断来确定网络的运行状态属性。又由于电力大数据的“4V”特征,要从这些海量数据中获得有用的价值信息就需要对其进行并行化处理,而偏序约简算法具备并行化特征。故本文对电力大数据的属性进行了偏序约简方法研究,首先,将电力系统中的属性视作变迁关系,属性值作为在相应变迁关系作用下的转换状态;然后把针对在某一顺序变迁关系组的转换下到达相同终止状态的一些变迁序列去掉中间的冗余状态,仅保留关键路径;最后将关键路径上的变迁关系解码为相应的属性输出。以下给出电力大数据属性偏序约简方法的形式化描述。

定义1 设三元组S=(U,A,V)表示一个电力系统的运行状态,也可以叫做电力系统信息决策表。其中U作为论域,表示全体对象的有限非空集合;满足A=C∪{D},D∉C,C是条件属性构成的集合,D是决策属性;V是属性a的值域,即Va∈V。

定义2假设电力系统信息决策表中初始状态为O,(i∈[1,n],且i为正整数),是在条件属性即变迁关系ci作用下的中间转换状态,相应的为初始状态O经各变迁关系c1,c2,…,cn,D变换之后的终止状态,即。

定义3 假设在电力系统信息决策表中,存在多个对象使得它们从同一状态量经过若干个变迁关系ci+1,ci+2,…,ci+k变换之后得到的状态量相同(所谓的状态量相同,即是根据决策表中数据的实际情况,这些对象的状态值相同或其状态值都属于某一特定范围,决策属性所对应的状态除外),并且在转换过程的中间不存在相同的状态量,即存在多个ui∈U,使得满足上述条件,则可以去掉这些冗余状态。

定义4 假设在电力系统信息决策表中存在多个对象,在同一状态量经一个或多个相同变迁关系转换之后得到的状态量相同,即存在多个ui∈U使得或满足上述条件,则只保留其中一个对象,删去其他冗余对象。

定理1 把电力系统信息决策表S中的所有对象根据决策属性D的值划分成等价类{D1,D2,…,Di},Di={u1,u2,…,ut}(t∈Z),若存在多个数据分片(k=1,2,…,n)同属于一个等价类,则对于该等价类内属性集的约简结果为各数据分片内约简结果的并集,即(Ak为第k个数据分片内求得的约简属性集,Akj为由第k个数据分片求得的第j个属性,j=1,2,…,r)。

2.3 电力系统属性偏序约简的算法设计

根据定义1,把电力大数据集看作一个由三元组S=(U,A,V)表示的电力系统信息决策表,假设该决策表含有n个对象,每个对象又包括m个条件属性和一个决策属性D,如表1所示。

考虑到偏序约简方法在处理并发事件时相互独立的特征,结合MapReduce模型的并行化优势,这里把电力大数据集根据其决策属性D的不同取值划分等价类,然后再利用MapReduce的多个map函数对每个等价类内的多个对象同时使用偏序方法单独进行约简。若决策属性D有k种不同取值,则根据决策属性D的值划分等价类如下:

式中:表示第j个对象在第i个属性上的取值。

现将其中一个map函数对根据决策属性值划分的等价类内的电力数据集进行偏序约简的算法流程描述如下:

1)算法1(map函数)

步骤1:把数据集中的每条记录视作一个对象,各属性视为变迁关系,各属性值看作在相应变迁关系作用下转换的中间状态,按照定义2,将数据集内的一个对象从初始状态O在各变迁关系的作用下朝着决策状态进行变换,如式(3)所示。

式中:j∈[1,i],且j为正整数;Oj为第j个对象的初始状态且所有对象的初始状态量相同;Vcij为第j个对象在变迁关系ci的作用下转换到的相应中间状态。

步骤2:定义一个整型变量k,调用步骤1的状态转换程序,执行以下循环,即定义k(k为正整数)值从1到i有

步骤3:根据定义3,若步骤2中各个对象从初始状态在向决策状态转换的过程中存在类似以下情况。

其中j+l∈[1,i],l为大于等于0的整数,p,q∈[1,m],且p和q均为正整数,且则可化简成:

即各个对象由初始状态向决策状态转换的过程中,假如存在多个对象都经过若干个相同状态的转换,到达相同的决策状态,则只保留这些对象所历经的相同状态。

步骤4:对步骤3的处理结果,依据定义4,把从相同状态量经同样的变迁关系转换之后又得到相同状态量的所有对象只保留一个,即

步骤5:若步骤4的处理结果存在多个对象,则根据定理1,求这些对象所历经状态的并集,否则,处理结果为步骤4所求得的单个对象历经状态的集合(初始状态与决策状态除外),即

步骤6:对步骤5的处理结果进行统计,若不存在步骤3中所提及的情况,则约简结果为全部条件属性,否则遍历步骤5的约简结果,根据各个中间状态量的下标还原其所对应的变迁关系,也就是把中间状态量的集合解码为其所对应的属性集合,作为约简结果输出,即

2)算法2

步骤1:根据决策属性D的k种不同取值,将电力数据集划分为如式(1)所示的k个等价类。

步骤2:调用k台worker(集群中的计算机)同时运行算法1。

步骤3:调用另一台空闲的worker用来接收上述k台worker的处理结果,然后将k台worker的结果属性集按属性个数由多到少排序,目的是可以依据该顺序用相应集合中的特定属性集依次对电力数据集中的大量对象进行快速分类,以确定其对应的决策值,即

步骤4:在步骤3的基础上,根据定理1,对k个等价类的处理结果进行求并集操作,如式(11)所示。

步骤5:将步骤4求并之后的结果属性集和步骤3的排序结果作为最后的约简结果输出。

3)算法3

步骤1:根据决策属性D的k种不同取值,将电力数据集划分为如式(1)所示的k个等价类。

步骤2:将上述的k个不同等价类内的数据集分别再进行划分,为充分发挥计算机集群的优势,根据计算机集群的规模和以往经验确定每台worker所要处理的数据集规模,使得各节点之间通信、调度等开销达到最小值,又由于各等价类内数据集规模的不同,依次划分为n1,n2,…,nk个数据分片,如式(12)所示(j∈ [1,k],t<i,且j,t,i均为正整数)。

步骤3:调用(n1+n2+…+nk)台worker同时运行算法1。

步骤4:调用另一台空闲的worker用来接收上述(n1+n2+…+nk)台worker的处理结果,首先,分别将同一等价类内由不同worker处理的结果属性集,根据定理1,进行求并集操作,然后再将不同等价类内各自求得的属性集的并集,根据定理1,再次进行求并集操作,如式(13)所示(t=n1+n2+…+nk)。

步骤5:将步骤4求得的各等价类内结果属性集的并集,按属性个数由多到少排序,目的是可以依据该顺序用相应集合中的特定属性集依次对电力数据集中的大量对象进行快速分类,以确定其对应的决策值,如式(10)所示。

步骤6:将步骤4求并之后的结果属性集和步骤5的排序结果作为最后的约简结果输出。

这里根据电力数据集中决策属性不同取值个数多少的实际情况,有两种约简方案可供选择。方案1:如果决策属性的取值种类较多,则可以选择算法1和算法2。方案2:如果决策属性的取值种类较少,则可以选择算法1和算法3。但是,为了提高数据预处理的效率,在决策属性值种类较多的情况下,也可以选择算法1和算法3。附录A图A1是电力大数据属性偏序约简下map函数的算法流程图,附录A图A2是其整体算法流程图。

3 实验分析

3.1 实验环境

本文所研究的偏序约简算法将采用Java语言进行编码,在Hadoop平台中进行实验验证。Hadoop是一个分布式存储和分布式计算的开源实现,它采用Master/Slave架构,即包含一个Master节点,一个或多个Slaves节点,由Master对Slaves进行统一管理。由于条件有限,本文将采用15 台512 MB内存的计算机(workers)集群作为Slaves节点,所使用的Hadoop版本号为Hadoop2.2.0。

3.2 算法模拟

本文通过对某光伏发电系统(24h,30d)的光能辐照度数据进行约简,找出其数据特征,用于更好地利用太阳能资源,并以此来演示偏序约简算法的执行过程。附录A表A1 是经过简化处理后,由17个属性构成的光能辐照度表,其中date和P以及24个时间点为条件属性,F为决策属性。根据2.3节所描述的算法设计方案,按照决策属性的值将这些光能辐照度数据划分等价类,如下所示(属性值全部为0 的列可视为无关属性列,直接略去即可)。

等价类1:

等价类2:

为了证明偏序约简的有效性,应用偏序约简算法对上述两个等价类进行伪并行处理,处理过程见附录B。经过伪并行运算,求得偏序约简的结果为{7,8,9,10,11,12,13,14,15,16,17,18,P},即7到18之间的各个时间点,以及P所代表的时期。从而得知在07:00—18:00之间存在光能辐射,可用于转换为电能,并根据P的属性值可判断该月份是否属于空调期,以更好地利用太阳能,合理分配电能的使用。

3.3 算法测试

本文将采用两种实验数据对算法的性能进行测试,对其条件属性进行约简,以比较不同属性个数情况下,偏序算法的约简效率。然后针对加速比把该算法与当前主流的并行化启发式约简算法进行性能对比;并从空间复杂度、时间复杂度和算法正确性3个方面给出了本文算法与当前几种主流约简算法的性能对比结果,如表2 所示;又进一步从约简效率、加速比两方面给出了应用本文算法后与目前主流的几种约简算法的性能对比结果,如表3 所示。此两种实验数据即来自于某地区电力系统的变压器故障诊断数据和智能变电站通信系统实时性和可靠性预测数据。其中,变压器故障诊断数据包括8个条件属性和1个决策属性,智能变电站通信系统实时性和可靠性预测数据包括9个条件属性和1个决策属性;所采用的数据量大小均为20GB,并且都在3.1节所搭建的Hadoop平台进行实验验证。

在图1中,DATA1表示20GB的变压器故障诊断数据,DATA2表示20GB的智能变电站通信系统实时性和可靠性预测数据。从该图可看出数据DATA2的约简时间略高于数据DATA1,这是由于数据DATA2的属性个数略多于数据DATA1。

并行化程度越高,算法的约简效率也越高,为了体现出Hadoop平台的并行化优势,现将采用20GB的变压器故障诊断数据,利用上述Hadoop平台分别采用节点数为5,10,15进行等规模数据集的时效对比实验,如图2所示。图3是文献[21]中基于云计算技术的并行化启发式约简算法加速比测试结果。

由图2可看出,当数据规模不变时,随着节点数成倍地增加,偏序算法的约简效率有所提升,但并非呈线性,这是因为各节点之间的通信、调度等开销,使得偏序算法的约简效率达不到理想的线性提升。但显而易见的是当数据规模较大时,节点数越多,偏序算法的约简效率越高,越能体现出Hadoop平台的并行化优势。由图2和图3可以看出,偏序算法的加速比要略优于启发式并行化约简算法,而且偏序算法还解决了启发式约简算法所引起的决策表信息丢失问题。

4 结语

随着智能电网建设进程的快速发展,电力系统的数据采集量呈几何级增长,即步入电力大数据时代。传统的非并行化启发式属性约简算法,在处理电力大数据时遇到了挑战,虽然改进的并行化启发式属性约简算法克服了这一瓶颈,但由于启发式属性约简算法自身固有的特点,在进行约简的过程中会丢掉一些属性重要度比较低的属性,从而造成决策表部分信息丢失。本文所研究的偏序约简算法,不但解决了启发式属性约简算法所引起的决策表信息丢失问题,还略过了启发式属性约简算法的求核过程,利用偏序方法的并行化特征将其应用到MapReduce框架下,直接对电力数据集的相关属性进行约简。最后,通过在Hadoop平台上进行仿真,结果证明偏序方法可用于电力大数据的约简运算,算法的时间性能良好。

目前已有的电力数据集属性约简算法大多通过约简,在所有属性中选取比较有代表性的若干个属性,以减少数据分析过程中的属性个数。但是,经过约简后仍可能出现属性数量比较多的情况。因此,在今后的研究工作中,可以考虑通过采用分层、分级的方法改进本文的研究成果,对这些属性集按不同等价类进行分组融合,以进一步优化属性约简的效率。

偏序规划 篇6

当前矿泉水瓶随处出现在人们的日常生活中, 科学技术不断提高, 人们的生活水平和对美的欣赏水平也在不断提高, 因此, 对于矿泉水瓶的外观的关注度也越来越高。多属性决策方法是从20世纪70年代中期发展起来的一种决策分析方法。迄今为止, 多属性决策理论已在各个领域尝试应用并成为国内外专家新的研究热点。目前, 属性权重信息已知的模糊多属性决策问题已有较多成熟的研究工作, 但属性权重信息未知的多属性决策问题还存在一定的问题, 还需要研究者进行深入的探讨。

1 理论依据

(2) 模糊偏序[1]的概念:通过模糊偏序关系模型, 得到所有方案的偏序, 并集结, 形成全序关系, 得到所有方案的优劣排序, 可以对混合型多属性决策的不同类型属性值难以直接集结的问题进行有效的解决。对于U中任意的两个元素Ui和Uj, 定义“二元相对比较”级为正数:fj (Ui) 表示Ui相对而言uj所具有的优点, fi (uj) 表示uj相对而言ui所具有的优点,

规定:0≤fj (ui) ≤1, 0≤fi (uj) ≤1, fi (ui) =1。称:

为二元相对比较矩阵。构造模糊偏序矩阵, 若U上的模糊矩阵S= (sij) n×n满足下列条件:

1) S具有模糊自反性, 即sii=1;

2) S具有模糊完全反对称性, 即当i≠j时, sji至少有一个必为零;

则称S为U上的模糊偏序矩阵。

2 基于模糊偏序关系的排序方法

2.1 评估值模型的建立

2.2 属性值的量化及满意度的建立

由于各属性的属性值具有不同的量纲和类型, 故为对其进行数据操作, 需先进行量化处理, 因本文所研究内容为产品设计, 由于各属性的属性值具有不同的量纲和类型, 故为对其进行数据操作, 需先进行量化处理, 因本文所研究内容为产品设计, 故其属性值大多为成本型的。其量化方法如下:故其属性值大多为成本型的。先将其量化, 设属性值区间数如下

若属性值为模糊语言, 则可将其转化为区间值模糊集来处理。令{A, B, C, D, E}={[0.9, 1], [0.8, 0.9], [0.6, 0.8], [0.4, 0.6], [0.2, 0.4]}, 其中A为非常满意, B为较满意, C为满意, D为不满意, E为非常不满意。

2.3 评估属性的权值的主观给定

对于一项产品而言, 其各属性的权重未知, 故需要利用模糊偏序关系采用主观的方法来处理评价信息, 结合调查者的自身经验以及调查反馈的相关信息, 主观的给定各部分属性的权值, 并根据最后结果进行适当修正计算。

设W= (ω1, ω2, …, ωm) 为属性权重, 则有:

2.4 模糊偏序的集结

通过建立模糊偏序关系模型, 可得到所有产品设计方案的偏序, 将其进行集结, 形成全序关系, 可以采用文献[2]给出的集结模型即:

然后进行优劣排序得到最符合消费者满意程度的产品设计方案, 其方法流程如下:

3 矿泉水瓶的设计

根据本文所提方法, 并通过问卷调查现对矿泉水瓶的外观进行权重分配, 如下。

根据式 (3) 可将直径和容积两个属性的区间值, 将其他属性的模糊语言转化为区间值模糊集, 进而转化为模糊偏序关系, 其评估关系矩阵为:

采用式 (4) 将模糊关系集结, 可得到全序关系

于是得到排序:x2>x1>x3>x4。最后得出矿泉水瓶的设计方案为:浅绿色, 直径为2-3厘米, 材料为PE的瓶盖;透明, 容积为400-500毫升, 材料为PE的圆形瓶身;透明, 材料为PE的凹形瓶底。

4 结束语

针对权重已知且属性值为精确实数型、区间型和模糊型的混合型多属性决策问题, 在模糊偏序的基础上提出了混合型多属性决策方法。这种方法是将多属性问题通过混合型评估值模型描述出来;经过处理后的属性值预, 经过构建混合型模糊偏序关系模型, 这样决策法问题就转化为评估关系模型;然后集结所有偏序关系, 得到全序关系, 最后得到所有方案的优劣排序结果。本文的模糊偏序多属性决策模型仅适用于不同属性的取值类型不同单属性取值相同的问题, 而对单属性取值不同的问题无法进行求解, 有待进一步研究。

参考文献

[1]张卓.混合信息的多属性决策研究[J].计算机与数字工程, 2014 (12) .

[2]谭金锋, 颜锋.编序式问卷调查的模糊偏序排序法[J].数学的实践与认识, 2012 (04) .

[3]陈小卫, 王文双, 宋贵宝, 宋殿宇.基于模糊偏序关系的混合型多属性决策方法[J].统工程与电子技术, 2012 (03) .

[4]刘健, 刘思峰.属性值为区间数的多属性决策对象排序研究[J].中国管理科学, 2010 (03) .