基于遗传模拟退火算法的QoS约束的Web服务选择研究

【摘要】为了提高 Web服务组合流程中服务选择技术的收敛性能，提出了一种基于遗传算法与模拟退火算法相融合的多目标优化策略，用于解决基于QoS的Web服务组合问题。为了使模拟退火算法更好的与遗传算法相结合，充分利用遗传算法的算子操作步骤和种群适应度值的进化趋势，本文重新设计了产生器、接受准则和控制参数。仿真实验结果表明，该改进算法能在较少的进化代数下得到最优路径，提高了Web服务组合的快速全局搜索能力。

【关键词】Web服务组合;模拟退火算法;遗传算法;QoS;全局最优

1.引言

Web服务组合问题属于NP难问题，传统典型的解决主要采用穷举算法和贪婪算法。当前较流行的Web服务选择算法主要是采用基于启发式的选择算法，如遗传算法、粒子群优化算法和蚁群优化算法等。这些方法都存在如收敛性能较差以及搜索全局最优解的能力不强等问题。文章在现有研究的基础上提出了一种基于遗传算法与模拟退火算法相融合的Web服务组合算法。

2.Web 服务组合模型的基本概念

抽象服务（Abstract Service，简称AS）。抽象服务是构成服务组合流程模型的基本逻辑单元。

具体服务（Concrete Service，简称CS）。在Web服务组合模型中，它是一个具有特定功能的真实的服务。

服务候选集（Service Candidate Set，简称C）。服务候选集是指由不同服务提供者提供的具有相同调用接口以及能够实现相同功能的一组服务，同一服务群中服务具有相同的功能，所不同的是各个服务的QoS属性。

3.遗传模拟退火选择算法

3.1 遗传模拟退火算法基本思想

仔细分析遗传算法和模拟退火算法的基本原理可以发现：遗传算法和模拟退火算法各自都有很多的优点，但也存在着很多不足之处，两种优化算法有很强的互补性。

为了克服遗传算法和模拟退火算法各自的缺点，发挥它们的优势，本文结合改进的遗传算法，将新的编码、交叉和变异操作策略引入算法中，并结合模拟退火算法，形成一种新的遗传退火混合算法（Genetic-Annealing Algorithm，GAA），以期望在提高全局最优解精度的同时解决全局搜索速度问题。

下面将详细介绍混合遗传模拟退火算法的改进策略。

3.2 遗传模拟退火算法的改进策略

（1）目标函数以及适应度函数的设计

设有P个属性为负含义（即数值越大，QoS越不好，如时长、价格等），m-P个属性为正含义（即数值越大，QoS越好，如有效性、声誉等），根据以上分析结果，可得出群体中第i个个体的目标函数fi（g）的计算公式：

其中，j表示第j个QoS属性，wj为相应QoS属性的权值，表示用户对不同QoS属性的关注程度，此权值从用户请求信息中获取。wj∈[o，1]，;为个体中所有Web服务的第j项QoS属性值的和，为所有个体的的最大值，为所有个体的最小值。

（2）种群多样性度量

设第t代的种群由构成，适应度分别为，个体的平均适应度为，最大适应度，最小适应度，种群适应度方差D种群适应度方差，从第一代群体到第t代群体为止的最大适应度方差为。

定义：，则指标Q可以用来表征第t代种群的多样性。Q越大，表明种群的多样性程度越高。

（3）个体交叉策略

本文采用一种基于适应度以及多样性的自适应交叉概率。第t待种群的适应度函数平均值计算公式为：

最优个体的适应度值，所有大于的个体适应度值再求平均得到，令，当&增大时，种群有早熟趋势。为防止因早熟得不到全局最优解而将计为&的函数：

其中，为大于零的常数，可根据实际情况确定。

（4）个体变异策略

本文提出了一种基于适应度的自适应交叉概率：

其中，为大于零的常数，可根据实际情况确定，其余变量均与中相同。

（5）个体选择策略

首先计算出群体中所有个体的适应度的总和，其次计算出每个个体的相对适应度的大小，它即为各个个体被遗传到下一代群体中的概率，最后则使用模拟赌盘操作（即随机产生0到1之间的随机数）来确定各个个体被选中的次数。设群体大小为N，个体i的适应度为，则个体i被选中的概率为：

由公式可见，适应度越高的个体被选中的概率也越大;反之，适应度越低的个体被选中的概率也越小。

3.3 遗传模拟退火算法的执行流程

首先通过遗传算法的进化操作（侧重全局搜索）产生出较优良的一个群体，再利用模拟退火算法的退火操作（侧重局部搜索）来对个体进行进一步的优化调整。运行过程反复迭代，直到满足某个终止条件为止。其实现流程如图1所示：

图1

表1

4.仿真实验与结果分析

基本遗传算法和改进的混合算法所采用的初始化参数如表1所示：

根据表1以上的测试数据，下面分别运行两种算法，并从运行时间和收敛性两方面分析测试结果。

（1）运行时间对比分析

基本遗传算法和改进遗传算法的平均运行时间对比图如图2所示。

图2

从表图综合可以看出，本文所提出的改进遗传算法大大增强了局部收敛速度，使得算法整体在收敛速度方面有比较好的提高。

（2）收敛性对比及分析

基本遗传算法和改进遗传算法的平均适应度值对比图。

图3

由图3可看出，当组合服务中的任务数较多时，改进的遗传模拟退火算法可以得到明显优于基本遗传算法的解。

5.结语

本文尝试使用遗传算法和模拟退火算法融合来求解组合服务问题，遗传算法和模拟退火算法作为新兴的模拟进化算法有它们各自的优点，在空间复杂度上与传统的算法相比具有较大的优越性，把它们结合起来运用在组合服务中，使求解过程中尽量避免了陷入局部最优同时提高了组合服务流程的执行效率，具有一定的理论参考价值和实际意义，我们的下一步工作是进一步完善该在组合服务中的实际应用，来达到用户对组合服务的需求。

参考文献

[1]顾宁，刘家茂，柴晓路.WebServices原理与研发实践[M].机械工业出版社，2006.1，ISBN7.1.17461.5.

[2]Zhang Liang-Jie，Li Bing，Chao Tian，et a1.On demand Web services-based business process composition.IEEE，2003，4057-4064.

[3]CanforaG，PentaMDi，Esposito R，eta1.Alightweight approach for QoS-aware service composition.ICSOC，2004.

[4]Yasuhiro TSUJIMURA Mitsuo GEN.Entropy-based genetical gorithmforsolvingTSEThe Second International Conference onKnowledge-based Intelligent ElectronicSystems，1998，285-290.

[5]SrinivasM，PatnaikLM.Genetic algorithm：asurvey.IEEE，1994，17-26.

作者简介：杨正茂，男，硕士研究生。