# Improved Quantum-Behaved Particle Swarm Algorithm Based on Levy Flight

Authors: Song Zheng; Xinwei Zhou; Xiaoqing Zheng; Ming Ge
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

To improve convergence speed and search accuracy, this paper proposes an improved quantum-behaved particle swarm optimization algorithm based on Levy flight. The improved algorithm reduces the probability of a local optimal solution through Levy flight and enhances the accuracy of the later search through a postsearch strategy. During the search process, the probability of quantum behavior is retained and the directivity of the particles is strengthened. According to the simulation comparison results, the improved quantum-behaved particle swarm algorithm exhibits faster convergence speed and higher accuracy.


---

## Body

## 1. Introduction

Particle swarm optimization is a swarm intelligence optimization algorithm that was proposed in 1995. This algorithm simulates the foraging behavior of some animal populations and is used to solve complex optimization problems. The basic particle swarm algorithm has the advantages of fast convergence and an accurate solution; however, it can easily succumb to the dilemma of local optimization. At the same time, it has been proven that PSO is not a globally convergent intelligent swarm algorithm [1].In 2004, Sun proposed a quantum behavior particle swarm algorithm by combining quantum behavior with PSO [2, 3]. Quantum-behaved particle swarm optimization (QPSO) has a simpler model, fewer control parameters, better convergence speed, and better global search capabilities. However, when QPSO addresses complex multidimensional optimization problems, it can also succumb to the problem of converging too quickly and falling into a local optimum [4]. Dong Yumin proposed a hybrid quantum-behaved particle swarm optimization algorithm [5] combining the artificial fish swarm algorithm (AFSA) [6] and QPSO to improve the QPSO. Gai-Ge Wang proposed an algorithm based on the krill herd (KH) algorithm [7] and QPSO [8]. Regarding the expansion-contraction factor, Sun proposed three methods in 2011 to improve QPSO [9]. ShuJiang Li proposed an improvement to the expansion-contraction factor [10]. Jing Zhao proposed a new search strategy that enabled particles to have a certain probability to remain unchanged or have a certain probability to initialize [11]. Dianbo Su updated the position of the worst particle in the swarm through a cross-method [12]. Yukun Wang also proposed a new hybrid quantum-behaved particle swarm algorithm by combining Levy flight and QPSO [13]. Luo [14] solved the constraints problem via a quantum-behaved particle swarm algorithm based on Lagrange multipliers [15]. In conclusion, increasing optimization algorithms have been proposed, such as whale optimization algorithms, flower pollination algorithms, binary spider monkey optimization algorithms, firefly algorithms, and spider monkey optimization algorithms [16–21].It can be found that QPSO, similar to many swarm intelligence optimization algorithms, is prone to falling into a local optimum. To improve the convergence speed and search accuracy, a new search strategy is proposed that combines the advantages of quantum mechanics and traditional mechanics. In the search process, the probability of quantum behavior is retained, and the directivity of the particles is strengthened so that the search is performed in a random and objective coexistence manner, which makes the convergence faster and the accuracy of the solution higher.


## 2. QPSO

The PSO algorithm obtains the optimal value through multiple iterations by introducing concepts such as speed and location. The formula is as follows:(1)vit+1=wvit+c1r1pbesti−xit+c2r2gbest−xit,xit+1=xit+vit+1,where v is the velocity of the particle and x is the position of the particle. pbesti are the optimal positions of particle i. gbest is the optimal position of the whole particle. w is an inertia parameter that can control the dynamics of flight, and c1 and c2 are often called the learning parameters. r1 and r2 represent random numbers from 0 to 1 that satisfy a uniform distribution.The QPSO algorithm is based on the PSO algorithm. The QPSO algorithm is proposed through the quantum model of particles. In quantum space, the speed and position of a particle cannot be accurately determined, and its position must be determined by a wave function. By using the Monte Carlo stochastic simulation method, the position of the particle can be measured. The formula is as follows:(2)xi,jt+1=pi,jt±αcjt−xi,jt×ln1ui,jt,pi,jt=βpbesti,j+1−βgbestj,where ui,jt and β represent random numbers from 0 to 1 that satisfy uniform distribution. gbestj is the jth dimension of the optimal position of the whole particle. pbesti,j is the jth dimension of the optimal position of particle i. α is the expansion-contraction factor, which is the only parameter of QPSO. Currently, the most commonly used method is to linearly reduce the value of α from 0.9 to 0.4. cjt is the average value of the optimal positions of all particles in the current iteration.By comparing PSO and QPSO, it can be found that QPSO only needs to adjust one parameter, which is easy to control. In addition, QPSO can converge to the global optimum with a probability of 1, and the optimization effect is better. The speed and position model is used in PSO, so a single particle can only find optimization in a limited space. However, QPSO uses a quantum model in which particles do not have a certain position and speed. All particles can appear anywhere in the search space, and the optimization effect is better. However, QPSO is prone to falling into a local optimum.


## 3. Improved QPSO Based on Levy Flight

In QPSO, the position of theith particle can be obtained as follows:(3)xi,1,xi,2,…,xi,d=pi+α±cj−xi,1×ln1ui,1,±cj−xi,2×ln1ui,2,…,±cj−xi,d×ln1ui,d,pi=βpbesti+1−βgbest,where d is the dimension of the particle i. By analyzing formula (3) of traditional physics, it can be found that the position of particle i is obtained by adding cj−xi,1×ln1/ui,1,cj−xi,2×ln1/ui,2,…,cj−xi,d×ln1/ui,d to pi. In other words, the position of particle i is obtained by adding pi to a direction vector. Although the randomness of the direction vector enables the optimization range of the particles in the entire feasible region, the randomness of the direction vector may affect the convergence speed. Therefore, to strengthen the directivity and purpose of the direction vector, two new strategies are proposed, as follows: (4)xi,jt+1=pi,jt±αcjt−xi,jt×ln1uit,xi,jt+1=pi,jt±αgbestj−xi,jt×ln1uit.uit represent random numbers from 0 to 1 that satisfy uniform distribution. Moreover, uit is the same in all dimensions of particle i. These two search strategies have clear directivity and fast convergence. However, fast convergence may fall into a local optimum. Therefore, we need to improve on this basis. Throughout the development of human society, it can be found that some people move in the best direction, some move toward the general trend, others rely on their own experience, and still others stand still. Therefore, a search strategy based on the development trend of human society is proposed. It is called strategy a, as follows:If 0 < q < q1, then(5)xi,jt+1=pi,jt±αcjt−xi,jt×ln1uit.Ifq1 < q < q2, then(6)xi,jt+1=pi,jt±αgbestj−xi,jt×ln1uit.Ifq2 < q < q3, then(7)xi,jt+1=xi,jt.Ifq3 < q < 1, then(8)xi,jt+1=xi,jt+γ×levy,where levy is a random number based on thelevy distribution and γ, q1, q2, and q3 are the parameters. q represents random numbers from 0 to 1 that satisfy a uniform distribution. The above strategy can increase the diversity of the previous solution and reduce the probability of falling into a local optimum to a certain extent. To further improve the accuracy of the solution, a postsearch strategy is proposed in the postsearch period. levy is calculated by the following equation:(9)levy=uv1/β,u∼N0,σ2,v∼N0,1,where β=1.5 and σ is a function of β.In the postsearch period, it is more desirable that the particles search in a small range near gbest. Strategyb is as follows:(10)xit+1=gbest,xi,nnt+1=xi,nnt+1+δ×levy,where nn is a random dimension in the d dimension of the i particle and δ is a parameter. When the value of δ×levy is small, the search accuracy can be increased. When the value of δ×levy is large, it can participate in the global search again. The concept of crossover can further improve the search accuracy. Strategy c is as follows: (11)xit+1=gbest,a=xi,nt+1,xi,nt+1=xi,mt+1,xi,mt+1=a,where n and m are two random dimensions in the d dimension of the i particle. Adopting strategies a and b can not only ensure that particles are optimized near the global best but also ensure that the particles do not overlap with the global best. In the implementation of the algorithm, for the particles that exceed the limit in the iteration, the following strategy d is used (assuming that the jth dimension of the i particle exceeds the limit). The strategy d is as follows:Ifxi,j<xmin and xi,j>xmax, execute formula (11). Also,(12)xi,j=gbestj+xi,j−gbestj1+rand.Here,rand represents random numbers from 0 to 1 that satisfy uniform distribution.The detailed description of the improved QPSO for solving optimization problems can be given as follows:(i)
Step 1: initialize the population according to the set number of particles and dimensions, set the maximum number of iterations, and set various parameters.(ii)
Step 2: evaluate all particles to find the individual best of each particle and the global best of all particles. Calculate the average value of the optimal positions of all particles in the current iteration.(iii)
Step 3: determine whether the current number of iterations is less than half the maximum number of iterations. If true, execute strategya to update the particles and skip to step 5. If false, execute strategy a to update the particles with a probability of μ, then skip to step 5, and perform step 4 with a probability of 1−μ.(iv)
Step 4: execute strategyb to update the particles with a probability of σ or execute strategy c to update the particles with a probability of 1−σ.(v)
Step 5: determine whether the particle is within the limited range, and if it is out of range, use strategyd to update the particle.(vi)
Step 6: evaluate all particles to determine and update the individual best of each particle and the global best of all particles. Calculate and update the average value of the optimal positions of all particles in the current iteration.(vii)
Step 7: if the maximum number of iterations is reached, the optimal solution is output. Otherwise, proceed to step 3.The description of the improved QPSO can is shown in Figure1.Figure 1
Flowchart of the improved quantum particle.Computational complexity is an important factor in the optimization algorithm. The complexity is generallyOn, On2, Ologn, Onlogn, O1, and Omn, representing an algorithm, the incremental relationship between the occupied time and data, where n represents the amount of data input. In the optimization algorithm, the input parameters are the number of particles (value n) and the number of iterations (value m). The computational complexity of the improved quantum-behaved particle swarm optimization algorithm is Onm, and the computational complexity of PSO and QPSO is Onm.


## 4. Simulation Results

To better compare the improved quantum-behaved particle swarm optimization algorithm, the quantum-behaved particle swarm optimization algorithm, and the particle swarm optimization algorithm, fifteen test functions are used for simulation comparison. The simulation compares the three algorithms by analyzing the accuracy of the solution and the speed of convergence. Fifteen test functions are shown in Table1.Table 1
Fifteen test functions.
NameMathematical formulaRangesBooth functionf1x=x1+2x2−72+2x1+x2−52x∈−10,10Holder table functionf2=−sinx1cosx2e1−x12+x22/πx∈−10,10Drop-wave functionf3x=−1+cos12x12+x22/0.5x12+x22+2x∈−5.12,5.12Shubert functionf4x=∑i=15icosi+1x1+i×∑i=15icosi+1x2+ix∈−10,10Cross-in-tray functionf5x=−0.0001sinx1sinx2e100−x12+x22/π+10.1x∈−10,10Schaffer function N.2f6x=0.5+sinx12−x222−0.5/1+0.001x12+x222x∈−100,100Levy function N.13f7x=sin3πx12+x1−121+sin3πx22+x2−121+sin2πx22x∈−10,10Matyas functionf8x=0.26x12+x22−0.48x1x2x∈−10,10Levy functionf9x=sinπw12+∑i=1d−1wi−121+10sinπwi+12+wd−121+sin2πwd2x∈−10,10Griewank functionf10x=∑i=1dxi2/4000−∏i=1dcosxi/i+1x∈−600,600Ackley functionf11x=−aexp−b1/d∑i=1dxi2−exp1/d∑i=1dcoscxi+a+ex∈−32.768,32.768Rastrigin functionf12x=10d+∑i=1dxi2−10cos2πxix∈−5.12,5.12Rotated hyperellipsoidf13x=∑i=1d∑j=1ixj2x∈−65.536,65.536Sum of different powersf14x=∑i=1dxii+1x∈−1,1Rosenbrockf15x=∑i=1d−1100xi+1−xi22+xi−12x∈−5,10The optimal values of the functions are 0, −19.2085, −1, −186.7309, −2.0626, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0.The improved quantum-behaved particle swarm algorithm is temporarily called G-QPSO. In G-QPSO,μ and σ are taken as 0.5; q1,q2, and q3 are taken as 0.5, 0.8, and 0.9; and α is linearly reduced from 1 to 0.5. In QPSO, α is linearly reduced from 1 to 0.5. In PSO, w is linearly reduced from 1.5 to 0.5, and c1 and c2 are taken as 2. The following data are the average of 100 tests.The first eight functions have only two variables, so the accuracy of the solution is analyzed by changing the number of particles with 100 iterations. Through analyzing Table2, it can be found that G-QPSO is better than QPSO and PSO on the average, maximum, and minimum values of the solution, proving that G-QPSO is better than QPSO and PSO in terms of the accuracy of the two-dimensional test function solution. For example, for function f1, when the number of particles is 20, the mean, worst, and best values of QPSO are 0.0042, 0.0715, and 2.45E-06; the mean, worst, and best values of G-QPSO are 4.31E−05, 1.30E−03, and 2.15E−08, respectively; and the mean, worst, and best values of PSO are 0.0014, 0.0182, and 1.10E−05, respectively.Table 2
Test function optimization results.
Number of particlesFunctionQPSOG-QPSOPSOMean valuesWorst valuesBest valuesMean valuesWorst valuesBest valuesMean valuesWorst valuesBest values20f10.00420.07152.45E−064.31E−051.30E−032.15E−080.00140.01821.10E−05f2−19.1694−18.6488−19.2085−19.2084−19.2065−19.2085−19.1876−19.0235−19.2084f3−1−0.9998−1−1−1−1−0.9727−0.936−1f4−182.8896−154.8117−186.7246−186.6805−186.1052−186.7309−185.2191−175.6943−186.7203f5−2.0626−2.0623−2.0626−2.0626−2.0626−2.0626−2.0626−2.0622−2.0626f68.68E−108.07E−0900004.40E−063.05E−042.83E−09f70.00160.01897.96E−063.31E−064.25E−058.12E−115.30E−032.88E−024.15E−06f81.20E−158.38E−146.72E−271.12E−306.47E−294.24E−506.47E−055.90E−041.26E−0740f10.00130.02353.15E−073.63E−061.08E−041.09E−103.58E−041.90E−031.32E−06f2−19.1941−19.0671−19.2085−19.2085−19.2084−19.2085−19.202−19.1424−19.2085f3−1−0.9998−1−1−1−1−0.9917−0.9362−0.9998f4−185.3481−178.7177−186.7302−186.7195−186.4609−186.7309−186.059−182.093−186.7298f5−2.0626−2.0625−2.0626−2.0626−2.0626−2.0626−2.0626−2.0625−2.0626f65.14E−109.69E−082.94E−130002.53E−073.45E−062.08E−09f73.53E−040.00392.14E−072.80E−079.30E−064.22E−150.00180.03385.52E−06f82.90E−161.56E−143.93E−231.35E−427.40E−411.52E−641.64E−051.07E−042.41E−0760f13.51E−040.0091.21E−061.19E−064.62E−057.16E−111.65E−041.20E−03..3956E−06f2−19.1961−19.0343−19.2085−19.2085−19.2085−19.2085−19.2033−19.1754−19.2085f3−1−0.9999−1−1−1−1−0.9964−0.9362−0.9999f4−185.1436−167.6131−186.7304−186.7277−186.6912−186.7309−186.3031−182.273−186.0393f5−2.0626−2.0626−2.0626−2.0626−2.0626−2.0626−2.0626−2.0624−2.0626f62.47E−101.68E−095.04E−140001.11E−071.70E−063.90E−10f79.21E−050.00252.20E−088.73E−081.81E−062.04E−149.24E−046.90E−038.38E−06f85.50E−171.63E−151.20E−231.85E−471.08E−451.25E−657.78E−064.71E−059.21E−1080f19.92E−059.92E−055.15E−072.13E−074.47E−052.25E−121.33E−041.10E−031.02E−07f2−19.2018−19.1234−19.2084−19.2085−19.2085−19.2085−19.2063−19.1933−19.2085f3−1−0.9998−1−1−1−1−0.9985−0.9884−1f4−185.7209−172.3019−186.7214−186.7289−186.6909−186.7309−186.4336−184.4008−186.7298f5−2.0626−2.0626−2.0626−2.0626−2.0626−2.0626−2.0626−2.0626−2.0626f63.00E−102.19E−095.51E−130007.06E−087.35E−071.28E−10f73.36E−057.75E−041.72E−074.36E−081.07E−064.72E−207.21E−041.33E−023.03E−06f89.73E−174.21E−151.38E−233.24E−531.64E−511.84E−734.52E−063.52E−051.97E−08The last 7 test functions analyze the resolution accuracy of QPSO, G-QPSO, and PSO in different dimensions by changing the dimensions of the test function with 1000 iterations when the number of particles is 40. Analyzing Table3, it can be found that G-QPSO outperforms QPSO and PSO on the average, maximum, and minimum values of the solution, which proves that G-QPSO is also better than QPSO and PSO in terms of the accuracy of multidimensional test functions. The analysis of Tables 2 and 3 proves that the search accuracy and solution accuracy of G-QPSO are better than those of PSO and QPSO.Table 3
Test function optimization results.
DimensionFunctionQPSOG-QPSOPSOMean valuesWorst valuesBest valuesMean valuesWorst valuesBest valuesMean valuesWorst valuesBest values2f98.50E−071.50E−059.19E−121.03E−115.39E−111.98E−212.79E−115.62E−115.13E−17f100.00250.01481.37E−070.0000740540.007400.00340.01049.94E−11f111.41E−061.63E−059.31E−108.88E−168.88E−168.88E−165.61E−066.07E−056.68E−08f122.88E−040.01168.66E−070001.37E−102.10E−092.13E−14f131.96E−1211.96E−1192.32E−1580001.71E−104.73E−094.13E−15f141.48E−1327.41E−1318.96E−1710008.32E−161.55E−141.29E−19f156.89E−050.0018.50E−103.59E−085.48E−078.04E−175.36E−104.54E−099.46E−1510f90.00260.00863.87E−043.37E−082.82E−074.37E−120.00220.093.98E−06f106.78E−062.70E−042.41E−140000.24160.56950.0672f115.56E−064.57E−044.70E−099.59E−164.44E−158.88E−160.45292.63580.0158f128.15E−050.00122.01E−110009.850621.75513.0815f132.34E−1202.19E−1185.42E−1443.59E−2893.54E−28700.1022.54060.0015f149.48E−1424.54E−1406.33E−1710009.42E−105.07E−091.54E−12f157.26058.01185.52395.8786.26735.052519.8227142.69812.185520f90.0170.03710.00441.32E−071.13E−064.98E−100.18840.71690.02f107.20E−071.18E−055.25E−140001.07261.24440.9007f111.42E−062.68E−059.33E−098.88E−168.88E−168.88E−162.79843.96791.6448f124.34E−057.94E−047.83E−1300043.052583.820418.0085f131.87E−1161.86E−1142.06E−1432.14E−2929.09E−163040.565143.708610.9991f142.98E−1401.48E−1388.67E−1670001.40E−088.78E−081.92E−10f1517.782618.526716.932616.760817.094716.4504131.9277341.192528.215930f90.0370.06860.00884.06E−072.94E−061.39E−091.01813.15530.311f103.64E−077.55E−061.48E−140001.6732.64951.2062f111.57E−061.62E−054.58E−088.88E−168.88E−168.88E−164.16995.82882.8203f124.43E−050.00134.23E−13000101.4013167.642649.3847f135.73E−1204.45E−1184.05E−1434.23E−3114.09E−3090528.03992020176.5473f143.06E−1383.07E−1362.78E−1720004.34E−083.91E−076.44E−10f1527.946528.697226.590727.15727.542226.8536336.6403967.2821159.5259The following compares the curves of the fitness values of the first 8 test functions to compare the convergence speed when the number of particles is 40 and the number of iterations is 50, where a-QPSO is G-QPSO without theb and c strategies; the following data are the averages of 100 tests.By comparing the eight test functions in Figures2–9, it is found that G-QPSO converges faster than QPSO and PSO. In summary, G-QPSO is better than QPSO and PSO in both the speed of convergence and the accuracy of the solution.Figure 2
Convergence curve test function f1.Figure 3
Convergence curve test function f2.Figure 4
Convergence curve test function f3.Figure 5
Convergence curve test function f4.Figure 6
Convergence curve test function f5.Figure 7
Convergence curve test function f6.Figure 8
Convergence curve test function f7.Figure 9
Convergence curve test function f8.However, to further understand the role of each strategy in G-QPSO, the functions from 9 to 12 are used for comparison when the number of particles is 40, the number of dimensions is 20, and the number of iterations is 50, where bc-QPSO is G-QPSO without the strategy; the following data are the average of 100 tests.By analyzing Figures10–13, it is clear that the convergence speed of G-QPSO and a-QPSO is faster than that of bc-QPSO. By analyzing Table 4, it is clear that the accuracy of G-QPSO and bc-QPSO is better than that of a-QPSO. In general, strategy a mainly speeds up the convergence speed, while strategy bc mainly improves the accuracy of the search to improve the accuracy of the solution.Figure 10
Convergence curve test function f9.Figure 11
Convergence curve test function f10.Figure 12
Convergence curve test function f11.Figure 13
Convergence curve test function f12.Table 4
Test function optimization results.
AlgorithmFunctionMean valuesWorst valuesBest valuesbc-QPSOf93.60E−039.60E−036.43E−04f102.56E−142.49E−120f111.17E−091.44E−081.81E−11f121.79E−141.36E−120a-QPSOf90.80331.18270.3098f106.88E−133.31E−110f115.40E−086.81E−075.02E−13f121.57E−135.45E−120G-QPSOf91.32E−071.13E−064.98E−10f10000f118.88E−168.88E−168.88E−16f12000By analyzing the search strategy of G-QPSO, a clear search direction and precise search in the later stage can ensure that the algorithm has higher accuracy and faster convergence speed.The following results are clear early in the search: (1) The clear directivity and the randomness ofln1/u work together to make particles search on the line between the global best (the average individual best) and themselves. Moreover, ln1/u ranges from 0 to infinity, which ensures that the search area is an entire straight line. (2) Either no update particle strategy or the Levy flight particle strategy keeps the average individual’s best away from the global best, ensures the diversity of the previous search solution, and reduces the probability of local optimization.At the later stage of the search, when the particle updates its position, some particles will follow the strategy of the later search so that the particle searches near the global optimal position.


## 5. Conclusion

Based on the analysis of the quantum-behaved particle swarm algorithm, an updated location method based on the combination of traditional physics and quantum behavior is proposed, which not only guarantees the directivity of the particles during the search but also reduces the probability of falling into a local optimum. Therefore, G-QPSO improves the directivity as well as the accuracy of the search. In general, strategya improves the convergence speed, while strategy bc improves the accuracy of the search. Strategies a, b, and c work together, so G-QPSO is better than QPSO and PSO in terms of both the convergence speed and the accuracy of the solution.



---

*Source: 3230643-2020-05-28.xml*