# Lens Learning Sparrow Search Algorithm

Authors: Chengtian Ouyang; Donglin Zhu; Yaxian Qiu
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

In this paper, a lens learning sparrow search algorithm (LLSSA) is proposed to improve the defects of the new sparrow search algorithm, which is random and easy to fall into local optimum. The algorithm has achieved good results in function optimization and has planned a safer and less costly path to the three-dimensional UAV path planning. In the discoverer stage, the algorithm introduces the reverse learning strategy based on the lens principle to improve the search range of sparrow individuals and then proposes a variable spiral search strategy to make the follower's search more detailed and flexible. Finally, it combines the simulated annealing algorithm to judge and obtain the optimal solution. Through 15 standard test functions, it is verified that the improved algorithm has strong search ability and mining ability. At the same time, the improved algorithm is applied to the path planning of 3D complex terrain, and a clear, simple, and safe route is found, which verifies the effectiveness and practicability of the improved algorithm.


---

## Body

## 1. Introduction

In recent decades, swarm intelligence algorithms have been gradually explored by researchers. The main principles of these algorithms are mostly to solve some optimization problems by simulating or revealing some natural phenomena or processes, such as Particle Swarm optimization (PSO) [1], Grey Wolf Optimizer (GWO) [2], Beetle Swarm Optimization (BSO) [3]. The sparrow search algorithm (SSA) is a group of intelligence algorithms proposed by Xue and Shen [4] in 2020 to simulate the feeding process of sparrows. It has few parameters, simple principles, and easy implementation and is superior to other algorithms in many optimization functions. However, for some complex optimization problems, the algorithm has some problems, such as low search accuracy and slow convergence rate. After the sparrow search algorithm was put forward, many scholars studied and applied it carefully and made improvements. Xin et al. [5] proposed a chaotic sparrow search algorithm (CSSA), which uses tent mapping based on random variables to initialize the population, so as to make the individual position of sparrows more evenly distributed and improve the diversity of the population; in the process of optimization, disturbance and mutation mechanism are used to prevent the algorithm from falling into the local extremum state and improve the global search performance of the algorithm. The effectiveness and feasibility of the algorithm are verified by 12 test functions and image segmentation problems. In addition, they also proposed an improved sparrow search algorithm for image segmentation [6]. Bird swarm algorithm (BSA) [7] is used to optimize the sparrow search algorithm. The benchmark function and multithreshold image segmentation based on interclass variance and Kapur’s entropy verify that the improved algorithm has strong search ability and development ability. Mao et al. [8] proposed an improved sparrow search algorithm which combined Cauchy mutation and reverse learning. At first, a sin chaotic mechanism with infinite folding times is used to initialize the population, and the global optimal solution of the previous generation is introduced into the position updating formula, which speeds up the information exchange of the algorithm. At the same time, the adaptive weight strategy is introduced to coordinate the local and global search ability. Then, the fusion of Cauchy mutation and reverse learning strategy is introduced to make disturbance mutation in the optimal position to produce new solutions with higher quality, which improves the ability of the algorithm to jump out of the local optimum. Eight test functions are used to verify that the algorithm has been greatly improved in global optimization. Liu et al. [9] proposed a modified sparrow search algorithm with application for 3D route planning for UAV. Chaos strategy is introduced to enhance the diversity of the population, and adaptive inertia weight is used to balance the convergence speed and exploration ability of the algorithm. Finally, Cauchy Gauss mutation strategy is used to get rid of the stagnation ability of the later algorithm. Through the comparison of several algorithms in 3D path planning, the improved sparrow search algorithm has strong search ability and the planned route is relatively safe.Currently, research on sparrow search algorithm has been proposed successively, but the proposed algorithms lack a global improvement mechanism. Although the mapping mechanism is uniform, it is not stable under the sparrow search algorithm with good global results, and it increases the workload of the population. Therefore, a search mechanism with global vision and flexibility is needed to improve the search ability of the sparrow search algorithm. For the above analysis, a lens learning sparrow search algorithm (LLSSA) is proposed. This algorithm uses a reverse learning strategy based on lens learning strategy in the discoverer location update formula to improve the algorithm's vision in the optimal space. A variable spiral search strategy is proposed to enable followers to search in more detail and flexibility. Finally, the current solution is refined by fusing simulated annealing algorithm to find a higher quality solution. Through 15 standard test functions, the effectiveness of LLSSA is verified, and a distinct, simple, and satisfying route is found in the complex three-dimensional path planning.


## 2. Sparrow Search Algorithm

During the food search process, the sparrow population is divided into two roles: discoverer and follower, which conduct behavioral strategies separately. Discoverers are generally 0.2 of the population size and are the guides of the individual population, leading other individuals in the search for things, so the role of the discoverer is crucial in the population. They have a wide search range. The location update formula for the discoverer is as follows:(1)Xi,jt+1=Xi,jt⋅exp−hα⋅M,ifR2<ST,Xi,jt+Q⋅L,ifR2≥ST.In formula (1), h represents the current number of iterations and M is the maximum number of iterations. Xi,j denotes the current position of the i-th sparrow in the j-th dimension. α is a random number between 0 and 1. Q is a random number from a normal distribution. L represents a 1 × D matrix with all elements 1. R2 and ST respectively represent warning and safety values, and R2∈0,1, ST∈0.5,1. When R2<ST, this indicates that the community environment is in a safe state at this time, no predators are found around, and the discoverers can search for food on a wide scale. When R2 is greater than or equal to ST, this indicates that the individuals within the cluster have found a predator and issued an alarm so that all individuals of the population will make antipredation behavior and the discoverer will lead the follower to a safe location.To obtain good quality food, the followers would closely follow the discoverers. Some of these followers oversee the discoverers and those discoverers with high rates of predation for food, thus increasing their own nutrition. The positional update for the followers is described below:(2)Xi,jt+1=Q⋅expXworstt−Xi,jti2,ifi>n2,XPt+1+Xi,jt−XPt+1⋅A+⋅L,otherwise.In (2), XP is the optimal position currently occupied by the discoverer, and Xworst denotes the current worst position. A is a matrix of 1 × D in which an element is only 1 or - 1, with A+=ATAAT−1. When i>n/2, it indicates that the sparrow population is aware of danger, at which point they make antipredation behavior, and the mathematical expression is as follows:(3)Xi,jt+1=Xbestt+β⋅Xi,jt−Xbesttiffi≠fg,Xi,jt+K⋅Xi,jt−Xworsttfi−fw+ε,iffi=fg.In (3), Xbest is the current global optimum. β is the control step size parameter and is a random number obeying a normal distribution with mean 0 and variance 1. K∈−1,1 is a random number, and K represents the direction in which the sparrow moves while also controlling the moving step size. fi indicates the fitness value of the current sparrow individuals. fg and fw are the optimal and worst fitness values within the current search scope, respectively. ε is the smallest real number, preventing the occurrence of 0 in the denominator. When fi≠fg indicates that the current sparrow is at the boundary of the population and vulnerable to predator attack, the location needs to be adjusted. fi=fg, which indicates that individual sparrow in the interior of the population is aware of the danger and need to be close to other sparrows to avoid the danger.


## 3. Inverse Learning Strategy Based on Lens Imaging

It is because of the broad search range and flexible search methods that discoverers can lead the group to find good food. Once the discoverer is trapped in the local optimum, the performance of the overall algorithm will be degraded, so improving the search horizon of the discoverer is particularly important. General learning strategies have achieved good results in some optimization algorithms, but have little effect on the performance of the algorithm, because the general learning strategies carry out reverse solutions in local space, which enriches the diversity of the population, but the search scope is narrow and loses flexibility. In order to improve the searching ability of the discoverer, a reverse learning strategy based on lens imaging [10] is proposed and applied to the individual update position formula of the discoverer. The application of this strategy allows new individuals to be acquired for each iteration, resolving the problems left over from previous general learning strategies. The principle is described as follows.Definition 1.
(reverse point). SetX=x1,x2,…,xD as a point in D-dimensional space, and xj∈aj,bjj=1,2,…,D; then, the reverse point of X is X′=x1′,x2′,…,xD′, and xj′=aj+bj+xj.Definition 2.
(base point). Suppose there are several pointsO1,O2,…,Om, for any point X=x1,x2,…,xD with its reverse point X′=x1′,x2′,…,xD′ to Oii=1,2,…,m. Euclidean distances are di and di′, so k=di/di′, and k=1,2,…,n, and Oi is called the base point of X and X′ when k=i.
Using one-dimensional space as an example, assume that an individualP with a height of h is projected as xP (the globally optimal individual) on the coordinate axis, and a lens with a focal length of f is placed at the base position O (the midpoint of [a, b] in the figure). An image P′ with a height of h′ can be obtained through the lens imaging process, and its projection on the coordinate axis is xp′. At this time, xp′ is such that xP gives rise to new individuals through a back learning strategy based on the principles of lens imaging. The diagram is shown in Figure 1.
As shown in Figure1, the globally optimal individual xP is giving its corresponding reversal point xp′, obtained from the principle of lens imaging:(4)a+b/2−xpxp′−a+b/2=hh′.
Leth/h′=k, k be the scaling factor, and the inverse point obtained upon transformation is(5)xp′=a+b2+a+b2k−xpk.
It follows that whenk = 1,(6)xp′=a+b−xp.
Form (6) is called general reverse learning strategy. From the above formulas, it can be seen that general learning strategy is only a specific case of lens imaging learning strategy, and the new individuals obtained by general reverse learning strategy are fixed each time. In high-dimensional complex functions, new individuals with fixed ranges are also likely to fall into local optimum with monotonicity; by adjusting the parameter k, new individuals based on lenses imaging learning strategies are dynamic, which improves population diversity. Extending the formula to D-dimensional space is available:(7)xp′j=aj+bj2+aj+bj2k−xpjk.
In (7), xpj versus xp′j are the j-th dimension components of xp versus xp′, and aj and bj represent the j-th dimension components at the upper and lower bounds of the decision variable, respectively.Figure 1
Lens schematic diagram.


## 4. Variable Spiral Search Strategy

While it is convenient for followers to follow the discoverer in updating their location, it is easy for followers to search blindly and singularly. Inspired by the rotation of the whale algorithm, this paper introduces a variable spiral location update strategy, which allows followers to have a variety of search paths to better update the location, while balancing the global and local search of the algorithm. The spiral search diagram is shown in Figure2.Figure 2
Schematic diagram of spiral search.In the follower location update process, the helix parameterz cannot be a fixed shape, which results in monotonous search methods and the possibility of falling into local optimum, thus weakening the search ability of the algorithm. The parameter z is designed as an adaptive variable to dynamically adjust the spiral shape of follower search, which expands the follower’s ability to explore unknown areas, makes the algorithm search more efficient, and improves the algorithm's global search performance. The formula for the variable spiral position update strategy is as follows:(8)Xi,jt+1=ezl⋅cos2πl⋅Q⋅expXworstt−Xi,jti2,ifi>n2,XPt+1+Xi,jt−XPt+1⋅A+⋅L⋅ezl⋅cos2πl,z=ek⋅cosπ⋅1−i/imax,otherwise.The parameterZ changes according to the number of iterations. The change of Z is determined by the exponential function based on e in formula (8), and the size and amplitude of the helix are dynamically adjusted according to the nature of cos function. k is the coefficient of change, which is 5 in this paper. Here, L is a uniformly distributed random number of [−1, 1]. Follower location updates range from large to small, find more quality solutions in the early stage, reduce the increase of search useless work in the later stage, and improve the global optimal search performance of the algorithm. At the same time, according to the spiral characteristics, the optimization accuracy of the algorithm is improved.


## 5. Simulated Annealing Algorithm

Simulated annealing algorithm, derived from the principle of solid annealing, is a probability-based algorithm and a stochastic global optimization algorithm proposed by Metropolis et al. [11]. The simulated annealing algorithm is a classical algorithm and has been studied extensively. Its principle is not described here. The simulated annealing algorithm combines with the improved sparrow algorithm. The simulated annealing algorithm is used to refine the solution found by the sparrow search algorithm each time. It uses the sudden jump of the simulated annealing to get rid of the interference of local optimum and extracts the solution each time. The algorithm has good judgment ability and improves the quality of each solution and tends to be global.


## 6. Lens Learning Sparrow Search Algorithm

Sparrow search algorithm has deficiencies in the case of multidimensional complex functions. Therefore, this paper presents a lens learning sparrow search algorithm. This algorithm applies the reverse learning strategy based on the principle of lenses to the discoverer stage of sparrow search, improving the diversity of the population and expanding the search range of individual sparrows. In the follower search phase, a variable spiral search strategy is introduced, which makes the follower search more detailed and flexible. Finally, this algorithm is combined with the simulated annealing algorithm, and the previously found solutions are filtered again to obtain the optimal solution. The algorithm works as follows.(1)
Initialize the population location, number, and number of iterations.(2)
Calculate the fitness function of each group to get the corresponding maximum and minimum values to determine the best and worst position.(3)
Calculate the alert value and update the location of the discoverer based on the alert value.(4)
Use Levy flight to update the location of the discoverer.(5)
Update the position of followers.(6)
Perform another sine-cosine search of the follower's location and update the location.(7)
Update the locations of sparrows that are aware of danger.(8)
Perform simulated annealing operation, as follows:(9)T=fitfgln5,Tk+1=λTk.(9)
Determine thePi of each particle at the current temperature T, and the formula is as follows:(10)Tfitpi=e−fitpi−fitfg/t∑i=1Ne−fitpi−fitfg/t.(10)
Determine a new global optimal valuefg from the current sparrow individual Pi.(11)
Determine whether the termination condition is met or not; if not, return to step (2). If so, proceed to the next step.(12)
Output best position and minimum cost. The specific pseudocode is as follows (Algorithm1).Algorithm 1: The framework of the LLSSA.
InputM: the maximum iterationsPD: the number of producersSD: the number of sparrows who perceive the dangerR2: the alarm valueN: the number of sparrowsλ: attenuation parameterInitialize a population ofN sparrows and define its relevantOutput:Xbest, fgInitialize the population according to equation (5)t = 1;While (t < M)Rank the fitness values and find the current best individual and the current worst individual.R2 = rand(1)Fori = 1: PDUsing equation (7) and equation (8) update the finder's location;End forFori = (PD + 1) : NUsing equation (13) update the follower's location;End forForl = 1 : SDUpdating the position of a sparrow individual who is aware of danger according to equation (3);End forPerform simulated annealingGet the current new location;If the new location is better than before, update it.t = t + 1End whileReturn:Xbest, fg


## 7. Effectiveness Analysis

In order to better see the advantages of the improved strategy, the SPHEREFUNCTION function is taken as an example to analyze the effectiveness of the strategy of the LLSSA algorithm. Let the number of populations and the number of iterations be 50 and 10, respectively, and the individual distribution map after 10 iterations of each algorithm is obtained. The specific distribution maps are shown in Figures3 and 4.Figure 3
Distribution of individuals in LLSSA.Figure 4
Distribution of individuals in SSA.It can be seen from Figures3 and 4 that the particles of LLSSA converge faster, most of the individuals are close to the optimal value, and the search range is wider, which is beneficial to jump out of the local optimum, while the particles of SSA converge slower, and the search range is smaller, which is easy to fall into the local optimum state in the high-dimensional complex function. This shows that LLSSA has flexibility in the optimization mechanism and verifies the effectiveness of the three strategies.


## 8. Time Complexity Analysis

For an algorithm, time complexity is an important consideration, and it is also an important means of judging the amount of calculations of an algorithm. Suppose the population size of the algorithm is P, the maximum number of iterations isM, and the dimension of the problem is D. From a macro point of view, the SSA algorithm is the same as other intelligent optimization algorithms, with a time complexity of O (P × M × D), while the LLSSA algorithm does not add extra cycles in the optimization process, so in the entire algorithm, time complexity did not increase.From a micropoint of view, suppose the ratio of discoverers isr, the calculation time of introducing reverse learning based on the lens principle is t1, the calculation time of the variable spiral search strategy is t2, and the calculation time of using the simulated annealing algorithm to update the optimal solution is t3. It can be seen from the pseudocode of the algorithm that the LLSSA algorithm adds O (M × P × r × t1 × D) in the discoverer phase and O (M × (1 − r) × P × t2 × D) in the follower position update phase. O (M × t3) is added in the update stage of the optimal solution. It can be seen that the LLSSA algorithm has increased O (M × (P × D(r(t1 − t2) + t2)) + t3) compared with the SSA algorithm. However, it has not been improved in the order of magnitude, and the optimization efficiency and accuracy of the algorithm can be effectively improved. Therefore, the increased time complexity is significant and worthwhile.


## 9. Performance Testing

In order to further verify the feasibility and effectiveness of the improved sparrow search algorithm, this paper selects 15 standard test functions to verify its optimization performance. The specific information is shown in Table1. In order to ensure the fairness of the experiment, all the algorithms are run on the computer with MATLAB 2018b, Windows 10 operating system, and 8g memory. The number of iterations of each algorithm is 200 and the number of population is 50. The initial temperature is t = 50, λ = 0.75, and the parameters of PSO algorithm are C1 = C2 = 2, w = 0.729.Table 1
Test function table.
FunctionDIMSectionMINF1x=∑i=1nxi230[−100, 100]0F2x=∑i=1nxi+∏i=1nxi30[−10, 10]0F3x=∑i=1n∑j=1ixj230[−100, 100]0F4x=maxixi,1≤i≤n30[−100, 100]0F5x=∑i=1n−1100xi+1−xi22+xi−1230[−30, 30]0F6=∑i=1dxi2+∑i=1d0.5ixi2+∑i=1d0.5ixi430[−5, 10]0F7x=∑i=1dxii+130[−100, 100]d0F8x=∑i=1nixi4+random0,130[−1.28, 1.28]0F9x=∑i=1n−xisinxi30[−500, 500]−418.9829nF10=418.9829n−∑i=1nxisinxi30[−500, 500]0F11=π/n10sinπy1+∑i=1n−1yi−121+10sin2πyi+1+yn−12+yi=1+xi+1/4uxi,a,k,m=kxi−am,xi>a,0,−a<xi<a,k−xi−am,xi<−a.30[−50, 50]0F12=sin23πx1+x1−121+sin23πx2+x2−121+sin22πx22[−10, 10]0F13x=1.5−x1+x1x22+2.25−x1+x1x222+2.625−x1+x1x2322[−4.5, 4.5]0F14=100x12−x22+x1−12+x3−12+90x32−x42+10.1x2−12+x4−12+19.8x2−1x4−14[−10, 10]0F15x=0.002+∑i=1251/i+x1−a1i6+x2−a2i6−1wherea=−32−1601632−32…03232−32−32−32−32−32−16…3232322[−65.536. 65.536]0.998At the same time, in order to exclude the contingency of each algorithm and enhance persuasion, the three indexes of optimal value, average value, and standard deviation of each algorithm's search result are counted, and the three indexes are used to judge the optimization ability and stability of each algorithm.As can be seen from Table2, the LLSSA algorithm has the best search performance in F1–7, F10-11, F15 and has better search ability than other algorithms. In the F9 function, BSO is the best. In F13-14, BSO can find the best one, but its stability is poor, and the optimization results on other functions are extremely poor. Therefore, BSO has some limitations in function optimization. LLSSA achieves good results on many function problems. It is inferior only to BSO in F9, which shows that LLSSA has strong optimization ability. Other algorithms have achieved poor optimization results. Therefore, the introduction and fusion of simulated annealing make the sparrow search algorithm have strong local judgment ability, balance the local and global search, and improve the search ability of the algorithm.Table 2
Table of optimization results of each algorithm.
FunctionAlgorithmBestAveStdF1(x)LLSSA000BSO8.1585126.385114.9876CSSA000SSA05.192E − 2510GWO1.5739E − 364.5232E − 347.3785E − 34PSO3.8599E − 123.0697E − 112.7076E − 11F2(x)LLSSA000BSO0.2122191.88362.13278CSSA03.8973E − 1602.1346E − 159SSA02.2022E − 1448.4437E − 144GWO1.6295E − 252.9050E − 234.4358E − 23PSO8.9056E − 082.5055E − 071.4584E − 07F3(X)LLSSA000BSO0.000494515.145934.9405CSSA04.2858E − 1920SSA07.7137E − 2100GWO2.2250E − 040.0294310.070791PSO22.259249.959618.1286F4(X)LLSSA01.008E − 1630BSO0.015030.0150261.40522CSSA04.1077E − 1412.2499E − 140SSA4.0636E − 141.9036E − 072.9266E − 07GWO2.4178E − 066.4757E − 062.1850E − 06PSO8.1218E − 146.9044E − 137.0838E − 13F5(X)LLSSA2.2981E − 132.3943E − 053.8273E − 05BSO553.70412543.21611657.5282CSSA1.3357E − 082.6062E − 040.0015114SSA4.7653E − 090.000283250.00049636GWO45.856547.38550.89355PSO89.4507234.8606104.6002F6(X)LLSSA000BSO10.967976.889744.1926CSSA02.6949E − 1531.476E − 152SSA06.9176E − 1393.7889E − 138GWO1.1787E − 062.2057E − 052.7228E − 05PSO30.872558.718918.8337F7(X)LLSSA000BSO7.8221E − 462.0384E − 393.2288E − 39CSSA06.07E − 953.3246E − 94SSA08.7599E − 974.798E − 96GWO09.7069E − 2510PSO1.6341E − 296.6714E − 241.2043E − 23F8(X)LLSSA8.0687E − 060.00015610.00012633BSO0.00388130.0096744570.004701CSSA9.9226E − 060.000260620.00016246SSA5.318E − 050.000295820.00025735GWO0.000403740.00202520.89355PSO0.0102010.0300150.00096086F9(X)LLSSA−12554.58326−10931.85561203.7127BSO−12569.4418−11820.3055973.8153CSSA−9859.7543−8700.9989615.6127SSA−9374.4498−8208.1416501.1037GWO−9055.703−6452.3541033.4608PSO−8405.1316−6176.2342793.1086F10(X)LLSSA0.0003820231467.51731296.1624BSO0.03331848.28181061.7445CSSA2529.39743661.9962725.5963SSA3471.6704394292.617883529.1990723GWO4866.18356134.3633604.5177PSO5205.78037638.93871024.9673F11(X)LLSSA1.04486E − 134.06779E − 109.93488E − 10BSO0.1404911.0532270.53947CSSA1.09657E − 121.93721E − 083.43612E − 08SSA2.36977E − 122.78963E − 095.17661E − 09GWO9.22011E − 060.0198388390.013634913PSO2.35982E − 060.0416702270.078731524F12(X)LLSSA1.3498E − 311.3498E − 310BSO1.3498E − 311.3498E − 310CSSA1.4730E − 312.3043E − 293.9261E − 29SSA1.3498E − 313.9049E − 295.2232E − 29GWO1.0606E − 088.9305E − 077.8567E − 07PSO1.30489E − 234.7707E − 216.0171E − 21F13(X)LLSSA6.2457E − 271.1032E − 203.5156E − 20BSO00.25400.3592CSSA4.3789E − 213.2277E − 161.5937E − 15SSA2.7959E − 211.2661E − 162.7684E − 16GWO1.2267E − 084.0761E − 074.2024E − 07PSO1.1013E − 228.1661E − 201.7949E − 19F14(X)LLSSA6.47687E − 149.70058E − 091.93534E − 08BSO02.174392.93539CSSA1.2546E − 145.2214E − 071.3653E − 06SSA9.50199E − 131.02709E − 062.50633E − 06GWO0.000225911.1423015172.11174329PSO0.0226673330.0260197050.001130521F15(X)ALSSA0.9980.9980BSO0.9981.03110.17843CSSA0.9982.10682.9273SSA0.9982.55943.6421GWO0.9982.80132.8092PSO0.9981.19680.3976To describe the convergence of each algorithm in each function, the average convergence of each algorithm in each function is counted, and the specific convergence effect is shown in Figure5. From Figure 5, it can be clearly seen that LLSSA has excellent convergence performance in F1-5, F8, F11-12, F14 functions, which all have advantages in accuracy and speed. However, among F6-7, F9-10, F15 functions, the convergence accuracy is high and the speed is slow, while it has advantages in other functions, but it is not significant. Generally speaking, LLSSA overcomes the limitations of the original algorithm search mechanism, has a reliable optimization scheme, and has greater advantages in speed and accuracy.Figure 5
Convergence effect diagram of each algorithm. (a)F1, (b) F2 (c) F3, (d) F4, (e) F5, (f) F6, (g) F7, (h) F8, (i) F9, (j) F10, (k) F11, (l) F12, (m) F13, (n) F14, (o) F15.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)(m)(n)(o)Comparing algorithms based on mean and standard deviation alone is not enough. To be more persuasive, statistical tests are needed to verify that the proposed improved algorithm has significant improvement advantages over other existing algorithms. To determine whether each result of LLSSA is statistically significantly different from the best results of other algorithms, the Wilcoxon rank sum test was used at the 5% significance level. TheP values calculated in the Wilcoxon rank sum test between LLSSA and other algorithms are given in Table 3 for all the benchmark functions. When P<5%, the HO hypothesis can be considered rejected, indicating a significant difference between the two algorithms. When P<5%, it can be assumed that the HO hypothesis is accepted, indicating that the difference between the two algorithms is not obvious; that is, the optimization performance of the two algorithms is equal. Therefore, an algorithm with equivalent performance in each function is marked as N/A, indicating that it is not applicable. The algorithm differences table is shown in Table 3.Table 3
Wilcoxon rank sum testP value.
FBSOCSSASSAPSOGWOF1 (X)3.0731e − 13N/AN/A3.0731e − 133.0731e − 13F2 (X)3.0229e − 125.0460e − 060.00336.6628e − 123.0229e − 12F3 (X)3.0731e − 13N/AN/A3.0731e − 135.0518e − 13F4 (X)3.0229e − 125.3855e − 061.9198e − 066.6628e − 126.6628e − 12F5 (X)3.0229e − 123.6614e − 060.00296.6628e − 126.6628e − 12F6 (X)5.6836e − 130.01784.1170e − 049.8825e − 139.8825e − 13F7 (X)3.0731e − 132.5775e − 071.0038e − 075.0518e − 136.9262e − 12F8 (X)3.0229e − 120.00500.00236.6628e − 128.0397e − 12F9 (X)8.1616e − 042.6075e − 086.3487e − 101.2362e − 101.4748e − 10F10 (X)N/A3.2490e − 083.2972e − 106.6628e − 126.6628e − 12F11 (X)3.0229e − 122.2047e − 070.00713.0229e − 123.0229e − 12F12 (X)N/A4.1939e − 132.1521e − 114.2371e − 137.1756e − 13F13 (X)0.02442.8131e − 111.8152e − 116.4913e − 076.6628e − 12F14 (X)1.1648e − 061.9492e − 056.3524e − 063.0229e − 123.0229e − 12F15 (X)3.5009e − 060.00680.02320.01934.9256e − 10From Table3, there is a big difference between each algorithm and LLSSA as a whole. Only on the first two unimodal functions, the basic SSA itself can find the optimal value. Therefore, there is no significant difference between LLSSA, SSA, and CSSA, but only on the F10 function, the P value is greater than 0.05. The experimental results show that BSO has better optimization ability on this function.


## 10. Application and Analysis

The proposal and improvement of an algorithm are ultimately to be implemented in the actual project. Since the development of intelligent optimization algorithms, the improvement of multiple algorithms has been successfully applied to specific applications; for example: literature [12] proposed a novel metaheuristic based on integrating chaotic maps into a Henry gas solubility optimization algorithm, which achieved good results in welding beams and cantilever beams. Reference [13] proposed an adaptive metaheuristic algorithm based on decomposition in order to solve the multitarget complex problem in UAV flight. The above authors have all proposed suitable algorithms in actual problems. Therefore, this paper applies the LLSSA algorithm to the UAV path planning of three-dimensional complex terrain to verify the feasibility and practicability of the LLSSA algorithm.In recent years, the problem of UAV path planning has been widely favored by researchers. UAV path planning is also one of the problems of automatic control. Common path planning methods include genetic algorithm [14], particle swarm and ant colony algorithm [15], artificial potential field method [16], and gray wolf algorithm, but for complex high-dimensional problems such as path planning, the functions of these algorithms are limited. Many factors considered are difficult for each algorithm. For complex path planning problems, the algorithm is very easy to meet the current minimum cost and give up the overall plan, lack of autonomous learning. Therefore, researchers have made different improvement measures for the deficiencies of each algorithm to make the optimized path more ideal. Aiming at the problem of path planning in three-dimensional complex terrain, this paper proposes to integrate the improved sparrow search algorithm with the simulated annealing algorithm, so that the algorithm avoids the local optimal solution in the solving process and finds a clear and simple path with the smallest cost function.


### 10.1. Cost Function Design

Cost function is an indispensable part of route planning. The more reasonable the cost function is set, the closer it is to the real demand. The cost function designed in this paper is as follows:(11)Jcost=w1Jlength+w2Jheight+w3Jsmooth,wi≥0.∑i=13wi=1.Jcost represents the total cost of the path, and Jlength, Jheight, and Jsmooth represent the total length cost, total height cost, and smoothness cost of the path, respectively. w1, w2, and w3 are the corresponding weights. In this paper, w1=0.5, w2=0.3, w3=0.2.The cost function can be used to evaluate the quality of the generated path, which is the basis of iterative evolution of algorithm population. The performance of cost function determines the efficiency and quality of algorithm implementation, and it is also the performance index of path planning. In order to better evaluate the path quality, this paper constructs the fitness function [17–19] by comprehensively considering the height cost, length cost, and smoothness cost of the path. Suppose each path is composed of n points. x, y are the point coordinates of the terrain projected on the horizontal plane, and z is the height corresponding to the point coordinates on the horizontal plane.


### 10.2. Path Length Cost

Path length is one of the most important indicators to evaluate the quality of a path. The shorter the path is, the less energy and time consumption the UAV will take to fly. The cost of introducing path length is as follows:(12)Jlength=∑j=0nxj+1−xj2+yj+1−yj2+zj+1−zj2.


### 10.3. High Cost

The stable flight height of the UAV is also an important part of the UAV track planning process. For most aircraft, the flight height should not change much. Stable flight height helps to reduce the burden on the control system and save more fuel. Therefore, the cost of introducing track elevation is(13)Jheight=1n∑j=1nzi−1n∑j=1nz2.


### 10.4. Smoothness Cost

When an UAV is making a turn, it needs to consume some energy due to the air resistance and at the same time exerts some pressure on the body. The smaller the turning angle, the greater the pressure generated and the more energy consumed, making the flight inefficient. Therefore, the smoothness of flight is also a key factor in the cost of flight.(14)Jsmooth=xn−x1∑j=1n−2arcos⟶φj+1⋅φj⟶φj+1⟶φj⟶,φj⟶=xj+1−xj,yj+1−yj,zj+1−zj.φj⟶ represents the degree of deviation between the previous position and this position, and Jsmooth describes the cumulative sum of the degree of deviation of the connected nodes in the entire path. It is used to simulate the turbulence during the flight of the UAV. The smaller the turbulence, the higher the safety inside and outside the UAV.


## 10.1. Cost Function Design

Cost function is an indispensable part of route planning. The more reasonable the cost function is set, the closer it is to the real demand. The cost function designed in this paper is as follows:(11)Jcost=w1Jlength+w2Jheight+w3Jsmooth,wi≥0.∑i=13wi=1.Jcost represents the total cost of the path, and Jlength, Jheight, and Jsmooth represent the total length cost, total height cost, and smoothness cost of the path, respectively. w1, w2, and w3 are the corresponding weights. In this paper, w1=0.5, w2=0.3, w3=0.2.The cost function can be used to evaluate the quality of the generated path, which is the basis of iterative evolution of algorithm population. The performance of cost function determines the efficiency and quality of algorithm implementation, and it is also the performance index of path planning. In order to better evaluate the path quality, this paper constructs the fitness function [17–19] by comprehensively considering the height cost, length cost, and smoothness cost of the path. Suppose each path is composed of n points. x, y are the point coordinates of the terrain projected on the horizontal plane, and z is the height corresponding to the point coordinates on the horizontal plane.


## 10.2. Path Length Cost

Path length is one of the most important indicators to evaluate the quality of a path. The shorter the path is, the less energy and time consumption the UAV will take to fly. The cost of introducing path length is as follows:(12)Jlength=∑j=0nxj+1−xj2+yj+1−yj2+zj+1−zj2.


## 10.3. High Cost

The stable flight height of the UAV is also an important part of the UAV track planning process. For most aircraft, the flight height should not change much. Stable flight height helps to reduce the burden on the control system and save more fuel. Therefore, the cost of introducing track elevation is(13)Jheight=1n∑j=1nzi−1n∑j=1nz2.


## 10.4. Smoothness Cost

When an UAV is making a turn, it needs to consume some energy due to the air resistance and at the same time exerts some pressure on the body. The smaller the turning angle, the greater the pressure generated and the more energy consumed, making the flight inefficient. Therefore, the smoothness of flight is also a key factor in the cost of flight.(14)Jsmooth=xn−x1∑j=1n−2arcos⟶φj+1⋅φj⟶φj+1⟶φj⟶,φj⟶=xj+1−xj,yj+1−yj,zj+1−zj.φj⟶ represents the degree of deviation between the previous position and this position, and Jsmooth describes the cumulative sum of the degree of deviation of the connected nodes in the entire path. It is used to simulate the turbulence during the flight of the UAV. The smaller the turbulence, the higher the safety inside and outside the UAV.


## 11. Simulation Experiment and Analysis

In order to verify the feasibility and practicability of the fusion algorithm to optimize the effect of UAV, it is compared with SAPSO, PSO, SSA, and CSSA. The parameters of each algorithm are set as follows: the number of population is 100, the number of iterations is 400, the initial temperatureT is 25, λ = 0.99, and the specific experimental model parameters are shown in Table 4. In order to enhance the persuasion of the experiment and reduce the interference of accidental events, each algorithm runs 10 times independently and counts the minimum value, average value, and the worst value of each planned route. The optimal roadmap of each algorithm is shown in Figure 6, the performance index of each algorithm is shown in Table 5, and the average cost function convergence diagram is shown in Figure 7.Table 4
Experimental environment parameter table.
NameCoordinateHeight (radius)Start point(5, 90)—End point(45, 15)8Obstacle 1(15, 70)4Obstacle 2(20, 60)3Obstacle 3(30, 30)4Obstacle 4(40, 45)3Figure 6
Optimal route planning for each algorithm. (a) LLSSA, (b) SAPSO, (c) CSSA, (d) SSA, and (e) PSO.
(a)(b)(c)(d)(e)Table 5
Route statistics of each algorithm.
AlgorithmMINAVERWorst valueLLSSA43.088943.105743.1205CSSA46.364848.513550.1908SSA50.190851.465753.3881SAPSO43.115944.013246.0752PSO48.522849.331250.8184Figure 7
Average cost convergence graph of each algorithm.As you can see from Figures6 and 7 and Table 4, the LLSSA and SAPSO algorithms optimize the UAV's path to be the simplest and clearest. The CSSA, SSA, and PSO optimization routes appear to be distorted, obviously falling into a local optimal state. From the performance index table of each algorithm, LLSSA has better convergence accuracy and stability than SAPSO, and other algorithms have poorer stability, with the worst cost value exceeding 50. From the average cost convergence graph, it can be seen that the LLSSA algorithm has extremely fast convergence speed and accuracy. It found a path with the least cost before 50 iterations. The route found by the SSA algorithm is poor, complex, and costly, indicating that the SSA algorithm has limitations in solving such complex multidimensional functions. At the same time, it also shows that in complex path planning problems, the algorithm will meet the current minimum cost and fall into a local optimal state. Therefore, a flexible and judging search mechanism is needed to make the algorithm get rid of the constraints of the complex environment.Table 6
Table of rank sum test.
AlgorithmLLSSASAPSOCSSASSAPSOLLSSAN/A0.00221.5540e − 041.5540e − 041.5540e − 04SAPSO0.0022N/A9.3240e − 041.5540e − 041.5540e − 04CSSA1.5540e − 049.3240e − 04N/A0.0042N/ASSA1.5540e − 041.5540e − 040.0042N/A9.3240e − 04PSO1.5540e − 041.5540e − 04N/A9.3240e − 04N/ASimilarly, in order to further verify the feasibility and significance of the algorithm on the UAV route, Wilcoxon test as described above is conducted among the algorithms, and the rank sum test results are shown in Table6.It can be seen from Table6 and the above comprehensive situation that the algorithm that introduces the simulated annealing strategy has a greater advantage in route planning. The performance of the PSO algorithm and the CSSA algorithm is equivalent, and the SSA algorithm is the worst. Applicable to SSA algorithm, a flexible search mechanism and judgment strategy should be added to make the improved SSA algorithm stand out.


## 12. Conclusion

In this paper, aiming at the problem that the sparrow search algorithm falls into the local optimum and depends on the initial population in the optimization process, the reverse learning strategy based on the lens principle and the variable cosine search strategy are introduced, which are applied to the stage of discoverer and follower, respectively, making the search method more flexible and careful. Then the simulated annealing algorithm is fused to extract the optimal solution. Through the test of standard test function, it can be seen that LLSSA has good optimization ability and convergence effect. It is applied to the path planning of UAV in three-dimensional complex terrain. Through the comparison of CSSA, SSA, SAPSO, and PSO optimization UAV route planning, it shows that LLSSA optimization UAV path is the simplest and clearest, and the cost is the least. Through the planning route index table and the average cost function convergence diagram, it shows that LLSSA has good stability, so its application in UAV path planning has high reliability. It can be seen that in the process of sparrow optimization, if the leading discoverer is limited, the whole algorithm will be paralyzed, and the solution found each time is not necessarily reliable. Therefore, it is extremely important to effectively improve the discoverer's search mechanism and judgment ability. It can be seen from the above experiments that LLSSA relies on the judgment ability of simulated annealing algorithm in complex terrain path planning problems. Although this method can improve the quality of route optimization, it does not necessarily have a good effect in simple path planning problems, and it increases the calculation time, which is still a challenge in multiple complex environments. In the next step, we apply it to the path planning of multimission UAV.



---

*Source: 9935090-2021-05-10.xml*