ARTICLE IN PRESS
S1051-2004(05)00171-5/FLA AID:620 Vol.•••(•••) [+model] P.4 (1-17)
YDSPR:m3SC+ v 1.53 Prn:22/02/2006; 10:15
ydspr620 by:R.M. p. 4
4 Q. Guo et al. / Digital Signal Processing ••• (••••) •••–•••
Using the above equation, a certain velocity that gradually gets close to pbest and gbest can be calculated. The
current position (searching point in the solution space) can be modified by the following equation:
x
k+1
id
= x
k
id
+ v
k+1
id
. (5)
Velocities of particles on each dimension are clamped by a maximum velocity V
max
. If the sum of accelerations
would cause the velocity on that dimension to exceed V
max
, which is a parameter specified by the user, then the
velocity on that dimension is limited to V
max
. V
max
influences PSO performance sensitively. A larger V
max
facilitates
global exploration, while a smaller V
max
encourages local exploitation [29].
The constants c
1
and c
2
represent the weighting of the stochastic acceleration terms that pull each particle toward
pbest and gbest positions. Low values allow particles to roam far from target regions before being tugged back. On the
other hand, high values result in abrupt movement toward, or past, the target regions. Hence, the acceleration constants
c
1
and c
2
were often set to be 2.0 according to past experience.
The inertia weight w is introduced in [30] to improve PSO performance. The model using (6) is called “inertia
weights approach (IWA).” Suitable selection of inertia weight w provides a balance between global and local explo-
ration and exploitation, and on average results in less iterations required to find a sufficiently optimal solution. As
originally developed, the inertia weight w is set according to the following equation:
w = w
max
−
w
max
− w
min
iter
max
× k, (6)
where w
max
is the initial weight, w
min
is the final weight, iter
max
maximum iteration number.
3.2. Constriction factor approach (CFA) [20,31,32]
The basic system equation of PSO ((4)–(6) in IWA) can be considered as a kind of difference equations. In later
studies, for insuring convergence, an analysis of the algorithm from mathematical aspects was given by Clerc [31,32],
who proposed the use of a constriction factor χ . The algorithm was named the constriction factor approach (CFA).
The velocity of CFA (simplest constriction) can be expressed as follows:
v
k+1
id
= χ(v
k
id
+ c
1
rand×(p
id
− x
k
id
) + c
2
rand×(p
gd
− x
k
id
)),
x
k+1
id
= x
k
id
+ v
k+1
id
,
χ =
2κ
t|2 − ϕ −
ϕ
2
− 4ϕ
,φ= c1 + c2,ϕ>4. (7)
The variable κ can range in [0, 1]; a value of 1.0 works fine, as does a value of ϕ = 4.1.
Thus, if ϕ = 4.1 and κ = 1, then χ ≈ 0.73, simultaneously damping the previous velocity term and the random ϕ.
The CFA of PSO is not defined for ϕ 4.0. As ϕ increases above 4.0, χ gets smaller; for instance, if ϕ = 5, then
χ ≈ 0.38, and the damping effect are even more pronounced. The convergence characteristic of the system can be
controlled by ϕ. Namely, Clerc et al. [32], found that the system behavior could be controlled so that the system
behavior has the following features:
(a) The system does not diverge in a real value region and finally can converge.
(b) The system can search different regions efficiently by avoiding premature convergence.
Unlike other EC methods, CFA of PSO ensures the convergence of the search procedures based on the mathe-
matical theory. CFA can generate higher quality solutions than PSO with IWA [33]. Eberhart and Shi compared the
performance of PSO with its different versions, and concluded that the best approach is to use the constriction factor
while limiting the maximum velocity V
max
to the dynamic range of the variable X
max
on each dimension [33]. For
instance, it is convenient to take V
max
= X
max
. However, CFA only considers dynamic behavior of one agent, but not
the effect of the interaction among agents. Namely, the equations were developed with fixed best positions (pbest and
gbest) although pbest and gbest can be changed during search procedure in the basic PSO equations.