Improving the performance of comprehensive learning particle swarm optimizer

1.1 Problem definition

Many optimization algorithms have been proposed for solving the continuous nonlinear function optimization problem: Min f ( X ) : X min ≤ X ≤ X max

The vector X = (x₁, …,  x _D ) is composed of D real-valued variables, and the vectors X_min and X_max are assumed finite and to satisfy X_min < X_max. The function f (X) is typically multimodal, so that local optima do not in general correspond to global optima. Examples for some well-known optimization methods used to solve this problem are evolutionary competition algorithms (e.g. Evolution Strategies (ES) [17], Genetic Algorithms (GA) [5], Differential Evolution (DE) [19] and Backtracking Search Algorithm (BSA) [2]) and swarm intelligence algorithms (e.g. Particle Swarm Optimization (PSO) [9], Artificial Bee Colony (ABC) [8], Flower Pollination Algorithm (FPA) [25] and Symbiotic Organism Search (SOS) [1]). For more details, interested readers are referred to [22–24].

1.2 Critical review

Swarm intelligence techniques are inspired by the collective behavior of the individuals in a population (swarm). While evolutionary competition methods focus on competition between individuals, swarm intelligence methods emphasize cooperation. The most popular swarm intelligence method for numerical optimization is PSO. PSO models the social behavior of bird flocking. In PSO, a swarm of particles fly through the search space. The position of a particle refers to a potential solution to the function to be optimized. A particle moves to a new position calculated by the velocity updated at each time step. This velocity is affected by the best personal experience of the particle and the best experience of the swarm. The velocity update is performed as follows,

v i , j ( t + 1 ) = wv i , j ( t ) + c 1 r 1 ( pbest i , j ( t ) - x i , j ( t ) ) + c 2 r 2 ( gbest j ( t ) - x i , j ( t ) )(1)where w is the inertia weight which affects theexploration/exploitation behavior of particle i, c₁ and c₂ are acceleration coefficients that determine the personal and social effects, r₁, r₂ ∼ U (0, 1) ,  pbest_i,j is the j-th component of the best personal position found by particle i and gbest _j is the j-th component of the best solution found so far by the whole swarm. Particles’ velocities on each dimension are clamped to a maximum velocity, V_max.

The new position of particle i is determined as follows,x i ( t + 1 ) = x i ( t ) + v i ( t + 1 )(2)

PSO is easy to implement, requires no gradient information, and computationally inexpensive given its low memory and CPU requirements [13]. Nevertheless, the canonical PSO suffers from premature convergence when applied to multimodal functions. One reason for this deficiency is poor swarm diversity [15]. Comprehensive Learning PSO (CLPSO) [11] addresses this problem and its results on multimodal functions show that it has a good balance between high and low diversity.

Another issue with PSO is the fact that its success depends on selecting the appropriate values for its control parameters (i.e. w, c₁ and c₂). Tuning these parameters for each problem is a time consuming task. Several PSO variants were proposed to automatically adapt these parameters. For example, a fuzzy system has been used to adapt w [18]. Pasupuleti and Battiti [14] proposed an adaptive variant of PSO called gregarious PSO. Ismail and Engelbrecht [6] proposed a self-adaptive variant for CLPSO. Omran et al. [12] proposed to use a fuzzy controller to adapt the parameters of CLPSO.

This work is an extension of the ideas first presented at the International Conference on Swarm Intelligence Based Optimization (ICSIBO’2014) [12]. Our two main objectives for this work are:

To investigate the performance of FC-CLPSO on more problems.

To achieve the first objective FC-CLPSO was tested on 24 problems (5 of them are real-world engineering problems). To achieve the second objective, two new CLPSO variants approaches were proposed. Both approaches have been inspired by the Artificial Bee Colony (ABC) algorithm [8].

The rest of the paper is organized as follows: Section 2 provides an overview of CLPSO and FC-CLPSO. The two new proposed methods are presented in Section 3. The methodology and experiments set up is explained in Section 4. The experiments and their results are presented and discussed in Section 5. Section 6 concludes the paper and Section 7 briefly describes future research works.

2.1 Comprehensive learning particle swarm optimizer (CLPSO)

The Comprehensive Learning Particle Swarm Optimizer (CLPSO) [11] addresses the premature convergence problem of the basic PSO by allowing each particle to learn from the personal best position of other particles. Each dimension of a particle can potentially learn from the best experience of a different particle (referred to as an exemplar). Hence, the velocity updating equation is modified as follows,v i , j ( t + 1 ) = wv i , j ( t ) + cr j ( t ) ( p f i ( j ) , j ( t ) - x i , j ( t ) )(3)where f → i = [ f i ( 1 ) , f i ( 2 ) , … , f i ( D ) ] and f _i  (j) = i₁ with j ∈ {1, 2, …, D} and i 1 ∈ { 1 , 2 , … , N } ; f → i defines which particle’s personal best position particle i should follow. p_{f i (j), j} can be the corresponding component of any particle’s personal best position including the particle’s own personal best experience. To generate p_{f i (j), j}, a random number is generated. If this number is greater than a learning probability, Pc _i , this component (i.e. dimension) will learn from its own best experience, otherwise, it will learn from another particle’s personal best position. If all examplars of a particle are its own personal best position, one component will be randomly chosen to learn from another particle’s personal best position. If a particle failed to improve itself for m (known as the refreshing gap) consecutive iterations, new exemplars will be chosen for that particle. Liang et al. [11] empirically determined that 7 is a good value for m. The learning probabilities are computed using,Pc i = 0.05 + 0.45 ( exp ( 10 ( i - 1 ) N - 1 ) - 1 ) ( exp ( 10 ) - 1 )(4)

According to [11], different learning probabilities affect the exploration/exploitation abilities of the particles.

Liang and Suganthan [10] proposed a self-adaptive technique to adapt the learning probability. In addition, the historical information is used in Equation (3) to search more effectively. However, the results were not very promising to merit further investigation. Ismail and Engelbrecht [6] proposed a self-adaptive variant of CLPSO (SACLPSO). In SACLPSO, position vectors are augmented to contain the inertia weight, w, and the acceleration coefficient, c. These two parameters are updated with the decision variables using Equation (3). Thus, in SACLPSO, the position, velocity, personal best position and global best position are all (D + 2)-dimensional vectors. The learning probability, Pc _i , is updated using Equation (4). SACLPSO outperformed CLPSO on ten well-known test functions.

Omran et al. [12] proposed a fuzzy controlled CLPSO (FC-CLPSO) where each particle has its own learning probability, inertia weight and acceleration coefficient. A fuzzy controller is used to adapt these three control parameters (i.e. Pc _i , w and c _i ). The controller takes the normalized rank of each particle as its input and generates three control parameters as outputs. The rank is determined by first sorting the swarm’s particles according to their cost function. The best particle (one with the smallest error) is given a rank of 1 (i.e. R₁ = 1), while the worst particle (with the biggest error) is given a rank of N (i.e. R _N  = N). The rank is then normalized to a value between 0 and 1 using, r i = 1 - R i - 1 N - 1

The normalized ranks are then assigned as membership grades in 3 fuzzy subsets as follows: LOW, MEDIUM and HIGH. The membership functions for Pc _i , w _i and c are also defined in a similar way. There are many alternative membership functions that can be used. In this study, a Gaussian curve membership function is chosen for the input and outputs of the fuzzy controller. Figure 1 shows these membership functions.

The fuzzy rules of the fuzzy controller are defined as follows:

The rationale behind the above rules is that if a particle has a low rank this means it has a low performance, thus, it needs to learn from other particles. This can be done by increasing its Pc _i and c _i . Moreover, such a particle needs to focus more on exploring the search space, thus, its w _i should be increased. On the other hand, good particles should focus more on exploitation (i.e. local search), thus, w _i should be decreased. Moreover, such particles do not need to learn often from other particles, hence, Pc _i and c _i should be decreased.

The fuzzy controller is called whenever new exemplars are needed for a particle (i.e. initially and when a particle failed to improve for m iterations).

FC-CLPSO was compared with CLPSO and SPSO2011 on 11 benchmark functions. The results showed that FC-CLPSO generally outperformed CLPSO and SPSO2011 [13].

3.1 CLPSO-ABC

Inspired by the onlooker stage of the Artificial Bee Colony (ABC) [8], a new approach, CLPSO-ABC, is proposed here. In the onlooker stage of ABC, solutions are randomly chosen based on their fitness values. One way to do this is by roulette wheel selection where each slice is proportional in size to the fitness value:p i = fit i ∑ n = 1 N fit n(5)

Where fit _i is the fitness value of solution i and i ∈ {1,  2, …,  N}. The fitness, fit _i , is inversely proportional to the objective function, f (x _i ).

An update process is then performed for each selected solution as follows,x i , j ′ = x ij + φ i , j ( x i , j - x k , j )(6)where x _ij is the j-th component of x _i , j ∈ {1, 2, …, D} is a random index, x _k is another solution selected randomly from the swam and φ_i, j is a uniform random number in [-1,  1]. Equation (6) shows that as the difference between x_i,j and x_i,k decreases, the perturbation on the selected solution decreases too. Hence, the step length is adaptively reduced.

In CLPSO-ABC, an onlooker stage is added after the position update Equation (2) step. In this stage, personal best positions are randomly chosen based on Equation (5) where the fitness, fit _i , is inversely proportional to the objective function, f (pbest _i ).

Then the selected personal best positions are updated as follows,pbest i , j ′ = pbest i , j + φ i , j ( pbest i , j - pbest k , i )(7)

If the solution generated by this operation, , is better than the old value, pbest _i , (i.e.) then replaces pbest _i (i.e.).

The CLPSO-ABC algorithm is shown in Algorithm 1. A MATLAB ^® implementation can be requested from the corresponding author.

The FC-CLPSO-ABC algorithm is exactly the same as CLPSO-ABC but with the three CLPSO control parameters (i.e. Pc _i , w and c _i ) adapted by the fuzzy controller used in FC-CLPSO.

5.1 Comparison with CLPSO and FC-CLPSO

In this subsection, the two proposed variants of CLPSO, namely CLPSO-ABC and FC-CLPSO-ABC, are compared with the original CLPSO and FC-CLPSO. Ranking of algorithms is done based on the median error. If two or more methods have the same median error, their ranks are determined by the meanerror.

Table 1 shows the results of CLPSO, CLPSO-ABC, FC-CLPSO and FC-CLPSO-ABC on the CEC05 benchmark functions. For unimodal problems, FC-CLPSO generally performs better than the other methods while for multimodal functions, CLPSO-ABC generally outperforms the rest. The FC-CLPSO-ABC, which is a hybridization of FC-CLPSO and CLPSO-ABC, seems to benefit from both approaches by ranking second or even first on some problems. So, in general, FC-CLPSO-ABC shows the best performance while CLPSO is the worst method on theseproblems.

Table 2 shows the results on high-dimensional CEC08 functions. The results show that CLPSO-ABC and FC-CLPSO-ABC perform comparably and better than CLPSO and FC-CLPSO. The results suggest that CLPSO suffers when applied to high-dimensional problems and that hybridizing it with ABC helps in improving CLPSO performance on this type of problems.

Table 3 shows the results on the five engineering problems. The results show the superiority of the FC-CLPSO-ABC method on this type of problems. CLPSO-ABC and FC-CLPSO perform comparably on the five engineeringproblems.

Figure 2 shows the progress of the mean best errors found by the four approaches over 30 runs for selected problems.

Overall, the results show that FC-CLPSO-ABC is the best approach. Thus, in the rest of the paper, we will only focus on this algorithm.

5.2 Comparison with other PSO variants

In this subsection, the performance of FC-CLPSO-ABC is compared with three variants of PSO, namely, Gregarious PSO (G-PSO) [14], SPSO2011 [3] and SACLPSO [6]. G-PSO uses only social knowledge and “reactively” determines the step size based on feedback from the last iterations. SPSO2011 is the most recent standard version of PSO. SACLPSO is chosen because it is a very recent and self-adaptive variant of CLPSO. The parameter settings for these three algorithms are based on the suggestions in the corresponding references.

Table 4 shows the results of the competing methods on the CEC05 benchmark functions. Compared to G-PSO, FC-CLPSO-ABC performs worse on two functions only. SPSO2011 outperforms FC-CLPSO-ABC on three functions. These three functions, viz. f2, f3 and f4, are unimodal functions. For multimodal functions, which are more interesting, FC-CLPSO-ABC generally outperforms SPSO2011. FC-CLPSO-ABC clearly outperforms SACLPSO on most functions.

Table 5 shows the results on high-dimensional CEC08 functions. The results show that FC-CLPSO-ABC outperforms G-PSO on all problems. Moreover, FC-CLPSO-ABC performs better than or equal to SPSO2011 and SACLPSO. These results suggest that FC-CLPSO-ABC can handle high-dimensional problems better than the other threePSO-variants.

Table 6 shows the results on the five engineering problems. For compression spring, SPSO2011 generates the best result. FC-CLPSO-ABC and G-PSO manage to do well on pressure vessel while SPSO2011 and SACLPSO fail. FC-CLPSO-ABC outperforms the other approaches on frequency modulation while G-PSO clearly obtains the best result on Lennard-Jones. In general, FC-CLPSO-ABC seems to be the best method on the engineering problems.

Figure 3 shows the progress of the mean best errors found by the four approaches over 30 runs for selected problems.

5.3 Effect of swarm size

In this subsection, the effect of the swarm size on the performance of FC-CLPSO-ABC is investigated.

The results (tables are not shown due to limited space) show that using a relatively small swarm size (20 or 40) generally improves the performance of FC-CLPSO-ABC.