一种面向最经济服务流的可视化动态贝叶斯网络模型_王洪泊

第6期2011年6月电 子 学 报ACTA ELECTRONICA SINICA Vol. 39 No. 6

J un. 2011

一种面向最经济服务流的可视化动态

贝叶斯网络模型

王洪泊, 涂序彦

(北京科技大学计算机与通信工程学院, 北京100083)

摘 要: 将面向最经济服务的流演算机制引入到动态贝叶斯网络结构的学习中, 提出一种面向最经济服务流的可视化动态贝叶斯网络分解协调模型(SFO -DBNs) 及具体实现算法; 该算法把Ford -Fulkerson 流分解算法推广到多源、多汇的情况下, 并加入了时间片t 因素对服务流稳定性约束, 可以把一个描述复杂大系统流演算的贝叶斯网络动态协调分解为几个子服务流分别建模, 便于简化动态贝叶斯网络的构造与其推理机制. 通过在数字气田采输管网调度中SFO -DBNs 仿真实例分析, 说明了该方法的有效性.

关键词: 动态贝叶斯网络; 数字气田; 服务流

中图分类号: TP391 文献标识码: A 文章编号: 0372-2112(2011) 06-1331-05

A Visual Dynamic Bayesian Network Model Orien ted

Most Econ omical Service -Flows

WANG Hong -bo, TU Xu -yan

(School o f Computer and Communication Enginee ring , Unive rsit y o f Science and Tec hnology , Bei jing 100083, China)

Abstract: Mo s t economical service -oriented flow s calculation mechanism is introduced during structure learning for dynamic

Bayesian networks and a coordination decomposing model for service flows oriented dynamic bayesian network (SFO -DBN s) is presented. In this model, a complex flow -calculation for large sys tem may be dynamically decompo s ed into several sub -service flow s that can be respectively modeling, which extends algorithm Ford -Fulker s on to mult-i sources and mult -i sinks and joins the time slice t factors on the service flow stability constraint. Simulating for digital gas fields pipe -net emergent scheduling plan and pick -convey balance analysis illustrate that the method of S FO -DBN s is effective and efficient.

Key words: dynamic Bayesian networks; digital gas field; ser vice -oriented flow

1 引言

为了能够处理动态的不确定性问题, 需要将贝叶斯网络扩展成带有时间参数的动态贝叶斯网络. 贝叶斯网络既可以从(在线和离线) 数据中学习得到, 也可以由(来至领域专家的) 知识来构造, 或者是二者的结合. 典型的研究工作有:D Koller 等将模块化和面向对象思想引入到贝叶斯网络中, 从面向对象角度提出多模块贝叶斯网络, 它是一个具有超级树形结构的贝叶斯网络, 其中每个超级结点都是一个贝叶斯子网; Sumit Sanghai, Pedro Domingos 和Daniel Weld 认为复杂系统随机过程中

[1]

伴随了许多对象和关系的创建, 提出一种关系动态贝叶斯网[2], 基于逻辑的方法对网络构造进行描述. Sui Ruan 等将动态贝叶斯网络应用于系统故障分析[3]. M ichailovic h O 等利用贝叶斯网络推理机制, 构建处理时间序列图像的学习模型, 用来消除噪声的影响; 文献[5]提出了一种贝叶斯网络增量学习方法, 将EM 算法和遗传算法引入到了贝叶斯网络的增量学习过程中. 文献[6]提出了一种基于混合方式的贝叶斯网弧定向算法. 值得注意的是, 上述这些方法在应用于复杂大系统时, 构造网络模型是极其费时的, 并且各个子系统间的交互和协调也会变得异常困难.

[4]

收稿日期:2010-07-14; 修回日期:2010-08-16

基金项目:国家自然科学基金(No. 60375038, No. 60503024) ; 国家/十五0重点科技攻关项目(No. 2004BA616A11) ; 中国科学院自动化研究所复杂系统与智能科学重点实验室开放课题(No.20060105) ; (国家高技术研究发展计划863项目(No.2009AA01Z119) )

1332 电 子 学 报2011年

气田管网生产调度问题的研究最初是集中在运筹学方法(动态规划) 上, Roger Z. 等提出了一种针对气田管网环结构、基于网络的启发式天然气输送有效操作的方法; B V Ba bu 等人提出基于微分进化的思想解决气田采输管网优化设计[8]. 由于气田勘探、开发、生产是随时间滚动进行的, 经常有新的气井或井站需并入气田管网中供气, 同样也有新的用户加入进来用气. 上述方法虽然计算结果精确, 但是难以解决复杂的气田管网生产实际调度问题[9], 十分需要引入新的理论模型和方法[10].

[7]

flow) , v 称为该路流的流量, 记作x t P ath(i 0, j 0) (v). 当v =0时, 称该路流为零路服务流, 否则称为非零路服务流. 定义3 环服务流. 如SF O -DBNs 中存在一个有向环Cycle (不含源或汇点) , 使得:0[v =x t i j [u i j , P (i , j ) I Cycle(i 1, i i ) t , i 1I Tr ; x t i j =0, P (i , j ) I A \Cycle(i 1, i i ) t , i 1I Tr. 则称x t 为环服务流(cycle service flow) , v 称为该环气流的流量, 记作x t C ycle(i 1, i i ) (v). v =0时, 称该环流为零环服务流, 否则称为非零环服务流.

最经济服务是指在给定的生产技术约束条件下, 使正常生产的经济目标函数最优化, 以实现生产系统的经济化. 式(3) 是SFO -DBNs 经济性能的目标函数.

G e =

其中:

S |p i 为第

S |=S |g

i=1

m

2 模型构建

面向最经济服务流的动态贝叶斯网络(Service Flo ws Oriented Dynamic Bayesian Network, 简称SFO -DBNs) 的核心思想就是将面向最经济服务的流演算机制引入到动态贝叶斯网络结构的学习中.

|p i i S E A |j g E B j S

n

y min (3)

j =1

i 个子服务流运行、维护等所需的经济代

211 SFO -DBNs 的相关概念

定义1 SFO -DBNs, 可用一个五元组表示:SFO -DB -Ns =(V, A , L, U, D , T ). 其中:V 为节点集; A 为弧集; L, U:A y R 分别为弧上的(容量下界、上界) 权函数; D:V y R 为顶点上的权函数(供需量) , T 是时间片向量.

t

SFO -DBNs 上t 时刻的一个服务流(service flo w) x 是指从弧集A 到R 的一个函数, 即每条弧(i , j ) I A 赋于一

t

个实数x ij (弧(i , j ) 的流量) , 如果流x t 满足流量守恒和容量约束条件, 分别如下式(1) 、(2) 所示:

j:(i, j) I A

j

价(成本) , A |g 为第j 个子子服i 是其对应的权重因子; S

务流所带来的经济收益, B j 是其对应的权重因子.

根据式(3), 分别给出路服务流、环服务流、源点、汇点的经济代价权重因子.

定义4 路服务流经济代价权重因子, 如式(4) 所示, 其中Sp 为源点集, 为汇点集Si.

Path(i 0, j 0) A =i

t

S p Pat h(i 0, j 0) (x t Pat h(i , j ) (v)) |

t

S |p i (x t (v) )

, i 0I Sp , j 0I Si

(4)

E

x t i j -l i j [

x t i j

j :(j, i) I A

E

t

x ji =d t i , P i I V

(1) (2)

[u ij , P (i , j ) I A

则称x t 为可行服务流. 至少存在一个可行服务流

的SFO -DBNs 称为可行服务流网络. 可见:¹当d t i >0时, 表示在t 时刻有d t i 个单位的流量从网络外部流入该结点, 因此在t 时刻顶点i 称为供应点或源点, 由许多源点构成的集合记为:S p ={i |

d t i

>0}; º当

d t i

时, 表示在t 时刻有d t i 个单位的流量从该结点流出到网络外部(或被网络吸收) , 因此在t 时刻顶点i 称为需求点或汇点, 由许多汇节点构成的集合记为:S i ={i |d t i

d t i

=0}.此

定义5 环服务流经济代价权重因子, 如式(5) 所

示, 其中Tr 为汇点集.

Cycle(i 1, i 1) A =j

S |p (x t C ycle(i 1, i 1) (v) ) |p (x t C ycle (v) ) S

, i 1I Tr

(5)

定义6 源点经济性能的目标函数, 如式(6) 所示.

S |p (G i e =

i 0=i

t

E x Path(i , j ) (v) )

|g (x t (v) ) S S |p (

, i 0, i I Sp , j 0I Si

(6)

定义7 汇点经济性能的目标函数, 如式(7) 所示. G j e =

j 0=j

E x t P ath(i , j ) (v) )

|g (x t (v )) S

, i 0I Sp , j 0, j I Si (7)

E d t i =

i I V

0, 即所有节点上

供需量之和为0.

定义2 路服务流. 可行服务流网中的流x t :A y R, 其中, 如果N 中存在一条从源i 0到汇j 0节点的有向路径Path(i 0, j 0) t , 使得:0[v =x t i j [u i j , P (i, j ) I Path (i 0, j 0) , i 0I Sp , j 0I Si ;

t

t x ij =

212 SFO -DBNs 协调分解引理及算法描述21211 引理

在SFO -DBNs 中, 任何一个可行服务流一定可以表示为若干个(经济性能稳定) 路服务流和若干个环服务流之和, 即:

x t (v) =

i 0I Sp j 0I S i

0, P (i, j ) I A \Path(i 0,

E x t Pat h(i , j ) (v) +E x t C ycle(i , i ) (v)

i 1I Tr

1i

(8)

j 0) t 0Sp j 0则称t (path

第 6 期王洪泊:一种面向最经济服务流的可视化动态贝叶斯网络模型

表1 Algorithm for SFO -DBNs

1 InitSe t(Gas -Station, Sp ) ;

2 InitSe t(Tran -node , Tr ) ;

3 4 5 6 7 8

InitSe t(Gas -U ser , Si) ;

Init Net flux(X , vedge [i][j ]); InitPathSet() ; InitCyc leSe t() ;

While (Get Node(Sp , &i0) X

1333

个) 源点指向一个(或多个) 汇点; 至多有m +n 个路服务流和环服务流为非零流, 且其中至多有m 个环服务流为非零流, 其中m 是N 中的结点数目, n 为边的数目.

证明 记可行流为x t , 设i 0是SFO -DBNs 中的一个源点, 则存在弧(i 0, i 1) I A 使得x i 0, i 1>0. 如果i 1是网络中的一汇点, 则找到了一条从一个源点指向一个汇点的有向路径. 否则, 从i 1出发, 重复上述过程, 直到找到一汇点或再次遇到已经经过的某顶点时为止, 即下列两种分类之一出现为止:

分类1:找到一条从一个源点i 0指向一个汇点i k

的有向路径Path. 此时, 定义:

v t (Path) =min {d i 0, -d i k , min {x t i, j (i , j) I Path}}.如果5

i t

G e (x Pat h(i 0, i k ) (

9 k =1;

10 Get No de (Si G Tr , &ik ) ; 11

While (x i

0, i k

X 0) do {

12 If (i k |Path) then Push (Path , i k )

Else { Cycle z Path ;

v (Cycle ) =min {x ij

13 If ((v (Cyc le ) =0) +(

t

P (i, j ) I Cycle}; 1

, i ) (v ) ) 1

5G i e (x t Cycle (i

:0) )

v) )

U 0, 则得到一个流值为v (Path ) 的

t

then exi t;

14 While (i , j I Cyc le) do x ij =x ij -v t (Cycle ) ; 15 16 17 18

Print(Cycle ) ;

Pat hSe t =PathSet G Cycle ; Cycle =

x ij =x ij -v t (Cycle) ; }

非零(经济评价稳定) 路服务流. 此时, 在SFO -DBNs 中

t t

重新定义:d i 0=d i 0-v (path) ; d i k =d i k +v (path) ; x i j =x i j -v t (path) , P (i , j ) I Path. 否则:从源点i 0重新开始.

分类2:找到一个有向环Cycle . 此时,

定义 v t (Cycle) =min {x i j P (i , j ) I Cycle}.5G i e (x t Cycl e(i 1, i 1) (v) ) 如果U 0, 则得到一个流值为

v t (Cycle) 的非零(经济评价稳定) 环服务流. 此时, 在SFO -DBNs 中重新定义:

x i j =x i j -v (Cycle) , P (i , j) I Cycle

否则:从源点i 0重新开始.

对重新定义的SFO -DBNs , 重复上述过程, 直到所有顶点变成转运点(平衡点). 然后, 对重新定义的SFO -DBNs , 找到一个至少有一条出弧上的流量为正的顶点, 继续重复上述过程, 这时只有分类2会出现, 即获得一个非零(稳定) 环服务流. 重复上述过程, 直到定义的流x 成为零流为止. 最后, 按照汇点(或源点) 对路服务流进行合并.

显然, 当SFO -DBNs 中的所有结点均为自耗节点时, 才会出现至多有m 个环流服务元组为非零流的情形; 同理SFO -DBNs 中的所有结点均为自耗节点, 且均是源和汇节点时, 才会出现m +n 个路流服务元组和环流服务元组为非零流的情形. 其中m 是SF O -DBNs 中的结点数目, n 为SFO -DBNs 中边的数目.

上引理将Ford -Fulkerson 流分解算法[11]

(证毕)

推广到多

t

19 If i k I S i then {20 Print(Path ) ; 21

v t (Path ) =min {d i , -d i , min {x i, j (i, j ) I Path }};

k

22 if (v t (Path) =0) +

then exi t ; 23 24

d i =d i -v t (Path) ;

0k

0k

5G i e (x t Path(i , i ) (v ) )

:0)

d i =d i +v t (Path ) ;

(9)

25 While (i, j I Path) do x ij =x ij -v t (Path ) ; 26 PathSet =PathSet G Path ; 27 Path =

k =k +1;

Ge tNe xt Node(Si G Tr , &ik ) ; }}

i I T r G Si k

32 If (v i 0I Sp &&

E

x i

, i 0k

=0)

then De lete -No de (Sp , i 0) ; 33 If (v j 0I Si &&

i I Tr G Sp

k

E

x i

, j =k 0

0)

34 then De lete -No de (Si, j 0) ; 35 If (v t r 0I Tr &&

i I Tr G Sp

k

E

x i

k

, tr

=0&&

i I Tr G Si k

E

x tr

, i =0k

0) then Delete -Node (Tr, tr 0) ;

}

}

SFO -DBNs 协调分解算法在实际操作中, 须遵循/大者优先0原则, 具体解释为:¹先高压管线气井组后低压管线气井组; º产气量大的气井所在进气点优先, 按产气量对进气点建立一个源点集合InitSet (Gas -Station, Sp ) ; »输气量大的管线所在管道优先, 按输气量对管

源、多汇的情况下, 并加入时间片t 因素对服务流稳定性约束, 得到一种SFO -DBNs 结构协调分解算法, 如表1所示.

1334 电 子 学 报2011年

线建立一个管线容量约束造成矩阵Init N etFlux (vedge [i ][j ]) ; ¼用气量大的用户所在输配站点优先, 按用气量对用户(或输配站) 建立汇点集合InitSet (Gas -User, Si ) , 输配站集合InitSet (Tran -node, Tr).

整体可靠性的影响大小, 随时监控整个管网系统的运行状况, 当每日采气量与输气量出现较大差异时, 及时

判断是哪一条管线或与哪一个用户之间出现了采输差, 进而为寻找影响输差的潜在因素, 以及输差控制提供决策依据.

3 算例实验分析

311 问题背景

图1是某气田气井(站) 集输局部子网络物理模型示意图, 考虑几个典型的井站(Sp 1在t 时刻以20万方气/小时产气, Sp 2在t 时刻以8万方气/小时产气, Sp 3在t 时刻以6万方气/小时产气) ; 两个用户(Si 1在t 时刻以17万方气/小时用气, Si 2在t 时刻以14万方气/小时用气) ; 6个集输站点或称阀室(Tr 1, , , Tr 6) ; 相关的管线分布如图1所示

.

312 算法运行结果

如图2所示, 为SFO -DBNs 协调分解算法的调度结果, 气田管网气流协调分解为两个路气服务流(Sp 1---#Si 1和Sp 2, Sp 3---#Si 2) 以及一个环气服务流(Tr 1

---#Tr 1) , (注:Si 3为一虚拟汇点, 表示网中自消耗流量). 根据式(4) ~(7) 可计算出各路气服务流、环气服务流和节点的经济性能的目标函数及评价因子. 其中:输配站节点间管线气流量的方向在算法中进行标注的. 对非零路服务流来说:气井或井站(网中的源点) 是服务提供方, 而天然气用户(网中汇点) 是服务申请方, 集输站场或管线等是服务的约束条件或中介; 而非零环服务流是一种特殊的自产自销式服务

.

314 效果比较分析

某日Sp 2停气检修, 管网总进气量减少, 根据天然气调度应急工作流程, 分案例匹配CBR 、专家推理ES 、SFO -DBNs 三种方法进行调度, 比较结果分析, 如图4所示.

从图4看出, 运用SFO -DBNs 方法进行数字气田采输管网应急调度, 对用户供气量气影响是三种方法中最小的, 不但能计算出气田采输管网经济性能的可靠性指标, 而且能给出每个井站、阀室或管线的承输因子, 为调度专家科学决策提供可视化依据; 由于算法本身就是从最经济服务流角度出发的, 所以也便于气井生产指令的快速下达.

313 采输经济性能分析

图2中一段时间内两个路气服务流的采输经济性

34 结语

第 6 期王洪泊:一种面向最经济服务流的可视化动态贝叶斯网络模型1335

个颇具挑战性的研究课题, 而数字气田管网的调度[12]为我们提供了一个很好的应用研究背景, 如何将服务流的进化、优化及服务质量评价体系融入到动态贝叶斯网络模型构造与推理机制中, 形成一个动态进化服务流网是本项研究的下一步工作.

致谢 向对本文的工作给予支持和建议的国家/十五0科技攻关项目(数字气田关键技术研究及示范应用) 的系统研究与开发课题组的全体同仁, 以及中石化西南分公司采输处的有关专家们表示衷心感谢. 特别对北京科技大学计算机与系统科学研究所王宗杰高工、张业贵、韩辛亮工程师, 和中石化西南公司采输处张仕强、王雨生、杨锦林高工等表示感谢.

参考文献

[1]Nir Friendman, D aphne Koller. Being bayesian about network

structure:A bayesian approach to structure discovery in

bayesian networks[J]. Machine Learni ng, 2003, 50(1-2) :95-125.

[2]Sumit Sanghai, Pedro D omingo s, Daniel Weld. Relational dy -namic bayesian networks [J].Jo u rnal of Artificial Intelligence

Res earch, 2005, (24) :759-797.

[3]Sui Ruan, et al. Dynamic mul tiple -fault diagnosis with imperfect

tes ts[J].IEEE Trans on Systems, M an and Cybernetics, Part A :Systems and Humans, 2009, 39(6) :1224-1236.

[4]M ichailovich O, T annenbaum A. Dynamic denoising of tracking

sequences[J]. IEEE Trans on Image Processing, 2008, 17(6) :847-856.

[5]田凤占, 黄丽, 等. 包含隐变量的贝叶斯网络增量学习方

法[J]. 电子学报, 2005, 33(11) :1925-1928.

TIAN F Z , HUANG L, et al. An incremental approach to learn -ing bayesian networks containi ng hidden variables [J ].Acta Electronica Si nica, 2005, 33(11) :1925-1928. (in Chinese) [6]贾海洋, 陈娟, 等. 基于混合方式的贝叶斯网弧定向算法

[J]. 电子学报, 2009, 37(8) :1842-1847.

JIA H Y, CHEN J, et al. A hybrid method for orienting edges of bayesian network[J].Acta Electronica Sinica, 2009, 37(8) :1842-1847. (in Chinese)

[7]Roger Z , R os -M ercado , et al. Efficient operation of natural gas

transmission systems:A network -bas ed heu ris tic for cyclic structures [J]. Computers and Operations Research, 2006, 33

(8) :2323-2351.

[8]B V Babu. Process Plant Simulation [M ]. New D elhi, India:

Oxford Univer si ty Press, 2004. [9]朱勇, 罗敏, 刘巍. D SS 技术在天然气应急调度管理中的

应用[J].天然气工业, 2004, 24(11) :131-136.

ZHU Y , LUO M, LIU W. D SS application i n urgent gas dis -patching [J]. Natural Gas Industry, 2004, 24(11) :131-136. (in Chinese)

[10]涂序彦, 王枞, 郭燕慧. 大系统控制论[M ].北京:北京邮

电大学出版社, 2005.

TU X Y , WANG C, GUO Y H. Large Systems Cybernetics [M]. Beijing:BUPT Publish Hous e, 2005. (in Chinese)

[11]L R Ford, D R Fulker s on. Flows in Networks[M ].NJ, U SA:Pri nceton Univer sity Press, 1962.

[12]WANG H B, ZENG G P, et al. Digital gas fields produce real

time scheduling based on intelligent autonomous decentralized sy s tem [A ].IEEE International Symposium on A u tonomo us Decentralized Systems[C].Chengdu, China:IEEE Computer Society, 2005. 630-635. 作者简介

王洪泊 男, 1972年生于山西浑源. 北京科技大学计算机与通信工程学院计算机系讲师、博士. 研究方向为协调智能调度、机器学习、人工生命.

E -mail:foreverwhb@126. com

涂序彦 男, 1935年生于江西南昌. 北京科技大学计算机与通信工程学院教授、博士生导师. 研究方向为人工智能, 智能控制、智能管理, 大系统控制论, 生物控制论, 人工生命.