基于退火果蝇优化算法的Web服务组合

王 妍，姚启豪，张以文

（安徽大学 计算机科学与技术学院 计算智能与信号处理教育部重点实验室，安徽 合肥 230031）

基于退火果蝇优化算法的Web服务组合

王 妍，姚启豪，张以文*

（安徽大学 计算机科学与技术学院 计算智能与信号处理教育部重点实验室，安徽 合肥 230031）

随着互联网中Web服务数量急剧增加，如何快速地从大量候选服务中选择出满足用户QoS需求的服务组合成为亟待解决的关键问题。QoS感知的服务组合优化问题是典型的NP-hard问题，而智能优化算法已成为主流的求解方法。在对web服务组合建模基础上，提出一种基于退火操作的果蝇优化算法（AFOA）。该算法通过引入模拟退火操作，使个体在进化过程中以一定概率进行突变，从而引向全局最优解，较好地避免了FOA易早熟收敛陷入局部最优的问题。大量实验结果表明，该算法在不减弱时间性能的同时，全局寻优性能较果蝇算法（FOA）、模拟退火算法（SA）有很大的提升。

服务组合；果蝇优化算法；模拟退火；服务质量

随着服务计算技术的发展，具有互操作性、跨平台性、松耦合以及高度可集成能力等特点的Web服务技术得到广泛应用[1]。但随着Web服务技术的推广，涌现出大量功能相同而服务质量（QoS）属性不同的Web候选服务。但单一的Web服务往往无法满足用户的需求，因此，如何高效地把现存各类Web服务按一定的业务逻辑整合，以形成新的满足不同用户需求的增值服务，已成为新的应用需求和研究热点。

在服务技术的发展过程中，出现过许多可执行的服务组合优化方案，可概括为基于服务功能的组合和基于服务质量的组合。但待优化问题已呈现出复杂性、多极性、强约束性、动态性、高维度等特点，导致传统的优化技术难以适用于新的应用场景。例如，基于功能属性的Web服务组合方法[2-4]，没有考虑到服务质量，找到的Web服务组合并不能满足用户的个性化需求及偏好。而现有的基于QoS约束的服务组合方法，也存在一些问题。例如，基于预先设定工作流程下的Web服务组合[5,6]以及基于QoS的时间感知下的服务组合[7]。前者限制较多，灵活性较差，在候选服务规模较大的情况下，寻优效果并不理想；后者服务选择范围较大，虽然可获得较优解，但同时产生巨大的服务选择时间开销。另有一些基于性能函数的Web服务组合方法，当一些性能函数存在很小误差时，整体的寻优能力也会大大下降[8]。

随着Web服务技术的进一步发展，智能优化算法逐步广泛应用于Web组合领域并表现出传统优化技术无法替代的优势，例如：遗传算法，粒子群算法，蚁群算法等。但这些算法同样也存在一些缺陷，例如，遗传算法(GA)，计算量较大，且拓展新空间的能力十分有限，易陷入局部最优解；粒子群算法(PSO)，在数据较离散的情况下，寻优效果不理想，且同样易陷入局部最优解；而蚁群算法（ACO）的计算过程则十分复杂。

为了有效解决以上问题，提出一种基于模拟退火下的果蝇优化算法(AFOA)。与传统遗传算法相比，AFOA寻优效果好，算法简单，参数少易调节，且计算量少，以及克服了传统服务组合优化算法收敛速度差，易陷入局部最优的缺陷。大量实验结果表明，与经典智能算法SA和FOA相比，AFOA具有寻优效率高，稳定性好，以及较强的全局寻优能力等特点。

1 相关算法

1.1 果蝇算法

果蝇优化算法（Fruit Fly Optimization Algorithm，FOA）[9]是一种受果蝇觅食行为启发从而推演出的寻求全局优化的新方法，其核心思想是利用果蝇优于其它物种的嗅觉和视觉，不断改变位置从而寻找到最佳觅食点。果蝇具有优秀的嗅觉和敏锐的视觉，易发现食物以及同类聚集的位置，并向该方向飞去。它属于演化式计算的范畴，亦属于人工智能的领域，在实际应用上没有领域限制。根据果蝇觅食的特性，FOA算法的具体描述过程如算法1。

算法1：FOA算法Step 1.Init(X_axis,Y_axis) Step 2.Get(X,Y) Step 3.Calculate(Disti,Si) Step 4.Smelli=Function(Si) Step 5.[bestSmell bestIndex]=min(Smell) Step 6.Set(X_axis,Y_axis) Step 7.Repeat(Step 2～Step 6)

其中，(X_axis,Y_axis)表示果蝇种群的位置，Si表示果蝇个体的气味浓度判定值，Smelli表示果蝇个体的气味浓度值，Function( )表示味道浓度判定函数。

1.2 模拟退火算法

模拟退火(Simulated Annealing，SA)是一种通用概率算法[10]，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。其思想来源于固体从某一较高初温出发，冷却过程中分子会逐渐趋向有序化，在每个温度达到平衡态，最后在常温态时，内能最小。对于温度T的每一个取值，算法都采用Metropolis[11]接受准则来进行判断，从而持续进行“产生新解～计算目标函数差～判断是否接受～接受或舍弃”迭代，同时逐步减少温度参数T，算法终止时所得的解即为近似最优解。模拟退火算法模型描述如算法2[12]。

算法2：SA算法Step 1.Init(S,T,T-r,T-Min) Step 2.Get(S') Step 3.Δt=C()S'-C()SStep 4.IfΔt＞0,Δt=S'else ifexp( ) Δt/T＞random( ) 0,1,S=S'Step 5.T=T*T-rStep 6.Repeat Step 2～Step 5 whileT＞T-Min

其中，S表示初始状态，T表示初始温度，T-r表示退火速度，T-Min表示温度下限，C()表示评价函数。

2 基于QoS的Web服务组合

本文提出的优化算法建立于两个实验模型之上，一个是Web服务模型，另一个是AFOA算法模型。通过Web服务的构建，可以清晰地定义和使用Web服务的各种属性，以及在实验中为Web服务指定一个量化的指标。而通过构建AFOA算法模型，则可以清楚地描述该算法中各参数在Web服务组合中代表的实际意义，便于算法实现。

2.1 问题描述

定义1服务质量(Quality of Service，QoS)

服务质量是指服务能够满足规定和潜在需求的特征和特性的总和。随着Web服务的广泛普及，服务质量将变成一个判定服务提供者是否成功的重要因素。本文采用一个四元组QoS=(T,A,C,R)来评价Web服务质量，其中T表示Web服务的响应时间（Response-Time），A表示Web服务的可用性（Availablility），C表示调用一次服务的代价（Cost），R表示Web服务的信誉度（Reputation）。

可用性是指一个Web服务可以提供某项特定服务的时间，即在时间段t内成功访问Web服务的时间所占比例，A=tsuccess/t，tsuccess表示在时间段t内成功访问服务的时间。

响应时间是指从用户提交服务请求到服务执行完成返回结果所消耗的时间。主要包括Web服务执行时间Texe、网络传输时间Ttrans和其它时间消耗Toth，即T=Texe+Ttrans+Toth。

费用是指从用户提交Web服务请求到服务执行完成返回结果所需要的所有费用。主要包括Web服务软件(SaaS)、硬件(laaS)、平台(PaaS)等服务基础成本Cserv和服务管理成本Cmanag，即C=Cserv+Cmanag。

定义2Web服务

本文采用一个四元组S={ID,Source,F,QoS}来表示Web服务。其中，ID是Web服务的唯一标识，Source表示资源的名称及发布者等描述信息，F指Web服务的功能性描述，QoS指Web服务质量。

定义3Web服务组合

服务组合是一个多元组，SC=(s1,s2,s3,…,sn-1,sn），其中s1至sn分别表示每个Web子服务，且s1∈S1,s2∈S2,s3∈S3,…,sn-1∈Sn-1,sn∈Sn，同时，S1至Sn称为Web服务组合的子服务集，Si中子服务功能相同但服务质量不同。则可得SC∈S1×S2×S3×…×Sn-1×Sn。常见的四种 QoS的基本计算模型如表1所示。其中，ρi为第i个分支被选中的概率，μ为循环次数。

表1 QoS参数计算公式

由于其他三种非顺序型可以转换为顺序型结构，本文采用顺序结构为基础研究Web服务组合优化问题。

2.2 算法建模

每条服务组合由N个子服务组成，每个子服务属于不同的子服务集。把每个子服务作为单个果蝇个体，每条组合当作一个果蝇种群。然后对N个果蝇分别进行果蝇迭代算法进行计算。对于每个组合，利用fitness函数进行计算，并寻找到最优解。

本文采用离散型编码方式，每个果蝇个体表示的是其在所归属子服务集中的位置信息。例如，Pi,j,k表示的是第i次迭代第j个种群中的第k个果蝇个体在子服务集中所对应的位置。

以每个中心位置随机产生K*N个领域个体，定义果蝇嗅觉搜索范围Rd为[-R，R]，则新个体为

其中NPi,j,k表示以Pi,j,k种群个体产生的邻域解的位置，并代入下次迭代。

对邻域解内的个体，计算Smell值，并选取最优的个体，使得种群向这个个体的位置转移。

其中，SC(NPi,j,k)表示第i次迭代的第j个种群的第k个个体在子服务集中所对应的位置，Disti,j,k表示第i次迭代过程中第j个果蝇种群中第k只果蝇的距离，Smelli,j,k表示第i次迭代过程中第j个果蝇种群的第k只果蝇的smell值。

不同类型的指标具有不同的量纲。为消除量纲和量纲单位不同所带来的不可公度性，在合作评价前需要将所有指标按某种效用函数归一化到某一无量纲区间（一般是将其归一化到[0,1]区间）。本文只考虑离散型指标，按公式（3）进行归一化处理。

Fitness函数用来评价组合服务的适应度(本文中越小越好)，通过不同服务组合的Fitness值来判断各个服务组合的优劣程度。结合公式（3）的预处理结果，Fitness函数可以定义为

由于果蝇算法存在易于陷入局部最优解的情况，在此引入模拟退火操作，以一定概率突变，使得其产生突变个体增加寻优能力并引向全局最优解，从而一定程度上避免了果蝇算法在搜索上陷入局部最优的情况。

给定初始温度T、冷却速率T_r，由果蝇种群S产生新的个体S'，并产生新的Fitness函数值。由此计算增量：

根据公式（5），若Δt'＞0，则接受S'作为新的种群位置。否则，以公式（6）来评价是否存在突变个体，并接受其作为新的种群位置。

2.3 AFOA算法实现

在引入退火机制的基础上，本文提出一种改进的果蝇优化算法，即退火果蝇优化算法（AFOA）。AFOA算法详细描述如下：

Step 1：确定初始温度T，冷却速率T_r，初始化产生N个种子果蝇种群位置Pos0～Posn。

Step 2：通过果蝇嗅觉搜索，对N个果蝇个体产生KN个新的邻近果蝇个体，组合成K个果蝇种群。

Step 3：根据公式(1)，计算种群位置。

Step 4：根据公式(2)，计算种群个体的smell值，得到新的邻近较优位置。

Step5：将气味smell集合转换成服务组合记录。

Step6：根据公式(4)，计算每条服务组合记录的Fitness函数值。在每次迭代中，比较当前解与全局已寻最优解，保留找到的最小Fitness值的果蝇位置。

Step7：根据新得到的Fitness函数值，结合当前温度，随机突跳并判断果蝇移动情况。若满足公式(5)＞0，则接受其作为新的种群位置，否则以公式(6)来评价是否存在突变个体，并接受其作为新的种群位置。

Step8：更新最优解，更新退火温度T=T*T_r。

Step9：重复Step 3～Step 8，迭代Lk次。

Step10：输出最优组合。

从时间复杂度方面，要迭代Lk次，并且每个种度为O(Lk*KN*N)。与果蝇算法复杂度一致。可见，AFOA并没有提高时间复杂度，并通过大量实验结果表明在相同的时间要求下，本文改进算法的寻优性能更优。

3 实验结果与分析

3.1 实验环境与实验数据

在实验过程中采用的是Zeng等提供的QWS数据集[13]。实验环境为：Windows 8.1，Inter(R) Core(TM)I5-3470 CPU@3.20 GHz 3.20 GHz，4.00 GB RAM，64位操作系统，Visual Studio 2010，C++。果蝇算法可依赖参数有KN(即新邻近解的个数，实验中的popsize)，R(新位置产生范围，实验中的步长L)等，模拟退火可依赖的的参数有T，T_r等，对于不同的参数或对实验效率产生影响，因此先对参数设置进行实验。实验参数设置如表2所示。

表2 实验参数配置

3.2 实验结果分析

3.2.1 迭代次数不同时的寻优性能

为分析不同迭代次数下FOA、SA以及AFOA的寻优性能，在初始温度10 000 000，候选服务规模100，种群规模120，子任务数分别为5、10、15和20，不同迭代次数的设置下，重复50次试验所得寻优效果如图1～4所示。

由图1～4易知，整体而言，随着迭代次数的增加，在不同子服务数下AFOA的寻优效果均显著优于SA和FOA，且随着迭代次数的增加寻优能力在不断增强。因此，AFOA在不同迭代次数下具有很强的寻优能力。

3.2.2 候选服务规模不同时的寻优性能

为了进一步探究FOA、SA以及AFOA的寻优性能，通过在迭代次数 500，初始温度群要产生KN个邻近的新果蝇个体，所以总复杂10 000 000，种群规模120，子任务数分别为5、10、15和20，候选服务规模不同的情况下进行50次重复试验，所得结果如图5～8所示。

图1 子任务数为5时不同迭代次数下的寻优效果

图2 子任务数为10时不同迭代次数下的寻优效果

图3 子任务数为15时不同迭代次数下的寻优效果

图4 子任务数为20时不同迭代次数下的寻优效果

图5 子任务数为5时不同候选服务规模下的寻优效果

图6 子任务数为10时不同候选服务规模下的寻优效果

由图5～8可清楚得知，在不同候选服务规模的情况下，AFOA的整体寻优效果普遍高于SA和FOA。此外，FOA的寻优能力时而高于SA，时而低于SA，但无论两者孰优孰劣，AFOA的寻优效果始终优于两者。因此，AFOA在不同候选服务规模下具有优秀的寻优能力。

图7 子任务数为15时不同候选服务规模下的寻优效果

图8 子任务数为20时不同候选服务规模下的寻优效果

图9 不同迭代次数下的时间开销

3.2.3 时间性能

为分析AFOA与FOA、SA之间的时间开销，通过在初始温度10 000 000，候选服务规模125，种群规模120，子任务数分别为20，不同迭代次数的设置下，重复50次试验所得时间开销如图9所示。由图可知，AFOA的时间开销与FOA算法相近，略低于SA。由计算的时间复杂度可知AFOA与FOA、SA算法时间复杂度相近，具体时间差异则由编译环境，编译时机等运行机制造成。因此，AFOA算法在和其他两种算法的时间性能方面势均力敌的情况下，仍能取得很好的寻优效果。

4 结论

为了更好的解决服务组合优化问题，本文提出了一种在果蝇算法和模拟退火算法的基础上进行完美融合的更加优化的智能算法（AFOA），该算法是在果蝇依据气味寻求最优解的过程中引入退火机制对产生的最优解进行一定概率突变，使得其产生突变个体进而产生进化过程并引向全局最优解，从而可以有效的避免在搜索过程中陷入局部最优解的风险。为了验证AFOA算法的有效性和可靠性，与多种算法进行了比较分析，大量的仿真模拟实验结果表明AFOA算法所用时间与FOA、SA算法相近，但AFOA算法的寻优能力显著高于FOA算法和SA算法。下一步我们将更加深入的研究如何在最适合的位置进行突变和找出最适合的突变概率，进一步提高算法的效率。

[1]陈国彬.基于Qos约束的Web服务组合算法[J].控制工程，2014，21（4）：609-612.

[2]El Falou M,Bouzid M,Mouaddib A I,et al.A distributed planning approach for web services composition [C].Web Services(ICWS),2010 IEEE International Conference on IEEE,2010：337-344.

[3]Bertoli P,Kazhamiakin R,Paolucci M,et al.Continuous Orchestration of Web Services via Planning[C]. ICAPS.2009.

[4]Hoffmann J,Bertoli P,Helmert M,et al.Messagebased web service composition,integrity constraints, and planning under uncertainty：A new connection[J]. Journal of Artificial Intelligence Research,2009：49-117.

[5]Zeng L Z,Benatallah B,Ngu A H,et al.QoS-aware middleware for Web Services Composition[J].IEEE Transactions on Software Engineering,2004,30(5)：311-327.

[6]Menasce D A.Composing web services：a QoS view [J].IEEE Internet Computing,2004,8(6)：88-90.

[7]Zou G B,Lu Q,Chen Y X,et al.QoS-Aware dynamic composition of web services using numerical temporal planning[J].IEEE Transactions on Services Computing,2014,7(1)：2-15.

[8]Volk F,Sokoli J,Muehlhaeuser M.Performance functions for QoS prediction in web service composites [C]//2014 IEEE 21ST INTERNATIONAL CONFERENCE ON WEB SERVICES(ICWS 2014),2014：574-581.

[9]Xing B,Gao W J.Fruit fly optimization algorithm[M]. Innovative ComputationalIntelligence：A Rough Guide to 134 CleverAlgorithms,2014：167-170.

[10]陈华根，吴健生，王家林，等.模拟退火算法机理研究[J].同济大学学报(自然科学版)，2004，32（6）：802-805.

[11]蒋惠波，刘 彬，袁卫华.基于Metropolis准则的自适应随机搜索算法研究[J].中国西部科技，2015（3）：17-19.

[12]庞 峰.模拟退火算法的原理及算法在优化问题上的应用[D].长春：吉林大学，2006.

[13]Zeng L Z,Benatallah B,Ngu A H,et al.QoS-aware middleware for Web Services Composition[J].IEEE Transactions on Software Engineering,2004,30(5)：311-327.

Web service composition based on annealing fruit fly optimization algorithm

WANG Yan,YAO Qi-hao,ZHANG Yi-wen
(Key Laboratory of Intelligent Computing and Signal Processing,Anhui University,Hefei Anhui230031,China)

With the rapid increase in the number of web services in the internet,it is a key problem to be solved urgently that how to select the service composition quickly,meeting the users’QoS requirements from a large number of candidate services.QoS-aware service composition optimization problem is a typical NP-hard problem,and the intelligent optimization algorithm becomes the mainstream solution.On the basis of the web service composition modeling,this paper proposes a novel algorithm named annealing fruit fly optimization algorithm(AFOA).By introducing simulated annealing operation,the individual mutates at a certain probability in the evolution process,thereby leading to the global optimal solution and avoiding FOA being premature to converge into local optimum.Substantial experiments show that without weakening the time performance,AFOA still has a great improvement in the global optimization capacity compared with fruit fly optimization algorithm(FOA)and simulated annealing algorithm(SA).

service composition;fruit fly optimization algorithm;simulated annealing;quality of service

TP311

：A

：1004-4329（2016）04-067-07

10.14096/j.cnki.cn34-1069/n/1004-4329(2016)04-067-07

2016-07-09

安徽省自然科学基金(1408085MF132)；大学生科研训练计划项目（KYXL2014060）资助。

张以文（1976- ），男，博士，副教授，研究方向：服务计算、云计算。Email：yuji912@163.com。