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.

Equ. 2

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

Equ. 6

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 xS (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 Ttheor is then (defining )

Equ. 8

 

By plotting Ttheor 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=evali

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 No-Hope 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 2D-Alpine 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 Re-hope adaptation to the basic algorithm: as soon as the No-hope 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. No-hope-Re-hope 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 No-hope-j-hope 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 No-hope -Re-hope 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.