基于改进粒子群优化算法的Web服务组合

摘要

It is an NP problem to generate the composition service fast and dynamically from a large number of candidate services under the users functional and non-functional requirements.Particle Swarm Optimization (PSO) is an effective approach to solve this kind of problem.There is some deficiency partly or entirely existing in services composition approaches based on PSO.It can only supporting specific workflow or the workflow includeding only sequence pattern.It can only use the number of iterations as the termination condition;not avoiding the premature convergence problem or the result of that being unsatisfactory.This paper proposes a web service composition method based on modified particle swarm optimization which supports sequence,parallel and choice patterns.The main improvements of our PSO are:adding a few initial particles generated by local optimization strategy;adjusting the setting proposal of cognitive factors and social factors;proposing the concept of diversity in the population and presenting a diversity of healing mechanisms to avoid premature convergence;setting an early termination condition of the iterative operations.The simulation experiments demonstrated the advantages of the proposal in time cost and method optimization.%针对现有的基于PSO的服务组合方法存在只能支持具体的工作流或仅包含顺序结构的工作流、仅使用迭代次数作为终止条件、未处理种群早熟或处理效果不是很理想等问题,提出了一种基于改进的粒子群优化算法的Web服务组合方法.它可支持包含顺序、并发与选择模式的工作流;向初始粒子中添加了少量通过局部优选策略生成的粒子;调整了认知系数和社会系数的设置方案;引入种群的多样性概念,提出了一种早期多样性修补机制以避免早熟;设定了一种提前终止迭代操作的条件.实验结果表明,该算法在寻优效果与时间开销上具有一定优势.