Improving the performance of comprehensive learning particle swarm optimizer

Abstract

Comprehensive Learning Particle Swarm Optimizer (CLPSO) is a state-of-the-art variant of PSO, which maintains the diversity of its swarm by learning from different exemplars on different dimensions. Preserving the swarm diversity enables CLPSO to address the premature convergence problem associated with the canonical PSO. In this paper, the performance of the recently proposed fuzzy-controlled CLPSO (FC-CLPSO) is investigated on 24 problems; five of them are real-world engineering problems and six high-dimensional problems. In addition, two new CLPSO variants inspired by the Artificial Bee Colony (ABC) algorithm are proposed, CLPSO-ABC and FC-CLSPO-ABC. These two methods are compared with CLPSO and FC-CLPSO. The results show that FC-CLPSO-ABC outperforms the other three methods. FC-CLSPO-ABC is then compared with three other state-of-the-art swarm intelligence approaches on 24 problems. The results show that FC-CLPSO-ABC generally outperforms the other approaches.

Keywords

Swarm intelligence particle swarm optimization comprehensive learning particle swarm optimizer fuzzy systems artificial bee colony metaheuristics stochastic search

1 Introduction

1.1 Problem definition

Many optimization algorithms have been proposed for solving the continuous nonlinear function optimization problem: $Min f (X) : X_{min} \leq X \leq 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,

$\begin{matrix} 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)) \end{matrix}$ (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.

1.3 Motivations and contribution

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 further improve the performance of CLPSO and FC-CLPSO.

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 Related work

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 ${\vec{f}}_{i} = [f_{i} (1), f_{i} (2), \dots, f_{i} (D)]$ and f_i (j) = i₁ with j ∈ {1, 2, …, D} and $i_{1} \in {1, 2, \dots, N}; {\vec{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 \frac{(exp (\frac{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.

2.2 Fuzzy controlled CLPSO (FC-CLPSO)

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 - \frac{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 Problem formulation and proposed methods

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} = \frac{{fit}_{i}}{\sum_{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.

3.2 FC-CLPSO-ABC

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.

4 Methodology

To test the performance of the proposed methods, we have chosen 24 functions: 13 CEC05 functions (namely, f1-f13), five real-world engineering problems (namely, Gear Train, Compression Spring, Pressure Vessel, Lennard-Jones, and Frequency Modulation Sound Parameter Identification) and the 6 CEC08 large-scale global optimization problems (i.e. F1-F6). The 13 CEC functions have different characteristics (e.g., rotated, non-separable, shifted, unimodal, multimodal, composite, etc.). We did not test the full 25 CEC05 benchmark set because functions f14-f25 require a very long running time (e.g. few days for 30 runs of each function) and we are using a normal desktop computer (iMac 2.7 GHz Intel Core i5 with 8GB RAM) to conduct the experiments. These functions are generally complex compositional functions. We hope to investigate the performance of the different methods on these functions in the future when we have better computing power. For more details about the CEC05 functions, the reader is referred to [20]. More information on the first three real-world problems can be found in [16]. For the Lennard-Jones and Frequency Identification problems, see [4]. For more details about the CEC08, refer to [21].

For all functions (except the CEC08 functions) we have used 100,000 function evaluations (FEs). For the CEC08 functions, 5000D FEs were used as suggested by [21]. A swarm size of 40 particles was used for the CLPSO and its variants as suggested by [11]. The results of all methods have been obtained using 30 independent runs of the algorithms against eachproblem.

Given the best-of-run error, which is defined as the absolute difference between the best-of-the-run f (X^*) value and the actual optimum of a given function, i.e. $err . = | f (X^{*}) - f (X^{'}) |$

The effectiveness of a method is measured using two metrics:

The median of the best-of-run error.

Success rate (SR): The number of successful runs, where a run is successful if err. ≤admissible error. In this paper the admissible error is set to 1e-4.

In solving real-world problems, the Fitness Evaluation (FE) time overwhelms the algorithm overhead. Hence, the mean number of FEs needed to reach acceptable accuracy would be much more interesting than the CPU time [26]. Hence, the efficiency of a method is measured in terms of the number ofFEs.

All programs are implemented using MATLAB version 8.1.0.604 (R2013a), and machine epsilon is 2.2204e-16. The result of any computation that needs numbers smaller than the epsilon-machine is questionable. In particular, numbers smaller than the epsilon-machine cannot be trusted. For the pseudo-random number generator (RNG), the rand built-in function provided by MATLAB has been used. The RNG was warmed by calling it 10,000 at the start of the program as suggested by [7]. The non-parametric Friedman’s test with α= 0.05 and the Dunn-Sidak correction as a post-hoc test have been used to compare the difference in performance of the different algorithms. In this study, the Null Hypothesis, H₀, states that there is no difference between the medians of errors of the different algorithms.

5 Experimental results and discussions

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.

6 Conclusions

In this paper, the performance of FC-CLPSO was investigated on 24 problems. The results show that FC-CLPSO generally improves the performance of CLPSO except for high-dimensional problems. Inspired by ABC, two new CLPSO variants were proposed, CLPSO-ABC and FC-CLPSO-ABC, in which an onlooker stage is added to exchange information between personal best positions. Based on the experiments conducted, FC-CLPSO-ABC outperformed CLPSO, FC-CLPSO and CLPSO-ABC on most problems. FC-CLPSO-ABC was then compared with three other PSO variants where it obtained the best results. Finally, the effect of the swarm size on the performance of FC-CLPSO-ABC was investigated and it was shown the using a relatively small swarm size (e.g. 20 particles) yielded the best results.

7 Future works

In ongoing research, in addition to investigating the performance of FC-CLPSO-ABC in other sets of problems (including real-world problems), ways to automatically adapt the swarm size of FC-CLPSO-ABC is being explored. The performance of the proposed approach on even higher-dimensional problems (e.g. D > 100) will be investigated.

Footnotes

Acknowledgments

The authors would like to thank the anonymous reviewers for their constructive and helpful comments and suggestions.

References

Cheng

and Prayogo

, Symbiotic Organism Search: A new metaheuristic optimization algorithm, Computers & Structures 139 (2014), 98–112.

Civicioglu

, Backtracking search optimization algorithm for numerical optimization problems, Applied Mathematics and Computation 219(15) (2013), 8121–8144.

M. Clerc., http://www.particleswarm.info, 2011.

Das

, Suganthan

, Problem definitions and evaluation criteria for CEC 2011 competition on testing evolutionary algorithms on real world optimization problems. Technical report, Jadavpur University, Nanyang Technological University, 2010.

Goldberg

, Genetic algorithms in search, optimization and machine learning, Addison-Wesley, 1989.

Ismail and Engelbrecht

, The self-adaptive comprehensive learning particle swarm optimizer, Lecture Notes in Computer Science 7461 (2012), 156–167.

Jones

, Good practice in (pseudo) random number generation for bioinformatics applications. Technical report, UCL Bioinformatics Group, 2010.

Karaboga

, An idea based on honey bee swarm for numerical optimization. Technical Report TR06, Erciyes University, Engineering Faculty, Computer Engineering Department, 2005.

Kennedy

, Eberhart

, Particle swarm optimization, In Proceedings of the IEEE International Joint Conference on Neural Networks, IEEE Press, 1995, pp. 1942–1948.

10.

Liang

and Suganthan

, Adaptive comprehensive learning particle swarm optimizer with history learning, Lecture Notes in Computer Science 4247 (2006), 213–220.

11.

Liang

, Qin

, Suganthan

and Baskar

, Comprehensive learning particle swarm optimizer for global optimization of multimodal functions, Transactions on Evolutionary Computation 10(3) (2006), 281–295.

12.

Omran

, Clerc

, Salman

and Alsharhan

, A fuzzy-controlled comprehensive learning particle swarm optimizer, Lecture Notes in Computer Science (LNCS) 8472 (2014), 35–41.

13.

Parsopoulos

and Vrahatis

, Recent approaches to global optimization problems through Particle Swarm Optimization, Natural Computing 1(2-3) (2002), 235–306.

14.

Pasupuleti

and Battiti

, The gregarious particle swarm optimizer (G-PSO), Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation (GECCO’06), 2006, pp. 67–74.

15.

Riget

and Vesterstrøm

, A diversity-guided particle swarm optimizer - the ARPSO. Technical report, EVALife, Denmark, 2002.

16.

Sandgren

, Non linear integer and discrete programming in mechanical design optimization, Journal of Mechanical Design 112(2) (1990), 223–229.

17.

Schwefel

, Kybernetische Evolution als Strategie der Experimentellen Forschung in der Strömungstechnik, Master’s Technical University of Berlin, Germany, 1965.

18.

Shi

and Eberhart

, Fuzzy adaptive particle swarm optimization, IEEE Congress on Evolutionary Computation (CEC 2001) vol. 1, IEEE Press 2001, pp. 101–106.

19.

Storn

and Price

, Differential Evolution – A simple and efficient adaptive scheme for global optimization over continuous spaces, Technical Report TR-95-012, International Computer Science Institute, Berkeley, CA, 1995.

20.

Suganthan

, Hansen

, Liang

, Deb

, Chen

, Auger

and Tiwari

, Problem definitions and evaluation criteria for the CEC2005 special session on real-parameter optimization. Technical report, Nanyang Technology University, Singapore, 2005.

21.

Tang

, Yao

, Suganthan

P.N.

, MacNish

, Chen

Y.P.

, Chen

C.M.

and Yang

, Benchmark functions for the CEC’2008 special session and competition on large scale global optimization. Technical Report, Nature Inspired Computation and Applications Laboratory, USTC, China, 2008.

22.

Vasant

, Meta-heuristics optimization algorithms in engineering, business, economics, and finance, IGI Global, 2013.

23.

Vasant

, Handbook of research on novel soft computing intelligent algorithms: Theory and practical applications, IGI Global, 2014.

24.

Vasant

, Handbook of research on artificial intelligence techniques and algorithms, IGI Global, 2015.

25.

Yang

, Flower pollination algorithm for global optimization, Lecture Notes in Computer Science 7445 (2012), 240–249.

26.

Zhan

, Zhan

, Li

and Chung

, Adaptive particle swarm optimization, IEEE Transactions on Systems Man and Cybernetics Part B 39(6) (2009), 1362–1381.