主客观权重遗传算法在服务选择中的研究

吴明礼，魏瑞珍

(北方工业大学 信息学院，北京 100144)

0 引 言

目前，网络上的Web服务越来越多，但是功能都比较单一，已经无法满足复杂应用的需求，需要通过一定的技术将这些Web服务组合起来，形成功能强大的服务[1]。Web服务组合的前提是服务选择，随着Web服务数量的不断增多，服务选择问题变得越来越复杂，如何从海量的候选服务中，选出开发人员满意的服务，成了Web服务选择领域的研究热点[2]。

Web服务的选择重点是找到既满足功能需求又满足非功能需求(服务质量)的服务[2]。而在基于服务质量的Web服务选择研究方面，选择结果的满意度和算法的求解受到广泛关注。但是，在满意度方面，以往都将开发人员的需求直接转化为权重，而忽略了服务的客观性能；在算法的求解方面，以往使用的智能算法如粒子群算法[3]、多目标蚁群算法[4]、人工蜂群算法[5]等虽然取得了一定的效果，但是，在面对大规模的Web服务选择问题时，仍然存在收敛性方面的不足，遗传算法[6,7]在研究中被认为更适合[8]。本文中，结合Web服务选择和遗传算法的特点，对遗传算法中的编码，适用度函数中的权重，交叉和变异都做了一定的改进，使改进后的遗传算法在结果满意度方面和算法收敛性方面都有一定的提升。

1 基于QoS的Web服务选择的研究现状

基于服务质量的Web服务选择问题，属于组合优化问题。是NP难问题。很多学者针对这个问题提出了各种解决方法。在对基于服务质量的Web服务选择求解时，传统的方法有穷举法和贪婪算法。但是这种算法都只适用于候选服务个数少的情况。目前，Web服务的数量不断增长，这些算法难以达到较好的求解速度，因此，学者们提出了各种启发式的智能算法，来应对目前的形势。

在使用遗传算法求解时，收敛速度慢，易陷入局部最优解。针对这些问题，鲁城华等[9]采用多属性多决策方法，对多个QoS属性同时处理，将问题转化为多目标优化问题，为了提高计算效率，提出基于ε支配的多目标遗传算法。徐甜等[8]针对使用遗传算法求解Web服务优化组合的问题，提出将多尺度交叉算子和信息共享因子引入遗传算法，提高了问题的求解速度。吴青林等[10]提出在求解动态Web服务组合时，将罚函数的概念引入遗传算法，并且动态调整变权因子，交叉因子和变异因子，实现了在较短时间内找到符合用户需求的服务。谭文安等[11]针对Web服务组合中的服务质量感知问题，提出了一种基于混沌遗传算法的Web服务组合方法。通过对每次进化后的子代群体附加混沌小扰动有效克服了遗传算法早熟和收敛速度慢的问题。叶恒舟等[12]在提出的遗传算法中，先使用Top-k选择方法，从每个抽象服务组中筛选出若干候选服务，有效减少了解空间，然后再使用遗传算法进行求解。

上述改进的遗传算法求解Web服务的选择问题时，都只关注算法本身的收敛性和求解效率，而忽略了Web服务自身的一些特殊性质。

(1)在使用遗传算法编码时，大多采用二进制编码方式，如谭文安等[11]在编码时，选中Web服务设为1，未选中设为0，当Web服务过多时，存在编码长度过长的问题。

(2)在计算遗传算法适应度函数值时，由于Web服务的QoS属性有多个，每个属性权重的赋值都很重要，不同的权重会产生不同的结果，但是大部分的研究只是简单考虑开发人员的偏好，如徐甜等[8]在使用遗传算法求解时，直接将开发人员的偏好设置为权重，如果开发人员设置的权重不恰当，就会给选择带来误差，这种情况要求系统有一定的纠正能力。

针对这些问题，本文对Web服务的QoS属性的权重进行分析，提出了一种基于主客观权重的遗传算法，并且对遗传算法的编码，选择，交叉，变异进行了改进，使算法更加适用于Web服务的选择问题，有效提高了算法的收敛性。

2 基于改进遗传算法的QoS的Web服务选择

2.1 标准遗传算法的流程

遗传算法(genetic algorithm)是一种全局的搜索算法，搜索过程不需要知道问题的内在性质。借鉴了生物界的适者生存，优胜劣汰的进化规律。由美国J.Holland教授在1975年首次提出。遗传算法首先要进行基因编码，从一个初始种群开始，经过遗传，交叉，变异，逐渐产生出满足要求的个体。遗传算法的工作流程如图1所示。

图1 标准遗传算法流程

2.2 Web服务选择模型的建立

2.2.1 Web服务的选择模型

在Web服务的工作流模型中，主要的组合结构有顺序，循环，选择和并行结构[13]。组合结构如图2所示。

图2 Web服务组合结构

由于顺序结构的组合模型，是组合模型中最基础也是最重要的模型，其它模型都可以转化为顺序模型，所以这篇文章中，只研究基于顺序结构的组合模型。

对于每个Web服务，都有若干个QoS属性，我们先对Web服务的QoS属性做一些介绍。本文中，Web服务的QoS属性主要选取响应时间，价格，可用性和信誉。响应时间(t)：介于发送请求和收到响应的时间间隔；可用性(v)：指服务成功执行的次数与总执行次数的比值；价格(p)：是调用一次服务的费用；信誉(r)：主要取决于调用者使用服务的体验，可以被定义为用户对服务的评价的得分。

在顺序结构的组合模型中，一个工作流可以被描述为：工作流中有n个抽象的服务，每个抽象服务表示为Fi， 有i到j个功能相似的服务可提供给用户，表示为Fij， 每个服务有k个QoS属性，表示为qk， 每组抽象服务中有且仅有1个服务被选中，最终的组合服务表示为WS， 求最优的组合方式。如图3所示。

图3 服务组合 注：上图是一个顺序结构的工作流模型下的服务组合 示意图，方框表示抽象服务，方框内的图案 表示功能相同，非功能属性不同的服务。

该模型可用数学公式描述为

(1)

其中， minFi=min{F11,F12,F13…F1m}， 同时

(2)

这是一个多目标组合优化问题，本文采用线性加权的方式将它转化为单目标优化问题，转化后为

(3)

在Web服务选择中，Web服务属性的权重非常关键，影响着最终的选择结果。需要对权重进行详细的分析，使得结果更加准确和满意。

2.2.2 Web服务选择中主客观权重分析

开发人员在选择服务时，往往需要按照自己的需求去选择，但是如果只按照开发人员需求选择时，往往会忽略服务潜在的性能。马友等[14]提出了一种自适应主客观权重的度量算法，很好解决了这个问题，本文把这一概念引用到Web服务选择中。

开发人员在选择Web服务时，针对应用领域的不同，对QoS属性的侧重可能有不同的要求，有的希望响应时间尽量短，有的希望服务的价格尽量低，不同的需求就会有不同的权重，这类按照开发人员的需求转化而来的权重，称为Web服务选择中的主观权重。

主观权重可以由用户直接指定，也可以通过自适应法，专家评分法，层次分析法等来确定。这里设主观权重为ws， 以供后文使用。

但是，当开发人员在给定主观权重时，往往会因为不了解情况而给出不恰当的值，如开发人员需要尽量便宜，但是便宜的那个服务其它性能都非常差，这种情况下，主观权重就需要系统进行纠正，以此来调整选出的结果。例如：对于服务A、B，当属性q1、q2的权重分别为0.6、0.4(情况a)时，A服务比B服务好，当权重调整为0.3、0.7(情况b)时，B服务比A服务好。比较结果见表1。

表1 权重对服务选择结果的影响比较

这里把系统给属性赋予的权重定义为客观权重。客观权重反应了服务的潜在性能和规律，对于一组服务，如果其中某一属性的值相差不大，那么这个属性的参考价值就不大，客观权重就小。客观权重是对服务的区分能力的体现。

客观权重的计算公式定义为

(4)

dis(qi)=|qi|/|S|

(5)

其中，qi表示第i个属性，dis(qi) 表示属性对服务的区分能力， |S| 表示服务的个数， |qi| 表示属性qi划分服务的个数。如某一抽象服务的价格属性值为2,3,4,5,5，则 |S|=5， |qi|=4。

在计算Web服务属性的权重时，首先确定开发人员的主观权重，然后再使用可以保证服务潜在性能的客观权重计算方法，求出客观权重，最后使用效用函数计算最终权值。最终权重的计算公式为

w=αws+(1-α)wo

(6)

2.3 基于改进遗传算法的Web服务选择模型求解

在分析完基于QoS的Web服务选择模型和Web服务选择中的权重后，就需要对模型进行求解。这里采用基于主客观权重的遗传算法，即在Web服务选择的适用度函数的计算中，权重的计算采用主客观相结合的方式。

2.3.1 数据预处理

在度量Web服务的QoS属性时，首先需要将不同单位不同方向的QoS属性化为[0,1]区间中的值。越大越好的QoS属性，称为正属性，如信誉度。越小越好的QoS属性，称为负属性，如价格。在使用遗传算法进行求解时，首先要进行数据的归一化处理，本文采用下面的常用公式进行归一化的处理,处理完成后，所有属性都是越大越好

(7)

(8)

2.3.2 编码

在Web服务选择中，功能相同的服务被认为是一类抽象服务，即每类抽象服务由个数不等的功能相同而服务质量不同的具体服务组成。以往的二进制编码方式很难准确的描述，而且如果功能相同的服务个数很多，二进制编码串会很长，不能很好反应Web服务选择的特定环境。所以，这里采用键值对整数编码方式，即Key-Value 编码，先对抽象服务的编号为Key，抽象服务中的具体服务的编号为Value。这种编码方式，逻辑清晰，可以很容易对应到服务选择的模型中，且易于代码实现；简化了后面计算适应度函数时个体的解码过程。编码如图4所示。

图4 编码

其中，k1到kn表示抽象服务编码，v1到vn为具体服务编号，v1到vn的最小值可取0，最大值为所属抽象服务所包含的具体服务的个数减1，以此类推。

2.3.3 初始化种群

随机的生成初始化种群，在生成初始化种群时，对于不符合约束条件的个体直接进行淘汰。保证最终种群的个体都是有效的个体。

2.3.4 群体的适应度函数

因为在以往计算群体的适应度函数时，只是简单的使用权重与综合值相乘再相加的模式，这种模式只注重了开发人员的主观权重，而忽略了服务的客观权重，造成服务选择的片面性，这里采用综合考虑主客观权重的方式，既考虑开发人员的需求问题，同时又注重服务的客观性，使最后的选择结果更具有全面性。适用度函数的公式如下

(9)

式中：ti表示Web服务的响应时间，pi表示Web服务的价格，vi表示Web服务的可用性，ri表示Web服务的信誉度。权重wt,wp,wv,wr使用式(6)进行计算。

2.3.5 选择

遗传算法有很多选择策略，如轮盘赌选择，随机遍历抽样法等。在Web服务的选择中，对轮盘赌的方式进行改进，以此来加快算法的收敛速度。

首先，利用公式

(10)

计算出个体的赌盘概率，同时得到个体的平均适用度值。然后，根据个体的赌盘概率和平均适应度，选择个体。最终选择的个体适应度都是在平均适应度之上的个体。

2.3.6 交叉

在Web服务选择中，编码方式采用了键值对编码方式，在交叉操作时，实质上我们仅对两个父类的value值进行交叉，如图5所示。

图5 个体交叉

同时，在对个体进行交叉时，考虑到对于两个相似度高的个体交叉时，产生的父代和子代的差异不大，交叉没有意义。所以这里引用小生境思想，让个体在一定的环境下进化。这里对交叉算子进行改进。具体做法是：首先，计算交叉个体Fi和Fj的距离Sij(即两个个体适应度函数值的差)，如果Sij小于特定的数，那么就不进行交叉，否则交叉。交叉概率的公式为

pc=pc0(1-t/T)-pcmint/T

(11)

其中，pc0为初始交叉概率，pcmin为最小交叉概率，t表示当前迭代次数，T为最终终止次数。当Sij较大时，父代个体的差异较大，进行交叉操作，迭代刚开始时，交叉概率较大，可使群体产生更多新的个体。随着迭代的进行，交叉概率慢慢减小，结果逐渐接近最优解，同时较小的交叉概率也可以一定程度上保护优良的个体，加快算法的收敛速度。

2.3.7 变异

在进化快结束时，种群的个体与最优解相差越来越小。个体的适应度和种群的平均适应度很接近，这时就要注意种群陷入局部最优，需要一个较大的变异概率来变异，这里的变异概率结合集中因子来考虑。如果种群最优值与平均值相差越小，集中因子越小，变异概率越大。

变异概率为

pm=pm0-mt/T

(12)

其中，pm0为初始变异概率，m为集中因子，计算公式为m=(Fmax-Favg)/Fmax。

2.3.8 终止

终止条件为最大迭代次数或选择出的服务满足用户需求时终止。

3 仿真实验

实验使用Java语言编程，JDK为jdk1.7.0_67；使用开发工具Eclipse，操作系统为win7，实验中的Web服务组合模型采用顺序结构的组合模型，数据采用QWS数据集，该数据集包含了全世界2507个Web服务的信息及调用情况，由于数据集中没有提供价格和信誉度属性，所以实验中的价格和信誉度在[0,1]区间内随机生成。将数据集中的数据随机分为8个抽象服务做组合(经计算，当为8组时，组合规模已经相当大，符合实验需求)，每个抽象服务下有n到m个具体服务。实验中选择响应时间，价格，信誉度和可用性作为Web服务QoS的评价指标，实验结果中的数据为归一化后的值。

3.1 实验1

实验使用改进的遗传算法IGA与文献[11]中的CGA遗传算法进行比较。实验结果如图6所示，实验结果表明经过改进的遗传算法，提高了收敛速度，具有很好的适用性。

图6 算法比较结果

3.2 实验2

该实验中，在对Web服务选择进行求解时，使用改进的遗传算法求解，不同之处是实验2.1的适应度函数中的权重直接使用用户的主观权重，实验2.2的适应度函数中的权重为综合考虑主客观权重。结果表明，实验2.2在符合开发人员的需求的同时，还综合考虑了服务的潜在性能，把性能更好的服务提供给开发人员。

3.2.1 实验2.1

实验中主观权重采用直接指定的方式：响应时间0.35、价格0.27、信誉度0.15和可用性0.3，只考虑主观权重时最终选出的组合服务见表2，表中抽象服务i使用符号Fi表示，最后求得的组合服务的综合值为7.057。

表2 主观权重计算结果

3.2.2 实验2.2

实验中综合考虑主客观权重，主观权重与实验2.1相同，客观权重使用式(4)、式(5)计算，综合权重使用式(6)计算，最后得到综合权重值：响应时间0.3、价格0.2、信誉度0.17和可用性0.33。最终选出的组合服务见表3，表中抽象服务i同样也使用符号Fi表示，最后求得的组合服务的综合值为7.117。

表3 主客观权重计算结果

通过比较可以得出：主要区别体现在F2， 综合考虑主客观权重选出的服务166号，虽然响应时间没有18号的服务性能好，但是信誉度和可用性都提升了，总体性能更好。

4 结束语

本文针对目前Web服务选择中属性权重和选择算法收敛问题，设计了一种将主客观权重和改进的遗传算法相结合的方法，对基于QoS的Web服务选择问题进行研究。采用了一种新的键值对编码方式，给解码工作带来了一定的便利，更加适用于Web服务选择的编程与后续操作，在计算个体的适应度值时结合主客观权重进行计算，并引入小生境思想和集中因子，提高算法的收敛速度。最后，采用QWS数据集进行了验证，实验结果表明改进的遗传算法在收敛方面和最终效果上都有良好的表现。