# Improved Sparrow Algorithm Based on Game Predatory Mechanism and Suicide Mechanism

Authors: Ping Yang; Shaoqiang Yan; Donglin Zhu; Jiangpeng Wang; Fengxuan Wu; Zhe Yan; Song Yan
Journal: Computational Intelligence and Neuroscience
 (2022)

---

## Abstract

In order to overcome the defect that sparrow search algorithm converges very fast but is easy to fall into the trap of local optimization, based on the original mechanism of sparrow algorithm, this paper proposes game predatory mechanism and suicide mechanism, which makes sparrow algorithm more in line with its biological characteristics and enhances the ability of the algorithm to get rid of the attraction of local optimization while retaining the advantages of fast convergence speed. By initializing the population with the good point set strategy, the quality of the initial population is guaranteed and the diversity of the population is enhanced. In view of the current situation that the diversity index evaluation does not consider the invalid search caused by individuals beyond the boundary in the search process, an index to measure the invalid search beyond the boundary in the search process is proposed, and the measurement of diversity index is further improved to make it more accurate. The improved algorithm is tested on six basic functions and CEC2017 test function to verify its effectiveness. Finally, the improved algorithm is applied to the three-dimensional path planning of UAV with threat area. The results show that the improved algorithm has stronger optimization performance, has strong competitiveness compared with other algorithms, and can quickly plan the effective and stable path of UAV, which improves an effective method for the application in this field and other fields.


---

## Body

## 1. Introduction

With the progress of modern technology, intelligent algorithms also continue to develop [1–5] and are applied to all kinds of engineering applications and real life. Comparing the swarm intelligence optimization algorithm and traditional optimization algorithm, the former is a heuristic search technology based on biological population characteristics. It has fast convergence speed, strong robustness, and high stability. With its own self-organization and adaptive characteristics, it can effectively solve complex optimization problems. The continuous development of swarm intelligence algorithm not only opens up a new world for solving various complex engineering problems but also stimulates the great research interest of scholars. Various swarm intelligence optimization algorithms appear one after another, and the family of swarm intelligence optimization algorithms has been unprecedentedly developed [6–9]. New algorithms are constantly proposed, such as naked mole-rat algorithm (NMRA) [10], firefly algorithm (FA) [11], ant lion optimizer (ALO) [12], whale optimization algorithm (WOA) [13], sine cosine algorithm (SCA) [14], crow search algorithm (CSA) [15], Harris hawks optimization (HHO) [16], slime mould algorithm (SMA) [17], hunger games search (HGS) [18], Runge–Kutta method [19], and colony predation algorithm (CPA) [20].Inspired by sparrows’ foraging behavior, predatory behavior, and antipredation behavior, a new swarm intelligence optimization algorithm, sparrow search algorithm (SSA) [21], was proposed by Xue et al. in 2020. Compared with traditional intelligent optimization algorithms, such as bat algorithm (BA) [22], grey wolf optimization (GWO) [23], and whale optimization algorithm (WOA) [13], SSA has the advantages of fast convergence, high stability, and strong robustness [24].The algorithm has the advantage of fast convergence speed, but the global search ability is poor, the optimization results have great randomness, and it is easy to fall into the trap of local optimization. In view of this defect, many scholars have proposed different improvement strategies to improve the performance of sparrow algorithm and successfully solve many complex engineering problems [25]. In literature [26], the search mechanism of bird swarm algorithm replaces the original search mechanism, enhances the global search ability, and effectively breaks through the local limited search. Literature [27] makes full use of the current dominant individuals through the iterative local search mechanism, making the search method more diversified and the optimization accuracy more detailed. Literature [28] introduced the dimension-by-dimension lens learning mechanism to reduce the interference between dimensions and accelerate the convergence of the population. Inspired by logistic model, literature [29] proposed a new adaptive factor to dynamically control the safety threshold, which balances the ability of global search and local development of the algorithm.The above algorithm has improved the sparrow algorithm and achieved some results, but there are still some shortcomings:(1)
The improved initialization method still has some randomness, which cannot guarantee the quality of each initialization population.(2)
The mechanism that the follower only pillages food with the discoverer’s optimal solution does not accord with the characteristics of biological population and makes insufficient use of other optimal solutions, so it is easy to skip the global optimal solution and miss it.(3)
The location update method of followers is to directly jump to the vicinity of the current optimal solution. Although this method leads to the advantage of fast convergence speed, it is also very easy to fall into local optimization. Once it cannot jump out of local optimization, it will reduce the optimization performance.To solve the above problems, based on the summary of previous work, this paper presents an improved sparrow search algorithm based on game predatory mechanism and suicide mechanism (GPSSA), which helps to improve the shortcomings of SSA algorithm, such as fast convergence speed while being easy to fall into local optimization. This paper presents an improved sparrow search algorithm based on game predatory mechanism and suicide mechanism, which is more in line with the biological habits of sparrow population, ensures more uniform population through a good point set, makes full use of the better individuals in the population through game predatory mechanism and ensures the flexibility of search, and helps the algorithm jump out of local optimum through suicide mechanism. An invalid search index is presented for the true location of individuals beyond the boundary during the search process, which improves the defect of the original index and makes it more accurate and realistic to reflect the population diversity, exploration, and development stages in the search process. The improved GPSSA has the advantages of good initialization population quality, flexible search ability, good population diversity, and fast convergence speed. It is easy to get rid of the characteristics of local optimal attraction. The main contributions are as follows:(1)
By adding good point set, the initial population is more uniform, the population is more diverse, and the quality of the initial population is guaranteed.(2)
On the basis of the original mechanism, a game predatory mechanism is proposed, which makes the algorithm more in line with biological characteristics and makes the search ability of the algorithm more flexible without reducing the advantages of fast convergence speed of the original algorithm.(3)
According to the unique biological characteristics of sparrows that cannot be kept in captivity, a suicide mechanism is proposed, which is to die and live afterwards, eliminate the original individuals and produce new individuals, help the algorithm increase the population diversity, and jump out of the local optimum.(4)
On the basis that the original population diversity index does not consider the individuals beyond the boundary in the search process, an index to measure the invalid search of individuals beyond the boundary is proposed, and the original population diversity index is improved to make the results more accurate.(5)
Six basic test functions are used for experimental simulation. The step size diagram, diversity index analysis, and development exploration stage index are used to analyze the role and effect of each strategy. The improved algorithm is compared with particle swarm optimization (PSO) [30], differential evolution (DE) [31], grey wolf optimization (GWO) algorithm [23], and sparrow search algorithm (SSA) [21] to verify its applicability.(6)
CEC2017 [32, 33] is used to verify the effect of GPSSA algorithm in more complex computing environment. On the basis of the above algorithm, newer cuckoo search (CS) algorithm [34] and multistrategy serial cuckoo search (MSSCS) algorithm [35] are added for comparison and analysis to verify its superiority, and Wilcoxon rank-sum analysis, box chart, and radar sorting chart are used to verify the effectiveness of the algorithm.(7)
The improved algorithm (GPSSA) is applied to a discrete problem, UAV path planning with threat [36], to help UAV quickly plan the optimal path.


## 2. Sparrow Search Algorithm

SSA is a new swarm intelligence optimization algorithm proposed by sparrows’ foraging behavior, predatory behavior, and antipredatory behavior. Its bionic principle is as follows.When the sparrow population is foraging, the individual population can be divided into discoverer, follower, and scouter. The discoverer is responsible for finding the food and leading the population to search the direction. The follower follows the discoverer to seize the food. The scouter is alert to the threat of the surrounding environment and sends a danger signal in time to remind the sparrow population to move to a safer area.When the sparrow population does not find the existence of predators or other external threats, the search and foraging environment is safe. The discoverer can perform a wide range of search operations to guide the population to obtain higher energy. When the scouter discovers the threat of the external environment or the presence of predators, with the release of the scouter’s early warning signal, the discoverer timely adjusts the search strategy and quickly approaches the safe area. Therefore, the location update formula for the discoverer to guide the population foraging is set as follows:(1)Xi,jt+1=Xi,jt⋅exp−iα⋅M,R2<ST,Xi,jt+Q⋅L,R2≥ST..In the above formula,Xi,j represents the current position of the i-th sparrow in the j-th dimension. M is the maximum number of iterations. t represents the current number of iterations. R2 represents an early warning value belonging to [0, 1]. α is a random number belonging to [0, 1]. ST is the security threshold belonging to [0.5,1]. L stands for a 1 × d matrix, and all elements in the matrix are 1. Q is a random number subject to normal distribution.When the followers follow the discoverers without food, they are very hungry and have low energy, so they need to fly to other places to find food to improve their energy. When the followers follow the discoverer to get food, they only need to find a place near the best position of the sparrow population for foraging. Based on this, the location update formula of the participant is set as follows:(2)Xi,jt+1=Q⋅expXworstt−Xi,jti2,i>n2,XPt+1+Xi,jt−XPt+1⋅A+⋅L,otherwise.In the above formula,Xp is the best position currently occupied by the discoverer, and Xworst represents the worst position. A is a 1 × d matrix with only 1 or −1 elements, where A+ = AT(AAT)−1.Wheni > n/2, it means that the i-th follower with low fitness does not get food, is in a very hungry state, and needs to fly to other places to find food. When i ≤ n/2, followers will compete for food with the discoverer who finds the most food (with the best fitness), so as to improve their energy.When the scouter is at the edge of sparrow population, it is very vulnerable to predator attack or other external environment threats, so the scouter needs to quickly move closer to the global optimal position to reduce the threat. When the scouters are in the middle of the population, if they are aware of the danger information, they will timely get close to other sparrows, so as to reduce the risk of being attacked or preyed on. Therefore, the scouter position update formula is set as follows:(3)Xi,jt+1=Xbestt+β⋅Xi,jt−Xbestt,fi≠fg,Xi,jt+K⋅Xi,jt−Xworsttfi−fw+ε,fi=fg.Xbest represents the global optimal position of the current population. β is responsible for controlling the step size parameter, which is a random number subject to standard normal distribution. K is responsible for controlling the moving direction and step of sparrow, which is a random number belonging to [−1, 1]. fi is the fitness value of the current i-th sparrow individual. fg and fw, respectively, represent the best and worst fitness values of the current population. ε is a minimal real number.


## 3. Improved Sparrow Algorithm Based on Game Predatory Mechanism and Suicide Mechanism (GPSSA)

### 3.1. Good Point Set

The good point set was proposed by Chinese mathematicians Hua and Wang [37], and its principle is as follows: let GS be the unit cube in s-dimensional Euclidean space, and if r∈Gs, the form is(4)Pnk=r1n⋅k,r2n⋅k,…rsn⋅k,1≤k≤n.If the deviationφn satisfies φn=Cr,εn−1+ε, ε is any positive number, where Cr,εn−1+ε is a constant only related to r and ε. Pnk is a good point set and r is a good point. rsn⋅k represents the decimal part, n represents the number of points, and r=2cos2πk/p,1≤k≤s , where p is the minimum prime number satisfying p−3/2≥s. Map it to the search space [34] as(5)xij=ubj−lbj⋅rji⋅k+lbj,where ubj and lbj represent the upper and lower bounds of the j-th dimension, respectively.Figure1(a) shows a randomly generated initial population distribution map when the good point set is in [0, 1], the number of populations is 500, and the dimension is 1. Figure 1(b)shows the frequency distribution histogram of good point set and tent chaotic map [35] under the above conditions. It can be seen that the good point integration is evenly distributed, and the initialization effect is better than that of tent chaotic map. In the initialization process, the good point set has a more uniform population, which can increase the diversity of the population and help to eliminate the attraction of the local optimal solution.Figure 1
Distribution of good point set.
(a)(b)


### 3.2. Game Predatory Mechanism

The followers in sparrow algorithm have a predatory mechanism; that is, the followers directly jump to the vicinity of the optimal location of the discoverer to compete for food. However, the food in the best position of the discoverer is not endless, and it is impossible to meet the food needs of a large number of followers, which is also inconsistent with the laws of nature. Therefore, based on the game theory, this paper proposes a game predator mechanism; that is, the predatory mechanism of followers and discoverers is regarded as a game process. Wheni < N/2, it is stipulated that the food found by each discoverer can only meet the needs of limited participants, and the amount of food found is determined by its fitness value. The top followers will give priority to those who find the most food to grab food. In order to obtain food and avoid hunger, the lower ranked participants will choose the discoverer who finds less food to eat, as shown in Figure 2(a). It is worth noting that, for the mechanism when i > N/2, the followers obtain food and forage alone is retained, as shown in Figure 2(b).Figure 2
Principle of game grabbing mechanism.
(a)(b)It is found from (2) that when i ≤ N/2, the followers will grab food after the discoverers. Therefore, there are R followers who directly jump to the vicinity of the discoverer who finds the most food and grab food, where R=N/2−PD⋅N and PD is the proportion of discoverers.Assuming that the food found by each discoverer is limited, the food in the optimal location of the discoverer cannot meet the food needs of a large number of followers, and the followers participating in the predator mechanism will grab food from different discoverers because of the shortage of food. At this time, it is a game process, and the followers will choose the discoverer who is most favorable to them to grab food. There are two steps in the game predatory mechanism: one is to count the food quantity of the discoverer, and the other is to make game selection to select the most beneficial discoverer for oneself as follows.


#### 3.2.1. Food Quantity Statistics of Discoverer

Individuals with lower fitness are considered to be better choices. The lower the fitness of the discoverer’s location is, the more food is found, and the number of discoverers isPD⋅N. Dz represents the z-th discoverer. Then the quantity G of food found by the z-th discoverer can be expressed as(6)Gz=1fDz,z=1,2,…,PD⋅N.


#### 3.2.2. Game Choice

WhenJz followers compete for food with the z-th discoverer, the subsequent followers will choose to compete for food with the z + 1-th discoverer because of the game mechanism, and so on. Fj represents the j-th follower. Jz is determined by the ratio pz of the quantity Gz of food found by the z-th discoverer to the total quantity. The specific principle is as follows:(7)pz=Gz∑z=1PD⋅NGz,(8)Jz=roundpz⋅R.At this time, the relationship between each follower in the game predatory mechanism and its predatory discoverer is as follows:(9)D1F1F2⋯FJ1,D2FJ1+1FJ1+2⋯FJ1+J2,⋯,DPD⋅NFJ1+J2+⋯+JPD⋅N−1+1,FJ1+J2+⋯+JPD⋅N−1+2,⋯FJ1+J2+⋯+JPD⋅N..Therefore, the location update formula of the improved followers is as follows:(10)Xi,jt+1=Q⋅expXworstt−Xi,jti2,i>N2,Dz,jt+1+Xi,jt−Dz,jt+1⋅A+⋅L,otherwise.


### 3.3. Suicide Mechanism

Sparrows mostly live in places where human beings live. They are very lively, bold, and approachable, but they are very vigilant. Sparrows are very proud birds. They live on people, but they do not want to be kept in captivity. If they do not have freedom, they would rather starve to death [38]. Therefore, this paper adds a suicide mechanism to the original mechanism of the sparrow search algorithm. ti represents the number of iterations in which the individual’s position is not updated. When the individual in the population exceeds the number of dangerous iterations Tc and does not update the position, it is considered that the sparrow is in an imprisoned state. At this time, the sparrow will go on hunger strike and commit suicide. At this time, we abandon the sparrow individual and generate a new sparrow individual, which helps the algorithm jump out of the local optimum. This process can be expressed by an old Chinese saying: “die and come back,” and its position is updated as follows:(11)Xi,jt+1=Xi,jt+Xi,jt⋅randn,ti≥Tc,Xi,jt,otherwise.


### 3.4. GPSSA Algorithm Flow

Algorithm 1: The framework of the GPSSA.
Input:(1)
N: Population sparrows(2)
M: Maximum number of iterations(3)
ST: Alert value(4)
Tc: Number of dangerous iterations(5)
PD: Proportion of discoverers in the population(6)
SD: Proportion of scouters in the population(7)
Output:Xbest, fg(8)
t = 1;(9)
Initialize population by formula (5).(10)
While (t < M)(11)
Sort fitness values and mark the positions of the best and worst sparrows.(12)
R2 = rand (1).(13)
Fori = 1: PD ∗ N(14)
Using formula (1) to update the location of the discoverers;(15)
End for(16)
Fori = (PD ∗ N + 1): N(17)
The discoverers who were going to prey were selected according to formulas (6)–(9);(18)
Using formula (10) to update the location of the followers;(19)
End for(20)
Forl = 1 : SD(21)
Using formula (3) to update the location of the scouters;(22)
End for(23)
Update the number of dangerous iterationsTc for each individual;(24)
Update the location of the sparrows according to formula (11);(25)
Get the new optimal individual;(26)
t = t + 1;(27)
End while(28)
Return:Xbest, fg


### 3.5. Time Complexity Analysis

According to the number of populations, iteration times, and dimensions of SSA algorithm, we can easily know that the time complexity of original SSA algorithm is O (P·M·D). Firstly, GPSSA algorithm is improved on the basis of SSA algorithm; GPSSA has the same structure as the original algorithm and does not increase the number of cycles. Secondly, the good point set strategy replaces the original method of randomly initializing the population, but the time complexity does not increase. The game predatory mechanism only changes the way to approach the current optimal solution and further approaches the suboptimal solution to prevent the omission of the suboptimal solution, which also does not increase the time complexity. The suicide mechanism adopts greedy strategy, which increases the complexity of the searcher's algorithm to a certain extent. Only a few individuals in the population increase the complexity of the algorithm but not the order of magnitude of the entire algorithm. To sum up, we can get that the time complexity of GPSSA is still O(P·M·D).


## 3.1. Good Point Set

The good point set was proposed by Chinese mathematicians Hua and Wang [37], and its principle is as follows: let GS be the unit cube in s-dimensional Euclidean space, and if r∈Gs, the form is(4)Pnk=r1n⋅k,r2n⋅k,…rsn⋅k,1≤k≤n.If the deviationφn satisfies φn=Cr,εn−1+ε, ε is any positive number, where Cr,εn−1+ε is a constant only related to r and ε. Pnk is a good point set and r is a good point. rsn⋅k represents the decimal part, n represents the number of points, and r=2cos2πk/p,1≤k≤s , where p is the minimum prime number satisfying p−3/2≥s. Map it to the search space [34] as(5)xij=ubj−lbj⋅rji⋅k+lbj,where ubj and lbj represent the upper and lower bounds of the j-th dimension, respectively.Figure1(a) shows a randomly generated initial population distribution map when the good point set is in [0, 1], the number of populations is 500, and the dimension is 1. Figure 1(b)shows the frequency distribution histogram of good point set and tent chaotic map [35] under the above conditions. It can be seen that the good point integration is evenly distributed, and the initialization effect is better than that of tent chaotic map. In the initialization process, the good point set has a more uniform population, which can increase the diversity of the population and help to eliminate the attraction of the local optimal solution.Figure 1
Distribution of good point set.
(a)(b)


## 3.2. Game Predatory Mechanism

The followers in sparrow algorithm have a predatory mechanism; that is, the followers directly jump to the vicinity of the optimal location of the discoverer to compete for food. However, the food in the best position of the discoverer is not endless, and it is impossible to meet the food needs of a large number of followers, which is also inconsistent with the laws of nature. Therefore, based on the game theory, this paper proposes a game predator mechanism; that is, the predatory mechanism of followers and discoverers is regarded as a game process. Wheni < N/2, it is stipulated that the food found by each discoverer can only meet the needs of limited participants, and the amount of food found is determined by its fitness value. The top followers will give priority to those who find the most food to grab food. In order to obtain food and avoid hunger, the lower ranked participants will choose the discoverer who finds less food to eat, as shown in Figure 2(a). It is worth noting that, for the mechanism when i > N/2, the followers obtain food and forage alone is retained, as shown in Figure 2(b).Figure 2
Principle of game grabbing mechanism.
(a)(b)It is found from (2) that when i ≤ N/2, the followers will grab food after the discoverers. Therefore, there are R followers who directly jump to the vicinity of the discoverer who finds the most food and grab food, where R=N/2−PD⋅N and PD is the proportion of discoverers.Assuming that the food found by each discoverer is limited, the food in the optimal location of the discoverer cannot meet the food needs of a large number of followers, and the followers participating in the predator mechanism will grab food from different discoverers because of the shortage of food. At this time, it is a game process, and the followers will choose the discoverer who is most favorable to them to grab food. There are two steps in the game predatory mechanism: one is to count the food quantity of the discoverer, and the other is to make game selection to select the most beneficial discoverer for oneself as follows.


### 3.2.1. Food Quantity Statistics of Discoverer

Individuals with lower fitness are considered to be better choices. The lower the fitness of the discoverer’s location is, the more food is found, and the number of discoverers isPD⋅N. Dz represents the z-th discoverer. Then the quantity G of food found by the z-th discoverer can be expressed as(6)Gz=1fDz,z=1,2,…,PD⋅N.


### 3.2.2. Game Choice

WhenJz followers compete for food with the z-th discoverer, the subsequent followers will choose to compete for food with the z + 1-th discoverer because of the game mechanism, and so on. Fj represents the j-th follower. Jz is determined by the ratio pz of the quantity Gz of food found by the z-th discoverer to the total quantity. The specific principle is as follows:(7)pz=Gz∑z=1PD⋅NGz,(8)Jz=roundpz⋅R.At this time, the relationship between each follower in the game predatory mechanism and its predatory discoverer is as follows:(9)D1F1F2⋯FJ1,D2FJ1+1FJ1+2⋯FJ1+J2,⋯,DPD⋅NFJ1+J2+⋯+JPD⋅N−1+1,FJ1+J2+⋯+JPD⋅N−1+2,⋯FJ1+J2+⋯+JPD⋅N..Therefore, the location update formula of the improved followers is as follows:(10)Xi,jt+1=Q⋅expXworstt−Xi,jti2,i>N2,Dz,jt+1+Xi,jt−Dz,jt+1⋅A+⋅L,otherwise.


## 3.2.1. Food Quantity Statistics of Discoverer

Individuals with lower fitness are considered to be better choices. The lower the fitness of the discoverer’s location is, the more food is found, and the number of discoverers isPD⋅N. Dz represents the z-th discoverer. Then the quantity G of food found by the z-th discoverer can be expressed as(6)Gz=1fDz,z=1,2,…,PD⋅N.


## 3.2.2. Game Choice

WhenJz followers compete for food with the z-th discoverer, the subsequent followers will choose to compete for food with the z + 1-th discoverer because of the game mechanism, and so on. Fj represents the j-th follower. Jz is determined by the ratio pz of the quantity Gz of food found by the z-th discoverer to the total quantity. The specific principle is as follows:(7)pz=Gz∑z=1PD⋅NGz,(8)Jz=roundpz⋅R.At this time, the relationship between each follower in the game predatory mechanism and its predatory discoverer is as follows:(9)D1F1F2⋯FJ1,D2FJ1+1FJ1+2⋯FJ1+J2,⋯,DPD⋅NFJ1+J2+⋯+JPD⋅N−1+1,FJ1+J2+⋯+JPD⋅N−1+2,⋯FJ1+J2+⋯+JPD⋅N..Therefore, the location update formula of the improved followers is as follows:(10)Xi,jt+1=Q⋅expXworstt−Xi,jti2,i>N2,Dz,jt+1+Xi,jt−Dz,jt+1⋅A+⋅L,otherwise.


## 3.3. Suicide Mechanism

Sparrows mostly live in places where human beings live. They are very lively, bold, and approachable, but they are very vigilant. Sparrows are very proud birds. They live on people, but they do not want to be kept in captivity. If they do not have freedom, they would rather starve to death [38]. Therefore, this paper adds a suicide mechanism to the original mechanism of the sparrow search algorithm. ti represents the number of iterations in which the individual’s position is not updated. When the individual in the population exceeds the number of dangerous iterations Tc and does not update the position, it is considered that the sparrow is in an imprisoned state. At this time, the sparrow will go on hunger strike and commit suicide. At this time, we abandon the sparrow individual and generate a new sparrow individual, which helps the algorithm jump out of the local optimum. This process can be expressed by an old Chinese saying: “die and come back,” and its position is updated as follows:(11)Xi,jt+1=Xi,jt+Xi,jt⋅randn,ti≥Tc,Xi,jt,otherwise.


## 3.4. GPSSA Algorithm Flow

Algorithm 1: The framework of the GPSSA.
Input:(1)
N: Population sparrows(2)
M: Maximum number of iterations(3)
ST: Alert value(4)
Tc: Number of dangerous iterations(5)
PD: Proportion of discoverers in the population(6)
SD: Proportion of scouters in the population(7)
Output:Xbest, fg(8)
t = 1;(9)
Initialize population by formula (5).(10)
While (t < M)(11)
Sort fitness values and mark the positions of the best and worst sparrows.(12)
R2 = rand (1).(13)
Fori = 1: PD ∗ N(14)
Using formula (1) to update the location of the discoverers;(15)
End for(16)
Fori = (PD ∗ N + 1): N(17)
The discoverers who were going to prey were selected according to formulas (6)–(9);(18)
Using formula (10) to update the location of the followers;(19)
End for(20)
Forl = 1 : SD(21)
Using formula (3) to update the location of the scouters;(22)
End for(23)
Update the number of dangerous iterationsTc for each individual;(24)
Update the location of the sparrows according to formula (11);(25)
Get the new optimal individual;(26)
t = t + 1;(27)
End while(28)
Return:Xbest, fg


## 3.5. Time Complexity Analysis

According to the number of populations, iteration times, and dimensions of SSA algorithm, we can easily know that the time complexity of original SSA algorithm is O (P·M·D). Firstly, GPSSA algorithm is improved on the basis of SSA algorithm; GPSSA has the same structure as the original algorithm and does not increase the number of cycles. Secondly, the good point set strategy replaces the original method of randomly initializing the population, but the time complexity does not increase. The game predatory mechanism only changes the way to approach the current optimal solution and further approaches the suboptimal solution to prevent the omission of the suboptimal solution, which also does not increase the time complexity. The suicide mechanism adopts greedy strategy, which increases the complexity of the searcher's algorithm to a certain extent. Only a few individuals in the population increase the complexity of the algorithm but not the order of magnitude of the entire algorithm. To sum up, we can get that the time complexity of GPSSA is still O(P·M·D).


## 4. Exploration and Exploitation Stage and Population Diversity

Literature [39] proposes a theoretical system to evaluate the algorithm’s exploration and exploitation stage and population diversity by using the differences between individual dimensions of the population. On the basis of the above, literature [40] uses the median that can better reflect the population center instead of the average to calculate the dimensional diversity, and the effect is more accurate. The calculation formula is shown in (12). When the population diverges, it indicates that it is in the exploration stage, and the calculation formula is shown in (12). When the population gathers, it indicates that it is in the exploitation stage, and the calculation formula is shown in the following equation:(12)Divj=∑i=1Nmedianxj−xi,jN,Div=∑j=1DDivjD,Xpl=DivDivmax,Xpt=Div−DivmaxDivmax,where medianxj represents the median of the j-th dimension of the whole population, xi,j represents the j-th dimension of the i-th individual, Divj represents the diversity of the j-th dimension, Div represents the diversity of the whole population, and Divmax represents the maximum population diversity in the iterative process. In the search process, Xpl and Xpt represent the percentages of exploration and exploitation stages, respectively.


### 4.1. Invalid Search Indicator

The above method does not take into account the fact that when an individual exceeds the boundary in the search process, the individual beyond the boundary will be corrected to the boundary in the next iteration. Therefore, the position beyond the boundary is invalid, and the diversity of the population is also invalid or inaccurate. Therefore, this paper proposes an indexInv to evaluate the invalid search beyond the boundary of the algorithm, which is used to describe the ability of invalid search in the t-th iteration of the algorithm. The specific expression is as follows:(13)Inv=1N⋅D∑i=1N∑j=1DmaxminXi,jt−lbj,0,minubj−Xi,jt,0,where minXi,jt−lb,0 and minub−Xi,jt,0 are used to determine the distance values of lb and ub beyond the boundary. If it does not exceed the boundary, the value is 0. maxminXi,jt−lb,0,minub−Xi,jt,0 is used to calculate the distance beyond the boundary. It is easy to know that one of the two must be 0, because it can only exceed one side of the boundary. The smaller the value, the stronger the ability of the algorithm to search effectively.


### 4.2. Improved Exploration and Exploitation Stage and Population Diversity

If the above indexes for evaluating the invalid search ability are brought into the original index system, more accurate indexes of population diversity and exploration and exploitation stage can be obtained. For individuals beyond the boundary in the search process, the strategy of modifying to the boundary will be adopted in the next iteration, so the boundary position is the real position of individuals beyond the search boundary. Since the individuals beyond the boundary do not affect the selection of the median, the improved formula is as follows:(14)Div′=Div−Inv,(15)Xpl′=Div′Divmax′,(16)Xpt′=Div′−Divmax′Divmax′.


## 4.1. Invalid Search Indicator

The above method does not take into account the fact that when an individual exceeds the boundary in the search process, the individual beyond the boundary will be corrected to the boundary in the next iteration. Therefore, the position beyond the boundary is invalid, and the diversity of the population is also invalid or inaccurate. Therefore, this paper proposes an indexInv to evaluate the invalid search beyond the boundary of the algorithm, which is used to describe the ability of invalid search in the t-th iteration of the algorithm. The specific expression is as follows:(13)Inv=1N⋅D∑i=1N∑j=1DmaxminXi,jt−lbj,0,minubj−Xi,jt,0,where minXi,jt−lb,0 and minub−Xi,jt,0 are used to determine the distance values of lb and ub beyond the boundary. If it does not exceed the boundary, the value is 0. maxminXi,jt−lb,0,minub−Xi,jt,0 is used to calculate the distance beyond the boundary. It is easy to know that one of the two must be 0, because it can only exceed one side of the boundary. The smaller the value, the stronger the ability of the algorithm to search effectively.


## 4.2. Improved Exploration and Exploitation Stage and Population Diversity

If the above indexes for evaluating the invalid search ability are brought into the original index system, more accurate indexes of population diversity and exploration and exploitation stage can be obtained. For individuals beyond the boundary in the search process, the strategy of modifying to the boundary will be adopted in the next iteration, so the boundary position is the real position of individuals beyond the search boundary. Since the individuals beyond the boundary do not affect the selection of the median, the improved formula is as follows:(14)Div′=Div−Inv,(15)Xpl′=Div′Divmax′,(16)Xpt′=Div′−Divmax′Divmax′.


## 5. Experimental Simulation of Basic Test Function

In this paper, six basic test functions are selected to verify the performance of GPSSA algorithm and compared with other heuristic algorithms, such as PSO, DE, GWO, SSA, and GPSSA. The specific parameter settings are shown in Table1. F1–F3 are high-dimensional single peak benchmark functions, F4-F5 are high-dimensional multipeak benchmark functions, and F6 is low-dimensional multipeak benchmark function. The test function information is shown in Table 2, and the parameter space is shown in Figure 3.Table 1
Parameter settings.
AlgorithmPSODEGWOCSMSSCSSSAGPSSAParameterc1 = 2CR = 0.2a = (2 ⟶ 0)α = 0.01α = 0.01SD = 0.2SD = 0.2c2 = 2β = 1.5PD = 0.2Wmin = 0.2Fmin = 0.2β = 1.5Pa = 0.25PD = 0.2ST = 0.8c = 0.2Wmax = 0.9Fmax = 0.8Pa = 0.25PAmax = 0.35ST = 0.8Tc = M/20PAmin = 0.25Table 2
Basic test function.
FunctionDimensionsIntervalMinF1x=∑i=1nxi230/100[−100, 100]0F2x=∑i=1nxi+∏i=1nxi30[−100, 100]0F3x=∑i=1nixi4+random0，130[−1.28, 1.28]0F4x=∑i=1n−xisinxi30[−500, 500]−418.98 ∗ dimF5x=∑i=1nxi2−10cos2πxi+1030[−5.12, 5.12]0F6x=∑i=17X−aiX−aiT+ci−14[0, 10]−10.4029Figure 3
Parameter space of function.Figure4 shows the initial population of the above algorithm and the step size update after only one iteration, in which the objective function is F1 and the number of populations is 100. The red cross in the figure is the location of the optimal solution. As can be seen from the figure, the step amplitude of PSO update is small, and the step amplitude of DE and GWO is large. However, the optimal solution found after initializing the population is not fully utilized by DE and GWO, resulting in blind search. Because of the influence of the discoverer-follower mechanism, most of the population individuals converge near the optimal solution, which is also the main reason why the SSA algorithm has the advantage of fast convergence speed. However, it is also easy to fall into the dilemma of local optimization, and it can be seen from the figure that the initial population of GPSSA is more uniform due to the influence of good point set strategy. Due to the game predatory mechanism, some followers will approach the current suboptimal solution to prevent missing the better solution and falling into the local optimum.Figure 4
Algorithm step diagram.Figure5 shows the comparison of the effects of the three strategies proposed in this paper. Set the population number to 30 and the number of iterations to 500, and select F1 as the objective function, where (a) is 30 dimensions and (b) is 100 dimensions. SSA is the original algorithm; SSA1, SSA2, and SSA3 are the improved algorithms with good point set strategy, game predatory mechanism, and suicide mechanism separately added to SSA; and GPSSA is the improved algorithm with three strategies added. As can be seen from the above figure, the addition of these three strategies can improve the performance of SSA algorithm to a certain extent. At 30 dimensions, SSA1 and SSA2 are better; at 100 dimensions, the effect of SSA2 and SSA3 is more obvious when the dimension increases, but SSA1 has no significant change. The effect of GPSSA is better than that of a single strategy, which shows that the good point set strategy, game predatory mechanism, and suicide mechanism all have a good improvement effect on the original algorithm.Figure 5
Strategy effect comparison.
(a)(b)Table3 shows the comparison of optimization effects of each algorithm running independently for 30 times, in which the population size is 30, the maximum number of iterations of each algorithm is 500, and the best value of each index is displayed in bold. Finally, the average value is used to sort each algorithm (if the average value is equal, consider the standard deviation). It can be seen from the table that GPSSA shows excellent optimization performance. GPSSA has found the optimal value in F1–F6, indicating that GPSSA has good optimization ability; each index is almost the best in all algorithms, and the comprehensive ranking is also the first, indicating that GPSSA has good optimization accuracy and stability. Except for F5, the results of GPSSA and SSA are the same. In other functions, GPSSA has found a better solution than SSA, indicating that GPSSA algorithm has stronger optimization performance than the original algorithm.Table 3
Comparison table of optimization effect.
IndexPSODEGWOSSAGPSSAF1Best8.93E −062.48E +016.31E −280.00E +000.00E + 00Worst8.36E −047.54E +044.66E −251.37E −670.00E + 00Ave1.63E −043.72E +045.25E −264.58E −690.00E + 00Std2.13E −042.08E +041.13E −252.51E −680.00E + 00Rank45321F2Best4.10E −035.61E +001.47E −160.00E +000.00E + 00Worst2.71E −013.71E +131.61E −153.45E −400.00E + 00Ave4.03E −021.28E +126.19E −161.15E −410.00E + 00Std5.51E −026.77E +123.56E −166.30E −410.00E + 00Rank45321F3Best6.02E −021.93E −035.47E −045.86E −063.90E−06Worst3.15E −011.64E +027.20E −031.28E −032.47E−04Ave1.63E −014.72E +011.93E −032.86E −045.88E−05Std6.39E −025.11E +011.52E −033.05E −045.21E−05Rank45321F4Best−7.10E +03−1.13E +04−7.18E +03−1.26E +04−1.26E + 04Worst−3.07E +03−1.61E +03−3.05E +03−5.56E +03−1.03E + 04Ave−5.37E +03−4.73E +03−5.62E +03−9.83E +03−1.21E + 04Std1.12E +032.25E +031.09E +032.34E +036.38E + 02Rank45321F5Best3.59E +016.24E +015.68E −140.00E +000.00E + 00Worst9.06E +014.45E +027.83E +000.00E +000.00E + 00Ave5.76E +013.11E +029.05E −010.00E +000.00E + 00Std1.30E +011.25E +021.97E +000.00E +000.00E + 00Rank45311F6Best−1.04E +01−6.43E +00−1.04E +01−1.04E +01−1.04E + 01Worst−2.75E +00−5.28E −01−5.09E +00−5.09E +00−1.04E + 01Ave−8.59E +00−1.76E +00−9.87E +00−9.34E +00−1.04E + 01Std3.11E +001.36E +001.62E +002.16E +002.53E−07Rank45231Average rank452.8321Figure6 shows the convergence diagram of each algorithm in the above function. GPSSA has faster convergence speed and better optimization accuracy than SSA. In F1 and F2, the convergence rate of GPSSA is very stable, almost in a straight line, and there is no cliff decline like SSA, indicating that the game predatory mechanism has stronger and more stable optimization ability than the original SSA predatory mechanism. In F3 and F4, SSA falls into the local optimum, while GPSSA will regenerate new individuals to jump out of the local optimum after stopping updating due to the suicide mechanism. In F5, although both SSA and GPSSA find the optimal solution, the convergence speed of GPSSA is faster. In F6, both SSA and GPSSA find the optimal solution after falling into the local optimum, which shows that the original SSA algorithm also has a certain ability to jump out of the local optimum, but GPSSA has a stronger ability to jump out of the local optimum.Figure 6
Convergence diagram of each algorithm.
(a)(b)(c)(d)(e)(f)Figure7 shows the invalid search index of each algorithm obtained according to formula (13), which is used to represent the index of invalid search caused by exceeding the boundary in the search process. The change trend of this index is mainly related to the update mechanism of the algorithm location. For example, the population will continue to converge in the search process of PSO, DE, and GWO algorithms, so it will continue to decrease with the number of iterations. Although SSA and GPSSA will also converge and converge faster, due to the antipredation behavior in the algorithm, some population individuals will continue to escape the current position and will not be reduced by the number of iterations, such as F3 and F6. F1, F2, F4, and F5 are not affected by the update step size and boundary size.Figure 7
Invalid search of each algorithm.
(a)(b)(c)(d)(e)(f)Because an individual experiences the phenomenon of exceeding the boundary in the search process and the individual is corrected to the boundary in the next iteration update, the boundary position is the real position of the individual exceeding the boundary in the search process. The improved diversity index removes such effects and the results will be more accurate. Figure8 shows the population diversity calculated according to the improved formula (14). It can be seen from Figure 8 that the diversity of PSO, DE, and GWO algorithms will decrease with the number of iterations due to the continuous convergence of population individuals, and the decline speed of PSO is the slowest. SSA and GPSS algorithms decline faster, but because the vigilant mechanism continues to escape from the current position, it will not fall to 0, but it will continue to fluctuate to maintain population diversity and prevent falling into local optimization. Combined with Figure 6, we can find that when SSA and GPSSA no longer converge (when the convergence curve level or no longer decreases), the population diversity will suddenly rise due to the antipredation behavior, which helps the algorithm jump out of the local optimum. At the same time, due to the suicide mechanism, GPSSA will think that it is in an imprisoned state at this time and then commit suicide to produce new individuals, which will have better population diversity compared to the SSA algorithm.Figure 8
Diversity of each algorithm.
(a)(b)(c)(d)(e)(f)According to equations (15) and (16), Figure 9 shows the exploration-exploitation ratio of each algorithm in six functions, where (a), (b), (c), (d), (e), and (f) are the development exploration ratio under F1, F2, F3, F4, F5, and F6, respectively. As can be seen from the figure, PSO, DE, and GWO algorithms all change from exploration stage to exploitation stage with the number of iterations, and the exploitation percentage increases and the exploration percentage decreases. SSA and GPSS algorithms enter the development stage after very few iterations because of their fast convergence speed. Combined with Figure 6, we can find that when SSA and GPSSA are no longer convergent, the development percentage continues to decline, the exploration percentage increases, and the development stage changes to the exploration stage to prevent them from falling into local optimization. Due to the addition of three strategies, GPSSA has better search ability and the ability to jump out of local optimization, which leads GPSSA to find the optimal solution earlier, end the exploitation stage, and then enter the exploration stage.Figure 9
Exploration-exploitation percentage of each algorithm.
(a)(b)(c)(d)(e)(f)


## 6. CEC2017 Test

In order to further verify the generality of the algorithm, the algorithm is tested on CEC2017 test function [41]. Due to the defects of F2 function, this paper will not test. The number of dimensions is 30, the number of individuals is 100, the number of evaluations is set to 10000 ∗ dim, and the algorithm parameters remain unchanged. After 30 independent runs, the average value and standard deviation of each algorithm are calculated according to the results and finally sorted. The best value for each index is displayed in bold. The specific test results are shown in Table 4.Table 4
CEC2017 test results.
IndexPSODEGWOCSMSSCSSSAGPSSAF1Ave3.32E +033.44E +078.25E +089.97E +073.24E +033.82E +031.57E +03Std3.40E +032.68E +065.83E +084.18E +073.35E +033.29E +032.26E +03Rank3576241F3Ave3.00E +021.22E +052.82E +043.81E +042.32E +045.03E +042.19E +04Std1.03E −019.82E +039.91E +031.23E +047.21E +032.05E +041.47E +04Rank1745362F4Ave4.73E +025.41E +025.35E +025.12E +025.06E +025.10E +024.88E +02Std2.77E +014.18E +002.72E +012.62E +012.28E +011.58E +012.90E +01Rank1765342F5Ave6.38E +026.82E +028.03E +026.33E +026.14E +027.80E +025.95E +02Std1.30E +011.11E +017.68E +001.89E +011.79E +016.20E +013.72E +01Rank4573261F6Ave6.38E +026.02E +026.57E +026.25E +026.30E +026.65E +026.03E +02Std9.06E +001.06E −016.18E +002.46E −011.66E −017.27E +001.55E +00Rank5163472F7Ave8.30E +029.28E +021.33E +038.64E +028.69E +021.33E +038.42E +02Std2.13E +017.59E +001.01E +012.09E +011.96E +011.36E +012.72E +01Rank1573462F8Ave9.11E +029.85E +029.74E +029.47E +029.29E +029.91E +028.86E +02Std1.58E +019.28E +003.22E +011.78E +011.66E +013.13E +012.55E +01Rank2654371F9Ave3.08E +032.89E +035.41E +031.05E +031.00E +035.42E +031.38E +03Std5.67E +022.09E +023.09E +017.65E +015.66E +011.10E +023.09E +02Rank5462173F10Ave4.23E +037.21E +035.75E +035.41E +034.86E +036.25E +034.43E +03Std5.71E +021.93E +021.02E +032.80E +024.16E +021.13E +031.12E +03Rank1754362F11Ave1.20E +031.62E +031.40E +031.21E +031.20E +031.24E +031.22E +03Std2.28E +018.83E +019.95E +012.80E +012.62E +014.38E +014.74E +01Rank2763154F12Ave5.18E +045.16E +072.78E +078.08E +097.08E +091.92E +061.16E +06Std2.60E +046.84E +062.74E +074.21E +094.93E +091.36E +061.50E +06Rank1547632F13Ave9.40E +034.28E +062.48E +067.07E +083.52E +081.49E +074.56E +03Std1.14E +041.35E +061.31E +072.64E +091.92E +095.73E +072.40E +03Rank2437651F14Ave8.51E +031.17E +052.94E +051.59E +031.56E +031.76E +046.20E +03Std4.65E +035.33E +043.29E +052.51E +011.28E +011.44E +041.18E +03Rank4672153F15Ave1.61E +043.74E +053.48E +042.15E +031.73E +037.62E +033.57E +03Std1.19E +042.64E +052.32E +041.77E +023.09E +016.45E +037.42E +02Rank5762143F16Ave2.53E +032.74E +033.37E +032.51E +032.36E +033.57E +032.36E +03Std1.82E +028.27E +015.91E +022.51E +022.05E +026.71E +022.63E +02Rank4563271F17Ave2.12E +032.01E +032.79E +031.98E +031.96E +032.87E +031.98E +03Std2.07E +025.48E +012.84E +029.25E +016.33E +012.51E +021.73E +02Rank5462173F18Ave1.45E +051.21E +067.22E +051.17E +055.71E +041.25E +053.61E +05Std1.47E +053.49E +056.37E +054.01E +042.29E +042.10E +051.63E +05Rank4762135F19Ave9.39E +034.08E +057.29E +052.84E +032.08E +036.35E +032.86E +03Std1.02E +049.24E +042.38E +064.61E +022.63E +013.84E +035.71E +02Rank5672143F20Ave2.46E +032.34E +032.80E +032.32E +032.30E +032.72E +032.37E +03Std1.18E +026.38E +014.06E +019.61E +018.90E +012.01E +021.13E +02Rank5372164F21Ave2.42E +032.49E +032.56E +032.49E +032.49E +032.55E +032.38E +03Std2.25E +017.43E +002.71E +014.14E +014.97E +012.46E +012.20E +01Rank2375461F22Ave3.46E +034.51E +036.95E +033.60E +033.61E +036.97E +034.55E +03Std1.85E +032.43E +021.76E +032.04E +031.86E +031.09E +032.28E +03Rank1462375F23Ave3.03E +032.83E +033.08E +032.85E +032.87E +033.26E +032.79E +03Std9.38E +017.69E +008.69E +013.23E +012.04E +011.09E +027.37E +01Rank5263471F24Ave3.14E +033.02E +033.21E +033.02E +033.03E +033.39E +032.91E +03Std1.06E +026.89E +005.94E +012.12E +016.03E +019.44E +013.89E +01Rank5263471F25Ave2.88E +032.92E +032.96E +033.00E +033.03E +032.91E +032.90E +03Std8.15E +005.19E +002.40E +011.48E +009.70E −011.51E +011.85E +01Rank1456732F26Ave6.02E +035.40E +038.84E +033.49E +033.37E +037.63E +034.45E +03Std2.17E +038.24E +019.26E +028.16E +026.27E +021.54E +033.63E +02Rank5472163F27Ave3.21E +033.23E +033.46E +033.34E +033.37E +033.59E +033.23E +03Std1.05E +023.01E +001.17E +028.91E +001.01E +012.75E +021.86E +01Rank1364572F28Ave3.19E +033.33E +033.36E +033.36E +033.37E +033.24E +033.19E +03Std5.53E +016.87E +003.59E +012.30E +012.13E +012.37E +015.41E +01Rank2465731F29Ave3.78E +034.03E +035.37E +033.78E +033.76E +035.02E +033.68E +03Std2.43E +029.67E +019.24E +021.10E +021.18E +025.75E +021.42E +02Rank3574261F30Ave5.26E +035.28E +057.35E +062.41E +041.33E +042.76E +042.43E +04Std2.38E +031.63E +053.03E +066.52E +033.18E +031.18E +041.02E +04Rank1673254Average rank2.974.766.003.592.935.482.28The results in Table4 show that the average value of GPSSA algorithm is the best value among all algorithms in F1, F5, F8, F9, f13, F14, F15, F16, F17, F19, F21, F23, F24, F26, F28, and F29 functions, which shows that GPSSA algorithm has good optimization ability and accuracy. The average ranking of GPSSA is 2.28, followed by PSO (2.97), MSSCS (2.93), CS (3.59), DE (4.76), SSA (5.48), and GWO (6.00). The SSA algorithm does not perform well in more complex CEC217. Only due to GWO, it shows that the optimization ability of the original algorithm decreases in more complex optimization problems, while the improved GPSSA is more suitable for complex optimization problems due to the improvement of mechanism.Figure10 shows a radar chart made according to the algorithm ranking. The higher the ranking is, the closer it is to the radar center. It can be seen that more than half of GPSSA functions are closest to the radar center, and the enclosed area is the smallest. According to the 30 times’ optimal results, all algorithms conduct Wilcoxon rank-sum test for GPSSA, and the results are shown in Table 5. When the value is greater than 0.05, it can be considered that there is no significant difference between the two; otherwise, it is considered that there is a significant difference between the two, where “+” and “−” mean greater than and less than 0.05, respectively. Only a few values in the results are greater than 0.05, indicating that GPSSA algorithm is significantly different from other algorithms. Figure 11 shows the selected six groups of box graphs, in which the box graph of GPSSA has a shorter length than other algorithms, indicating that GPSSA algorithm has strong optimization performance and stability. The results show that the optimization performance of GPSSA is better than that of SSA, and the optimization performances of PSO and MSSCS are also better.Figure 10
Ranking radar chart.Table 5
Wilcoxon rank-sum test results.
FF1F3F4F5F6F7F8F9F10F11PSO2.20E −022.78E −114.52E −011.15E −072.51E −116.71E −028.20E −073.25E −116.62E −017.18E −02DE2.66E −112.80E −117.74E −098.10E −092.39E −012.57E −112.38E −102.79E −117.22E −092.75E −11GWO2.69E −118.97E −031.90E −072.44E −112.51E −112.73E −111.63E −102.76E −112.10E −066.20E −10CS2.65E −118.15E −061.25E −045.09E −072.88E −112.99E −037.59E −103.02E −064.20E −086.30E −01MSSCS2.67E −021.58E −018.61E −043.33E −042.88E −111.14E −043.60E −095.75E −093.82E −037.21E −03SSA7.38E −031.74E −088.73E −059.22E −112.72E −112.52E −111.02E −102.66E −114.03E −083.02E −01F12F13F14F15F16F17F18F19F20F21PSO2.94E −115.58E −015.28E −031.02E −033.72E −044.36E −032.21E −052.50E −011.06E −021.43E −08DE2.59E −112.83E −112.58E −112.42E −115.14E −097.93E −024.48E −112.57E −116.09E −017.48E −11CS6.16E −112.81E −113.99E −102.45E −112.00E −102.83E −116.43E −032.52E −112.42E −112.78E −11MSSCS2.23E −086.88E −092.63E −114.17E −111.83E −033.25E −011.42E −078.53E −011.90E −011.13E −09GWO1.40E −042.60E −032.63E −112.52E −116.84E −013.95E −018.08E −098.13E −104.34E −021.51E −08SSA3.08E −022.92E −093.06E −102.73E −051.60E −102.64E −115.30E −074.25E −043.80E −092.41E −11F22F23F24F25F26F27F28F29F30+/ = /−PSO2.52E −042.74E −118.73E −111.06E −067.61E −039.31E −088.65E −011.44E −012.41E −1121/0/8DE8.19E −011.85E −015.22E −102.94E −064.81E −109.70E −012.78E −113.07E −102.78E −1123/0/6GWO2.96E −052.83E −112.78E −111.95E −092.43E −112.83E −113.74E −114.59E −112.75E −1129/0/0CS2.91E −021.50E −027.03E −102.72E −113.05E −042.93E −113.00E −112.02E −031.53E −0125/0/5MSSCS5.36E −021.59E −034.78E −092.72E −112.32E −062.93E −113.00E −117.44E −021.24E −0925/0/5SSA6.79E −072.47E −112.48E −113.49E −034.63E −102.44E −119.40E −052.68E −111.66E −0127/0/2Figure 11
Box diagram of each algorithm.In the SSA algorithm, when the participants in the population move closer to the discoverer, they jump directly to the current optimal solution instead of moving slowly to the current optimal solution, so the result of SSA is very poor. This problem leads to a large range of individual update steps of the population in SSA algorithm, which accelerates the convergence of the algorithm, but it is easy to miss the high-quality solution. GPSSA algorithm adopts an improved strategy to make up for this disadvantage, which makes the initial population more uniform, makes full use of other better solutions or generates new solutions, increases the population diversity, makes the search method more flexible, and greatly reduces the loss of population diversity. In general, GPSSA algorithm retains the advantage of fast convergence speed of the original algorithm, has good universality and optimization performance, and has strong competitiveness compared with other algorithms.


## 7. UAV Path Planning

UAV path planning problem [42] is an optimization problem where UAV uses terrain as cover to effectively avoid various threats, so as to improve the survivability of aircraft and quickly reach the destination. Aiming at the problem of UAV path planning, several methods such as graph theory search, element decomposition, potential field, and natural heuristic algorithm are proposed in the literature [43–45]. However, with the more and more complex tasks undertaken by UAV, the uncertainty of its flight environment, and the higher requirements for track planning, the superiority of swarm intelligence algorithm in solving complex problems makes more and more scholars apply swarm intelligence algorithm to this field. To solve the UAV track planning problem, it is necessary to establish an appropriate fitness function and consider various constraints affecting the track quality. The static global 3D track planning model mainly includes cost function and constraint function.


### 7.1. Flight Path Cost

In the actual combat mission, the fuel carried by UAV is limited, the track length can reflect the fuel consumption, andLi is the track length of the i-th segment. That is, UAV flight fuel consumption cost can be expressed as track length:(17)fpath=∑i=1NLi.


### 7.2. Flight Altitude Change Cost

In order to avoid radar search and prevent collision with mountains or other obstacles, the UAV must raise or lower the height, but repeated lifting and lowering will also endanger the safety of the UAV. The variance of track altitude change can describe the stability of flight altitude. As the cost of altitude change, it can be expressed as(18)fheight=∑i=1Nzi−1/N∑i=1Nzi2N.


### 7.3. Smoothing Cost

In the flight process, the larger the deflection angle is, the more unstable the flight state of the UAV is and the less smooth the flight path is. Therefore, the smoothing cost is added to increase the stability and smoothness of UAV track, and the smoothing cost is expressed by the change degree of deflection angleδ. The function is set as follows:(19)fsmooth=∑i=1Nδi−δi−1.


### 7.4. Integrated Threat Constraints

UAV encounters enemy air defense system when it passes through enemy areas, including detection radar, antiaircraft artillery, and ground-to-air missile. The above threats are approximated as a cylindrical area in three-dimensional plane, and the detection or attack range is used as its radiusR. The current track segment Li is divided into five segments, M represents the comprehensive threat, kM represents the k-th comprehensive threat, RkM represents the radius of the current threat, and dk,i represents the distance from the current threat point to each of the five equal segments. The threat cost of the current synthetic threat point to the track segment is shown in Figure 12, and its threat constraint function is(20)Constraint=∑i=15N∑kM=1nMmaxRkM−dkM,iRkM,0.Figure 12
Threat principle.η is a penalty function, and the trajectory planning objective function in this paper is(21)minfcost=ω1⋅fpath+ω2⋅fheight+ω3⋅fsmooth+η⋅Constraint.In this paper, the cubic B-spline method is used to ensure better curve smoothness for UAV track smoothing. The spline curve generated during track smoothing is determined by four adjacent control points. By reducing the dependence of track smoothing on each operating point, the smoothed track is more effective, as shown in Figure13.Figure 13
Cubic B-spline principle.


### 7.5. Track Coding

An individual in a population is defined as a path connected by multiple track points,Si=sx1,sy1,sz1,sx2,……sxn,syn,szn, in which every 3 coordinates constitute a track point in three dimensions, a total of N track points, and a dimension of 3 ∗ n for each individual.


### 7.6. Experimental Simulation

This paper establishes a three-dimensional mountain terrain using a 100 km × 150 km × 3 km digital elevation map as shown in Figure14. There are five nonflight zones for the composite threat, with the center coordinates of (20,45), (40,75), (60,30), (80,65), and (100,30) and a radius of 15. The starting and ending coordinates are (10,90, 1.1) and (130, 10, 1.1).Figure 14
Original map.η=107, ω1=0.5, ω2=0.3, and ω3=0.2 are set. The cubic B-spline method is used to ensure better curve smoothness for UAV track smoothing.This paper runs 20 times, with 10 track nodes , 30 dimensions, maximum number of iterations of 200, and a population of 100. The experimental results are shown in Table6. Path planning with threats is shown in Figure 15. Top view of path planning contour is shown in Figure 16, and target function convergence is shown in Figure 17.Table 6
UAV track planning results.
IndexPSODEGWOSSAGPSSABest80.824080.620380.812479.625276.0988Worst105.1887104.2779105.1887107.175789.3498Ave88.608087.412786.425292.532582.4084Std9.12918.16427.90809.31973.6872Figure 15
Path planning with threats.Figure 16
Top view of path planning contour.Figure 17
Objective function convergence graph.Combining Figures15–17, it can be seen that SSA is trapped in a local optimum and cannot jump out. GPSSA algorithm can quickly avoid the constraints of threat area and complete path planning, and the path planning is optimal, with faster convergence speed and better accuracy. From the results in Table 6, the four indicators of GPSSA are all optimal, indicating that they have strong optimization ability and stability. The good algorithm performance of GPSSA is verified, which can quickly and accurately get rid of the constraints of threat areas and complete the unmanned aircraft path planning. This helps the unmanned aircraft path static planning to have shorter time, better path planning, and better stability.


## 7.1. Flight Path Cost

In the actual combat mission, the fuel carried by UAV is limited, the track length can reflect the fuel consumption, andLi is the track length of the i-th segment. That is, UAV flight fuel consumption cost can be expressed as track length:(17)fpath=∑i=1NLi.


## 7.2. Flight Altitude Change Cost

In order to avoid radar search and prevent collision with mountains or other obstacles, the UAV must raise or lower the height, but repeated lifting and lowering will also endanger the safety of the UAV. The variance of track altitude change can describe the stability of flight altitude. As the cost of altitude change, it can be expressed as(18)fheight=∑i=1Nzi−1/N∑i=1Nzi2N.


## 7.3. Smoothing Cost

In the flight process, the larger the deflection angle is, the more unstable the flight state of the UAV is and the less smooth the flight path is. Therefore, the smoothing cost is added to increase the stability and smoothness of UAV track, and the smoothing cost is expressed by the change degree of deflection angleδ. The function is set as follows:(19)fsmooth=∑i=1Nδi−δi−1.


## 7.4. Integrated Threat Constraints

UAV encounters enemy air defense system when it passes through enemy areas, including detection radar, antiaircraft artillery, and ground-to-air missile. The above threats are approximated as a cylindrical area in three-dimensional plane, and the detection or attack range is used as its radiusR. The current track segment Li is divided into five segments, M represents the comprehensive threat, kM represents the k-th comprehensive threat, RkM represents the radius of the current threat, and dk,i represents the distance from the current threat point to each of the five equal segments. The threat cost of the current synthetic threat point to the track segment is shown in Figure 12, and its threat constraint function is(20)Constraint=∑i=15N∑kM=1nMmaxRkM−dkM,iRkM,0.Figure 12
Threat principle.η is a penalty function, and the trajectory planning objective function in this paper is(21)minfcost=ω1⋅fpath+ω2⋅fheight+ω3⋅fsmooth+η⋅Constraint.In this paper, the cubic B-spline method is used to ensure better curve smoothness for UAV track smoothing. The spline curve generated during track smoothing is determined by four adjacent control points. By reducing the dependence of track smoothing on each operating point, the smoothed track is more effective, as shown in Figure13.Figure 13
Cubic B-spline principle.


## 7.5. Track Coding

An individual in a population is defined as a path connected by multiple track points,Si=sx1,sy1,sz1,sx2,……sxn,syn,szn, in which every 3 coordinates constitute a track point in three dimensions, a total of N track points, and a dimension of 3 ∗ n for each individual.


## 7.6. Experimental Simulation

This paper establishes a three-dimensional mountain terrain using a 100 km × 150 km × 3 km digital elevation map as shown in Figure14. There are five nonflight zones for the composite threat, with the center coordinates of (20,45), (40,75), (60,30), (80,65), and (100,30) and a radius of 15. The starting and ending coordinates are (10,90, 1.1) and (130, 10, 1.1).Figure 14
Original map.η=107, ω1=0.5, ω2=0.3, and ω3=0.2 are set. The cubic B-spline method is used to ensure better curve smoothness for UAV track smoothing.This paper runs 20 times, with 10 track nodes , 30 dimensions, maximum number of iterations of 200, and a population of 100. The experimental results are shown in Table6. Path planning with threats is shown in Figure 15. Top view of path planning contour is shown in Figure 16, and target function convergence is shown in Figure 17.Table 6
UAV track planning results.
IndexPSODEGWOSSAGPSSABest80.824080.620380.812479.625276.0988Worst105.1887104.2779105.1887107.175789.3498Ave88.608087.412786.425292.532582.4084Std9.12918.16427.90809.31973.6872Figure 15
Path planning with threats.Figure 16
Top view of path planning contour.Figure 17
Objective function convergence graph.Combining Figures15–17, it can be seen that SSA is trapped in a local optimum and cannot jump out. GPSSA algorithm can quickly avoid the constraints of threat area and complete path planning, and the path planning is optimal, with faster convergence speed and better accuracy. From the results in Table 6, the four indicators of GPSSA are all optimal, indicating that they have strong optimization ability and stability. The good algorithm performance of GPSSA is verified, which can quickly and accurately get rid of the constraints of threat areas and complete the unmanned aircraft path planning. This helps the unmanned aircraft path static planning to have shorter time, better path planning, and better stability.


## 8. Conclusions

In this paper, game predatory mechanism and suicide mechanism are proposed to improve sparrow search algorithm, which is more in line with the biological habits of sparrow population, ensures more uniform population through a good point set, makes full use of the better individuals in the population through game predatory mechanism and ensures the flexibility of search, and helps the algorithm get rid of the trap of local optimization through suicide mechanism. An invalid search index is presented for the true location of individuals beyond the boundary during the search process, which improves the defect of the original index and makes it more accurate and realistic to reflect the population diversity, exploration, and development stages in the search process. By comparing the basic test functions and CEC2017 with other heuristic algorithms, it is proved that GPSSA has good optimization performance and effectively improves the shortcomings of poor initial population quality, poor utilization of the current better solution, and poor ability to jump out of local optimal. It also strengthens the ability of the original algorithm to get rid of local optimal attraction while retaining the advantages of fast convergence. Through the UAV path planning simulation, the effectiveness and superiority of GPSSA are verified. Using the advantages of rapid convergence and strong optimization performance of GPSSA, it helps to quickly plan the better path. It provides a new method for the research of this kind of field and provides a good case for the research of this algorithm in other fields.In the future, we will try to integrate with PSO and other heuristic algorithms and combine the advantages of these two algorithms to improve their poor global search ability, further improve the search performance, and better apply them to more practical problems.



---

*Source: 4925416-2022-05-16.xml*