计 算 机 工 程 第 37 卷 第17期
V ol.37 No.17 Computer Engineering
文章编号：1000—3428(2011)17—0130—03·人工智能及识别技术·
2011年9月
September 2011
文献标识码：A
中图分类号：TP 301.6
改进粒子群优化算法在服务组合中的应用
胡 珀，娄渊胜
(河海大学计算机与信息学院，南京 210098)
摘 要：针对标准粒子群优化(PSO)算法存在收敛速度慢、容易陷入局部最优的问题，提出一个改进的PSO算法，该算法设计一种新的惯性权重，在粒子搜索的不同阶段采用不同的计算公式计算惯性权重，并引入自适应变异策略和线性变化的学习因子。实验结果表明，该算法的收敛性等性能比基本粒子群算法有明显提高，能较好地解决非线性问题。 关键词：粒子群优化；惯性权重；自适应变异；服务组合优化
Application of Improved Particle Swarm Optimization Algorithm
in Service Composition
HU Po, LOU Yuan-sheng
(College of Computer & Information, Hohai University, Nanjing 210098, China)
【Abstract】As the Particle Swarm Optimization(PSO) algorithm has some shortcomings of slow convergence and easy to fall into the local extreme value, this paper presents a improved particle swarm optimization with a new inertia weight. In different stages of the algorithm run, a corresponding formula is used to calculate the inertia weight. In Addition, adaptive mutation and linear-changed learning factor are introduced. The relational test simulation experiment is carried out. Experimental results show that the improved algorithm is feasible and efficient, it can solve norlinear problem. 【Key words】Particle Swarm Optimization(PSO); inertia weight; adaptive mutation; service composition optimization DOI: 10.3969/j.issn.1000-3428.2011.17.044
1 概述
粒子群优化(Particle Swarm Optimization, PSO)算法最早是在1995年由Eberhart和Kennedy[1]共同提出的，其基本思想是受他们早期对许多鸟类的群体行为进行建模与仿真研究结果的启发。但是基本粒子群算法也存在收敛慢、易陷入局部极值等缺点。因此，研究人员提出了多种粒子群改进方法，如线性改变惯性权重、引入选择算法子。后来Higashi等分别提出了自己的变异PSO算法，希望通过引入变异算法跳出局部极值点，从而提高算法的全局搜索能力。在粒子群算法的惯性权重设计上，之前的研究倾向于将惯性权重设定为一个固定值，后来出现了动态变化的惯性权重，包括线性变化和非线性变化，但都是单一的采用一种变化方式。
本文考虑采用惯性权重动态非线性变化与线性变化相结合的改进方法，在不同阶段采用不同变化方式，并用于对函数进行优化。
在每次迭代过程中，粒子根据下列公式更新速度和位置：
k+1kkkvid=vid+c1r1(pid−zid)+c2r2(pgd−zid) (1) k+1kk+1zid=zid+vid (2)
2 基本粒子群算法
在粒子群算法中，每个个体称为一个“粒子”，每个粒子
代表一个潜在的解。举例来说，在一个D维的搜索空间中，每个粒子看作是空间中的一个点。假如粒子群由m个粒子构成。zi=(zi1,zi2,
计 算 机 工 程 第 37 卷 第17期
V ol.37 No.17 Computer Engineering
文章编号：1000—3428(2011)17—0130—03·人工智能及识别技术·
2011年9月
September 2011
文献标识码：A
中图分类号：TP 301.6
改进粒子群优化算法在服务组合中的应用
胡 珀，娄渊胜
(河海大学计算机与信息学院，南京 210098)
摘 要：针对标准粒子群优化(PSO)算法存在收敛速度慢、容易陷入局部最优的问题，提出一个改进的PSO算法，该算法设计一种新的惯性权重，在粒子搜索的不同阶段采用不同的计算公式计算惯性权重，并引入自适应变异策略和线性变化的学习因子。实验结果表明，该算法的收敛性等性能比基本粒子群算法有明显提高，能较好地解决非线性问题。 关键词：粒子群优化；惯性权重；自适应变异；服务组合优化
Application of Improved Particle Swarm Optimization Algorithm
in Service Composition
HU Po, LOU Yuan-sheng
(College of Computer & Information, Hohai University, Nanjing 210098, China)
【Abstract】As the Particle Swarm Optimization(PSO) algorithm has some shortcomings of slow convergence and easy to fall into the local extreme value, this paper presents a improved particle swarm optimization with a new inertia weight. In different stages of the algorithm run, a corresponding formula is used to calculate the inertia weight. In Addition, adaptive mutation and linear-changed learning factor are introduced. The relational test simulation experiment is carried out. Experimental results show that the improved algorithm is feasible and efficient, it can solve norlinear problem. 【Key words】Particle Swarm Optimization(PSO); inertia weight; adaptive mutation; service composition optimization DOI: 10.3969/j.issn.1000-3428.2011.17.044
1 概述
粒子群优化(Particle Swarm Optimization, PSO)算法最早是在1995年由Eberhart和Kennedy[1]共同提出的，其基本思想是受他们早期对许多鸟类的群体行为进行建模与仿真研究结果的启发。但是基本粒子群算法也存在收敛慢、易陷入局部极值等缺点。因此，研究人员提出了多种粒子群改进方法，如线性改变惯性权重、引入选择算法子。后来Higashi等分别提出了自己的变异PSO算法，希望通过引入变异算法跳出局部极值点，从而提高算法的全局搜索能力。在粒子群算法的惯性权重设计上，之前的研究倾向于将惯性权重设定为一个固定值，后来出现了动态变化的惯性权重，包括线性变化和非线性变化，但都是单一的采用一种变化方式。
本文考虑采用惯性权重动态非线性变化与线性变化相结合的改进方法，在不同阶段采用不同变化方式，并用于对函数进行优化。
在每次迭代过程中，粒子根据下列公式更新速度和位置：
k+1kkkvid=vid+c1r1(pid−zid)+c2r2(pgd−zid) (1) k+1kk+1zid=zid+vid (2)
2 基本粒子群算法
在粒子群算法中，每个个体称为一个“粒子”，每个粒子
代表一个潜在的解。举例来说，在一个D维的搜索空间中，每个粒子看作是空间中的一个点。假如粒子群由m个粒子构成。zi=(zi1,zi2,