基于混沌机制和改进粒子群算法的Web服务组合优化

王妍，刘瑜岚，荆紫慧，张以文

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

基于混沌机制和改进粒子群算法的Web服务组合优化

王妍，刘瑜岚，荆紫慧，张以文*

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

随着互联网和大数据的迅速发展，如何从大量Web服务中选择合适服务及组合以满足用户需求已成为新的热点。本文提出一种改进的混沌粒子群优化（ICPSO）算法，应用到Web服务组合优化问题。针对传统PSO算法易陷入早熟收敛和局部最优的缺点，该算法引入了混沌扰动机制使粒子易跳出局部极值，增强了种群多样性，从而提高算法寻优能力。最后通过仿真实验验证了ICPSO算法的可行性和有效性。

服务组合；ICPSO算法；混沌机制；服务质量

随着面向服务计算（service-oriented computing）技术的迅速发展，基于Web服务的分布式计算模式正成为技术发展的趋势[1,2]。Web服务作为一种能够自适应、自描述和模块化的应用模式，吸收了分布式计算、网格计算和XML等各种技术的优点，包括平台无关性、松散耦合性、规范约束协议以及封装性等，使其广泛应用于基于Internet环境的异构系统的互操作与应用系统集成。

然而，越来越多的功能相同或相近而服务质量不同的服务出现在网络上。而单个Web服务所具有的功能一般都比较单一，无法满足用户服务质量（Quality of Service,QoS）的复杂需求，因此如何从多个功能单一的Web候选服务中挑选出若干服务并形成一个满足用户复杂需求的组合服务已成为服务计算领域的研究重点[3,4]。为了能够满足用户业务需求，提供更强大的服务功能，有必要根据特定的应用场景和需求对现有的服务进行有效的组合。因此Web服务组合问题也就成了典型的NP-hard问题。

为此，本文提出了一种基于混沌理论的改进的粒子群算法来解决Web服务组合优化问题，其基本思想体现在以下几个方面：

1 相关工作

近年来，工业界和学业界分别应用不同的方法对Web服务组合优化问题进行了研究。在服务组合优化问题研究中，服务组合模型是由多个服务节点按照一定的逻辑顺序关系组成，每个服务节点是若干服务实例的抽象类，这些候选服务实例具有相同功能但不同非功能属性（QoS），且QoS又是评价一个Web服务的重要指标。目前，基于QoS的服务组合优化方法主要可分为两大类，第一类是传统计算方式的优化方法，如穷举法、动态规划、线性规划、和图算法等。Alrifai等人[5]提出了一个把全局优化和局部选择技术结合在一起的混合方案去解决服务组合问题。范小芹等人[6]利用随机型离散事件系统的马尔科夫决策过程(MDP),提出了Web服务各随机QoS指标的度量方法，设计出随机QoS感知的可靠Web服务组合算法。第二类是智能优化算法，如遗传算法、蚁群算法、粒子群算法等。张成文等人[7]提出一种基于遗传算法的QoS感知的Web服务选择算法，可以有效的从全部组合方案中选出满足用户QoS需求的服务组合。Zhang等人[8]在服务组合优化过程中应用蚁群算法提出了一个基于QoS的动态服务组合方法。与遗传算法和蚁群算法相比，粒子群算法具有参数少、收敛速度快的特点，在很多优化问题上表现出良好的搜索能力。刘莉平等人[9]针对现有服务组合中QoS优化的不足，利用粒子群算法的智能优化原理加快粒子群的搜索速度，提出了一种基于粒子群算法的QoS动态服务组合算法，不过该算法中种群的粒子容易陷入局部最优值。范小芹等人[10]提出了一种面向动态Web服务选择的离散粒子群算法，为了增强算法的全局搜索能力，定义相关的准则。胡旺等人[11]采用简化粒子群优化方程和添加极值扰动算子两种策略，提出了简化粒子群优化算法，避免了由粒子速度引起的粒子发散而导致后期收敛慢和精度低的问题。基于以上分析，PSO算法较其他方法能更好的解决服务组合优化问题，但在进行组合时种群的粒子易被当前全局最优粒子吸引而快速收敛于局部最优值。同时，候选服务的规模越来越大，传统的优化技术已无法有效地处理该问题。为此，本文提出了改进的混沌粒子群算法解决服务组合优化问题，引入混沌优化思想提高种群多样性。

2 组合服务模型描述

定义1Web服务（WS）是一种具有跨平台、低耦合、高度可集成、模块化的软件应用程序。用WSi=(Ii,Oi,QoSi)表示一个服务，其中Ii为第i个服务的输入，Oi为第i个服务的输出，QoSi为其对应的非功能属性服务质量。

定义2服务质量（QoS）是服务的非功能属性，本文中服务QoS用一个四元组表示QoS=(T,C,A,R)，其中T表示响应时间，C表示调用一次服务的费用，A表示可用性，R表示可靠性。

定义3候选服务集（SS）是由一组具体Web服务组成的集合，这些服务具有一样的功能但QoS不同。组合服务模型中每个服务都有一个相对应的候选服务集，用SSj表示第j个服务对应的候选服务集。

定义4组合服务（CS）是由候选服务集中服务依据服务模型，形成的一个具体的Web服务序列。用一个五元组表示CS=(QoS,L,S,W,F)，其中本文服务包含四个QoS属性，L是服务直接关系的集合，W是属性权重W={w1,w2,w3,w4}且w1+w2+w3+w4=1，S是组合模型中的所有服务集S={S1,S2,...,Sj,...,Sn}，F是组合服务评价函数。

Web组合服务有多个原子服务组合而成，原子服务之间有明确的逻辑执行循序。服务组合是根据各原子服务间的逻辑关系，重用已有的Web服务，组合成能够满足用户业务需求的服务组合。根据其逻辑执行关系，服务组合流程有如下四种基本结构。

以上模型的QoS计算公式如表1所示。

表1 组合服务的QoS计算公式

对以上Web服务的QoS属性，可划分为两种类型：积极型和消极型。积极型（positive型)，其指标值越大服务质量越好，如可靠性、可用性。消极型（negative型)，如响应时间、费用等，其指标越小，服务质量越好。为统一度量组合服务的QoS属性，需要对各个QoS属性进行标准化。可采用公式（1）和（2）分别对消极属性和积极属性进行归一化处理。

Qh,k表示第h类服务中的某个Web服务实例的第k个质量属性，为第h类服务中的某个Web服务实例的第k个质量属性的最大值，为最小值。对于消极属性采用公式（1）计算，而对于积极属性则可采用公式（2）计算。Qh,k为转换后的质量属性，其值越大表示QoS属性越好。

3 标准PSO算法

PSO算法是1995年由Eberhart和Kennedy博士提出的一种启发式进化计算方法[12]，来源于对生物群体智能行为的简化模拟。PSO算法在初始阶段随机产生一个初始种群并赋予种群中每个粒子一个随机速度，在飞行过程中粒子速度依据自身以及种群飞行经验进行不断调整，使整个种群能够飞向更好的搜索区域，从而发现较优的解。

PSO具体算法具体实现步骤描述如下：

Step 1初始化粒子群，随机初始化种群中每个粒子的位置与速度。

Step 2根据适应度函数Fitness(x)，计算出每个粒子位置的适应度值。

Step 3更新pbest，对比粒子本次迭代位置与其历史最佳位置，若Fitness(xi)＞Fitness(pbest)，则Fitness(pbest)=Fitness(xi)。

Step 4更新gbest，找出当前种群中适应度值最大的粒子，假设为xg，若Fitness(xg)＞Fitness(gbest)，则Fitness(gbest)=Fitness(xg)。

Step 5根据公式（3）和（4）更新粒子的位置和速度。

Step 6检验是否满足终止条件(通常是达到最大迭代次数或得到满足一定条件的较优解)，若满足，终止迭代，算法结束。否则返回步骤Step 2。

4 基于改进ICPSO算法的服务组合算法

4.1 混沌机制及其特性

一般将由确定性方程得到的具有随机性的运动状态称为混沌，混沌状态广泛存在于自然现象和社会现象中，是非线性系统中一种较为普遍的现象，其行为复杂且类似随机。混沌变化过程看似一片混乱，但实际上并不是一片混乱，而是有着内在结构的一类现象。

混沌变量有以下特点：随机性即它的分布杂乱，如同随机变量。遍历性即它可以遍历空间区域内的所有状态且不重复。规律性该变量是由确定的混沌模型迭代导出的。

混沌优化算法是一种智能优化算法，利用混沌特性在一定范围内进行优化搜索。其基本思想是首先产生一组混沌变量，其数量与待求解问题中的优化变量相同，利用混沌变量具有随机性、遍历性和规律性的特点进行混沌扰动产生新解，同时把混沌变量的运动范围映射到优化变量的解空间，对优化变量做出优劣评价，经多次迭代，最终产生最优解。Logistic映射方程是一个典型的混沌系统[13]：

其中μ为控制变量，当μ=4时，系统（5）进入完全混沌状态，对于任意的χ(0)∈[0,1],可根据Logistic方程迭代出一个序列χ(1)，χ(2)，χ(3),…。

4.2 算法改进策略

4.2.1 混沌初始化种群

假设种群中有m个粒子群，搜索空间为n维,即Web服务组合模型中有n个服务类。粒子位置变量则表示服务组合优化的解（即可行的组合服务方案），粒子的位置可用一个n维向量来表示，本文采用整数编码，若第j个服务类Sj对应的候选服务集规模为hj，候选服务集中的每个候选服务依次进行编码，则第z个候选服务对应的编号为z，其中z是区间[1,hj]上的整数，初始化时粒子位置的每一维都是整数，即对应得候选服务集中Web服务的编号。例如向量xi=(xi,1,xi,2,...,xi,n)表示粒子i的位置，则xi,j表示第i种服务组合方案中第j个服务类的编号为xi,j的候选服务。

本文采用混沌序列初始化粒子群中的粒子，对简单的一维逻辑混沌映射模型公式（5）的进行重写，描述形式如下：

其中，μ取值与公式（5）相同，t是迭代次数，ctj为粒子位置在j维上的混沌变量，初始化生一个n维的混沌序列，采用公式（6）进行m-1次混沌迭代，即则产生m-1个混沌序列，然后将每个混沌序列利用公式（4）行映射到粒子位置解空间，最终得到m个粒子的初始化位置。

hj是第k个粒子位置第j维的解空间大小，即第j个服务类的候选服务规模。对变量四舍五入，保证粒子位置映射到解空间。

4.2.2 早熟收敛处理机制

PSO算法解决服务组合优化问题时种群易陷入早熟收敛状态，导致得到的解很可能不是全局最优的，本文根据种群的多样性和种群在进化过程中找到最优解的波动程度，判断种群是否陷入早熟收敛，同时采用Chaos-Process混沌扰动机制处理粒子群早熟收敛状态，提高种群多样性。本文参考文献[14]，当粒子群多样性小于0.35且K代最优算法平均数在连续10代内不发生变化，则认为满足收敛条件，粒子群早熟，此时启动混沌扰动机制增加种群多样性。

混沌扰动机制Chaos-Process描述如下：

将Chaos1i[j]映射到粒子维数区间[1,n]内得到num1，然后将Chaos2i[j]映射到第num1维服务类的候选服务集中得到服务编号num2。用num2替换xi[num1]得到新的粒子位置xi_new，但Fitness(xi)＜Fitness(xi_new)，则xi=xi_new。

当种群陷入早熟收敛时，经过Chaos-Process混沌扰动机制处理使种群中所有粒子进行混沌搜索，提高种群多样性，加速全局最优解粒子以及其它粒子附近的进一步搜索，而且可以使粒子更易跳出局部极值，提高算法的寻优能力。

4.3 ICPSO算法描述

ICPSO算法首先使用Skyline操作[15]对所有服务类对应的候选服务集进行处理，剔除那些被其他服务支配的候选服务，保留可能成为最优服务组合的潜在候选者，从而得到Skyline服务。然后从每个服务类的Skyline服务中进行Web服务选择，提高了服务选择效率。采用混沌序列初始化粒子群，使初始种群保留了经典PSO算法中的随机性，同时由于混沌的特性使得种群的多样性得到提高。Chaos-Process混沌扰动机制针对粒子群易陷入早熟收敛状态，进行有效处理，提高种群多样性改善解质量。

ICPSO算法具体实现描述如下：

输入：所有服务类的候选服务集

输出：最优组合服务

Step 1：使用Skyline操作处理所有服务类的候选服务集，得到每个服务类的Skyline服务。

Step 2：设置当前迭代次数t=0，并混沌初始化粒子群中m个粒子的位置。

Step 3：计算粒子群中粒子的适应度值

找出种群中全局最优粒子下标gi，更新粒子群全局最优解

Step 10：计算粒子群多样性psdis和K代最优算术平均kma，判断粒子群是否收敛。

Step 11：If（满足收敛条件）then启动Chaos-Process增加种群多样性。

Step 12：Ift＜T（最大迭代次数）then转到Step 5。

Step 13：结束。

其中，搜索空间为n维，种群规模为m，X=(x1,x2,…,xm)表示整个粒子群。粒子i位置xi=(xi,1,xi,2,…,xi,n)，速度vi=(vi,1,vi,2,…,vi,n)，粒子i历史最优解pi=(pi,1,pi,2,…,pi,n)，全局最优解pg=(pg,1,pg,2,…,pg,n)。

5 实验设计与结果分析

本文的实验数据采用公共数据集QWS[16,17]。实验基于顺序型服务组合模型，且模型中包含7个服务类，默认情况下每个服务类的候选服务集规模为500，最大迭代次数为500次，每个候选服务有4个QoS属性，即响应时间(T，response time)、可靠性（R，reliability）、可用性（A，availability）和费用（C，cost）。QoS属性值在规定范围内均匀分布，参数取值范围参考表1。ICPSO代表本文提出的算法，CPSO代表文献[18]中提出的算法是由Wang等人[19]提出的改进粒子群算法以解决服务组合优化问题。假设种群规模m=100，对于以下实验结果，算法运行50次取平均值。

表1 随机数据集QoS属性取值范围

5.1 可行性

为验证本文提出的ICPSO算法在解决Web服务组合优化问题的可行性，将ICPSO算法与其它算法分别在不同服务候选规模下与不同迭代次数下的求解质量进行对比，实验结果如图1所示。

图1 不同算法的寻优性能

通过图1的实验结果可以看出，本文算法的寻优结果明显优于算法其它两种算法，CPSO算法与Proposed by Wang算法的寻优结果差不多。在ICPSO算法中，本文针对粒子群算法易陷入早熟收敛，导致所求得的解为局部最优解的缺点采用Chaos-Process混沌扰动机制进行早熟收敛处理。引入混沌优化的思想使种群中所有粒子进行混沌搜索，提高种群多样性，加速全局最优粒子以及其它粒子附近的进一步搜索，而且可以使粒子更易跳出局部极值，从而使更易找到更好的解。

5.2 稳定性

为验证本文提出的ICPSO算法在解决Web服务组合优化问题的稳定性，将ICPSO算法与其它算法分别在不同服务候选规模下与不同迭代次数下的运行50次实验所求得解的方差进行了对比，实验结果如图2。

通过图2的实验结果可以看出，本文的ICPSO算法在不同服务候选规模下与不同迭代次数下的方差小于其它两种算法，所以ICPSO算法具有较好的稳定性，总体上比CPSO算法好。随着候选服务规模的增加，组合服务可选方案数量也增加，因此增加了服务选择难度，总体上方差值也有小服务的增加，即候选服务规模越大选优性能稳定性越差。但由于ICPSO算法先采用Skyline操作对数据进行预处理，剔除冗余服务减少了服务选择空间，在粒子群初始化阶段，利用混沌的特征初始化种群，使初始种群中粒子位置既保留了经典PSO的随机性，又利用混沌变量的优点提高种群的多样性与搜索的遍历性，以及对于粒子群陷入早熟时的处理操作提高求解质量，增加较优组合服务被选中的几率，因此算法稳定性也有所提高。

图2 不同算法的稳定性

6 结束语

本文研究了标准粒子群算法在Web服务组合优化问题上的应用，结合Skyline技术以及混沌的思想提出一种改进的混沌粒子群算法（ICPSO），在数据预处理阶段引入Skyline操作，减少服务选择搜索空间，提高服务选择效率。在初始化阶段混沌初始化种粒子群，当种群陷入早熟收敛状态时，采用Chaos-Process混沌扰动机制增加粒子群多样性，增强全局搜索能力，提高服务组合质量。最后通过仿真实验对算法的综合性能验证，实验结果表明，ICPSO在服务优化问题上，较其他算法有更好的可行性和有效性。

[1]Papazoglou M P,Traverso P,Dustdar S,et al.Service-Oriented Computing:State of the Art and Research Challenges[J].Computer,2007,40(11):38-45.

[2]邓水光，吴朝晖.Web服务组合方法综述[J].中国科技论文在线，2008，3（2）：79-84．

[3]Zhang Y W,Cui G M,Zhao S,et al.IFOA4WSC:a quick and effective algorithm for QoS-aware service composition[J].International Journal of Web&Grid Services,2016,12(1):81-108.

[4]王尚广，孙其博，杨放春.基于全局QoS约束分解的Web服务动态选择[J].软件学报，2011，22（7）：1426-1439．

[5]Alrifai M,Risse T,Nejdl W.A hybrid approach for efficient Web service composition with end-to-end QoS constraints[J].Acm Transactions on the Web,2012,6 (2):373-382.

[6]范小芹，蒋昌俊，王俊丽，等.随机QoS感知的可靠Web服务组合[J].软件学报，2009,20（3）：546-556．

[7]张成文，苏森，陈俊亮．基于遗传算法的QoS感知的Web服务选择[J].计算机学报，2006，29（7）：1029-1037．

[8]Zhang W,Chang C K,Feng T M,et al.QoS-Based Dynamic Web Service Composition with Ant Colony Optimization[C]//Computer Software and Applications Conference(COMPSAC),2010 IEEE 34th Annual. IEEE,2010:493-502.

[9]刘莉平，陈志刚，刘爱心.基于粒子群算法的Web服务组合研究[J].计算机工程，2008，34（5）：104-106．

[10]范小芹，蒋昌俊，方贤文，等.基于离散微粒群算法的动态Web服务选择[J].计算机研究与发展，2010，47（1）：147-156．

[11]胡旺，李志蜀.一种更简化而高效的粒子群优化算法[J].软件学报，2007，18（4）：861-868．

[12]Eberhart R,Kennedy J.A new optimizer using particle swarm theory[C]//International Symposium on MICRO Machine and Human Science.1995:39-43.

[13]Alatas B,Akin E,Ozer A B.Chaos embedded particle swarm optimization algorithms[J].Chaos Solitons& Fractals,2009,40(4):1715-1734.

[14]温涛，盛国军，郭权，等.基于改进粒子群算法的Web服务组合[J].计算机学报，2013，36（05）：1031-1046．

[15]Alrifai M,Skoutas D,Risse T.Selecting skyline services for QoS-based web service composition[C]//International Conference on World Wide Web.2010:11-20. [16]Al-Masri E,Mahmoud Q H.Discovering the best web service:A neural network-based solution[C]//IEEE International Conference on Systems.IEEE,2009: 4250-4255..

[17]Al-Masri E,Mahmoud Q H.QoS-based Discovery and Ranking of Web Services[C]//Computer Communications and Networks,2007.ICCCN 2007.Proceedings of 16th International Conference on.IEEE,2007:529-534.

[18]Wang L,He Y X.Web Service Composition Based on QoS with Chaos Particle Swarm Optimization[C]// Wireless Communications Networking and Mobile Computing(WiCOM),2010 6th International Conference on.IEEE,2010:1-4.

[19]Wang S G,Sun Q B,Zou H,et al.Particle Swarm Optimization with Skyline Operator for Fast Cloud-based Web Service Composition[J].Mobile Networks&Applications,2013,18(1):116-121.

Web service composition optimization based on chaotic mechanism and improved particle swarm optimization

WANG Yan,LIU Yu-lan,JING Zi-hui,ZHANG Yi-wen*
(Key Laboratory of Intelligent Computing and Signal Processing,Anhui University,Hefei Anhui230031,China)

with the rapid development of internet and big data,it becomes a hotspot to select appropriate ones from substantial web services and composite them to meet users’requirements.So an improved chaotic particle swarm optimization algorithm(ICPSO)is presented and applied to web service composition optimization problem.As the traditional PSO is easy to fall into premature convergence and local optimum,chaotic mechanism is introduced to make the particle jump out of local optimum,thereby enhancing population diversity and improving the optimization capacity.Finally the feasibility and effectiveness of ICPSO are verified through simulation experiments.

service composition;improved chaotic particle swarm optimization algorithm;chaotic mechanism;QoS

TP311

A

1004-4329（2017）01-066-07

10.14096/j.cnki.cn34-1069/n/1004-4329（2017）01-066-07

2016-07-15

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

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