最优化理论与方法论文

《最优化理论与方法论文》由会员分享，可在线阅读，更多相关《最优化理论与方法论文（11页珍藏版）》请在金锄头文库上搜索。

1、第 1 页 共 11 页优化理论与方法第 2 页 共 11 页全局及个性化web服务组合可信度的动态规划评估方法摘要： 随着 Internet的快速发展 ,web 服务作为一种软件构造形式其应用越来 越广泛。单个 web服务无法满足日益复杂的用户需求,web 服务组合有效地解决 了这个问题。然而 , 随着功能相似的web服务实例的不断出现 , 如何选择可信的 web 服务组合成为了人们关注的热点。服务选择依赖于web 服务组合的评估结 果, 因此 , 本文主要从web 服务组合着手 , 对其可信性进行研究, 提供一种可信 web 服务组合评估方法。：针对 web 服务组合的全局及个性化问题,

2、提出了基于 全局的个性化web 服务组合可信评估方法。从全局角度动态地调整评估模型; 同时引入用户业务关注度来描述原子web 服务对服务组合可信性的影响程度; 结合前文的度量及评估方法, 构建一个全局的个性化服务组合可信评估模型; 并 分析了模型的相关应用 , 给出了改进的动态规划模型。关键字： web服务组合可信评价；全局个性化；动态规划；0. 引言随着软件系统规模的日趋复杂，运行环境的不断开放，软件的可信性要求 日益增加，可信软件成为了研究的热点。据中国互联网发展状况统计报告 统计显示，截至 2014 年 12 月底，我国网民数量突破8 亿，全年新增网民 5580 万。互联网普及率较上年底

3、提升4 个百分点，达到 38。3%。因此，随着 Internet 的广泛应用和网络技术的快速发展，面向服务的软件体系结构（SOA）作为一 种新型的网络化软件应用模式已经被工业界和学术界广为接受。同时，网民对 互联网电子商务类应用稳步发展，网络购物、网上支付、网上银行和在线旅游 预订等应用的用户规模全面增长。因而，对web服务的可信性要求更高。单个 web 服务的功能有限，往往难以满足复杂的业务需求，只有通过对已有web 服 务进行组合，才能真正发挥其潜力。在现有的web服务基础上，通过服务组装 或者 Mashup 方式生成新 web 服务作为一种新型的软件构造方式，已成为近年 的研究热点之一。

4、 web 服务组合并不是多个原子web 服务的简单累加，各原子 web 服务之间有着较强的联系。因此对web 服务组合的可信需求更高。目前大 量的研究工作着重于如何实现原子web 服务间的有效组合，对服务组合的可信 评估研究较少。如今，随着web 服务资源快速发展，出现了大量功能相同或相 似的 web 服务，对 web 服务组合而言，选择可信的web服务变得越来越难。在 大量的功能相似的原子web服务中，如何选出一组可信的web 服务组合，成为 了人们关注的热点问题。本文将从web 服务组合着手，对其可信性进行研究， 旨在提供一种可信web 服务组合评估方法，为web 服务组合的选择提供依据。

5、 web 服务组合的可信度主要包括以下三个部分： 1）基于领域本体的web服务可信度量模型。 2）基于偏好推荐的原子web 服务可信评估方法。 3）基于全局的个性化web 服务组合可信评估方法。研究思路 ：本文主要研究基于全局的个性化web服务组合的可信评估方法，其研究思 路可以大致如下：基于领域本体的web 服务可信度和基于偏好推荐的原子web 服务可信评估方法。针对web 服务组合的四种基本组合结构模式，主要研究如第 3 页 共 11 页何从全局角度动态地调整评估模型；同时引入用户业务关注度来表达原子web 服务对服务组合可信性的影响程度（从用户角度）；应用动态规划的方法构建一 个全局的个

6、性化 web 服务组合可信评估模型， 最后给出一个代表性的数值算例。文章结构布局：1 节将主要介绍几种不同的服务组合模式，并对进行分析，引入基于全局 的问题，并给出一种解决方法；2 节将主要介绍如何构建一个全局的个性化服 务组合评估模型，并根据用户的业务关注度，获得各原子web 服务对服务组合 的可信性影响权重，进而获得可信评估值。3 节将主要介绍如何应用此模型， 并给出了一个最优服务组合选择方法（动态规划模型）。1. 基于组合全局的调整策略基于全局的评估策略，是指从全局角度计算服务组合的可信评估值。目前 已有的全局评估模型， 基本都是采用原子服务属性值汇总，再加权评估的方式， 没有考虑到组合

7、服务的业务逻辑关系（服务组合模式）。在本节的全局策略中， 将充分考虑服务组合方式对服务组合可信性的影响，为可信web 服务组合评估 提供一种更可信的全局策略。首先，介绍基本的服务组合模式；接着，分析不 同模式的影响；最后，给出考虑全局的调整方法。服务组合流程可以被定义为 一组相互关系的任务（或业务） ，这些任务具有各种不同的功能，并通过原子服 务完成。在常见的服务组合应用中，原子web 服务通过一定的组合模式构成服 务组合。研究者提供了多种原子web服务组合模式，提WS4BPEL 支持多种组 合模式。但实质上都可以分解为顺序模式、分支模式、并行模式和循环模式的 有限递归嵌套，因此本文仅讨论这4

8、 中模式。 1）顺序模式相当于程序结构中的顺序结构，服务组合中的服务根据业务被分解 为多个阶段。每个服务按顺序依次完成其业务功能。 2）分支结构相当于程序结构中的分支结构，多个分支中根据一定的判断条件选 择一条分支执行。在计算该模式下的属性值时， 由于无法判断具体运行那条， 一般采用统计方式估算，即根据可能执行的概率计算平均值。 3）并行模式相当于程序结构中的并行结构，多条分支同时进行。一般用于为下 一阶段的业务准备多个初始条件。这些任务之间相互独立，全部完成后，才 能进入下一阶段。 4）循环模式相当于程序结构中的循环结构，一条路径被重复循环地执行次。可 以看作顺序模式的一个复合结构，即把这条

9、路径展开Z次执行。在进行可信 评估时，需要考虑执行的次数。 由上面四种结构组合出来的服务组合网络有多种形式，如何从中识别出关键的 路线成了研究的关键步骤；关键路径：服务组合业务流程中执行时间最长的那 一条路径。关键路径上的业务称为关键任务，其他任务称为非关键任务。其中 关键路径的识别问题类似求解最短路径问题（目标函数转化为最大），可采用 E.W. Dijkstra 提出的 T、P 标号算法或 L.R.Ford 提出的 Ford 算法。2基于全局的个性化web服务组合可信评估模型2.1 构建评价模型步骤目前大部分关于服务组合评估的研究中，基本都是采用的全局一致化的评第 4 页 共 11 页估模型

10、。即在服务组合中，每个原子服务釆用相同的评估属性项及权重，然后 根据每个原子服务的属性评估值计算出服务组合全局的各属性评估值，最后结 合权重得到服务组合的综合评估值。虽然这种评估方法取得了一定的成果，但 是每个原子服务的类型存在差异，其处在的领域不同，根据前面分析，显然， 其评估属性及其权重是不一致的。所以，这种全局一致化的评估模型很难得到 可信的评估值本文提出全局个性化的可信评估模型在原子服务个性化的评估模 型基础上合成服务组合的评估模型。其构建步骤如下： 步骤 1：构建服务组合中原子web 服务的个性化评估模型： 步骤 1.1：识别服务组合中各原子web 服务的类型； 步骤 1.2：根据类

11、型构建基于领域的评估模型（算法2。1 WSTAM） 。 步骤 2：构建好个性化的评估模型后，需根据原子web 服务在服务组合中的位 置（关键路径、非关键路径） ，动态地调整其评估模型： 步骤 2.1：识别非关键任务； 步骤 2.2：对并行路径非关键任务上的web 服务评估模型进行调整。2.2 确定原子 web服务权重不同的用户对服务组合中不同的原子服务的关注程度是不同的。如，在网 上购物流程中，用户对选择商品、网上支付、提交评价信息这三个原子服务， 更多地关注前两个原子服务的可信性，对提交评价信息这个服务的关注较少。 虑到用户对每个原子服务的关注度是定性的，采用先排序后比较相邻关注度的 方法，

12、将用户的定性关注度转化为定量的权重值。具体步骤如下： 步骤 1：将服务组合中所有的原子服务组成集合， 步骤 2：用户根据个人对服务组合中原子服务关注程度的高低进行降序排序，获得降序序列(1)(2)(3)()nssss其中，可以通过不断地从剩余的原子服务中选择出最重要的一个原子服务来完成排序。步骤 3：用户设定序列(1)(2)(3)( )nssss中，相邻两个原子服务( ) is 与( +1)is的相对关注度。步骤 4： 根据用户给出的相对关注度等级， 获得相对权重(1)(2)(1),nrrr其中( )ir是两个原子服务的绝对权重之比。又 因 为 ：()(1)( )(1)(2)()1( )( )

13、( )(1)iiiiinnaaakiinaaa kirrrr其 中 ：( ) i 11nia，()()()1111 11 ( )( )()( ) 111(1)innnnnnakina naa iiikiraa则有：11() 11 ()(1)nnk ikinra（4.1）1( )( )( )ninkkiaar（4.2）按公式 4-1 和 4-2 计算得到用户对每个原子服务的用户关注度权重，即每个原第 5 页 共 11 页子服务对整个服务组合可信评估重要程度权重。12 1,1nni iAa aaa（4.3）计算服务组合可信评估值，需要的信息包括各原子web 服务的可信属性及属性 权重值，各原子we

14、b 服务相对服务组合的权重，各属性的评估值。在计算web服务组合评估值时还需考虑其执行的概率ip ，和次数il ，因此服务组合评估值的计算公式如下：11niiii iniii ipLaDpLaD（4.4）其中，ia ，iD 分别表示第i个原子 web 服务的权重和可信评估值，D 是整个服务组合的可信评估值3. 动态规划在服务组合可信评价方案中的应用对 web服务进行可信评估的目的是为了在大量满足功能需求的web服务中 选择出最可信的web服务组合。根据 web 服务组合的状态， 其应用可分为两类： 1）对已有的 web服务组合进行评估，选择最优的web 服务组合； 2）选择最优 的原子 web

15、服务组合成可信的web服务组合。下面将从这两方面分析其应用。3.1 web 服务组合的选择对多个已经组合好的web 服务组合，我们只需按其组合模式分解成多个原 子 web服务，再釆用第2 节中的方法，获得每个web 服务组合的可信评估值。 排序选择评估值最大的web服务组合即可，选择出的服务组合可信性最好。具 体的操作，上文中已详述，此处不再重复。3.2 原子 web服务的最优组合根据本文提出的评估方法，原子web服务最优组合问题，可转化为了一个 动态规划问题。即将最优组合问题转化为多阶段决策问题，随着时间的推移， 在每一阶段上做出最恰当的决策，以实现web 服务组合的可信性全局最优。同 时每

16、阶段需根据服务组合的模式及客观执行时间动态调整原子web服务的评估 模型。选择出的最优组合满足功能需求，且可信性最优。动态规划包括以下几个基本概念： 1）阶段：把所给的问题恰当地分为若干个相互联系的阶段，阶段的划分 一般是根据时间和空间的自然特征来划分。描述阶段的变量称为阶段变量，可 用 k 表示。如，在本文的最优组合中可按执行先后的顺序将每个原子web 服务 分成一个阶段。 2）状态：状态表示每个阶段始所处自然状态或客观条件，它描述了研究 问题过程中的状况，又称不可控因素。描述过程状态的变量称为状态变量，可用kZ 表示第 k 阶段的状态变量。状态变量应具有无后效性，即如果某阶段的状第 6 页 共 11 页态给定后，则以后过程的发展仅仅取决于这一时刻的状态，而与这一时刻以前 的状态和决策无关。如，在本文中非并行路径上的每个原子web 服务的服务实 例可作为状态变量。 3）决策：决策表示当过程处于某一阶段的某一状态时，所做出的不同的决定或选择。 描述决策的变量称为决策变量， 可用()kkc z表示决策变量，()kkcz表示每个阶段的允许决策集合。如，在本文中，每个阶