Adaptive Particle Swarm Optimization*
Keiichiro Yasuda, Azuma Ide and Nobuhiro Iwasaki Graduate School of Engineering Tokyo Metropolitan University Tokyo 1920397, Japan yasuda@eei.metrou.ac.jp
A b s t r a c t  The Particle Swarm Optimization (PSO) method is one of the most powerful methods f o r solvglobal optimization problem when the method is applied t o global optimization problems. This paper deals with the analysis of the dynamics of PSO in order t o obtain an understanding about how it searches a globally optimal solution and a strategy about how to tune its parameters. While a generalized reduced model of PSO is proposed in order to analyze the dynamics of PSO, the stability analysis is carried out on the basis of both the eigenvalue analysis and some numerical simulations on a typical global optimization problem.
ing unconstrained and constrained global optimization problems. Little is, however, known about how the PSO method W O T ~ SOT finds a globally optimal solution of a global optimization problem when the method is applied to global optimization problems. This paper deals with the analysis of the dynamics of PSO in order to obtain an understanding about how it searches a globally optimal solution and a strategy about how to tune its parameters. While a generalized reduced model of PSO is proposed in Order to analyze the dynamics of Pso, the stability analysis is carried out on the basis of both the eigenvalue analysis and some numerical simulations on a typical global optimization problem.
2
~
~
Keywords: Global Optimization, hletaheuristics, Particle Swarm Optimization, Stability Analysis.
The Particle Swarm Optimization algorithm and its reduced system
The Particle Swarm Optimization algorithm
2.1
1
Introduction
~
In real optimization problems, we encounter many cases in which a problem can be formulated as a global optimization problem of the objective function having nonlinear or multipeaked characteristics. Since it is felt necessary in recent years to derive a global solution for nonlinear and multipeaked optimization problems, global optimization is one of the most important topics in optimization. h4oreover, with the popularity of highspeed digital computers, tremendous research activity is going on in the area of global optimization in nonlinear optimization problems. Many global optimization methods have been reported in the literatures [4],[5],[2],[3]. The Particle Swarm Optimization (PSO) method is one of the most powerful methods for solving unconstrained and constrained global optimization problems. The method was originally proposed by J. Kennedy as a n optimization method in 1995 and has been proved t o be an efficient method for many global optimization problems. Little is, however, known about how the PSO method works or finds a globally opt.imal solution of a
*0780379527/03/$17.00 0 2003 IEEE.
While the PSO algorithm was proposed in terms of social and cognitive behavior, two different types of algorithms exist  binarynumber and realnumber forms. The PSO in a realnumber form is only analyzed in this paper. The projected position of ith particle of the swarm and the velocity of the particle at ( k 1)th iteration are defined as the following two equations:
+
' : :U
=w . U :
+ c1 . r a n d ( ) . (pbestij  zf,)
+c2.
zy= . : ,+
rand().(gbestj  zs)
(I)
(2)
where, i = 1, ...,n and n is the size of the swarm; c1 and c2 are positive constants; rand() is random number which is uniformlydistributed in [0,1];and k determines the iteration number.
2.2
A reduced system of Particle Swarm
Optimization
The above algorithm will be simplified in order to analyze the dynamics of the PSO algorithm. If the particle x is reduced to one dimension, then vector notation
1554
~
can be thrown out and the particle's trajectory can be displayed as a simple graph. Without any information, the two terms of the formula can be transformed into one term:
= M[$]
(9)
where p is the weighted average of the two best, and 4 is a random number distributed in 10, (c1 C Z ) ] and its average vdue is
4
p
=
T. c1 .rand() + c2. rand()
ci . rand() . pbest ci . rand()
+
=
+ cz .rand() .gbest + cz rand()
.
(4)
(5)
Though the exact location of t.he particle z changes on every iteration because of the random number 4, the random number 4 is made constant for the simplicity in this paper. The trajectory of the particle can be plotted and studied when the weighted best point p and the random number 4 are made constant 4 = The reduced formulas of PSO can be expressed as follows:
where AT is the matrix, of the system. The state of the particle at iteration k can be represented as follows:
T.
P is a diagonal transformation matrix and
where
yk = p  x k
(7 )
sent the original PSO situation. In general population sizes are greater than one and seldom a particle operates on only one dimension. Furthermore, the weighted hest point p is not static but dynamic, often exhibiting complex behavior. Therefore this simplified model is contrived only to provide some information on how each particle behave without the interaction among the particles. The stability of each particle, however, can be exactly evaluated based on this model when the fluctuation of p is bounded. Since the search space (feasible region) is generally limited in global optimization problems, the fluctuation of p is also bounded. Therefore, i t can be applied in the evaluation of the stability of each particle in usual global optimization problems.
Keep in mind that the simplified model does not repre
are the eigenvalues of M . The dynamics of the reduced system is completely defined by A l . Based on the stability theory in a linear dynamical system, the stability of each particle is evaluated. According to the stability theory, the behavior of the particle is stable if and only if IX1/ < 1 and IXzl < 1. Since the eigenvalues XI, Xz are a function of parameters w, c1 and c ~the , eigenvalue analysis will be carried out in the following four conditions.
(a) w = 0
From equation (13)
X=14
(14)
The condition in which absolute values of the eigenvalues X i , Xz become under 1 is the following equation.
0<4<2
(15)
3
3.1
Stability analysis of the reduced system
Stability analysis in terms of matrix algebra
Therefore, the reduced system is stable when 0 < 4 < 2, and each particle x converges to p .
(b)$<w+lZfi
Since the above condition can be rewritten as
w + 14 > 2 & >
0
(16)
The reduced system, which is a deterministic system, can be written in terms of matrix algebra.
The condition in which absolute values of the eigenvalues XI, Xz become under 1 is the following equation.
w+ll~lmaz =
++J ( w +
2
1  4 ) Z 4w
< 1 (17)
1555
In addition, if the following relationships are considered
J(~+14)~4w
<
@w+l
(18)
Since 4 which satisfies Equation (27) must satisfy the condition 0 < w  4 3, and w is a nonnegative coefficient, then
+
O<w<l
(28)
O<w<l
(21)
Under the condition U 1+ 2 f i < 4 < 2w 2, the , and each reduced system is stable when 0 5 w < 1 particle x converges to stable equilibrium point p . Based on the above analysis and by using the parameters 4 and 20, the criterion of convergence (AI( < 1 and 1,421 < 1 can be written as follows:
+
+
Under the condition 4 < w + 1  2& the reduced system is stable when 0 5 w < 1 , and each particle 5 converges to stable equilibrium point p .
( c ) w + 1 2 J i s
o< 4
0 5 w
<2w+2 <1
(29)
(30)
< 4 < w + 1 + 2J;s
3.2
w + 1+ 2fi,
Since (U+ 1 4 ) *  4 w < 0 when w + 1 2 f i < 4 < X becomes a complex number. Therefore (XI can be given in the following equation.
w
More detailed analysis of the reduced system
+ 1 4
(W
J(w
+ 1 4 ) Z
2
+
 4w
+

' ) Q
(J('uI
+ 1 '#J)'+ 4W
2
\
%/G
(221
,
)
While only the stability of the reduced system is discussed in the previous section, more detailed analysis such as the analysis on period of vibration will be investigated in this section. In case of (cl w 1  2dG < d < w + 1 2&. X is a complex number. Therefore the following relationship holds,
\ ,
+
+
.
I
1x1 = 4
(31)
That is, whether the reduced system converges or diUnder the condition +  2@ < 4 < n~ + + 'fi~, verges is dependent on w. In other words, the adjustwhen 5 < ', and each ment of the dynamics of the reduced system is possible the red"ced system is by only adjusting w. particle z converges to stable equilibrium point p. By using a parameter (d) U + 1 2 f i < 4
+
w
+ 1 4 <  2 f i
<0
(23)
and buy using the following condition
w
1x1 has an absolute maximum when the molecule of eauation (13) is less than 0. In this condition. X is a i o negative and the condition in which the reduced system is stable is given in the following equation.
IXI"
=
+ 1 2 & <
4 <w+l+2&
(33)
4 can be expressed as fo~lows:
4 = w + 1 2J;J+4K1J;J
(34)
w
\
+ 1 @ + 1 4)'
\/(w+ 1 6)'  4W
2
I
< 1(24)
The polar coordinates expression of X is the following equation when X is a complex number.
Xk = l X l ~ e k @
Therefore
J(w
(35)
 4w < w  4 + 3
< (U $ + 3)'
(25)
When 0 < w  Q
(w
+ 3, the following relationship holds.
(26) From the above equation, the following relationship can be obtained.
4<2w+2
+ 1 4)'  4 w
It is clear from Equations (12) and (35).that the trajectory of the reduced system vibrates periodically. If T is to he the period of the reduced system (12), then
T = = 0
2a
2n
taIIE
1.0
0.9
0.8
0.7
L
l
'
0.6
0.5
0 . 4
0.3
32& 0. I
0.5 1.0
1.5
2.0 Value
2.5
3.0
3.5
4.0
where
ji, /
',I
I.,i
i ;.., 1
1,
1
9
!,!
!*I/),!
, li . . , ,
) ? ;
i
.i \ e . .
8
. ,.
yt,
\, ,
...,.
T=
LII
tan*
12x.
(RI
< 0.51, > 0.5)
(38)
w : If 0 5 w < 1, the convergence tendency of the
27r
n+tan1
12%1
(KI
By using a parameter 0
CI
< K Z < 1, we have
1
Cz=%
and
C1
C2

K2
(39)
reduced system strengthens as 20 becomes small. If 1 < w,the divergence tendency of the reduced system strengthens as w becomes large. K I : 0 < K I < 1, the dynamics of the reduced system becomes vibrational as K I becomes large. K Z : 0 < R Z < 1, while p is put in the neighborhood of pbest if nz % 0, p is put in the neighborhood of gbest if R Z x 1.
3.3
=
=
2(1K2)r$
Analysis of Inertia Weights Approach
2K24
(40)
The above results provide a projected position of 2th particle of the swarm is defined as the following equation:
uk+l e) =w
+ Z(1
K Z ) ~ rand(). .
(pbest,,  z ) :
+2~2+. rand() . (gbest, 
zt,)
(41)
where
The qualitative relation between the search trajectory of the reduced model of PSO and the parameters ( w , K~ and R Z ) is summarized as follows:
As a parameter adjustment method of PSO, the IWA (Inertia Weights Approach) has been proposed. Figure 1 shows the stability region obtained by the above analysis. While the value of w is made t o decrease gradually with the increase in the number of iterations in IWA, parameters wmor = 0.9,wmin = 0 . 4 , ~= cz = 2.0 are recommended in order t o improve the search efficiency of PSO. w = 1 corresponds to a stability limit of the reduced system, and the system has the high stability when w < 0.5. Therefore, w is adjusted in order to reach the region w < 0.5 with the high stability margin from the stability limit 20 = 1. By this adjustment strategy of parameter w, while the diversification in search is realized in the
1557
5
'._
0
Y
5 10
Iteration
IJ
? O
15
1
Iteration
15
30
Iteration
~i~~~~ 4 Relationship between parameter rameter p .
K2
e.the
Figure 3: Relationship between search trajectories of reduced model of PSO and parameter K I .
and pa
initid stage of the search, the intensification in search
is alsofealized in the final stage of the search.
4
Experimental results
Some simulations were carried out in order to examine the relationship between search trajectories of the reduced model of PSO and the parameters w, K I and
K2.
Figure 2 shows simulation results which were carried out under the condition K ] , K Z = constant value in order to examine the relationship between a search trajectory and parameter w.It is seen from Figure 2 that the trajectory of the reduced system stably approaches to point p within 30 iterations when w is small, but the trajectory does not approach to point p within 30 iterations when w is large. Figure 3 shows simulation results which were carried out under the condition w, K Z = constant value in order to examine the relationship between a search trajectory and parameter K ] . I t is seen from Figure 3 that the trajectory of the reduced system is asymptotic when K I is small, but the trajectory is vibrational when 1c.1 is large.
~ i 4 shows ~ simulation ~ ~ e which were carried out under the condition w, K~ = constant value in order to examine the relationship between a search trajectory . is seen from figure that p is put in and parameter ~ 2 It the neighborhood of pbest if K Z FZ 0 and p is put in the neighborhood of gbest if K z FZ 1, Figure 5 indicates the relationship between search traiectories of the reduced model of PSO and varying parameter p . It is verified that the system follows changing
~~

On the other hand, in order to analyze the behavior of trajectories several types of PSO were applied to the following typical nonconvex optimization problem:
min.
f(z1,zz) =
z ( z 4
2
;=I
 16z:
+ 0.5zi)
(43)
subj. to
 50.0 5 z1,z2 5 50.0
Contours for objective function f(z1,z2) are shown in Figure 6. The success rates of each simulation using the above optimization problems are shown in Figures 7 and 8; SA indicates simulated annealing method in these figures.
1558
~
100
1
A
Iteration
1
I
10
100
1000
10000
Figure 5: Relationship between search trajectories of the reduced model of PSO and varying parameter p.
Itemtion Figure 7: Searching ability of each method for problem (43)
0
1.10
XI
1
10
100
1000
10000
Figure 6: Contours for objective function f ( 5 1 ~ x 2 )
Iteration
5
Conclusion
: Searching ability of each method for problem Figure 8 (43)
In this paper, how the Particle Swarm Optimization algorithm works is explored on the basis of the stability analysis in discrete dynamical systems. Some improvements to the original PSO is proposed and tested based on the analysis and the simulation. The proposed approach for tuning the parameters of PSO allows control over the dynamical characteristics of the particles in PSO. It should be minded that the simplified model does not represent the original PSO situation because population sizes are generally greater than one and seldom a particle operates on only one dimension. Furthermore, the weigbted best point p is not static but dynamic, often exhibiting complex behavior. Therefore this simplified model is contrived only t o provide some information on how each particle behave without the interaction among the particles. This work was supported by GrantinAid for Scientific Research (C) (15560252).
References
[l]A. Ide and K. Yasuda, "RobustAdaptive Particle Swarm Optimization", OPTIS2002(JSh4E), No.0203, pp.195200 2002. (in Japanese)
1 2 1 J. Kennedy and R. C. Eberhart, "Swarm Interlligence", Morgan Kaufmann Publishers 2001.
[3] A4. Clerc and J. Kennedy, "The Particle SwarmExplosion, Stability, and Convergence in a Multidimensional Complex Space", IEEE Transactions on Evolutionary Computation, Vo1.6, No.1, pp.5873 2002.
[4] R. Horst and P. At. Pardalos, Handbook of Global Optimization, Kluwer Academzc PublLshers, 1995. [5] S. Kirkpatrick et al., Optimization by simulated annealing, Science, Vol. 220, pp. 671680, 1983.
1559