基于多目标粒子群优化算法的Web服务组合  

Web service composition based on multi-objective particle swarm optimization algorithm

作　　者：徐涛[1,2] 王新环[1,2] 

机构地区：[1]中国民航大学计算机科学与技术学院,天津300300 [2]中国民航信息技术科研基地,天津300300

出　　处：《计算机工程与设计》2010年第18期4076-4081,共6页Computer Engineering and Design

基　　金：国家863高技术研究发展计划基金项目(2006AA12A106);国家自然科学基金项目(60979011);天津市应用基础及前沿技术研究计划基金项目(09JCYBJC02300)

摘　　要：基于服务质量(QoS)的Web服务组合是一个非线性、多目标优化求解问题,属于NP难问题。提出一种多目标粒子群优化算法来求解基于QoS的Web服务组合问题,在Web服务组合模型中考虑了服务执行代价、时间、可用性等五方面的因素。针对基于QoS的Web服务组合特点,借鉴运动学速度分解原理对粒子每维的速度进行相应分解,采用多目标指导粒子的飞行;基于Pareto支配关系来更新粒子的个体极值,采用精英归档技术维持种群多样性,粒子的全局极值由外部档案库中的非劣最优解提供;针对粒子群易陷入局部最优问题,采用了变异策略来改善。与基于遗传算法的Web服务组合算法相比,基于多目标粒子群优化的Web服务组合算法可以快速收敛,并获得综合QoS较好的解。Web service composition based on quality of service （QoS） is a nonlinear, multi-objective optimization problem which belongs toNP-hard problem. A new multi-objective particle swarm optimization （MOPSO） algorithm is proposed to solve the problem. Five objectives, such as execution cost, execution duration and availability are considered in the algorithm. The velocity of each dimension of particle is decomposed with the help of the kinematics principle of resolution of velocity. The particles fly under the direction ofmultipleobjectives. The best particle position is updated based on Pareto dominance relationship. Elitismarchivingtechniqueofnon- dominated solutions is used for keeping diversity and global particle best position is provided by non-inferior solutions in the archive. Since the solutions are prone to stagnant, variation strategy is employed. Compared with Web service composition algorithm based on genetic algorithm, the experimental results of MOPSO are better.

关 键 词：WEB服务组合 服务质量 多目标粒子群 PARETO最优集 速度分解 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]