基于遗传算法考虑服务质量的服务组合方式的研究

王雯雯

（中国石油大学胜利学院，山东 东营 257000）

基于遗传算法考虑服务质量的服务组合方式的研究

王雯雯

（中国石油大学胜利学院，山东 东营 257000）

随着云计算的发展，服务越来越多地出现在我们的生活中，服务的粒度也根据企业的具体工作流程或侧重点发生了变化。单一的服务往往关注的是一个功能单元，而不足以支撑用户的工作流程，其多样性及广泛性使得服务组合的概念应运而生。在这里我们结合软件质量的知识以及遗传算法的使用，来介绍考虑服务质量的服务组合。

服务组合；遗传算法；服务质量

1 服务组合问题引入

云计算近几年来愈来愈多地出现在个人或企业资源使用的优化名单上，而越来越多的企业也乐于将自己的业务功能或者工作流程打包成符合云计算相关标准的Web服务在云上进行发布，这样无疑可以拓宽客户群体，实现业务增值。那么对用户来说就面临这样一个问题：单一服务不足以支撑使用需求时，如何选择、组合已达到最优利用。

1.1 服务组合方法研究现状

对于服务组合这个问题，许多学者都进行了大量的研究，提出了相应的技术或系统，其分类方式也具有不同的标准，可根据服务组合的实现方式划分为：编制和编排两种，其区别主要是是否依赖于总控协调；根据服务组合的动态程度划分为：动态和静态服务组合；还有依据自动化程度进行划分等等。其中讨论最多的是依据方法论的角度进行划分：工作流程、软件开发过程、软件质量。在此论文中，主要讨论以软件质量为出发点，考虑服务质量的服务组合方式。

1.2 考虑服务质量的服务组合的过程

云计算的流行使软件开发过程发生了重大改变。面向服务的软件工程描述了一种对基于组件的软件工程的自然解决方法，基于组件的软件工程中，一个组件综合者寻找可复用的软件，并利用一些粘合代码，将它们组合成一个新的系统。而在云中，无须通过开发应用程序整合服务，服务接口都是公开的，可分为服务发现和服务调用两部分。而作为面向服务系统的最大的承诺即后期绑定技术的应用，在一个工作流程中给定的功能需求在这里我们称为抽象服务，其可能由一系列的服务来实现，在这里我们称这一系列的服务为具体服务。

对应着同一个抽象服务的所有的具体服务都是在功能上等价的即其可以互相替代，而对于组合来说我们就是要对这些等价的具体服务根据一些非功能的属性进行选择，这些非功能的属性即为服务质量属性。例如，我们可以选择最便宜的属性、最快的属性或者两者兼顾。服务质量被定义为一组属性包括：价格、响应时间、有效性、名声等等，它还可以拥有一些领域特定的服务质量属性。当然，在选择过程中，用户可以指定某一属性值的限制约束，如价格不可以高于某一指定值，这也有可能影响最终的选择。而服务的提供商也可以评估Qos属性值的范围作为与潜在的用户建立合同的一部分。

对于考虑服务质量的服务组合来说，速度是十分重要的，特别是对于互操作系统，客户一般不能接受较长时间的拖延，例如：一个订票系统，用户不会希望为了要从候选的服务中选择提供最低价的预订系统而等待较长的时间。在一个快速的组合中，也要求在执行过程中重新服务组合，从服务质量的角度来看，在运行过程中，因为Web服务环境是动态的，这就会导致服务的组合在执行期间发生变化，例如：在后期的某一具体服务选择时，会对前期所选择的服务有一定的牵制作用，所以除了速度外还有一个重要的要求：这一方案是可行的且遵循SLA。

对于上述的服务组合需要解决的问题，利用整数规划无疑是可以解决的，但是在这里我们不得不假设约束和目标函数都是线性的。在整数规划方法中对服务质量的考虑主要集中在花费、响应时间、有效性、可靠性等，而且这一类的模型声称可以对一些更加一般的约束属性做出处理，如服务依存关系、用户的喜好等等，但是这些优化的方法没有给出；在这里建议使用遗传算法，遗传算法比整数规划方法慢，但是其描述了更多可改变的选择，更加适合操作一般的服务质量属性。当然我们可以采用非线性的规划方法，但是其可用工具的成熟度不高，而且无法验证其结果的准确性。还有一种基于人工智能的约束处理方法叫做约束逻辑编程，这种方法有一个优势就是它具有丰富的建模能力，其特点是约束传播，即用约束来定义变量的允许子域，并且递归地运用此方法，显然这一方法可以得到一个有效的组合，但是其价格昂贵。在下文将陈述基于遗传算法考虑服务质量的服务组合的具体方法、这种方法的优势及不足。

2 基于遗传算法考虑服务质量的服务组合方法陈述

如上文所述，本文旨在提出一种基于遗传算法的、可以快速地为一组抽象服务决定其具体的服务集合。此服务集合必须符合以下规则：

（1）满足服务水平协议中的服务质量约束。

（2）对其它的服务质量参数有一定的优化作用。

在这里我们要考虑的是一个由n个抽象服务组成的组合服务S，S={s1,s2,……sn}。而其具体的结构由一些工作流的描述语言给出，每一个成员Si又与m个具体服务相对应CSi.1，……CSi.m，其中这m个具体服务在功能上是等价的。

在描述使用遗传算法解决、优化问题之前，我们需要描述如何计算组合服务的服务质量。

2.1 组合服务的服务质量计算

首先，在这里我们所考虑的是基于工作流程的组合服务的服务质量，那么我们就要对工作流程中的不同情况进行不同的考虑：switch结构（选择），每一个case选择语句都标注着其被选择的可能性（概率），例如，一个包含着switch的工作流，其中switch结构中有两个选择，其花费分别为C1，C2，其概率分别为P及1-P，则全部的成本可由下式计算：PC1+(1-P)C2。显然，概率的初始化是由工作流的设计者完成的，其更新取决于工作流在执行过程中监测所得的信息。Loop结构（循环）由其循环次数k标注，如果循环的代价是C，那么此循环的预测成本为：kC；这样定义循环结构的优势在于：它允许在不展开循环的前提下，对工作流的质量进行快速计算；对循环结构的服务质量的评估与对其循环次数的评估相关联。Fork结构（分叉）中除时间属性的聚合函数为并行任务中的最大耗时外，其它属性的聚集函数与顺序结构一致。不同结构的不同服务质量聚集函数可由表1给出：

表1 各结构对应质量属性的聚集函数

上表中给出了不同的结构针对不同的软件质量属性所对应的聚集函数，亦可以由此得出基于遗传算法进行服务组合的优势：这些聚集函数不可能要求其全部为线性的，尤其是由用户指定的聚集函数。

2.2 基于遗传算法的解决方案

遗传算法并不强制其服务质量的属性成分必须是线性的（目标函数和约束），这就使得我们可以对所有的可能的服务质量属性（包括自定义的属性）使用此方法，而无须将其线性化。

要使用遗传算法首先要确定基本的组成元素：

基因：组成染色体的单元。

染色体或者个体：表示待求解问题的一个可能解。

群体：由一定量的染色体组成是遗传算法的搜索空间。

适应度：个体所对应解的好坏，通常由某个适应度函数表示。

根据遗传算法的知识，要想使用遗传算法来解决我们的问题，首先要将这个问题编制为一个适当的基因组也就是染色体。在我们的例子中，基因组被描述为一个整数序列，其中数组的项数等于组成这一组合服务的完全分开的抽象服务的个数。每一项都有一个索引，这一索引对应着一个数列，此数列表示的是该抽象服务对应的具体服务组，其结构如图1所示：

图1 基因组结构

遗传算法的基本运算包括选择、交换和突变，起初随机选择服务组合方式，也就是随机选择一些个体，充分体现“适者生存，优胜劣汰”的进化原则，所谓优劣通过适应度函数来进行计算，服务组合适应度函数的建模将在下文中给出，根据适应度排序并产生下一代，这个过程通过选择和繁殖（交换和突变）完成，在这里就涉及到交叉算子和变异算子的概念，结合服务组合问题给出两种算子的含义：交叉算子是标准的二点交叉，而变异算子是随机选择一个抽象服务（即基因组中的位置）并用另一个有效的具体服务随机替换与此抽象服务对应的具体服务。显然，在遗传算法的执行过程中，一个抽象服务只与一个具体服务对应。周而复始，直到满足终止条件。常见的终止条件有进化的次数、资源限制、适应度饱和等等，在本文中依据服务组合这个具体问题的实际需求，给出的终止条件与约束条件有关。

下面我们就可以对适应度函数及一些约束进行建模，适应度函数需要使某一些服务质量属性（如：可靠性）增至最大，而使某一些减至最小（如：代价），当使用到我们上文所提到的特定领域的服务质量属性时，其具体的适应度函数由工作流的设计者给出。

此外，适应函数必须分别对那些违反约束但是可以推动得出符合约束的演变的情况作出惩罚，我们假设一个组合服务服务质量有如下一系列的约束：其中，g为一个基因组即一个个体，也就是一个服务组合；此服务组合中共有n个服务；cl表示每种服务的约束函数，当此个体在某一服务约束函数大于0时则说明其违反了约束也就是针对每一个服务的y取值会为1，这样也就是所谓的惩罚；D函数计算一个个体（服务组合）服务约束距离之和。

我们定义约束满足的距离为：

那么其适应度函数可定义为：

在此公式中，服务质量因子的大小控制在[0,1]之间，w1,w2,w3,w4,w5是不同的适应度函数中真实确定的权重，w1,w2,w3,w4暗示了特定的服务质量因子对适应性函数的贡献，其中Cost()为花费、Response Time()为响应时间、Availability()为可用性、Reliability()为可靠性，这些都是常用的软件质量评价属性，w5代表了惩罚因子的权重。

最后，我们定义此遗传算法的结束标准，一种可行的方法是固定最大的遗传代数(maxgenconstr)，除此之外以下两种方法也可以：

（1）执行，直到约束全部满足D(g)=0；如果在最大代数里没有遇到这种情况，则说明这一问题无解；

（2）一旦D(g)=0，记录此时遗传代数为maxgenfitness这可能是maxgenconstr的一个百分数，这一代可作为选择，继续执行遗传算法，直到个体的适应度函数不随遗传代数的增加而改变。

2.3 动态的适应函数

在上文中的适应函数包含了对个体违反约束的静态处理，也就是说在每一代中的惩罚都是一样的，若惩罚因子的权重w5很高就会存在这样的风险：在此解决方案中可能违反了某一个约束但其已十分接近完美的解决方案，它有可能会被舍弃。其解决方法就是采用动态的惩罚：

其中gen是指现在所处的代数，maxgen是遗传算法中规定的最大代数。

2.4 基于遗传算法的优缺点

在解决考虑质量的服务组合问题时，使用最多的方法是整数规划，其与遗传算法相比有如下的优缺点：在整数规划中，其服务质量属性的聚合函数必须是线性的，对于一些标准的属性我们可以对其聚合函数使用线性化，但有些特殊的属性其线性化就很困难（例如：分叉结构中其响应时间聚合函数的线性化），而用户自定义的质量属性其聚合函数线性化无法把握。当然，我们可以选择使用非线性整数规划，但其可预测性很差。

换句话说，线性规划的方法要比遗传算法方法速度快，当工作流程数目和具体服务数目有限且无须使用非线性聚合函数时，整数规划方法更加合适。当对于每一个抽象服务都有大量的具体服务可供选择时，应选用遗传算法。

3 结论

在这里我们详述了一种解决考虑服务质量的服务组合的方法，此方法是基于遗传算法的。即寻找一组满足约束且对于每一个服务质量因子最优化的具体服务，这些具体服务和与其对应的抽象服务绑定。与整数规划这一常用方法相比，遗传算法中其服务质量属性的聚合函数可为非线性的，且当具体服务数目增加时，遗传算法的性能可保持。

[1]邓水光，吴朝晖．Web服务组合方法综述[J]．中国科技论文在线，2008，3(02)：79-84．

[2]许广宇．Web服务组合研究与实现[D]．北京：北京邮电大学，2009．

[3]曹洪江．基于用户需求的Web服务组合系统研究[D]．武汉：武汉理工大学，2010．

Research on Service Composition Based on GeneticAlgorithm in Consideration of Service Quality

Wang Wenwen
(Shengli College,China University of Petroleum,Dongying 257000,Shandong)

With the development of cloud computing,more and more services appear in our life,the service granularity also changes according to the specific procedures or the emphasis in enterprises.Single service tends to pay attention to a functional unit,which is not enough to support the user's work flow,so the concept of service composition arise according to the diversity and universality of service.This paper combines the knowledge of software quality and the usage of genetic algorithms,and introduces service composition considering service quality.

service composition;genetic algorithm;service quality

TP393.09

A

1008-6609(2017)08-0048-03

作者介绍：王雯雯（1986-），女，山东东营人，硕士，助教，研究方向为软件工程。