Quantum Behavior-Based Enhanced Fruit Fly Optimization Algorithm with Application to UAV Path Planning

Xiangyin Zhang; Shuang Xia; Xiuzhi Li

doi:10.2991/ijcis.d.200825.001

<Previous Article In Issue

Download article (PDF)

Next Article In Issue>

Volume 13, Issue 1, 2020, Pages 1315 - 1331

Quantum Behavior-Based Enhanced Fruit Fly Optimization Algorithm with Application to UAV Path Planning

Authors

Xiangyin Zhang^*^{, 1}^{, 3}^{, 4}^,, Shuang Xia¹^{, 2}^{, 4}, Xiuzhi Li¹^{, 2}^{, 4}

¹Faculty of Information Technology, Beijing University of Technology, Beijing 100124, PR China

²Engineering Research Center of Digital Community, Ministry of Education, Beijing 100124, PR China

³Beijing Laboratory for Urban Mass Transit, Beijing 100124, PR China

⁴Beijing Key Laboratory of Computational Intelligence and Intelligent System, Beijing 100124, PR China

^*Corresponding author. Email: zhangxgyn@foxmail.com

Corresponding Author

Xiangyin Zhang

Received 19 January 2020, Accepted 23 August 2020, Available Online 7 September 2020.

DOI: 10.2991/ijcis.d.200825.001 How to use a DOI?
Keywords: Fruit fly optimization algorithm; Continuous function optimization; Delta potential well; Quantum behavior; Path planning
Abstract: As a newly developed simple and effective optimization technology, the fruit fly optimization algorithm (FOA) has been successfully applied in many fields. To accelerate the algorithm convergence and avoid the local optimum, the enhanced FOA based on quantum theory called QFOA is proposed in this paper. When establishing the quantum Delta potential well around the location of fruit fly swarm, QFOA introduces the quantum behavior-based searching mechanism into the original osphresis-based search procedure of FOA. In the process that fruit flies find and move toward the food source, fruit flies follow the wave function property of the Delta potential well rather than the Newtonian mechanics. Taking advantage of the probability and uncertainty of quantum theory, the proposed QFOA can effectively overcome the weakness in premature convergence and easy trapping into local optimum. Since there are two popular models of the basic FOA, this paper also develops two corresponding QFOAs. Experimental results on various benchmark functions show that both the two QFOA models has overall better performance compared with the basic FOA as well as other FOA variants and other well-known optimization algorithms. In addition, the proposed QFOAs are also applied to unmanned aerial vehicle (UAV) path planning problem in the three-dimensional environment, and comparative results about the obtained optimal flight path and population convergence process show the effectiveness of QFOAs.
Copyright: © 2020 The Authors. Published by Atlantis Press B.V.
Open Access: This is an open access article distributed under the CC BY-NC 4.0 license (http://creativecommons.org/licenses/by-nc/4.0/).

1. INTRODUCTION

The complex continuous optimization problem, which is to find the optimal solution that fulfills a set of constraints and achieves the maximum or minimum value of the function [1], is a universal issue, in many mathematical and engineering ﬁelds, such as automatic control, decision-making, signal processing, etc. Many traditional optimization techniques, which often use the gradient strategy, are applied to these problems, such as the integer programming, gradient descent methods, linear programming, and dynamic programming [2]. They are usually based on the single initial individual solution and will achieve the same local solutions when starting from the same initial individual. When dealing with complex practical problems that generally have high dimension, or multiple constraints, or multimodal [3], these traditional optimization techniques easily lead to the high computational complexity and even fail to determine the optimal solutions. To solve the complex optimization problems, population-based intelligent optimization techniques, which usually search for the feasible solution in some random fashion with starting from the initial solution set, have emerged and show their advantages in terms of calculate precision and time complexity [4,5]. These intelligent optimization techniques are generally inspired by the biological social behavior, such as ant colony optimization (ACO) [6], particle swarm optimization (PSO) [7], artificial bee colony (ABC) optimization [8], firefly algorithm (FA) [9], etc., and the evolution process in nature, including differential evolution (DE) algorithm [4,10], genetic algorithm (GA) [11], etc., as well as the physical or chemical phenomenon, such as chemical reaction optimization (CRO) algorithm [12], gravitational search algorithm (GSA) [13], biogeography-based optimization (BBO) [14] algorithm, etc.

The fruit fly optimization algorithm (FOA) is another newly proposed population-based intelligent optimization technique [15], which is originally inspired by the food-finding behavior of fruit flies. FOA is not only very effective to solve complex optimization problems, but also more simple and easy to implement than other existing population-based algorithms [16]. Firstly, the procedure of FOA only takes several lines to code the core part of the algorithm in any programming language. Secondly, FOA has no other additional control parameters besides the maximum number of iteration and population size. Therefore, FOA has widely attracted the attention of many researchers from various fields, including path planning [16,17], flowshop rescheduling [18], multi-dimensional knapsack problem [19], parameter identification [20], controller parameter tuning [21], etc.

FOA has simple operation and acceptable searching capability, however, it also has some shortcomings of the premature convergence and slow convergent speed during the later evolution process. To overcome these shortcomings as well as improve the search efficiency and global search capability, various improved FOA variants have been put forward by researchers [1, 16, 18-20,22-26]. The improved fruit fly optimization (IFFO) algorithm [1] introduces a new parameter to adaptively control the search scope around the fruit fly swarm location and a new solution generating method to enhance the accuracy and convergence rate. The phase angle-encoded FOA with mutation adaptation mechanism (θ-MAFOA) [12] adopts the mutation adaptation mechanism to enhance the balance between the exploitation and exploration ability of the basic FOA, and besides, the phase angle-based-encoded strategy for fruit fly locations is also adopted to achieve the better convergence performance. In the chaotic-enhanced fruit fly optimization algorithm (CFOA) [20], the chaotic sequence is employed to enhance the global optimization capacity of the original FOA. In the multi-swarm fruit fly optimization algorithm (MFOA) [24], several sub-swarms move independently in the search space at the same time and local behavior rules between sub-swarms are employed to explore global optimal. All these improved FOA variants succeed in overcoming the drawback of the original FOA to some degree. However, for the FOA variants, there is still much room for improvement to achieve better performance in terms of either convergence speed or avoiding to trap into the local optimum, especially for the complex practical problems. Generally, the population diversity and the search randomness play the crucial roles in the population-based optimization techniques. In this paper, we proposed the quantum-behaved FOA (QFOA) model, with the purpose that try to take advantage of the uncertainty of quantum theory to further enhance the performance of FOA by enabling fruit flies to have the quantum behavior. Especially, for the two popular standard FOA models in the literatures, two QFOA models are both presented accordingly, as well as the implement processes.

The idea behind quantum theory, of which the theoretical basis is the classical quantum mechanics, is to hijack some of the “spookiness” in the area of physics known as quantum behavior mechanism [27]. For the population-based optimization techniques, solutions can usually show the higher diversity, which helps to achieve the powerful searching capability, when moving according to the quantum behavior rule. For example, the quantum-behaved particle swarm optimization (QPSO) makes particles move following quantum mechanics rather than Newtonian mechanics, and thus, help to enhance the particle’s ability of jumping out of the local optimum [28,29]. The quantum firefly algorithm (QFA) integrates quantum theory into the basic FA and succeed in overcoming the loss of diversity [30].

In this paper, we introduce the quantum theory into the original FOA to achieve more effective performance. In the enhanced FOA, we assume that the fruit flies locate in a quantum world and the Delta potential well exists around the location of fruit fly swarm. When moving in the space to search for the food, fruit flies follow the quantum mechanics and their behaviors have the uncertainty as the wave function. The quantum-behaved strategy can effectively avoid the premature convergence and improve the escaping ability from the local optimum. Numerical results on benchmark functions reveal that the proposed FOA models are superior to the standard FOA models and other FOA variants as well as some state-of-the-art population-based techniques. Then, we apply the proposed QFOA models to the practical complex problem that finds the optimal flight path for unmanned aerial vehicle (UAV) in the three-dimensional (3D) terrain environments with various enemy weapons. Numerical experiments are carried out on various test scenarios and the results show the effectivity of our proposed QFOA models.

The rest of this paper is organized as follows: Overview of the basic FOA is described in Section 2, including common descriptions of two FOA models. Section 3 presents detailed statement and implement process for the models of the proposed QFOA variants. In Section 4, the comparison and simulation results on several benchmark functions are studied. Section 5 presents the application of the proposed QFOA models to the UAV path planning. Experimental results of path planning are shown in Section 6. Section 7 concludes this paper finally.

2. STANDARD FOA MODELS

FOA is a new population-based algorithm for searching global optimization based on the foraging behavior of fruit flies [11]. Fruit flies are superior to other species in terms of olfactory and visual senses. By using their osphresis, fruit flies can find all types of scents floating in the air and explore the direction of food source. After that, fruit flies can find the food source when getting close to the location of food by using their vision.

According to the foraging characteristics of the fruit fly swarm, FOA can be divided into three consecutive operations, namely swarm location initialization, osphresis-based search, and vision-based search. As to the detailed implementation, existing literatures give two different types of mathematical models to describe the three operations, which are summarized and recorded as FOA-1 and FOA-2 in this paper. Both the two FOA models will be described in the following section:

Without loss of generality, the global optimization problem in the continuous domain can be summarized as follows:

minf(x)s.t. xj∈Xmin,Xmax,j=1,2,…,D (1)

where f(x) is the objective function with the D-dimensional decision variable x=x1,x2,…,xD, and X_min and X_max are the lower and upper bounds of the decision space, respectively.

2.1. FOA-1 Model

In 2012, W.T. Pan put forward the basic idea of FOA for the first time [15], and meanwhile, the complete mathematical model was given to describe the three operations of FOA. In this type of FOA model, the decision variable is encoded as the reciprocal of the distance between the fruit fly location and the origin. To avoid confusion, the FOA model appearing in Refs. [9,15,17,19], is recorded as FOA-1, of which the operations are described as follows:

Swarm location initialization

Set the population size M_osp and the maximum number of iterations G_max, and then, the fruit fly swarm location (X_axis, Y_axis) is randomly initialized in the decision space as

Xaxis=rand×Xmax−Xmin+XminYaxis=rand×Ymax−Ymin+Ymin (2)

where rand is the uniform random number within [0,1].

Osphresis-based search

In the osphresis-based search process, the fruit fly swarm generate M_osp new locations of the food source that are randomly around the current location of the fruit fly swarm. The random searching strategy using the osphresis to find the new food location is given by

Xi=Xaxis+randomYi=Yaxis+random (3)

where i = 1, 2, …, M_osp, and random is the random value in the range of [−1,1].

For every location generated by the osphresis-based searching strategy, its smell concentration judgment S_i is the reciprocal of the distance between the location and the origin, as follows:

Disti=Xi2+Yi2 Si=1/Disti (4)

Actually, the smell concentration judgment corresponds to the candidate solution of the objective function in the decision space. The value of the objective function for the candidate solution, which corresponds to the smell concentration of the food source for the smell concentration judgment, is calculated as follows:

Smelli=fSi (5)

Vision-based search

The vision-based searching process of the fruit fly swarm is essentially a greedy selection procedure. The fruit fly swarm observe all the locations generated via the above osphresis-based searching process and select the best location with the minimum smell concentration, as follows:

index=argminSmelli (6)

The best smell concentration Smell_index is compared with Smell_axis of the fruit fly swarm location (X_axis, Y_axis). If Smell_index< Smell_axis, then the fly swarm will fly toward the new location by using vision and (X_axis, Y_axis) will be replaced by (X_index, Y_index). The vision-based search can be described as follows:

Smellaxis=Smellindex Xaxis=Xindex Yaxis=Yindex (7)

The osphresis-based and vision-based searching processes are repeated until the stopping criterion is satisfied. The general procedure of abovementioned operations is shown in Algorithm 1.

Algorithm 1: Procedure of FOA-1

/* Initialization*/

1. Set the generation counter g = 0;

2. Set the number of fruit flies as M_osp;

3. Randomly initialize the fruit fly swarm’s location as [X_axis, Y_axis];

/* Iterative search*/

4. while termination criteria is not satisfied do

5. Generation counter g = g + 1

/* Search using osphresis */

6. for i = 1: M_osp do

7. Generate the random direction and distance as:

X_i = X_axis + random, Y_i = Y_axis + random

8. Compute the distance to the origin as: Di=Xi2+Yi2

9. Calculate judged value of smell concentration as: S_i= 1/D_i

10. Evaluate the smell concentrations as: Smell_i = f(S_i)

11. end for

/* Search using vision */

12. Select the fruit fly that has the best smell concentration:

index = arg max(Smell_i)

13. if [X_index, Y_index] has the better smell than [X_axis, Y_axis], then

14. X_axis = X_index and Y_axis = Y_index

15. end while

2.2. FOA-2 Model

In addition to the above FOA-1 model, there existing another popular mathematical model to describe operations of FOA [1,23], which is recorded as FOA-2 in this paper. The FOA-2 model codes the decision variable using the floating number directly and can be adapted to solve the high-dimensional functions [1]. The operations of FOA-2 model are described as follows:

Swarm location initialization

Firstly, the fruit fly swarm location x_axis = [x_axis,1, x_axis,2, …, x_axis,_D] is randomly initialized as

xaxis,j=rand×Xmax−Xmin+Xmin (8)

where rand is the uniform random generator number in the range of [0,1], j = 1,2,…,D.

Osphresis-based search

In the osphresis-based search process, the M_osp new locations are randomly generated around the current swarm location as

xij=xaxis,j+random (9)

where i = 1, 2, …, M_osp, j = 1,2,…,D, and random is the random value in the range of [−1,1].

Then, the smell concentration is calculated as follows:

Smelli=fxi (10)

where x_i = [x_i₁, x_i₂, …, x_iD].

Vision-based search

The vision-based searching process of the fruit fly swarm is essentially a greedy selection procedure. That is, the fruit fly swarm observer all the locations generated via the above osphresis-based searching process and find out the best location that has the minimum smell concentration, as follows:

index=argminSmelli (11)

Compare the best smell concentration Smell_index with the smell concentration Smell_axis of the current swarm location x_axis. If Smellindex<Smellaxis, then the fly swarm will leave x_axis and fly toward the new location x_index by using vision, as follows:

Smellaxis=Smellindex xaxis=xindex,if Smellindex<Smellaxis(12)

General procedure of the FOA-2 model is shown in Algorithm 2.

Algorithm 2: Procedure of FOA-2

/* Initialization */

1. Set the generation counter g = 0;

2. Set the number of fruit flies as M_osp;

3. Randomly initialize x_axis = [x_axis,1, x_axis,2, …, x_axis,_D] with [X_min, X_max]^D;

/* Iterative search */

4. while termination criteria is not satisfied do

5. Generation counter g = g + 1

/* Search using osphresis */

6. for i = 1: M_osp do

7. Generate random location as x_ij= x_{axis, j} + random, j = 1,2,…D

8. if x_ij> X_max, then

9. x_ij= X_max

10. if x_ij< X_min, then

11. x_ij= X_min

12. Evaluate smell concentrations Smell_i = f(x_i), x_i= [x_i₁, x_i₂,…, x_iD]

13. end for

/* Search using vision */

14. Select the fruit fly that has the best smell concentration:

index = arg max(Smell_i)

15. if f(x_index) < f(x_axis), then

16. x_axis = x_index

17.end while

3. QUANTUM-BEHAVED FOA MODELS

Based on the quantum theory, the fruit fly swarm are assigned to move in the quantum multi-dimensional space. The Delta potential well model is established to increase the uncertainty that the fruit fly sense and move to the food.

3.1. Quantum Delta Potential Well

According to the quantum theory [28], objects are described by the wave function ψ(x, t), rather than the position x and velocity v. Any quantum object has the wave-like properties and can exist in many places at once. In the quantum space, the probability of the object appearing on a spot is proportional to the strength module of the wave function on this spot, as follows:

|ψ(x,t)|2dxdydz=Qdxdydz (13)

where Qdxdydz is the probability of the object appearing on the spot x= (x, y, z) at time t. Thus, the strength module |ψ(x,t)|² is the probability density function satisfying the following equation:

∫−∞+∞|ψ|2dxdydz=∫−∞+∞Qdxdydz=1 (14)

According to the quantum physics, the motion of objects is described by the Schrödinger’s equation as follows:

ih∂∂tψ(X,t)=H^ψ(X,t) (15)

where ħ is a constant called Planck Constant, Ĥ is the Hamiltonian operator which is given by the following equation:

H^=−h2m∇2+V(x) (16)

where m is the object mass and V(x) denotes the potential field of the object.

3.2. Quantum Behavior of Fruit Flies

Hypothesize the fruit fly swarm move in the quantum space, and fruit flies search for the food source in the Delta potential well. In the quantum space, the foraging and random search operations of fruit flies are replaced by the quantum behavior. Both the osphresis and vision of fruit flies become more uncertainty and random, which can help to increase the population diversity.

For simplicity, the one-dimensional space is considered here. If the location of the food source is denoted by x, its potential energy in the one-dimensional Delta potential well is represented as follows:

V(x)=−γδ(x−paxis)=−γδ(y) (17)

where the location of fruit fly swarm p_axis is center of the Delta potential well.

According to the Schrödinger’s equation [7,28], the following normalized wave function can be obtained as

ψ(y)=1Le−|y|/L (18)

where L is the characteristic length of Delta potential well. Therefore, the probability density function is as follows:

Q(y)=|ψ(y)|2=1Le−2|y|/L (19)

The above equation is equated to

y=±L2ln1u (20)

where u is the random number uniformly distributed on (0, 1). Hence, we can obtain the food source location that the fruit fly searches for, which is determined as follows:

x=paxis±L2ln1u (21)

3.3. Quantum-Behaved Searching Mechanism

In my proposed QFOA model, it assumes that a 1-D Delta potential well exists on each dimension at the swarm center attractor point, and the osphresis-based search operation has the quantum properties. The quantum-behaved foraging process of the fruit fly is depicted by the wave function instead of the completely random way.

Compared with the two standard FOA models, both two proposed QFOA models also contain three basic operations, including the swarm location initialization, the osphresis-based search using quantum-behaved mechanism, and the vision-based search. Unlike the standard FOA, the proposed QFOA models execute the quantum-behaved searching mechanism instead of the completely random osphresis-based search which are described in details as follows.

3.3.1. Quantum-behaved searching mechanism of QFOA-1

In the osphresis-based search process, M_osp new locations of the food source are generated in the Delta potential well of which the swarm location (X_axis, Y_axis) is the center. Different from (9), the quantum-behaved searching mechanism for FOA-1 can be given by

Xi=Xaxis±Lx,i2ln1rxYi=Yaxis±Ly,i2ln1ry (22)

where i = 1, 2, …, M_osp, r_x and r_y are the random value in the range of [0,1]. L_x_,_i and L_y_,_i are the Delta potential well characteristic length of the corresponding dimension, which are determined by the last searching location of the fruit fly based on the olfactory as follows:

Lx,i=2b|Xaxis−Xi|Ly,i=2b|Yaxis−Yi| (23)

where g is the current number of iteration and b is contraction-expansion coefficient to control the quantum searching range, which is determined by

b=b1logsig10⋅0.5−g/Gmax+b2 (24)

where b₁ and b₂ are the two parameters to restrict the value range, namely b∈[b2,b1+b2].

3.3.2. Quantum-behaved searching mechanism of QFOA-2

As to the QFOA-2 model, fruit flies search the location of food source in the 1-D Delta potential well around the fruit fly swarm x_axis = [x_axis,1, x_axis,2, …, x_axis,_D] and generate the new food location on each dimension by the following equation:

xij=xaxis,j±Lij2ln1r (25)

where i = 1, 2, …, M_osp, j = 1, 2, …, D, and r is a random number that uniformly distributed in [0,1]. The characteristic length L is determined by

Lij=2b|xaxis,j−xij| (26)

where the parameter b is determined by (24).

3.3.3. Detailed procedure of QFOA models

The detailed implementation procedure of two QFOA models are presented in Algorithms 3 and 4, respectively.

Algorithm 3: Procedure of QFOA-1

/* Initialization*/

1. Set the generation counter g = 0;

2. Set the number of fruit flies as M_osp; set the parameters b₁ and b₂;

3. Randomly initialize the fruit fly swarm’s location as [X_axis, Y_axis] and ensure the judged value of smell concentration S is within the search range [X_min, X_max];

/* Iterative search */

4. while termination criteria is not satisfied do

5. Generation counter g = g + 1;

6. Calculate parameter b = b₁ logsig(10 (0.5 −g/G_max)) + b₂;

/* Quantum-behaved search using osphresis */

7. for i = 1: M_osp do

8. Calculate the characteristic length

L_x,i = 2b|X_axis – X_i|, L_y,i = 2b|Y_axis – Y_i|;

9. while 1 do

10. Generate the random direction and distance as follows:

11. if random > 0.5 then

12. X_i = X_axis+ 0.5 L_x,j ln(1/r_x);

13. else

14. X_i = X_axis– 0.5 L_x,j ln(1/r_x);

15. if random > 0.5 then

16. Y_i = Y_axis+ 0.5 L_y,j ln(1/r_y);

17. else

18. Y_i = Y_axis– 0.5 L_y,j ln(1/r_y);

19. Calculate the distance to the origin:

Di=Xi2+Yi2;

20. Calculate judged value of smell concentration:

S_i= 1/D_i;

21. if S_i≤ X_max and S_i≥ X_minthen

22. break;

23. end while

24. Evaluate the smell concentrations:

Smell_i = f(S_i);

25. end for

/* Search using vision */

26. Select the fruit fly that has the best smell concentration:

index = arg max(Smell_i);

27. if [X_index, Y_index] has the better smell than [X_axis, Y_axis], then

28. X_axis = X_index and Y_axis = Y_index;

29. end while

4. RESULTS FOR FUNCTION OPTIMIZATION

To show the advantage of the proposed QFOA models, the standard FOA models [1,15], as well as some existing improved FOA variants, e.g., IFFO [1], MFOA [24], and θ-MAFOA [16] are used to compare. Besides, three typical papulation-based algorithms are also compared with the proposed QFOA, including PSO [7], DE [4], ABC [8]. All algorithms are coded using Matlab-2009a according to their original references, and no commercial algorithm tools are used. The experiments are performed on a computer with Intel(R) Core(TM) i5-4590 @ 3.3GHz CPU and 8 GB RAM under Win-7 platform. Each algorithm is run 50 times independently for every benchmark function and the statistical results are used to evaluate and compare the performance of the algorithm.

Algorithm 4: Procedure of QFOA-2

/* Initialization */

1. Set the generation counter g = 0;

2. Set the number of fruit flies as M_osp; set parameters b₁ and b₂;

3. Randomly initialize x_axis= [x_axis,1,x_axis,2,…,x_axis, _D] with [X_min, X_max]^D;

/* Iterative search */

4. while termination criteria is not satisfied do

5. Generation counter g = g + 1;

6. Calculate the parameter b = b₁ logsig(10 (0.5 − g/G_max)) + b₂;

/* Quantum-behaved search using osphresis */

7. for i = 1: M_osp do

8. for j = 1: D do

9. Calculate the characteristic length

L_ij = 2b|x_axis, _j− x_ij|;

10. while 1 do

11. Generate the random location as follows:

12. if random > 0.5 then

13. x_ij= x_axis,_j + 0.5 L_ijln(1/r);

14. else

15. x_ij = x_axis, _j– 0.5 L_ijln(1/r);

16. if x_ij≤ X_max and x_ij≥ X_minthen

17. break;

18. end while

19. end for

20. Evaluate the smell concentrations:

Smell_i = f(x_i), x_i= [x_i1, x_i2, …, x_iD];

21. end for

/* Search using vision */

22. Select the fruit fly that has the best smell concentration:

index = arg max(Smell_i);

23. if f(x_index) < f(x_axis), then

24. x_axis = x_index;

25. end while

4.1. Test Functions

We considered eight typical benchmark functions with dimensions equal to 10 and 20 (i.e., D = 10 and D = 20), which are commonly used in the literatures [1,7,24]. The test functions include four unimodal (F₁, F₂, F₃, F₄) and four multimodal functions (F₅, F₆, F₇, F₈). For all the tested functions, we set the optimum o=1D.

F₁: Shifted Sphere Function

F1(x)=∑i=1Dzi2, z=x−o,

x=x1,x2,⋯,xD_,o=o1,o2,⋯,oD

where x∈[−100, 100]^D, the global optimum x*=o, and F₁(x*)=0.
F₂: Shifted Schwefel’s Problem 1.2

F2(x)=∑i=1D∑j=1izj2, z=x−o,

x=x1,x2,⋯,xD_,o=o1,o2,⋯,oD

where x∈[−100, 100]^D, the global optimum x*=o, and F₂(x*)=0.
F₃: Shifted Rotated High Conditioned Elliptic Function

F3(x)=∑i=1D106i−1D−1zi2, z=x−o,

x=x1,x2,⋯,xD, o=o1,o2,⋯,oD

where x∈[−100, 100]^D, the global optimum x*=o, and F₃(x*)=0.
F₄: Shifted Step Function

F4(x)=∑i=1D⌊zi+0.5⌋2_,z=x−o_,

x=x1,x2,⋯,xD_,o=o1,o2,⋯,oD

where x∈[−100, 100]^D, the global optimum x*=o, and F₄(x*)=0.
F₅: Shifted Rosenbrock’s Function

F5(x)=∑i=1D−1100zi2−zi+12+zi−12_,z=x−o_,

x=x1,x2,⋯,xD_,o=o1,o2,⋯,oD

where x∈[−10, 10]^D, the global optimum x*=o, and F₅(x*)=0.
F₆: Shifted Rotated Ackley’s Function with Global Optimum on Bounds

F6(x)=−20exp−0.21D∑i=1Dzi2−exp1D∑i=1Dcos(2πzi)+20+e_,z=x−o_,

x=x1,x2,⋯,xD_,o=o1,o2,⋯,oD

where x∈[−32, 32]^D, the global optimum x*=o, and F₆(x*)=0.
F₇: Shifted Rastrigin’s Function

F7(x)=∑i=1Dzi2−10cos(2πzi)+10_,z=x−o_,

x=x1,x2,⋯,xD_,o=o1,o2,⋯,oD

where x∈[−5.12, 5.12]^D, the global optimum x*=o, and F₇(x*)=0.
F₈: Shifted Rotated Griewank’s Function without Bounds

F8(x)=14000∑i=1Dzi2−∏i=1Dcos⁡(zii)+1,z=x−o

x=x1,x2,⋯,xD_,o=o1,o2,⋯,oD

where x∈[−600, 600]^D, the global optimum x*=o, and F₈(x*)=0.

4.2. Parameter Setting

The parameter settings of all tested algorithms are as follows:

QFOA-1 and QFOA-2: set the population size as M_osp= 10D and the maximum number of function evaluation as fes = 5000D, as well as the parameters are set as b₁= 1 and b₂= 0.5 for both two QFOA models.
FOA-1 and FOA-2: the population size and the maximum number of function evaluation are set as M_osp= 10D and fes = 5000D.
IFFO: set M_osp= 10D and fes = 5000D; in addition, set parameters λ_max= 0.5 and λ_min= 0.01 according to the original literature [1].
MFOA: set M_osp= 10D and fes = 5000D as well as parameter M = 10 according to the original literature [24].
θ-MAFOA: set M_osp= 10D and fes = 5000D as well as the Cr = 0.9 according to the original literature [13].
PSO: set the population size as M_pop= 10D and the maximum number of function evaluation is fes = 5000D; other parameters are set as c₁= c₂= 0.5, w_max= 0.9 and w_max= 0.4 [2].
DE: set M_pop= 10D and fes = 5000D; other parameters are set as F = 0.6 and cr = 0.9 [9].
ABC: set M_pop= 10D, fes = 5000D and Limit = 50 [8].

All the above parameters values are set according to the suggestions in related literatures, where these values have been proved to lead to the good performance, empirically.

4.3. Comparison and Discussion

The mean best function values of the 50 independent trials for each combination of benchmark function and tested algorithm are recorded in Table 1, while the corresponding minimum best function values of the 50 independent trials are recorded in Table 2.

D	F	QFOA-1	QFOA-2	FOA-1	FOA-2	IFFO	MFOA	θ-MAFOA	PSO	DE	ABC
10	F₁	4.51×10⁻²⁹	2.47×10⁻²⁸	2.40×10⁻¹	3.78×10⁻¹	5.90×10⁻⁵	3.70×10⁻¹⁵	2.95×10⁻¹⁰	8.14×10⁻⁶	3.14×10⁻⁶	2.25×10⁻⁷
	F₂	5.26×10⁻¹⁴	6.78×10⁻¹²	3.32×10⁻¹	3.70×10⁻¹	6.96×10⁻¹	3.25×10⁻⁹	4.24×10⁻⁹	2.42×10⁻¹	1.01	7.46
	F₃	1.09×10⁻¹²	9.97×10⁻²⁵	9.59×10²	1.19×10⁵	6.08	2.62×10⁵	5.04×10⁻⁶	8.03×10⁻⁵	2.70×10⁻⁴	4.58×10⁻³
	F₄	0	0	0	0	0	0	0	0	0	0
	F₅	4.26	4.47	2.89×10¹	1.35×10³	2.82×10¹	2.08×10¹	9.00	9.36	6.78	3.26×10¹
	F₆	2.32×10⁻¹⁴	3.06×10⁻¹⁴	1.45	1.57×10¹	2.76×10⁻³	2.48×10⁻⁸	2.20×10⁻⁵	2.39×10⁻⁴	1.14×10⁻³	4.01×10⁻¹
	F₇	3.104	1.58×10⁻¹⁶	2.65×10¹	3.74×10¹	2.63×10⁻⁵	1.45×10¹	4.85	1.07×10¹	2.13×10¹	1.60×10⁻⁵
	F₈	4.22×10⁻¹⁷	6.22×10⁻²	2.63×10⁻²	4.26×10¹	3.71×10⁻²	1.19×10⁻¹	3.01×10⁻¹¹	4.93×10⁻¹	4.96×10⁻¹	4.68×10⁻²
20	F₁	4.43×10⁻²⁰	2.94×10⁻¹⁴	1.24	1.82	1.20×10⁻⁴	9.25×10⁻¹³	3.35×10⁻⁹	8.34×10⁻¹	4.57×10⁻⁵	8.86×10⁻⁶
	F₂	5.01×10⁻⁴	1.02×10⁻²	2.22	2.70	2.46×10¹	4.68×10⁻⁴	2.07×10⁻⁷	3.84	5.72×10³	2.60×10²
	F₃	1.04×10¹	2.46×10⁻⁸	1.03×10⁴	7.37×10⁵	1.42×10¹	1.31×10⁶	3.94×10⁻⁴	1.23×10²	7.90×10⁻³	1.41×10⁻¹
	F₄	0	0	2.20×10⁻¹	1.52	0	0	0	8.00×10⁻¹	0	0
	F₅	1.53×10¹	1.99×10¹	1.65×10²	1.90×10³	6.21×10¹	1.74×10¹	1.90×10¹	2.27×10²	6.63×10¹	7.47×10¹
	F₆	9.51×10⁻¹¹	1.55×10⁻⁸	2.29	1.87×10¹	2.89×10⁻³	3.71×10⁻⁷	4.96×10⁻⁵	3.87×10⁻¹	2.45×10⁻³	1.04×10¹
	F₇	8.68	1.06×10⁻¹²	8.41×10¹	1.31×10²	5.80×10⁻⁵	5.42×10¹	9.43	2.04×10¹	8.28×10¹	6.51×10⁻⁵
	F₈	8.91×10⁻¹⁵	4.37×10⁻²	8.10×10⁻²	5.82×10⁻¹	1.56×10⁻²	8.82×10⁻³	2.21×10⁻¹⁰	8.92×10⁻¹	3.18×10⁻¹	3.27×10⁻²

Note: MFOA, multi-swarm fruit fly optimization algorithm; QFOA, quantum-behaved fruit fly optimization algorithm; FOA, fruit fly optimization algorithm; IFFO, improved fruit fly optimization; θ-MAFOA, angle-encoded fruit fly optimization algorithm with mutation adaptation mechanism; PSO, particle swarm optimization; DE, differential evolution; ABC, artificial bee colony.

Table 1

Mean optimization results on benchmark functions.

D	F	QFOA-1	QFOA-2	FOA-1	FOA-2	IFFO	MFOA	θ-MAFOA	PSO	DE	ABC
10	F₁	0	1.23×10⁻³²	8.03×10⁻²	1.77×10⁻¹	6.80×10⁻⁶	2.16×10⁻¹⁶	1.67×10⁻¹¹	6.65×10⁻¹⁴	5.58×10⁻⁷	6.36×10⁻⁹
	F₂	1.97×10⁻²⁴	1.30×10⁻¹⁵	1.53×10⁻¹	1.40×10⁻¹	1.99×10⁻¹	1.02×10⁻¹⁰	6.97×10⁻¹⁰	4.37×10⁻³	2.31×10⁻¹	4.26×10⁻¹
	F₃	0	0	3.41×10²	2.15×10⁴	1.41×10⁻¹	2.85×10⁴	2.32×10⁻⁷	5.64×10⁻¹⁰	7.05×10⁻⁵	1.12×10⁻⁵
	F₄	0	0	0	0	0	0	0	0	0	0
	F₅	2.38	2.50×10⁻³	2.03×10¹	1.62×10¹	5.77×10⁻²	3.46	9.00	5.25	3.71	1.37×10⁻²
	F₆	4.44×10⁻¹⁵	4.44×10⁻¹⁵	9.43×10⁻¹	1.32	1.28×10⁻³	8.26×10⁻⁸	8.99×10⁻⁶	1.28×10⁻⁶	4.39×10⁻⁴	4.13×10⁻⁴
	F₇	0	0	1.66×10¹	1.99×10¹	5.37×10⁻⁶	4.97	9.95×10⁻¹	3.98	1.18×10¹	9.26×10⁻⁷
	F₈	0	7.40×10⁻³	1.06×10⁻²	2.39×10¹	9.42×10⁻⁵	3.45×10⁻²	2.54×10⁻¹²	3.34×10⁻¹	3.22×10⁻¹	7.28×10⁻⁶
20	F₁	1.05×10⁻²⁷	7.39×10⁻²⁰	7.58×10⁻¹	1.22	3.05×10⁻⁵	7.51×10⁻¹⁴	1.08×10⁻⁹	3.83×10⁻³	1.75×10⁻⁵	2.28×10⁻⁶
	F₂	2.98×10⁻⁷	3.11×10⁻⁴	1.40	1.83	7.50	6.92×10⁻⁵	9.20×10⁻⁸	2.24	3.54×10³	5.86×10¹
	F₃	1.28×10⁻¹⁸	6.73×10⁻¹⁶	4.93×10³	2.73×10⁵	7.81×10⁻¹	4.38×10⁵	9.50×10⁻⁵	2.49	2.76×10⁻³	5.12×10⁻³
	F₄	0	0	0	0	0	0	0	0	0	0
	F₅	1.26×10¹	2.20×10⁻¹	1.08×10²	1.39×10²	7.39×10⁻¹	1.22×10¹	1.90×10¹	4.45×10¹	3.15×10¹	3.67×10⁻¹
	F₆	7.90×10⁻¹⁴	3.66×10⁻¹¹	1.79	2.66	1.70×10⁻³	1.13×10⁻⁷	3.42×10⁻⁵	3.35×10⁻²	1.52×10⁻³	1.80×10⁻³
	F₇	2.98	7.11×10⁻¹⁵	6.50×10¹	9.72×10¹	2.11×10⁻⁵	2.79×10¹	4.97	7.82	6.30×10¹	1.69×10⁻⁵
	F₈	0	1.22×10⁻¹⁵	5.73×10⁻²	1.46×10¹	1.12×10⁻⁴	7.63×10⁻¹¹	6.54×10⁻¹¹	1.59×10⁻¹	1.12×10⁻¹	9.78×10⁻⁶

MFOA, multi-swarm fruit fly optimization algorithm; QFOA, quantum-behaved fruit fly optimization algorithm; FOA, fruit fly optimization algorithm; IFFO, improved fruit fly optimization; θ-MAFOA, angle-encoded fruit fly optimization algorithm with mutation adaptation mechanism; PSO, particle swarm optimization; DE, differential evolution; ABC, artificial bee colony.

Table 2

Minimum optimization results on benchmark functions.

From Table 1, it can be seen that, in the average sense, two QFOA models show the great advantage in finding the global minimum on all sixteen benchmarks and are significantly superior to the basic standard FOA models on these functions. Compared with other improved FOA variants, two QFOA models achieve the significantly better performance on F₁-F₃ and F₅-F₆ with D = 10 as well as F₁ and F₆ with D = 20. For other functions, such as F₇-F₈ with D = 10 as well as F₃ and F₅-F₈ with D = 20, there is one QFOA model, either QFOA-1 or QFOA-2, that outperforms IFFO, MFOA, and θ-MAFOA. It can be claimed that at least one FOA model performs the best on fifteen functions except for only F₂ with D = 20. Hence, in the average sense, it can be concluded that the proposed QFOA models do not only greatly improve the original standard FOA models, but also significantly exceed other improved FOA variants. Compared with PSO, DE, and ABC, Table 1 shows that both two QFOA models are superior to the three population-based algorithms on ten functions, while at least one QFOA is superior to the three population-based algorithms on all sixteen functions.

Table 2 indicates that the proposed QFOA models have the best performance than other tested algorithms on nine functions, and meanwhile, at least one QFOA outperforms the three population-based algorithms on fifteen functions except for only F₂ with D = 20, on which θ-MAFOA achieves the best performance. Therefore, the proposed QFOA models have absolute superiority in dealing with complex continue optimization problems.

Moreover, to further study the performance of proposed QFOA models comparatively, the performance of all tested algorithms in dealing with benchmark functions are ranked according to the numerous results in Tables 1–2. Table 3 records the rank of mean results of tested algorithms. It can be seen that QFOA-1 wins total eleven first places and QFOA-2 wins six first places and six second places. As to the mean-rank, two QFOA models are in the top two ahead of other tested algorithms. For the rank of minimum results listed in Table 4, QFOA-1 wins total twelve first places and QFOA-2 wins seven first places and seven second places. Two QFOA models are still in the top two much more ahead of other tested algorithms according to the mean-rank. In a word, the proposed QFOA models surpassed the standard FOA models, some improved FOA variants and population-based algorithms.

D	F	QFOA-1	QFOA-2	FOA-1	FOA-2	IFFO	MFOA	θ-MAFOA	PSO	DE	ABC
10	F₁	1	2	9	10	8	3	4	7	6	5
	F₂	1	2	6	7	8	3	4	5	9	10
	F₃	2	1	8	9	7	10	3	4	5	6
	F₄	1	1	1	1	1	1	1	1	1	1
	F₅	1	2	8	10	7	6	4	5	3	9
	F₆	1	2	9	10	7	3	4	5	6	8
	F₇	4	1	9	10	3	7	5	6	8	2
	F₈	1	6	3	10	4	7	2	8	9	5
20	F₁	1	2	9	10	7	3	4	8	6	5
	F₂	3	4	5	6	8	2	1	7	10	9
	F₃	5	1	8	9	6	10	2	7	3	4
	F₄	1	1	8	10	1	1	1	9	1	1
	F₅	1	4	8	10	5	2	3	9	6	7
	F₆	1	2	8	10	6	3	4	7	5	9
	F₇	4	1	9	10	2	7	5	6	8	3
	F₈	1	6	7	9	4	3	2	10	8	5
Mean-rank		1.8	2.4	7.2	8.8	5.3	4.4	3.1	6.5	5.9	5.6

MFOA, multi-swarm fruit fly optimization algorithm; QFOA, quantum-behaved fruit fly optimization algorithm; FOA, fruit fly optimization algorithm; IFFO, improved fruit fly optimization; θ-MAFOA, angle-encoded fruit fly optimization algorithm with mutation adaptation mechanism; PSO, particle swarm optimization; DE, differential evolution; ABC, artificial bee colony.

Table 3

Rank of the mean optimization results.

D	F	QFOA-1	QFOA-2	FOA-1	FOA-2	IFFO	MFOA	θ-MAFOA	PSO	DE	ABC
10	F₁	1	2	9	10	8	3	5	4	7	6
	F₂	1	2	7	6	8	3	4	5	9	10
	F₃	1	1	8	9	7	10	4	3	6	5
	F₄	1	1	1	1	1	1	1	1	1	1
	F₅	4	1	10	9	3	5	8	7	6	2
	F₆	1	2	9	10	8	3	5	4	7	6
	F₇	1	1	9	10	4	7	5	6	8	3
	F₈	1	5	6	10	4	7	2	9	8	3
20	F₁	1	2	9	10	7	3	4	8	6	5
	F₂	2	4	5	6	8	3	1	7	10	9
	F₃	1	2	8	9	6	10	3	7	4	5
	F₄	1	1	1	1	1	1	1	1	1	1
	F₅	5	1	9	10	3	4	6	8	7	2
	F₆	1	2	9	10	6	3	4	8	5	7
	F₇	4	1	9	10	3	7	5	6	8	2
	F₈	1	2	7	10	6	4	3	9	8	5
Mean-rank		1.7	1.9	7.3	8.2	5.2	4.6	3.8	5.8	6.3	4.5

MFOA, multi-swarm fruit fly optimization algorithm; QFOA, quantum-behaved fruit fly optimization algorithm; FOA, fruit fly optimization algorithm; IFFO, improved fruit fly optimization; θ-MAFOA, angle-encoded fruit fly optimization algorithm with mutation adaptation mechanism; PSO, particle swarm optimization; DE, differential evolution; ABC, artificial bee colony.

Table 4

Rank of the minimum optimization results.

In addition, the convergence curves of the ten tested algorithms on the eight benchmark functions are shown in Figure 1(a)-(h) for the dimension D = 10 and in Figure 2(a)-(h) for the dimension D = 20, respectively, where convergence curves show the mean best function values of 50 trials per iteration. Through comparing these convergence curves, it is easy to ﬁnd that the QFOA models have the better convergence performance than other tested algorithms on most benchmark functions. QFOA-1 can converge much more rapidly during the early stage of the search process and then achieve the optimum so quickly. This characteristic is very remarkable on F₁-F₂, F₄-F₆ and F₈ with D = 10 as well as F₁, F₄-F₆ and F₈ with D = 20. On the contrary, QFOA-2 often shows its powerful search capability and accelerates convergence to the optimum during the later stage of the search process. Especially, QFOA-2 converges to the optimum on F₃, F₄, F₇ with D = 10 and 20, and converges to the sub-optimum on F₁-F₂ and F₅-F₆ with D = 10 as well as F₁ and F₆ with D = 20. The proposed QFOA models can not only ﬁnd higher quality solutions but also possess faster convergence speed on benchmark functions.

Analyzing the experiment results, it is clear that, the proposed QFOA models perform significantly better than the standard FOA models, and meanwhile, are superior to or at least competitive with existing improved FOA variants as well as some population-based algorithms. Above all, the proposed QFOA models have faster convergence speed and stronger search capability, which could avoid most of the local optimum and significantly improve the shortcomings of the premature convergence and slow convergent speed during the later evolution process on the continuous function optimization problems.

5. QFOA MODELS FOR UAV PATH PLANNING

5.1. Model of Objective Function of UAV Path

The core work of path planning is to set up an effective objective or cost function which acts as the criterion to evaluate whether a path or a location of fruit fly is good or not [16]. The path planning problem is modeled as an optimization problem that minimizes the objective function. Assume the full UAV path is represented by a collection of discrete waypoints {p₀, p₁, …, p_N, p_N₊₁}, where the coordinate of the waypoint p_k is (xp_k, yp_k, zp_k), k = 0, …, N+1. The objective function of the UAV path can be defined as [31]

minJ=∑i=15fi (27)

where f_i, i = 1,…,5, is the costs of flight length, safety, altitude, turning angle, climbing and gliding slope, and terrain constraint.

The length cost f₁ is defined as the sum of all path segment lengths from the first to last points:

f1=∑k=0Nlkwithlk=xpi+1−xpi2+ypi+1−ypi2+zpi+1−zpi2 (28)

The threat cost f₂ penalizes the paths that fly dangerously close to threat sites, which depends on the length and the threat probability of each path segment as follows:

f2=∑k=0Nlk⋅∑j=1nTPj,kwithPj,k=0dj,k>Rmax,jRmax,j4dj,k4+Rmax,j4dj,k≤Rmax,j (29)

where P_j_,_k is the threat probability of the path segment p_kp_k₊₁ suffering from the j-th threat, R_max,_j denotes the maximum threaten range of the j-th threat, and d_j_,_k is the distance between p_kp_k₊₁ and the j-th threat center.

The altitude cost f₃ is introduced to make the UAV fly at the low altitude, so that the UAV can benefit from the terrain mask effect. Meanwhile, f₃ can penalize the nonfeasible paths that pass through the terrain, as follows:

f3=∑k=1Nfk3withfk3=C,if zpk<Hmapxpk,ypk+Hsafezpk,otherwise(30)

where C is the penalty factor, H_map(xp_k, yp_k) is the ground level at the point (xp_k, yp_k), and H_safe is the minimal safe flight height.

The lateral maneuvering cost f₄ is the sum of those points that do not satisfy the turning constraint as follows:

f4=∑k=1Nfk4withfk4=0,if ϕk≤ϕkmaxC,otherwise (31)

where φ_k denotes the turning angle at the waypoint p_k, and C is the penalty factor. The UAV maneuverability is constrained by the maximum turning angle φ_k^max as follows:

ϕkmax=nmaxgV2⋅xpk+1−xpk2+ypk+1−ypk2(32)

where g is the gravitational acceleration, n_max is the maximum lateral overload and V is the flight velocity.

The vertical maneuvering cost f₅ is the sum of those points that do not satisfy the slope constraint as follows:

f5=∑k=1Nfk5withfk5=0,if βk≤sk≤αkC,otherwise (33)

where s_k is the UAV slope at the waypoint p_k, α_k is the maximum climbing slope and β_k is the minimum gliding slope, which are calculated as follows [4,16]:

αk=−1.5377×10−10zpk2−2.6997×10−5zpk+0.4211βk=2.5063×10−9zpk2−6.3014×10−6zpk−0.3257sk=zpk+1−zpkxpk+1−xpk2+ypk+1−ypk2 (34)

5.2. Path Representation in 3D Environment

The full UAV path is represented by a collection of N discrete waypoints except the given start and target points. Considering each waypoint p_k, k = 1, …, N, are determined by three coordinates (xp_k, yp_k, zp_k), the total dimension of the decision variable in a UAV path is 3N. In order to reduce the problem dimension and meanwhile to obtain the smooth path, the B-Spline-based path representation strategy is adopted in this paper to determine these waypoints and then represent the desired UAV path.

Given n+1 control points with the coordinates (x₀, y₀, z₀), …, (x_n, y_n, z_n), the B-Spline curve can be constructed by [31]

Xt=∑i=0nxi⋅Bi,KtYt=∑i=0nyi⋅Bi,KtZt=∑i=0nzi⋅Bi,Kt (35)

where B_i_,_K(t) is defined recursively as follows:

Bi,1t=1,ifKnoti≤t<Knoti+11,if Knoti≤t≤Knoti+1 and t=n−K+20,otherwise (36)

Bi,Kt=t−Knott⋅Bi,KtKnoti+K−1−Knoti+Knoti+K−t⋅Bi+1,K−1tKnoti+K−Knoti+1(37)

with

Knoti=0,if i<KKnoti=i−K+1,if K≤i≤nKnoti=n−K+2,if n<i

where the order K is used to control the curve smoothness. The parameter t varies from 0 to n−K+2 with a constant step, providing the discrete points of the B-Spline curve.

Using the B-Spline-based path representation, if the UAV path is represented by the collection of discrete waypoints {p₀, p₁, …, p_N, p_N₊₁} with the coordinates (xp_k, yp_k, zp_k), k = 1, …, N, for each waypoint, then the corresponding control point collection is {w₀, w₁, …, w_n, w_n₊₁} with the coordinates (xc_i, yc_i, zc_i), i = 1, …, n. Both the first waypoint p₀and the first control point w₀ are the given start point, while both the last waypoint p_N+1 and the last control point w_n₊₁are the given target point. The task of the path planner is to generate n control points, and thus, these control points can achieve the B-Spline curve-based path together with the given start and target points.

5.3. Path Planning Using QFOA

In order to obtain the optimal UAV flight path, the B-Spline curve-based path connecting the given start and target points should have the minimum value of cost function. Using the proposed QFOA models to design the UAV path planner, the coordinates of the control points are treated as the food source of fruit fly swarm. The number of control points is n, and then, D = 3n parameters {x₁, x₂, …, x_D} should be determined by the path planner, where (x_i, x_n₊_i, x₂_n₊_i), i = 1,2,…,n, denotes the 3D coordinates of the i-th control point w_i. That is to say, (xc_i, yc_i, zc_i) = (x_i, x_n₊_i, x₂_n₊_i). These coordinates take values within the limits of the constrained physics 3D space of the mission map. Each candidate path obtained by path planner is evaluated according to the cost function described in (28), which is employed as the smell concentration judgment function for fruit flies. Suppose that the mission space of the UAV flight path is limited in [0,L_max]×[0,W_max], and the maximum flight altitude is H_max. The following section will show how to apply QFOA models to the path planning problem:

Procedure of path planning using QFOA-1

At the t-th iteration of QFOA-1, locations of the i-th fruit fly is represented by (X_i_,1,X_i_,2,…,X_i_,_D) and (Y_i_,1,Y_i_,2,…,Y_i_,_D), and the judged value of smell concentration (S_i_,1,S_i_,2,…,S_i_,_D) corresponds to the control point coordinates (xc₁,…,xc_n, yc₁,…,yc_n, zc₁,…,zc_n). The detailed implemented procedure of QFOA-1 applied to UAV path planning is described in Algorithm 5.

Procedure of path planning using QFOA-2

For the i-th fruit fly at the t-th iteration in the QFOA-2, both the location and the judged value of smell concentration are represented by (x_i_,1,x_i_,2,…,x_i_,_D), which are treated as the decision variable of the optimization problem. Therefore, for the QFOA-2-based path planning problem, the location of the fruit fly (x_i_,1,x_i_,2,…,x_i_,_D) corresponds to the control point coordinates (xc₁,…,xc_n, yc₁,…,yc_n, zc₁,…,zc_n), and thus can be decoded into a candidate UAV path using the B-Spline curve. The implemented procedure of QFOA-2 applied to UAV path planning is described in Algorithm 6.

Algorithm 5: Procedure of path planning using QFOA-1

/* Mission */

1. Mission information: start and target points (x_S,y_S)^T, (x_T,y_T)^T,

UAV performance parameters,

the number of the control points n..

2. Threat information: threat centres (x_threat _j, y_threat _j)^T,

threat radius R_j.

3. Map information: the mission map range L_max,W_max, H_max.

/* Initialization */

4. Set the generation counter g = 0.

5. Generation counter g = g + 1;

6. Randomly initialize the fruit fly swarm’s location as [X_axis, Y_axis] and ensure the judged value of smell concentration S is within the search range [0, 1] ^D.

/* Iterative search */

7. while termination criteria is not satisfied do

8. Generation counter g = g + 1.

9. Calculate the parameter b = b₁ logsig(10 (0.5 −g/G_max)) + b₂.

/* Quantum-behaved search using osphresis */

10. for i = 1: M_ospdo

11. for j = 1: Ddo

12. Calculate the characteristic length:

L_x_,_i_,_j = 2b|X_axis – X_i_,_j|, L_y_,_i_,_j = 2b|Y_axis – Y_i_,_j|.

13. while 1 do

14. Generate the random direction and distance as follows:

15. if random > 0.5 then

16. X_i_,_j = X_axis,_j+ 0.5 L_x_,_i_,_j ln(1/r_x);

17. else

18. X_i_,_j = X_axis,_j− 0.5 L_x_,_i_,_j ln(1/r_x).

19. if random > 0.5 then

20. Y_i_,_j = Y_axis,_j + 0.5 L_y_,_i_,_j ln(1/r_y)

21. else

22. Y_i_,_j = Y_axis,_j − 0.5 L_y_,_i_,_j ln(1/r_y).

23. Calculate the judged value of smell concentration:

Si,j=1/Xi,j2+Yi,j2.

24. if S_i_, _j≤ 1 then

25. break.

26. end while

27. end for

/* Evaluation */

28. Set (xc₀, yc₀, zc₀)^T as the coordinates of the start point.

29. for j = 1: ndo

30. xc_j= S_i_,_j× L_max

31. yc_j= S_i_,_n₊_j× W_max

32. zc_j= S_i_,2_n₊_j× H_max

33. end for

34. Set (xc_n₊₁, yc_n₊₁, zc_n₊₁)^T as the coordinates of the target point.

35. Generate the B-Spline curve using the control points (xc₀, yc₀, zc₀)^T, …, (xc_n₊₁, yc_n₊₁, zc_n₊₁)^T.

36. Evaluate smell concentrations (the cost value) according to (27):

Smell_i = J(Path_i), Path_i= [(xc₀,yc₀,zc₀)^T,…,(xc_n₊₁,yc_n₊₁, zc_n₊₁)^T].

37. end for

/* Search using vision */

38. Select the fruit fly that has the best smell concentration:

index = arg max(Smell_i).

39. if [X_index, Y_index] has the better smell than [X_axis, Y_axis], then

40. X_axis = X_index and Y_axis = Y_index.

41. end while

/*Output*/

42. Decode and output the best path for UAV.

Algorithm 6: Procedure of path planning using QFOA-2

1. Mission information: start and target points (x_S,y_S)^T, (x_T,y_T)^T,

UAV performance parameters,

the number of the control points n.

2. Threat information: threat centres (x_threat_j,y_threat_j)^T,

threat radius R_j.

3. Map information: the mission map range L_max,W_max, H_max.

/* Initialization */

4. Set the generation counter g = 0.

5. Set the number of fruit flies as M_osp as well as parameters b₁, b₂.

6. Randomly initialize x_axis = [x_axis,1, x_axis,2, …, x_axis,_D] with [0, 1] ^D.

/* Iterative search */

7. while termination criteria is not satisfied do

8. Generation counter g = g + 1.

9. Calculate the parameter b = b₁ logsig(10 (0.5 −g/G_max)) + b₂.

/* Quantum-behaved search using osphresis */

10. for i = 1: M_ospdo

11. for j = 1: D do

12. Calculate the characteristic length:

L_i_j= 2b|X_axis,j – X_ij|.

13. while 1 do

14. Generate the random direction and distance as follows:

15. if random > 0.5 then

16. X_i,j = X_axis,j+0.5 L_i,jln(1/r_x);

17. else

18. X_i,j = X_axis,j–0.5 L_i,jln(1/r_x).

19. if random > 0.5 then

20. break

21. end while

22. end for

/* Evaluation */

23. Set (xc₀, yc₀, zc₀)^T as the coordinates of the start point.

24. for j = 1: ndo

25. xc_j = x_i,j× L_max

26. yc_j = x_i,n₊_j× W_max

27. zc_j = x_i,2n₊_j× H_max

28. end for

29. Set (xc_n₊₁, yc_n₊₁, zc_n₊₁)^T as the coordinates of the target point.

30. Generate the B-Spline curve using the control point set (xc₀, yc₀, zc₀)^T, …, (xc_n₊₁, yc_n₊₁, zc_n₊₁)^T.

31. Evaluate smell concentrations (the cost value) according to (27):

Smell_i= J(Path_i), Path_i= [(xc₀,yc₀,zc₀)^T,…, (xc_n₊₁,yc_n₊₁,zc_n₊₁)^T].

32. end for

/* Search using vision */

33. Select the fruit fly that has the best smell concentration:

index = arg max(Smell_i).

34. if [X_index, Y_index] has the better smell than [X_axis, Y_axis], then

35. X_axis = X_index and Y_axis = Y_index.

36. end while

/*Output*/

37. Decode and output the best path for UAV.

6. EXPERIMENT RESULTS

To evaluate our designed QFOA-based path planners, several comparison simulations are carried out. We mainly concern the performance of the proposed QFOA algorithms versus the original standard FOA models, and thus, the QFOA-1, QFOA-2, FOA-1, and FOA-2 are tested under two scenarios in this section. All the tested algorithms are coded using Matlab-2009a on a personal computer. Due to the randomness nature of swarm intelligence algorithms, every tested algorithm is run 50 times independently for each scenario and the statistical results are used for evaluation and comparison. The mission map is a rectangular region with known terrain and threat environments. The number of the B-Spline control points is set as n = 4, which means the dimension of the problem is D = 3n = 12. Other parameters of the UAV are set as the maximum lateral overload n_max= 5, the minimum safety flight altitude H_safe= 50 m, and the flight velocity V = 200 m/s. To make a fair comparison, the same maximum iteration number is used for all algorithms as the stopping criterion, while the population size is set as M_osp= 40 for all algorithms.

Figures 3 and 4 show the simulation results obtained by QFOA-1, QFOA-2, FOA-1, and FOA-2 on two different scenarios during 50 independent runs. The best UAV paths obtained by the four algorithms on two different scenarios are projected on the xoy contour plane as shown in Figures 3(a) and 4(a), respectively. In the maps, the circle dot “∘” in the lower-left corner is the start point, the square dot “□” in the upper-right corner is the target point, and the gray round areas represent the threat regions. As is shown, all algorithms succeed in finding the safe path that completely avoids all the threat regions. The change curves of the flight altitude of the best UAV paths along the length for the tested algorithms are displayed in Figures 3(b) and 4(b). Values of the five cost of the obtained best UAV paths for the 1st and 2nd scenarios are compared in Tables 5 and 6. It can be seen that all tested algorithms can achieve the feasible paths that satisfy all threat and altitude constraints, while QFOA-1 and QFOA-2 generates the shorter and lower paths than the original FOA algorithms. The proposed QFOA-based path planner can generate the UAV path with the threat-avoidance and terrain-following characteristics, and thus, increases both the survivability of the aircraft and the effectiveness of mission. Comparing QFOA-1 and QFOA-2, it can be seen that the cost criteria of the best UAV path obtained by QFOA-2 are smaller than those by QFOA-1, which indicates the powerful searching ability of QFOA-2.

Algorithm	f₁	f₃
QFOA-1	114.98	79.24
QFOA-2	117.15	66.25
FOA-1	118.89	132.28
FOA-2	158.45	152.12

UAV, unmanned aerial vehicle; QFOA, quantum-behaved fruit fly optimization algorithm; FOA, fruit fly optimization algorithm.

Table 5

Cost values of the best UAV paths obtained by various algorithms on the 1st scenario.

Algorithm	f₁	f₃
QFOA-1	119.68	177.04
QFOA-2	106.56	156.19
FOA-1	122.41	214.62
FOA-2	121.82	264.83

UAV, unmanned aerial vehicle; QFOA, quantum-behaved fruit fly optimization algorithm; FOA, fruit fly optimization algorithm.

Table 6

Cost values of the best UAV paths obtained by various algorithms on the 2nd scenario.

The statistical results of four tested algorithms during 50 runs on two test scenarios are listed in Tables 7 and 8, where the best, median, mean, worst, and standard deviation of the cost value are recorded. The best values of each column are highlighted using boldface. The search ability and stability of a swarm intelligence algorithm can be reflected by the mean cost value and the standard deviation, respectively. Compared these statistical results, it is observed that QFOA-2 obtains the minimum best, mean, median, and worst cost, which indicates QFOA-2 has the most powerful optimization ability in the statistical sense. QFOA-1 also can obtain the smaller value of all statistical results than the original standard FOA models. The convergence curves of the average best cost values are displayed in Figures 3(c) and 4(c). It can be seen that, QFOA models achieve the faster convergence speed and the smaller cost than FOA models. The global convergence performance can be sorted as QFOA-2 > QFOA-1 > FOA-1 > FOA-2.

Algorithm	Best	Median	Mean	Worst	Std.
QFOA-1	194.22	236.36	259.84	418.38	63.70
QFOA-2	183.40	215.79	244.64	429.97	69.14
FOA-1	251.17	297.32	351.73	682.51	117.44
FOA-2	310.57	407.73	423.55	652.89	65.31

QFOA, quantum-behaved fruit fly optimization algorithm; FOA, fruit fly optimization algorithm.

Table 7

Performance comparison on the 1st test scenario.

Algorithm	Best	Median	Mean	Worst	Std.
QFOA-1	296.72	360.20	328.21	437.77	46.92
QFOA-2	262.75	323.90	325.51	319.19	35.57
FOA-1	337.03	407.66	408.49	564.44	40.28
FOA-2	386.65	572.48	574.79	689.98	55.86

QFOA, quantum-behaved fruit fly optimization algorithm; FOA, fruit fly optimization algorithm.

Table 8

Performance comparison on the 2nd test scenario.

Furthermore, in order to study the distribution of the solutions, the cumulative frequency graphs of the minimum cost values during independent runs are listed in Figures 3(d) and 4(d), where the horizontal axis denotes the cost value and vertical axis denotes the cumulative frequency. Define the cumulative frequency as follows:

Pcumx=N(Jmin≤x)50×100% (38)

where N(J_min< x) is the number of runs that obtain the cost value smaller than x. The result figures clearly show that both QFOA models perform better than original standard FOA. For example, on the 1st test scenario, all cost values obtained by QFOA are distributed in the interval smaller than 450, while only about 70% of FOA-1 trials and 80% of FOA-2 trials can achieve the same performance. As to the 2nd test scenario, 100% of cost values obtained by QFOA-2 are smaller than 350, while 100% of QFOA-1 trials, about 95% of FOA-1 trials and only 5% of FOA-2 trials achieve cost values less than 450. These experimental results demonstrate that QFOAs maintain the higher performance than the original standard FOA models in solving the UAV path planning problem, and meanwhile, QFOA-2 shows the better performance than QFOA-1. Above all, the proposed QFOA models have the advantage over the original standard FOAs in terms of searching ability, stability, and robustness.

7. CONCLUSIONS

This paper introduces the quantum theory into FOA model and replaces the osphresis-based search of FOA as the quantum behavior-based searching mechanism, and thus, proposed the QFOA variant. In QFOA models, the Delta potential well is established around the fruit fly swarm location and fruit flies find and move toward the food source following the rules of wave function. Several comparative studies are conducted based on benchmark functions. Results show the proposed QFOA models are superior to the original standard FOA models and other improved FOA variants, as well as several state-of-the-art population-based algorithms, such as DE, PSO, and ABC. The proposed QFOA show the powerful searching abilities, robustness, and global convergence in solving continuous optimization problems.

In addition, the proposed QFOA models are also successfully applied to solve UAV path planning problem and the QFOA-based path planner are designed. The detailed implemented procedures of the path planning are given. Simulation results on two scenarios show that the proposed QFOA can solve this complex optimization problem and achieve much better performance in terms of searching ability, stability, and robustness than the original standard FOA models, which further indicates that the proposed QFOA is the powerful optimization technique.

It is the first work that take advantage of quantum theory to enhance the original FOA. Another contribution of this paper is that the improvement strategy is simultaneously employed to two standard FOA models. In the future work, we will further investigate the performance of the QFOA models and apply the them to the multi-objective optimization problems.

ACKNOWLEDGMENTS

This work is supported by National Natural Science Foundation of China (No. 61703012), Beijing Natural Science Foundation (No. 4182010).

REFERENCES

1.Q.K. Pan, H.Y. Sang, J.H. Duan, and L. Gao, An improved fruit fly optimization algorithm for continuous function optimization problems, Knowledge Based Syst., Vol. 62, 2014, pp. 69-83.

2.Y.W. Zhang, G.M. Cui, J.T. Wu, W.T. Pan, and Q. He, A novel multi-scale cooperative mutation fruit fly optimization algorithm, Knowledge Based Syst., Vol. 114, 2016, pp. 24-35.

3.R. S. Patwal, N. Narang, and H. Garg, A novel TVAC-PSO based mutation strategies algorithm for generation scheduling of pumped storage hydrothermal system incorporating solar units, Energy, Vol. 142, 2018, pp. 822-837.

4.X.Y. Zhang and H.B. Duan, An improved constrained differential evolution algorithm for unmanned aerial vehicle global route planning, Appl. Soft Comput., Vol. 26, 2015, pp. 270-284.

5.H. Garg, A hybrid PSO-GA algorithm for constrained optimization problems, Appl Mathematics Comput., Vol. 274, 2016, pp. 292-305.

6.W. Gao, New Ant colony optimization algorithm for the traveling salesman problem, Int. J. Comput. Intell. Syst., Vol. 13, 2020, pp. 44-55.

7.Y.G. Fu, M.Y. Ding, and C.P. Zhou, Phase angle-encoded and quantum-behaved particle swarm optimization applied to three-dimensional route planning for UAV, IEEE Trans. Syst. Man. Cybern. A. Syst. Hum., Vol. 42, 2012, pp. 511-526.

8.B. Kruekaew and W. Kimpan, Enhancing of artificial bee colony algorithm for virtual machine scheduling and load balancing problem in cloud computing, Int. J. Comput. Intell. Syst., Vol. 13, 2020, pp. 496-510.

9.I. Brajevic and P. Stanimirovic, An improved chaotic firefly algorithm for global numerical optimization, Int. J. Comput. Intell. Syst., Vol. 12, 2018, pp. 131-148.

10.X.Y. Cui, Z. Chen, and F.L. Yin, Differential evolution and local search based monarch butterfly optimization algorithm with applications, Int. J. Comput. Intell. Syst., Vol. 12, 2018, pp. 149-163.

11.H. Garg, A hybrid GSA-GA algorithm for constrained optimization problems, Inf. Sci., Vol. 478, 2019, pp. 499-523.

12.H. Li and W Gan, A decomposition-based multiobjective chemical reaction optimization algorithm for community detection in complex networks, Int. J. Comput. Intell. Syst., Vol. 13, 2020, pp. 524-537.

13.H. Garg, An efficient biogeography based optimization algorithm for solving reliability optimization problems, Swarm Evol. Comput., Vol. 24, 2015, pp. 1-10.

14.H. Garg, A Hybrid GA-GSA Algorithm for Optimizing the Performance of an Industrial System by Utilizing Uncertain Data, Handbook of Research on Artificial Intelligence Techniques and Algorithms, IRM Press, 2015.

15.W.T. Pan, A new fruit fly optimization algorithm: taking the financial distress model as an example, Knowledge Based Syst., Vol. 26, 2012, pp. 69-74.

16.X.Y. Zhang, X.Y. Lu, S.M. Jia, and X.Z. Li, A novel phase angle-encoded fruit fly optimization algorithm with mutation adaptation mechanism applied to UAV path planning, Appl. Soft Comput., Vol. 70, 2018, pp. 371-388.

17.X.Y. Zhang, S.M. Jia, X.Z. Li, and M. Jian, Design of the fruit fly optimization algorithm based path planner for UAV in 3D environments, in Proceedings of 2017 IEEE International Conference on Mechatronics and Automation (Takamatsu, Japan), 6–9 August 2017, pp. 381-386.

18.J.Q. Li, Q.K. Pan, and K. Mao, A hybrid fruit fly optimization algorithm for the realistic hybrid flowshop rescheduling problem in steelmaking systems, IEEE Trans. Automation Sci. Eng., Vol. 13, 2016, pp. 932-949.

19.T. Meng and Q.K. Pan, An improved fruit fly optimization algorithm for solving the multidimensional knapsack problem, Appl. Soft Comput., Vol. 50, 2017, pp. 79-93.

20.X.F. Yuan, Y.M. Liu, Y.Z. Xiang, and X.G. Yan, Parameter identification of BIPT system using chaotic-enhanced fruit fly optimization algorithm, Appl. Mathematics Comput., Vol. 268, 2015, pp. 1267-1281.

21.W. Sheng and Y. Bao, Fruit fly optimization algorithm based fractional order fuzzy-PID controller for electronic throttle, Nonlinear Dynamics, Vol. 73, 2013, pp. 611-619.

22.S. Kanarachos, J. Griffin, and M.E. Fitzpatrick, Efficient truss optimization using the contrast-based fruit fly optimization algorithm, Comput. Struct., Vol. 182, 2017, pp. 137-148.

23.M. Mitić, N. Vuković, M. Petrović, and Z. Miljković, Chaotic fruit fly optimization algorithm, Knowledge Based Syst., Vol. 89, 2015, pp. 446-458.

24.X.F. Yuan, X.S. Dai, J.Y. Zhao, and Q. He, On a novel multi-swarm fruit fly optimization algorithm and its application, Appl. Mathematics Comput., Vol. 233, 2014, pp. 260-271.

25.L. Wu, W.S. Xiao, L. Zhang, Q. Liu, and J.L. Wang, An improved fruit fly optimization algorithm based on selecting evolutionary direction intelligently, Int. J. Comput. Intell. Syst., Vol. 9, 2016, pp. 80-90.

26.X.Y. Zhang and S. Xia, Quantum behaved fruit fly optimization algorithm for continuous function optimization problems, in Proceedings of the 9th International Conference on Swarm Intelligence (Chiengmai, Thailand), 26–30 July 2019, pp. 331-340.

27.L. Gyongyosi and S. Imre, A survey on quantum computing technology, Comput. Sci. Rev., Vol. 31, 2019, pp. 51-71.

28.J. Sun, B. Feng, and W. Xu, Particle swam optimization with particles having quantum behavior, in Proceedings of IEEE conference on cybernetics and intelligent systems, 2004, pp. 111-116.

29.T.Y. Liu, L.C. Jiao, W.P. Ma, and R.H. Shang, Quantum-behaved particle swarm optimization with collaborative attractors for nonlinear numerical problems, Commun. Nonlinear Sci. Numerical Simulation, Vol. 44, 2017, pp. 167-183.

30.F.B. Ozsoydan and A. Baykasoglu, Quantum firefly swarms for multimodal dynamic optimization problems, Expert Syst. Appl., Vol. 115, 2019, pp. 189-199.

31.E. Besada-Portas, L. de la Torre, A. Moreno, and J. L. Risco-Martín, On the performance comparison of multi-objective evolutionary UAV path planners, Inf. Sci., Vol. 238, 2013, pp. 111-125.

<Previous Article In Issue

Download article (PDF)

Next Article In Issue>

Journal: International Journal of Computational Intelligence Systems
Volume-Issue: 13 - 1
Pages: 1315 - 1331
Publication Date: 2020/09/07
ISSN (Online): 1875-6883
ISSN (Print): 1875-6891
DOI: 10.2991/ijcis.d.200825.001 How to use a DOI?
Open Access: This is an open access article distributed under the CC BY-NC 4.0 license (http://creativecommons.org/licenses/by-nc/4.0/).

Cite this article

ris enw bib

TY  - JOUR
AU  - Xiangyin Zhang
AU  - Shuang Xia
AU  - Xiuzhi Li
PY  - 2020
DA  - 2020/09/07
TI  - Quantum Behavior-Based Enhanced Fruit Fly Optimization Algorithm with Application to UAV Path Planning
JO  - International Journal of Computational Intelligence Systems
SP  - 1315
EP  - 1331
VL  - 13
IS  - 1
SN  - 1875-6883
UR  - https://doi.org/10.2991/ijcis.d.200825.001
DO  - 10.2991/ijcis.d.200825.001
ID  - Zhang2020
ER  -

download .riscopy to clipboard