Grasshopper optimization algorithm with principal component analysis for global optimization

Abstract

As one of the latest meta-heuristic algorithms, the grasshopper optimization algorithm (GOA) has extensive applications because of its efficiency and simplicity. However, the basic GOA still has enough room for improvement. Therefore, a new variant GOA algorithm which combines two strategies, namely PCA–GOA, is proposed. Firstly, principal component analysis strategy is employed to obtain the grasshoppers with minimally correlated variables, which can improve the exploitation capability of the GOA. Then, a novel inertia weight is proposed to balance exploration and exploitation in an intelligent way, which makes the GOA to have better search capability. Furthermore, the performance of PCA–GOA is evaluated by solving a series of benchmark functions. The experimental results manifest that the PCA–GOA provides better outcomes than the basic GOA and other state-of-the-art algorithms on the majority of functions, which demonstrates the superiority of the PCA–GOA.

1 Introduction

Optimization is used to select the best options among all the solutions, and it exists in many fields such as scheduling problem, parameter estimation, materials prediction and structure design [1,2,3,4,5]. However, it is difficult to solve the high dimension optimization problems with the traditional optimization algorithms, and this issue has drawn much attention of researchers [6]. It is reported that the heuristic and meta-heuristic algorithms show superiority on complex optimization tasks. The majority of these algorithms are proposed based on natural phenomena. Some of the typical algorithms are genetic algorithm (GA) which is inspired from genetic mechanism [7], and particle swarm optimization (PSO) is proposed based on the behavior of birds [8]. Some recent optimization algorithms employ the ant colony optimization (ACO) [9], artificial bee colony algorithm (ABC) [10], firefly algorithm (FA) [11], cuckoo search (CS) [12], gravitational search algorithm (GSA) [13], bat algorithm (BA) [14], gray wolf optimization (GWO) [15] and moth-flame optimization algorithm (MFO) [16]. In addition, modifying the existing algorithms is an important work, and it helps using the hardware better. This point is also meaningful to supercomputing [17]. Graphics processor units (GPUs) have been widely used for large number computation due to its high performance [18]. If the optimization algorithm runs on GPU, the execution time will be shorter [19].

The grasshopper optimization algorithm (GOA) is newly proposed to solve optimization problems. The advantages of the GOA have been proven by comparing with some well-known and latest algorithms [20]. Therefore, practitioners and researchers are interested with employing the GOA to solve the various optimization problems. Aljarah et al. [21] used the GOA to solve the feature selection and support vector machine problem. Zhang et al. [22] applied GOA to analyze vibration signals. Wu and Wang [23] had applied adaptive GOA to trajectory optimization problem. Hekimoğlu and Ekinci [24] applied GOA to automatic voltage regulator system. Łukasik et al. [25] used GOA to solve data clustering problem. Lal et al. [26] applied GOA to optimize fuzzy PID controller. Fathy [27] used GOA to solve reconfiguration of PV array problem.

The basic GOA is a promising algorithm and has been successfully applied to many fields. However, the basic GOA has some shortcomings, such as limited exploitation capability and premature [28]. Therefore, many researchers are interested in improving the GOA. Ewees et al. [29] proposed a novel improved GOA which combined opposition-based learning (OBL) strategy. The outstanding performance of the proposed GOA was proved by benchmark functions and engineering problems. Saxena et al. [30] used chaotic strategy with 10 maps to enhance bridging mechanism of GOA. The results proved the efficiency of the improved GOA. In multilevel thresholding image segmentation, Liang et al. [31] presented a modified GOA, which combined the Levy flight algorithm. To overcome the drawbacks of the basic GOA algorithm, Luo et al. [32] proposed an improved GOA and applied to financial stress predicting problem. Three strategies named Gaussian mutation, Levy flight and opposition-based learning were integrated into GOA. The experiment results indicated that the modifications can significantly improve the basic GOA.

As we can see above, many versions of GOA have been proposed. However, the enhanced GOA algorithms are far from perfect. To further improve the GOA, an enhanced grasshopper optimization algorithm, namely PCA–GOA, is proposed. The main contributions of the paper are as follows:

• (a) In the PCA–GOA, the principal component analysis is incorporated to generate the new population with high quality. Then, the generated population is used to replace the population with bad fitness values. This operation is able to improve the exploitation capability of the GOA.

• (b) The novel inertia weight is introduced to control the search process in an intelligent way. Under this strategy, the grasshoppers with better fitness values move quickly to the target grasshopper and the grasshoppers with worse fitness values maintain strong exploration capabilities. Therefore, novel inertia weight plays a role in both enhancing the exploration and exploitation capability.

The structure of the rest of this paper is as follows. Section 2 presents the basic GOA algorithm. Section 3 shows the proposed PCA–GOA algorithm. Section 4 provides discussions and analyses of the experiment results. Section 5 concludes the paper.

2 Basic grasshopper optimization algorithm

The basic grasshopper optimization algorithm (GOA) was originated by Saremi and Mirjalili [20], which mimics the behavior of grasshopper. The mathematical model of the GOA can be expressed as follows:

$$ X_{i} = S_{i} + G_{i} + A_{i} $$

(1)

where $X_{i}$ is the position of the $i{\text{-th}}$ grasshopper, ${\text{S}}_{i}$ represents the social interaction, $G_{i}$ denotes the gravity force of the $i{\text{-th}}$ grasshopper, ${\text{A}}_{i}$ refers the wind advection.

$$ S_{i} = \mathop \sum \limits_{{\begin{array}{*{20}c}_ {j = 1} \\ _{j \ne i} \\ \end{array} }}^{N} s\left( {d_{ij} } \right)\frac{{x_{j} - x_{i} }}{{d_{ij} }} $$

(2)

$$ d_{ij} = \left| {x_{j} - x_{i} } \right| $$

(3)

where $x_{i}$ and $x_{j}$ are the positions of $i{\text{-th}}$ and $j{\text{-th}}$, respectively. $d_{ij}$ denotes the distance of $i{\text{-th}}$ and $j{\text{-th}}$ grasshoppers. The $s$ function represents social force is given as follows:

$$ s\left( r \right) = fe^{{ - \frac{r}{l}}} - e^{ - r} $$

(4)

where $f$ is the intensity of attraction, $l$ denotes the attractive length scale.

$$ G_{i} = - g\hat{e}_{g} $$

(5)

where $g$ denotes the gravitational constant, $\hat{e}_{g}$ is unity vector.

$$ A_{i} = u\hat{e}_{w} $$

(6)

where $u$ denotes a constant drift, $\hat{e}_{w}$ represents a unity vector.

The mathematical model can be written as:

$$ X_{i} = \mathop \sum \limits_{{\begin{array}{*{20}c} _{j = 1} \\ _{j \ne i} \\ \end{array} }}^{N} s\left( {\left| {x_{j} - x_{i} } \right|} \right)\frac{{x_{j} - x_{i} }}{{d_{ij} }} - g\hat{e}_{g} + u\hat{e}_{w} $$

(7)

where $N$ defines the number of grasshoppers.

In order to solve the optimization problem in a better way, a modified GOA is expressed as follows:

$$ X_{i}^{d} = c\left. {\left\{ {\mathop \sum \limits_{{\begin{array}{*{20}c} _{j = 1} \\_ {j \ne i} \\ \end{array} }}^{N} c\frac{{ub_{d} - lb_{d} }}{2}s\left( {\left| {x_{j}^{d} - x_{i}^{d} } \right|} \right)\frac{{x_{j} - x_{i} }}{{d_{ij} }}} \right.} \right\} + \hat{T}_{d} $$

(8)

where $ub_{d}$ and $lb_{d}$ are the upper bound and lower bound, $\hat{T}_{d}$ is a target grasshopper. $c$ is the parameter, which used to balance exploration and exploitation. $c$ can be given by:

$$ c = c_{{\rm max} } - l\frac{{c_{{\rm max} } - c_{{\rm min} } }}{L} $$

(9)

where $c_{{\rm max} }$ and $c_{{\rm min} }$ are the maximum value and the minimum value, $l$ is the number of current iterations, $L$ denotes the maximum number of iterations.

3 The proposed PCA–GOA algorithm

3.1 Principal component analysis

In basic GOA, the grasshoppers fly around the target grasshopper, which leads redundancy that reduces the diversity of population. More importantly, the grasshoppers with bad fitness have the low possibility to reach the optimal solution. In this work, principal component analysis is introduced to solve this problem. Principal component analysis is an important statistical analysis method, which has two main functions that are data reduction and interpretation [33, 34]. The minimally correlated variables can be transformed from correlated variables by principal component analysis [35]. In the PCA–GOA algorithm, the new generated solutions are minimally correlated and show the information of original solutions. Furthermore, the new solutions may have better quality than the original solutions, which enhance the exploitation capability of the GOA. Let that $U = \left( {U_{1} ,U_{2} \ldots ,U_{p} } \right)^{'}$ is an exemplar of the original data set, and it can be expressed as follows:

$$ U = \left( {\begin{array}{*{20}c} {u_{11} } & {u_{12} } & . & . & . & {u_{1n} } \\ {u_{21} } & {u_{22} } & . & . & . & {u_{2n} } \\ . & . & . & {} & {} & . \\ . & . & {} & . & {} & . \\ . & . & {} & {} & . & . \\ {u_{p1} } & {u_{p2} } & . & . & . & {u_{pn} } \\ \end{array} } \right) = \left( {\begin{array}{*{20}c} {\begin{array}{*{20}c} {\begin{array}{*{20}c} {U_{1} } \\ {U_{2} } \\ \end{array} } \\ . \\ \end{array} } \\ . \\ . \\ {U_{p} } \\ \end{array} } \right) $$

(10)

where $p$ represents the number of exemplars. The linear transformations can be calculated as follows:

$$ \left\{ {\begin{array}{*{20}c} {\begin{array}{*{20}c} {Z_{1} = a_{1}^{'} U = a_{11} U_{1} + a_{12} U_{2} + \ldots a_{1p} U_{p} ,} \\ {Z_{2} = a_{2}^{'} U = a_{21} U_{1} + a_{22} U_{2} + \ldots a_{2p} U_{p} ,} \\ \end{array} } \\ \ldots \\ {Z_{p} = a_{p}^{'} U = a_{p1} U_{1} + a_{p2} U_{2} + \ldots a_{pp} U_{p} .} \\ \end{array} } \right. $$

(11)

where $a_{i}$ represents the coefficient vector. The linear transformation model can be represented in a simple way as follows:

$$ Var\left( {Z_{i} } \right) = a_{i}^{'} \sum a_{i} , \quad i = 1,2 \ldots p $$

(12)

$$ Cov\left( {Z_{i} ,Z_{j} } \right) = a_{i}^{'} \sum a_{j} , \quad i,j = 1,2 \ldots p $$

(13)

It is important to choose the number $m$ of principal components. The $m$ is defined as follows:

$$ \frac{{\lambda_{1} + \lambda_{2} + \cdots \lambda_{m} }}{{\mathop \sum \nolimits_{i = 1}^{s} \lambda_{i} }} \ge \delta $$

(14)

where $\delta$ is contribution rate. In this work, we use $\delta = 0.85$.$\lambda_{1} ,\lambda_{2} ,\lambda_{m}$ denote eigenvalues of covariance matrix.

Suppose the covariance matrix of grasshoppers $X = \left\{ {x_{1}^{t} ,x_{2}^{t} , \ldots x_{n}^{t} } \right\}$ is $V$, principal population can be generated as follows:

$$ \left\{ {\begin{array}{*{20}c} {\begin{array}{*{20}c} {F_{1}^{t} = a_{1}^{'} X = a_{11} x_{1}^{t} + a_{12} x_{2}^{t} + \cdots a_{1n} x_{n,}^{t} ,} \\ {F_{2}^{t} = a_{2}^{'} X = a_{21} x_{1}^{t} + a_{22} x_{2}^{t} + \cdots a_{2n} x_{n,}^{t} ,} \\ \end{array} } \\ \ldots \\ {F_{m}^{t} = a_{m}^{'} X = a_{m1} x_{1}^{t} + a_{m2} x_{2}^{t} + \cdots a_{mn} x_{n,}^{t} .} \\ \end{array} } \right. $$

(15)

where $(a_{1}^{'} ,a_{2}^{'} , \ldots , a_{m}^{'} )$ denote feature vectors of $V$. According to the principal component analysis theory, the new generated population is uncorrelated. The individuals of bad fitness are substituted by principal population. Figure 1 shows the flow of principal component analysis operation.

Fig. 1

Flowchart of principal component analysis operation

3.2 Novel inertia weight

In basic GOA algorithm, the parameter $c$ plays an important role in balancing exploration and exploitation, which decreased with the number of iterations in a linear way. However, all the grasshoppers take the same parameter $c$ without considering the fitness of each grasshopper. In this paper, we propose a novel inertia weight, which takes different strategies based on the fitness values of grasshoppers. To guarantee the steady of searching process, one of $c$ is replaced. The novel inertia weight is calculated as follows:

$$ \left\{ {\begin{array}{*{20}l} {c_{i}^{k} = c_{{\rm max} } - \left( {c_{{\rm max} } - c_{{\rm min} } } \right)*\left( {\frac{l}{L}} \right) \quad if \quad fitness\left( i \right) \ge average} \hfill \\ {c_{i}^{k} = c_{{\rm max} } - \left( {c_{{\rm max} } - c_{{\rm min} } } \right)*\left[ {\frac{2l}{L} - \left( {\frac{l}{L}} \right)^{2} } \right] \quad if \quad fitness\left( i \right) < average} \hfill \\ \end{array} } \right. $$

(16)

The modified mathematical model can be expressed by:

$$ X_{i}^{d} = c\left. {\left\{ {\mathop \sum \limits_{{\begin{array}{*{20}c} _{j = 1} \\_ {j \ne i} \\ \end{array} }}^{N} c_{i}^{k} \frac{{ub_{d} - lb_{d} }}{2}s\left( {\left| {x_{j}^{d} - x_{i}^{d} } \right|} \right)\frac{{x_{j} - x_{i} }}{{d_{ij} }}} \right.} \right\} + \hat{T}_{d} $$

(17)

The flowchart of the proposed PCA–GOA is shown in Fig. 2.

Fig. 2

Flowchart of the proposed PCA–GOA algorithm

4 Experimental results and discussion

In this section, unimodal benchmark functions, multimodal benchmark functions and fixed-dimension multimodal benchmark functions are used to test the performance of the PCA–GOA [36,37,38,39]. The benchmark functions are provided in Tables 1, 2 and 3. The exploitation of an algorithm can be tested by unimodal benchmark functions $\left( {f_{1} - f_{7} } \right)$ as only one global is contained. Multimodal benchmark functions $\left( {f_{8} - f_{13} } \right)$ and fixed-dimension multimodal benchmark functions $\left( {f_{14} - f_{23} } \right)$ are efficient tool for evaluating exploration capability and local optima avoidance. However, fixed-dimension multimodal benchmark functions are different from multimodal benchmark functions in dimensionality.

Table 1 Unimodal benchmark functions

Table 2 Multimodal benchmark functions

Table 3 Fixed-dimension multimodal benchmark functions

4.1 Parameters analyze

Parameters setting can influence the performance of the PCA–GOA when solving the various optimization problems. In this study, the five parameters of PCA–GOA include maximum parameter $c_{\rm max}$, minimum parameter $c_{{\rm min} }$, number of search agents $N$, maximum number of iterations $L$, contribution rate $\delta$ are analyzed on benchmark function $f_{1}$. An orthogonal test is worked as a tool to show the relations between the performance and each parameter setting. Ranges of PCA–GOA parameters are described in Table 4. According to the number of factors and levels, we select the $L_{27} \left( {3^{13} } \right)$ type to complete the task. To make the results more convincing, the average values after 30 runs are used to make comparisons.

Table 4 Ranges of the PCA–GOA parameters

As shown in Table 5, the maximum number of iterations $L$ is the most important factor that affects the search capability of the PCA–GOA. Furthermore, the importance of the other factors is as follows: $c_{{\rm max} } > c_{{\rm min} } > N > \delta$. Figure 3 shows the relation between average fitness values and the five parameters. From Table 5, we can obtain the best combination is $c_{\rm max} = 1$, $c_{{\rm min} } = 0.00001$, $N = 50$, $L = 300$, $\delta = 0.85$.

Table 5 $L_{27} \left( {3^{13} } \right)$ orthogonal testing for $f_{1}$

Fig. 3

Factor-index diagram

4.2 Performance evaluation

Six typical and recent algorithms including particle swarm optimization (PSO) [8], bat algorithm (BA) [14], ant lion optimizer (ALO) [40], dragonfly algorithm (DA) [41], grasshopper optimization algorithm (GOA) [20] and chaotic grasshopper optimization algorithm (CGOA) [28] are employed to compare the performance of the PCA–GOA. The key parameters of the seven algorithms are shown in Table 6. To test the generality of the PCA–GOA, different number of iterations and population sizes are used to make comparisons. The experiments are first tested on $N = 20$ and $L = 300$. Then, $N = 30$ and $L = 1000$ are used to further assess the performance of the proposed PCA–GOA. Each process independently runs 30 times. Best fitness values, worst fitness values, average fitness values and standard deviation values are recorded. It is obvious that the lower value means better search capability of the algorithm. For the drawbacks of the four indices cannot measure whether the results are significant, we use Wilcoxon statistical test to perfect comparisons [42, 43]. If $p < 0.05$, it demonstrates the improving affect is significant. Furthermore, CPU time and allocated memory are used to evaluated the computation amount of the PCA–GOA.

Table 6 Parameters setting for chosen optimization algorithms

The details of experiments environment are as follows: Core (TM) i5-4590 CPU @ 3.30 GHz with 8 GB RAM and 64 bit under Windows 7 system using Matlab R2015a.

Tables 7, 8 and 9 illustrate the results of unimodal benchmark functions, multimodal benchmark functions and fixed-dimension multimodal benchmark functions, respectively. In addition, the best results are highlighted in bold.

Table 7 Results of the unimodal benchmark functions

Table 8 Results of the multimodal benchmark functions

Table 9 Results of the fixed-dimension multimodal benchmark functions

Table 7 summarizes the best fitness values, worst fitness values, average fitness values and standard deviation values achieved by PSO, BA, ALO, DA, GOA, CGOA and PCA–GOA. As the results reported in Table 7, the PCA–GOA provides the best results on the four indexes for $f_{1}, f_{2}, f_{3}, f_{4}, f_{5}, f_{6} ,$ and $f_{7}$, which shows the PCA–GOA has remarkable advantages in terms of unimodal test functions. The superiority of the PCA–GOA can be further proved by Table 10, because all p values are much less than 0.05. Therefore, we can conclude that the PCA–GOA has a high exploitation capability.

Table 10 P values obtained from the Wilcoxon rank-sum test on unimodal benchmark functions

Observed from Table 8, it is apparent that PCA–GOA obtains better results for the majority functions except $f_{8}$ and $f_{9}$. For $f_{8}$, the PCA–GOA provides the best standard deviation values. It can be seen from Table 11, the PCA–GOA is markedly better than the other algorithm for $f_{10}, f_{11}, f_{12}$ and $f_{13}$. It suggests that the principal component analysis plays an important role in improving the search precision, and novel inertia weight is an efficient tool for keeping the exploration capability. In a word, the PCA–GOA has a perfect exploration ability and superior capability in jumping out of local optima. The PCA–GOA fails to achieve the best performance on some functions, and the reasons are as follows: the principal component analysis helps the algorithm finds the better solutions with a fast rate; however, this leads the grasshoppers gather around the best solution and the novel inertia weight mechanism is insufficient to jump out of the local best solution with a certain probability.

Table 11 P values obtained from the Wilcoxon rank-sum test on multimodal benchmark functions

Table 9 shows the results from the seven algorithms for the fixed-dimension multimodal benchmark functions. As we can see the results from Table 9, the PCA–GOA obtains very competitive results by comparing with the other algorithms. The PCA–GOA achieves the best results on $f_{16}, f_{17}, f_{20}, f_{21}, f_{22}$ and $f_{23}$ in terms of average fitness values. The ALO provides the best average fitness values for $f_{15}$. However, the p values in Table 12 are bigger than 0.05, which demonstrates the advantage is not obvious. Therefore, it can be claimed that the PCA–GOA shows better performance than other algorithms on fixed-dimension multimodal benchmark functions.

Table 12 P values obtained from the Wilcoxon rank-sum test on the fixed-dimension multimodal benchmark functions

Tables 13, 14 and 15 display the CPU time of the PSO, BA, ALO, DA, GOA, CGOA and PCA–GOA. From Tables 13 and 14, the DA requires the more computation time than the other algorithms on unimodal benchmark functions and multimodal benchmark functions. Table 15 shows that the PCA–GOA demands the highest computation time among the seven algorithms on the fixed-dimension multimodal benchmark functions. However, the CPU time of PCA–GOA is slightly longer than the GOA and CGOA. It indicates that time complexity of the principal component analysis mechanism is acceptable.

Table 13 Comparisons of the runtime on the unimodal benchmark functions

Table 14 Comparisons of the runtime on the multimodal benchmark functions

Table 15 Comparisons of the runtime on the fixed-dimension multimodal benchmark functions

Tables 16, 17 and 18 present the allocated memory of the seven algorithms. These tables show that PCA–GOA demands more allocated memory than the other algorithms. However, the allocated memory of PCA–GOA is almost in the same in the level with the GOA and CGOA.

Table 16 Comparisons of the allocated memory on the unimodal benchmark functions

Table 17 Comparisons of the allocated memory on the multimodal benchmark functions

Table 18 Comparisons of the allocated memory on the fixed-dimension multimodal benchmark functions

To continue evaluating the search capability and robustness of the proposed PCA–GOA, different number of iterations and population size are used to make further comparisons. The results are shown in Tables 19, 20 and 21. From the tables, with the increasing of number of iterations and population size, all the algorithms provide better results.

Table 19 Results of the unimodal benchmark functions

Table 20 Results of the multimodal benchmark functions

Table 21 Results of the fixed-dimension multimodal benchmark functions

Table 19 lists the results of the seven algorithms for unimodal test functions. Compared with other algorithms, the PCA–GOA always achieve better results on all unimodal test functions; meanwhile the superiority of the PCA–GOA is demonstrated by Table 22. The results show that the PCA–GOA is efficient enough to deal with the unimodal test functions

Table 22 P values obtained from the Wilcoxon rank-sum test on unimodal benchmark functions

It can be seen from Tables 20 and 23 the PCA–GOA performs significantly better than the other algorithms on $f_{10,} f_{11,} f_{12}$ and $f_{13} .$ Table 21 exhibits statistical results for the fixed-dimension multimodal benchmark functions. From the perspective of average fitness values, the PCA–GOA is the first rank on $f_{14} ,f_{16} ,f_{17} ,f_{18}$ and $f_{20}$. In addition, Table 24 shows that p values of $f_{14} ,f_{16}$$f_{17}$ and $f_{18}$ are much below 0.05, which verify the performance of the PCA–GOA is much better than the other algorithms. Mainly, the PCA–GOA performs better than the PSO, BA, ALO, DA, GOA and CGOA on two types multimodal benchmark functions.

Table 23 P values obtained from the Wilcoxon rank-sum test on multimodal benchmark functions

Table 24 P values obtained from the Wilcoxon rank-sum test on the fixed-dimension multimodal benchmark functions

Tables 25, 26, 27, 28, 29 and 30, the CPU time and the allocated memory are increased due to the changing of iterate numbers and population size. The conclusions are consistent with the above.

Table 25 Comparisons of the runtime on the unimodal benchmark functions

Table 26 Comparisons of the runtime on the multimodal benchmark functions

Table 27 Comparisons of the runtime on the fixed-dimension multimodal benchmark functions

Table 28 Comparisons of the allocated memory on the unimodal benchmark functions

Table 29 Comparisons of the allocated memory on the multimodal benchmark functions

Table 30 Comparisons of the allocated memory on the fixed-dimension multimodal benchmark functions

5 Conclusion

In this paper, the GOA is modified by incorporating it with principal component analysis and novel inertia weight. The proposed PCA–GOA is assessed on 23 benchmark functions with different number of iterations and population sizes. The experiments results show that the proposed PCA–GOA is much better than PSO, BA, ALO, DA, basic GOA and CGOA in most test cases. In the PCA–GOA, combing with the two strategies leads the CPU time and allocated memory rise. However, the increasing computation amount is limited.

For some cases, the PCA–GOA falls into local best solutions, and this is the biggest issue requires to be resolved in the future. Furthermore, the PCA–GOA is planned to solve some engineering problems.