基于改进遗传算法的Web服务优化组合研究

徐　甜　刘凌霞

(安阳师范学院计算中心　河南 安阳 455000)



基于改进遗传算法的Web服务优化组合研究

徐甜刘凌霞

(安阳师范学院计算中心河南 安阳 455000)

摘要为了获得更优的Web服务优化组合方案，提出一种基于改进遗传算法的Web服务优化组合方法。首先将Web服务组合优化方案的可行解看作遗传算法的个体。然后通过遗传算法模拟自然界的生物进化过程，找到Web服务组合的最优解，同时在标准遗传算法引入多尺度交叉算子和信息共享因子，提高问题的求解速度。最后进行仿真对比实验。结果表明，改进遗传算法可以快速、准确找到Web服务组合问题的最优解，为解决Web服务组合问题提出了一种新的解决思路。

关键词Web服务遗传算法服务组合服务质量

0引言

随着互联网和电子商业的迅速发展，Web服务技术市场日益成熟，大量的企业将应用、资源和技术加入到互联网上的Web服务中实现共享，然而单个Web服务功能比较单一，不能满足现代企业多样性的应用需求，这样Web组合服务应运而生[1]。Web组合服务将单个Web服务采用一定的技术组合在一起，产生功能更强大的服务，用户可以按照自己需求选择相应的服务，以创造更多的价值，降低企业成本。但是在互联网上存在大量的Web服务，如果从海量服务中选择客户真正要求的服务，成为当前电子商务研究中的重点，具有十分重要的意义[2]。

针对Web组合服务优化问题，国内外学术界对其开展了大量的研究，已经取得了许多研究进展，文献[3]将Web组合服务优化问题看作一个0-1背包问题，候选服务对应一个物品包，QoS优化目标属性与物品的价值相对应，然后采用分支定界法对包进行选择；文献[4]将Web组合服务优化问题看作为一个有向无环图，这样Web服务问题求解变成了一个多约束的路径选择问题；文献[5]将Web组合服务优化问题映射成为一个覆盖网络，然后采用Dijkstra的最短算法进行求解，这些算法均存在求解速度慢，效率低等缺陷，不能满足Web服务组合优化在线优化要求[6]。近年来，随着智能优化算法研究的不断深入，有学者将它们引入到Web服务组合优化问题求解中。由于它们有并行计算、群体寻优的等特点，十分适合对大规模、复杂的Web服务组合优化问题进行求解。如文献[7]提出基于蚁群算法的Web服务组合优化模型，但是蚁群算法存在易陷入局部最优等缺陷；文献[8]提出基于模拟退火算法的Web服务组合优化模型；文献[9]提出基于粒子群优化算法Web服务组合优化模型；文献[10]提出基于遗传算法Web服务组合优化模型。相对其他算法，它们获得不错的效果，同时大量研究结果表明，遗传算法更适合于大规模的Web服务组合问题求解，具有较明显的优势。但是遗传算法存在一些自身难以克服的缺陷：收敛速度慢、易陷入局部最优等，为此许多学者从不同角度对遗传算法进行了改进，不同程度改善了Web服务组合的解[11,12]。

为了获得更优的Web服务优化组合方案，提出一种基于改进遗传算法的Web服务优化组合方法。首先将Web服务组合优化方案的可行解看作遗传算法的个体。然后通过遗传算法模拟自然界的生物进化过程，找到是Web服务组合的最优解，同时针对遗传算法的不足进行改进，以提高问题求解的速度。最后进行仿真对比实验。

1Web服务组合的数学模型

(1)

(2)

式中，qcom为组合服务的QoS属性；qmax、qmin为组合服务QoS属性值的最大、最小值。

Web服务的QoS属性值及约束值为：

(3)

式中，q1,q2,…,qk为Web服务的QoS属性值，c1,c2,…,ck表示QoS属性对应的约束值。

Web服务优化组合问题的数学模型可以描述为：

Maxf(CSi)f(CSi)=w1×q1+w2×q2+…+ wk×qk

(4)

式中，CSi为第i个Web服务组合方案。

根据式(3)可知，Web服务组合优化问题是指在满足用户要求条件下，找到一个QoS较优的组合服务资源。

对式(3)的组合优化问题，如果采用人工方法进行求解，无法实现。本文利用改进遗传算法对Web服务组合优化问题进行优化，以获得更优的Web服务组合优化方案。

图1　标准遗传算法的工作流程

2改进遗传算法

2.1标准遗传算法

1962年，Holland教授等提出了一种基于概率的随机搜索算法—遗传算法GA。其将问题的潜在的解表示为个体，并采用适应度函数评价个体的优劣，并经过交叉、变异、选择等遗传操作，找到问题的最优解，标准遗传算法的工作流程如图1所示[14]。

2.2遗传算法的改进

大量研究表明，标准遗传算法存在一定的缺陷，如全局搜索能力差、易出现早熟等，这样找到问题解是一个局部最优解，而非全局最优解。为此，本文提出了一种改进遗传算法。通过引入具有引向因子的交叉算子，并且引入信息共享因子，在保证子代个体向最佳个体靠近的同时，防止早熟收敛现象发生，改善了解的质量，最后利用反向搜索找到问题的全局解。

2.2.1自适应交叉操作

标准遗传算法的交叉算子缺乏方向性，收敛速度慢、搜索效率低。为此，在交叉算子基础上，改进遗传算法采用最佳个体替代其中一个交叉个体，并引入了引向因子，使个体搜索有了方向性，加快了收敛速度。同时，引入粒子群算法的群体间信息共享机制，保证个体搜索方向朝着群体最优方向进行，不易出现局部收敛现象，克服出现局部最优解难题。

(5)

(6)

式中，γ,β∈[0,1]的随机数。

交叉概率使用自适应交叉概率，即：

(7)

式中，Pc1、Pc2分别为最大和最小交叉概率；fmax、favg分别为种群中最大和平均个体适应度；f为种群中个体适应度。

2.2.2自适应变异操作

(8)

式中，μ的值随着进化代数t的增加逐渐减小。

构建如下关系：

(9)

式中，T为最大进化代数。

根据式(9)可知，在种群进化初期，r值较小，此时变异尺度较大，加快全局搜索的速度；在进化后期，r值较大，局部搜索能力强。

变异概率使用自适应变异概率，即：

(10)

式中，Pm1、Pm2分别为最大和最小变异概率。

2.2.3反向搜索

(11)

式中，xmax(t)和xmin(t)分别为第t代变异操作前的最大值和最小值。

2.3改进遗传算法的工作步骤

(1) 参数初始化。确定种群规模popsize，最大和最小交叉概率分别为：Pc1和Pc2，最大和最小变异概率分别为Pm1和Pm2，最大迭代次数T。

(2) 产生初始种群。

(3) 计算个体适应度值，并根据适应度值对个体进行排序，保留最优个体。

(4) 根据式(12)计算个体被选择的概率，然后进行轮盘赌选择。

(12)

式中，q为最佳个体被选中的概率。

(5) 计算每个个体交叉的概率，然后进行交叉操作。

(6) 保存变异前种群最优个体和最差个体，然后计算个体的变异概率，并进行变异操作。

(7) 利用反向搜索产生新种群。

(8) 如果满足算法终止要求，则输出最优结果，不然返回步骤(3)继续进行。

采用3个标准函数对标准遗传算法和改进遗传算法性能进行测试，3个标准函数具体如下：

① Griewank 函数：

(13)

② Rastrigin函数：

(14)

③ Schaffer函数

(15)

3个标准测试函数的求解曲线如图2所示。从图2可以清楚看出，对于3个标准测试函数，相对标准遗传算法，改进遗传算法的收敛速度快，同时对于多峰值函数，改进遗传算法可以较好地找到最优解，而标准遗传算法却陷入局部最优解。结果表明，改进遗传算法由于引入具有引向因子的交叉算子，并且引入信息共享因子，在保证子代个体向最佳个体靠近的同时，防止早熟收敛现象发生，改善了解的质量，提高了算法的收敛性能，可以获得理想的结果。

图2　标准遗传算法和改进遗传算法的性能对比

3仿真实验

3.1仿真环境

为了测试改进遗传算法的Web组合服务问题求解有效性，在CPU：Pentium(R) 3.00 GHz，4.00 GB RAM，Windows XP操作系统，100 Mb/s局域网，采用Java语言实现服务Web 组合服务算法的仿真实验。设Web组合服务由20个Web子服务串联而成，每个服务节点有20个候选服务可供选择，每个候选服务的QoS参数采用随机方法在一定的范围内生成，具体参见文献[14]。

3.2不同算法的比较分析

使用文献[11,12]遗传算法和改进遗传算法对Web组合服务问题进行求解，它们的平均运行时间如图3所示。由图3可以看出，对比各算法，改进遗传算法搜索速度明显加快。主要由于引入了多尺度变异算子和反向搜索策略，加快算法收敛的速度，提高了Web组合服务问题的求解效率，证明本文对遗传算法进行改进，并应用Web组合服务问题求解的思想是可行的，且具有一定的优越性。

图3　不同算法的平均运行时间比较

使用文献[11,12]遗传算法和改进遗传算法的的Web组合服务最优方案的优化结果如图4所示。从图4可以清晰地看出，本文改进遗传算法的性能明显优于对比算法。对比结果表明，采用本文算法对Web组合服务问题进行求解，搜索能力较强，可以快速地找到用户条件的服务组合，是一种有效解决Web组合服务问题的方法。

图4　不同算法的优化结果比较

4结语

Web服务组合优化是当前电子商务领域中的一个研究热点问题，本文借助信息共享机制和多尺度交叉算子，提出一种基于改进遗传算法的Web服务优化组合方法。实验结果表明，改进遗传算法的全局搜索能力强，而且搜索速度快，可以在较短时间找到Web服务组合优化问题的最优解。

参考文献

[1] Chen Ming,Wang Zhenwu.An approach for web services composition based on QoS and discrete particle swarm optimization[C]//Proceedings of the Eighth ACIS International Conference on Software Engineering,Artificial Intelligence,Networking,and Parallel/Distributed Computing,2010:37-41.

[2] Canfora G,Penta M Di,Esposito R,et al.A lightweight approach for QoS-aware service composition[C]//Proceedings of the 2nd International Conference on Service Oriented Computing,2014,1:36-47.

[3] 王创伟,钱雪忠.蚁群算法在Web服务组合问题中的应用研究[J].计算机工程与设计,2007,28(24):5912-5914.

[4] 彭晓明,何炎祥,朱兵舰.蚁群算法在Web服务组合中的应用[J].计算机工程,2009,35(10):181-187.

[5] 刘莉萍,陈志刚,刘爱心.基于粒子群算法的Web服务组合研究[J].计算机工程,2008,34(5):104-106.

[6] 周清雷,陈明昭,张兵.多目标人工蜂群算法在服务组合优化中的应用[J].计算机应用研究,2012,29(10):3626-3628.

[7] 李东民,钟佩思,刘梅,等.基于业务流程的物流Web服务组合匹配研究[J].青岛农业大学学报,2009,26(1):56-60.

[8] 戴雪梅,姜浩.基于带权图规划算法的语义Web服务组合[J].计算机技术与发展,2013,20(3):68-75.

[9] 夏虹,李增智.粒子群算法求解Web服务组合中基于QoS的服务选择[J].北京邮电大学学报,2012,32(4):63-67.

[10] 黄振光,徐家兴,余阳.三段式动态服务组合优化算法[J].计算机集成制造系统,2012,18(8):1712-1718.

[11] 张成文,苏森,陈俊亮.基于遗传算法的QoS感知的Web服务选择[J].计算机学报,2009,29(7):1029-1037.

[12] 毛一梅,乐嘉锦.基于遗传算法的Web服务组合优化[J].计算机应用与软件,2008,25(11):199-201,277.

[13] 王肖燕.基于QoS的Web物流服务组合的优化模型[D].广东:中山大学,2012.

[14] Liu Qing,Zhang Shilong.Web service composition with QoS bound based on simulated annealing algorithm[J].Journal of Southeast University,20011,24(3):308-311.

ON OPTIMISATION OF WEB SERVICE COMPOSITION BASED ON IMPROVED GENETIC ALGORITHM

Xu TianLiu Lingxia

(DepartmentofComputingCenter,AnyangNormalUniversity,Anyang455000,Henan,China)

AbstractIn order to obtain better optimisation scheme of Web service composition, this paper proposes an optimisation method which is based on the improved genetic algorithm. First, it deems the feasible optimisation scheme of Web service composition as the individual of genetic algorithm, and then simulates the biological evolution in nature through genetic algorithm to find optimal solution of Web service composition; meanwhile it introduces multi-scale crossover operator and information sharing factor to standard genetic algorithm to improve problem’s solving speed. Finally we carry out the comparative experiments in simulation. Results show that the improved genetic algorithm can find the optimal solution of Web service composition problem quickly and accurately, this provides a new solution idea to the problem of Web service composition.

KeywordsWeb servicesGenetic algorithmService compositionQuality of service

收稿日期：2014-08-13。徐甜，副教授，主研领域：机器学习，数据挖掘。刘凌霞，副教授。

中图分类号TP391

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.05.007