基于图规划的启发式Web服务组合方法

摘要

本发明提供的是一种基于图规划的启发式Web服务组合方法。首先对服务组合问题进行建模，阐述了其与智能规划问题的对应关系；为了解决基于图规划的服务组合算法的盲目搜索的缺点，提出了状态距离的概念，分析和证明了其在可达性分析中的作用，给出了状态距离矩阵的构建方法；依据状态距离矩阵，设计启发函数对服务的可达性进行估计，修剪不必要的服务，减小规划图的规模，提高算法的求解效率。

说明书

技术领域

本发明涉及的是一种启发式Web服务组合方法。

背景技术

如今，服务组合问题得广大研究人员的关注，其中，在工业界主要致力于将服务组合的方法和理论应用于工程实践方面，主要采用流程建模和执行的引擎的方式，存在着灵活性和扩展性差的缺陷。在学术界，研究人员关注于服务的自动组合方法的理论研究，为了实现服务的自动组合，通常通过语义服务描述服务，以便计算机能够自动理解服务的语义信息，进而结合智能规划的相关理论，解决服务组合问题。但是自动组合方法的相关理论并不成熟，往往难以在实际工程中得到应用。服务组合问题从不同的角度可以得到不同的分类结果，按照组合契机的不同分为静态方法和动态方法；按照支持技术的差异归类为图搜索控制的方法、业务流控制的方法以及智能规划理论控制的方法；将服务组合问题分为实时任务求解的方案以及业务驱动的方案

流程驱动的组合方案是通过在流程定义图中绑定服务节点实现的，表现为参与者按照预定规则采取行动实现功能。由于工作流已经被广泛使用，因此流程驱动的组合方案有着成熟的理论基础和技术应用背景。流程驱动的组合方式以工作流为技术基础，以业务模板为核心，用户使用起来易于理解，提高了执行期间的可管理性。其缺点在于自动性差，大部分工作必须采用手动的方式，而且需要领域专家设计业务模板，难以应对大规模、复杂的业务流程。

实时任务求解的方案是基于AI规划理论的组合方案，采用经典的人工智能的思想，把服务组合问题映射为规划问题，通过智能规划推理获得解，即在已知起始状态和目标状态的情况，从Web服务候选库中搜寻一条最优执行序列来实现这两个状态间的逐步演化。基于AI规划的组合方案，即按照智能规划的相关描述方法刻画组合问题，并自动求解。因此服务组合问题可以抽象为智能规划问题，智能规划领域的众多研究成果已经被应用于服务组合。

图规划算法是一个迭代的过程，通过每一次迭代，规划图会扩展新的服务并且得到新的命题。在不断的迭代扩展之后，若命题层包含了全部目标命题或者规划图进入了不动层则结束扩展过程。如果规划图进入不动层，说明没有满足需求的服务解。否则，规划图进入解提取阶段，该阶段规划图对每个目标状态需找一组服务满足该状态，并形成新的目标状态，直至所有目标状态均出现在初始状态中为止，则得到该问题的规划解。

如果规划问题无解的那么规划图将不会返回解决方案；否则，它将返回一个解决问题方案的动作序列集合。另外，每一个规划图存在一个层数k，并且只需要多项式时间完成对规划图的扩展。并且图规划的算法具有可靠性、完整性和可终止性。

在基于图规划的服务组合算法中：

(1)服务ws可以映射为规划问题中的动作a；

(2)服务的输入参数I可以映射为前提条件preconds(a)；

(3)服务的输出参数O可以映射为的动作效果effects(a)；

(4)用户请求中的r_in可以映射为的初始状态s₀；

(5)用户请求中的r_out可以映射为的目标状态g；

(6)G＝<SL₁,AL₁,SL₂,AL₂,...,SL_i-1,AL_i-1,SL_i>：由动作层和状态层构成的规划图。

在经典图规划问题中，动作存在积极效果和消极效果之分，然而，在服务组合问题中，Web服务只存在积极效果，因此提出了简单规划图以便于应用在服务组合问题中，在简单规划图中，动作之间是相互独立的，不存在动作与动作、命题与命题的互斥关系。为便于描述，本发明将继续将简单规划图称为规划图。基于图规划的服务组合算法分成扩展阶段和解提取阶段。

扩展阶段：

(1)根据用户给出的初始命题集合构建第一层状态层

(2)根据服务库扩展满足条件的服务ws并形成规划图动作层AL_i

(3)将effects(ws)形成新的状态层SL_i+1

(4)重复步骤(2)和(3)，直至目标状态全部出现在状态层中，或者到达不动层。

(5)不断迭代扩展规划图，直至规划图中包含全部目标状态则通过解提取算法得到一个服务组合方案，若规划图达到不动层，则说明不存在一组服务满足用户需求。

解提取阶段：

(1)对每个目标状态g，寻找一组服务WS,使的其能输出并得到状态g

(2)将effects(WS)构成新的目标状态集合；

(3)重复以上过程，直至到达初始状态层，则得到一个从初始状态到达目标状态的组

合解ResultWS(<WS₁,WS₂,...,WS_i>)。

图2所示为服务关系图示例，其中A、B和C为该组合问题的初始状态，H和J为目标状态，W₁、W₂、W₃、W₄和W₅为服务库中已有的服务。由初始状态A、B和C构成第一个命题层，在服务库中搜索并选取所有可以执行的服务构成第一个动作层，将动作层中的服务W₁的输出D和E添加到第二层命题层中，形成新的命题层，依次类推，直至目标状态G和H全部包含在命题层中，此时进入解提取阶段。在该阶段，对于子目标H和I，在前一动作层中选择一组能够到达目标H和I的服务W₄，并将该服务的输入D和F构成新的目标状态，依次类推，直至到达初始状态，则得到一组解W₁、W₂、W₄使得由初始状态A、B和C能够到达目标状态H和J。

基于图规划的服务组合方法，在时间复杂度与空间复杂度上相对于其他方法均有一定优势，但仍然存在着不足：基于图规划的服务组合算法的扩展过程上类似于广度优先算法，盲目搜索，时间复杂度高，易发生组合爆炸，难以应用于海量服务集。

发明内容

本发明的目的在于提出一种能缩小规划图空间，提高求解效率的基于图规划的启发式Web服务组合方法。

本发明的目的是这样实现的：

步骤1：输入用户请求和数据库中的服务；

步骤2：构建状态距离矩阵M(i,j)；

步骤3：计算启发函数值h(ws_i),对服务的可达性进行估计，修剪不必要的服务；

步骤4：判断规划图进入不动点层，则执行步骤5，否则执行步骤6；

步骤5：规划无解，算法结束；

步骤6：判断规划图出现某个状态层包含全部目标状态，则执行步骤7，否则返回步骤3；

步骤7：执行解提取算法；

步骤8：输出组合结果，结束。

本发明还可以包括：

所述状态距离矩阵以及启发函数值为：

(1)服务用一个三元组ws(ID,S_in,S_out)表示，其中S_in表示一组用于描述输入状态的语义概念集合，S_out表示一组用于描述输出状态的语义概念集合；

(2)语义状态距离D(s_i,s_j)表示语义状态s_i与语义状态s_j的关联程度：

(3)语义状态距离矩阵M，是用以表示语义状态之间的关系的矩阵，具体为：

M(i,j)＝D(s_i,s_j)；

状态距离描述了状态与状态之间的弱可达性，即状态距离总是过高的估计服务解的可达性，若状态A与状态B之间的状态距离无穷大，即不可达，则不存在一组规划解使得从状态A到达状态B；

(4)若初始状态为r_in＝(i₁,i₂...i_n)，目标状态r_out＝(o₁,o₂...o_n)，服务WS＝(ws₁,ws₂...ws_n)，N(S)表示状态集合S所含状态的个数，其中g_s(p)为从状态s到目标状态p的估计值即为状态距离矩阵M(s,p)的值，则服务ws_i的启发值h(ws_i)为：

h(ws_i)利用服务的输出状态距离的值估计了当前服务与目标状态集合的可达性，该值描述了服务的输出状态与目标状态之间的状态距离的均值，h(ws_i)总是在状态距离中选取最小值进行估计，h(ws_i)的值为无穷大时、服务ws_i不会出现在解中。

本发明分析了基于图规划的服务组合算法的缺陷，并对其改进提出了图规划框架下的启发式Web服务组合算法(SDSC-GP)。首先对服务组合问题进行建模，阐述了其与智能规划问题的对应关系；为了解决基于图规划的服务组合算法的盲目搜索的缺点，提出了状态距离的概念，分析和证明了其在可达性分析中的作用，给出了状态距离矩阵的构建方法；依据状态距离矩阵，设计启发函数对服务的可达性进行估计，修剪不必要的服务，减小规划图的规模，提高算法的求解效率。

由于基于图规划的服务组合算法的扩展过程上类似于广度优先算法，存在扩展效率低的问题，本发明通过评估服务与目标状态的可达性，对规划图进行剪枝。提出了状态距离的概念，以评估当前服务与目标状态的关联程度以及可达性，并对不可达的服务进行剪枝，从而减小规划图规模，提高规划图的扩展效率。最后证明了通过该剪枝策略不会破坏规划图的解。该方法在不影响求解成功率的基础上，拥有更低的空间消耗和更高的求解效率。

在启发式算法中，为了避免盲目搜索不必要的节点，为了缩小解空间，通常采用基于松散问题的启发式策略。在该策略中，通常将原问题的约束条件减少，简化问题规模，在通过计算简化问题下的代价，估计原问题的目标代价。其提出的状态距离，通过状态距离的计算算法，通过松散问题中的状态可达性估算出原问题中的状态可达性，进而对每个动作(服务)进行评估，删除对目标状态可达性没有促进作用的服务。通常情况下，随着松散程度的减小，简化问题与原问题越接近，松散估计也更加准确。

结合图4，在图中根据状态距离公式的计算，D(A,G)＝2，D(B,H)＝2，D(C,K)＝2。对于状态A而言，到达状态G的状态距离D(A,G)＝2，由于服务W₄缺少输入状态C，并不存在一组服务使得状态A到达状态G，状态A到状态G的真实距离为0；而对于状态B来说，其状态距离D(B,H)＝2，同时存在一组服务(W₂,W₃,W₅)使得状态B到达状态H，即状态B到达状态H的真实距离为3。对于状态C而言，其状态距离D(C,K)＝2，存在一组服务(W₆,W₇)使得状态C到达状态K，即状态C到达状态K的真实距离为2。由此可以知道，状态距离总是过高估计状态之间的可达性。

从状态矩阵的构建过程不难发现，状态矩阵描述了所有状态之间的关联程度和可达性。

本发明的剪枝策略，可以避免规划图的盲目扩展，有效的减小规划图的大小，提升求解效率，并且启发值h(ws_i)的计算复杂度很低，若假设ws_i的输出参数的最大个数为c，目标状态集合的参数个数为k，则h(ws_i)的计算复杂度为O(k*c)，通常情况下c和k是一个小于3的数，因此h(ws_i)计算效率高。

附图说明

图1是基于图规划的服务组合算法的服务关系图示例。

图2是基于图规划的服务组合算法的规划图示例。

图3是本发明的流程图。

图4是本发明的服务关系图。

图5是本发明的服务关系图。

图6是状态矩阵示例。

图7是剪枝效果示例图。

图8是本发明的具体实施方式的总体流程图。

图9是本发明的状态距离矩阵框图。

图10为三种方法在不同数据规模的情况下，组合成功率的变化情况。

图11为三种方法在不同数据规模的情况下，服务请求处理时间的变化情况。

图12是规划图规模对比图。

具体实施方式

下面举例对本发明做更详细的描述。

结合图8，本发明的基于图规划的启发式Web服务组合算法包括：

步骤1：输入用户的请求(r_in,r_out)和服务库中的服务；

步骤2：构建状态距离矩阵M(i,j)；

步骤3：初始化状态层SL₁；

步骤4：遍历服务库的服务；

步骤5：判断当前状态层是否包含服务所需的全部输入参数，若满足则执行步骤6，否则返回步骤4；

步骤6：根据公式2-3计算启发值h(ws_i)；

步骤7：若h(ws_i)不是最大值，即未到临界值，则执行步骤8，否则认为当前服务不能成为规划解的一部分，返回步骤4；

步骤8：将该服务加入到第一层动作层AL₁，将服务的输出状态加入到新的状态层SL₂；

步骤9：判断是否遍历完服务库中的服务，则执行步骤10，否则返回步骤4；

步骤10：产生完整的新的状态层SL₂；

步骤11：判断所有的目标状态r_out出现在状态层，则执行步骤12，否则执行步骤14；

步骤12：执行解提取算法；

步骤13：输出组合结果，算法结束；

步骤14：判断规划图进入不动点层，则执行步骤15，否则返回步骤4；

步骤15：规划无解，算法结束。

结合图9，本发明在规划图的扩展过程中构建状态距离矩阵，构建状态距离矩阵的方法如下：

步骤1：输入用户请求(r_in,r_out)和服务库中的服务；

步骤2：初始化矩阵M，M(i,j)＝∞；

步骤3：遍历服务库的每个服务；

步骤4：将包含初始状态和目标状态的服务M(i,j)赋值为1；

步骤5：遍历矩阵M的每个值；

步骤6：判断服务M(i,j)、M(j,k)都不为0，则执行步骤7，否则返回步骤5；

步骤7：进行计算M(i,k)；

步骤8：判断k<j，则执行步骤9，否则执行步骤10；

步骤9：标记为真，返回步骤5；

步骤10：标记为假；

步骤11：完整的状态距离矩阵。

下面讨论规划图是可终止的，首先给出不动点层的定义如下：

定义1.规划图G的不动层是第k层，则对G的低i层恒等于第k层。即SL_i＝SL_k,AL_i＝AL_k。

定义2.每个规划图G都存在一个最小的不动点层k，使得SL_k-1＝SL_k。

由以上两个定义可知，由于在规划图的扩展过程中，命题层中的状态个数一定是单调递增的，即命题层的规模不断增大，而经典规划问题中命题个数有限，因此规划图算法必然存在着不动点层k。因此，若请求无规划解，该算法一定能到达不动点层，并终止该算法。

实验验证：

为验证SDSC-GP方法的有效性，采用组合成功率、规划图规模、组合时间作为衡量指标，与PGSGA方法以及ACSWS-PG方法进行对比试验。

测试的软件环境以及硬件环境如下：

CPU：Intel(R)Core(TM)2 Quad CPU

物理内存：1.96GB

主频：2.66GHz

操作系统：Windows XP Professional

数据库：MySQL

软件工具：Protégé具有免费下载、图形化界面、丰富的插件等特性，因此本课题选择Protégé作为本体编辑器，使用Protégé下的OWL-S Editor插件进行语义Web服务描述OWL-S文档的编辑。OWL-S API是由马里兰大学开发并维护的一套Java API，用于OWL-S文件的创建、读写和执行。本实验使用OWL-S API的类库解析OWL-S文件，获取OWL-S服务的输入输出等信息，之后将智能规划产生的结果转化为组合服务的OWL-S文件，执行该目标服务。

实验数据：OWLS-TC4数据集是开源的，可以由个人和团体任意使用，该数据集由Benedikt Fries，MahboobAlam Khalid，Martin Vasileski共同开发，包含1083个语义Web服务，涉及交通、经济、教育、食品、地理、医药、仿真、旅游和武器九个领域。

测试程序均采用java语言实现。为了衡量算法的有效性，本课题在OWL S-TC4中随机选取不同规模的5个服务库，分别为200、400、600、800、1000。本课题与PGSCA算法以及ACSWS-PG算法进行对比，采用组合成功率与请求处理时间作为评价标准。

实验结果与分析：

针对实验生成了5组服务请求，每组含有100个服务请求。在5个服务库上分别提交这5组服务请求，比较PGSCA、ACSWS-PG以及SDSC-GP这三种方法在不同规模的服务库上服务组合的成功率。

图10为三种方法在不同数据规模的情况下，组合成功率的变化情况。随着数据集中服务数量的增加，PGSCA、ACSWS-PG以及SDSC-GP方法的组合成功率均有明显增长，这表明，随着数据集规模的增加，规划解存在的可能性增加，这是与实际情况相符合的。ACSWS-PG与SDSC-GP方法，在服务规模相同的情况下，其组合成功率均高于PGSCA方法，这是由于PGSCA在处理参数匹配时采用的基于关键字的匹配方式，无法匹配出互为等价类的本体参数，造成了服务组合成功率的降低。

图11为三种方法在不同数据规模的情况下，服务请求处理时间的变化情况。从图中可以方便的看出，PGSCA、ACSWS-PG以及SDSC-GP方法的求解时间，随着服务数量的增加呈上升趋势，其中ACSWS-PG方法的组合请求处理时间低于PGSCA方法，SDSC-GP方法的组合请求处理明显低于ACSWS-PG方法，但随着服务数量的增加，SDSC-GP方法的组合请求处理时间开始趋近于PGSCA方法。ACSWS-PG方法对服务的输出参数建立倒排索引优化了PGSCA方法，因此ACSWS-PG方法的处理效率高于PGSCA方法是合理的。SDSC-GP方法的求解时间低于ACSWS-PG方法和PGSCA方法说明了，SDSC-GP通过建立状态距离矩阵，对规划图进行剪枝的方法可以有效的提示规划求解效率。但随着服务数量的增加，SDSC-GP方法的组合请求处理时间开始趋近于PGSCA方法，这说明随着服务数量的增加，语义状态之间的关联程度增大，导致PGSCA方法的剪枝效果变弱。

为了验证SDSC-GP方法能够减小规划图的规模，实验随机生成100个请求，并在规模为200、400、600、800、1000的服务库上分别用SDSC-GP和PGSCA方法进行求解统计规划图扩展的服务数量的平均值。实验结构如图11所示。

由图12所示，随着服务规模的增大，SDSC-GP和PGSCA方法构建的规划图的规模增大，SDSC-GP与PGSCA方法规模的差值站PGSCA方法的比例逐渐减小，SDSC-GP方法构建的规划图规模始终小于PGSCA方法构建的规划图规模。两种方法随服务库的增大规划图的规模增大，SDSC-GP方法构建的规划图规模始终小于PGSCA方法构建的规划图规模验证了SDSC-GP方法的剪枝效果。SDSC-GP与PGSCA方法规模的差值站PGSCA方法的比例逐渐减小，这说明随着服务数量的增加，状态之间的关联程度增大，导致PGSCA方法的剪枝效果变弱。