改进粒子群优化算法在服务组合中的应用

改进粒子群优化算法在服务组合中的应用

胡 珀，娄渊胜

(河海大学计算机与信息学院，南京 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

计 算 机 工 程 Computer Engineering 第37卷 第17期

V ol.37 No.17 2011年9月

September 2011

·人工智能及识别技术· 文章编号：1000—3428(2011)17—0130—03文献标识码：A

中图分类号：TP 301.6

1 概述

粒子群优化(Particle Swarm Optimization, PSO)算法最早是在1995年由Eberhart 和Kennedy [1]共同提出的，其基本思想是受他们早期对许多鸟类的群体行为进行建模与仿真研究结果的启发。但是基本粒子群算法也存在收敛慢、易陷入局部极值等缺点。因此，研究人员提出了多种粒子群改进方法，如线性改变惯性权重、引入选择算法子。后来Higashi 等分别提出了自己的变异PSO 算法，希望通过引入变异算法跳出局部极值点，从而提高算法的全局搜索能力。在粒子群算法的惯性权重设计上，之前的研究倾向于将惯性权重设定为一个固定值，后来出现了动态变化的惯性权重，包括线性变化和非线性变化，但都是单一的采用一种变化方式。

本文考虑采用惯性权重动态非线性变化与线性变化相结合的改进方法，在不同阶段采用不同变化方式，并用于对函数进行优化。

2 基本粒子群算法

在粒子群算法中，每个个体称为一个“粒子”，每个粒子

代表一个潜在的解。举例来说，在一个D 维的搜索空间中，每个粒子看作是空间中的一个点。假如粒子群由m 个粒子构成。12(,,,)i i i iD z z z =z 为第i 个粒子(i =1,2,…,m )的D 维位置矢量，根据先前设定好的适应度函数计算i z ，用来衡量粒子的优劣程度；12(,,,,,)i i i id iD v v v v v = 为粒子i 的飞行速度，即粒子的移动距离12(,,,,,)i i i id iD p p p p p = 为粒子迄今为止搜索到的最优位置；12(,,,,,)g g g gd gD p p p p p = 为整个粒子群迄今为止搜索到的最优位置。

在每次迭代过程中，粒子根据下列公式更新速度和位置：

11122()()k k k k id id id id gd id v v c r p z c r p z +=+?+? (1) 11k k k id id id z z v ++=+ (2)

其中，i =1,2,…,m ；d =1,2,…,D ；k 是迭代次数；r 1和r 2为[0,1]之间的随机数，这2个参数用来保持群体的多样性；c 1和c 2称为学习因子，也叫加速因子，它们使粒子具有自我总结和向群体优秀个体学习的能力，从而向自己的历史最优点和群体内的历史最优点靠近。这2个参数对粒子群算法的收敛起的作用不是很大，但是如果适当调整这2个参数，可以减少局部最小值的困扰，同时也会使收敛速度变快。由于粒子群算法中没有实际的机制来控制粒子的速度，因此有必要对速度的最大值进行限制。式(1)的第2项是认知部分，代表粒子对自身的学习，而第3项是社会部分，代表粒子之间的协作。式(1)正是粒子根据它上一次迭代的速度、当前位置和自身最好经验与群体最好经验之间的距离来更新速度。然后粒子根据式(2)飞向新的位置。

3 粒子群算法的改进

3.1 基本思路

Shi 和Eberhar 在1998年正式引入惯性权重的概念[2]。基本粒子群算法的速度公式的右边包括3个部分：第1部分是粒子当前的速度；第2部分和第3部分是粒子对速度的调整。如果没有后面两部分，粒子将会以恒定的速度朝一个方向飞

作者简介：胡 珀(1985－)，男，硕士研究生，主研方向：人工智能，分布式计算；娄渊胜，副教授、博士、CCF 高级会员 收稿日期：2011-02-22 E-mail ：4612705hupo@https://www.wendangku.net/doc/056344836.html,

第37卷 第17期 131

胡 珀，娄渊胜：改进粒子群优化算法在服务组合中的应用 行，直到达到边界，这样粒子很难找到最优解。文献[2]在基

本粒子群速度公式的基础上添加了一个惯性权重，其公式为：

11122()()k k k k

id id id id gd id v wv c r p z c r p z +=+?+? (3)

惯性权重w 对算法性能起着重要作用。当惯性权重较小时，如果粒子能够找到全局最优，那么它所经历的搜索时间是很短的，所有的粒子能够快速汇集在一起。当惯性权重较大时，粒子群算法更像是全局搜索算法，它趋向于探索新的区域。这就需要更多的迭代次数来寻找全局最优解，并有可能找不到全局最优。文献[3]提出一种混合粒子群算法提高算法的搜索效率。

本文在基本粒子群算法的基础上，针对基本算法存在的问题，分析了加入惯性权重的粒子群速度公式，各个参数对算法性能的影响，并从3个方面对算法进行改进。

3.2 惯性权重策略

本文采用惯性权重非线性与线性变化相结合的方案来改进基本粒子群算法的性能，在粒子群搜索的前一个阶段惯性权重以一个初始值非线性减小，这样就保证了算法初期，粒子趋向于探索新区域寻找最优解，而当算法到达后一阶段时，惯性权重线性减小，使算法快速收敛，实验结果表明了本文采用的惯性权重变化策略的有效性。下面是本文所采用的惯性权重公式：

max

'

'min e /2()/2

d M

M w v d M w d w w w d d M M

???×??=????×???≥ (4) 其中，d 是算法当前的迭代次数；M 是最大迭代次数；,w 是前半阶段结束搜索时的惯性权重的即时值。

3.3 自适应变异策略

在处理非线性的函数优化问题上粒子在寻优过程中很容易陷入局部最优点而停止迭代，不同于其他算法在算法运行的整个阶段都加入变异机制，为使粒子能够跳出局部极值点，提高算法性能，本文在算法运行的初期加入自适应变异机制，使算法在初期能够跳出局部最优点，这样能够进一步提高算法的性能。本文的实验结果也说明了这一机制的合理性。

算法1 自适应变异伪代码

(1)for i=1 to MaxDat/2 //i 为当前迭代次数，MaxDat 为最大迭代次数。

(2)While rand>T //rand 为随机生成的粒子的位置，T 为给定的值。

(3)re-initialization(rand)//重新初始化粒子位置。

在算法1中，当粒子的位置向量某一维的值超过设定的值时，粒子的位置就会被重新初始化，这样就能在一定程度上克服基本算法在初期容易陷入局部最优的缺点，使算法能够及时跳出局部最优点。

3.4 学习因子

粒子群速度公式中的c 1和c 2通常被称作学习因子，也称加速因子。通常情况下它们为固定值并且相同，这种做法虽然被普遍采用，但是它没有考虑到粒子的反馈信息对公式中参数的影响。因此，Ratnaweera 采用了改变加速因子的方法来平衡搜索的随机性，开始时给c 1一个较大的值，给c 2一个较小的值，使粒子有较好的自身认知能力可以自由分布到空间中，增加粒子的多样性。随迭代次数的增加，c 1线性递减，c 2线性递增：

1111()c f c d

c c c c G

=+

? (5) 2222()c f c d

c c c c G

=+

? (6) 本文算法采用上述的学习因子设计方案。

4 仿真实验与分析

4.1 实验环境说明

本文实验硬件条件均为Inter Pentium CPU 3.2 GHz ，1 GB 内存，软件环境为Windows XP ，算法编译环境为Matlab 6.5。为了检验改进算法的性能，本文采用Ackley 函数[4]进行仿真：

1111min ()exp exp cos(2π)n j j f x c x c e

n =???

=???++∑???????其中，(5,5),1,2,,j x j n ∈?= 。当n =2时该函数全局最优为f (x *)=f (0,0)，这是一个无约束优化问题，该函数存在许多局

部最优解的陷阱。参数设置如下：Ackley 函数120c =，

2.7182e =。基本粒子群算法12,c c 均采用固定值，取1.494 45。

改进粒子群算法中12(),,w d c c 采用式(4)~式(6)进行更新，算法的精度设置为410?，迭代次数为1 000，粒子群规模为20，搜索空间2维，程序运行50次取平均值。 4.2 结果分析

基本算法和本文算法的性能比较如表1所示。

表1 Ackley 函数性能对照

算法 平均迭代次数 平均优化极值

平均CPU 算法

基本PSO 算法 253.952 0 ?0.003 8 0.523 6 本文算法

53.260 0

?0.001 5

0.042 5

为了更为直观地比较基本粒子群算法和本文改进算法的性能，图1、图2给出了2种算法的寻优曲线。

图1 基本粒子群算法适应值变化曲线

图2 本文算法适应值变化曲线

以上仿真结果表明本文所用的改进的粒子群算法较基本粒子群算法有了性能上的提高，主要表现在以下3点：

(1)新的惯性权重策略使算法的收敛性提高。

(2)自适应变异策略的引入使改进算法能够及时跳出局部最优解。

(3)平均迭代次数和平均搜索时间较基本粒子群算法均

132 计算机工程2011年9月5日

有所减小。

5 改进粒子群算法在服务组合优化中的应用

近年来国内外学术界和行业界围绕着Web服务组合开展

了大量的研究工作，提出了多种算法的Web服务组合的优化

方法。文献[5]提出了一种基于离散粒子群算法的服务组合优

化方法；本文提出的改进粒子群算法也将其应用到了服务组

合优化中。

5.1 问题描述

服务组合问题可以看做是从m个服务类中按一定顺序选

取合适的原子服务组合而成的复杂服务。服务类是指具有相

同功能属性和不同QoS属性的一组服务的集合。服务组合问

题如图3所示，其中，S、D是另外加入的虚拟初始节点和结

束节点，WS1、WS2等表示一个服务类，它们由具有相同功

能属性不同QoS值的服务组成。由此Web服务组合问题可以

看为是一个从初始节点S到结束节点D的路径选择问题。每

条可行的路径就是服务组合问题的一个解。运用改进粒子群

算法进行求解的基本思想如下：首先按照一定的规则产生一

定数量的粒子，每个粒子都是一个可能的解，然后粒子按照

改进的算法过程进行迭代，产生具有更好适应值的粒子，这

一过程不断进行，直到算法终止。

图3 服务组合优化示意图

5.2 初始粒子群生成及粒子的编码方式

为了能够产生初始粒子群，本文利用Dijkstra算法产生

多条从源点至目的节点的路径，用来得到一组从S到D的初

始路径集。针对路径的单个度量指标，使用一次Dijkstra算

法只能产生一条最短路径，本文使用线性组合方法将各链路

的代价和时延线性组合起来，根据聚合的单一度量标准寻找

最“短”路径。对链路(u,v)而言，此时权重变为：

(,)(,)(,)

W u v Cost u v Cost u v

αβ

=×+×(7)

其中α、β为位于[0,1]之间的乘数因子，且满足：α+β=1。

本文采用算法2来生成初始粒子群：

算法2 Init

输入目标函数集F，群体规模N

输出初始群体P

Begin

(1) P←Ф

(2) while(|P|

(3)P→PUConstr(SR(S,T))

(4)Goto(2)

(5)Output P

End

当初始粒子群生成之后本文对初始群体中的个体进行整

数定长编码。以图4为例进行说明，首先对图4中的所有粒

子进行编号，初始节点和结束节点的取值为?1，其他节点的

取值为0或者其对应编号。假设

12

(,,,)

i i i iD

X X X X

= 表示一

个粒子，在图4中(1,1,2,0,0,5,1)

X=??表示一条经过S1、S2、

S5的组合路径。

图4 服务组合优化实例

5.3 粒子适应值的计算及运算规则

结合服务组合优化问题，本文选取时间、价格和可靠性

作为服务的QoS属性，下面给出这3种属性的计算方式，以

图4中一条经过S1、S2、S5的路径为例进行说明，对于该

粒子本文计算它的时间QoS(time)、价格QoS(cost)、可靠性

QoS(rel)：

(time)125

(cost)125

(rel)125

QoS

QoS

QoS

t t t

c c c

r r r

?=++

?

=++

?

?=××

?

(8)

然后，采用加权综合的方法来计算粒子的总体适应值。

当粒子在飞行过程中发现了更优秀的粒子，那么，粒子

会按照改进粒子群算法的位置变化操作来进行位置的变更，

本文定义了改进粒子群算法中粒子更新操作的具体内容。由

5.2节的编码方式知道，每个粒子按照改进公式的速度公式更

新自己的速度，而位置的更新具体到服务组合优化问题中，

为了便于理解，给出下面一个例子来说明问题，在图4中

(-1,1,2,0,0,5,-1)、(-1,1,0,3,0,5,-1)表示2个粒子，假设服务2、

服务3属于同一个服务类，当粒子搜索过程中发现后面粒子

的适应值优于前一个粒子时候，便会按照式(2)进行位置的更

新，此时对照粒子编码的变化，前一个粒子选择了具有更优

QoS值的组合。因此，式(2)的操作时将粒子的某一维的位置

更换为具有更优适应值的服务实例，来完成位置的更新。

6 结束语

本文针对基本粒子群算法存在的不足，对算法进行相关

的改进，并进行仿真实验验证了改进算法的优越性，最后对

改进粒子群算法用于服务组合优化问题进行了相关讨论，确

定了合理的编码方式、粒子适应值的计算和粒子的运算规则，

为进一步的工作打下基础。

参考文献

[1] Eberhart R C, Kennedy J. A New Optimizer Using Particle Swarm

Theory[C]//Proceedings of the 16th International Symposium on

Micro and Human Machine Science. Piscataway, USA: [s. n.],

1995: 39-43.

[2] Shi Y, Eberthart R C. A Modified Particle Swarm Optimizer[C]//

Proceedings of IEEE International Conference on Evolutionary

Computation. Piscataway, USA: IEEE Press, 1998: 69-73.

[3] 俞靓亮, 王万良, 介婧. 基于混合粒子群算法的旅行商问题

求解[J]. 计算机工程, 2010, 36(11): 183-184.

[4] Janson S, Middendorf M. A Hierarchical Particle Swarm Optimizer

and Its Adaptive Variant[J]. IEEE Trans. on Systems, Man, and

Cyberneticss, 2005, 35(6): 1272-1282.

[5] Fan Xiaoqin, Jiang Changjun, Fang Xianwen. An Efficient Approach

to Web Service Selection[C]//Lecture Notes in Computer Science.

Berlin, Gemary: Springer, 2009: 271-280.

编辑索书志