Beyond Standard Particle Swarm Optimisation

Standard Descriptions

A Standard PSO is now freely available on the Particle Swarm Central (PSC, 2010) since a few years. The current version is called Standard PSO 2007 (SPSO-2007 in short). The list of contributors is quite long as it also includes the “negative” contributions, i.e. work from people who have tested some possible variants, and found them to be not suitable for inclusion in a “standard” that should be both simple and robust.

The velocity update equation for one particle in SPSO-2007 is given by

The notations in this equation are as usually found in papers about PSO, that is, t is the time step, v is the velocity vector (in fact the displacement vector), and x is the position. The positions and are respectively the best previous position of the particle, and the best previous position known by its neighbours (or informants) at time t. Also, this formula has to be applied independently for each dimension. (resp.) is a random number drawn from the uniform distribution on (resp. ). The inertia weight is constant. The values of these three coefficients are derived analytically (Clerc, 2006b), and are

These are slightly different from the ones used in SPSO 2006, which were derived using an older analysis (Clerc & Kennedy, 2002). The new position is given by

A typical example of a variant that is commonly used but is not included in this standard is the reduction of the weight from to as a function (usually linear) of the time t (Shi & Eberhart, 1998). It does not mean that this method is bad. In fact, it is good for some problems, but is highly dependent on four parameters: , , the swarm size S, and the pre-defined maximum number of fitness evaluations FE_max . As the standard should be both simple and robust, and as this variant has too much dependence on too many parameters; it has not been retained in the standard.

Of course, SPSO-2007 also uses a swarm size, but it is not a parameter to be tuned. There, it is automatically computed by the formula

The initialisation of the positions is done at random (uniform distribution) inside the search space. The initialisation of the velocities is also done at random, by the “half-diff” method (see (Helwig & Wanka, 2008) for an analysis of various techniques). For each particle, it can be formulated as

To control excessive movements of the particles, SPSO 2007 uses a confinement method: when a particle tends to leave the search space, the component of the position that is too big (resp. too small) is set to the maximum admissible value (resp. to the minimum acceptable value) and the corresponding velocity component is set to zero.

Finally, to complete the description of SPSO-2007, we have to define the communication network between the particles (the topology). It depends on a parameter K, set by default to 3. At the very beginning (initialisation), and after each unsuccessful iteration (i.e. if the current solution does not improve), each particle builds K information links at random, by using an uniform distribution over the whole swarm. Also, each particle informs itself. As a result, the number Y of informants of a given particle is given by a probability distribution

Figure 1.

Distribution of the number of informants in SPSO-2007 for a swarm size S=20. It may be any number between 1 and S, with a mean value slightly greater than K.

Now, let us consider the proposed standard defined in (Bratton & Kennedy, 2007). We will call it SPSO-BK. What are the differences? Let us look at the coefficients first. The values are still the ones used in SPSO-2006, i.e., and. So the difference for the coefficients is not significant.

Second, the swarm size is fixed at 50. However, this is just a compromise. In practice, for good performance, the swarm size is in fact a parameter that has to be tuned if the dimension of the problem is very different from the most commonly used in (Bratton & Kennedy, 2007), i.e. 30.

Third, there is no confinement. The approach taken here is to “let the particles fly”, without re-evaluating the position of a particle that is outside the search space, for anyway it tends to get back sooner or later. This is indeed the simplest way, but the performance may be significantly worse than with a true confinement, particularly when the optimum lies near the search space boundary (Helwig & Wanka, 2007). Also, in some rare cases, the program may loop a very large number of times because the stopping criterion is the maximum number of fitness evaluations, which may be difficult to reach if there are too few re-evaluations.

Fourth, the initialisation method is different: it is done within a subspace of the entire feasible search space that does not contain the global optimum. However it is not really applicable in practice, for we are not supposed to know where the optimum is.

The fifth point, topology, is the most significant one. The authors propose the use of old classical fixed ring topology, in which each particle i (in {0,1,...,S-1}) is informed by the particles (i+1) mod S and (i-1) mod S (and by itself). This method indeed often gives good results. However, it is less robust than a variable topology like the one used in SPSO-2007. Actually, it is interesting to compare the two topologies in terms of probability of being informed of the best position.

For simplicity, let us suppose that S is even and that the best known position is not modified over S/2 time steps. Now, let us choose a particle at random (uniform distribution). After t time steps it may or may not have been informed (directly or indirectly) about the best position. The probabilities of being informed are

The lower the probability, the more “free” the particle is to explore without being too quickly attracted by the best position. Of course, the counterpart is that, for simple problems, the convergence, if any, can be slower. Note that formulae like (7) may help us to define a rule of thumb for detecting stagnation. We define a stagnation as follows: a stagnation occurs if there is still no improvement even though the probability of being informed about the best position is at least for any particle. The corresponding number of iterations is then

Let us take an example from Figure 2. For we need to wait six or seven time steps for both SPSO-2007 (K = 3) and SPSO-BK, and nine time steps for SPSO-2007 (K = 2). Also, it can be derived from the formulae that the best similarity between the two curves is obtained for, an empirical value that is often used.

Figure 2.

Probability of being informed about the best position, for S=20, assuming it does not change over 10 time steps

From this point of view of information transmission, the ring topology is interesting, as after S/2 iterations, if there is still no improvement, stagnation is very probable. On the other hand, with this topology, the swarm may converge too quickly to a point that is not the optimum. So it is tempting to define a compromise between the two methods.