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

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

基于服务质量(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.