GuASPSO: a new approach to hold a better exploration–exploitation balance in PSO algorithm

Abstract

This paper presents a new variant of particle swarm optimization (PSO) algorithm named guided adaptive search-based particle swarm optimizer (GuASPSO). In this algorithm, the personal best particles are all divided into a linearly decreasing number of clusters. Then, the unique global best guide of a given particle located at a cluster is obtained as the weighted average calculated over other clusters’ best particles. Since the clustered particles are being well-distributed over the whole search space in the clustering process, there would be a moderate distance between each particle and its unique global best guide, contributing the particles neither to be trapped in local optima nor engaged in a drift leading to lose diversity in the search space. In this approach, the number of clusters is high at the early iterations and is gradually decreased by lapse of iterations to less stress the diversity factor and further stress the fitness role to cause the particles to better converge to the optimal point. Holding this balance between global and personal bests’ role to attract the particles, on the one hand and between convergence and diversity, on the other hand, can hold a better exploration–exploitation balance in the proposed algorithm. To test the performance of GuASPSO, four popular meta-heuristic algorithms, including genetic algorithm, gravitational search algorithm, gray wolf optimizer, and PSO algorithm as well as 23 standard benchmark functions as the test beds, are employed. The experimental results validated GuASPSO as a robust well-designed algorithm to handle various optimization problems.

1 Introduction

1.1 Literature review

Meta-heuristic optimization techniques have become very popular over the last two decades. Some of them such as particle swarm optimization (Kennedy and Eberhart 1995), Artificial Bee Colony (ABC) (Karaboga 2005), differential evolution (DE) (Storn and Price 1997), and simulated annealing (SA) (Kirkpatrick et al. 1983) are well-known among not only computer scientists but also researchers from different fields of engineering. The reasons making these algorithms so common in solving engineering optimization problems could include these key points: simplicity, flexibility, derivation-free mechanism resulting in relatively low computational cost, and local optima avoidance, especially in solving multi-modal problems (Mirjalili et al. 2014).

Particle swarm optimization (PSO) algorithm is a nature-inspired population-based technique, attracting lots of attention since proposed by Kennedy and Eberhart (1995). In PSO, the social behavior of the bird flocks and fish schools is simulated. Through such a simulation, a population of particles can cooperate and transfer information to each other to search for the best regions in the space. In fact, two main tasks are implemented by particles in PSO: (1) exploration and (2) exploitation. The former task is pursued by interaction of all particles to address their own as well as other particles’ experiences in finding the promising regions in the search space. The latter task is implemented at the final iterations when the particles finish their global search and are left lethargic to further search. Due to the stochastic nature of PSO, the particles are tending to move toward personal best (Pbest) and global best (Gbest), sometimes more accelerated to move toward Pbests and sometimes more accelerated to reach to the Gbest. As a result, there is no guarantee for the particles to discard their low-fitness Pbests and move toward other regions of the search space. Thus, the particles can be trapped in local optima, contributing to premature convergence. To avoid premature convergence to improve the performance of the PSO, a large number of PSO variants have been proposed in the past two decades. These variants can be falling into four categories including: (1) population topology and multi-swarm techniques (Van den Bergh and Engelbrecht 2004; Janson and Middendorf 2005; Liang and Suganthan 2005), (2) parameter fine tuning (Clerc and Kennedy 2002; Ratnaweera et al. 2004; Shi and Eberhart 1998; Zhan et al. 2009; Družeta and Ivić 2016), (3) hybrid methods (Juang 2004; Shi et al. 2005; Grimaccia et al. 2007; Kao and Zahara 2008; Valdez et al. 2008; Premalatha and Natarajan 2009; Jeong et al. 2009; Zhang et al. 2009; Li et al. 2010, 2011; Liu et al. 2013; Zhang and Yang 2014); (4) novel learning schemes (Mendes et al. 2004; Liang et al. 2006; Zhan et al. 2011; Li et al. 2012; Ren et al. 2014). Although these variants are all attempting to increase population diversity to avoid premature convergence, but the quality of their solutions may be aggravated as a result of not holding a nice balance between exploration phase (as a step needed to further maintain diversity) and exploitation phase (which determines the quality of the final solutions obtained by the algorithm), mainly depending on the convergence ability of the algorithm (Gong et al. 2016). The novel learning schemes can be divided into two major categories: (1) the algorithms trying to tackle the cause of the problem and (2) the algorithms attempting to cope with the effect of the problem (Ostadmohammadi Arani et al. 2013). Here, an overview on the algorithms involved in the first category is presented and thereafter, a novel variant of PSO belonging to this category is proposed.

Peram et al. (2003) proposed a fitness-distance-ratio-based PSO (FDR-PSO) in which each particle prefers to interact with the best-so-far experience of the nearest neighbor. Janson and Middendorf (2005) introduced a hierarchical particle swarm optimization in which the particles are placed in the hierarchy based on their best-so-far found position. The higher rank a particle receives, the more the influence of that particle on the entire swarm will be. Liang et al. (2006) introduced a comprehensive learning particle swarm optimizer (CLPSO), in which all opposite particles’ Pbests contribute to update the velocity of a particle. Nasir et al. (2012) proposed a dynamic neighborhood learning-based particle swarm optimizer (DNLPSO) which is similar to CLPSO in its structure except that the guide particle is selected from a dynamically changed neighborhood. Ostadmohammadi Arani et al. (2013) proposed a territorial particle swarm optimization (TPSO), in which a new social interaction scheme is incorporated into the PSO which helps the particles to effectively exploit the local candidate regions in their neighborhood. Furthermore, a new collision operator is embedded in the PSO to prevent the poor particles from moving toward the better particles located in more-densely populated regions, in order to promote diversity of the solutions.

In the application fields of other well-known meta-heuristics mentioned in this section, a study was done to predict the heat transfer coefficients to obtain temperature distribution in a rectangular fin by simulated annealing (SA) (Das and Oor 2013). In a similar study, Das and Prasad (2015) applied differential evolution (DE) algorithm is used to predict the porosity and thermal diffusivity in a porous fin in order to determine the temperature distribution in the fin. They found out that DE is superior to SA and genetic algorithm (GA) to do their inverse prediction task. In other works, the Artificial Bee Colony (ABC) algorithm was applied to minimize the size of a solar collector, and the ABC was applied to maximize heat transfer in a perforated fin (Das et al. 2016a, b). Also, Das et al. (2017) hybridized DE with nonlinear programming (NLP) to estimate the critical dimensions for a trapezoidal-shaped steel fin.

1.2 Difficulties in meta-heuristic optimization and the proposed method

The major shortcoming of PSO and any other meta-heuristic algorithm is the ability to hold a suitable balance between exploration and exploitation phases of the optimization process. Some algorithms, including PSO, have strong capability to do exploitation with a high rate of convergence to the found promising areas in the search space, while some others, such as genetic algorithms (GA), benefit from a highly effective exploration capability with low convergence rate (Chang et al. 2013). Therefore, we believe that there is a need to boost both capabilities for exploration and exploitation processes for a given optimization algorithm so that it would be applicable to any kind of optimization problem, without a prior knowledge on the characteristics of the problem.

This paper aims to propose a novel improved variant of PSO algorithm, named guided adaptive search-based particle swarm optimization (GuASPSO) as an alternative learning scheme. As mentioned above, the original PSO algorithm benefits from a high exploitation capability, but lacks ability to suitably maintain diversity of the particles in the search space which could cause premature convergence. Unlike the original PSO, in GuASPSO, the diversity is recognized as a major player to guide the particles in the search space and the Gbest particles are calculated based on a dual fitness-diversity criterion. To implement this idea, a clustering algorithm is employed to divide the Pbest particles into a number of clusters, the density of each of which is calculated as the influence factor of the best particle in that cluster. Moreover, a nice compromise between exploration and exploitation is held via linearly decreasing the number of clusters over iterations.

The organization of this paper is as follows. Section 2 describes the methodology in two separate parts including original PSO algorithm and the self-organizing maps (SOMs) as the chosen clustering technique involved in the proposed method and the structure of the novel GuASPSO algorithm in details. In Sect. 3, the results are presented, separated in a number of subsections. Sects. 3.1 and 3.2 provide the details of benchmark functions and conduct a detailed discussion over the tests of the algorithms. Section 3.3 implements a multi-criteria analysis carried out to highlight the best-performing algorithm on each benchmark function and overall. Moreover, in Sect. 3.4, a statistical test is conducted to determine the significance of the outperformance of the best algorithms on each function and a runtime analysis is also provided in Sect. 3.5. Finally, Sect. 4 reviews the theory of the proposed algorithm, stressing its unique structure to better handle optimization problems and attempting to summarize and conclude the main advantages of the proposed algorithm against its other popular competitors, as the major contribution of this paper to the field of numerical optimization.

2 Methodology

2.1 Original particle swarm optimization (PSO) algorithm

For a D-dimensional optimization problem, it is taken that $X_{i} = \left( {x_{i1} , x_{i2} , \ldots , x_{iD} } \right)$ and $V_{i} = \left( {v_{i1} , v_{i2} , \ldots , v_{iD} } \right)$ are, respectively, the ith particle’s position vector and the velocity vector. If ${\text{Pbes}}t_{i}^{t} = \left( {p_{i1} , p_{i2} , \ldots , p_{iD} } \right)$ is the personal best (Pbest) position of the ith particle and ${\text{Gbest}}^{t} = \left( {p_{g1} , p_{g2} , \ldots , p_{gD} } \right)$ represents the global best (Gbest) position of the swarm, the velocity and position of each particle in PSO algorithm are updated using Eqs. (1) and (2) (Kennedy and Eberhart 1995).

$$ V_{i}^{t + 1} = wV_{i}^{t} + c_{1} r_{1} \left( {{\text{Pbest}}_{i}^{t} - X_{i}^{t} } \right) + c_{2} r_{2} \left( {{\text{Gbest}}^{t} - X_{i}^{t} } \right) $$

(1)

$$ X_{i}^{t + 1} = X_{i}^{t} + V_{i}^{t + 1} $$

(2)

where i Є{1, 2, …, N}; N is the swarm size and D is the number of dimensions; superscript t is the iteration number; w is the inertia weight; r₁ and r₂ are two random vectors, and c₁ and c₂ are cognitive and social scaling parameters, respectively. An efficient form of Eq. (1) is the constriction coefficient model shown below (Rezaei et al. 2017):

$$ V_{i}^{t + 1} = \chi \left[ {V_{i}^{t} + \varphi_{1} \left( {{\text{Pbest}}_{i}^{t} - X_{i}^{t} } \right) + \varphi_{2} \left( {{\text{Gbest}}^{t} - X_{i}^{t} } \right)} \right] $$

(3)

$$ \chi = \frac{2k}{{\left| {2 - \varphi - \sqrt {\varphi \left( {\varphi - 4} \right)} } \right|}}; \varphi = \varphi_{1} + \varphi_{2} ; \varphi_{1} = c_{1} r_{1} ; \varphi_{2} = c_{2} r_{2} $$

(4)

where χ is the constriction factor. The parameter k Є [0,1] in Eq. (4) controls the exploration and exploitation abilities of the swarm, which can be calculated as follows:

$$ k = k_{ \hbox{max} } - \frac{{k_{ \hbox{max} } - k_{ \hbox{min} } }}{{t_{ \hbox{max} } }} \times t $$

(5)

where k_max and k_min are constants that must be set properly; t is the number of iterations; t_max is the maximum number of iterations.

2.2 The present work

In this section, a new variant of PSO algorithm, named guided adaptive search-based particle swarm optimization (GuASPSO) algorithm, is introduced. The algorithms, such as particle swarm optimization (PSO) (Kennedy and Eberhart 1995), genetic algorithm (GA) (Tang et al. 1996), ant colony optimization (ACO) (Dorigo et al. 2006), gravitational search algorithm (GSA) (Rashedi et al. 2009) and some other meta-heuristics, utilize the local and/or global guides to conduct the search process. In these algorithms, the fitness (objective function value) of the solutions is evaluated as the main criterion to discriminate different solutions generated at each iteration. In this procedure, the solutions with the high fitness values are adopted to be the unique local guide for a solution as long as the Euclidean distance between the local guide solution and each solution is small enough. This mechanism for local guide selection can localize the search processes done by each particle. In some of these algorithms such as GSA, besides this mechanism, solutions are forced to move to the average of the opposite particles, thereby the diversity can be injected in the search space. These two mechanisms are used in common in a variety of the meta-heuristic algorithms. In the original PSO algorithm, similar mechanisms are implemented. In PSO, the personal best (Pbest) particles play the role of the local guides and the global best (Gbest) particle attempts to conduct global search in the search space. Indeed, the Pbests help the exploration process to be done in the search space and the Gbest leads the particles to the high-fitness areas in the search space to accomplish exploitation. In the most algorithms introduced so far such as PSO, the diversity of the solutions in each generation is not directly taken into account in the calculations to conduct the search agents. The GuASPSO algorithm attempts to change the conventional mechanism existing in the original PSO algorithm, mainly in order to better preserve diversity among the solutions generated in the swarm. In this proposed algorithm, a unique Gbest particle is assigned to each particle. In this way, the Gbest particle is neither so far from, nor so near to its relevant particle, meaning that it is neither involved in a drift leading to lose diversity in the search space, nor is going to be trapped in local optima. Accordingly, this Gbest computation mechanism can maintain the distances between the particles and their Gbests in a well-balanced manner to help a more proper exploration–exploitation balance to be held in the optimization process.

In GuASPSO algorithm, once a swarm of particles is generated, a newly generated particle is compared to its current Pbest and the particle having the best fitness is selected as the new Pbest particle. This procedure is performed over all particles of the swarm. Thus, the Pbest selection mechanism in the GuASPSO is just the same as in the original PSO algorithm, while the major difference is laid in the Gbest selection mechanism. Here, the self-organizing map (SOM) neural network is utilized to help to perform the Gbest selection mechanism. In the next subsection, the SOM structure is introduced and the training process of the SOM is explained and then, the rest of the details of the proposed algorithm are described.

2.2.1 Self-organizing map (SOM) clustering technique

SOM is a special type of artificial neural networks (ANNs) used for classification/clustering of a wide number of multi-dimensional data through an unsupervised training process. The SOM consists of an input layer and an output layer called Kohonen’s layer. The output layer can be one- or two-dimensional. Read more about SOM in Haykin (2009). The SOM algorithm is described as follows:

The input vector or input pattern presented to SOM for denoting its corresponding class/cluster can be defined by:

$$ X = \left[ {x_{1} ,x_{2} , \ldots , x_{D} } \right]^{\text{T}} $$

(6)

where D is the maximum number of features considered for each input pattern X. The weight vectors of the neurons in the output layer can be considered as:

$$ W_{i} = \left[ {w_{1i} ,w_{2i} , \ldots , w_{Di} } \right]^{\text{T}} ;i = 1, 2, \ldots , M $$

(7)

where $W_{i}$ is the weight vector of the neuron i in the output layer which is representing a cluster, D is the total number of dimensions of the neurons’ weight vectors and M is the number of neurons/clusters. Similar to any other type of neural networks, the SOM must be first trained to be prepared for clustering data sets/patterns. In the training process, all input patterns (here, the Pbest particles determined at each iteration) are inserted into the SOM network one-by-one. Once an input pattern is presented to the SOM, a competition is started between all SOM’s neurons. The Euclidean distance between each neuron’s weight vector and the input vector depicted by d_i is calculated through Eq. (8), and the neuron that minimizes this Euclidean distance is identified to be the corresponding cluster of the input vector and wins the competition.

$$ d_{i} = X - W_{i} = \sqrt {\mathop \sum \limits_{j = 1}^{N} \left( {x_{j} - w_{ij} } \right)^{2} } $$

(8)

After determining the winning neuron, some interactions begin between the winning neuron and its neighborhood in a one- or two-dimensional lattice of neurons. Thus, once a neuron wins the competition, this neuron activates other neurons lying in its neighborhood and the influence of the winning neuron is gradually decreased while the neighborhood radius increases. When a neuron wins the competition, it moves toward the imposed input vector (Pbest particle) by an updating rule. Thus, $W_{i} \left( t \right)$ is updated to $W_{i} \left( {t + 1} \right)$ by Kohonen’s rule as follows:

$$ W_{i} \left( {t + 1} \right) = W_{i} \left( t \right) + \eta \left( t \right)\left( {X - W_{i} \left( t \right)} \right) $$

(9)

where $W_{i} \left( t \right)$ is the ith neuron’s weight vector in the iteration t and $W_{i} \left( {t + 1} \right)$ is the weight vector of ith neuron at the iteration t + 1. $\eta \left( t \right)$ is the variable learning-rate parameter. One can define $\eta \left( t \right)$ to monotonically decrease when t increases, as follows:

$$ \eta \left( t \right) = \eta \left( 0 \right){ \exp }\left( {\frac{ - t}{{\tau_{1} }}} \right) $$

(10)

where $\eta \left( 0 \right)$ is set to 0.1 and $\tau_{1}$ is set to the maximum number of SOM iterations. In this paper, $\tau_{1}$ is set to be four times the number of the input vectors (Pbest particles) (Chen et al. 2011). In this way, the training process of the SOM network is carried out at each iteration of the proposed algorithm.

2.2.2 Proposed guided adaptive search-based particle swarm optimization (GuASPSO) algorithm

After training SOM network by the Pbest particles of the swarm generated at each iteration, the clustering process runs. In this process, the nearest (best-matching) neuron to each Pbest is determined and appointed to that Pbest as the center of its cluster. Thus, the SOM divides the Pbest particles into a variable adaptive number of clusters, such that based on Eq. (11) the number of clusters is high in the early iterations where diversity is needed to be further maintained and gradually decreases toward the last iteration to help the algorithm to converge to the promising regions found in the early iterations.

$$ N_{\text{cluster}} \left( t \right) = {\text{Round}}\left( {N_{\text{cluster}} \left( 1 \right) - \frac{{\left[ {N_{\text{cluster}} \left( 1 \right) - N_{\text{cluster}} \left( {t_{ \hbox{max} } } \right)} \right]}}{{\left( {t_{ \hbox{max} } - 1} \right)}} \times \left( {t - 1} \right)} \right) $$

(11)

where $N_{\text{cluster}} \left( t \right)$ is the number of clusters at the tth iteration and $t_{ \hbox{max} }$ is the maximum number of iterations. In this paper, $N_{\text{cluster}} \left( 1 \right)$ is set to be the swarm size and $N_{\text{cluster}} \left( {t_{ \hbox{max} } } \right)$ is set to the value of 2 as the number of clusters at the final iteration. So, the number of clusters is linearly decreased over iterations. Once the clustering is done, the clusters to which at least one Pbest particle is belonging are named the active clusters. Then, the inverted number of the Pbests collected in each of the active clusters is obtained as the inverted density of the given active clusters. Performing this procedure over all active clusters, an inverted density value is appointed to each active cluster. Defining the inverted density as the diversity, the less the density of an active cluster, the more the diversity that cluster could inject in the search space, will be. These inverted density values of each cluster can be taken as the weight of that cluster calculated as follows:

$$ W_{c}^{t} = 1/\left| {C_{c}^{t} } \right|;{\text{for }}\;{\text{the}}\;{\text{clusters }}\;{\text{whose}} \left| {C_{c}^{t} } \right| \ge 1 $$

(12)

where $W_{c}^{t}$ is the weight of the cth active cluster at the tth iteration and $\left| {C_{c}^{t} } \right|$ is the number of the Pbest particles collected in the cth active cluster at the tth iteration. Then, the best Pbest particle placed in each active cluster is designated by evaluating the Pbests involved in each cluster based on their fitness (objective function) values. The best Pbest found in this way is named the best of the own active cluster or the Cbest particle. Finally, the unique Gbest particle for each particle can be calculated via a weighted averaging over all other (opposite) Cbests, i.e., all cluster centers excluding the cluster center to which the focused particle’s Pbest is belonging. Meanwhile, the weights in the weighted average are just the same weights calculated by Eq. (12). Eq. (13) depicts the way to calculate the Gbest for each particle.

$$ {\text{Gbest}}_{i}^{t} = \frac{{\mathop \sum \nolimits_{{\begin{array}{*{20}c} {j = 1} \\ {j \ne c\left( i \right)} \\ \end{array} }}^{{N_{\text{cluster}} \left( t \right)}} W_{j}^{t} \times {\text{Cbest}}_{j}^{t} }}{{\mathop \sum \nolimits_{{\begin{array}{*{20}c} {j = 1} \\ {j \ne c\left( i \right)} \\ \end{array} }}^{{N_{\text{cluster}} \left( t \right)}} W_{j}^{t} }} $$

(13)

where ${\text{Gbest}}_{i}^{t}$ is the unique Gbest particle for the ith particle at the tth iteration, $W_{j}^{t}$ is the weight calculated for the jth cluster at the tth iteration, ${\text{Cbest}}_{j}^{t}$ is the Cbest particle of the jth cluster at the tth iteration and $c\left( i \right)$ is the cluster to which the ith Pbest particle is belonging. Thus, Eq. (3) is changed to Eq. (14) in GuASPSO algorithm by replacing ${\text{Gbest}}^{t}$ by ${\text{Gbest}}_{i}^{t}$. Other calculations, updating relations and parameter settings, are just as the same of the original PSO algorithm.

$$ V_{i}^{t + 1} = \chi \left[ {V_{i}^{t} + \varphi_{1} \left( {{\text{Pbest}}_{i}^{t} - X_{i}^{t} } \right) + \varphi_{2} \left( {{\text{Gbest}}_{i}^{t} - X_{i}^{t} } \right)} \right] $$

(14)

In GuASPSO, at the first iterations, the number of clusters is large, such that nearly all single Pbests or the Pbests located in the less-densely populated regions are gathered in separate clusters. As a result, the fitness values of the cluster best particles (Cbests) are endowed less influence factor to guide the particles in the search space and the inverted density (diversity) values of the clusters are imparted more influence factor. Accordingly, in the early iterations, it is possible to find a Cbest conducting the particles, while it is lacking a suitable fitness value. By lapse of iterations, the number of active clusters is decreased and the low-fitness Pbests with high degree of similarity are aggregated in the common clusters. Thus, by determining the Cbests of the clusters, it is more probable that the designated Cbests have relatively more fitness values than those they had in the previous iterations. Consequently, the influence factor of the diversity is less stressed and the influence factor of the fitness is more stressed as the iterations go by. This process could assist the algorithm to hold a suitable balance between exploration, in which the diversity of the solutions is the major problem and the exploitation, in which the solutions attempt to converge to the optimal point of the promising regions found in the exploration process. The steps of the GuASPSO algorithm are as follows:

Step 1:

Initializing PSO by providing uniformly distributed random numbers as the decision variables of the particles included in a swarm, setting t = 1, in which t is the number of iterations.

Step 2:

If t = 1, then considering each particle as its Pbest particle, otherwise comparing each particle with its Pbest and setting the particle having the best objective function value as the new Pbest particle, then recording the best Pbest particle in an external archive as the best-so-far solution obtained till the current iteration.

Step 3:

Training SOM Presenting each Pbest to the neurons of the SOM at each iteration, finding the nearest neuron (the neuron having the minimum Euclidean distance to the imposed Pbest) and updating the nearest neuron’s weight vector and continuing this procedure to reach the final SOM iteration when all Pbests are imposed to the network for a number of times.

Step 4:

Clustering by SOM Determining the nearest (best-matching) neuron to each Pbest and appointing it as the cluster of that Pbest.

Step 5:

Comparing the fitness (objective function) values of the Pbests collected in each cluster to designate the best particle of that cluster (Cbest).

Step 6:

Calculating the inverted number of the Pbests included in each cluster as the weight of that cluster.

Step 7:

Calculating the weighted average over the Cbests of all clusters excluding the cluster in which the focused particle’s Pbest is located, attributing the obtained weighted average value to the focused particle as its unique Gbest and continuing this procedure to assign the unique Gbests to all particles.

Step 8:

Updating the velocity and position of all particles based on the relevant equations and setting t = t + 1.

Step 9:

If the termination criteria are satisfied, stop the algorithm and go to step 10, otherwise go to step 2.

Step 10:

Repeating the steps 1–9 for a given number of runs and calculating the average, median, best, and the standard deviation of the best-so-far solutions at the last iteration of all runs as the final results of optimization, averaging the best-so-far solutions recorded in the external archive at each iteration over all runs to plot the convergence curve of the GuASPSO algorithm.

Step 11:

Stop. A detailed flowchart of the GuASPSO algorithm is shown in Fig. 1.

Fig. 1

The flowchart of GuASPSO

3 Results and discussion

3.1 Benchmark functions

To validate the GuASPSO algorithm in solving optimization problems, we tested the implementation of the algorithm on 23 benchmark functions (Yao et al. 1999) along with four other popular algorithms. The functions are divided into three categories including: (1) high-dimensional uni-modal problems, (2) high-dimensional multi-modal problems and (3) fixed-dimension multi-modal problems. Thus, these benchmark functions provide a large variety of difficulties some of which challenge the algorithms in exploitation phase and in their ability to converge to the global optimum and some test the capability of the algorithms in exploration process, evaluating whether the optimization algorithms can avoid being trapped in local optima. The benchmark functions are displayed in detail in Tables 1, 2 and 3. All benchmark functions are to be minimized. The minimum values for the benchmark functions shown in Tables 1 and 2 are zero, except for $F_{8}$ which has a minimum value of − 418.9829 × n, in which n is the number of dimensions (decision variables). The value of n illustrated in Tables 1 and 2 is set to 30 for high-dimensional uni-modal and high-dimensional multi-modal benchmark functions. A detailed description of the parameters emerging in the benchmark functions depicted in Table 3 can be found in “Appendix 1”.

Table 1 High-dimensional uni-modal benchmark functions

Table 2 High-dimensional multi-modal benchmark functions

Table 3 Fixed-dimension multi-modal benchmark functions

3.2 Comparison with popular algorithms

For doing precise comparisons and figuring out the competence of the GuASPSO algorithm to tackle the difficulties of the optimization problems, the GuASPSO was compared with four well-known robust algorithms. These algorithms include: (1) genetic algorithm (GA) (Tang et al. 1996) as the most well-known evolutionary algorithms; (2) gravitational search algorithm (GSA) proposed by Rashedi et al. (2009), as a robust physics-based meta-heuristic algorithm; (3) gray wolf optimizer (GWO), first introduced by Mirjalili et al. (2014), as a supreme, newly proposed, swarm-intelligence technique, and (4) original particle swarm optimization (PSO) algorithm proposed by Kennedy and Eberhart (1995), as the most popular swarm-intelligence algorithm.

To do a fair comparison, the population size of all algorithms was set to 50 and a maximum of 1000 and 500 iterations were considered for all algorithms for, respectively, the high- and fixed-dimensional problems. All algorithms were run for 30 independent times, and the best-so-far solution obtained in the last iteration of each run was taken as the main result of the optimization. Then, the average, median, best, and standard deviations of the values of the best-so-far solutions over 30 runs were calculated and employed as the major performance criteria for testing the abilities of any single-objective optimization algorithm. The termination criterion was met when the algorithm reached the maximum number of iterations. The detailed results of the implementation of the algorithms are displayed in Tables 4, 5 and 6. Note that in these tables “Std” represents standard deviation. In addition, the convergence curves of the algorithms depicted for all benchmark functions are displayed in Figs. 2, 3, 4 and 5. The details of comparisons performed over all algorithms when being applied to the benchmark functions are given in the next three subsections each of which is reporting the results obtained from running the algorithms on a particular category of the benchmark functions explained in Sect. 3.1. It is noteworthy that in all comparisons, “an algorithm outperforms the other one(s)” means “that algorithm outperforms or equally performs as the other algorithm(s),” wherever not clearly mentioned.

Table 4 Minimization results of benchmark functions presented in Table 1 with n = 30

Table 5 Minimization results of benchmark functions presented in Table 2 with n = 30

Table 6 Minimization results of benchmark functions presented in Table 3

Fig. 2

Convergence curves obtained for a$F_{1}$; b$F_{2}$; c$F_{3}$; d$F_{4}$; e$F_{5}$; f$F_{6}$ and g$F_{7}$

Fig. 3

Convergence curves obtained for a$F_{8}$; b$F_{9}$; c$F_{10}$; d$F_{11}$; e$F_{12}$ and f$F_{13}$

Fig. 4

Convergence curves obtained for a$F_{14}$; b$F_{15}$; c$F_{16}$; d$F_{17}$; e$F_{18}$ and f$F_{19}$

Fig. 5

Convergence curves obtained for a$F_{20}$; b$F_{21}$; c$F_{22}$ and d$F_{23}$

3.2.1 Comparison on the high-dimensional uni-modal benchmark functions

Among a wide number of problems, the uni-modal ones need less emphasis on the exploration phase, as nearly any algorithm can find out the optimum or near-optimum region of the search space for these problems; however, they could completely converge to the optimal point in the found region as long as the search space is small enough. Moreover, the high-dimensional uni-modal problems need well-balanced exploration–exploitation processes, while the low-dimensional uni-modal problems demand higher exploitation and lower exploration capabilities which should be provided by the optimization algorithms.

The experimental results indicated absolute superiority of the proposed GuASPSO algorithm to the original PSO in 27/28 (96%) performance criteria, while the PSO outperforms or performs equally to GuASPSO in only 3/28 (11%) of the criteria. This excellent performance was predictable regarding to the well-designed structure of GuASPSO which directly takes the diversity of the solutions into account over whole optimization process without disrupting the local search process, mainly due to adapting the global and local search with the number of iterations. In addition, the GuASPSO reached smaller standard deviations in 78% versus 30% for PSO over all benchmark functions, marking GuASPSO as a much more reliable algorithm compared to PSO. The GuASPSO is also performing better than all comparative algorithms in solving uni-modal functions by 50% superiority versus 0%, 11%, 36%, and 18% outperformance rate for GA, GSA, GWO, and PSO algorithms, respectively. The detailed results of applying the algorithms to the high-dimensional uni-modal functions are seen in Table 4. Also Fig. 2 depicts the convergence curves of the benchmark functions involved in the first category of the functions examined in this paper.

3.2.2 Comparison on the high-dimensional multi-modal benchmark functions

The multi-modal problems require further stressing on the exploration phase to figure out all local optima in the search space. The high-dimensional multi-modal problems intensify the need to further stress on the exploration process. The results indicate absolute superiority of GuASPSO compared to original PSO algorithm by achieving the outperformance rate of 71% versus 29% in the performance criteria of this category of benchmark functions. This dominance was extended when comparing the GuASPSO with other robust algorithms examined in this paper, such that the results represented outperformance of the GuASPSO in 11/24 (46%) of the whole criteria, while the comparative algorithms performed better or equally to others by the rates of 21%, 25%, 17%, and 0% for GA, GSA, GWO, and PSO, respectively. Furthermore, the proposed algorithm achieved the smaller standard deviations in 67% of the test problems of this category, benchmarking the GuASPSO as a much more reliable algorithm which ensures the users of the minimum differences among the solutions obtained over numerous runs. This would contribute to avoiding large number of runs which alleviate running time of the algorithm. In comparison, the original PSO had the worst performance in solving high-dimensional multi-modal functions, mainly due to the Gbest selection mechanism, contributing the global search of the algorithm to be implemented in an inappropriate way. In fact, there is a general Gbest particle for all particles in the swarm in PSO algorithm which possibly causes a drift in the search space which could reduce diversity among solutions. The detailed results of applying the algorithms on the high-dimensional multi-modal functions are seen in Table 5. Also Fig. 3 illustrates the convergence curves of the benchmark functions involved in the second category of the functions examined in this paper, which helps to better understanding the behavior of the proposed algorithm versus other algorithms in such a difficult family of the problems.

3.2.3 Comparison on the fixed-dimension multi-modal benchmark functions

This category of problems contains a variety of low-dimensional multi-modal problems. An algorithm is required to consider even roles for the exploration and exploitation processes to solve this category, as the problems in this category are neither uni-modal to require an algorithm to have only high exploitation capability, nor high-dimensional to need high exploration capability, to be properly solved. In this category, the results obtained for GuASPSO and PSO are getting closer, such that the original PSO has edge to GuASPSO by outperforming in 78% versus 63% of the performance criteria. This was mainly because of the low-dimensionality of the problems. In fact, the original PSO algorithm has edge to all other comparative algorithms by an outperformance rate of 68% versus 63%, 48%, 35%, and 60% rates obtained for GA, GSA, GWO, and GuASPSO, respectively. These digits recommend the original PSO algorithm as a suitable optimization algorithm mostly for solving small-scale problems, while the GuASPSO algorithm can present itself as a versatile algorithm, being able to solve any types of optimization problems, from uni-modal to multi-modal and low-dimensional to high-dimensional problems. This capability, due to the perfect balance between exploration and exploitation phases, can ensure GuASPSO users of the algorithm’s suitability for solving the optimization problems with no prior knowledge about their structure, function shape, and degree of complexity. The detailed results of applying the algorithms to the fixed-dimension multi-modal functions are seen in Table 6. Also Figs. 4 and 5 illustrate the convergence curves of the benchmark functions involved in the third category of the functions examined in this paper.

3.2.4 Overall comparison

Overall, the GuASPSO was superior to all comparative algorithms in solving the majority of three categories of the optimization problems by the outperformance rate of 53% versus 33%, 33%, 30%, and 33% rates for GA, GSA, GWO, and PSO, respectively. The proposed algorithm also performed better than other algorithms in achieving the best solutions over 30 runs in 61% of all cases, while this rate did not exceed 48% for the comparative algorithms. In addition, the GuASPSO was acknowledged as the most reliable algorithm, reaching the rate of 57% outperformance to have the least standard deviations among the solutions found over all implementations on all benchmark functions, while the least standard deviation values have achieved in 22%, 26%, 17%, and 22% of cases for GA, GSA, GWO, and PSO, respectively. The key factor contributing the GuASPSO algorithm to receive both titles of the best-performing and the most reliable algorithm among a number of popular algorithms is hidden in its capability not to only directly take the diversity of the solutions into consideration for selecting the guide particles, but to also hold a perfect balance between exploration and exploitation processes which helps the proposed algorithm to succeed in both processes to a sufficient degree.

3.3 Multi-criteria analysis

Since there were four performance criteria used to compare the examined algorithms on each benchmark function, one can figure out that it is possible that for a benchmark function no algorithm is absolutely superior. For instance, it is possible for four algorithms each of which outperforms others in just one criterion or for two algorithms each of which performs better than others in two criteria. Furthermore, the degree of outperformance in the performance criteria may be different, such that an algorithm may be superior to others in one criterion while another algorithm outperforms in two other criteria, but the degree of outperformance of the first algorithm is much higher than that of the second algorithm. In addition, there are 23 different standard benchmark functions employed to test the examined algorithms. Thus, one may desire to know which algorithm is superior to others overall the benchmark functions suite. These questions necessitate the use of multi-criteria analysis methods to provide a whole comparison among all algorithms. Among such methods, compromise programming (Zeleny 1973) was selected as a suitable tool to do the desired comparison. In compromise programming, there are a number of solutions versus a number of criteria. Each solution has a performance in each of criteria. Finally, the compromise programming index can be calculated as follows:

$$ {\text{CPI}} = \sqrt {\mathop \sum \limits_{i = 1}^{{N_{c} }} w_{i}^{2} \left( {\frac{{Z_{i} - Z_{{i,{\text{best}}}} }}{{Z_{{i,{\text{worst}}}} - Z_{{i,{\text{best}}}} }}} \right)^{2} } $$

(15)

where $Z_{i}$ is the ith criterion, $Z_{{i,{\text{best}}}}$ is the best ith criterion, $Z_{{i,{\text{worst}}}}$ is the worst ith criterion, $w_{i}$ is the weight assigned to the ith criteria, $N_{c}$ is the number of criteria and CPI is the compromise programming index used for wholly comparing the solutions (algorithms). The smaller this index, the better the solution (algorithm) having that index will be, compared to other solutions (algorithms). In this paper, the compromise programming analysis was carried out in two steps. In the first step, the overall performance of the algorithms in each of the benchmark functions was evaluated considering the average, median, best, and standard deviation of the best-so-far solutions at the final iteration as the criteria. At the second step, the overall performance of the algorithms over all benchmark functions was measured considering the CPIs obtained for each algorithm in each function as the criteria. All weights were set to one to impart even importance degrees to the criteria in the analysis. The results are seen in Table 7.

Table 7 The multi-criteria compromise programming analysis indices calculated over all benchmark functions

The analysis indicated that the GuASPSO algorithm held the smallest CPIs in 3 out of 7 benchmark functions over the high-dimensional uni-modal problems and in 3 out of 6 benchmark functions over the high-dimensional multi-modal problems. Also the proposed algorithm was superior to other algorithms in 4 out of 10 fixed-dimension test problems. In all the benchmark problems except for the third category, the GuASPSO held the highest number of outperformance cases. Having compared algorithms over all benchmark functions, the GuASPSO was suggested to be superior in uni-modal and multi-modal test functions, while conceding the dominance to the original PSO in the fixed-dimension multi-modal functions. Overall, the proposed GuASPSO algorithm has received the CPI of 3.5098 versus the indices of 4.5413, 4.0812, 3.8920, and 3.9624 for GA, GSA, GWO, and PSO algorithms, respectively, demonstrating the total outperformance of the proposed algorithm in solving all types of the benchmark functions.

3.4 Wilcoxon statistical analysis

The Wilcoxon rank-sum test is a nonparametric test in statistics that can be used to determine if two sets of solutions are statistically different to a significant degree. In this method, one algorithm is taken as the base and other algorithms are compared to this base algorithm to delineate the degree of significance of dominance of the basic algorithm over other algorithms. The Wilcoxon test also examines the null hypothesis. If the results of both paired algorithms are of the same distribution, the base algorithm rejects the null hypothesis and otherwise, it fails to reject the null hypothesis, meaning that the differences among the base algorithm and the other algorithms are not statistically significant. This statistical test returns a parameter called p-value. In fact, the p value determines the significance level of two algorithms (García et al. 2008). In this work, an algorithm is statistically significant if it results in a p value less than 0.05. The results of the Wilcoxon rank-sum test are presented in Table 8 in which the test results of the best algorithm, determined in the multi-criteria analysis in the previous subsection, are displayed for each benchmark function,. For the benchmark functions in Table 8, the expression N/A for an algorithm on a specific function represents that that algorithm was Not Applicable in the Wilcoxon test on that benchmark function. In other words, that algorithm was taken as the base in the comparisons on that specific benchmark function. For making the test results more concise and efficient, only the algorithm that outperforms other ones was taken as the N/A algorithm on each of the benchmark functions. The results suggest that the superiority of the proposed GuASPSO algorithm is absolutely significant over $F_{1}$, $F_{2}$, $F_{4}$ and $F_{10}$. Generally, the results generated by the algorithms were much more statistically significant when applied on the first 13 benchmark functions. Unlike, the results of the algorithms are slightly different on 10 fixed-dimension multi-modal functions in which almost all p values exceeded 0.05. Furthermore, on $F_{16}$, $F_{17}$, $F_{18}$, and $F_{19}$, more than one algorithm were taken as the N/A algorithm, since on these functions, a number of algorithms generated the same optimal function values at the last iteration of the optimization process. Overall, the proposed GuASPSO was outperforming other competitors on 40 cases, from which 22 cases rejected the null hypothesis. The GA, GSA, GWO, and PSO algorithms were superior to other algorithms on 28, 28, 12, and 24 cases, respectively, rejecting the null hypothesis on, respectively, 3, 3, 7, and none of their outperformance cases. Therefore, the Wilcoxon test suggests superiority of the proposed GuASPSO algorithm in not only producing much better results, but also in the higher significance in results as compared to other state-of-the-art algorithms examined in this paper.

Table 8 p values of the Wilcoxon rank-sum test over all benchmark functions

3.5 Comparative complexity

The researchers usually measure the computational efficiency of an algorithm as the number of basic operations it performs as a function of its inputs. Hence, the efficiency of an algorithm could be calculated by a function T on a set of natural numbers such that T(n) is the maximum number of basic operations that the algorithm implements on the inputs having length n. However, this function is sometimes totally dependent on the details of the definition of a basic operation. For example, an algorithm will take about three times more operations if it utilizes single-digit binary (i.e., base 2) numbers, as compared to when it is handling decimal (i.e., base 10) numbers (Arora and Barak 2007).

Here, the complexity of the proposed PSO and GuASPSO algorithms is reported based on a standard method suggested by Suganthan et al. (2005) in CEC 2005 special session. This method can reflect the algorithm complexity and does not define it, as a result of the fact that this method simultaneously takes the algorithm complexity, fitness function complexity and also the computer hardware properties into account, when reflecting the complexity. The results are seen in Table 9, where T₀ is the computing time in seconds for a standard loop shown in Fig. 6, T₁ is computing time of the function 3 of CEC 2005 for 200,000 function evaluations in seconds and Ť₂ is the mean of the computing time for the algorithms employed to solve the function 3 of CEC 2005 with 200,000 function evaluations for 5 times in seconds. Here, only PSO and GuASPSO are compared in terms of their computational complexity for three reasons: (1) the PSO is a well-known meta-heuristic algorithm with a known and very low computational complexity and thus, one can figure out from this comparison that how low the complexity of the proposed algorithm is, (2) the PSO is the base of the proposed GuASPSO algorithm and the difference between their complexities can actually reflect the additional complexity of the modifications and revisions made to the original PSO to obtain GuASPSO algorithm and (3) the codes of the PSO and GuASPSO are both written by the authors with the same programming skills which can make all comparisons between these algorithms complexities fair and plausible to report.

Table 9 Computational complexity of PSO and GuASPSO

Fig. 6

The standard loop whose computing time is taken as T₀ (Suganthan et al. 2005)

As can be seen in Table 9, the complexity of the proposed GuASPSO algorithm is 5.3541, 2.3050, and 1.4536 times of the original PSO algorithm for 10-, 30-, and 50-dimensional problems, respectively. For each case, the swarm size is set directly proportional to the dimensionality of the problem. As can be seen, the complexity of the GuASPSO can be further mitigated and more competitive to the PSO, when applied to solve higher-dimensional and thus, more expensive problems, namely the problems having more expensive objective function evaluations, such as the real-world engineering problems. It is worthwhile mentioning that all algorithms were run in the MATLAB-R2017a environment on an Intel Quad-core computer with 2.8 GHz CPU and 16 GB of memory.

4 Conclusion

This paper proposed a new approach, named GuASPSO, to hold a better balance between exploration and exploitation in particle swarm optimization (PSO) algorithm. The GuASPSO algorithm benefits from a self-organizing map (SOM) neural network to divide the personal best (Pbest) particles into an adaptively tuned number of clusters. Then, the inverted density of each cluster is calculated and taken into account as the weight assigned to the best particle located in that cluster, named cluster best (Cbest) particle of that cluster. Having weighted all Cbests, a weighted average over all Cbests excluding the Cbest of the cluster to which the focused particle is belonging, is calculated and named as the unique global best (Gbest) of the focused particle. This process is extended to find out the Gbests of all particles. The Gbests were proved to be more suitable guides for the particles, helping them in a much more extensive search in the space. In the proposed algorithm, the number of clusters is varied over the iterations in a descending manner. The diversity of the particles is much more emphasized at the early stages of the optimization, while the fitness of the solutions is less stressed. As the iterations pass, the diversity is less emphasized, while the role of the fitness in assigning Gbests to the particles is more highlighted. This procedure was proved to enable the proposed algorithm to hold a nice exploration–exploitation balance, which is a serious problem any optimization algorithm, including the original PSO, suffers from. The experimental results validated the proposed GuASPSO algorithm using applications on 23 standard benchmark functions and comparing the results with four other popular meta-heuristics. Because of the multi-criteria nature of all comparisons performed in this paper, finally, a compromise programming multi-criteria analysis was implemented over all performance criteria obtained in each test problem at the first step and over all test problems at the second step. Furthermore, a Wilcoxon test was carried out to benchmark the significance of the numerical outperformance of the algorithms compared to each other in different cases. The results showed the significant statistical superiority of the GuASPSO algorithm in the majority of the statistical cases when solving high-dimensional uni-modal, high-dimensional multi-modal, and fixed-dimension multi-modal problems. These results rated the proposed algorithm as a robust, well-designed algorithm to handle any type of the optimization problems, especially large-scale optimization problems. As the future work, we aim to further validate the GuASPSO algorithm through testing it on real-world engineering problems as the practical applications in the field of optimization.

Appendix A

See Tables 10, 11, 12, 13, 14, 15, 16, 17.

Table 10 $a_{ij}$ in $F_{14}$

Table 11 $a_{i}$ and $b_{i}$ in $F_{15}$

Table 12 $a_{ij}$ and $c_{i}$ in $F_{19}$

Table 13 $P_{ij}$ in $F_{19}$

Table 14 $a_{ij}$ and $c_{i}$ in $F_{20}$

Table 15 $P_{ij}$ in $F_{20}$

Table 16 $a_{ij}$ and $c_{i}$ in $F_{21}$, $F_{22}$ and $F_{23}$

Table 17 Optima in functions presented in Table 3