An improved adaptive differential evolution algorithm for single unmanned aerial vehicle multitasking

Jian-li Su, Hua Wang

School of Astronautics, Beihang University, Beijing,100191, China

Keywords:Unmanned aerial vehicle Multitasking Adaptive differential evolution Mutation factor Crossover factor

ABSTRACT

1. Introduction

UAVs are increasingly widely used in the past decade, and its technology becomes more mature. Perform a single task can no longer meet the demand for UAV,particularly in the field of military[1]. The use of UAV has made warfare more efficient and has resulted casualties [2,3]. In consequence, research on multitasking of UAV has aroused worldwide attention.

Although multi-UAVs cooperative multi-targets assignment is a wide-ranging topic, research on multitasking of single UAV is particularly important, such as the RQ-4, MQ-1 and MQ-9 are expensive to produce, and the high cost of their operations and maintenance, allowing large scale cooperation of these vehicles is not possible [4]. Single UAV multi-tasking assignment, like multi-UAVs cooperative multi-targets assignment, proved to be a NPhard problem that getting a global optimized solution [5]. Many intelligent algorithms have been put forward and improved by scholars to address the computing complexity, for example,mathematical algorithms, genetic algorithm (GA) [6-9], particle swarm optimization (PSO) [10-12], and ant colony optimization(ACO) [13-15]. GA, which is formed by the biological laws and natural genetic mechanisms search algorithm, works as a parallel algorithm. Professor J. Holland said GA can be mainly realized by the means of crossover, mutation, and selection operators in his proposed book in 1975 [16]. In the PSO algorithm, which is proposed by Kennedy and Eberhart [17], several particles working as potential solution of the search space are randomly generated in the first stage. Secondly, the iteration process can help to find the optimal solution.Thirdly,two“extreme values”are used to update the velocity and displacement of the particle,one of which is called the local optimal solution working for the particle itself as the optimal solution and another one is called the global optimal solution for the entire population. In Ref. [18], the spherical vectorbased SPSO algorithm was proposed to solve the UAV path planning problem and minimize the cost function. In Ref. [19], the proposed motion-encoded PSO algorithm is applied to the UAV's search for moving targets. In Ref. [20], Rauch-Tung-Striebel (RTS)smoother is used to improve the PSO algorithm,and the algorithm is applied to UAV path planning,and good results are obtained.The ACO imitates the process of ant foraging. At first, the ant colony randomly searches for food and finally gathers at the place where there is more food. The ant colony foraging will show a certain pattern. The algorithm that imitates this process is called ACO. In order to determine the trajectory of the UAV so that it can find the missing target in the shortest time,Sara Perez-Carabaza proposes a new method based on ACO[21].

Those heuristic algorithms are put to be widely used in UAV multi-target attacking and path planning as digital technology and computer technology improvement, each one of which has its advantages and disadvantages. Although GA has good global searching ability, but its local searching turned out not very effective.During the early stage of PSO with the fast convergence speed,the low efficiency results in poor accuracy and divergence. ACO has many advantages, however, the complicated calculations cause long processing time and converge slowly,and easily fall into local optimal solution.

In recent years, differential evolution (DE) [22] is widely concentrated and applied, especially for multi-targets assignment and path planning. Zhao and Huang present an improved DE algorithm,aiming at the problem that UAV cooperative multi-targets assignment in 3D environments which makes it difficult to model and calculate [23,24]. An approximate clustering dual-strategy DE algorithm is proposed to improve the efficiency of obtaining the optimal solution.An improved discrete DE algorithm is imported in the interval-valued intuition fuzzy decision making, aiming at multiple UAV task assignment [25]. Wang establishes a weapontarget assignment (WTA) model and proposes a self-adaptive DE algorithm to get better parameters of the WTA [26]. In addition,there are many studies about the UAV route planning based on DE algorithm. It is generally accepted that the collaborative path planning for UAV as inequality constrained optimization problems.A series of improved DE algorithms have been proposed to solve the UAV path planning problem, especially in 3D environments[27-29]. An improved DE algorithm adopts B-Spline curve is presented to obtain a 3D online optimum route[30].Zhang develops a DE algorithm with the exponential selection to get better planning route[31].Aiming at the UAVs dynamic path planning,an improved DE algorithm is adopted[32].Lei presents an effective DE algorithm with hybrid strategy to obtain an optimal path [33].

Same as other heuristic algorithms,there are some drawbacks to DE algorithm, such as early convergence and stagnation. Hence,many scholars propose some improvements, especially in the combination of DE algorithm and adaptive mechanisms. Among them,JADE has been accepted by most researchers[34].In order to make the parameters of the objective function can be obtained quickly and accurately, Li proposes an enhanced adaptive DE algorithm [35]. In Ref. [36], a fitness-based adaptive DE algorithm is proposed, then the algorithm is optimized by utilizing three adaptive strategies. Tan proposes an improved adaptive DE algorithm with different strategies for mutation factor and crossover factor [37]. Shen presents an adaptive differential evolutionary strategy based on double mutation strategies [38]. Tao [39] introduces an adaptive differential evolutionary strategy using an improved elitist strategy. Meng proposes a novel parameter adaptive DE (PaDE) to solve the shortcomings of many DE variants[40,41].Based on the idea of greedy search,Miguel Leon proposes a new greedy adaptation method to dynamically adjust the mutation factor and crossover rate in DE [42]. M Leon combines RAM and JAPDE to propose RAM-JAPDE algorithm,which can simultaneously adjust the selection probability of control parameter pair and mutation strategy in DE [43]. In Ref. [44], it is pointed out that the performance of DE depends on the selection of mutation factor and crossover probability. As on this, a method of setting the control parameters of the differential evolution method is proposed.

In this paper,aiming at the difficulties of single UAV multi-task execution in a three-dimensional environment,and answering how to make UAVs reasonably allocate the execution order of targets in UAV missions and improve efficiency under complex threedimensional terrain environments and multiple constraints, a new adaptive differential evolution algorithm is proposed. In the solution process, the three-dimensional voyage cost is used to express the allocation relationship between the UAV and the target,and the dynamic adaptive mutation and cross-differential evolution strategy are combined to adjust the balance of detection and development in algorithm search to avoid falling into local optimality.The accuracy of task execution is improved,and it is suitable for solving larger-scale target execution tasks. Firstly, a single UAV multitasking model and its related constraints are established in a three-dimensional environment. Secondly, an adaptive evolutionary algorithm based on population iteration times and individual fitness values to adjust the mutation factor and crossover factor is proposed to solve the problem of exploratory and exploitive balance existing in the current evolutionary process.Thirdly, through different scales of simulation experiments, the rationality of the IADE algorithm is proved.Finally,the comparative experiments with other algorithms show the superiority of the IADE algorithm.

The rest of this article is organized as follows. Section 2 mainly explains the UAV multitasking model, various of constraints and corresponding mathematical formulations. Section 3 introduces the IADE algorithm. In Section 4, the simulation experiments are carried out and compared with other algorithms. Section 4 summarizes the whole article and proposes the work to be done in the future.

2. UAV multi-targets assignment model

2.1. Objective function

UAV multitasking is a constrained optimization problem (COP).As usual,this kind of problem contains both equality and inequality constraints. According to the optimization theory, the mathematic description of COP is as follows:

where x?D represents the decision variable of optimization problem,f（x）is the objective function,which depicts targets to be optimized, hi（x） and gj（x） respectively expresses the equality constraint and inequality constraint.

From the description above,connecting with specific problem of UAV multitasking, assumption can be made that a single UAV attacks multiple targets or executes multi-tasks in different areas of the mission space.The key to solve this problem is to obtain attack and execution sequence, making the UAV have the shortest flight distance and minimum flight time that satisfy all constraints.

The objective function of UAV multitasking model can be described as follows:

where djis the flight distance from UAV to target j, wjis the objective weight of j, and its range is between 0 and 1, and the larger the value, the higher the priority, tjdenotes the UAV flight time to target,ckrepresents the constraint violation,α and β denote the scaling factors which are used to balance the polynomial of the objective function, keeping the voyage cost, flying time and constraint violation in the same order of magnitude. Djrepresents the decision variable,which determines the target to be performed by the UAV.As shown in Fig.1,the 3D environment and application scenarios are displayed.

Fig.1. Application scenario in three-dimensional environment.

2.2. Constraint relation

(1) Maximum flying distance constraint Maximum flying distance constraint represents the performance and fuel consumption index of UAV, which is the UAV maximum range limit in the process of completing all missions.The key to this constraint is to ensure that the UAV can complete all targets, otherwise, it will be penalized. The constraint function is written as:

where djis the estimated cost of voyage, D represents the UAV maximum range limit.C1violdenotes the constraint violation that it will be penalized if the UAV exceeds the maximum flying distance while performing the j-th task.

(2) Airspeed constraint

where V（j）minand V（j）maxrespectively represents the maximum speed and minimum speed of UAV; C2violrepresents that the UAV will be punished if it flies beyond the speed range of the specified minimum and maximum speed.

(3) Maximum flying time constraint

Maximum flying time constraint represents the total time elapsed for the UAV to complete all missions. The key to this constraint is to ensure that the UAV completes all missions within the specified flight time.

where C3violrepresents that the UAV will be punished if it surpasses the maximum flying time.

(4) Timing constraint between target points

Timing constraint reflects the execution order among the target points.Priority to important target points must take precedence on execution, thus other target points will be performed in order according to their constraints.

where Tj

(5) Maximum number of tasks to execute constraint.

The maximum number of missions performed by the UAV is represented by this constraint

where Mj

3. Improved adaptive differential evolution

3.1. Standard differential evolution

The DE algorithm first initializes the population,and then carry out mutation, crossover and selection operations to continuously iterate and update the population size. The steps of DE algorithm are as follows:

(1) Initial population

DE algorithm randomly generates NPindividuals within the dimension D of the search range of the solution according to

(2) Mutation

The DE algorithm often use some fixed mutation strategies to generate mutant individuals vito ensure the diversity of the population. The deterministic mutation strategies in DE algorithm are shown below:

Where xbestdenotes the best individual,F is the scaling factor r1r2r3r4, r5represent distinct random integers on [1, NP] and are not equal to i.

(3) Crossover

The basic principle of crossover operation is to generate experimental vector after parameter hybrid of mutation vector and predetermined vector. The specific expression is as follows:

where CR is the crossover probability; jrand represents a random integer on [1,D].

(4) Selection

The main idea of the DE algorithm is to select the next generation of individuals according to the law of greed,which means the excellent individuals are retained and the inferior ones are eliminated.For the optimization problem,the excellent individual has a smaller fitness value.

3.2. JADE

DE/current-to-pbest,as a new mutation strategy,forms the base of JADE which is an adaptive DE algorithm and is with optional archive.

where randc is the Cauchy distribution,if Fi>1,let Fibe equal to1,or regenerate Fiif Fi≤0, initialize uFto 0.5 and updated by as follows:

where c is the value within interval (0,1), SFdenotes the set of all excellent mutation factors.

In JADE, CR is generated independently from a normal distribution which has a mean of uCRand a standard deviation of 0.1.

where meanAdenotes the average value, and SCRis the set of all excellent CRi.

3.3. PaDE

In the whole evolution process,k groups are maintained where all individuals are classified in for evolution in PaDE algorithm.Then, uFcan be updated according to the following equation.

Furthermore, the selection probability is updated according to the following equation.

In order to adapt to dynamic changes for the population size, a new scheme for reducing the size of the parabolic population is proposed.

Presenting a new mutation strategy with time stamp can help to initialize all the inferior individuals in the first stage, followed by the insertion into the external archive.

3.4. RAM-JAPDE

RAM-JAPDE is a combination of Rank-Based Adaptation of Mutation Strategies (RAM) and Joint Adaptation of Parameters in DE(JAPDE) to produce a new algorithm. The main process and calculation formulas of RAM-JAPDE algorithm are as follows:

3.5. Improved mechanisms

Among many adaptive DE algorithms, mutation and crossover operation are two important steps in DE family.The improvement is mainly aimed at F and CR,whose values are of great significance to whether the algorithm can avoid falling into the local optimum and find the global optimal solution.

For F, it should be as large as possible in the pre-phase of evolution, and quickly approach to the global optimal solution,avoiding trapping in local optimum. The population is clustered around the global optimal solution in later period, so the F value should be as small as possible to improve the search accuracy and find the global optimal solution.

CR determines the number of mutated individuals that can enter the selection operation.If the value of CR is large,the offspring will inherit less information from the parent, and the population renewal mainly depends on the process of mutation, which not only enriches the diversity of the population,but also improves the ability of global search.If the value of CR is small,the search of the offspring will mainly focus on the surrounding of the parent generation, which will narrow the optimization range, but will improve the convergence speed, which is beneficial for local optimization.

Since the F and CR values of many DE variants are generated randomly, independent of the number of iterations and individual fitness values,its convergence is not as good as expected.For these problems,an improved adaptive DE algorithm is presented(IADE).In order to make the mutation factor adjust to the extent of evolution, a new dynamic adaptive mutation factor is proposed. The specific expression is as follows:

where g represents gth generation,G denotes the total generations of evolution, Fmaxand Fminrespectively denotes respectively denotes the maximum and minimum values of the mutation factor.

The crossover factor CR controls the degree to which each dimension of individual parameters participates in the crossover step, in order to make it change with the individual fitness values and ensure the stability of algorithm convergence, presenting a dynamic adaptive crossover factor. The specific expression is as follows:

where CRuand CRlrespectively represents the minimum and maximum limits of CR, fiis the individual fitness value, fmaxrepresents the largest value, fbestdenotes the best value.

In view of the above description, Fig. 2 is the algorithm flowchart of IADE.

4. Experiments and analysis

To verify the performance of the IADE algorithm solving how a single UAV attacks multiple targets or executes multi-tasks, simulation experiments have been carried out,and the IADE algorithm is simultaneously compared with other algorithms.

4.1. Performance of the IADE algorithm

To prove the validity of the ability of the algorithm to find the optimal solution without falling into the local optimal solution,two experiments are conducted with different target numbers: experiment 1 has a smaller target scale,while experiment 2 has a larger target scale. Before the experiment, we firstly established the 3D space topographic map, and set the initial position of UAV and target points, as well as some parameters of UAV itself.

Table 1 shows some initializations of the UAV's own parameters,where Num is the UAV number,Position denotes the initial position of UAV, D represents the flight range of UAV, V describes the maximum and minimum flight speeds of UAV and N denotes the maximum number of missions performed by UAV per flight.

Table 2 sets the number and location of target points, T is the number of targets.

Parameters setting of the two groups of experiments are shown in Table 3. Where Target is target points, P is individuals in the population, G represents the number of evolutionary iterations,Num denotes the number of times the program is run.

Fig. 3 shows the optimal simulation results of two groups of experimental UAV attacking targets in the three-dimensional environment. The yellow circle indicates the starting position of the UAV,the yellow stars indicate the location of the target points,the red line indicates the order in which the UAV executes the target points.

Fig. 2. The algorithm flowchart of IADE.

Table 1 Initialization of UAV parameters.

Fig. 4 shows the convergence curves of the two groups of experiments. It can be seen that due to the small number of target points in Experiment 1, the algorithm gets the optimal solutionfrom the beginning till the end of evolution. Experiment 2 converges to the optimal solution at about generation 50, which indicates that the IADE algorithm has good convergence in the early stage of evolution.From the convergence curve of Experiment 2,it can be seen that the algorithm still converges half way through execution, which proves that the algorithm can effectively obtain the optimal solution under the joint action of the adaptive mutation factor and the adaptive crosssover factor, so as to ensure the balance between detection and development.

Table 3 Set evolution parameters.

Table 4 lists the statistical data of the results of the two groups of experiments. Where Avgtime denotes the average algorithm execution time, Bestcost represents the optimal total voyage cost,Avgcost represents the average total cost of the voyage, Optimal denotes the efficiency of obtaining the optimal solution, which is defined as a percentage.According to the results of thetwo groups of experiments,the IADE algorithm can solve the UAV multitasking problem well, which can get the optimal solution.

By comparing the results of the two experiments, although the large-scale experiment 2 adds to the complexity of the UAV multitasking problem,the IADE algorithm can still find the optimal solution within limited time, and the optimal solution proportion reaches 92.5%.The scale of Experiment 1 is relatively small,which indicates that the algorithm can quickly get the optimal solution,and the running time is short, and the efficiency of the optimal solution reaches 97.5%.Although the tasks in experiment 2 is twice as large as that in experiment 1, the average running time of the optimal solution obtained by the two groups of experiments is at the same order of magnitude,which indicates that it is suitable for solving multitasking problems of different scales with high efficiency, and the Avgcost is close to the Bestcost.

Table 5 shows the optimal allocation results of the two groups of experiments.

4.2. Comparison with other algorithms

To further verify the validity and rationality of IADE algorithm,comparison of this algorithm, DMDE algorithm and standard DE algorithm is also made. The comparative experiments are carried out in the exact same simulation environment. Table 6 is the experimental results. The simulation results and convergence curves of each algorithm are respectively shown in Fig.5,Fig.6 and Fig. 7.

Through the comparative experiments, it can be seen that the IADE algorithm has the shortest execution time, the fastestconvergence speed, the lowest average flight cost and the highest efficiency in obtaining the optimal solution. Although the DEDM algorithm[17]performs well in multi-UAV cooperative multi-target assignment, it performs poorly in dealing with single-UAV multitasking,especially when the scale of the task is relatively large.TheDEDM algorithm has the longest running time and the highest average flight cost, and the efficiency of obtaining the optimal solution is only 30 %. Although standard DE algorithm is better than DMDE algorithm, its execution time is relatively longer compared with IADE algorithm. The efficiency of obtaining the optimal solution is 72.5 %, which is 20 % lower than IADE algorithm.

Table 2 Initialization of target coordinates.

Fig. 3. Simulation results of Experiment 1 and Experiment 2.

Fig. 4. Convergence curves of Experiment 1 and Experiment 2.

Table 4 Statistics of the results.

Table 6 Statistics of the results.

Table 5 Assignment results.

Fig. 5. Results and convergence curves of IADE algorithm.

Fig. 6. Results and convergence curves of DMDE algorithm.

Fig. 7. Results and convergence curves of DE algorithm.

5. Conclusions

In this paper,a novel algorithm is proposed to solve the problem of difficult modeling and complex calculation of UAV during multitask execution. The main contributions are as follows:

(1) A single UAV multitasking model and its related constraints are established in a three-dimensional environment.

(2) An adaptive evolutionary algorithm based on population iteration times and individual fitness values to adjust the mutation factor and crossover factor is proposed to solve the problem of exploratory and exploitive balance existing in the current evolutionary process.

(3) Through different scales simulation experiments, the rationality of the IADE algorithm is proved.

(4) The comparative experiments with other algorithms show the superiority of the IADE algorithm.

The future work is to apply the IADE algorithm to UAV path planning.

Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Acknowledgements

This work is not funded and supported by any organization or institute.