基于改进BPSO的Web服务组合选择算

基于改进BPSO的Web服务组合选择算法黄海芳1,2，孙建华1(1.湖南大学计算机与通信学院，长沙410082；2.湖南信息职业技术学院计算机工程系，湖南望城410200)摘要：现有Web服务组合中服务选择技术不足。为此，提出一种基于改进的二进制粒子群(BPSO)的高效服务选择算法。引入变异算子和线性递减惯性权重，克服传统的二进制粒子群算法的早熟收敛问题，增强其全局寻优性能。使用粒子记忆性对不满足约束条件的个体进行修正，使算法在可行解空间搜索，以提高寻优效率。实验结果表明，该算法具有可行性和收敛性。关键词：Web服务组合；二进制粒子群算法；服务选择；服务质量CombinationSelectionAlgorithmforWebServiceBasedonImprovedBPSOHUANGHai-fang1,2,SUNJian-hua1(1.SchoolofComputerandCommunication,HunanUniversity,ChangshaHunan410082,China;2.DepartmentofComputer,HunanCollegeofInformation,WangchengHunan410200,China)【Abstract】AglobaloptimalalgorithmbasedonBinaryParticleSwarmOptimization(BPSO)ispresentedtoresolveservicesselectioninWebservicecomposition.Toavoidconvergingtoofast,thealgorithmisimproved.Themutationoperationandlinearlydecreasinginertiaweightareused.Meanwhile,basedonthememoryofparticles,theindividualsthatdonotconformtotheconstraintconditionsaremodifiedtomakethealgorithmsearchinginthespaceoffeasiblesolution,thusthesearchingefficiencyisgreatlyimproved.Experimentalresultsshowthealgorithmhasfeasibilityandconvergence.【Keywords】Webservicescomposition;BinaryParticleSwarmOptimization(BPSO);serviceselection;qualityofserviceDOI:10.3969/j.issn.1000-3428.2011.24.000计算机工程ComputerEngineering第37卷第24期Vol.37No.242011年12月December2011·人工智能及识别技术·文章编号：1000—3428(2011)24—00—0文献标识码：A中图分类号：TP301.61概述随着Web服务的快速发展和应用，越来越多的企业把应用程序作为Web服务共享在Internet上，然而单个Web服务只能提供一些比较单一的功能，无法满足复杂应用的需求，因此需要对单一服务所提供的各种功能进行组合以形成新的、功能更强大的服务，以满足用户的复杂需求。同时随着Web服务数量的增加，出现了许多服务提供者提供的服务具有相同或相似操作(功能)，因此基于功能的Web服务选择已经不能满足用户的需求，需要用户通过一些非功能性的约束属性来选择。近年来，人们开始用粒子群算法去求解基于QoS(QualityofServices)属性约束的Web服务组合选择问题。文献[1]提出一种基于粒子群算法求解Web服务组合中基于QoS的服务选择。文献[2]提出一种多目标粒子群优化算法来求解基于QoS的Web服务组合问题。粒子群算法具有计算简单、鲁棒性好等优点，具有较强的通用性，但存在“早熟”收敛，容易在后期陷入局部极值等缺点。本文针对粒子群算法的缺点，提出一种自适应变化惯性权重、变异操作改进的离散二进制粒子群(BPSO)算法来求解基于QoS的Web服务组合选择。2问题描述Web组合服务的功能可以分成多个子功能(任务)，每个子功能会有多个候选服务，因此会存在很多完成组合服务功能的组合方案，这些组合方案在任务数量、组合顺序上是不同的。本文将一个任务组合称为一条从起始任务到终止任务的路径。在服务组合过程中，每个任务会存在多个服务组件与其对应，这些服务组件具有对应任务要求的功能但具有不同的QoS属性，因此每条路径又存在多个具有不同QoS属性的组合方案。根据各子功能(任务)间的执行逻辑关系，大部分组合服务都可以串联、并联、选择和循环4种基本模型组合而成，因此整个Web组合服务的QoS属性可通过这4种基本模型的QoS计算公式来获取[3]。本文从执行时间T(Time)、可靠性R(Reliability)、信誉等级Rep(Reputation)和执行费用C(Cost)4种QoS属性对Web服务进行QoS建模。组合服务中单个Web服务ijS(第i个任务的第j个侯选服务)的服务质量模型为(,,,)iTCRepRsijijijijQQQQQ。其中，T和C属性是减量型的，即其值越低，质量越高；R和Rep是增量型的，即其值越大，质量越高。Web服务组合的选择问题(全局优化问题)可描述如下：(1)目标函数11Maxknijijijxf(1)(2)约束条件11knijijijxrQ≤11nijjx(i=1,2,…,k)(2)其中，ijx=0或1，如果服务ijS被选中，则ijx=1，否则ijx=0，ijf为第i个任务的第j个侯选服务的效用函数；ijr为第i个任基金项目：湖南省教育厅科学研究项目基金资助项目(09C1257)作者简介：黄海芳(1981－)，女，讲师、硕士研究生，主研方向：Web服务，进化计算；孙建华，副教授、博士收稿日期：2011-07-18E-mail：[e-mail]2计算机工程2011年12月20日务的第j个侯选服务所需的资源；Q为用户设置的该资源的上限。3粒子群算法文献[4]提出粒子群优化(ParticleSwarmOptimizer,PSO)算法是在模拟鸟群觅食行为的基础上，发展而来的一类基于群体智能的随机优化算法。假设在一个D维的搜索空间中，有M个粒子组成一个种群，其中，第i个粒子位置iX=(1ix,2ix,…,iDx)，速度表示为iV=(1iv,2iv,…,iDv)。迄今为止第i个粒子本身搜索到的最优位置记为ipb=(1ipb,2ipb,…,iDpb)，迄今为止整个种群搜索到的最优位置记为gb=(1gb,2gb,…,Dgb)，第i个粒子在第d(d=1,2,…,D)个维子空间的速度和位置更新如下：11122ttttttididididdidvwvcrpbxcrgbx(3)11tttidididxxv(4)其中，tidv是粒子i在第t次迭代中第d维的速度，通常要受到最大速度maxV和最小速度minV的限制，其取值被限制在允许范围内；1c、2c是加速系数；1r、2r为在[0,1]范围内的随机数；w表示粒子“飞行”的速度惯性。为了解决实际工程中广泛存在的离散组合优化问题，在1997年提出二进制粒子群(BinaryParticleSwarmOptimization,BPSO)算法。与连续PSO相比，在二进制编码中，该模型限制tidx和tidpb只能取0或1，而对速度不作这种限制。二进制粒子群算法中的速度向量不再是位置变化，而是作为粒子位置取1或0的概率，引入了模糊函数Sigmoid，迭代式(4)变为：1()0tidtidrandSigvx其他(5)其中，()rand是0~1之间的随机数。PSO算法具有收敛快、简单灵活的特点，但是粒子总是向着自身和群体最好的位置飞行，信息单向流动，容易陷入局部最优和“早熟”。4基于改进的BPSO的Web服务组合选择算法4.1编码规则针对问题模型，假设Web服务组合中有k个任务，每个任务有n个侯选服务，采用矩阵ijxX(i=1,2,…,k；j=1,2,…,n)，其中，ijx表示第i个服务类中第j个服务的状态，用0、1表示，0表示服务未被选中；1表示服务被选中。因此粒子的位置编码为kn的0-1矩阵；速度编码为kn的实数矩阵。4.2初始化粒子群为了保证产生的初始粒子均为可行解，使算法在可行解区域内开始寻优，本文采用一种新的策略来生成粒子。假设粒子群的粒子数为M，首先随机初始化M个粒子的当前位置，即产生一个kn的0矩阵(元素均为0)，然后在每一行中随机选取一个元素的值设置为1。如果某些粒子的位置不是可行解，即不满足式(2)，则在矩阵中随机取一个值为1的元素置为0，并在该元素所在行中另外选择一个不同的元素置为1，直到生成满足约束条件的粒子(解)。为防止Sigmoid函数饱和，粒子的速度矩阵中的每一个元素的值在[−4,+4]间随机选取进行初始化。4.3位置与速度的更新更新规则如下：(1)在PSO中，惯性权重w的值对粒子的搜索能力有很大的影响，不同的w值使得粒子群具有不同的搜索能力。研究发现，较大的惯性权重可以加大粒子下一步的飞行速度，有利于粒子跳出局部极值，而较小的惯性权重可以减小粒子下一步的飞行速度，使得粒子在局部区域进行搜索，更快的达到算法的收敛，于是采用惯性权重随着迭代次数线性递减的算法。计算式为：maxminmaxmax(6)其中，maxw为最大惯性权值，取maxw=0.9；minw为最小惯性权值，minw=0.4；T为当前迭代次数；maxT为算法总的迭代次数。(2)在进化算法当中，变异算子可增加种群的多样性，从而避免早熟收敛。因此针对粒子群算法中的早熟现象，考虑到粒子在当前最优位置的作用下，可能发现更好的位置，加入遗传算法中的变异操作[5]。在整个粒子群中，对每个粒子的每一位赋一个[0,1]之间的随机数，如该随机数小于预先给定的变异概率，则对这一位进行变异，如果原来这一位是1，则变为0，如果原来为0，则变为1。虽然变异操作可能会降低算法的收敛速度，但是由于增加了种群的多样性，使得算法的全局搜索能力增加，避免陷入局部极值。(3)满足约束条件的粒子经过式(3)和式(5)迭代更新和变异后，产生的新粒子不一定满足约束条件：11nijjx即位置矩阵中某一行值为1的元素不止一个或全为0，为此引入粒子的记忆功能[6]。先用一个数组记录目前位置已含有1的列，在粒子的每个元素[i,j]更新其位置时，通过该数组来判断元素[i,j]所在的第j列中前i−1个元素中是否已经含有1，如未含有，且满足()tidrandSigv，则该元素才可更新为1，并把j记录在“记忆”数组中；若不能同时满足这2个条件，则该元素更新为0。每个粒子的位置和速度更新后，都要判断是否满足式(2)约束条件，满足则跳出循环，否则重新赋值更新直至满足约束为止。4.4算法步骤算法步骤如下：(1)初始化设置粒子群规模，加速系数和最大允许迭代次数maxT，随机产生满足约束条件粒子初始位置和初始速度。(2)使用目标函数式(1)对所有初始粒子评价适应度值，求出初始全局最优解gb；个体历史最优解ipb。(3)设迭代次数T=1。(4)判断是否达到最大迭代次数或粒子群迄今为止搜索到的最优位置连续没有变化的次数超过某一给定值，如未达到，按照式(3)、式(5)，和第4.3节更新粒子位置和速度，并对种群中的个体以一定的变异概率进行变异操作，得到满足约束条件的粒子，否则转步骤(7)。(5)用目标函数重新评价每个粒子的适应度值，如果粒子适应度优于ipb的适应度，则将ipb设置为新位置；如果粒子适应度优于gb，则更新全局最优解。(6)1TT，转步骤(4)。(7)输出解集，算法结束。5实验结果