最优化理论与方法论文(DOC)

第1页共11页优化理论与方法第2页共11页全局及个性化web服务组合可信度的动态规划评估方法摘要：随着Internet的快速发展,web服务作为一种软件构造形式其应用越来越广泛。单个web服务无法满足日益复杂的用户需求,web服务组合有效地解决了这个问题。然而,随着功能相似的web服务实例的不断出现,如何选择可信的web服务组合成为了人们关注的热点。服务选择依赖于web服务组合的评估结果,因此,本文主要从web服务组合着手,对其可信性进行研究,提供一种可信web服务组合评估方法。：针对web服务组合的全局及个性化问题,提出了基于全局的个性化web服务组合可信评估方法。从全局角度动态地调整评估模型;同时引入用户业务关注度来描述原子web服务对服务组合可信性的影响程度;结合前文的度量及评估方法,构建一个全局的个性化服务组合可信评估模型;并分析了模型的相关应用,给出了改进的动态规划模型。关键字：web服务组合可信评价；全局个性化；动态规划；0.引言随着软件系统规模的日趋复杂，运行环境的不断开放，软件的可信性要求日益增加，可信软件成为了研究的热点。据《中国互联网发展状况统计报告》统计显示，截至2014年12月底，我国网民数量突破8亿，全年新增网民5580万。互联网普及率较上年底提升4个百分点，达到38。3%。因此，随着Internet的广泛应用和网络技术的快速发展，面向服务的软件体系结构（SOA）作为一种新型的网络化软件应用模式已经被工业界和学术界广为接受。同时，网民对互联网电子商务类应用稳步发展，网络购物、网上支付、网上银行和在线旅游预订等应用的用户规模全面增长。因而，对web服务的可信性要求更高。单个web服务的功能有限，往往难以满足复杂的业务需求，只有通过对已有web服务进行组合，才能真正发挥其潜力。在现有的web服务基础上，通过服务组装或者Mashup方式生成新web服务作为一种新型的软件构造方式，已成为近年的研究热点之一。web服务组合并不是多个原子web服务的简单累加，各原子web服务之间有着较强的联系。因此对web服务组合的可信需求更高。目前大量的研究工作着重于如何实现原子web服务间的有效组合，对服务组合的可信评估研究较少。如今，随着web服务资源快速发展，出现了大量功能相同或相似的web服务，对web服务组合而言，选择可信的web服务变得越来越难。在大量的功能相似的原子web服务中，如何选出一组可信的web服务组合，成为了人们关注的热点问题。本文将从web服务组合着手，对其可信性进行研究，旨在提供一种可信web服务组合评估方法，为web服务组合的选择提供依据。web服务组合的可信度主要包括以下三个部分：1）基于领域本体的web服务可信度量模型。2）基于偏好推荐的原子web服务可信评估方法。3）基于全局的个性化web服务组合可信评估方法。研究思路：本文主要研究基于全局的个性化web服务组合的可信评估方法，其研究思路可以大致如下：基于领域本体的web服务可信度和基于偏好推荐的原子web服务可信评估方法。针对web服务组合的四种基本组合结构模式，主要研究如第3页共11页何从全局角度动态地调整评估模型；同时引入用户业务关注度来表达原子web服务对服务组合可信性的影响程度（从用户角度）；应用动态规划的方法构建一个全局的个性化web服务组合可信评估模型，最后给出一个代表性的数值算例。文章结构布局：1节将主要介绍几种不同的服务组合模式，并对进行分析，引入基于全局的问题，并给出一种解决方法；2节将主要介绍如何构建一个全局的个性化服务组合评估模型，并根据用户的业务关注度，获得各原子web服务对服务组合的可信性影响权重，进而获得可信评估值。3节将主要介绍如何应用此模型，并给出了一个最优服务组合选择方法（动态规划模型）。1.基于组合全局的调整策略基于全局的评估策略，是指从全局角度计算服务组合的可信评估值。目前已有的全局评估模型，基本都是采用原子服务属性值汇总，再加权评估的方式，没有考虑到组合服务的业务逻辑关系（服务组合模式）。在本节的全局策略中，将充分考虑服务组合方式对服务组合可信性的影响，为可信web服务组合评估提供一种更可信的全局策略。首先，介绍基本的服务组合模式；接着，分析不同模式的影响；最后，给出考虑全局的调整方法。服务组合流程可以被定义为一组相互关系的任务（或业务），这些任务具有各种不同的功能，并通过原子服务完成。在常见的服务组合应用中，原子web服务通过一定的组合模式构成服务组合。研究者提供了多种原子web服务组合模式，提WS4BPEL支持多种组合模式。但实质上都可以分解为顺序模式、分支模式、并行模式和循环模式的有限递归嵌套，因此本文仅讨论这4中模式。1）顺序模式相当于程序结构中的顺序结构，服务组合中的服务根据业务被分解为多个阶段。每个服务按顺序依次完成其业务功能。2）分支结构相当于程序结构中的分支结构，多个分支中根据一定的判断条件选择一条分支执行。在计算该模式下的属性值时，由于无法判断具体运行那条，一般采用统计方式估算，即根据可能执行的概率计算平均值。3）并行模式相当于程序结构中的并行结构，多条分支同时进行。一般用于为下一阶段的业务准备多个初始条件。这些任务之间相互独立，全部完成后，才能进入下一阶段。4）循环模式相当于程序结构中的循环结构，一条路径被重复循环地执行次。可以看作顺序模式的一个复合结构，即把这条路径展开Z次执行。在进行可信评估时，需要考虑执行的次数。由上面四种结构组合出来的服务组合网络有多种形式，如何从中识别出关键的路线成了研究的关键步骤；关键路径：服务组合业务流程中执行时间最长的那一条路径。关键路径上的业务称为关键任务，其他任务称为非关键任务。其中关键路径的识别问题类似求解最短路径问题（目标函数转化为最大），可采用E.W.Dijkstra提出的T、P标号算法或L.R.Ford提出的Ford算法。2．基于全局的个性化web服务组合可信评估模型2.1构建评价模型步骤目前大部分关于服务组合评估的研究中，基本都是采用的全局一致化的评第4页共11页估模型。即在服务组合中，每个原子服务釆用相同的评估属性项及权重，然后根据每个原子服务的属性评估值计算出服务组合全局的各属性评估值，最后结合权重得到服务组合的综合评估值。虽然这种评估方法取得了一定的成果，但是每个原子服务的类型存在差异，其处在的领域不同，根据前面分析，显然，其评估属性及其权重是不一致的。所以，这种全局一致化的评估模型很难得到可信的评估值本文提出全局个性化的可信评估模型在原子服务个性化的评估模型基础上合成服务组合的评估模型。其构建步骤如下：步骤1：构建服务组合中原子web服务的个性化评估模型：步骤1.1：识别服务组合中各原子web服务的类型；步骤1.2：根据类型构建基于领域的评估模型（算法2。1WSTAM）。步骤2：构建好个性化的评估模型后，需根据原子web服务在服务组合中的位置（关键路径、非关键路径），动态地调整其评估模型：步骤2.1：识别非关键任务；步骤2.2：对并行路径非关键任务上的web服务评估模型进行调整。2.2确定原子web服务权重不同的用户对服务组合中不同的原子服务的关注程度是不同的。如，在网上购物流程中，用户对选择商品、网上支付、提交评价信息这三个原子服务，更多地关注前两个原子服务的可信性，对提交评价信息这个服务的关注较少。虑到用户对每个原子服务的关注度是定性的，采用先排序后比较相邻关注度的方法，将用户的定性关注度转化为定量的权重值。具体步骤如下：步骤1：将服务组合中所有的原子服务组成集合…，步骤2：用户根据个人对服务组合中原子服务关注程度的高低进行降序排序，获得降序序列(1)(2)(3)()nssss其中，可以通过不断地从剩余的原子服务中选择出最重要的一个原子服务来完成排序。步骤3：用户设定序列(1)(2)(3)()nssss中，相邻两个原子服务()is与(+1)is的相对关注度。步骤4：根据用户给出的相对关注度等级，获得相对权重(1)(2)(1)[,,]nrrr其中()ir是两个原子服务的绝对权重之比。又因为：()(1)()(1)(2)()1()()()(1)iiiiinnaaakiinaaakirrrr其中：()i11nia，()()()111111()()()()111(1)innnnnnakinanaaiiikiraa则有：11()11()(1)nnkikinra（4.1）1()()()ninkkiaar（4.2）按公式4-1和4-2计算得到用户对每个原子服务的用户关注度权重，即每个原第5页共11页子服务对整个服务组合可信评估重要程度权重。121[,,],1nniiAaaaa（4.3）计算服务组合可信评估值，需要的信息包括各原子web服务的可信属性及属性权重值，各原子web服务相对服务组合的权重，各属性的评估值。在计算web服务组合评估值时还需考虑其执行的概率ip，和次数il，因此服务组合评估值的计算公式如下：11niiiiiniiiipLaDpLaD（4.4）其中，ia，iD分别表示第i个原子web服务的权重和可信评估值，D是整个服务组合的可信评估值3.动态规划在服务组合可信评价方案中的应用对web服务进行可信评估的目的是为了在大量满足功能需求的web服务中选择出最可信的web服务组合。根据web服务组合的状态，其应用可分为两类：1）对已有的web服务组合进行评估，选择最优的web服务组合；2）选择最优的原子web服务组合成可信的web服务组合。下面将从这两方面分析其应用。3.1web服务组合的选择对多个已经组合好的web服务组合，我们只需按其组合模式分解成多个原子web服务，再釆用第2节中的方法，获得每个web服务组合的可信评估值。排序选择评估值最大的web服务组合即可，选择出的服务组合可信性最好。具体的操作，上文中已详述，此处不再重复。3.2原子web服务的最优组合根据本文提出的评估方法，原子web服务最优组合问题，可转化为了一个动态规划问题。即将最优组合问题转化为多阶段决策问题，随着时间的推移，在每一阶段上做出最恰当的决策，以实现web服务组合的可信性全局最优。同时每阶段需根据服务组合的模式及客观执行时间动态调整原子web服务的评估模型。选择出的最优组合满足功能需求，且可信性最优。动态规划包括以下几个基本概念：1）阶段：把所给的问题恰当地分为若干个相互联系的阶段，阶段的划分一般是根据时间和空间的自然特征来划分。描述阶段的变量称为阶段变量，可用k表示。如，在本文的最优组合中可按执行先后的顺序将每个原子web服务分成一个阶段。2）状态：状态表示每个阶段始所处自然状态或客观条件，它描述了研究问题过程中的状况，又称不可控因素。描述过程状态的变量称为状态变量，可用kZ表示第k阶段的状态变量。状态变量应具有无后效性，即如果某阶段的状第6页共11页态给定后，则以后过程的发展仅仅取决于这一时刻的状态，而与这一时刻以前的状态和决策无关。如，在本文中非并行路径上的每个原子web服务的服务实例可作为状态变量。3）决策：决策表示当过程处于某一阶段的某一状态时，所做出的不同的决定或选择。描述决策的变量称为决策变量，可用()kkcz表示决策变量，()kkcz表示每个阶段的允许决策集合。如，在本文中，每个阶段选择一个原子web服务实例为一个决策。4）策略：从起点到终点的全过程中，每个阶段都有一个决策，由这一系列决策所构成的行为方案称为全过程的一个策略。可记为：11122{(),(),(),}nnPczczcz，n在本文中，每一种web服务组合作为做一个策略。5）状态转移方程：状态转移方程是确定过程由一个状态转移到另一个状态的演变过程。即1kZ的值随着在,kkzc的变化而变化，这种确定的对应关系，记为1=(,)kkkkZTzc，它描述了由k阶段到k+1阶段的状态转移规律，称为状态转移方程式，kT称为状态转移函数。