颉斌,杨扬,王洁莹

(北京科技大学 计算机通信工程学院,北京100083)

摘要：对于Web服务组合优化的问题，蚁群算法的求解主要是串行进行，收敛时间长，容易收敛于非最优解。在云计算环境中，将蚁群算法并行化，可对Web服务组合优化问题进行分布式并行求解。根据多目标优化模型给出基于多信息素的蚁群算法，使用MapReduce并行编程框架对蚁群算法中最耗时的部分——蚂蚁独立求解的过程并行化，给出了使用MapReduce改进的基于多信息素的蚁群优化算法，有效地对Web服务组合进行全局优化，弥补传统的蚁群算法求解过程的缺点。

0引言

随着云计算的发展，Web服务组合优化问题已经成为了国内外研究的热点。现有优化算法一般是启发式算法。许多研究结果表明，蚁群优化算法具有分布式计算、鲁棒性好等优势，但通常需要足够的群落大小和足够数量的迭代。随着目标问题规模的增长，会导致计算效率低下。蚁群算法的求解主要是在集中式串行环境下，而在云计算环境中，利用云计算技术将蚁群算法并行化对问题进行分布式并行求解的研究较少。

大多数现有并行化的蚁群算法都依赖于使用传统的并行编程模型来实现。MANFRIN M等人用消息传递接口(Message Passing Interface,MPI)在多机环境中实现了TSP的并行ACO ［1］。CRAUS M等人用一种一主多从机制实现了基于MPI的并行ACO算法［2］。Huang Diwei等人用MapReduce实现了作业调度问题的遗传算法，并得到了合理的结果［3］。参考文献［4］用MapReduce针对TSP实现了并行的蚁群算法，但存在多次迭代使算法性能降低的问题。

本文提出将蚁群算法并行化的思想，使用MapReduce并行化编程模型，将基本的蚁群算法并行化，可解决云计算环境下使用蚁群算法进行Web服务组合优化容易出现的求解困难的问题。本文根据多目标优化模型给出基于多信息素的蚁群算法，使用MapReduce并行编程框架对蚁群算法中最耗时的部分——蚂蚁独立求解的过程并行化，给出使用MapReduce改进的基于多信息素的蚁群算法。

1问题建模

1.1优化目标建模

本文选择子服务的负载、服务级别协议［5］（Service Level Agreement, SLA）（包括价格C(Si)、执行时间T(Si)、可靠性A(Si)）以及用户优先级这3个非功能性属性约束条件来制定服务组合优化的目标准则。利用排队论思想，定义这些指标为随时间t变化而变化的密度分段函数。

（1)服务的负载

QB(Si)=λ/μ(1)

其中，λ为任务到达率，μ为服务率。

（2)服务级别协议（SLA）

本文选取3个服务质量参数：价格C(Si) 、执行时间T(Si)、可靠性A(Si)。

服务的价格C(Si)表示为：

QC(Si)=C(2)

执行时间T(Si)的密度函数为：

QT（Si）=p(T(Si))=(μ-λ)e-(μ-λ)t,t>0(3)

服务Si的可靠性A(Si)反映了服务的可靠程度，即单位时间内服务可用的时间与服务的失效率成反比。出错率的分布函数为：

QA（Si）=p(A(Si))=βt,0<t<T(4)

其中，T为出错维护时间。

（3)用户优先级

L(Si)=l(5)

本文采用参考文献［6］中的预处理方法，将这些非功能性属性的值进行标准化的转换。设一个Web服务Sij，具有n个非功能性属性，表示为Qij={q1ij,q2ij,…，qnij}。通过式(6)、式(7)进行转换。若第r个属性为正属性，则用式(6)处理；若第r个属性为负属性，则用式(7)处理。

其中，qrmax为组合服务中全部Web服务中第r个属性中的最大值，∑qrml为组合服务中全部Web服务的第r个属性之和。

1.2Web服务组合优化问题的建模

在Web服务组合优化的过程中，对非功能性属性简单地加和会影响某些属性值，不能准确地表达非功能性属性［7］。通常将Web服务组合优化问题转换成有限方案的多目标决策问题，在各目标之间进行协调权衡，使得所有目标函数尽可能达到最优。

将多目标优化问题定义为一个三元组：（X,C,F）。其中X代表一个n维决策空间，即x=(x1,x2,…，xn)∈X；C代表一个集合，包含了一组决策变量所同时满足的约束条件；F是一个矢量，包含所有的目标函数，个数m≥2，可表示为：F=(f1(x),f2(x),…，fm(x))。多目标优化就是使这些不同的目标函数同时达到最小。当多个目标要同时达到最优时，最优解就是Pareto最优集。

设单个Web服务为Sij={Fij，Qij}，其中Fij为功能性属性集合。服务组合优化问题就是在由服务节点构成的图中的多条路径中选择一条，使得这条路径中的各个非功能属性的汇总能够符合用户需求［8］。这就将服务组合优化的问题转换为了一个多目标决策的数学问题，即针对组合服务的多个非功能性目标进行优化。本文考虑串行服务组合问题。

（1)负载

利用式(6)和式(7)对服务的各个非功能性属性进行预处理。设这个组合服务中共包含m个子服务实例，候选服务实例共有n个，则将Web服务组合优化问题转换为多目标优化的数学模型，多目标函数如式(13)所示。

f1=∑mi=1λiμi∑ni=1λiμi

f2=m(QCmax+1)∑ni=1Ci-1

f3=m(QTmax+1)τe-τt-1

f4=∑mi=1βit∑ni=1βit

f5=∑mi=1li∑ni=1li(13)

算法的目标就是使式(13)中的5个目标函数均尽量达到最小，此时所得到的Pareto最优解集就是服务组合优化后的解集。

2基于MapReduce改进的蚁群算法

2.1多信息素蚁群算法

基本的蚁群算法是针对于单一种类信息素的，因而无法解决组合服务中多属性约束的问题。但本文是针对Web服务组合中的多个非功能性属性进行优化，因此要对蚁群算法进行改进。在本文的改进蚁群算法中，启发式信息和信息素都用服务的多个非功能性属性来表示，每个非功能性属性都对应一个目标函数。

通常把信息素限制在一个区间，设为［τmin,τmax］。用于Web服务组合优化的多信息素蚁群算法1如下所述：

算法1:多信息素蚁群算法

(1)所有信息素初始化都为τmax；

(2)设定目标函数共为n个，总的迭代循环次数为m；

(3)蚁群算法开始，每只蚂蚁开始行动。第j代蚂蚁单独选路时，随机选取一个优化目标函数（设为第i个），然后以第i个信息素表中的信息素求解一个解（求解方法见算法2）；

(4)单独选路完毕，即更新第i个信息素表中的所有信息素值；

(5)如果j=n，则计算结束，否则返回步骤（2）继续计算。

2.2状态转移概率

将服务实体Sij的第k个非功能性属性的信息素表示为τki(j)，将第k个非功能性属性的启发式信息表示为ηki(j)。状态转移概率的计算公式如式(14)所示，其中α和β参数分别决定了信息素和启发式信息的相对影响力。

规定式(14)中的启发式信息ηi(j)为用户所关注的所有非功能属性的启发式信息（即n个优化目标）之和，由式(15)求出。根据这个规则求解即可完成组合服务的多目标优化。利用这个转移概率，基于多信息素的蚁群算法中蚂蚁根据信息素求解的过程如下：

算法2:解的构建算法

（1)初始化解为空；

（2)按照式(14)计算出下一子任务中所有子服务实体的转移概率，选择转移概率最大的服务实体，更新解空间；

（3)如果所有任务都已选择完成，则返回，否则转到步骤（2）。

ηi(j)=∑nk=1ηki(j)(15)

2.3信息素更新规则

综上所述，信息素更新规则总结如下：

算法3: 信息素更新规则

（1)初始化i=1。

（2)首先按照式(16)求出新的第i个信息素表中的信息素值，范围已设定为［τmin,τmax］，若超过，则取边界值。

(3)利用目标函数fi的公式计算出所有解的目标函数值，根据式(17)求出Δτk，利用式(18)计算最新的信息素。更新后的信息素值若在［τmin,τmax］之外，则一律取边界值。

(4)若解Si优于解Sibest，则令Sibest=Si。

(5)若信息素表未被完全更新，则i增加1，算法跳转到步骤（3)；否则返回，更新信息素结束。

2.4MapReduce并行化改进

本文为了使用蚁群算法解决多目标优化的问题并减少计算量，将基于多信息素的蚁群算法进行并行化的改进。在云计算环境下，引入MapReduce思想，改进蚁群算法，应用Map函数来并行化每只蚂蚁的独立求解过程，用Reduce函数分解出问题的解和值，求得较优解并处理信息素更新。从整体结构上，应用云计算的管道能力实现逐代的计算。具体设计如下：将多个Map、Reduce函数首尾相连，本代任务的输出作为下一代任务的输入，开始下一个并行计算任务。将多对Map、Reduce任务串行起来，形成一个Map1Reduce1Map2Reduce2…MapnReducen的执行序列。

3仿真实验

本实验以校园云平台为背景、以平台上的服务组合实例为基础进行。组合服务实例共有5个子任务，将每个子任务上部署10个服务实例。实验部署在Apache Hadoop 0.21.0环境中，MapReduce集群包含了16个节点。实验中蚂蚁数=100，循环次数n=2 000，集群中计算机数目=2。其他参数取值为：τmin=10，τmax=100，ρ=0.01，启发式信息按照式(15)取值，信息素按算法3进行迭代更新。

3.1算法优化效果测试

每轮测试10次，取平均数。针对两种情况进行对比实验：α=2，β=2；α=1，β=4，输出结果如图1、图2所示。图中纵轴代表各个目标函数的结果的平均值。

由图1、图2可见，5个目标函数随着循环次数增加全部呈减小趋势，并且在一定的循环次数时趋近于稳定值。图2中目标函数收敛得更快一点，可见通过改进的蚁群算法，使得服务组合得到了有效优化。第二组参数取值中，β取值较大，说明蚂蚁在选路时，受到启发式信息的影响更大，所以目标函数收敛速度更快。

上述实验证明了本文算法的有效性，结果稳定且有良好的鲁棒性。

3.2MapReduce并行化效率提升测试

本实验中，算法连续运行10次，对运行时间取平均值，结果如图3所示。其中横坐标是MapReduce并行化节点job个数，纵坐标是运行时间（ms）。

由图3可见，折线图呈近线性下降趋势，表明该并行化方法达到了近线性的加速优化，说明基于MapReduce对蚁群算法中最耗时的蚂蚁独立求解部分进行并行化，有效提高了优化效率。

4结论

本文改进了传统的蚁群算法，增加多信息素，使其适用于多目标优化的数学问题，同时考虑到蚁群算法的隐含并行性质，利用MapReduce框架将算法中最耗时的蚂蚁独立求解过程并行化。根据制定好的目标准则，使用改进过的蚁群算法对云计算环境下的Web服务组合进行有效的全局性优化。通过仿真实验验证了方法的有效性。

参考文献

［1］ MANFRIN M, BIRATTARI M, STTZLE T, et al. Parallel multicolony ACO algorithm with exchange of solutions［C］. BelgiumNetherlands Conference on Artificial Intelligence, 2006.

［2］ CRAUS M, RUDEANU L. Parallel framework for antlike algorithms［C］. 2004 Third International Symposium on Parallel and Distributed Computing, 2004 Third International Workshop on Algorithms, Models and Tools for Parallel Computing on Heterogeneous Networks, IEEE, 2004:3641.

［3］ Huang Diwei, Lin Jimmy. Scaling populations of a genetic algorithm for job shop scheduling problems using MapReduce［C］. Proceedings of the 2010 IEEE Second International Conference on Cloud Computing Technology and Science, IEEE Computer Society, 2010:780785.

［4］ 夏卫雷,王立松.基于MapReduce的并行蚁群算法研究与实现［J］.电子科技,2013, 26(2):146149.

［5］ 徐忠胜,沈苏彬.一种云计算资源的多目标优化的调度方法［J］.微型机与应用, 2015,34(13):1720.

［6］ 刘彬,张仁津.基于QoS多目标优化的Web服务组合方法［J］.计算机工程与设计,2012, 33(3):885889.

［7］ AKBAR M M, MANNING E G, SHOJA G C, et al. Heuristic solutions for the multiplechoice multidimension knapsack problem［M］. Computational Science ICCS 2001. Springer Berlin Heidelberg, 2001:659668.

［8］ WADA H, SUZUKI J,YAMANO Y, et al. E3: a multiobjective optimization framework for SLAaware service composition［J］. IEEE Transactions on Services Computing, 2012, 5(3):358372.