首页> 中国专利> 一种基于动态规划的语义服务组合方法

一种基于动态规划的语义服务组合方法

摘要

本发明提出一种基于动态规划的语义服务组合方法,首先通过工作流引擎将制造业务流程模型进行分解,提取每一个活动节点的需求,然后过服务发现匹配过程获取满足该活动的所有服务,最后根据一定策略从每个挑选合适的候选服务生成服务组合方案,实现将具体的语义服务映射到任务上。结合网络化制造模式特点,采用工作流模型描述的制造业务过程,将语义服务组合方案的生成过程转化为一个动态演化、多阶段决策过程,以服务间数据语义关系为约束,以组合方案综合质量为优化目标,利用动态规划方法生成全局最优的组合方案。该方法易于确定全局最优解,节省了计算量,有助于为用户提供丰富的组合方案结果,提高组合方案的可执行性和组合过程的自动化程度。

著录项

  • 公开/公告号CN103149840A

    专利类型发明专利

  • 公开/公告日2013-06-12

    原文格式PDF

  • 申请/专利权人 西北工业大学;

    申请/专利号CN201310041818.3

  • 发明设计人 王明微;周竞涛;

    申请日2013-02-01

  • 分类号G05B13/04(20060101);

  • 代理机构61204 西北工业大学专利中心;

  • 代理人陈星

  • 地址 710072 陕西省西安市友谊西路127号

  • 入库时间 2024-02-19 19:11:24

法律信息

  • 法律状态公告日

    法律状态信息

    法律状态

  • 2020-01-17

    未缴年费专利权终止 IPC(主分类):G05B13/04 授权公告日:20150304 终止日期:20190201 申请日:20130201

    专利权的终止

  • 2015-03-04

    授权

    授权

  • 2013-07-17

    实质审查的生效 IPC(主分类):G05B13/04 申请日:20130201

    实质审查的生效

  • 2013-06-12

    公开

    公开

说明书

技术领域

本发明涉及网络化制造服务的组合技术领域,具体为一种基于动态规划的语义服务组合方法。

背景技术

服务组合是构建网络化制造环境中的业务流程,实现制造资源按需分配的有效途径。现有服务组合技术可归纳为两大类。一种是基于工作流的方法,使用与经典工作流建模方法相类似的模型来描述组合服务,实现简单,但是要求事先知道流程的具体结构以及流程中每个活动要求实现的功能与目的,从工作流业务模型到服务环境的映射只能进行静态的转换,流程运行的自动化和动态调整程度不高。另一类是基于人工智能方法,利用本体对Web服务的输入输出参数、前提和结果等进行语义标注及业务过程建模,通过形式化的推理来得实现Web服务的自动匹配,得到服务的组合序列,但是该方法的复杂度较高,纯粹依赖计算机自动进行Web服务的组合在目前还尚未成熟。

发明内容

要解决的技术问题

为了克服上述各种方法的缺点,提高网络化制造环境下服务组合及优选过程的自动化程度,本发明将工作流与语义Web服务技术优势相结合,提出一种基于动态规划的语义服务组合方法,从封装为语义服务的制造资源中准确、动态生成满足用户需求并且质量最优的组合方案,有利于合理配置资源,提高其利用效率,对于网络化制造模式的应用实施具有意义。

技术方案

为避免现有技术造成的组合方案生成方式的实效性、灵活性不足,实现制造任务需求和语义服务之间的按需分配,本发明采用动态绑定模式。在制造业务流程建模中并不绑定具体的服务,执行一个制造任务时,首先通过工作流引擎将制造业务流程模型进行分解,提取每一个活动节点的需求,然后过服务发现匹配过程获取满足该活动的所有服务,最后根据一定策略从每个挑选合适的候选服务生成服务组合方案,实现将具体的语义服务映射到任务上。

由于每个制造活动都有多个候选服务与之匹配,这就产生了全局优化选取最优语义服务组合方案问题。虽然枚举计算可以穷举所有可能方案,但随着问题规模的扩大、活动数目或候选服务数目的增多,将会产生组合爆炸。因此,本发明将服务组合方案的生成转化为一个动态演化、多阶段的决策过程,即将整个服务组合过程分为若干个互相联系的阶段,在每个阶段都需要做出服务选择决策,并且上一个阶段的服务确定后,会对下一个阶段服务选择决策产生影响。本发明的目标就是在各阶段允许的决策范围内,选择一个最优决策序列,在预定的约束下达到最佳组合服务质量。因此,本发明利用动态规划方法在保持服务间数据语义依赖关系的前提下,求解出全局服务质量(Quality of Service,QoS)最优的服务组合方案。

本发明的技术方案为:

所述一种基于动态规划的语义服务组合方法,其特征在于:采用以下步骤组成:

步骤1:将包含有n-1个制造活动的组合方案按照制造过程分为n个制造活动节点vi,其中i={0,…,n},v0代表开始节点,vn代表结束节点;根据服务发现匹配过程,得到每个制造活动节点对应的满足其功能要求的候选服务,其中候选服务表示制造活动节点vi对应的第j个候选服务;每个制造活动节点对应的满足其功能要求的候选服务组成该制造活动节点的初始状态集合,其中对于初始状态集合Ui,且表示制造活动节点vi有m个满足其功能要求的候选服务;

步骤2:计算制造活动节点的候选服务与后继相邻制造活动节点的候选服务之间的数据依赖关系,并确定制造活动节点的候选服务对应的有效后继服务集合:其中对于制造活动节点vi的第j个候选服务采用以下步骤得到的有效后继服务集合:

步骤2.1:取制造活动节点vi+1对应初始状态集合Ui+1中的元素计算描述输出参数的概念c1与描述输入参数的概念c2之间的语义相似度Sem(c1,c2):

>Sem(c1,c2)=|P(c1)P(c2)||P(c1)P(c2)|+α(c1,c2)|P(c1)/P(c2)|+(1-α(c1,c2))|P(c2)/P(c1)|>

其中函数P(c)表示本体中对概念c的属性定义,∩、/、‖分别是集合的交、差和势运算,>α(c1,c2)=depth(c1)depth(c1)+depth(c2)depth(C1)>depth(C2)1-depth(c1)depth(c1)+depth(c2)depth(C1)depth(C2),>函数depth(c)计算概念c在本体中所处的深度;

步骤2.2:采用步骤2.1的方法遍历制造活动节点vi+1对应初始状态集合Ui+1中的所有元素,得到描述输出参数的概念与描述Ui+1中各个元素输入参数的概念之间的语义相关度,取Ui+1中的语义相关度不小于设定阈值的元素组成的有效后继服务集合>Xi(si(j));>

步骤3:建立每个制造活动节点的原始质量参数矩阵:对于有m个候选服务的制造活动节点vi,vi的原始质量参数矩阵Q(vi)为:

>Q(vi)=[qsi(1),......,q(si(m))]T=qi1(1),qi2(1),......,qiw(1)qi1(2),qi2(2),......,qiw(2)........................qi1(m),qi2(m),......,qiw(m)m×w>

其中表示候选服务的原始质量参数w表示质量参数个数;

步骤4:对每个制造活动节点的原始质量参数矩阵归一化:对于制造活动节点vi的原始质量参数矩阵Q(vi),取分别为矩阵Q(vi)中第k列的最大值和最小值,k=1,…,w;当第k列原始质量参数为参数值越高服务质量越好的正比型质量参数时,将第k列原始质量参数按照

>ibik(j)=qik(j)-qkminqkmax-qkminqkmaxqkmin1qkmax=qkmin>

进行归一化;当第k列原始质量参数为参数值越高服务质量越差的反比型质量参数时,将第k列原始质量参数按照

>dbik(j)=qkmax-qik(j)qkmax-qkminqkmaxqkmin1qkmax=qkmin>

进行归一化;

步骤5:计算每个制造活动节点的每个候选服务的综合质量值:对于制造活动节点vi,根据归一化后的质量参数矩阵,按照

>QoS(si(j))=Σk=1tωkibik(j)Σk=1w-tωkdbik(j)>

计算制造活动节点vi的每个候选服务的综合质量值,其中ωk∈[0,1]并且t代表正比型质量参数的数量;

步骤6:以fi(ui)为优化目标,建立动态规划方程

>fi(ui)=maxsi+1(a)Xi(ui){QoS(si+1(a))+fi+1(ui+1)ui+1=si+1(a)fn(un)=0i=n-1,...,1>

其中ui表示状态集合Ui的元素;采用递归算法对动态规划方程求解,得到全局最优的服务组合方案。

有益效果

本发明结合网络化制造模式特点,采用工作流模型描述的制造业务过程,将语义服务组合方案的生成过程转化为一个动态演化、多阶段决策过程,以服务间数据语义关系为约束,以组合方案综合质量为优化目标,利用动态规划方法生成全局最优的组合方案。该方法易于确定全局最优解,节省了计算量,同时有助于为用户提供更丰富的组合方案结果,提高了组合方案的可执行性和组合过程的自动化程度。

附图说明

图1:服务组合方案的生成过程。

图2:本实施例中服务组合方案的生成过程。

具体实施方式

下面结合具体实施例描述本发明:

本实施例以加工叶片零件为例,该叶片加工分为加工阻尼台(v1)、叶身(v2)、叶根(v3)三道工序,v0和v4为开始和结束节点,如图2所示。用户对于每个质量参数的关注程度相同,要求各种偏差控制在10%内,求解满足该制造任务要求的最优服务组合方案。

本实施例中的基于动态规划的语义服务组合方法采用以下步骤:

步骤1:本实施例中加工叶片零件的加工组合方案包含有3个制造活动,分为加工阻尼台(v1)、叶身(v2)、叶根(v3)三道工序,按照制造过程分为4个制造活动节点vi,其中i={0,…,4},v0代表开始节点,v4代表结束节点;根据服务发现匹配过程,每道工序存在多个候选服务实例可满足要求,其中候选服务表示制造活动节点vi对应的第j个候选服务;每个制造活动节点对应的满足其功能要求的候选服务组成该制造活动节点的初始状态集合,本实施例中的五个制造活动节点的初始状态集合分别为

>U1={s1(1),s1(2),s1(3)},>>U2={s2(1),s2(2),s2(3),s2(4)},>>U3={s3(1),s3(2)},U4={s4(1)}.>

步骤2:为保证组合服务行为的正确性,被组合的服务之间必须满足数据依赖关系,即在组合服务序列中,每个位于序列前面的前驱服务应产生后继服务所要求的输入。本发明将制造资源通过语义服务形式进行封装,服务接口中的输出、输入参数与领域本体中的概念对应起来。

本步骤计算制造活动节点的候选服务与后继相邻制造活动节点的候选服务之间的数据依赖关系,并确定制造活动节点的候选服务对应的有效后继服务集合:

其中对于制造活动节点v1的第1个候选服务采用以下步骤得到的有效后继服务集合:

取制造活动节点v2对应初始状态集合U2中的元素描述每个元素输入参数的概念c2分别为:描述输出参数的概念c1为数控铣床。分别计算描述输出参数的概念c1与描述U2中各个元素输入参数的概念c2之间的语义相似度Sem(c1,c2):

>Sem(c1,c2)=|P(c1)P(c2)||P(c1)P(c2)|+α(c1,c2)|P(c1)/P(c2)|+(1-α(c1,c2))|P(c2)/P(c1)|>

其中函数P(c)表示本体中对概念c的属性定义,在制造资源本体中对数控铣床和加工中心这二个概念的属性定义如下:P(数控铣床)={规格型号,工作台宽度,主轴转速,快移速度,换刀速度,联动速度,主电机功率,主轴最大扭矩,重复定位精度,主轴主高径向圆跳动},P(加工中心)={规格型号,工作台宽度,主轴转速,联动轴数,主电机功率,主轴最大扭矩,重复定位精度,铣削平面度}。∩、/、‖分别是集合的交、差和势运算,例如|P(C1)∩P(c2)|表示P(c1)与P(c2)共有元素的个数,>α(c1,c2)=depth(c1)depth(c1)+depth(c2)depth(C1)>depth(C2)1-depth(c1)depth(c1)+depth(c2)depth(C1)depth(C2),>α(c1,c2)反映了两个概念在本体层次中的位置对语义上相似评价产生的不对称影响。函数depth(c)计算概念c在本体中所处的深度。0≤Sem(c1,c2)≤1,1表示概念c1、c2完全一致,0表示完全不相关。依次计算得到与U2中各个元素的数据依赖关系程度为>Sem(s1(1)·c1,s2(1)·c2)=1,>>Sem(s1(1)·c1,s2(2)·c2)=0.78,>>Sem(s1(1)·c1,s2(3)·c2)=1,>>Sem(s1(1)·c1,s2(4)·c2)=0.78.>由于用户要求各种偏差控制在10%内,即要求数据依赖关系程度的阈值为0.9,所以不是的有效后继服务,不满足数据依赖关系,有效后继服务集合为如图2所示,如果服务节点间有边相连,表示二者之间满足数据依赖关系,可以进行组合操作,否则没有连线。这样在组合方案求解过程中,在每个阶段上只保留真正有效的部分方案,不满足要求的部分方案将作为劣解而放弃,从而及时剪去不可能扩展为最优方案的路径,加快了求解速度。

步骤3:计算服务的综合质量,作为阶段决策的指标。为了保证每个阶段都能做出最优决策,需要建立用于衡量所选定决策策略优劣的阶段指标函数。在功能相似和满足数据依赖关系的前提下,服务质量成为衡量所做决策优劣的重要指标,阶段指标函数记为由于服务质量参数的目标方向、量纲、取值范围等都不一致,简单地对原始质量数值作加权和不能正确反映服务组合方案之间的相对优劣,所以需要对服务质量参数进行规范化处理。这里采用最小-最大规范化方法,选择[0,1]区间将原始语义服务质量数据进行规范化处理,实现质量数据的客观性和可比性。

描述候选服务的所有原始质量参数可以表示为w表示服务质量参数个数,制造活动节点vi的候选服务集合Ui中所有服务的质量参数构成了原始质量参数矩阵。通过这种构造服务质量矩阵方式,将多个空间的质量参数统一在一个计算模型中,增加一个新的质量参数时,即从矩阵中增加新的一列,使得质量参数的添加和删除不影响后续求解过程,满足了服务质量参数的可扩展性要求。

本实例采用响应时间、成本、可靠性、可用性和满意度等5个参数来度量服务质量,建立每个制造活动节点的原始质量参数矩阵,这里以制造活动节点v2为例,有4个候选服务满足了其功能需求,它们的QoS参数如表1所示,据此构造制造活动节点v2的原始质量参数矩阵Q(v2):

表1 v2制造活动节点的候选服务质量参数

>Q(v2)=105000.917121000.60.8452000.80.682030010.99>

步骤4:对每个制造活动节点的原始质量参数矩阵归一化:仍以制造活动节点v2为例,取分别为矩阵Q(v2)中第k列的最大值和最小值,k=1,…,w。

当第k列原始质量参数为参数值越高服务质量越好的正比型质量参数时,将第k列原始质量参数按照

>ibik(j)=qik(j)-qkminqkmax-qkminqkmaxqkmin1qkmax=qkmin>

进行归一化;当第k列原始质量参数为参数值越高服务质量越差的反比型质量参数时,将第k列原始质量参数按照

>dbik(j)=qkmax-qik(j)qkmax-qkminqkmaxqkmin1qkmax=qkmin>

进行归一化;

由于可靠性、可用性和满意度为正比型质量参数,响应时间、成本为反比型质量参数,所以归一化后的制造活动节点v2的质量参数矩阵B(v2):

>B(v2)=2/300.7510.61/3100.5010.750.500.800.510.751>

步骤5:计算每个制造活动节点的每个候选服务的综合质量值:对于制造活动节点vi,根据归一化后的质量参数矩阵,按照

>QoS(si(j))=Σk=1tωkibik(j)Σk=1w-tωkdbik(j)>

计算制造活动节点vi的每个候选服务的综合质量值,其中ωk∈[0,1]并且表示第k个质量参数在质量效用上所占的比重,反映了用户偏好,t代表正比型质量参数的数量。

本实施例中用户对各质量参数的关注度相同,即ω12345=0.2。制造活动节点v2为例,根据B(v2)中的数据,得到各服务的综合质量值分别为:>QoS(s2(2))=0.38,>>QoS(s2(3))=0.74,>>Qos(s2(4))=5.5,>如图2所示,服务节点s所标识数值为该服务综合质量值。

步骤6:以fi(ui)为优化目标,建立动态规划方程

>fi(ui)=maxsi+1(a)Xi(ui){QoS(si+1(a))+fi+1(ui+1)ui+1=si+1(a)fn(un)=0i=n-1,...,1>

其中ui表示状态集合Ui的元素;采用递归算法对动态规划方程求解,得到全局最优的服务组合方案。

本实施例中:

①当i=3时,状态集合当状态或者时,其后继服务集合所以建立递归方程为:

>f3(u3)=maxs4(1)X3(u3){QoS(s4(1))+f4(u4)}f4(u4)=0>

由递归方程得到f3(u3)=0,最优后继服务

②当i=2时,状态集合>U2={s2(1),s2(2),s2(3),s2(4)}:>

当状态时,有效后继服务集合为根据递归方程得到:

>f2(s2(1))=maxQoS(s3(1))+f3(u3)QoS(s3(2))+f3(u3)=max0.92+00.89+0=0.92,>最优后继服务>x2*(s2(1))=s3(1);>

同理,>f2(s2(2))=0.92,>最优后继服务>x2*(s2(2))=s3(1);>

>f2(s2(3))=0.92,>最优后继服务>x2*(s2(3))=s3(1);>

>f2(s2(4))=0.89,>最优后继服务>x2*(s2(4))=s3(2).>

③当i=1,状态集合>U1={s1(1),s1(2),s1(3)}:>

当状态时,有效后继服务集合为根据递归方程得到:

>f1(s1(1))=maxQoS(s2(1))+f2(s2(1))QoS(s2(3))+f2(s2(3))=max3.53+0.920.74+0.92=4.45,>最优后继服务>x1*(s1(1))=s2(1);>

同理,>f1(s1(2))=1.66,>最优后继服务>x1*(s1(2))=s2(3);>

>f1(s1(3))=0.39,>最优后继服务>x1*(s1(3))=s2(4);>

根据状态转移方程以及以上的计算过程,采用顺序追踪法,可求得本实例的最优决策序列:

>u1=s1(2)u2=s1(2)u3=s2(3)u4=s3(1)x1*=s1(2)x2*=s2(3)x3*=s3(1)x4*=s4(1)>

由此可知,满足该任务要求的最优服务组合方案为确定最优服务组合方案后,即决定了对业务流程中各个活动QoS的赋值,因此还可以计算出该方案的总体任务时间完成时间、成本等其他关键质量参数值。

去获取专利,查看全文>

相似文献

  • 专利
  • 中文文献
  • 外文文献
获取专利

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号