Maurice.Clerc@WriteMe.com 1998/12/11
The Simplest Particle Swarm Optimization
(towards an Adaptive Deterministic PSO)
Equations
The basic iterative representation is just
Equ. 1 
This can be rewritten without explicit reference to the velocity.
So, referring to the general representation
Equ. 3 
we obtain easily
Equ. 4 
We are in a case where the general explicit analytical formulas for x and v can not be used, for the determinant of the system is equal to zero. That is why we study now directly this system, from an algebraic point of view.
Theoretical study
From the Equ. 2 we have immediately
Equ. 5 
The convergence condition is then
or 
In particular, if we want a convergence to p with an admissible error e, and if the objective function f is not too "sharp" nor too "flat" around the solution point x_{S} (in practice if we have ), we obtain the convergence time T
Equ. 7 
If we have but know nothing about p nor , a theoretical estimation of the convergence time T_{theor} is then (defining )
Equ. 8

By plotting T_{theor} versus j, we obtain a performance curve. The Figure 1 shows a typical one.
Figure 1. Typical theoretical performance curve (e=0.01, Dx=10).
Basic Algorithm
Now, in practice, p is modified at each time step. It means we still have then a sure convergence towards something (assuming the condition of the Equ. 6 is respected), but not necessarily towards the wanted solution.
The simpliest way is probably to consider p is the best position found in the neighbourhood at each time step, and even to consider this neighbourhood itself is the whole swarm. The pseudocode of the algorithm for N particles and an objective function f defined on is given below (here in the case where we are looking for a given objective value S, not necessarily an optimum). Note that for the space of search is strictly decreasing at each time step, the best initial position is a regular disposition on the "frontier" of the hypercube .
'Initialization
<choose the acceptable error e>
<put the particles regularly on the frontier of the space of search>
<choose a j value>
best=1 'Rank i of the "best" particle. Arbitray value to begin
' Iterations
loop:
for i=1 to N
if then
print "Solution ";
end
else
if then
best=i
best_eval=eval_{i}
end if
end if
next i
if <stop_criterion is true> then
print "Failure"
end
else
for i=1 to N
for j=1 to D
next j
next i
goto loop
end if
The stop criterion can be simply something like <number of time steps = MaxIter> or, more subtle, a NoHope criterion as <the probability to find a solution is now smaller than …>. Here we just use . Also, j can be either a constant (deterministic PSO) or randomly chosen at each time step (we will not study this case).
Results with the Alpine function
We study here what happens when we are looking for the maximal value of the 2DAlpine function on . The Figure 2 shows a typical convergence process, but from a certain point of view, the performance curve we obtain by trying different j values(see Figure 3. Note that to plot this curve the convergence time T is an arbitrary high value when there is no convergence) is a bit "unfair".
Figure 2. Example of convergence process (j=0.4).
For example we have a quite quick convergence for j=0.22 and for j=0.26, but no convergence at all for j=0.24.
Figure 3. Performance curve with the basic algorithm (e=0.01, Dx=10).
But if we examine carefully what happens, it appears that the particles are not so far of the solution point (7.917,7.917), for they converge to (7.900,7.852) in about 30 time steps. The problem is that the steps are then so small that the particles have indeed "no hope" to really reach the solution.
That is why we now add a Rehope adaptation to the basic algorithm: as soon as the Nohope criterion is true we temporarily change the j value for a j_hope one, bigger than 2, just for one time step, in order to regive some "vitality" to the particles. As we can see on the Figure 4, some of them have now the possibility to reach the solution area in just three additional time steps.
Figure 4. NohopeRehope method (j=0.24, j_hope=3).
We can then plot the new performance curve. As we can see on the Figure 5 the result is far better.
Figure 5. Comparison of performance curves(Alpine function).
Results with the Banana function
Rosenbrock's valley (De Jong's function 2, Banana function) is a classic optimization problem. The global minimum (S=0) is inside a long, narrow, parabolic shaped flat valley, and convergence to the solution point (1,1) is well known to be difficult. In 2D the equation of the surface is
Equ. 9 
The Figure 6 shows how looks like the function for (as the values of the function are quite big, the scale has been reduced).
Figure 6. The Banana function (reduced scale for function values).
We can see on the Figure 7 there is still a improvement with the use of the Nohopejhope method, but not as good as with the Alpine function, particularly for j values greater than 1.
Figure 7. Comparison of performance curves (Banana function).
Conclusion
We have studied what is probably the simplest Particle Swarm Optimization method: deterministic, just one equation and one parameter. Not surprisingly the results are not very good, but the system is quite easy to analyze and this analysis gives us two precious indications, used here in what we call the Nohope Rehope method:
We have now to find what could be the best strategy for such an adaptive deterministic PSO, and to study whether it is worth or not to add some parameters to the system.