|Computer Modeling in Engineering & Sciences|
A Chaos Sparrow Search Algorithm with Logarithmic Spiral and Adaptive Step for Engineering Problems
Aeronautics Engineering College, Air Force Engineering University, Xi'an, 710038, China
*Corresponding Author: Huan Zhou. Email: email@example.com
Received: 30 April 2021; Accepted: 15 July 2021
Abstract: The sparrow search algorithm (SSA) is a newly proposed meta-heuristic optimization algorithm based on the sparrow foraging principle. Similar to other meta-heuristic algorithms, SSA has problems such as slow convergence speed and difficulty in jumping out of the local optimum. In order to overcome these shortcomings, a chaotic sparrow search algorithm based on logarithmic spiral strategy and adaptive step strategy (CLSSA) is proposed in this paper. Firstly, in order to balance the exploration and exploitation ability of the algorithm, chaotic mapping is introduced to adjust the main parameters of SSA. Secondly, in order to improve the diversity of the population and enhance the search of the surrounding space, the logarithmic spiral strategy is introduced to improve the sparrow search mechanism. Finally, the adaptive step strategy is introduced to better control the process of algorithm exploitation and exploration. The best chaotic map is determined by different test functions, and the CLSSA with the best chaotic map is applied to solve 23 benchmark functions and 3 classical engineering problems. The simulation results show that the iterative map is the best chaotic map, and CLSSA is efficient and useful for engineering problems, which is better than all comparison algorithms.
Keywords: Sparrow search algorithm; global optimization; adaptive step; benchmark function; chaos map
The optimization problem is a common real-world problem that requires seeking the maximum or minimum value of a given objective function and they can be classified as single-objective optimization problems and multi-objective optimization problems [1,2]. There are two types of methods commonly used for optimization problems. One type is the traditional gradient-based approach. One is the metaheuristic algorithm [3,4]. Generally speaking, the traditional gradient-based methods often encounter difficulties in solving complex engineering problems . The existing research shows that the traditional mathematical or numerical programming methods are difficult to deal with many non-differentiable and discontinuous problems efficiently . In order to overcome these shortcomings, a kind of metaheuristic optimization algorithm is proposed and used to solve global optimization problems. Metaheuristic algorithms are usually divided into three categories: evolutionary algorithms, physics-based algorithms, and swarm-based algorithms. Evolutionary algorithm is a kind of algorithm inspired by the mechanism of natural evolution. Genetic Algorithm (GA)  based on Darwin's theory of survival of the fittest is one of the most famous evolutionary algorithms. There are also some other evolutionary algorithms such as Evolution Strategy (ES) , Evolutionary Programming (EP) , Differential Evolution (DE)  and Biogeography Based Optimization (BBO) . Physical-based algorithms are based on physical concepts to establish optimization models, such as Simulated Annealing (SA) , Gravity Search Algorithm (GSA) , Nuclear Reaction Optimization (NRO) , and Black Hole Algorithm (BHA) . Swarm-based algorithms based on the characteristics of group behavior are the focus of research in recent years. These algorithms establish optimization models by imitating the behavior of gregarious animals . Particle Swarm Optimization (PSO)  is the most well-known swarm intelligence optimization algorithm among these algorithms and has been applied to many fields. Other swarm intelligence optimization algorithms include Ant Colony Optimization (ACO) , Monarch Butterfly Optimization (MBO) , Moth Search Algorithm (MSA) , and Harris Hawk Optimization (HHO) . In addition to the algorithms mentioned above, there are more algorithms proposed, such as Earthworm Optimisation Algorithm (EOA) , Elephant Herding Optimization (EHO)  and Slime Mould Algorithm (SMA) . Besides proposing new algorithms to solve the optimization problems, more researchers also solve them by modifying existing algorithms. Gao et al.  propose a new selection mechanism to improve the DE performance and apply it to solve the job-shop scheduling problem. To enhance the population diversity of the equilibrium optimizer, Tang et al.  suggested the utilization of distribution estimation strategies and selection pools and perform well in solving the UAV path planning problem. Chen et al.  enhanced the performance of neighborhood search algorithm by introducing ad hoc destroy/repair heuristics and a periodic perturbation procedure, with successful solution of the dynamic vehicle routing problem Wang et al.  proposed a new newsvendor model and apply a histogram-based distribution estimation algorithm to solve it. However, the no free lunch theory states that no single algorithm can solve all problems well . This motivates us to continuously propose and improve algorithms to be applicable to more problems. SSA is a new swarm-based optimization algorithm based on sparrow foraging principle proposed by XUE in 2020 , which has the advantages of simple structure and few control parameters. In SSA, each sparrow finds the best position by looking for food and anti-predation behavior.
However, similar to other metaheuristic algorithms, there are also problems such as reduction of population diversity and early convergence in the late iterations when solving complex optimization problems.
Based on the discussion above, a chaos sparrow search algorithm based on logarithmic spiral search strategy and adaptive step size strategy (CLSSA) is proposed in this paper, which employs three strategies to enhance the global search ability of SSA. In CLSSA, different chaotic maps are used to change the random values of the parameters in the SSA. Logarithmic spiral search strategy is used to expand the search space and enhance population diversity. Two adaptive step size strategies are applied to adjust the development and exploration ability of the algorithm. To verify the performance of CLSSA, 23 benchmark functions and three engineering problems were used for the tests. Simulation results show that the CLSSA proposed in this paper is superior to the existing methods in terms of accuracy, convergence speed and stability.
The rest of this article is organized as follows: Section 2 introduces the principle and structure of SSA. Section 3 introduces the improvement strategy of CLSSA. Section 4 introduces the experimental results and analysis based on benchmark functions and engineering problems. In Section 5, the full text is summarized, and the direction of further research is pointed out.
2 The Basic Sparrow Search Algorithm
SSA is a novel swarm-based optimization algorithm that mainly simulates the process of sparrow foraging. The sparrow foraging process is a kind of discoverer-follower model, and the detection and early warning mechanism is also superimposed. Individuals with good fitness in sparrows are the producers, and other individuals are the followers. At the same time, a certain proportion of individuals in the population are selected for detection and early warning. If a danger is found, these individuals fly away to find new position.
There are producers, followers, and guards in SSA. The location update is per-formed according to their respective rules. The update rules are as follows:
where t indicates the current iteration, represents the value of the dimension of the sparrow at iteration t. is a constant with the largest number of iterations. is a random number. and represent the alarm value and the safety threshold respectively, where is randomly generated and is usually set to 0.8. Q is a random number which obeys normal distribution. shows a matrix of 1 × D for which each element inside is 1.
where indicates the best position occupied by the discoverer, indicates the current worst position, and is a matrix with a row of multi-dimensional elements of 1 or −1.
where is the current global best position, is a step size control parameter that obeys Gaussian distribution, is a random number, is the fitness of the current sparrow, and is the best fitness and the worst fitness at present, and is a constant to avoid zero denominator. The pseudo code of SSA is shown in Algorithm 1:
3 The Improved Sparrow Search Algorithm
In Section 3, we introduce a new SSA variant called CLSSA, which can improve the performance of the basic SSA. We introduce three strategies to improve the SSA algorithm. Firstly, we use chaotic map sequence to replace the random parameter of the algorithm. Secondly, we use the combination of logarithmic helix strategy and original search strategy to balance the discoverer's development and exploration ability. finally, we use two adaptive step size strategies to update the alert position and adjust the algorithm exploitation and exploration ability.
3.1 Chaotic Maps
Chaos is a random phenomenon in nonlinear dynamic systems, which is regular and random, and is sensitive to initial conditions and ergodicity. According to these characteristics, chaotic graphs represented by different equations are constructed to update the random variables in the optimization algorithm. Table 1 and Fig. 1 show ten chaotic maps which are used in the experiments. These ten chaotic maps have different effects in generating numerical values. More details about the 10 chaotic maps can be found in the literature [31,32]. Many researchers have demonstrated the effectiveness of chaotic maps in their studies, investigating the contribution of chaotic operators in the HHO , Krill Herd Algorithm (KHA)  and WOA .
3.2 Logarithmic Spiral Strategy
Through experiments, it is found that the original SSA is easy to fall into the local optimum, which leads to premature convergence. As shown in Fig. 2b, each iteration update of its discoverer approaches the individual optimal solution straight line, which has a strong exploitation ability, but loses the exploration of the nearby search space in the process of approaching the optimal individual, the population diversity is reduced, and it is easy to fall into the local optimum. Therefore, we introduce a logarithmic spiral search model  to solve this problem. The mathematical model is described as follows:
where a is constant that determines the shape of the spiral, whose value is 1, l is a parameter that linearly decreases from 1 to −1, and is the optimal position of the current iteration individual.
It can be seen from the Fig. 2a that when individuals of each generation update their positions, they gradually approach in a spiral shape, increasing the search for the surrounding space, maintaining the diversity of the population, and enhancing the exploration ability of the algorithm. Based on this analysis, the position update formula is adjusted as follows:
where is a uniformly distributed random number from 0 to 1, p is a constant and the value is 0.5.
3.3 Adaptive Step Strategy
In the SSA, two strategies are used for the location update of the guards. The Gaussian distribution is used to generate the step size for individuals with poor fitness. It can be seen from the Fig. 3 that the probability of the Gaussian distribution producing a smaller step size is higher. Conducive to the global search of the algorithm. The random step strategy is used for individuals with better fitness, and there is still a greater probability of large step in the later iterations, which is not conducive to algorithm convergence. Based on the above analysis, in order to balance the exploitation and exploration capabilities of the algorithm and enhance the convergence speed of the algorithm, an adaptive step size update formula is proposed for two strategies:
where is the average fitness of the dominant population and is the ratio of the dominant population which is 0.35.
For the individuals with poor fitness, when the dominant population of the updated sparrow is better than the dominant population of the previous generation, the larger step size of the Cauchy distribution is used to make the poor individual approach to the dominant population quickly; while when the dominant population of the updated sparrow is weaker than the dominant population of the previous generation, indicating that the renewal effect of this generation is not good, the smaller step size of Gaussian distribution is used to strengthen the search of the space near the individual. For individuals with better fitness, the adaptive step strategy is used. As can be seen from the Fig. 4, the large step size produced by the large probability in the early stage is beneficial for the individual to jump out of the local optimization, maintain the population diversity, increase the probability of small step size in the later stage, and impose only a small disturbance on the dominant individual, which is conducive to the convergence of the algorithm.
The pseudo code and flow chart of CLSSA is shown in Algorithm 2 and Fig. 5.
4 Experimental Results and Discussion
In Section 4, the benchmark function will be used to evaluate various chaotic map combination algorithms, and then determine which chaotic map sequence to replace the original SSA parameters. Secondly, we need to explore the impact of different improvement strategies in CLSSA on the optimization performance of the algorithm. Finally, we evaluate the performance of the CLSSA and compare the results with other latest algorithms.
4.1 Introduction of Benchmark Function
In this paper, 23 classical test functions are employed, including 7 unimodal functions, 6 multimodal functions and 10 fixed dimensional functions. The above test functions are all single-objective functions. The unimodal function F1–F7 has only one global optimal value, which is mainly used to test the development ability of the algorithm; the multimodal function has multiple local minima, which can be used to test the exploration ability of the algorithm. The benchmark function is shown in Table 2. The 3D view of each test function is shown in Figs. 6a–6d.
4.2 Chaos Map Test
Ten kinds of chaotic maps are combined with SSA algorithm to form new algorithms, the first chaotic map combined algorithm is named SSA-1, the second chaotic map combined algorithm is named SSA-2, and so on. The ten combined algorithms are compared with SSA in the benchmark function. In order to make a fair comparison, on the same experimental platform, the number of populations is set to 50, and the maximum number of iterations is 300. Except for using chaotic sequences to replace parameter , the other parameters are consistent with the original literature, and the initial values of chaotic mapping sequences are set to 0.7. All the algorithms are implemented in MATLAB R2016a and the test environment is set up on a computer with AMD R7 4700U CPU@1.80 GHz 16GB RAM, running on Windows 10. The average value is used to measure the accuracy of the algorithm, and the standard deviation is used to measure the robustness of the algorithm, so the average value and standard deviation are used to measure the performance of the algorithm. The results are recorded in Table 3. The last row in this table presents the count of the better than, equal to or worse than SSA obtained by each chaotic map over all functions.
It can be observed from Table 3 that SSA-8 (Singer map) outperforms or equals SSA in 14 test functions. SSA-3 (Gauss map), SSA-9 (Sinusoidal map) and SSA-10 (Tent map) perform better than or equal to SSA in 15 test functions. SSA-5 (Logistic map), SSA-6 (Precewise map) and SSA-7 (Sine map) perform better than or equal to SSA in 16 test functions. SSA-1 (Chebyshev map), SSA-2 (Circle map) and SSA-4 (Iterative map) are superior or equal to SSA in 17 test functions.
In order to further analyze the optimization ability of the eleven algorithms, the results of these algorithms in each test function are compared and sorted according to the mean value of Table 3. The results are shown in Table 4, and the average sorting results of each algorithm in the last behavior of the table. SSA-4 ranks first, indicating that iterative mapping is the best alternative to the original parameter . In addition to SSA-4, SSA-2, SSA-3, SSA-5, and SSA-7 also rank higher than SSA. The above analysis shows that using chaotic map sequence to replace the random parameter in the algorithm can better improve the algorithm's optimization performance, and each chaotic map sequence has different improvement effects on the algorithm. In order to visually show the performance of each algorithm in different test functions, a block diagram is used to plot the ranking results in Table 4, as shown in Fig. 7. The larger the area of the circle in the Fig. 7, the darker the color, indicating that the algorithm has a stronger performance in this test function, and the numbers in the figure indicate the ranking of each algorithm in each test function. It can be seen from Fig. 7 that SSA-4 performs better in the test function, and only performs poorly on F12 and F14.
In order to further prove the effectiveness of using chaotic sequences to replace SSA algorithm parameter, Figs. 8 and 9 list the convergence curves and box plots of eleven algorithms. It can be seen from Fig. 8 that SSA performs generally in each test function, and all chaotic mapping combination algorithms are better than SSA in convergence speed and convergence accuracy. The box diagram is used to show the distribution of the solutions of each algorithm. It can be seen from Fig. 9 that the optimal, median and worst values of the improved algorithm are better than those of SSA in most functions.
Combined with the above analysis, the chaotic mapping sequence can promote the improvement of SSA performance, and iterative mapping has the best effect on improving the performance of the SSA. Therefore, in the next part of the CLSSA performance test, the iterative mapping sequence is used to replace the random value parameter in the SSA.
4.3 Comparison of Different Improvement Strategies
As mentioned above, this paper mainly uses three strategies to improve SSA, so three different derivative algorithms are designed to evaluate the impact of these three strategies on the algorithm. These three derivation algorithms are obtained by removing the corresponding improvement strategy from CLSSA. CLSSA-1 removes both logarithmic spiral strategy and adaptive step strategy; CLSSA-2 removes chaotic map and adaptive step strategy at the same time; CLSSA-3 removes chaotic map strategy and logarithmic spiral strategy at the same time. 23 benchmark functions are used to compare the performance of the three derived algorithms with SSA and CLSSA. Each algorithm runs 30 times independently on each test function, and the statistical average results are shown in Tables 5 and 6 show the ranking of each algorithm in the test function. Obviously, CLSSA which includes all the improvement strategies, performed best, ranking first on average. The performance of the derived algorithm with one improved strategy is better than that of SSA. From the specific optimization results and sorting table provided by the Table 6, the chaotic mapping strategy mainly improves the development ability, while the logarithmic spiral strategy enhances the exploration ability of the algorithm, while the adaptive step strategy enhances the exploitation ability and exploration ability of the algorithm to some extent. The above analysis proves the effectiveness of each improvement strategy.
4.4 Performance Test of CLSSA
In order to verify the performance of CLSSA, the proposed CLSSA is compared with the SSA, WOA, BSO , PSO, GSA, HHO, GWO , SCA , MVO , MFO , BBO, FPA  Flower pollination algorithm for global optimization. The experimental environment is the same as the previous article, the number of populations is set to 50, the maximum number of iterations is 300, and the parameters of each algorithm are consistent with the original literature. Meanwhile, to reduce the influence of randomness on the experimental results, all algorithms need to run 30 times independently. Table 7 lists the best fitness, mean fitness and standard deviation, in which the best mean fitness is marked in bold.
As shown in Table 7, when solving the unimodal test functions F1–F7, CLSSA can stably converge to the optimal value in F1–F4 and F6, and the performance is better than the comparison algorithm. CLSSA could not obtain the optimal value of F5, but it was 19 orders of magnitude higher than SSA. HHO perform best on F7, with CLSSA in second position. In the unimodal test functions F1–F7, CLSSA is better than SSA, indicating that the proposed chaotic map sequence substitution strategy can effectively improve the local search ability of the algorithm.
When solving the multimodal test functions F8–F13, GSA, PSO, BBO and MFO outperform CLSSA in solving F8. For F9–F11, CLSAA, SSA, HHO can all stably converge to the optimal value. WOA can obtain the optimal value, but it is not stable. The CLSSA has the highest accuracy for F12–F13, with optimal values improved by 17 and 11 orders of magnitude compared to SSA. When solving the fixed-dimensional multimodal functions F14–F23, the CLSSA performs poorly for F14, outperforming only SSA, WOA, GSA, GWO and BBO. For the F15, optimal values can be obtained for CLSSA and SSA, but CLSSA is more stable than SSA. All algorithms have similar performance at F16, and all can obtain optimal values. GSA is the most stable and CLSAA is the second most stable. The CLSSA outperforms WOA, HHO, GSA, CSA, MVO, BBO and FPA for F17, with performance comparable to other algorithms. As for F18, the stability of CLSSA is only weaker than BSO, PSO, and GSA. The CLSSA outperforms all comparison algorithms for F19, F21 and F23. The GSA performs best for F22, with the CLSSA second best. In all multimodal test functions, CLSSA performs better than SSA, which shows that the logarithmic spiral strategy proposed in this paper can significantly improve the performance of algorithm exploration.
Combined with the above analysis, the CLSSA proposed in this paper is better than all the comparison algorithms in 12 of the 23 benchmark functions, 11 comparison algorithms in 6 test functions, 9 comparison algorithms in 3 test functions, and CLSSA is better than SSA, in all test functions, which proves that our proposed CLSSA has obvious advantages in optimization accuracy.
In order to directly show the performance differences of each algorithm in solving the test function, the algorithms are sorted according to the mean fitness of Table 7, the results are shown in Table 8, and the last column is the average ranking of each algorithm.
Fig. 10 is drawn according to the ranks in Table 8. The smaller the area of the algorithm performance curve, the better the performance of the algorithm.
The black bold line is the sorting result curve of CLSSA, and it can be seen intuitively that the performance of CLSSA is in the middle level on F8 and F14, and performs better in other test functions, and its surrounding area is the smallest, indicating that CLSSA has the best optimization performance as a whole.
To further illustrate the convergence performance of CLSSA, Fig. 11 lists the mean convergence curves of 13 algorithms to solve these functions. For the unimodal test function F1–F7, CLSSA has the best performance, the convergence speed is faster than all comparison algorithms, and the convergence accuracy is also higher than all comparison algorithms. For the multimodal functions F8–F23, CLSSA performs best in most of them. However, for functions F14, F17, and F18, CLSSA converges slowly in the early iterations. The CLSSA converges slower in the early iterations on F21 and F22 but can converge to better results afterwards. CLSSA converges faster than SSA on all test functions, which shows that the variable step strategy proposed in this paper can effectively improve the convergence speed.
To analyze the distribution characteristics of each algorithm in the test function, Fig. 12 lists box plots of 13 algorithms. Compared with other comparison algorithms, the CLSSA proposed in this paper performs well on most functions, and the obtained maximum, minimum, and median values are almost the same as the optimal solution, especially for F9, F10, F11, F16, F17, F19 and F20. In other test functions, although there are individual outliers, the overall distribution is still more concentrated than the comparison algorithm. Therefore, the CLSSA proposed in this paper has stronger stability.
The above analysis shows that CLSSA shows strong optimization ability on low-dimensional functions. However, the optimization algorithm is prone to fail in solving high-dimensional complex function problems. Real-world optimization problems are mostly large-scale complex optimization problems. Therefore, to verify the performance of CLSSA in high-dimensional problems, 13 algorithms were compared on the 100D test functions, and the experimental results are shown in Table 9. CLSSA is better than all comparison algorithms in F1–F6 and F12–F13. HHO performs best in F7 and F8, CLSSA ranks second and third respectively. When solving F9–F11, CLSSA and SSA can get the best value. It can also be seen from Figs. 13 and 14 that CLSSA performs well in other test functions except for the pool performance on F8 and can steadily and quickly converge to a better value.
In summary, compared with other algorithms, the CLSSA proposed in this paper is competitive, and the proposed improvement strategy can handle the relationship between exploitation and exploration well.
4.5 CLSSA for Engineering Problems
Engineering design problem is a nonlinear optimization problem with complex geometric shapes, various design variables and many practical engineering constraints. The performance of the proposed algorithm is evaluated by solving practical engineering problems. In the simulation, the population size is set to 50, and the maximum iterations is 500. The results of 30 independent runs of CLSSA are compared with those in other literatures.
4.5.1 Pressure Vessel Design Problem
The pressure vessel design optimization problem shown in Fig. 15 is a typical hybrid optimization problem, whose goal is to reduce the total cost, including forming cost, material cost and welding cost. There are four different variables: container thickness Ts(x1), head thickness Th(x2), inner diameter R(x3) and container cylindrical section length L(x4). The comparison results are shown in Table 10. The problem can be described as Eq. (10).
4.5.2 Tension/Compression Spring Design Problem
The tension/compression spring design problem is a mechanical engineering design optimization problem, which can be used to evaluate the superiority of the algorithm. As shown in Fig. 16, the goal of this problem is to reduce the weight of the spring. It includes four nonlinear inequalities and three continuous variables: wire diameter w(x1), coil average diameter d(x2), coil length or number L(x3). The comparison results are shown in Table 11. The mathematical model of this problem can be described as Eq. (11).
4.5.3 Welded Beam Design Problem
As shown in Fig. 17, the main purpose of the welded beam design problem is to reduce the manufacturing cost of the welded beam, which mainly involves four variables: the width h (x1) and length l (x2) of the weld zone, the depth t (x3) and the thickness b (x4), and subject to the constraints of bending stress, shear stress, maximum end deflection and load conditions. The comparison results are shown in Table 12. The mathematical model of the problem is described as Eq. (12).
In this paper, 15 algorithms are selected and compared with CLSSA. The simulation results show that CLSSA achieves the optimal values in all three engineering problems, which proves that CLSSA is highly competitive.
In this paper, we use three strategies combining chaos theory, logarithmic spiral search and adaptive steps to modify the basic sparrow search algorithm. First, the chaotic mapping is used to generate the values of the parameter . Second, the logarithmic spiral search strategy is used to expand the search of SSA to the surrounding area, thus enhancing the population diversity and avoiding falling into local optimum. In addition, the adaptive step control strategy is proposed to effectively balance the exploitation and exploration of SSA. To evaluate the performance of the proposed CLSSA, 23 classical test functions are used for verification. The simulation results show that it is effective to improve the SSA performance by using chaotic mapping to generate the value of parameter , in which the iterative mapping has the best impact. Three improvement strategies can improve the performance of SSA. Compared with eleven advanced algorithms, CLSSA has higher convergence accuracy, faster convergence speed and more stable performance. In addition, CLSSA was applied to three engineering optimization problems. The results show that CLSSA has excellent performance in terms of convergence rate and accuracy for structural engineering design problems. In future work, we plan to further improve the performance of CLSSA. We can hybridize CLSSA with other algorithms, such as combining with MBO, EHO, etc., with the same excellent performance, to achieve the effect of 1 + 1 > 2. We can also further study the impact of SSA parameter settings on performance. In addition, we plan to apply it to solve some real world problems, such as unmanned combat aerial vehicles task allocation and unmanned combat aerial vehicles path planning.
Funding Statement: The author acknowledges funding received from the following science foundations: The Science Foundation of Shanxi Province, China (2020JQ-481, 2021JM-224), Aero Science Foundation of China (201951096002).
Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.
|This work is licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.|