THREE-DIMENSIONAL TRACK PLANNING METHOD BASED ON IMPROVED PARTICLE SWARM OPTIMIZATION ALGORITHM

Abstract

A three-dimensional track planning method based on improved particle swarm optimization algorithm is disclosed. During the process of searching an optimal three-dimensional track in a track space, Different inertia weights are set in different particle swarm iterative evolution stages. A maximum inertia weight is used to make global convergence in a set early stage of evolution, and a minimum inertia weight is used to make local convergence in a set late stage of evolution. Disturbance mutation operation in a motion process of particles is added based on swarm diversity. Infeasible particles are selected based on constraints. Constraint violation functions of infeasible particles are compared, and infeasible particles with small constraint violation functions are kept. The disclosure makes full use of all particles, so that the infeasible solutions can also provide help for the overall optimization of the swarm, and ensures the reliability and efficiency of track planning

Claims

1. A three-dimensional track planning method based on improved particle swarm optimization algorithm, wherein during the process of particles searching an optimal three-dimensional track in a track space, the method comprises following steps: different inertia weight settings in different iterative evolution stages of the particle swarm: using a maximum inertia weight to make global convergence in a set early stage of evolution, and using a minimum inertia weight to make local convergence in a set late stage of evolution; adding disturbance mutation operation in a motion process of particles based on swarm diversity, wherein the disturbance mutation operation comprises position disturbance of particles, mutation update of global extremum and individual extremum, and setting of number of divergence generations of particles; and selection of infeasible particles based on constraints: comparing constraint violation functions of infeasible particles, keeping infeasible particles with small constraint violation functions to continue to participate in the iterative evolution of the particle swarm, and discarding non-winning particles directly due to violating constraints.

2. The three-dimensional track planning method based on improved particle swarm optimization algorithm of claim 1, wherein the track space is set with multiple optimization parameters, that is, for the multi-dimensional track space, different inertia weights are used for different dimensions: the inertia weights are set to change according to the following rules: $w_j\left(\ell \right)=\{\begin{array}{cc}{w}_1,& 0\le \ell <\frac{{\ell }_{\max }}{3}\\ w_0+\left(w_1-w_0\right)e^{-3K_{w,j}},& \frac{{\ell }_{\max }}{3}<\ell <\frac{2{\ell }_{\max }}{3}\\ w_0,& \frac{2{\ell }_{\max }}{3}<\ell \le {\ell }_{\max }\end{array}$ wherein, w.sub.0 is the minimum value of the inertia weights, w.sub.1 is the maximum value of the inertia weights, 0≤K.sub.w,j≤1, K.sub.wj is a closeness of particle i to an optimal position of the swarm in the j-th dimensional space, is the number of iterations, and .sub.max is the maximum number of iterations.

3. The three-dimensional track planning method based on improved particle swarm optimization algorithm of claim 1, wherein when the particle swarm gathers at an optimal track space position in the early set stage of evolution, position disturbance is performed on a set number of particles; when the global extremum of the particle swarm optimization algorithm has stagnated in a set past stage evolution, a new global extremum is calculated by interpolation algorithm, and it is judged whether the new global extremum is better than the global extremum before calculation, and if so, the global extremum before calculation is replaced by the new global extremum; when the individual extremum of the particle swarm optimization algorithm has stagnated in a set past evolution stage, reverse mutation is performed on the particle i to calculate a new individual extremum, and it is judged whether the new individual extremum is better than the individual extremum before mutation, and if so, the individual extremum before mutation is replaced by the new individual extremum; and when the swarm diversity of the particle swarm tends to converge in the set early stage of evolution, a set number of particles is selected, and the number of divergence generations of the selected particles is set to make them diverge in a search motion region in the track space.

4. The three-dimensional track planning method based on improved particle swarm optimization algorithm of claim 1, wherein the infeasible particles are particles that do not meet constraints of terminal height, terminal landing, dynamic pressure range and overload range, and a constraint violation function is defined as: $f_{V,i}=\frac{u_{V,i}}{\underset{i=1}{\overset{M_v}{.Math.}}{u}_{V,i}}$ wherein, M.sub.v is a total number of the infeasible particles in the swarm; u.sub.V,i is a degree evaluation of deviation from a constraint value; $u_{V,i}=\sqrt{\underset{j=1}{\overset{4}{.Math.}}{\Psi }_j^2}$ wherein, Ψ.sub.1, Ψ.sub.2, Ψ.sub.3, Ψ.sub.4are normalized values of the deviation degree of the above four constraints respectively; and a plurality of infeasible particles are compared and the infeasible particles with small f.sub.V,i are kept.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0026] In order to explain the embodiments of the present disclosure or the technical solutions in the prior art more clearly, the following drawings that need to be used in the description of the embodiments or the prior art will be briefly introduced. Obviously, the drawings in the following description are only embodiments of the present disclosure. For those of ordinary skill in the art, other drawings can be obtained based on the drawings disclosed without creative work.

[0027] FIG. 1 is a schematic diagram of the motion mechanism of a single particle in the three-dimensional track planning method based on improved particle swarm optimization algorithm provided by the embodiments of the disclosure.

[0028] FIG. 2 is a schematic diagram of disturbance operation to the swarm in the three-dimensional track planning method based on the improved particle swarm optimization algorithm provided by the embodiments of the disclosure.

[0029] FIG. 3 is a schematic diagram of the constraint processing mechanism in the three-dimensional track planning method based on the improved particle swarm optimization algorithm provided by the embodiments of the disclosure.

[0030] FIG. 4 is a schematic diagram of a three-dimensional simulation scene provided by the embodiments of the present disclosure.

[0031] FIG. 5 is a two-dimensional display diagram of the optimal track of the unmanned aerial vehicle based on the improved PSO algorithm provided by the embodiments of the disclosure.

[0032] FIG. 6 is a three-dimensional display diagram of the optimal track of the unmanned aerial vehicle based on the improved PSO algorithm provided by the embodiments of the disclosure.

[0033] FIG. 7 is a schematic diagram of the relationship between the convergence time and the inertia weights of the basic PSO algorithm provided by the embodiments of the disclosure.

DETAILED DESCRIPTION OF THE EMBODIMENTS

[0034] Technical solutions of the present disclosure will be clearly and completely described below with reference to the embodiments. Obviously, the described embodiments are only part of the embodiments of the present disclosure, not all of them. Based on the embodiments of the disclosure, all other embodiments obtained by those skilled in the art without making creative work belong to the protection scope of the disclosure.

[0035] This embodiment designs a highly autonomous and versatile flight track planning method based on the improved PSO algorithm. First, the basic PSO algorithm flow is introduced as follows.

[0036] The PSO algorithm uses particles to search for the optimal solution in the search space, each particle represents a potential solution to the optimization problem, and its corresponding performance index is called “fitness”. Assuming that there are M.sub.pso particles searching for D.sub.pso optimization parameters in the space, the position vector and velocity vector of the i-th (i=1, 2, . . . , M,) particle in the D.sub.pso-dimensional search space are:

[00004]$\begin{array}{cc}\{\begin{array}{c}{X}_i=\left(x_{i,1},x_{i,2},.Math.,x_{i,D_{\mathrm{pso}}}\right)\\ V_i=\left(v_{i,1},v_{i,2},.Math.,v_{i,D_{\mathrm{pso}}}\right)\end{array}& \left(1\right)\end{array}$

[0037] At the same time, the best position searched by the i-th particle from the beginning of the algorithm is recorded as P.sub.i, and the fitness corresponding to P.sub.i is p.sub.best. Correspondingly, the best position searched by all particles is record as P.sub.g, and the fitness corresponding to P.sub.g is g.sub.best.

[00005]$\begin{array}{cc}\{\begin{array}{c}{P}_i=\left(p_{i,1},p_{i,2},.Math.,p_{i,D_{\mathrm{pso}}}\right)\\ P_g=\left(p_{g,1},p_{g,2},.Math.,p_{g,D_{\mathrm{pso}}}\right)\end{array}& \left(2\right)\end{array}$

[0038] In the basic PSO algorithm, the entire swarm evolves as follows:

=+c.sub.1r.sub.1(p.sub.i,j−)+c.sub.2r.sub.2(p.sub.g,j−)   (3)

=+v.sub.i,j.sup.+1   (4)

[0039] wherein, superscript “” indicates the current number of iterations, 0<w<1 is inertia weight, c.sub.1 and c.sub.2 are learning factors, which generally take values between 0 and 4, and r.sub.1 and r.sub.2 are random numbers between 0 and 1.

[0040] The meanings of each variable are as follows:

[0041] 1. w indicates that the particle position is affected by the velocity, which makes the particle maintain different motion characteristics (swarm diversity) from other companions.

[0042] 2. c, determines the degree to which particles are affected by individual experience, which guides the particles to approach P.sub.i.

[0043] 3. c.sub.2 determines the degree to which particles are affected by swarm experience, which guides the particles to approach P.sub.g.

[0044] In practical problems, each optimization parameter has its own value range. Therefore, when applying PSO algorithm, the position of each particle in the search space should be limited to a certain range, that is:

x.sub.Lj≤x.sub.i,j≤x.sub.Uj   (5)

[0045] wherein, x.sub.Uj and x.sub.Lj are the upper/lower bounds of the j-th dimensional space respectively.

[0046] Accordingly, the velocity of particles in the j-th dimension space is also limited within a certain range to prevent particles from jumping out of the space boundary in the next iteration:

x.sub.Lj−x.sub.Ui≤v.sub.i,j≤x.sub.Uj−x.sub.Lj   (6)

[0047] In this paper, the swarm diversity at the -th generation is defined as:

[00006]$\begin{array}{cc}{\delta }_{\mathrm{swarm}}^{\ell }=\frac{1}{M_{\mathrm{pso}}}\underset{i=1}{\overset{M_{\mathrm{pso}}}{.Math.}}\sqrt{\underset{j=1}{\overset{D_{\mathrm{pso}}}{.Math.}}{\left(\frac{x_{i,j}^{\ell }-{\stackrel{\_}{x}}_j^{\ell }}{x_{\mathrm{Uj}}-x_{\mathrm{Lj}}}\right)}^2}& \left(7\right)\end{array}$

wherein, x.sub.j.sup.t is the average position of all particles in the j-th dimension. The calculation of takes into account the differences in the value range of different optimization parameters, and ∈(0,1).

[0048] The maximum number of iterations is set as .sub.max, then when >.sub.max, the PSO algorithm terminates.

[0049] The convergence of the basic PSO algorithm is as follows:

[0050] Defining ϕ.sub.1=c.sub.1r.sub.1+c.sub.2r.sub.2 and ϕ.sub.2=c.sub.1r.sub.1p.sub.i,j+c.sub.2r.sub.2p.sub.g,j, it can be obtained from the evolution formula of PSO algorithm:

+(ϕ.sub.1−w−1)+=ϕ.sub.2   (8)

[0051] If the movement of particles is regarded as a continuous process, the above formula is a classical non-homogeneous second-order differential equation without velocity term. The above formula shows that PSO algorithm actually does not need the concept of speed, so it can avoid setting the speed boundary and make the swarm evolution process more concise.

[0052] It is assumed that p.sub.i,j and p.sub.g,j are constant values, which are respectively recorded as p and g. The expectation of a variable is expressed by the symbol .sub.E. If c.sub.1=c.sub.2={tilde over (c)}, then

[00007]$\begin{array}{cc}\{\begin{array}{c}{E}_{}\left(r_1\right)=E_{}\left(r_2\right)=0.5\\ E_{}\left({\varphi }_1\right)=\tilde{c}\\ E_{}\left({\varphi }_2\right)=\frac{\tilde{c}}{2}\left(p+g\right)\end{array}& \left(9\right)\end{array}$

[0053] According to equation (8), there is:

.sub.E()=[1+w−.sub.E(ϕ.sub.1)].sub.E()−w.sub.E()+.sub.E(ϕ.sub.2)   (10)

[0054] When PSO algorithm converges, there is .sub.E ()=.sub.E()=.sub.E(), therefore:

.sub.E(ϕ.sub.1).Math..sub.E()=.sub.E(ϕ.sub.2)   (11)

[0055] Therefore, a particle of PSO algorithm will converge to the following position in a certain dimension:

[00008]$\begin{array}{cc}{\hslash }_E^{*}=E_{}\left(x_{i,j}^{\ell }\right).fwdarw.\frac{{\hslash }_E\left({\varphi }_2\right)}{{\hslash }_E\left({\varphi }_1\right)}=\frac{p+g}{2}& \left(12\right)\end{array}$

[0056] Assuming that the damping of the second-order system represented by equation (8) is ξ.sub.n and the frequency is ω.sub.n, then there is

[00009]$\begin{array}{cc}\{\begin{array}{c}{\omega }_n=\sqrt{w}\\ {\xi }_n=\frac{{\varphi }_1-w-1}{2\sqrt{w}}\end{array}& \left(13\right)\end{array}$

[0057] Therefore, when ϕ.sub.1−w−1>0, the particle converges gradually to *.sub.E in the j-th dimension space. This conclusion is obtained under the assumption that p.sub.i,j and p.sub.g,j are constants, but in fact p.sub.i,j and p.sub.g,j are dynamic, so the actual motion of the particle is described by multiple second-order differential equations. When the inertia weight is 1, the position of the particle will change according to the sine law, and the particle will continue to jump from one sine wave to another in the process of evolution. Under the influence of random numbers, particles actually spiral around in space.

[0058] From equation (13), the convergence condition of the algorithm is ϕ.sub.1−w−1>0. It is set that the algorithm converges when the relative error is less than 2%, and the convergence time is set to t.sub.s, then:

[0059] 1. When 0ξ.sub.n<1, equation (8) is an underdamped system, and the convergence time is:

[00010]$\begin{array}{cc}{t}_s=\frac{4-\ln \left(1-{\xi }_n^2\right)}{{\omega }_n{\xi }_n}& \left(14\right)\end{array}$

[0060] 2. Because the ϕ.sub.1 in ξ.sub.n is random, ξ.sub.n=1 hardly occurs, so it can be considered that there will be no critical damping system.

[0061] 3. When ξ.sub.n>1, equation (8) is an overdamped system, and the convergence time is:

[00011]$\begin{array}{cc}{t}_s=\frac{1}{{\omega }_n\left({\xi }_n-\sqrt{{\xi }_n^2-1}\right)}\ln \frac{25}{\sqrt{{\xi }_n^2-1}\left({\xi }_n-\sqrt{{\xi }_n^2-1}\right)}& \left(15\right)\end{array}$

[0062] In PSO algorithm, it usually takes c.sub.1=c.sub.2=2.0, so ℏ.sub.E (ϕ.sub.1)=2. Taking ϕ.sub.1=2, equation (13) is substituted into equations (14) and (15) respectively, frequency and damping are substituted by inertia weight, and the relationship between the time required for particle convergence and inertia weight is obtained, as shown in FIG. 7.

[0063] As can be seen from FIG. 7, in general, the motion of particles around *.sub.E is basically underdamped, and the convergence time decreases with the decrease of weight. When entering the overdamped state, the convergence time increases with the decrease of the weight. In this paper, it is set that 0.2≤w≤0.9, that is, particles always move in an underdamped state.

[0064] It should be noted that in PSO algorithm, the motion of particles is described by the number of iterations, not time. Therefore, the results in FIG. 7 are not the actual convergence time, but only provide a reference for the analysis of particle convergence process.

[0065] The derivative of damping to inertia weight is:

[00012]$\begin{array}{cc}\frac{d{\xi }_n}{dw}=-\frac{\left({\varphi }_1-1\right)+w}{4w\sqrt{w}}\approx -\frac{1+w}{4w\sqrt{w}}<0& \left(16\right)\end{array}$

[0066] It can be seen that the damping decreases with the increase of inertia weight. Therefore, when the inertia weight is large, the particles converge in the direction of *.sub.E with a large oscillation amplitude, and the convergence time naturally increase, which is consistent with the conclusion above.

[0067] Let the convergence center formed by P.sub.i and P.sub.g in the whole search space be:

*.sub.E=[*.sub.E1, .sub.E2, . . . , *.sub.ED.sub.pso].sup.T   (17)

[0068] As the swarm evolves, there will be P.sub.i.fwdarw.P.sub.g, .sub.E.fwdarw.P.sub.g.

[0069] On the basis of the basic principle of PSO algorithm, the embodiment of the disclosure proposes an improved PSO algorithm based on convergence analysis. The performance of the PSO algorithm is mainly reflected in convergence accuracy and convergence speed. For convergence accuracy, like many intelligent algorithms, the basic PSO algorithm is easy to fall into local optimization, that is, P.sub.g only hovers around a non-optimal position, resulting in the final result is not the global optimization. Suppose the theoretical optimal position is .sub.E.sup.†, then the convergence accuracy is ε.sub.E=∥.sub.E.sup.†−*.sub.E∥.sub.2. Therefore, in order to improve the accuracy, *.sub.E must be as close to .sub.E.sup.† as possible. In order to improve the convergence speed, the first is to ensure that the particles quickly “fly” to the convergence center *.sub.E , and the second is to find .sub.E.sup.† as soon as possible.

[0070] In the process of particles searching the optimal three-dimensional track in the track space, the following steps are performed.

[0071] Different inertia weights are set in different particle swarm iterative evolution stages. A maximum inertia weight is used to make global convergence in a set early stage of evolution, and a minimum inertia weight is used to make local convergence in a set late stage of evolution.

[0072] Disturbance mutation operation in a motion process of particles is added based on swarm diversity. The disturbance mutation operation includes position disturbance of particles, mutation update of global extremum and individual extremum, and setting of number of divergence generations of particles.

[0073] Infeasible particles are selected based on constraints. Constraint violation functions of infeasible particles are compared, infeasible particles with small constraint violation functions are kept to continue to participate in the iterative evolution of particle swarm.

[0074] In one embodiment, the track space is set with multiple optimization parameters, that is, for the multi-dimensional track space, different inertia weights are used for different dimensions:

[0075] the inertia weights are set to change according to the following rules:

[00013]$\begin{array}{cc}{w}_j\left(\ell \right)=\{\begin{array}{cc}{w}_1,& 0\le \ell <\frac{{\ell }_{\max }}{3}\\ w_0+\left(w_1-w_0\right)e^{-3K_{w,j}},& \frac{{\ell }_{\max }}{3}<\ell <\frac{2{\ell }_{\max }}{3}\\ w_0,& \frac{2{\ell }_{\max }}{3}<\ell \le {\ell }_{\max }\end{array}& \left(18\right)\end{array}$

[0076] wherein, w.sub.0 is the minimum value of the inertia weights, w.sub.1 is the maximum value of the inertia weight, 0≤K.sub.w,j≤1, K.sub.wj is closeness of particle i to an optimal position of the swarm in the j-th dimensional space, is the number of iterations, and .sub.max is a maximum number of iterations.

[0077] In this embodiment, once all particles gather in *.sub.E, the search of the whole swarm will gradually stop. Therefore, *.sub.E should be avoided wandering around a non-optimal location, but the space should be constantly searched to increase the chance of finding .sub.E.sup.† and reduce errors. It can be seen from the convergence analysis of PSO algorithm that a larger inertia weight will produce a smaller damping, increase the oscillation amplitude of particles and improve the probability of finding .sub.E.sup.†. At the same time, the earlier .sub.E.sup.† is found, the earlier the algorithm ends. Therefore, large weight is beneficial to reduce the number of generations of swarm evolution and improve the convergence speed. However, from the perspective of individual convergence speed, it is appropriate to use a small inertia weight. Therefore, the effect of inertia weight on convergence accuracy (global convergence) and convergence speed (local convergence) is contradictory.

[0078] Compared with the constant inertia weight, the performance of PSO algorithm can be significantly improved by using the inertia weight which changes dynamically with the number of iterations. However, many methods, such as linear weight, exponential weight, random weight, polynomial weight, chaotic weight, can not accurately control the relationship between global convergence and local convergence. At the same time, the inertia weight can not take into account the global convergence and local convergence, so relying solely on the inertia weight can not obtain the best search results.

[0079] As shown in FIG. 1, the inertia weight is adaptively adjusted according to the swarm evolution. The main principle is: using large inertia weight to promote global convergence in the early stage of evolution, and using small inertia weight to promote local convergence in the late stage of evolution. In addition, since the optimization problem studied in this embodiment involves many optimization parameters, the search space dimension is high, and different inertia weights need to be used for different dimensions.

[0080] In the inertia weight law change formula, there is:

[00014]$\begin{array}{cc}{K}_{w,j}=\frac{.Math.p_{i,j}-p_{g,j}.Math.}{{.Math.P_i-P_g.Math.}_2}& \left(19\right)\end{array}$

[0081] Obviously, 0≤K.sub.wj≤1. K.sub.wj represents the closeness of particle i to the optimal position of the swarm in the j-dimensional space. The smaller K.sub.wj indicates that the motion range of the particle in this dimension is too small. The weight should be increased to intensify the motion oscillation of the particle, so that it can search in this dimension more comprehensively.

[0082] In one embodiment, the disturbance mutation operation based on swarm diversity includes the following specific contents:

[0083] Equation (8) is rewritten as follows:

x.sub.i,j.sup.i+2+[(ϕ.sub.1−1)−(w−r.sub.3)]x.sub.i,j.sup.i+1+(w+r.sub.4)x.sub.i,j.sup.t=ϕ.sub.2   (20)

[0084] wherein, r.sub.3 and r.sub.4 are random numbers between 0 and 1.

[0085] At this point, the convergence condition of the second-order system becomes ϕ.sub.1≠1−w+r.sub.3>0. Compared with equation (8), equation (20) is equivalent to adding a random number to the frequency and damping of the original second-order system respectively, which makes the motion process of particles subject to random disturbance, so as to search in space more fully. At the same time, it can improve the swarm diversity and help to find better P.sub.i and P.sub.g.

[0086] In fact, the above method is to make the particles find a better position in the process of motion, but the effect is not obvious in practical application. Since P.sub.g is the main direction of motion of particles, particles mainly gather around P.sub.g. If .sub.E.sup.† generated by random initialization is far away from P.sub.g, the swarm will be difficult to find .sub.E.sup.†. Therefore, in order to make the particles fully search the space, the motion law of the particles must be changed.

[0087] When it evolves to the j-th generation, the value of P.sub.g is recorded as , and the value of P.sub.i is recorded as . The follows are calculated separately:

[00015]$\begin{array}{cc}{\Delta }_g=\frac{1}{{\ell }_g}\stackrel{\ell }{\underset{k=\ell -{\ell }_g}{.Math.}}{.Math.P_g^{\ell }-P_g^k.Math.}_2& \left(21\right)\end{array}$$\begin{array}{cc}{\Delta }_i=\frac{1}{{\ell }_i}\stackrel{\ell }{\underset{k=\ell -{\ell }_i}{.Math.}}{.Math.P_i^{\ell }-P_i^k.Math.}_2& \left(22\right)\end{array}$$\begin{array}{cc}{\Delta }_{\delta }=\frac{1}{{\ell }_{\delta }}\stackrel{\ell }{\underset{k=\ell -{\ell }_{\delta }}{.Math.}}.Math.{\delta }_{\mathrm{swarm}}^{\ell }-{\delta }_{\mathrm{swarm}}^k.Math.& \left(23\right)\end{array}$

[0088] wherein, .sub.g, .sub.i, .sub.δ are the number of generations considered in calculating Δ.sub.g , Δ.sub.i and Δ.sub.δ.

[0089] 1. As shown in FIG. 2, when the particle swarm gathers at an optimal track space position in the early set stage of evolution, position disturbance is performed on the set number of particles.

[0090] The top 20% of particles are selected to subject to the position disturbance:

[00016]$\begin{array}{cc}{X}_i=X_i\left(1+r_5{K}_{\mathrm{wj}}\frac{{\ell }_{\max }-\ell }{{\ell }_{\max }}\right)& \left(24\right)\end{array}$

[0091] wherein, r.sub.5 is a random integer equal to 2 or −2. The above formula shows that the mutation range of particles gradually decreases with the increase of number of iterations, which is conducive to promoting convergence to *.sub.E in the late evolution.

[0092] 2. When the global extremum of particle swarm optimization algorithm has stagnated in a set past stage evolution, a new global extremum is calculated by interpolation algorithm, and it is judged whether the new global extremum is better than the global extremum before calculation, and if so, the global extremum before calculation is replaced by the new global extremum.

[0093] When Δ.sub.g<ε.sub.g , it indicates that the global extremum has stagnated in the past .sub.g generation.

[0094] At this time, according to the change history of P.sub.g, a new global extremum P.sub.g is obtained by interpolation:

P.sub.g=f.sub.3(, , . . . , ,)   (25)

[0095] wherein, f.sub.3 is cubic spline interpolation function. If P.sub.g is better than P.sub.g, let P.sub.g=P.sub.g. Otherwise, P.sub.g is kept.

[0096] 3. When the individual extremum of particle swarm optimization algorithm has stagnated in the set past evolution stage, reverse mutation is performed on the particle i to calculate a new individual extremum, and it is judged whether the new individual extremum is better than the individual extremum before mutation, and if so, the individual extremum before mutation is replaced by the new individual extremum.

[0097] When Δ.sub.i<ε.sub.i, it indicates that the individual extremum has stagnated in the past , generation.

[0098] At this point, reverse mutation is performed on the particle:

P=−P.sub.i   (26)

[0099] If P.sub.i is better than P.sub.i, P.sub.i is replaced by P.sub.i. Otherwise, P.sub.i is kept.

[0100] 4. When the swarm diversity of the particle swarm tends to converge in the set early stage of evolution, a set number of particles is selected, and the numberof divergence generations of the selected particles is set to make them diverge in a search motion region in the track space.

[0101] When Δ.sub.δ<ε.sub.Δ and <.sub.max/2, it indicates that the swarm diversity has not been improved.

[0102] At this time, the weight modification or position disturbance can no longer effectively improve the search efficiency of the algorithm, and the particle motion state needs to be greatly changed. The top 10% of the particles are selected, and r.sub.1 and r.sub.2 are adjusted to make ϕ.sub.1−w−1<0, that is, to make the motion of some particles tend to diverge. The number of divergence generations is calculated as follows:

[00017]$\begin{array}{cc}{\ell }_{D,k}=\frac{{\Delta }_i}{\stackrel{N_D}{\underset{i_D-1}{.Math.}}{\Delta }_{i_D}}{\ell }_D& \left(27\right)\end{array}$

[0103] wherein, N.sub.D is the number of selected particles, .sub.D,k is the number of divergence generations of the k-th particle among the selected particles, and .sub.D is the maximum number of divergence generations.

[0104] In the present embodiment, there are max .sub.g=.sub.max/4, .sub.i=.sub.max/5, .sub.δ=.sub.max/4, and .sub.D=.sub.max/6.

[0105] In one embodiment, it is noted that the particles satisfying all constraints are feasible particles, and vice versa are infeasible particles. Constraints can be processed through simple comparison. When comparing two particles:

[0106] 1. if both are feasible, the fitness values are compared, and the one with the smaller fitness value wins;

[0107] 2. if one is feasible and the other is not, the feasible particle wins; and

[0108] 3. if neither is feasible:

[0109] a) the constraint violation function is defined as:

[00018]$\begin{array}{cc}{f}_{V,i}=\frac{u_{V,i}}{\underset{i=1}{\overset{M_v}{.Math.}}{u}_{V,i}}& \left(28\right)\end{array}$

[0110] wherein, M.sub.v is the total number of infeasible particles in the swarm, u.sub.V,i is a degree evaluation of deviation from constraint value.

[00019]$u_{V,i}=\sqrt{\underset{j=1}{\overset{4}{.Math.}}{\Psi }_j^2}$

wherein, Ψ.sub.1, Ψ.sub.2, Ψ.sub.3, Ψ.sub.4 are normalized values of the deviation degree of the above four constraints respectively.

[0111] b) the one with small f.sub.V,i wins.

[0112] The comparison principles described above are used to select P.sub.g in the swarm. As shown in FIG. 3, when comparing three infeasible particles, although particle □ violates more constraints, it is closer to the feasible region and thus is considered to be more optimal. The winning particles continue to participate in the optimization iteration, while the non-winning particles are directly discarded due to violation of constraints.

[0113] Different from the commonly used penalty function method, the comparison method proposed in this embodiment makes full use of all particles by virtue of the relationship between particles and feasible region, so that the infeasible solutions can also provide help for the overall optimization of the swarm, and the efficiency of the algorithm is ensured while solving the constraints.

[0114] The process and results of the method of the disclosure in UAV aviation track analysis are given below.

[0115] Algorithm environment: Windows? 64 bit, Matlab R2017a. Processor: Intel® Core™ i5-5200U. Main frequency: 2.2 GHz. Computer RAM: 8 GB.

[0116] In order to verify the effectiveness of the algorithm in three-dimensional space, different from two-dimensional track planning, the environment model was established considering the impact of flight height on the track, and then the simulation was carried out. Two topographic maps were designed for simulation verification.

[0117] The initial conditions are as follows.

[0118] 1. The constraint parameters of UAV flight capability set in this embodiment are as follows.

[0119] (1) The maximum air-range was 40 km.

[0120] (2) the minimum route segment distance was 0.8 km.

[0121] (3) The maximum number of waypoints was 20.

[0122] (4) The maximum turning angle was 90 °.

[0123] (5) The average flight speed of the UAV was 200 m/s.

[0124] (6) The shortest allowable interval between two routes was 0.5 km.

[0125] (7) The UAV take-off preparation time was 10 s.

[0126] (8) The minimum height of the UAV above the ground was 200 m.

[0127] 2. Settings of optimization variables

[0128] .sub.max was taken as .sub.max=20, and c.sub.1 and c.sub.2 were taken as c.sub.1=c.sub.2=2.0. In equation (18), w.sub.0 was taken as w.sub.0=0.1, and w.sub.1 was taken as w.sub.1=0.9.

[0129] The three-dimensional space of the three-dimensional simulation scene was 30 km long, 30 km wide, and 1 km high. It consisted of six peaks with different heights and five defense circles. The UAV track planning were carried out in this space, as shown in FIG. 4.

[0130] The track of the UAV was optimized based on the improved PSO algorithm, and the results are shown in FIG. 5 and FIG. 6. Table 1 is the simulation data of the evaluation criteria of the basic PSO algorithm and the improved PSO algorithm of the present disclosure to optimize the track of the UAV.

TABLE-US-00001 TABLE 1 Simulation data of 3D simulation scene Track Evaluation Criteria Basic PSO Improved PSO Track optimum 45.13 43.94 Track average 46.58 44.10 Average running time 18.629 12.925 Standard deviation 0.5964 0.2616 Track maximum 46.69 44.19

[0131] The simulation results are analyzed as follows.

[0132] FIG. 5 and FIG. 6 respectively show the effect of track planning from the starting point 0 to the target point 30 km. In this embodiment, two algorithms are selected for comparative analysis, namely, the basic PSO algorithm and the improved PSO algorithm. From the effects comparison of track planning from FIG. 5 and FIG. 6, it is obvious that the planned track is relatively smooth, and from Table 1, it can be seen that the shortest track of the improved PSO algorithm in this embodiment was 43.94 km, and the average track value was 44.10 km. Therefore, based on the comparison of the two algorithms, the track planning of the improved PSO algorithm of the disclosure has better effect on UAV planning

[0133] The above describes in detail the three-dimensional track planning method based on the improved particle swarm optimization algorithm provided by the disclosure. In the specification, specific embodiments are used to explain the principle and implementation mode of the disclosure. The description of the above embodiments is only used to help understand the method and core idea of the disclosure. Meanwhile, for those skilled in the art, there will be changes in the specific implementation mode and application scope according to the idea of the disclosure. In conclusion, the contents of this specification shall not be construed as limiting the disclosure.

[0134] The above description of the disclosed embodiments enables the skilled in the art to achieve or use the disclosure. Multiple modifications to these embodiments will be apparent to those skilled in the art, and the general principles defined herein may be achieved in other embodiments without departing from the spirit or scope of the disclosure. The present disclosure will therefore not be restricted to these embodiments shown herein, but rather to comply with the broadest scope consistent with the principles and novel features disclosed herein.