1. Introduction

Optimization problems are used extensively in science, engineering and business. Over the last few decades, a number of meta-heuristic optimizations have been developed. These optimizations are based on biotic factors [1] [2]. Fruit fly optimization algorithm (FOA) is a new novel optimization algorithm presented by the scholar Pan [1][3], which is inspired by the food searching behavior of fruit-fly, and has the advantage of being easy to understand, much simpler and more robust compared with the complicated optimization methods proposed by past scholars [1][3]. The fruit fly has obvious advantages over other creatures in olfactory and visual sensory perception; its olfactory senses can perceive extremely faint smells of food floating in the air, even can smell a food source accurately up to 40 kilometers away. The fruit fly’s keen vision can confirm the food’s location, as well as the location of other fruit flies that have gathered close to the food.

FOA has some advantages such as being easily understandable and having simple calculations [4]. Therefore, the algorithm can be widely used in science and engineering fields [4], such as in solving the steelmaking casting problem [5], continuous mathematical function optimization problems [6], GRNN parameters optimization [7], semiconductor final testing scheduling problem [8], web auction logistics service [9], design of the PID controller [10], power load forecasting [11], multidimensional knapsack problem optimization [12] and analyzing swarms of mini autonomous surface vehicles [13].

2. Literature review

To improve the search efficiency and global search ability, researchers designed several improved FOAs [2].Yuan et.al [14] proposed a novel CFOA (chaotic-enhanced fruit fly optimization algorithm), which employs chaotic sequence to enhance the global optimization capacity of original FOA. Wang et.al [15] introduced AM-FOA (adaptive mutation fruit fly optimization algorithm). When algorithm trap in local optimum, AM-FOA selected a corresponding number of fruit files from the population and makes mutation and then updated the global optimum. Niu et.al [4] proposed an improved fruit fly optimization algorithm DFOA (differential evolution FOA) by modifying the expression of the smell concentration judgment value and by introducing a differential vector to replace the stochastic search. Wang et.al [2] introduced an improved FOA (IFOA) in which a new method of maintaining the population diversity was developed to enhance the exploration ability and fruit flies with better fitness values use vision to fly toward a new location, and the others fly randomly in initial search space based on swarm collaboration. Shan [16] has proposed LGMS-FOA (FOA based on linear generation mechanism of candidate solution), in which fruit fly individuals are generated by a linear mechanism. Pan [6] had put forward IFFO (improved fruit fly optimization). In IFFO, a new control parameter is introduced to tune the search scope around its swarm location adaptively and a new solution generating method is developed to enhance accuracy and convergence rate of the algorithm. But in the later stage of IFFO, while the adjacent generation optimal solution remains unchanged, it is not rational to reduce the iteration step value continually. Yuan [17] presented MFOA (multi-swarm FOA). In the MFOA approach, several sub-swarms moved independently in the search space with the aim of simultaneously exploring global optimal at the same time, and local behavior between sub-swarms are also considered [17].

But there is a common disadvantage of all these FOAs, the search direction of fruit fly is random. Obviously, it is not suit for the demand of efficiency. For the purpose of improving the search efficiency, a mechanism called “selecting the evolutionary direction intelligently” was introduced. And then, an improved fruit fly optimization algorithm called SEDI-FOA based on selecting the evolutionary direction intelligently was presented. The best search direction is fixed after evaluating the optimization results of the current group, so more fruit flies would fly in the best search direction or in a nearby direction to find the optimal solution. In SEDI-FOA the search direction of population individuals is selected according a certain mechanism which be introduced in this paper. But in other FOAs, the search direction and distance of population individuals are random. The effectiveness of SEDI-FOA is verified by a simulation experiment.

The rest of the paper is organized as follows. Section 3 describes original fruit fly optimization FOA and the improved fruit fly optimization algorithm SEDI-FOA. Simulation results and comparisons are introduced in Section 4. Section 5 covers conclusions.

3. Fruit fly optimization algorithm

3.1 Original fruit fly optimization FOA

The main idea behind the FOA technique is based upon the drosophila’s biological behavior [13]: (1) The fly flies with levy flight motion; (2) It smells the potential location (attractiveness); (3) It would then taste. Parameters in the original fruit fly optimization FOA mainly include: the initial position of the group (X,Y), the population size S, the iteration number M, and the iteration step value R.

According to fruit fly foraging behavior, the iterative optimization process of fruit fly optimization algorithm can be summarized in the following steps [17](a case study of solving two-dimensional function extremum):

• Step1 :

  Random initial fruit fly swarm location (X,Y) as shown in Fig. 1;

• Step2 :

  Individual searches for food in random directions and distances;

  (1){X(i)n=X+R·rand(  ),   i=1,2,⋯,SY(i)n=Y+R·rand(  ),   n=1,2,⋯,M

  (X(i)_n,Y(i)_n) is the position of i-th fruit fly individual among S fruit flies.

• Step3 :

  Since the food location cannot be known, estimate the distance D(i)_n between the coordinate origin and the individuals;

  (2)D(i)n=X(i)n2+Y(i)n2

  The closer the location is to the origin location, the smaller the density of the food. Then, the smell concentration judgment value S(i)_n is calculated, and this value is the reciprocal of the distance.

  (3)S(i)n=1/D(i)n

• Step4:

  Substitute the smell concentration judgment value S(i)_n into a smell concentration judgment function F (sometimes called the Fitness function) so as to find the smell concentration Smell(i) of the individual location of the fruit fly.

  (4)Smell(i)=F(S(i)n)

• Step5:

  Identify the fruit fly with the maximal smell concentration (finding the maximal value) among the fruit fly swarm.

  (5)[bestSmell bestIndex]=max(Smell)

• Step6:

  Reserve the best smell concentration value and the individual coordinate with the highest density of fruit fly individuals (X(best)_n,Y(best)_n) of the n-th generation swarm. Other individuals fly toward the highest density individual using their keen vision.

  (6){Smellbest=bestSmellX=X(best)nY=Y(best)n

• Step7 :

  Apply iterative optimization to repeat the implementation of Step 2-Step 5, and then judge if the smell concentration is superior to the previous iterative smell concentration; if so, implement Step 6. When the number of iterations is less than the maximum iterative number M, the loop terminates.

Fig.1.

Iterative process of FOA

3.2 Improve fruit fly optimization algorithm SEDI-FOA

In the original FOA, the smell concentration of fruit fly individuals is judged by the distance from the fruit fly individual to the virtual food source. As we know, the distance value cannot be negative, so the original FOA cannot solve for the extremum when the extremum is in the negative domain. Therefore, in this paper, the smell concentration Smell(i) is evaluated based on the decision variable X = (x₁,x₂,⋯x_n) directly as Smell(i) = F(X(i)) [17].

In the original FOA, the fruit fly individual search direction and distance are random. However, in the actual biological world, the swarms have intelligence and can intelligently evaluate and remember individual search behavior. Given the biological swarm’s intelligence, the individual direction should not be randomly selected in FOA. This paper presents an intelligent decision method for the FOA individual optimization direction. This method evaluates the optimization effect of the fruit fly’s contemporary generation, and then the optimal search direction is determined in order to ensure that more fruit fly generations move in the optimal search direction or in the nearby direction when finding the optimal solution.

The initial position of the fruit fly swarm is random (X,Y) ; the coordinate of the highest taste density of individual is (X(best)_n,Y(best)_n) after n generations of optimization. According to the FOA optimization rules, the n-th generation of a fruit fly group will converge (X(best)_n,Y(best)_n), and there are:

(7){Xn=X(best)nYn=Y(best)n

(X_n,Y_n) is the position coordinate of n-th generation swarm’s converged position.

Define the optimal search direction Fn→ of the n-th generation swarm (as shown in figure 2):

(8)Fn→=[(X(best)n−X),(Y(best)n−Y)]  n=1,2,⋯M

Fig.2.

Optimization process of SEDI-FOA

Fn→ , which is called the optimal search direction of the n-th generation swarm, is the flight direction that can enable the swarm to reach the optimal solution in the shortest time. In the evolution of the (n+1)-th generation swarm, more fruit fly individuals should fly toward Fn→ or in the nearby direction.

Assume that the position coordinates of one fruit fly of the (n+1)-th generation swarm is (X(a)_n+1,Y(a)_n+1),a = 1,2,⋯S. Define the angle θ between the flight direction and the optimal search direction Fn→ as follows:

(9)cos θ=(X(a)n+1−Xn)(Xn−X)+(Y(a)n+1−Yn)(Yn−Y)(X(a)n+1−Xn)2+(Y(a)n+1−Yn)2 (Xn−X)2+(Yn−Y)2

As we know, θ ∈ [0, π] distributed symmetrically on two sides of Fn→ .

In the process of the (n+1)-th generation optimization, the swarm flies around a center at coordinates (X_n,Y_n). The mechanism of intelligent selection search direction prescribes that the nearer the flight direction is to Fn→ (meaning that θ is closer to 0), the greater probability of the direction being selected. Likewise, the farther the flight direction is from Fn→ (meaning that θ is closer to π), the smaller the probability of the direction being selected.

Define the selection function of the individual flight direction g(θ) as follows:

(10)g(θ)=−Cπ*θ+C

C is a given constant. As we know from equation (10), when θ = 0, g(θ) = C. This means that individuals of the (n+1)-th generation swarm fly toward Fn→ in the maximum probability C. Likewise, when θ = π, g(θ) = 0 ; this means that individuals of (n+1)-th generation swarm fly against Fn→ in the probability 0.

Obviously, the value of C must insure that the probability of being selected of anyone in swarm is 100%. In the other words, any individual of fruit fly swarm can be selected and then flies toward a direction.

So, we can conclude:

(11)2·∫0πg(θ)=2·∫0π(−Cπ·θ+C)=1

It is easy to calculate that:

(12)C=1π

The optimization flowchart of SEDI-FOA is found in Fig. 3.

Fig.3.

optimization flowchart of SEDI-FOA

4. Simulation results and comparisons

To test the performance of the proposed algorithm SEDI-FOA, we conducted experiments on 12 benchmark functions [4]. The details of these 12 functions in list in Table 1.

In order to verify the effectiveness and advancement of SEDI-FOA, several improved FOAs such as DFOA [4], IFFO [6] and LGMS-FOA [16] are used to compare. Otherwise, three widely-used evolutionary algorithms are compared with the proposed SEDI-FOA approach: they are the particle swarm optimization (PSO) algorithm [18], the covariance matrix adaptation evolution strategy (CMAES) [19], the self-adaptive differential evolution (SaDE) algorithm [20]. Owing to their stochastic nature, evolutionary algorithms may arrive at solutions that are better or worse than solutions they have previously reached during their search for new solutions. For this reason, it is beneficial to use statistical tools to compare the problem-solving success of one algorithm with that of another [17]. All the seven algorithms (DFOA, IFFO, LGMA-FOA, PSO, CMAES, SaDE and SEDI-FOA) are run 50 times for the 12 test functions.

The parameter settings of seven evolutionary algorithms are as follow:

1. (1)

   DFOA: In the experiments, we set S=100, M=1000 and F=0.9 according to the literature [4].

2. (2)

   IFFO: In the experiments, we set S = 100 and M = 1000 for IFFO algorithms; the other parameters are fixed as λ_max = (UB − LB) / 2 and λ_min = 10⁻⁵, according to the literature [6].

3. (3)

   LGMS-FOA. LGMS-FOA generates a new individual X_i = (x_i,1,x_i,2,⋯x_i,n) by setting x_i,j = δ_j + ω × rand() × (UB_j − LB_j) for j = 1,2,⋯n, where ω is a weight generated by ω = ω₀ × α^Iter, ω₀ is the initial weight and α is the weight coefficient. According to Shan et al. [16], we set the population size S = 100, the iteration number M = 1000, ω₀ = 1, and α = 0.95. UB and LB are the top and bottom limitations of the search region.

4. (4)

   The iteration number M =1000, the population size S=100. Other parameter settings of PSO, CMAES and SaDE, are according to the literature [18], [19] and [20] respectively.

5. (5)

   SEDI-FOA. In the experiments, we set S=100, M=1000, C=1/π. Besides, the iteration step value R is set according with the region of search. Usually, the value of R is one-tenth of the value of region.

The comparison of the results are reported in Table 2.

In Table 3, where the “Best” means the optimal objective function value, the “Mean” reflects the precision and rate of convergence, and the “Std.” reflects the stability and robustness of the algorithm [21].

From the Table 3 we can know that SEDI-FOA has the best performance in finding the “Best”, “Mean”, “Std.” of f₁, f₄, f₅, f₆, f₇, f₈ and f₉. Refer to f₂, SEDI-FOA has found the “Best”, but the performance in “Mean” and “Std.” is ranking only second to PSO. SEDI-FOA has best performance in “Best” and “Mean” of f₃, but the performance in “Std.” is worse than DFOA. Besides, SEDI-FOA has best performance in “Best” and “Std.” of f₁₀, “Best” of f₁₁, “Mean” and “Std.” of f₁₂. Taken together, SEDI-FOA achieved 29 optimum value in 36 testing items. So we can concluded that SEDI-FOA has made great improvement in finding the optimal value.

The best fruit fly flying routes for benchmark functions in this simulation using the proposed SEDI-FOA approach are illustrated in Fig. 4, which shows that the best fruit fly can direct the global optimal solution in an efficient way.

Fig.4.

Best fruit fly flying route for benchmark functions using SEDI-FOA approach

5. Conclusion

In order to overcome the defect of original fruit fly optimization FOA, an improved FOA called SEDI-FOA based on selecting the evolutionary direction intelligently was proposed. Fruit fly of the swarms fly towards the best search direction or along a nearby direction to find the optimal solution, so that the efficiency of SEDI-FOA will increase. Simulation results showed that the SEDI-FOA achieved 29 optimum value in 36 testing items compared with three improved FOAs and three evolutionary algorithms.

But SEDI-FOA still has many problems that need to be improved, such as solving for the high-dimensional continuity function, identifying how to code when solving engineering problems, learning how to realize rapid convergence in practical problems and so on.

Acknowledgements

This work was supported in part by the project foundation of china Ministry of industry and information technology “Research of gordian technique of deep-water semi-submersible platforms”, and the National 863 plan project foundation of china “Key technology research of automated processing of deep-water drilling rig and string” (No. 2012AA09A203), and Project of scientific and technological achievements of Jiangsu province “Research and industrialization of the key techniques of drilling string used in marine deep water”.