Equ. 1
For more information about the model itself see Jim Kennedy.
Analytical
study
Iterative
Representation versus Explicit Representation
From
IR to ER
From
ER to IR
Particular classes of solution
Class 1 model
Class 1' model
Class 1’’ model
Class 2 model
Particle
in Complexland
Back
to reality
Removing the discontinuity
Removing the imaginary
Reality
and convergence
Convergence
and Space of States
Constriction for model Type
1
Constriction for model Type
1'
Constriction type 1’’
Moderate constriction
Attractors
and convergence
Generalization
In Particle Swarm Optimization, the usual iterative
form is the following one:
|
|
Equ. 1
|
where 
(see also the Generalization section).
The matrix of the system is 
.
By solving a classical second order differential
equation, we find the explicit (analytic) representation (ER):
 |
Equ. 2
|
with
and 
(see below for c1 and c2)
There is also an interesting algebraic representation wich take
into account the fact that 
and 
are the eigenvalues
of 
. We don't study it in
this paper.
It is worth to note immediately an important difference between
IR and ER: in the previous one t is always an integer and v(t)
and y(t) are real numbers. In the second one we obtain real
numbers if (and only if) t is an integer, but nothing prevent us
to give any real positive value to t, and then v(t)
and y(t) are "true" complex numbers. This fact will give
us an elegant way to "explain" the system, by the use of a 5-dimensional
space (see the "Particle swarm in Complexland " section).
By computing the eigenvalues of the matrix M, we find
 |
and then
 |
This coefficients are always defined (but not necessarily
real), for the denominator cannot be equal to zero.
Note 1
If we want 
and 
are real numbers for
a given j value,
we must have some relations between the five real coefficients 
.
If we write the imaginary parts of 
and 
are equal to zero,
we obtain
 |
with
By combining them the two equalities of Equ. 5. Solutions are usually not completely independent of j. To satisfy this equations,a set of possible conditions is
But this conditions are not necessary. For example,
an interesting particular case (studied below) is
.
We have then 
for any j
(Equ. 5 is always satisfied)
From we obtain
or
 |
There are an infinity of solutions in.
We can add some others conditions. Let us study some particular classes
of solutions.
 |
Equ. 7
|
In this particular case, From the Equ. 4 we obtain
A easy way to be sure to obtain real coefficients
is then to have 
.Under this
additional condition, a class of solution is simply given by
 |
Equ. 8
|
 |
Equ. 9
|
From Equ. 4 we obtain
If we add again the condition ,
we find
 |
Equ. 10
|
I we don't add this condition, we have nevertheless from the Equ. 4
 |
Equ. 11
|
 |
Equ. 12
|
For " historical " reason and for the its simplicity,
the case 
has been well
studied.
 |
Equ. 13
|
We have then
which give us g and d.
Again, an easy way to obtain real coefficients for
every j value
is to have 
. Then we have
In the case 
we obtain
 |
Equ. 14
|
It is interesting to note (it will be useful to study the convergence) that we have
 |
and for 
 |
 |
Equ. 17
|
As we will see below in the Convergence and Space of States sections, it means that for this cases, we will just have to choose
,
and 
, 
, 
respectively, to have a convergent system.
The system has usually has a discontinuity in j
due to fact that there is the term 
in the eigenvalues.
So, if we want to have a completely continuous system,
we just have to choose
so that
By computing the discriminant we find the last condition is equivalent to
In order to be "physically plausible", we are looking
for positive parameters .
So the conditionbecomes
|
Equ. 18
|
This conditions specify a "volume" in 
for
the admissible values of the parameters..
By using the above condition the trajectory is
usually still partly in a complex space, as soon as one of the eigenvalue
is negative (due to the fact that 
is
a complex if t is not an integer). So we may want to find some stronger
conditions in order to have always positive eigenvalues.
By noting that we have
we find easily
 |
Note 2
From an algebraic point of view, these conditions can be written as
But now this conditions are depending on j.
Nevertheless, if we know the maximun j
value, we can rewrite them
Under this conditions, the system is completely real.
An under the conditions Equ. 19 and Equ. 20,
the system is continuous and real.
Example
If we suppose 
and 
, the conditions become
For example
The system converges quit quickly (about 25 time
steps) and at each time step the values of y and v are almost
the same, for a large range of j
values. The Figure 1 shows the result for j
= 4.
The quick convergence of the above example suggests an interesting question. Does "reality" implies convergence ? Or, in other terms, we are wondering if we have
Unfortunately the answer is negative.
Example
We have indeed
but for 
(for
instance) we obtain 
and
the system diverges (see Figure 2).
Figure 2. "Reality" doesn't imply convergence.
From the Equ. 15 and the Equ. 3 we find the criterion
of convergence:
 |
Equ. 21
|
In the explicit general form of the system, vtand
yt
are usually "true" complex numbers. So, the whole system should be represented
in a 5-dimension space 
.
Here we study more completelysome examples of an
important class of constricted cases : the onez with just one constriction
coefficient ,
We use the implicit representation of the model
class 1
From the Equ. 15 we know that the convergence criterion
is satisfied if we have 
.
As 
we can take as constriction
coefficient
 |
Equ. 22
|
We use the following
implicit representation (with c
instead of a)
We can take again
 |
Equ. 23
|
but we have seen this formula is a priori valid only for j<2, so it is interesting to find directly another constriction coefficient. We have here
The expression under the square root is negative
for 
. In this case, the
eigenvalue is a "true" complex number, and we have simply
.
So, if 
, that is to say
if j<4,
we just have to choose 
to
satisfy the convergence criterion. So, for example, we can define
 |
Now, can we find another formula for greater
j values ? The answer is "No". For in this
case, 
is a real number,
on its absolute value is
,
and the minimal value is 
(greater than 1),
For simplicity, we may want to have the same formula
than for the Type 1, not only for j<2,
but also for j<4.
This is indeed also possible, but then k
can not be too small, depending of j.
More precisely, we must have 
.
But as for j<4,
we have 
, it just means
that the curves in the Figure 4 can then by interpreted as the mean (resp.
Minimal) acceptable k
value for sure convergence. For example, for j=3,
we must have k>0.536.
In particular, we can note there is no restriction on 
if
j=1.
Figure 4. Constriction coefficient for convergence Type 1'.
.
Referring to the Class 1’’ model, in the particular
case 
, we use the following
implicit representation (with c
instead of a)
In fact, this system is just a transformation of the almost " classical " one
so it may be interesting to detail here how, in practice, the constriction coefficient is found and proved.
Step 1. Matrix of the system
We have immediately 
.
Step 2. Eigenvalues
They are the two solutions of the equation
that is to say of
We find here
with
Step 3. Complex and real areas on 
The discriminant 
is
negative for the values 
.
In this area the eigenvalues are true complex numbers and their absolute
value (i;e. module) is simply 
.
Step 4. Extension of the complexe area and constriction coefficient
In the complex area, according to the convergence
criterion, we just have to choose 
.
So the idea is to find a constriction coefficient depending on so
that the eigenvalues are true complex numbers for a large field of
values , for in this case the common absolute value of the eigenvalues
is simply
 |
Equ. 25
|
which is smaller than 1 for all
values as soon as 
is itself
smaller than 1.
This is generally the most difficult step and needs sometimes some intuition. But here, we may remark three points:
,
 |
Equ. 26
|
that is to say 
It is easy to see that is
negative only between two
values 
and 
depending
on 
.
The general algebraic form of 
is
quite complicated (polynom in 
with
some coefficients being roots of an equation in 
)
so it is much easier to compute it indirectly for some 
values.
If we suppose 
smaller than 4, we have 
and
by solving 
we find simply
, which
is then valid as soon as 
.
The Figure 5 shows how the discriminant is depending
on , for two 
values. It is negative between the
values given below:
|
 |
 |
| 0.4 | 0.3377 | 8.07 |
| 0.99 | 0.000025 | 39799.76 |
Figure 5. Discriminant D versus j.
So, in practice, the constriction coefficient works
for almost values as soon
as is near of 1. If is
exactly equal to 1, we have 
and 
. Theoretically the
convergence is not completely sure , for we have then 
but
it appears in the simulations we still have convergence, due to the fact
we are using several particles and random
values.
We use the following explicit representation:
that is to say 
.
From the Equ. 6 we obtain
There are an infinity of possibilities for the parameters a..h, that is to say there are an infinity of different implicit representations which give this same explicit one. For example:
or
From a mathematical point of view, this case is "richer" than the previous ones, for we have no more explosion, but not always convergence either. That is why we will study it more in detail. We could call this kind of system "stabilized", for, as we will see, the representative point in the state space tends to move along an "attractor" which is not always reduced to a single point, as in classical convergence.
The Figure 6 and its sections show what it is usually
studied, that is to say just the "real" restrictions 
.
We can clearly see the three cases:
- "spiral" easy convergence towards a non trivial attractor for j<4 (Figure 7),
- difficult convergence for j=4 (Figure 8),
- quick almost linear convergence for j>4
(Figure 9).
Figure 6. Surface (Re(y), Re(v), j), t=0..50, j=0..20, y(0)=0, v(0)=1, k=0.8
Nevertheless, it is interesting to have a look
at what is the "true" system. The following figures show some others sections
of the whole surface in 
.
Figure 10. 
,
j=2.5.
Attractor: circle center (0,0) radius=0.819
Figure 11. 
,
j=4.
Attractor: circle center (0,0) radius=9
Figure 12. 
,
j=6.
Attractor: circle center (0,0) radius=0
Figure 13. Global attractor for v and 
.
Axis (Re(v), Im(v), j),
k=0.8
Note 3
There is a discontinuity, for the radius is equal
to zero for j>4.
Figure 14. Global attractor for y and 
.
Axis (Re(y), Im(y), j),
k=0.8
So, what it seems to be an "oscillation" in the real
world is in fact a continuous spiralic move in a complex space. More important,
the attractor is very easy to define: it is the "circle" 
(center (0,0) and radius r).
So when j <
4, 
and when j
is greater than 4 
(
with 
) for the constriction
coefficient c
has been precisely chosen so that the part 
of v(t) tends to zero. This gives us a good and simple intuitive
way to transform this stabilization into a true convergence. We just have
to use a second coefficient to reduce the attractor, in the case 
,
so that 
Note 4
As we are studying here the "one constriction coefficient
models", we have to choose 
,
and finally we retrieve the type 1 constriction. But now, we understand
better why it works.
We study here the more general system defined by
We just have to define
to obtain exactly the same system as the one studied above.
For instance, if we have a cycle for 
,
so we have an infinity of cycles for the values 
so that 
.
If we compute the constriction coefficient, we obtain
Coming back to the (v,x) system, we have then
The use of the constriction coefficient could be seen as a recommendation to the particle "Make more little steps"
The convergence is towards the point 
.
Remember v is in fact the velocity of the particle, so it has indeed
to be equal to zero in a convergence point.
Example
j1 and j2 are uniform random variables between 0 and jmax,1 and jmax,2 respectively.
