# A Particle Swarm Optimization Algorithm with Gradient Perturbation and Binary Tree Depth First Search Strategy

Authors: Xionghua Huang; Tiaojun Zeng; MinSong Li
Journal: Journal of Mathematics
 (2022)

---

## Abstract

In this study, a particle swarm optimization (PSO) algorithm with a negative gradient perturbation and binary tree depth-first strategy (GB-PSO) is proposed. The negative gradient term accelerates particle optimization in the direction of decreasing the objective function value. To calculate the step size of this gradient term more easily, a method based on the ratio was proposed. In addition, a new PSO strategy is also proposed. Each iteration of PSO yields not only the current optimal solution of the group, but also the solution based on the 2-norm maximum. Under the current iteration solution of PSO, these two solutions are the children nodes. In the sense of the binary tree concept, the three solutions constitute the father-son relationship, and the solution generated throughout the entire search process constitutes the binary tree. PSO uses a traceable depth-first strategy to determine the optimal solution. Compared with the linear search strategy adopted by several algorithms, it can fully utilize the useful information obtained during the iterative process, construct a variety of particle swarm search paths, and prevent premature and enhance global optimization. The experimental results show that the algorithm outperforms some state-of-the-art PSO algorithms in terms of search performance.


---

## Body

## 1. Introduction

The general form of optimization problem is as follows:(1)minX∈ℝNFX.This represents the minimum value of the functionminX∈ℝNFX in set ℝN, where X represents the decision variable and FX represents the objective function, and the optimal solution is any feasible solution that minimizes the objective function. Optimization problems are common in industrial production, management science, computer science, and other application fields and disciplines, and more complex optimization problems emerge as these fields and disciplines develop. To solve large-scale complex optimization problems, traditional optimization methods such as Newtons method, the conjugate gradient method, and the trust region method are used. These methods require first- and second-order derivative information of the objective function, involving the calculation of the gradient and Hesse matrix, including matrix inversion [1–10]. Although the traditional method has fast convergence speed, the structure of the objective function in practical engineering applications is complex, and the gradient and Hesse matrices are difficult to calculate or do not exist. These shortcomings limit the scope traditional optimization algorithms of application. Therefore, the search for efficient, universal, and easy-to-calculate optimization algorithms has become one of the primary research topics in related disciplines. Since the 1980s, the theory and methods of swarm intelligence algorithms have been extensively studied, applied, and developed. The swarm intelligence algorithm build stochastic optimization algorithms by simulating the group behavior of natural organisms, such as the ant colony algorithm that simulates ant foraging behavior, particle swarm algorithm that simulates bird foraging behavior, and hybrid frog leaping algorithm that simulates frog foraging. These swarm intelligence algorithms require a low mathematical model of the objective function and can solve nonconvex or nondifferentiable functions. Therefore, they outperform traditional algorithms in solving complex engineering problems [11–15]. Among them, the particle swarm optimization (PSO) algorithm with fewer parameters is simple to implement, and has seen widespread use in image processing, pattern recognition, optimization, and other fields [16–18]. However, similar to other swarm intelligence algorithms, PSO performance declines sharply as the search space dimension increases, and it has some shortcomings, such as slow convergence speed and poor accuracy in late evolution. To solve these problems, researchers have improved the PSO algorithm in terms of parameter selection, multi-algorithm fusion, and algorithm topology, and have achieved several study results. A novel self-adaptive PSO algorithm proposed by Tang et al. [19] was used to alleviate the convergence issue of the basic PSO by fine-tuning the three primary control parameters. Zhang et al. proposed an improved adaptive PSO algorithm [20], which controlled the search direction of particles by dynamically adjusting the sensitive parameter. Vafashoar et al. studied a PSO algorithm based on cellular learning automata and maximum likelihood updating mechanism [21]. To improve the performance of PSO on complex problems, an all dimension-neighborhood-based PSO with randomly selected neighbors learning strategy was proposed in [22]. An integrated PSO algorithm with random-restart hill climbing was presented for the resolution of flexible job shop scheduling problem (FJSP) [23]. Girish proposed a hybrid PSO algorithm in a rolling horizon framework to solve the aircraft landing problem [24]. Feng et al. proposed a new PSO algorithm, which realizes the conditional learning behavior and enables particles to perform natural conditional behavior under unconditional motivation [25]. Zou et al. proposed a multiobjective PSO algorithm based on grid technology and multistrategy. The algorithm combined grid technology to enhance the diversity and convergence of the algorithm, increase the number of particles, and improve the convergence and diversity of the multiobjective PSO algorithm [26]. Fan and Jen proposed enhanced partial search PSO (EPS-PSO), which used the concept of collaborative multiswarm optimization. By designing a special cooperative search strategy, preventing particles from falling into the local optimal solution, and effectively locating the global optimal solution, the convergence and efficiency of PSO algorithm were improved [27], and a hybrid algorithm based on the Nelder Mead (NM) simplex search method and PSO was proposed in [28] for unconstrained optimization. The algorithm improved the performance of the standard PSO algorithm by combining hybrid strategies such that it can converge to the optimal solution faster and more accurately.In this study, an improved algorithm is proposed from the perspective of fully utilizing PSO historical data to build a traceable nonlinear search evolution strategy. First, a perturbation term for the negative gradient of the objective function is added to the velocity update formula. The term provides a clear direction (negative gradient is the direction of the fastest descent of the function value) when the particle is searching in the local neighborhood to avoid a completely random search, which can speed up the particle searching speed and enhance the optimization efficiency of the whole particle swarm. Second, using queues and binary trees to preserve the historical data obtained during the evolution process, a binary-tree depth-first search strategy is constructed. In this manner, when the particle swarm falls into the precocious region, it can return to the upper binary tree node using a retrospective method and select the other direction, thus escaping from the current premature region and continuing optimization. Simultaneously, when the binary tree is empty, a new solution vector system is constructed by queue, and the evolution continues until the binary tree and queue are empty simultaneously or the number of iterations reaches the preset maximum number of times, and the algorithm ends. It can be observed that the search evolutionary strategy proposed in this study is more flexible and diverse, and the existing common search strategy is only a special case, thus, the performance of this algorithm is better.The remainder of this paper is organized as follows: the original PSO algorithm is presented in Section2. In Section 3, the GB-PSO algorithm is proposed. The simulation results are presented in Section 4, and the conclusions are drawn in Section 5.


## 2. Particle Swarm Optimization

The swarm intelligence algorithm is a method generated by observing the activities of predation, migration, and other activities of animal groups. The PSO algorithm is a population-based intelligent algorithm proposed by Dr. Kennedy and Dr. Eberhart in 1995 [29]. Its principle is simple, iterative, and easy to implement with velocity and displacement formulas, memory function, fewer parameters to adjust, and great advantages in terms of optimization stability and global convergence.The description of the standard PSO algorithm is as follows: let the dimension of the search space beN. Then, the individual size of the particle group be M, the current position of the i-th particle is Xi=xi1,xi2,…,xiN, the current velocity is Vi=vi1,vi2,…,viN and current optimal position is Pi=pi1,pi2,…,piN. For the entire particle swarm, a global optimal solution Gt=gt1,gt2,…,gtN is found. In each iteration, the particle’s velocity and position update formula are as follows:(2)Xit+1=Xit+Vit+1,(3)Vit+1=ωVit+c1r1Pit−Xit+c2r2Gt−Xit,t=0,1,2,…,i=1,2,…,M,where w denotes the inertia weight, which is used to balance the global search and local search ability of the algorithm; c1 and c2 are individual cognitive factors and social cognitive factors, respectively; and r1 and r2 are random numbers in the range [0,1].


## 3. The Proposed Algorithm

The PSO has the advantages of simple model, fewer parameters, and easy implementation. However, in the process of optimizing some complex functions, it is easy to have a slow convergence speed, low optimization accuracy, and prematurity. The main reason is that particles usually move around the global and local optimum locations, however do not fully explore the entire search space. Considering the shortcomings of the standard PSO algorithm, we propose the following two improvements:


### 3.1. Gradient Perturbation

In this section, a perturbation algorithm based on the objective function negative gradient is proposed, which can enhance the optimization ability of each particle in the local neighborhood. It is well known that the gradient algorithm in the analytic domain is an efficient, simple, and easy-to-program optimization algorithm. The improved algorithm adds a negative gradient item to equation (2) to achieve the fastest descending direction of the objective function in each iteration of the particle, increasing the search targeting and accelerating the evolution. To a certain extent, the optimal value is within the neighborhood of the steepest descent direction of the objective function.(4)Xit+1=Xit+Vit+1+αi−∇XiF.The difference between equations (2) and (4) is shown in Figure 1:Figure 1
Differences between the two equations.It is clear that equation (4) contains information regarding the decline of function values, which assists particles to find optimal values. Considering that the objective function is not necessarily steerable in the search domain, we use the following approximate method to calculate its gradient.(5)∇XiF=∂F∂xi1∂F∂xi2…∂F∂xiN,∂F∂xij=Fxi1xi2xij+Δxij…xiN−FXiΔxij.The step sizeαi in equation (4) can be calculated using the Wolfes rule, that is αi satisfies the following inequalities [30]:(6)FXi+αidi≤FXi+σ1αigiTdi,gXi+αidiTdi≤σ2αigiTdi,where di=−gigi=∇XiF. σ1 and σ2 are given constants. However, this method requires a large amount of calculation and is time-consuming. To reduce the calculation and improve the efficiency, we propose a method in this study. First, the ratio is introduced as follows:(7)ϕi=FXi−FXi+αidiFXi−φXi+αidi,where φXi+αidi=FXi+giTαid. It is clear that the value of ϕi represents the similarity between functions FXi+αidi and φXi+αidi, and when αi⟶0, ϕi⟶1. In the process of iteratively calculating the value of αi, when ϕi≥c0 (c0 is a preset threshold), it shows that FXi+αidi is very similar to φXi+αidi, αi can be accepted, and the value of function FXi decreases along the direction of αidi (∵FXi−FXi+αidi>0); otherwise, the value of αi is reduced and the value of ϕi is recalculated until the above conditions are satisfied. The specific steps of the algorithm are as follows:Step 0. Given points Xk, gk and the constant 0<c0<1. Let dk=−gk.Step 1. Because FXi−φXi+αidi=αigi2>0, αi can be initialized to a large positive number, and then proceed Step 2.Step 2. If ϕi≥c0, the computation is stopped and output αi is obtained. Otherwise, let αi←c1αi0<c1<1 and loop with Step 2.


### 3.2. Binary Tree Depth-First Search Strategy

Standard PSO and many improved algorithms use linear search for global optimization. This search strategy is based on the optimal solution vector obtained by the current PSO to indicate the direction of the next evolution. Its advantages are that it is simple in form and easy to program, however it has two shortcomings: (1) when the optimal group solution tends to be locally optimal, under the action of equation (3), the particle group enters the neighborhood of the local optimal solution. Because this linear search is unidirectional, the entire particle swarm will converge to the local optimal solution even if it is searched for a long time in the neighborhood and lacks the ability to jump out of the precocious trap and perform global optimization. (2) In the entire process of particle swarm evolution, only the optimal solution of the current swarm is preserved, and not the information of various solutions in the process of evolution, which can be used to construct more diverse evolutionary strategies. This method of preserving the current global optimal solution information and using it to build the particle swarm evolution path is similar to that in [27]. Based on this, the data structure of the queue and the binary tree are adopted to save the current optimal, suboptimal, and norm maximum solutions, and define the corresponding operations to construct a traceable and multidirectional search strategy. The steps of the algorithm are as follows:Step 0: Random generation of initial solution vectorXi0,i=1,2,…,M for each particle in search space; initializing the optimal position vector Pi0, the velocity vector Vi0, and the current optimal solution vector G0, let Vi0=Pi0=Xi0, G0=argMinXFXi0, G˜0=argMinX≠G0FXi0 (i.e., G˜0 is a suboptimal vector); generate queue Qu, push group solution vector PSO0=Xi0Pi0Vi0 and suboptimal vector G˜0 into the queue; generate a binary tree BTree, set the data field of the root node to null, and use BTr0=PSO0g0 as the data field of the left child node, where g0=argMaxX∇XiF2 (that is, the value of function FX varies the most in the neighborhood centered on g, which is far from the premature zone), BTr0=PSO0G0 is the data field of the right child node, as shown in Figure 2:Step 1: Particle swarms evolved as follows:(1)
Each time the right side child direction depth search is preferred, the particle speed and position values are updated by the following formula:(8)Xit+1=Xit+Vit+1+αi−∇XiF,Vit+1=ωVit+c1r1Pit−Xit+c2r2Gt−Xit,t=0,1,2,…,i=1,2,…,M.If the particle swarm evolves successfully, that is,MinFXit+1<FGt, compute gt+1, Gt+1 and G˜t+1. Insert BTlt+1=PSOt+1gt+1 and BTrt+1=PSOt+1Gt+1 into the corresponding nodes of the binary tree (Figure 3(a)), and push Qt+1=PSOt+1G˜t+1 into the queue as shown in Figure 3(b).If the PSO is always evolutionary, the maximum number of iterations is calculated based on to the above method, and the optimal value is obtained. If there is no evolutionary situation, the algorithm proceedsStep 2.Step 2: When the particle swarm cannot evolve, proceed as follows:Considering the current solutionBTrt=PSOtGt as the framework, and equation (8) as an iterative formula, use the general evolutionary method, attempt to search forward several times, and then detect whether it evolves. If the particle swarm can evolve, continue to evolve forward, as shown in Figure 4(a). If the particle swarm is still unable to evolve, it can be considered that the particle swarm is trapped in the field of local optimal value, then the search direction is traced back to the upper binary tree node, and the left child node is considered as a new search starting point, take out its solution information: PSOtgt⟶Gt, and continue to evolve according to the method shown in Step 1, as shown in Figure 4(b). In the process of searching, if the particle swarm cannot evolve for a long time, it will exceed the root node of the binary tree after multiple backtracking (because in programming implementation, the stack is used to store the data of the binary tree node and to implement the above algorithm by pressing and popping operations, thus when this happens, the stack is empty), as shown in Figure 4(c). The solution vector system based on the optimal solution vector Gt does not continue to evolve. The algorithm proceeds to step 3, and the system is reconstructed with the suboptimal solution G˜t.Step 3: Consider the current element based on the direction of the queue head pointer, and move the pointer to the next element, as shown in Figure5.Figure 2
Initializing search binary tree.Figure 3
Updating binary tree and queue.
(a)(b)Figure 4
Back trackable binary tree depth-first search strategy.
(a)(b)(c)Figure 5
Remove team head elements and reconstruct solution system.Complete the following assignments:(9)PSOt⟶PSO0,G˜t⟶G0.The above steps are followed to search for the optimization again. WhenQu and BTree are empty or the number of iterations reaches a preset value, the algorithm completes and outputs the optimal solution obtained during the entire iteration process.From the above steps, linear search is only a special case of this algorithm, that is, the situation shown in Figure3(a). However, in actual calculations, particle swarms cannot always evolve, particularly when optimizing complex functions, and the entire particle swarm enters precocious areas at some stage of evolution, in which case, a linear search lacks the ability to jump out of precocious traps. By contrast, the proposed algorithm uses a variety of solution information to construct a traceable nonlinear search algorithm, thus having a more flexible search strategy and more powerful global optimization capabilities.


## 3.1. Gradient Perturbation

In this section, a perturbation algorithm based on the objective function negative gradient is proposed, which can enhance the optimization ability of each particle in the local neighborhood. It is well known that the gradient algorithm in the analytic domain is an efficient, simple, and easy-to-program optimization algorithm. The improved algorithm adds a negative gradient item to equation (2) to achieve the fastest descending direction of the objective function in each iteration of the particle, increasing the search targeting and accelerating the evolution. To a certain extent, the optimal value is within the neighborhood of the steepest descent direction of the objective function.(4)Xit+1=Xit+Vit+1+αi−∇XiF.The difference between equations (2) and (4) is shown in Figure 1:Figure 1
Differences between the two equations.It is clear that equation (4) contains information regarding the decline of function values, which assists particles to find optimal values. Considering that the objective function is not necessarily steerable in the search domain, we use the following approximate method to calculate its gradient.(5)∇XiF=∂F∂xi1∂F∂xi2…∂F∂xiN,∂F∂xij=Fxi1xi2xij+Δxij…xiN−FXiΔxij.The step sizeαi in equation (4) can be calculated using the Wolfes rule, that is αi satisfies the following inequalities [30]:(6)FXi+αidi≤FXi+σ1αigiTdi,gXi+αidiTdi≤σ2αigiTdi,where di=−gigi=∇XiF. σ1 and σ2 are given constants. However, this method requires a large amount of calculation and is time-consuming. To reduce the calculation and improve the efficiency, we propose a method in this study. First, the ratio is introduced as follows:(7)ϕi=FXi−FXi+αidiFXi−φXi+αidi,where φXi+αidi=FXi+giTαid. It is clear that the value of ϕi represents the similarity between functions FXi+αidi and φXi+αidi, and when αi⟶0, ϕi⟶1. In the process of iteratively calculating the value of αi, when ϕi≥c0 (c0 is a preset threshold), it shows that FXi+αidi is very similar to φXi+αidi, αi can be accepted, and the value of function FXi decreases along the direction of αidi (∵FXi−FXi+αidi>0); otherwise, the value of αi is reduced and the value of ϕi is recalculated until the above conditions are satisfied. The specific steps of the algorithm are as follows:Step 0. Given points Xk, gk and the constant 0<c0<1. Let dk=−gk.Step 1. Because FXi−φXi+αidi=αigi2>0, αi can be initialized to a large positive number, and then proceed Step 2.Step 2. If ϕi≥c0, the computation is stopped and output αi is obtained. Otherwise, let αi←c1αi0<c1<1 and loop with Step 2.


## 3.2. Binary Tree Depth-First Search Strategy

Standard PSO and many improved algorithms use linear search for global optimization. This search strategy is based on the optimal solution vector obtained by the current PSO to indicate the direction of the next evolution. Its advantages are that it is simple in form and easy to program, however it has two shortcomings: (1) when the optimal group solution tends to be locally optimal, under the action of equation (3), the particle group enters the neighborhood of the local optimal solution. Because this linear search is unidirectional, the entire particle swarm will converge to the local optimal solution even if it is searched for a long time in the neighborhood and lacks the ability to jump out of the precocious trap and perform global optimization. (2) In the entire process of particle swarm evolution, only the optimal solution of the current swarm is preserved, and not the information of various solutions in the process of evolution, which can be used to construct more diverse evolutionary strategies. This method of preserving the current global optimal solution information and using it to build the particle swarm evolution path is similar to that in [27]. Based on this, the data structure of the queue and the binary tree are adopted to save the current optimal, suboptimal, and norm maximum solutions, and define the corresponding operations to construct a traceable and multidirectional search strategy. The steps of the algorithm are as follows:Step 0: Random generation of initial solution vectorXi0,i=1,2,…,M for each particle in search space; initializing the optimal position vector Pi0, the velocity vector Vi0, and the current optimal solution vector G0, let Vi0=Pi0=Xi0, G0=argMinXFXi0, G˜0=argMinX≠G0FXi0 (i.e., G˜0 is a suboptimal vector); generate queue Qu, push group solution vector PSO0=Xi0Pi0Vi0 and suboptimal vector G˜0 into the queue; generate a binary tree BTree, set the data field of the root node to null, and use BTr0=PSO0g0 as the data field of the left child node, where g0=argMaxX∇XiF2 (that is, the value of function FX varies the most in the neighborhood centered on g, which is far from the premature zone), BTr0=PSO0G0 is the data field of the right child node, as shown in Figure 2:Step 1: Particle swarms evolved as follows:(1)
Each time the right side child direction depth search is preferred, the particle speed and position values are updated by the following formula:(8)Xit+1=Xit+Vit+1+αi−∇XiF,Vit+1=ωVit+c1r1Pit−Xit+c2r2Gt−Xit,t=0,1,2,…,i=1,2,…,M.If the particle swarm evolves successfully, that is,MinFXit+1<FGt, compute gt+1, Gt+1 and G˜t+1. Insert BTlt+1=PSOt+1gt+1 and BTrt+1=PSOt+1Gt+1 into the corresponding nodes of the binary tree (Figure 3(a)), and push Qt+1=PSOt+1G˜t+1 into the queue as shown in Figure 3(b).If the PSO is always evolutionary, the maximum number of iterations is calculated based on to the above method, and the optimal value is obtained. If there is no evolutionary situation, the algorithm proceedsStep 2.Step 2: When the particle swarm cannot evolve, proceed as follows:Considering the current solutionBTrt=PSOtGt as the framework, and equation (8) as an iterative formula, use the general evolutionary method, attempt to search forward several times, and then detect whether it evolves. If the particle swarm can evolve, continue to evolve forward, as shown in Figure 4(a). If the particle swarm is still unable to evolve, it can be considered that the particle swarm is trapped in the field of local optimal value, then the search direction is traced back to the upper binary tree node, and the left child node is considered as a new search starting point, take out its solution information: PSOtgt⟶Gt, and continue to evolve according to the method shown in Step 1, as shown in Figure 4(b). In the process of searching, if the particle swarm cannot evolve for a long time, it will exceed the root node of the binary tree after multiple backtracking (because in programming implementation, the stack is used to store the data of the binary tree node and to implement the above algorithm by pressing and popping operations, thus when this happens, the stack is empty), as shown in Figure 4(c). The solution vector system based on the optimal solution vector Gt does not continue to evolve. The algorithm proceeds to step 3, and the system is reconstructed with the suboptimal solution G˜t.Step 3: Consider the current element based on the direction of the queue head pointer, and move the pointer to the next element, as shown in Figure5.Figure 2
Initializing search binary tree.Figure 3
Updating binary tree and queue.
(a)(b)Figure 4
Back trackable binary tree depth-first search strategy.
(a)(b)(c)Figure 5
Remove team head elements and reconstruct solution system.Complete the following assignments:(9)PSOt⟶PSO0,G˜t⟶G0.The above steps are followed to search for the optimization again. WhenQu and BTree are empty or the number of iterations reaches a preset value, the algorithm completes and outputs the optimal solution obtained during the entire iteration process.From the above steps, linear search is only a special case of this algorithm, that is, the situation shown in Figure3(a). However, in actual calculations, particle swarms cannot always evolve, particularly when optimizing complex functions, and the entire particle swarm enters precocious areas at some stage of evolution, in which case, a linear search lacks the ability to jump out of precocious traps. By contrast, the proposed algorithm uses a variety of solution information to construct a traceable nonlinear search algorithm, thus having a more flexible search strategy and more powerful global optimization capabilities.


## 4. Simulation Results

To verify the performance of GB-PSO, 22 numerical functions, which are widely adopted in the performance comparison of global optimization algorithms (some test functions can be observed in [28]) were selected in this study, and the performance of the algorithm was reflected by solving their minimum values. The definitions of the benchmark functions and their detailed information are listed in Tables 1 and 2, respectively. Functions were divided into three groups based on their physical properties and shapes.Table 1
The benchmark functions used in the study.
NameFXSpheref1=∑i=1Nxi2Schwefel 2.22f2=∑i=1Nxi+∏i=1NxiSchwefel 1.2f3=∑i=1N∑j=1ixj2Schwefel 2.21f4=max|xi|,1⩽i⩽NEllipticf5=∑i=1N106i−1/N−1xi2Stepf6=∑i=1N⌊xi+0.5⌋2Noisef7=∑i=1Nixi4+random0,1Hyper ellipsoidf8=∑i=1N∑j=1ixj2Rastriginf9=∑i=1N−1xi2−10cos2πxi+10Ackleyf10=−20exp−0.21/N∑i=1Nxi2−exp1/N∑i=1Ncos2πxi+20+eGriewankf11=1/4000∑i=1Nxi2−∏i=1Ncosxi/i+1Schwefelf12=418.9829N−∑i=1NxisinxiShifted spheref13=∑i=1Nzi2−450Z=X−O,O=o1,o2…oNShifted schwefelf14=∑i=1N∑j=1izj2−450Z=X−O,O=o1,o2…oNShifted rosenbrockf15=∑i=1N−1100zi+1−zi22+zi−12+390Z=X−O+1,O=o1,o2…oNShifted rastriginf16=10N+∑i=1Nzi2−10cos2πzi−330Z=X−O,O=o1,o2…oNShifted ackleyf17=−aexp−b1/N∑i=1Nzi2−exp1/N∑i=1Ncosczi+a+e−140,a=20,b=0.2,c=2π,Z=X−OShifted griewankf18=1/4000∑i=1Nzi2−∏i=1Ncoszi/i+1−180Z=X−O,O=o1,o2…oNRotated rosenbrockf19=∑i=1N−1100zi+1−zi22+zi−12−900Z=M2.048/100X−O+1,O=o1,o2…oNMis an orthogonal matrixShifted rotated ellipticf20=∑i=1N106i−1/N−1zi2−450,Z=MX−OShifted rotated rastriginf21=10N+∑i=1Nzi2−10cos2πziZ=MX−OShifted rotated griewankf22=1/4000∑i=1Nzi2−∏i=1Ncoszi/i+1−180Z=MX−OTable 2
Detailed information of test functions modal.
ModalFXSearch spaceOptXMinAccepted valueUnimodalf1−100,100N0.0N0.010−6f2−10,10N0.0N0.010−8f3−100,100N0.0N0.010−6f4−100,100N0.0N0.010−6f5−100,100N0.0N0.010−8f6−100,100N−0.5⩽xi⩽0.50.010−8f7−1.28,1.28N0.0N0.010−2f8−100,100N0.0N0.010−8Multimodalf9−5.12,5.12N0.0N0.010−8f10−32,32N0.0N0.010−8f11−600,600N0.0N0.010−8f12−500,500N420.9687N0.02×103Rotated and shiftedf13−100,100NO−450−350f14−100,100NO−450−350f15−100,100NO390490f16−5,5NO−330−230f17−32,32NO−140−135f18−600,600NO−180−170f19−100,100NO−900−800f20−100,100NO−450−350f21−5,5NO0.05.0f22−600,600NO−180−100The first group contains eight unimodal benchmark functions. From their mathematical properties and geometric distribution, these functions are single-mode, that is, there is only one global optimal value and the optimal solution is the center of the search interval. Therefore, the convergence rate of the search algorithm is important in determining global optimum, while the second group includes 11 multi modal benchmark functions. The characteristic of these functions is that the number of local minimums increases with an increase in the dimension of the variable, which makes it easy for the algorithm to fall into the premature zone when searching for the global optimal solution, and makes it more difficult for the algorithm to converge to the global optimal value, while the rest are rotated and shifted functions. For shifted functions, the global optimal vector is no longer the center of the search interval, but shifted to the position vectorO=o1,o2…oN. In the simulation experiment, O is randomly generated within the range of the search interval, that is, each component satisfied: oi∈xminxmax. Rotating the function did not change the shape, however it increased the difficulty of the algorithm in identifying it. The rotation matrix M was randomly generated, each element satisfied the standard normally distributed, and was then orthogonalized by the Gram-Schmidt method.In the experiment, the initialization of all parameters is randomly generated based on its logical meaning, all experiments were performed in a Windows XP Professional environment using an Intel Core Dual Core system with 2.11 GHz and 2.0 GB RAM, and the codes were implemented in C compiled Language.


### 4.1. Testing Performance of the Proposed Algorithm

In this subsection, we verify the effectiveness of the proposed GB-PSO algorithm. The maximum number of iteration was set to 1500 for all functions, and the particle number was considered as 120 with 20-dimension. Each experiment was independently repeated 50 times for every function. The mean of the best values and the best standard deviations of the 22 benchmark functions obtained by the GB-PSO algorithm are shown in Table3. Because of the limited space, we can only list the variation curve of the optimal value of some functions in Figure 6.Table 3
Performance of the GB-PSO algorithm.
FXIterationMeanStandard deviationsBest value of 50 simulationf1803.4227E −496.7053E −491.4004E −50f22006.3650E −484.3692E −477.7993E −49f32002.2398E −392.8080E −395.4812E −40f42004.5270E −227.8410E −221.3581E −28f52001.2286E −171.7176E −173.1967E −19f61000.00.00.0f71200.00.00.0f84001.0666E −251.8447E −258.9995E −29f91406.5074E −385.1779E −387.5266E −39f1010003.0018E −153.9191E −155.8872E −16f113506.2598E −485.5918E −481.0000E −50f122000.0102450.0091010.000112f13700−427.201520.5264−449.868f14150−445.2455.094−449.999f15100396.2553.3955392.417f161000−324.2934.971−329.999f17100−135.6614.509−139.995f18100−177.6192.056−179.931f191200−895.0834.041−898.750f201200−444.73614.571−448.402f2115005.1086E −107.9533E −101.4282E −11f221200−177.6422.0817−179.975Figure 6
The variation curve of the best function value in 50 simulations. (a)f1, (b) f2, (c) f9, (d) f10, (e) f21, and (f) f22.
(a)(b)(c)(d)(e)(f)These results indicate that the GB-PSO algorithm is effective. The algorithm is divided into three stages. As an example, the functionf5 variation curve is shown in Figure 7. In the first stage, the two curves coincide highly, which shows that the algorithm converges quickly and the PSO approaches the global optimum quickly. In the second stage, the particle swarm is trapped in the premature region, which further shows that the negative-gradient deflection term has played its due role. Because the algorithm adopts the binary tree depth-first search strategy, the optimal value of the current particle swarm is promoted to a high frequency and large jump. This transition eventually causes the particle swarm to escape from the region, continue to evolve, and become further closer to the global optimal value. In the third stage, because the particle swarm is already close to the global optimal value, although the particle swarm still attempts to evolve further, it fails, and the algorithm converges to its ultimate optimal value. After several experiments, the performance of the algorithm was observed to be related to the parameter values. The convergence performance of the algorithm is different under different values; therefore, we will study the parameter selection strategy to further improve the performance of the algorithm.Figure 7
Three-stage sketch of particle swarm evolution under GB-PSO.


### 4.2. Comparison of GB-PSO with Other Algorithms

In this simulation, to further test and verify the performance of the GB-PSO algorithm, we compared it with four state-of-the-art PSO algorithm: the novel self-adaptive PSO algorithm (SAPSO) [20], the hybrid particle swarm optimizer with sine cosine acceleration coefficients (H-PSO-SCAC) [31], the improved global-best-guided particle swarm optimization with learning operation (IGPSO) [32] and the competitive mechanism based multiobjective PSO (CMOPSO) [33]. For all test algorithms, the maximum number of iterations was set to 2000 for all functions with 30-dimension, the particle number was considered as 120, and each experiment was independently repeated 20 times for every function. The results are listed in Table 4, and Figure 8 shows the convergence graphs in terms of the best mean fitness value of each algorithm for the benchmark function.Table 4
Mean and standard deviations of the function values.
FXCriteriaCMOPSOSAPSOH-PSO-SCACIGPSOGB-PSOf1Mean2.90E −102.92E −081.13E −206.42E −112.01E −31S.D.4.24E −091.96E −105.23E −221.45E −104.47E −31f2Mean4.68E −112.21E −101.29E −092.23E −194.20E −33S.D.2.09E −114.37E −105.34E −084.34E −195.31E −33f3Mean1.51E −203.66E −083.59E −131.18E −151.06E −34S.D.8.83E −196.10E −077.74E −133.61E −134.46E −34f4Mean3.65E −076.96E −086.08E −091.08E −061.21E −21S.D.7.28E −078.72E −084.31E −081.16E −064.44E −20f5Mean3.68E −072.52E −31.79E −023.19E −082.68E −12S.D.7.23E −074.51E −33.87E −025.46E −085.58E −11f6Mean2.13E −131.22E −092.19E −063.16E −134.34E −26S.D.4.66E −132.28E −084.68E −067.08E −139.21E −26f7Mean1.66E −093.71E −184.35E −167.31E −163.06E −30S.D.2.12E −096.87E −185.38E −161.11E −155.45E −30f8Mean1.38E −195.46E −143.23E −137.49E −102.19E −17S.D.2.27E −191.13E −138.08E −125.82E −104.91E −17f9Mean4.56E −126.75E −148.14E −117.49E −124.89E −29S.D.6.96E −113.95E −147.89E −108.98E −128.92E −28f10Mean2.95E −105.13E −043.59E −063.34E −097.72E −10S.D.7.92E −107.96E −046.69E −057.48E −098.18E −09f11Mean2.97E −061.86E −203.59E −121.33E −155.01E −30S.D.7.66E −056.83E −208.19E −118.78E −158.92E −30f12Mean0.14350.02730.04890.55700.0032S.D.0.07180.01180.00230.76580.0013f13Mean−426.9618−436.7843−416.1015−377.6605−427.0233S.D.2.34437.866812.393.264918.7899f14Mean−389.23−401.67−389.67−421.89−430.23S.D.10.3423.3430.3430.129.15f15Mean407.6742407.1695406.4978406.3855396.4175S.D.12.3423.895.8414.566.89f16Mean−256.34−306.45−297.45−245.49−319.91S.D.4.785.7812.2316.217.89f17Mean−136.12−136.89−130.51−129.45−134.89S.D.5.1212.129.1911.916.51f18Mean−171.34−169.77−173.88−174.12−175.23S.D.5.8610.236.445.233.81f19Mean−801.34−821.22−802.41−825.21−880.78S.D.12.729.1212.248.126.12f20Mean−371.09−367.91−381.33−389.11−409.78S.D.13.5614.3412.9910.2112.33f21Mean2.91E −026.15E −031.235.48E −043.31E −07S.D.0.455.15E −023.115.98E −037.32E −06f22Mean−125.78−142.99−126.44−144.89−165.98S.D.12.778.3312.3612.635.99Mean: mean of objective values; S.D: standard deviation.Figure 8
The variation curve of the best mean fitness value. (a)f3, (b) f4, (c) f11, (d) f12, (e) f13, and (f) f15.
(a)(b)(c)(d)(e)(f)From the results in Table4, for the eight unimodal functions, except for f8, the proposed GB-PSO algorithm performs better than the SAPSO, H-PSO-SCAC, IGPSO, and CMOPSO algorithms on function f8. The CMOPSO exhibited the best performance. However, in its entirety, the proposed GB-PSO exhibits strong computational power, and its optimization results are very close to the theoretical global optimum; for four multi modal functions, the GB-PSO algorithm performs best and achieves the global optimal solutions or is close to the global optimal solution on two functions (f9 and f11). However, on two multi modal functions (f10 and f12), the proposed algorithm could not determine the global optimal values because the choice of parameters would greatly affect its performance, as described above; for 10 rotated and shifted functions, because of the complexity of these functions, not all the algorithms can determine the global optimal value. These values were within the acceptable range. Comparatively speaking, the GB-PSO algorithm is better than other algorithms in 10 test functions except for f13 and f17. From the simulation results, this performance difference is evident.Figures8(a)–8(f) show the convergence curves obtained by the five algorithms for six functions (f3, f4, f11, f12, f13, and f15). Figure 8(a) clearly shows that GB-PSO has faster convergence speed and more powerful optimization ability than that in the other four methods, although it falls into local optimum during evolution, however after less iteration calculation, the particle swarm can finally escape from the local optimum and converge to a higher precision solution. From figure 8(b), it can be observed that GB-PSO has the best performance for this benchmark function. Figure 8(c) shows that the GB-PSO algorithm surpasses all other approaches, and the algorithm identified the global optimal solution for approximately 10−30. Figure 8(d) shows that the GB-PSO algorithm shows the fastest convergence speed initially. From figure 8(e), in terms of search accuracy, the GB-PSO algorithm is slightly inferior to SAPSO however it is stronger in terms of algorithm stability. Figure 8(f) illustrates the values achieved for the four algorithms when optimization f15 and the figure shows that GB-PSO owns strong convergence speed and stability than SAPSO, H-PSO-SCAC, IGPSO, and CMOPSO.In summary, as shown in Table4 and Figure 8, the GB-PSO algorithm achieves a better search performance and a stronger ability to escape from local optimum solutions than SAPSO, H-PSO-SCAC, IGPSO, and CMOPSO. Thus, the GB-PSO method is highly efficient for solving numerical optimization problems.


## 4.1. Testing Performance of the Proposed Algorithm

In this subsection, we verify the effectiveness of the proposed GB-PSO algorithm. The maximum number of iteration was set to 1500 for all functions, and the particle number was considered as 120 with 20-dimension. Each experiment was independently repeated 50 times for every function. The mean of the best values and the best standard deviations of the 22 benchmark functions obtained by the GB-PSO algorithm are shown in Table3. Because of the limited space, we can only list the variation curve of the optimal value of some functions in Figure 6.Table 3
Performance of the GB-PSO algorithm.
FXIterationMeanStandard deviationsBest value of 50 simulationf1803.4227E −496.7053E −491.4004E −50f22006.3650E −484.3692E −477.7993E −49f32002.2398E −392.8080E −395.4812E −40f42004.5270E −227.8410E −221.3581E −28f52001.2286E −171.7176E −173.1967E −19f61000.00.00.0f71200.00.00.0f84001.0666E −251.8447E −258.9995E −29f91406.5074E −385.1779E −387.5266E −39f1010003.0018E −153.9191E −155.8872E −16f113506.2598E −485.5918E −481.0000E −50f122000.0102450.0091010.000112f13700−427.201520.5264−449.868f14150−445.2455.094−449.999f15100396.2553.3955392.417f161000−324.2934.971−329.999f17100−135.6614.509−139.995f18100−177.6192.056−179.931f191200−895.0834.041−898.750f201200−444.73614.571−448.402f2115005.1086E −107.9533E −101.4282E −11f221200−177.6422.0817−179.975Figure 6
The variation curve of the best function value in 50 simulations. (a)f1, (b) f2, (c) f9, (d) f10, (e) f21, and (f) f22.
(a)(b)(c)(d)(e)(f)These results indicate that the GB-PSO algorithm is effective. The algorithm is divided into three stages. As an example, the functionf5 variation curve is shown in Figure 7. In the first stage, the two curves coincide highly, which shows that the algorithm converges quickly and the PSO approaches the global optimum quickly. In the second stage, the particle swarm is trapped in the premature region, which further shows that the negative-gradient deflection term has played its due role. Because the algorithm adopts the binary tree depth-first search strategy, the optimal value of the current particle swarm is promoted to a high frequency and large jump. This transition eventually causes the particle swarm to escape from the region, continue to evolve, and become further closer to the global optimal value. In the third stage, because the particle swarm is already close to the global optimal value, although the particle swarm still attempts to evolve further, it fails, and the algorithm converges to its ultimate optimal value. After several experiments, the performance of the algorithm was observed to be related to the parameter values. The convergence performance of the algorithm is different under different values; therefore, we will study the parameter selection strategy to further improve the performance of the algorithm.Figure 7
Three-stage sketch of particle swarm evolution under GB-PSO.


## 4.2. Comparison of GB-PSO with Other Algorithms

In this simulation, to further test and verify the performance of the GB-PSO algorithm, we compared it with four state-of-the-art PSO algorithm: the novel self-adaptive PSO algorithm (SAPSO) [20], the hybrid particle swarm optimizer with sine cosine acceleration coefficients (H-PSO-SCAC) [31], the improved global-best-guided particle swarm optimization with learning operation (IGPSO) [32] and the competitive mechanism based multiobjective PSO (CMOPSO) [33]. For all test algorithms, the maximum number of iterations was set to 2000 for all functions with 30-dimension, the particle number was considered as 120, and each experiment was independently repeated 20 times for every function. The results are listed in Table 4, and Figure 8 shows the convergence graphs in terms of the best mean fitness value of each algorithm for the benchmark function.Table 4
Mean and standard deviations of the function values.
FXCriteriaCMOPSOSAPSOH-PSO-SCACIGPSOGB-PSOf1Mean2.90E −102.92E −081.13E −206.42E −112.01E −31S.D.4.24E −091.96E −105.23E −221.45E −104.47E −31f2Mean4.68E −112.21E −101.29E −092.23E −194.20E −33S.D.2.09E −114.37E −105.34E −084.34E −195.31E −33f3Mean1.51E −203.66E −083.59E −131.18E −151.06E −34S.D.8.83E −196.10E −077.74E −133.61E −134.46E −34f4Mean3.65E −076.96E −086.08E −091.08E −061.21E −21S.D.7.28E −078.72E −084.31E −081.16E −064.44E −20f5Mean3.68E −072.52E −31.79E −023.19E −082.68E −12S.D.7.23E −074.51E −33.87E −025.46E −085.58E −11f6Mean2.13E −131.22E −092.19E −063.16E −134.34E −26S.D.4.66E −132.28E −084.68E −067.08E −139.21E −26f7Mean1.66E −093.71E −184.35E −167.31E −163.06E −30S.D.2.12E −096.87E −185.38E −161.11E −155.45E −30f8Mean1.38E −195.46E −143.23E −137.49E −102.19E −17S.D.2.27E −191.13E −138.08E −125.82E −104.91E −17f9Mean4.56E −126.75E −148.14E −117.49E −124.89E −29S.D.6.96E −113.95E −147.89E −108.98E −128.92E −28f10Mean2.95E −105.13E −043.59E −063.34E −097.72E −10S.D.7.92E −107.96E −046.69E −057.48E −098.18E −09f11Mean2.97E −061.86E −203.59E −121.33E −155.01E −30S.D.7.66E −056.83E −208.19E −118.78E −158.92E −30f12Mean0.14350.02730.04890.55700.0032S.D.0.07180.01180.00230.76580.0013f13Mean−426.9618−436.7843−416.1015−377.6605−427.0233S.D.2.34437.866812.393.264918.7899f14Mean−389.23−401.67−389.67−421.89−430.23S.D.10.3423.3430.3430.129.15f15Mean407.6742407.1695406.4978406.3855396.4175S.D.12.3423.895.8414.566.89f16Mean−256.34−306.45−297.45−245.49−319.91S.D.4.785.7812.2316.217.89f17Mean−136.12−136.89−130.51−129.45−134.89S.D.5.1212.129.1911.916.51f18Mean−171.34−169.77−173.88−174.12−175.23S.D.5.8610.236.445.233.81f19Mean−801.34−821.22−802.41−825.21−880.78S.D.12.729.1212.248.126.12f20Mean−371.09−367.91−381.33−389.11−409.78S.D.13.5614.3412.9910.2112.33f21Mean2.91E −026.15E −031.235.48E −043.31E −07S.D.0.455.15E −023.115.98E −037.32E −06f22Mean−125.78−142.99−126.44−144.89−165.98S.D.12.778.3312.3612.635.99Mean: mean of objective values; S.D: standard deviation.Figure 8
The variation curve of the best mean fitness value. (a)f3, (b) f4, (c) f11, (d) f12, (e) f13, and (f) f15.
(a)(b)(c)(d)(e)(f)From the results in Table4, for the eight unimodal functions, except for f8, the proposed GB-PSO algorithm performs better than the SAPSO, H-PSO-SCAC, IGPSO, and CMOPSO algorithms on function f8. The CMOPSO exhibited the best performance. However, in its entirety, the proposed GB-PSO exhibits strong computational power, and its optimization results are very close to the theoretical global optimum; for four multi modal functions, the GB-PSO algorithm performs best and achieves the global optimal solutions or is close to the global optimal solution on two functions (f9 and f11). However, on two multi modal functions (f10 and f12), the proposed algorithm could not determine the global optimal values because the choice of parameters would greatly affect its performance, as described above; for 10 rotated and shifted functions, because of the complexity of these functions, not all the algorithms can determine the global optimal value. These values were within the acceptable range. Comparatively speaking, the GB-PSO algorithm is better than other algorithms in 10 test functions except for f13 and f17. From the simulation results, this performance difference is evident.Figures8(a)–8(f) show the convergence curves obtained by the five algorithms for six functions (f3, f4, f11, f12, f13, and f15). Figure 8(a) clearly shows that GB-PSO has faster convergence speed and more powerful optimization ability than that in the other four methods, although it falls into local optimum during evolution, however after less iteration calculation, the particle swarm can finally escape from the local optimum and converge to a higher precision solution. From figure 8(b), it can be observed that GB-PSO has the best performance for this benchmark function. Figure 8(c) shows that the GB-PSO algorithm surpasses all other approaches, and the algorithm identified the global optimal solution for approximately 10−30. Figure 8(d) shows that the GB-PSO algorithm shows the fastest convergence speed initially. From figure 8(e), in terms of search accuracy, the GB-PSO algorithm is slightly inferior to SAPSO however it is stronger in terms of algorithm stability. Figure 8(f) illustrates the values achieved for the four algorithms when optimization f15 and the figure shows that GB-PSO owns strong convergence speed and stability than SAPSO, H-PSO-SCAC, IGPSO, and CMOPSO.In summary, as shown in Table4 and Figure 8, the GB-PSO algorithm achieves a better search performance and a stronger ability to escape from local optimum solutions than SAPSO, H-PSO-SCAC, IGPSO, and CMOPSO. Thus, the GB-PSO method is highly efficient for solving numerical optimization problems.


## 5. Conclusions

The GB-PSO algorithm was proposed to enhance the search performance of the PSO algorithm and obtain a good global optimal solution. PSO is combined with a gradient descent algorithm and binary tree depth-first search strategy. First, the negative gradient perturbation term is introduced into the particles velocity and position update formulas. On the microlevel, the deflection term can enhance the local optimization ability of each particle, thus accelerating the optimization speed of the particle swarm as a whole. On the other hand, based on the binary tree depth-first search strategy, it can fully use the various solution information in the optimization process to construct a multidirectional and retrospective optimization mechanism to avoid the premature shortcomings of single-directional optimization. This increases the global optimization ability of the algorithm and improves the calculation accuracy.



---

*Source: 6599899-2022-11-30.xml*