动态贝叶斯博弈（共5篇）
动态贝叶斯博弈 篇1
当前, 工程建设的规模日益扩大, 加上工程具有技术复杂性、风险高、差异性大、综合性强等特点, 合同双方未履行合同的情况屡见不鲜, 因此索赔的发生也是经常的。随着工程建设市场竞争的日益激烈, 低价中标, 通过索赔规避风险、赢得利润, 已成为许多承包商的重要手段。
建设双方对工程索赔缺少全面清楚的认识, 承包商在工程索赔过程中经常因为索赔不及时、索赔证据收集不全面、索赔数额计算不规范等原因不能获得合理的索赔, 而业主在与承包商谈判的过程中也会因为运用谈判技巧、索赔策略等使承包商不能得到应得的索赔。有的承包商不敢向业主提出索赔, 因而索赔能否成功, 对于承包商来说至关重要。
通过分析大量的国内外资料可知, 已经有大量的学者通过博弈模型来分析索赔问题。但是大多数学者还是倾向于建立完全信息下的动态博弈模型, 而对不对称下的讨价还价博弈模型缺乏相应的研究。有的学者虽然建立了不完全信息博弈模型, 但只对博弈过程进行了简单的分析, 缺乏更深入的研究。
一、工程索赔博弈模型的建立
从博弈的角度分析, 工程索赔问题属于一个信息不完整的、非合作的、动态的、序贯的博弈问题, 站在理性的角度上, 强调承包商的最优决策。工程项目施工的招投标中“中标靠报价, 赢利靠索赔”就突出了索赔的非合作博弈特征。
索赔的多轮谈判满足讨价还价问题的条件, 本文以此为基础建立讨价还价博弈模型, 如图1所示。
在一般的二人有限零和博弈中, 两个局中人的得失之和为零, 而在工程索赔中, 由于工程项目的特殊性, 二者的得失不是完全对立的, 不能用一般的线性规划来求解, 因此需要用Bayes方法来修正。
假设局中人Ⅰ—承包商、Ⅱ—业主
博弈顺序:
(1) 局中人Ⅰ第一轮报价为S1, 局中人Ⅱ决定接受还是拒绝。
(2) 局中人Ⅰ第二轮报价为S2, 局中人Ⅱ决定接受还是拒绝。
……
(n) 局中人Ⅰ第n轮报价为Sn, 局中人Ⅱ决定接受还是拒绝。
二、贝叶斯理论下的工程索赔博弈模型分析
运用Bayes定理进行决策是将定性分析与定量分析相结合。
(1) 根据Bayes公式计算概率。
(2) 承包商估计业主的保留值:
承包商对业主的保留值进行修正:
(3) 求解承包商的效应函数。
现假设效应函数是线性的 (uo=kx+b) , 保留值ec的效应为ūc, 则承包商的效应函数为:
(4) 承包商估计业主的效应函数。
设业主的效应函数为uc=kx+b, 保留值eo的效应为ūo, 则承包商估计业主的效应函数为:
(5) 求解联合效应函数。
综合承包商与业主之间的效应关系, 换算得到二者的效应函数之间的联系为:
(6) 估计风险。
其中:Pomax—业主承受风险的最大能力;
Pcmax—承包商承受风险的最大能力;
utcc—给定承包商在第t轮谈判中的报价, 承包商的效用;
utoo—给定业主在第t轮谈判中的报价, 雇主的效用;
utco—给定雇主在第t轮谈判中的报价, 承包商的效用;
utoc—给定承包商在第t轮谈判中的报价, 雇主的效用;
uc (c) —争论中承包商的效用, 博弈中假设是零;
uo (c) —争论中业主的效用, 博弈中假设是零。
(7) 计算让步率。
(8) m轮讨价还价。
经过多轮讨价还价, 一方的报价被另一方所接受, 报价结束。
三、算例
现有某工程, 计划开工时间为3月份, 完工时间为10月份。在施工期间由于对地质状况了解不深入导致在挖基坑期间出现了大量的流沙, 并伴有管涌现象的出现, 而此时又恰逢雨季, 给施工造成了严重的困扰。
第一步, 承包商分析了造成成本增加的因素。
自然因素:业主未能将准确的工程地质条件提供给承包商, 导致基坑开挖的成本增加。
环境因素:雨季施工, 再加上大量的流沙出现, 给施工造成巨大困难, 这是一个有经验的承包商所不能预测到的。
第二步, 索赔意向。
业主考虑到不按期交工所造成的损失远远大于索赔的金额, 因此, 愿意支付一定额度的赔偿金以保证工期的按时完成;承包商也愿意通过索赔的金额按时完成施工任务, 赢得业主的信赖, 为下一次的合作打好基础。承包商综合考虑, 决定索要600万元的索赔额, 保留值为400万元。
第三步, 承包商经过判断, 给出业主可以接受报价的先验概率分布及业主最终可能接受报价的概率, 如表1、表2所示。
注:1) 表中数据可根据工程的实际情况加以调整 (单位:万元) ;2) P (R) 是估计的先验概率, ∑P (R) =1。
第四步, 谈判过程。
承包商报价600万元, 业主还价400万元。
(1) 承包商综合分析业主承受索赔的能力和以往的经验, 修正概率分布, 计算后得出后验分布概率。根据贝叶斯公式计算得出当e=400时的概率值, 见表3。
(2) 承包商估计业主的保留值ec=∑RiP (Ri) =400×0.4+450×0.3+500×0.15+550×0.1+600×0.05=455万元。
承包商根据谈判结果, 得出修正保留值eo=∑RiP (Ri/e) =400×0.573+450×0.258+500×0.086+550×0.057+600×0.025=434.65万元。
(3) 求解承包商的效应函数。
假设保留值ec的效应为ūc (0<ūc<1) , ūc=0.2, 承包商效用函数的两个关键点:最大值 (600, 1) , 保留值 (400, 0.2) , 承包商的效应函数为:
(4) 承包商估计业主的效用函数。
假设保留值eo的效应为ūo (0<ūo<1) , ūc=0.2, 承包商效用函数的两个关键点:最小值 (400, 1) , 保留值 (434.65, 0.8) , 承包商的效应函数为:
(5) 联合效用函数。
(6) 估计风险。
由于业主的风险相对小, 因此业主在此次报价中损失会比较大, 因而会做出让步, 承包商依然会坚持原来的报价。
(7) 让步率。
最后, 经过三轮的谈判, 业主出价550万元, 经过承包商修正后的业主保留值为563.4万元, 业主出价与此接近, 谈判结束。
四、结论与展望
本文主要提出了用贝叶斯理论和博弈模型解决承包商和业主的索赔问题, 不仅可以增加承包商索赔成功的概率, 也可以减少工程施工中的风险, 使索赔更加科学合理, 对于规范工程索赔市场具有重要的意义。但是本文没有考虑到补充信息的可靠性和工程师在索赔谈判中的作用, 因此还需后续研究。
动态贝叶斯博弈 篇2
关键词：贝叶斯博弈,混合策略,Web应用安全,Stackelberg均衡
0 引言
近年来,许多研究都集中于博弈论在资源分配和调度方面的问题[1],但博弈论不仅适合应用在这些问题上,也可以应用在Web安全攻防问题上。 Stackelberg博弈应用在Web安全问题中时, 领导者是信息安全人员, 而追随者是黑客。 随着安全技术的提升,有多种先进的策略和技术可以提供给攻击者和防御者。 本文中要解决问题是寻找稳定的Stackelberg博弈用于Web应用安全中领导者的最优策略。 本文提供了Stackelberg安全博弈和贝叶斯Stackelberg安全博弈的详细描述,对其在Web安全领域的适用性进行了讨论,并给出了实验的结果。
不同的研究者探索用博弈论的方法来建立安全问题的适用性[1], 在过去的几年有了显著的结果和实际运用。 在文献[2]中,提出了ARMOR框架,能够有效地在洛杉矶国际机场内设置检查点和警犬巡逻维护安全。 在文献[3-4] 中, 博弈论被用于联邦空警在商业航班中的安全护航,以及在纽约地铁中的逃票检查。 博弈论也已经被用在建立信息安全领域的模型中, 文献[5] 用完全信息的静态博弈来建立信息安全的攻防模型。 在文献[6]中,利用零和随机博弈对攻击者和系统管理员的行为进行建模,其中网络被表示为一组独立的节点来对应安全资产和漏洞。 在文献[7-8]中,描述了在信息安全问题中运用博弈论的方法找到最佳的策略,提出了相关决策的惩罚参数。 在文献[9]中,提出了基于马尔科夫决策过程的博弈模型对漏洞威胁进行风险评估。
本文将会探讨在Stackelberg博弈中防守者和攻击者形成最优稳定局面可能性以及在Web安全领域的应用。 本文的目标是找到在Web安全问题中面对攻击时最有效的防守策略。
1 Stackelberg博弈
Stackelberg博弈是非合作、 有先后次序的决策博弈。是由两个局中人领导者和追随者参与的一种博弈论类型。 被称为领导者(leader)的参与者首先发布一个混合策略,另一个被称为追随者(follow) 的参与者在领导者的策略下优化自己的性能或收益,回应一个纯策略。 两个参与者都想其收益最大化。 每个参与者有一个可能的行动集合, 每个参与者可以从集合中选择形成策略, 这个策略是参与者可能采取行动的概率分布,可以表示参与者选择这个行动的可能性。 参与者只能选择一个行动的策略就叫做 “纯策略”。 而在混合策略中每个行动可以被选择的概率是0≤p<1。 由于本文侧重于Stackelberg博弈在安全领域中的应用, 相关术语 “ 领导者” 对应的 “ 防守者”及 “追随者”对应的 “攻击者”会被交替使用。
在Stackelberg博弈中, 我们定义x表示领导者的混合策略, 追随者则从纯策略集合J中选择一个纯策略,回应领导者的策略并最大化其预期收益。 对于追随者执行的每个纯策略j, 领导者的预期收益为ujTx + uj ， 0追随者的预期收益为vjTx + vj ， 0, 其中uj和vj是RN中的实向量,uj ， 0, vj ， 0∈R。 定义U和V分别表示领导者和追随者的收益矩阵:
1 . 1 贝叶斯Stackelberg博弈
贝叶斯Stackelberg博弈将Stackelberg博弈扩展成允许有多个类型的追随者,每种类型都有其自己的收益矩阵, 方便建立有多个类型攻击者的模型。 在贝叶斯Stackelberg博弈中, 追随者的类型集合表示为{ 1 , 2 , … ,I } , 其中每种类型1 ≤ λ ≤ I都有一个先验概率Pλ来表示其出现的可能性。 领导者在知道每种类型追随者先验概率分布的情况下承诺一个混合策略,但是领导者不知道面对的追着者的具体类型。 而追随者会根据领导者的策略回应一个最佳的策略。 对于每个追随者类型,领导者和追随者对应的收益矩阵分别为Uλ和Vλ。
在本文中定义j =(j1,j2, … ,jI) 来表示追随者回应的纯策略,其中jλ是追随者类型 λ 的纯策略,对于类型为 λ的追随者,其预期收益为vλ(x,jλ)=(vjλTλ)x + vjλ， 0, 领导者总收益,其中对应每种i类型的追随者时,领导者的相应策略对应收益为uλ(x,jλ)=(ujλTλ)x + ujλ， 0。
1 . 2 稳定Stackelberg均衡条件
为了计算领导者的最优策略, 则需要先定义稳定Stackelberg均衡[10]。 首先需要定义一组向量函数g =( g1, g2, … , gI) , 其中每个gλ表示领导者的混合策略到 λ类型追随者的纯策略的映射关系, 那么g (x) 就是追随者回应x策略的一组向量, 可以表示为g(x)=(g1(x), … ,gI( x ) ) 。
定义1: 对于给定一个收益矩阵为(U1,V1), … , (UI,VI) 类型的概率分布为p的贝叶斯Stackelberg博弈, 一组策略集(x,g) 当且仅当满以下条件时能构成一个稳定Stackelberg均衡。
( 1 ) 领导者执行最优反应策略
( 2 ) 所有类型的追随者执行最优反应策略
( 3 ) 在每个类型追随者在最优反应的前提下, 使领导者收益最优
其中的所有j都是(2)中追随者的最优反应策略.
2 DOBSS算法
在以前的研究中, 有很多方法可以用来解决Stackelberg安全博弈问题[11],DOBSS算法是其中一个能够有效计算出在贝叶斯Stackelberg博弈中领导者的最优混合策略。 采用这个方法有3 个优势,首先这个方法不需要通过海萨尼转换转化为正则形式的博弈来表示贝叶斯博弈;第二,该方法仅需计算一个混合整数线性规划问题,而不是计算一组线性规划问题的集合;第三,它直接搜索了领导者的最优策略,而不是Nash均衡,从而使其能够找到高回报的Stackelberg均衡策略(利用了领导者的优势)。
首先需要定义一个基本形式来解决贝叶斯Stackelberg博弈问题, 这是一个混合整数二次规划问题( MIQP ) , 其次会将其转化为一个混合整数线性规划的问题(MILP)。 我们用x表示领导者的策略, 其由一组领导者的纯策略向量组成。 xi的值表示纯策略i在混合策略中的比例。 同样,用q表示追随者策略的向量。 我们用X和Q表示领导者和追随者各自纯策略的集合。 M则是表示一个无穷大的正数。 收益矩阵R和C的定义是:当领导者选择纯策略i, 追随者选纯策略j,Rij是领导者的收益,Cij是追随者的收益。
领导者的MIQP问题定义为:
为了扩展这个Stackelberg模型来处理多个追随者类型,我们遵循贝叶斯方法先假设存在一个先验概率pl来表示追随者类型l出现概率, 用L表示追随者类型的集合。 在这个例子中,ql表示追随者类型l ∈L的策略向量。 同样的, 领导者和追随者类型为l的收益矩阵用矩阵Rl和Cl表示。 那么领导者需要解决问题变为:
现在面临的最终步骤是消除MIQP中目标函数的非线性, 使之变为一个MILP, 我们可以通过交换变量zilj=xiqjl, 得到式( 6 ) :
这是我们可以在IBM的cplex框架下实施的最终形式,将会在第4 章讨论。
3 Stackelberg博弈在Web安全上的应用
3 . 1 Stackelberg博弈在Web安全上的适用性探讨
Stackelberg博弈在Web安全应用问题中非常有用。在这种情况下, 领导者可以是信息安全人员或者组织,追随者可以是黑客或者有组织的犯罪集团。 领导者首先通过部署不同的信息安全策略来保护其资源,然后追随者可以通过探测网络确定其状态,用纯策略回应领导者的策略。 不同类型的追随者可以被解释为不同类型的攻击, 根据以前的研究和统计[12], 安全部门可以构建攻击技术分布比例, 而攻击者可以扫描网络的当前状态,查找漏洞,实施最佳策略。
安全部门可以被当做一个领导者,原因如下:
( 1 ) 在大多数情况下, Web应用的安全策略是对外公开的。
( 2 ) Web应用的安全手段和措施都是标准的和众所周知的。 黑客可以通过探测网络来推断安全部署。 而且这种信息经常也可以从安全供应商得到。
( 3 ) 每个安全措施都有自己的弱点和不足, 这给了攻击者有机会选择最好的方式来攻击。
这些情况都可以说明Stackelberg策略可用在Web安全领域。
3 . 2 Web应用中的攻击策略和修补策略
为了具体说明将Stackelberg博弈策略运用在Web安全应用中, 本文建立了在Web安全应用中的攻防模型。 在Web应用安全问题中,攻击者(跟随者)试图利用一些漏洞来执行未经授权的操作,而安全人员(领导者)试图解决这些错误。 根据研究[13],Web应用中最广泛的追随者的攻击策略和领导者的修补策略见表1, 这些攻击手段和防御手段分别对应了追随者的行动集合和领导者的行动集合。
3 . 3 Web安全中领导者和追随者的收益计算
将Stackelberg博弈应用于Web应用的安全问题上,其核心问题是需要以一种有意义的方式填充领导者和追随者的收益矩阵。 在研究[13]中,OWASP团队的文档数据由7 家专业的应用安全公司提供。 数据涵盖了来自上百家组织上千个应用,超过500 000 个漏洞。 根据这些数据, 同时考虑攻击向量的可利用性、 安全漏洞的普遍性和可检测性以及技术影响的严重性程度等多方面因素, 给出了Web漏洞每个风险因素的风险值。 在研究[ 13 ] 的基础上, 本文给出了Web安全应用中领导者修补策略的收益(表2)和追随者攻击策略的收益(表3)。
根据收益表格,当追随者发起攻击时给出定义:
( 1 ) 如果修补手段对攻击手段是有效的, 那么领导者的收益为领导者行动的影响减去领导者修补手段的成本,追随者的收益是其攻击手段的成本。
( 2 ) 如果修补手段对攻击手段是无效的, 那么领导者的收益是负的,其值为领导者修补手段的成本减去追随者攻击手段的影响,追随者的收益为追随者行动的影响减去追随者攻击手段的成本。
( 3 ) 追随者同样可以选择不进行攻击, 那么领导者的收益为其修补手段的成本, 追随者的收益为0, 由此可以得到收益表格来定义收益矩阵(表4)。
4 实验结果
在本文实验中使用了IBM ILOG CPLEX软件来处理寻找Stackelberg博弈领导者的最优策略时面临的线性规划问题,IBM ILOG CPLEX是一种非常强大的线性规划处理工具,支持各种编程语言,在这个例子中,我们使用JAVA语言编程实现。
在这个例子中, 定义了两种类型的追随者, 它们的攻击手段相同时具有相同的收益值,但是有不同的行动集合。其中A类型的追随者可以用第3 章表1 里攻击策略集合中的任何纯策略,但是不可以不进攻(选择NA策略)。 而B类型的追随者不可以使用SQLi和ITIP策略。 A类型的追随者先验概率为0.7,B类型的追随者先验概率为0.3.
得到程序的结果如下:
优化状态:Optimal
领导者最大预期效用:-0.702 052 238 805 969 8
A类型追随者最大预期效益:1.357 142 857 142 857 2
B类型追随者最大预期效益:1.283 582 089 552 239
追随者的追策略:
A的纯策略:SQLi
B的纯策略:XSS
领导者的混合策略:
采取转义程序行动的概率:0.390 485 074 626 865 66
采取会话安全的概率:0.221 641 791 044 776 13
采取访问控制行动的概率: 0.0
采取跨站点请求伪造防卫行动的概率:0 . 166 231 343 283 582 05
采取环境安全行动的概率: 0.221 641 791 044 776 05
采取安全算法行动的概率:0.0
上述结果与研究[13] 中的Web应用安全的研究情况相符,SQLi和XSS是威胁性最大的攻击手段, 因此基于所得到的结果,领导者可以使用如上的混合策略达到最优防守状态。
5 结论
博弈论在安全领域有着越来越重要的作用, 近年来理论研究和生产实践使安全博弈分析有了长足的发展[14]。本文综述了贝叶斯Stackelberg博弈, 在此基础上提出了一种贝叶斯Stackelberg博弈策略在Web安全中的应用的模型,综合考虑领导者和追随者的成本参数和收益参数,构建了更加全面的局中人收益函数。 并利用文献[10] 提出的DOBSS算法, 计算贝叶斯Stackelberg博弈均衡的混合整数二次规划问题转化为混合整数线性规划问题,并且借助了高性能的线性规划问题处理工具CPLEX,给出实例计算了Web应用安全中防守者的最优混合策略。
动态贝叶斯博弈 篇3
随着高通量数据的产生和计算机技术的发展,对这些大数据的处理和挖掘已经成为研究的热点。一个网络可以抽象为由结点和边组成的一个图,结点表示现实网络中的一些研究对象,边可以理解为结点之间潜在的相互作用关系。如在疾病基因网络中,一些疾病基因可以看成网络中的结点,基因之间的相互作用关系可以理解为网络中的边,那么就可以通过网络的手段知道哪些基因作用关系密切,可能会成为致病因素,这就对药物设计和疾病治疗起到一定的理论意义。因此构建的网络可以系统地研究网络中结点之间的调配关系,为深入挖掘结点之间的复杂关系及作用机制提供理论模型。
现今已经诞生了很多数学模型和计算机方法来推断网络构建,这些模型方法主要包括布尔网络模型(Boolean networks)[1],常微分方程模型[2],信息论模型[3,4],线性规划[5]模型和贝叶斯网络模型[6,7]。这些方法能够对网络系统动态行为提供更深层次的理解,但是构建方法的精度对模型中参数的依赖性非常大,且算法的时间复杂度非常大,这就使得构建大规模网络变得异常困难[8]。由于基因调控过程的复杂性、调控的方向性、网络的规模性以及基因表达数据的噪声等因素的影响,这些都会影响基因调控网络构建性能。如基于互信息的方法不能检测网络的方向,不能区分直接和间接调控;基于优化模型的方法很难解决高维低样本数据;基于贝叶斯网络的方法具有较高的计算复杂度,且很难处理大规模网络等。如何克服这些模型和方法中的缺点,是基因调控网络构建方法提高其性能的关键所在。
贝叶斯网络模型是一种图形概率模型,利用贝叶斯规则建立结点间的联合概率分布来构造调控网络的。贝叶斯网络模型是基于统计理论的,并且能够应用到各种类型的生物数据中,因此能够捕捉到表达数据中固有的噪声,而且准许在决定结点间相互作用关系的过程中可以利用贝叶斯规则来结合一些先验生物学知识。动态贝叶斯网络(DBN)是贝叶斯网络的扩展版,既可以使用稳态数据,也可以应用到基因表达时间序列数据中。当构建的调控网络包含大量的基因结点时,DBN需要花费大量时间来学习条件依赖关系。为此我们提出了一种数据相对变化率的策略来预处理随机结点数据,以此来识别出网络中一些关键的结点,在这个基础之上我们再采用时延的动态贝叶斯方法和一些先验知识来构建网络,所构建网络的优劣用性能指标AUPR和AU-ROC值来评估。试验结果验证我们的方法取得了良好的网络构建性能,在网络的构建准确率和精度方面都取得了较好的结果。
1 理论方法
1.1 相对变化率
网络中的边表示结点之间潜在的相互作用关系,在给定的网络中,一个结点的表达水平值发生变化会影响那些和它有相互作用关系的结点的表达值。如果结点在整个网络中扮演了一个非常重要的角色,那么它的变化会引起其周围近邻结点的变化,我们也称这些点为中心结点或者关键结点(Hub Node)。因此一些结点值的表达类型不同(如原态数据,表达缺失数据,表达值减小数据和带有噪声的数据等)就会影响网络构建的精度。这里我们引入相对变化率的数据预处理策略来识别出一些中心结点,为进一步网络构建减小时间复杂度。
对于给定实验数据集中的每一个结点数据,我们以它的原态表达数据作为参照点,然后计算每个数据结点的相对变化率,数据的相对变化率公式定义如下:
其中Ri,j表示结点j在结点i表达值敲除情况下的相对变化率,Gi,j表示结点j在结点i表达值敲除情况下的表达值,Wj表示结点j原态表达值,Max(G:,j)-Min(G:,j)表示结点j对所有结点表达值变化范围,如果i=j,则相对变化率Ri,j为零。
如果结点的变化率大于给定的一个阈值,我们就认为这个结点是关键结点,在整个网络中扮演非常重要的角色。当结点的表达值相对于参照结点的变化小于给定的一个阈值时,我们认为它是噪声,把它从潜在的调控结点表单中剔除。如图1所示,计算结点1到10对于结点1的相对变化率,其中结点2,4,5,7,8明显高出阈值,那么我们就认为这些节点潜在的被结点1调控,结点1在整个网络中是一个关键结点。
1.2 动态贝叶斯网络
动态贝叶斯网络是贝叶斯网络在时序上的扩展,它是代表复杂时序数据随机过程的通用模型。典型的动态贝叶斯模型可以用图2来表示。二元组(B0,B1)表示时序变量结点X={X1,X2,…,Xn}的联合概率分布,其中Xi(1≤i≤n)表示网络中的二值结点,小写xi(1≤i≤n)表示变量结点Xi的样本值。动态贝叶斯网络由初始态的贝叶斯网络B0=(G0,θ0)和过渡态的贝叶斯网络B1=(G1,θ1)组成,其中B0表示变量结点X(0)的联合概率分布,B1表示对于所有的时间t转移概率。那么Xi(0)的双亲结点假设就在网络B0中,即的双亲结点其中1≤i≤n,t0。随机结点变量X(0)∪X(1)∪…∪X(T)可以被表示成如下的一个联合概率[9,10]:
1.3 时延动态贝叶斯网络
K Murphy[11,12]提出了动态贝叶斯的表示方法,网络推断及结构学习,但是这个模型有两个主要的缺陷。第一,这个算法的时间复杂度非常大,对于网络中某结点,其父节点可能是剩余结点的一个或者多个,其算法的时间复杂度会随着网络规模成指数级增长。由于计算的时间太长一般认为一个结点的父节点数量限制在30个以内。第二,这个算法没有考虑相关性的延时问题,这会降低网络构建的精度。
为了克服这个缺陷,Conzen[7]74提出了基于时序数据的带有时延的动态贝叶斯网络构建算法,这种方法能够有效地降低算法的时间复杂度和提高算法的准确性。在网络中相互作用的两个结点,它们的时序表达值都有一个相应的延时趋势或者同时发生变化,那么用这种方法就可以限制一个结点的父节点的数量,以此来降低算法的时间复杂度。还发现在生物分子网络中,调控结点和被调控结点之间都会存在一个转录时延周期,那么结点表达值的延迟就代表了生物相对延时周期。这种方法考虑了结点变量间的相对关系,借助表达值的变化来估计调控结点和被调控结点之间的关系。那么用这种带有延迟的动态贝叶斯方法就可以直接从时序的基因表达数量识别出其对应的网络。
在我们的方法中,首先用相对变化率从时序数据中找出那些关键的网络结点,这些结点比其它结点更可能成为其它节点的父节点,在生成的网络中这些结点会扮演非常重要的角色,用相关性给这些关键结点先构建出一个调控网络。其次用时延的动态贝叶斯网络方法再从这些时序数据中构建另一个调控网络,把两个网络中都存在的那些边保留成为我们构建的最终网络,用DREAM[13]人工合成数据和真实网络数据来对我们的算法进行检测,证明我们方法的有效性和准确性。
2 结果分析讨论
2.1 构建的网络和标准网络比对结果
网络预测的性能可以用如下参数来评估,用真阳性(true positive,TP),假阳性(false positiv,FP),真阴性(true negative,TN),假阴性(flase negative,FN),召回率(Recall)也叫真阳性率(true positive rate,TPR),假阳性率(flase positive rate,FPR),精确度(Precision)也叫查准率(Positive Predictive Value,PPV)和准确率(accuracy,ACC)来对构建的网络进行检测,它们的公式定义如下:TPR=TP/(TP+FN),FPR=FP/(FP+TN),PPV=TP/(TP+FP),ACC=(TP+TN)/(TP+FP+TN+FN)。除了上述指标外还有受试者工作特性曲线(Receiver Operation Characteristic Curve,ROC曲线)和其曲线下的面积(Area under ROC,AUROC),精度召回率曲线(Precision and Recall Curve,PR曲线)和其曲线下的面积(Area under PR,AUPR)来衡量构建算法的优劣性。
我们的方法成功地应用到了人工合成数据集上[14,15],在E.coli数据集上,真实网络有10个结点,10条边。我们预测出来的网络共有11条边,其中7条正确,精度达到70%。在另外一个酵母(yeast)数据中,有50个结点,77条边,我们的方法预测的带有方向的网络如图3所示,其中预测正确的边有52条,准确率达到了68%。实验验证了我们的方法取得了较好的性能。
2.2 相对变化率在网络构建中的作用
在三个不同的实验数据集上用我们的方法来构建网络,在10个结点的实验数据集上,只用相对变化率的方法来构建网络;在50个结点的实验数据集上,用相对变化率结合时延动态贝叶斯的方法来构建网络;在100个结点的实验数据集上,只用动态贝叶斯网络的方法来构建网络,以此来测试这三种网络构建方法的性能。
结果显示在10个结点和50个结点的网络构建中效果明显好于100个节点的网络构建,在E.coli数据集上构建网络的效果明显好于在yeast数据集上,具体参数如表1所示。结果显示采用了相对变化率策略可以比单独使用延迟动态贝叶斯方法取得更高的网络构建性能,这就可以解释为什么在100个结点的网络构建中,AUPR和AUROC值都相对偏低,在10个结点和50个结点的网络构建中,AUPR和AUROC值都相对偏高。这是因为在100个结点的网络构建中只采用了延迟的动态贝叶斯方法,在10个和50个结点的网络构建中都有相对变率策略的干预,由此可见,相对变化率的策略能提高网络构建的精度。
为了进一步说明相对变化率策略在网络构建中所起的作用,在10个结点的数据集上分别采用延迟动态贝叶斯方法,相对变化率策略方法和它们二者结合的方法来构建网络,这三种网络构建方法所获得的AUPR值如图4所示。实验结果说明采用相对变化率策略的方法和它们二者相结合的方法性能都优于单独使用时延动态贝叶斯方法,这充分说明相对变化率策略在网络构建中起着比较重要的作用。动态时延贝叶斯网络构建方法在计算结点潜在调控的父节点时,选取范围偏大导致网络中有较高的假阳性边,以致降低了网络构建的精度,如何把相对变化率策略和时延动态贝叶斯网络更好的结合,以提高网络构建的精度将是我们将来继续研究的问题。
3 结束语
文中提出了一种数据相对变化率的策略来预处理随机结点数据,以此来识别出网络中一些关键的结点,为后续的网络构建提供帮助,这些关键结点在生成的网络中会扮演一个非常重要的角色,它们会潜在地调控网络中的其它结点。在这个基础之上我们再采用时延的动态贝叶斯方法和一些先验知识来构建网络,所构建网络的优劣用性能指标AUPR和AUROC值来评估。试验结果验证我们的方法取得了良好的网络构建性能,在网络的构建准确率和精度都取得了较好的结果。如何把相对变化率策略和时延动态贝叶斯网络更好地结合,以提高网络构建的精度将是我们将来继续研究的问题。
摘要：从大规模实验数据中构建的网络可以反向发掘网络结点之间潜在的相互作用关系,可以更深层次解释网络结点间复杂的作用机理,因此产生了很多网络构建的理论建模方法。在一些实验数据中某个时间点的样本值表达减少或者被敲除,这会影响网络构建的精度。为了克服这个问题提出了相对变化率的策略来识别结点间潜在的作用关系。在时序实验数据中,用策略融合时延动态贝叶斯方法来进行网络构建。可以缩减贝叶斯的搜索空间,以此来获得较高的网络构建性能和精度。DREAM(Dialogue for Reverse Engineering Assessments and Methods)竞赛项目最早被提出用来严格检测结点间网络构建模型方法的性能和优劣。在这个数据集上推测出来的网络在AUROC(area under the ROC curve)和AUPR(area under the precision recall curve)指标上和其它方法进行了比较,实验结果验证算法在网络构建过程中总体性能略胜一筹。
动态贝叶斯博弈 篇4
炼化过程在大量的稳定工作状态中有不可避免的状态之间的转换过程,称之为过渡过程,启动和关闭过程是过渡过程的常见形式。当化工装置经历过渡过程,参数变量的从一个稳定状态值过渡到另一个稳定状态值。在此过程中,传统的报警系统无法判断过渡过程并为其预先设定告警管理方法。因此,在过渡过程期间,可能出现潮水般的误报警,即使转换到新的稳态过程后,报警洪水依然存在。当过渡过程已经结束,一个新的稳定状态开始,也可能因为阈值设置不当而导致报警错误。我国较早开展的告警管理方法的研究是在1982年应用于电力系统的云南电网计算机监控系统[1]和郑州供电网的计算机调度监控系统[2],利用DJS-131单机系统实现了功率信号的自动采集、叠加计算和告警功能。在工业过程领域内的告警管理主要包括以下几种方法:
1)基于典型案例的告警管理方法
基于对告警案例的分析总结经验提出这种方法,在处理一个告警信息后,将其作为典型告警案例记录下来,为后续的相似问题的解决提供学习经验。文献[3]研究多层次范例推理方法,提出了时序预测中的CBR循环模型,应用于时序数列的告警中。文献[4]提出了基于范例推理的工程监测位置和时序曲线矩阵的探索方法,建立支持向量机先验知识的告警管理模型。基于典型案例的分析方法直接引用以往的经验,但典型案例的数量的不断增多将造成查找的不便,此方法需要增加告警知识库或经验库来对典型案例进行分类和储存。
2)基于规则判断的告警管理方法
此方法引入了对告警信息的判断规则,一般在告警系统中添加一个告警策略监控机制,该机制决定了判断规则的使用逻辑顺序和推导条件。文献[5]提出一种基于频繁加权模式树的关联规则告警挖掘算法,该方法提高了数据挖掘的速度,提高告警管理的效率。文献[6]采用数据挖掘和大数据存储技术,实现故障特征与关联设备信息的提取及时发布告警信息协助运行人员分析和处理事故。文献[7]利用动态时间窗生成技术,通过判断规则对动态过程的故障征兆和发展信息进行监控,连续动态地进行告警管理。基于规则判断的告警信息分析方法的判断规则由专家或用户基于自主经验自定义,判断结果受到主观性影响较大。
3)基于神经网络的告警管理方法
在告警信息处理中引入人工神经网络方法,作为一种系统故障定位的途径。文献[10]通过高斯核函数的变换将离散的采集数据转化为伪连续的时间函数,减少间断点带来的误告警,但是提高了在线告警处理的难度,对实际应用中的实时函数值判断尚需进一步的研究。文献[11]研究在过程工业中由于告警算法的设计不当或缺乏适当的调试导致频繁告警(alarm chatter)的现象,通过分析历史告警数据得到频繁告警评判指数,用于甄别分类。文献[12]提出一种新的告警信息显示方法来解决告警洪水问题,改善了传统告警信息显示的列表模式。文献[13]提出一种基于有向网络目标检测方法(NIDS)的告警管理系统,该系统对每个告警信号赋予有向标识和分类处理,将误告警最小化。文献[14]提出一种支持决策告警管理方案,在实际告警发生前预测告警的发生情况和时间点,该方法有助于更快地完成诊断和告警,但是没有从根源上提高告警信息判断的准确性。文献[15]提出一种基于有向图的概率分析告警信号选择方法,使告警管理系统更加合理,该方法降低了误告警的概率。
结合国内外研究现状,针对动态关联炼化系统的告警管理方法存在以下两点技术难点:(1)现有的告警管理方法无法准确判断炼化装置运行中的过渡过程。(2)在过渡过程的正常运行中工艺参数随着工艺调节而动态变化,而现有的告警线设置无法自行动态调试。
因此,本文提出了基于贝叶斯估计的动态告警线计算方法,通过训练历史过渡过程数据得到先验概率,自适应判断过渡过程和估计动态告警线,解决了传统告警线的斜率不能赋值且只能依靠人为调节的问题,并可通过判断系统状态调节告警管理方式。
1 贝叶斯估计方法基本理论
与常用估计方法极大似然估计法相比,贝叶斯估计方法考虑先验知识的影响,更适用于历史数据的训练,估计结果更加准确。该方法不仅提高了预测的准确性和适应性,还大大地提高了系统的灵活性。贝叶斯估计方法是通过给定的样本数据D来确定在假设空间H中的D的最佳假设。最佳假设的定义是在给定样本数据D以及空间H时,D的同假设的先验概率在有关知识下的最可能假设。
一个线段变量是n对有序点的集合(ti,yi)(i=1,…,n),其中yi是时间ti的观测值,在点(ti,yi)中包括错误信息和噪声信息。为了建立[ti,tn]的回归模型,需要得到观测值与时间值之间的线性关系。一般地,线性方程的关系由两个因素决定:斜率β和y轴的截距α0,方程表示如式(1):
无论方程以何种形式表示,斜率β和y轴的截距α0必须已知。传统的方程参量估计方法经常使用最小二乘法,但是在没有数据概率模型的情况下无法得知斜率β和y轴的截距这两个必要条件。因此,引入贝叶斯估计的方法来进行方程的参量估计。
在应用贝叶斯估计方法前,作出以下假设:
1)方程假设
其中,是直线t=珋t的y轴截距。假设和β的最小平方估计值是相互独立的,这使得计算的复杂性大大降低。
2)误差假设
每个变量的误差服从0到方差的正态分布,假设所有观测值yi的误差相对独立并恒等分布:
其中,是y的平均值,β是斜率,每一个误差ei服从0到方差的正态分布。
假设变量数据[tanchor,tn],需要应用贝叶斯估计方法做出拟合线段。根据上述假设,拟合线段由两个因素决定,斜率β和y轴的截距α0。斜率β的联合分布和由贝叶斯估计算出的y轴截距α0与先验概率和节点概率的乘积成正比。
其中,是联合概率密度,是节点概率。
由式(3)得知,yi|ti服从正态分布对于观测点
由于假设观测数据都是相互独立的,联合概率密度又可以表示为:
斜率β和y轴截距α0的节点概率有如下关系:
且斜率α0和y轴的截距α0服从正态分布:
计算β和α0的联合后验分布,由式(7)推出:
其中,
由此,可将变量数据[tanchor,tn]的下一时刻误差算出:
计算下一时刻的节点状态:
其中,
一旦预测分布算出,预测数据的置信区间可以得出,由置信区间计算动态告警线。估计方差用于获得未知离散噪音
2 基于贝叶斯估计的炼化装置动态告警策略
本节采用贝叶斯估计法通过训练历史数据得到的动态告警线的先验概率,自适应判断过渡过程和估计动态告警线,具体实施步骤如下:
步骤一:训练历史数据
收集目标样本过渡过程的历史数据,将50次过渡过程的参数值时间序列作为贝叶斯估计的训练对象,以期实现过渡过程的准确识别和告警线的动态估计。
步骤二:贝叶斯估计动态告警线
对于一个典型的过程参数变量,预测值置信区间在95%的界限内是合理的[22],因此将高告警线和低告警线之间的间隔按照95%的置信区间设置,动态告警线的设置结果为(my-T0.025×s'y,my+T0.025×s'y)。
在历史数据的训练基础上,利用贝叶斯估计对动态告警线进行自适应估计,得到动态告警线的状态方程中各未知参数的估计值,估计过程见图1。
步骤三:动态告警管理
告警管理过程通过判断运行状态是否属于过渡状态,参数值是否触发动态告警线,对系统进行告警管理。管理过程见图2。
步骤四:动态告警结果检验
统计动态告警过程中告警数量,判断告警洪水是否发生。
历史数据的处理与训练在离线阶段完成,离线阶段的任务需在对过渡过程进行动态告警之前完成,并在不断的数据采集和告警过程中收集有效数据,及时更新贝叶斯估计的训练数据定时训练,以保障贝叶斯估计的有效性。
在线阶段的实时数据具有恒定的采样频率,根据贝叶斯估计方法,动态告警线不断的拟合确定,对不同阶段的过渡过程自适应地调整动态告警线。
3 案例分析
常压蒸馏是在接近大气压力条件下完成原油的分馏,从而将原油生产为石脑油、煤油、溶剂油、柴油及变压器油料等不同产品。原油通过加热炉被加热到360~370℃,进入到常压蒸馏塔,塔顶操作压力约为0.05MPa,塔顶蒸馏得到石脑油馏分,可与初馏塔顶的轻汽油一起作为催化重整的工业原料。由于常压蒸馏工艺在原油蒸馏流程中有“承上启下”的作用,因而要操作好常压蒸馏流程使其稳定运行。某炼化厂常减压塔的原油进料流量随着生产过程进行调节,流量调节过程属于过渡状态。
步骤一:训练历史数据
将50次124 min的过渡状态原油进料流量的历史数据作为训练对象,根据图1对样本进行动态告警线的训练,并用贝叶斯估计方法估计动态告警线。
步骤二:贝叶斯估计动态告警线
在历史数据训练的基础上,分别以两次原油进料流量的过渡过程作为目标样本,以5%浮动区间作为告警阈值区间,进行动态告警线的贝叶斯估计。
步骤三:动态告警管理
图3和图4为分别对两次原油进料流量的过渡状态数据进行动态告警的结果。
在图3中可看出通过贝叶斯估计训练成功在42、44、71和74 min识别出过渡状态并及时调整上下告警线,对过渡状态进行监控。
在图4中可看出通过贝叶斯估计训练成功在35、42、65和73 min识别出过渡状态并及时调整上下告警线,对过渡状态进行监控。
步骤四:动态告警结果检验
以传统告警方式为对照组,对比两种告警管理方法的误告警数量。在44和74 min时(示例1)及42和73min时(示例2),传统告警方式通过人为调节,更改告警上下线,告警线始终为与x轴平行的直线。两种告警方法的误告警数量对比分别见表1及表2。
通过两组对比数据得出,在过渡状态中传统告警管理方法难以实时调整告警线,产生大量误告警,造成告警洪水。动态告警管理方法适应性较强,能够完成过渡过程的监控与管理。
4 结论
1)研究了动态告警管理策略,以离线阶段的历史数据处理与训练为基础,在线实时的判断系统运行状态,采用不同的告警管理方式。动态告警管理方法解决了现有告警管理方法无法准确判断过渡过程并无法及时调整告警线的问题,系统性地判断动态过程并实时监控。
动态贝叶斯博弈 篇5
配电系统在电力系统中处于末端,直接与用户联系,主要包含配电站、馈电线路、断路器、隔离开关等设备,因此配电系统可靠性评估不仅关系到配网规划的优劣,而且关系到电力系统供电能力和电能质量。
针对多状态元件组成的配电系统可靠性定量分析的难点及传统故障树在配电系统可靠性评估中的局限性,提出基于贝叶斯网络和随机集理论的复杂配电系统可靠性建模与评估的新方法。应用贝叶斯网络在建立由不确定因素组成的结构层次清晰的配电系统模型和图形化直观表达的优势,计算配电系统可靠性指标,从而对配电系统进行整体评价;结合包含DemP-ster组合规则在内的多种经典组合规则的随机集统一表示模型对任何一个或多个要素影响配电系统可靠性的概率进行计算,从而有效识别目前配电系统薄弱环节,为配电系统的改造提供坚实基础,为台州配电系统建模分析提供新思路。
1 配电系统可靠性指标
1.1 系统平均停电频率指标
每个由系统供电的用户在单位时间内的平均停电次数,以用户停电次数与系统供电的总用户数之比来表示,即:
式中,λi为负荷点的故障率;Ni为负荷点的用户。
1.2 系统平均供电可用率指标
1年内用户不停电的时间总数与用户要求供电的时间总数之比,即:
式中,μi为负荷点年平均停电时间。
1.3 系统平均停电持续时间指标
每个由系统供电的用户在1年内的平均停电持续时间为:
1.4 用户平均停电持续时间指标
1年内被停电用户的平均停电持续时间为:
1.5 总电量不足
系统在1年中因停电而造成的用户总电量损失为:
式中,Li为连接在每个负荷点上的平均负荷;Fi为负荷系数。
2 配电系统评估建模步骤
本文应用动态故障树和贝叶斯网络混合法建模的步骤如图1所示。
2.1 静态子树的分析计算
由于静态子树只包含用电负荷对配电系统可靠性的影响,因此对于只由用电负荷节点构成的静态子树,可采用二元决策图(BDD)直观算出系统故障概率。
在BDD中,配电系统正常时表示为0,故障时表示为1,因此有:
2.2 动态子树的分析计算
由于传统动态子树的求解采用马尔可夫链有组合爆炸的危险,因此利用贝叶斯网络的图表直观和双向推理更适合大型复杂配电网系统。本文将动态子树转换为贝叶斯网络分析求解。
2.2.1 贝叶斯网的定义
贝叶斯网络是一个有向无环图(Directed Acyclic Graph,DAG),它由代表变量的节点及连接这些节点的有向边构成。设“系统故障”为事件DSF,事件DSF为样本空间Ω,B1,B2,…,Bn为Ω的子集,且,并假定P(Bi)>0,则由贝叶斯公式可知某节点故障概率的计算公式为:
因此,系统整体故障概率为:
由式(1)推出动态贝叶斯网络的求解法,即由动态模块求出系统在任何时刻的故障概率为:
根据贝叶斯网络的反推,得出最可能引发系统故障的薄弱点为:
I(t)=P(DS=1|Si=1)—P(DS=1|Si=0)
2.2.2 逻辑门转化为动态贝叶斯网络
贝叶斯网络逻辑门的转换:故障树的先验概率表现为父节点的先验概率,转换形式如图2所示。
3 配电系统可靠性算例分析
下面以台州某10kV配电系统为实际算例,检验算法的有效性。台州某10kV配电系统如图3所示,主线路有工业负荷4个、商业负荷2个、居民负荷12个;支路1有工业负荷3个、商业负荷1个、居民负荷6个;支路2有工业负荷5个、商业负荷1个。
以主馈线为例建立的贝叶斯网络如图4所示,部分节点实际可靠性指标见表1。
各层次计算式如下:
式中,Li为线路长度;λi为线路故障率;ri为线路因故障停运时间;λPi为变压器故障率;rPi为变压器因故障停运时间。
负荷点概率式如下:
P(LP1=1)=1—P(L1=0)P(L2T1=0)
P(LP2=1)=1—P(L1D1L3D2=0)P(L9T2=0)
结合节点的实际可靠性指标,部分节点可靠性指标及配电系统可靠性指标见表2、表3。
由表2、表3可知,采用本算法计算出的数值与实际指标相差不大,且耗时短。
本文取P(DSF=1|C=1)求元件处在故障状态时系统故障概率,取P(C=1|LP2=1)求系统处于故障状态时各元件故障概率,这样不仅可求出各元件故障概率,而且通过计算运行状态下节点故障概率最高值可找出系统薄弱环节。
该算法可找出由隔离开关、断路器拒动造成的系统故障次数与总的系统概率百分比。如图5所示,线路L1、线路L3故障概率最高,其次为线路L4、线路L5、线路L6,提高这些元件的可靠性或缩短检修时间可适当提高系统可靠性。
如图6所示,当负荷点LP3故障时,线路L5、线路L10、变压器T3为故障概率较大的3个元件,概率值分别为0.423 7、0.238 8、0.217 2,其次为L1、L3、L4,提高这些元件的可靠性,可以增强负荷点LP3的可靠性。
4 结束语
本文结合动态故障树与贝叶斯网络,提出了完整的配电系统可靠性算法,并通过建立数学模型对配电系统进行评估。该模型解决了传统故障树无法反映配电系统动态特性的问题,真实反映了配电系统的实际情况,并可利用贝叶斯网络的双向性,找出配电系统中的薄弱点,以便加强监测及检修,确保配电系统的可靠性,适用于大规模复杂配电系统。通过对台州某配电系统可靠性的评估,证明了该模型的有效性。
参考文献
[1]陈文高,配电系统可靠性实用基础[M].北京:中国电力出版社,1998
[2]万国成,任震,吴日异,等.混合法在复杂配电网可靠性评估中的应用[J].中国电机工程学报,2004,24(9):92-98
[3]李志民,李卫星,刘迎春.复杂辐射状配电系统的可靠性评估[J].中国电机工程学报,2003,23(3):69-73