Sage Journals: Discover world-class research

Abstract

Fruit fly optimization algorithm, which is put forward through research on the act of foraging and observing groups of fruit flies, has some merits such as simplified operation, strong robustness, easy to parallel computing, and fast convergence rate; it could solve the bottlenecks of traditional intelligent optimization algorithms on precocity and low convergence speed effectively. Fruit fly optimization algorithm is applied to almost all the numerical optimization problems and is very useful in engineering applications. When the design variable is negative, traditional fruit fly optimization algorithm is not qualified for the extraordinarily slow convergence rate during the late stage of calculation and easy to be trapped in local optimum. Because of the defects of classical fruit fly optimization algorithm, a new coding method of the process of optimization is improved by this article, so the design variables could be searched toward the direction. In addition, a novel bionic global optimization—fruit fly optimization algorithm of learning—is proposed by introducing the concept of “study.” This article tries to apply fruit fly optimization algorithm of learning to compare calculations; therefore, four classical test functions and two engineering problems are performed. It turned out that not only does fruit fly optimization algorithm of learning inherit the advantages of fruit fly optimization algorithm, but has a strong learning ability. The introduction of “study” ability into fruit fly optimization algorithm notably improves the efficiency and capability of optimization; it has characteristics of fast convergence rate and fast speed of approaching the global optimum solutions. Fruit fly optimization algorithm of learning has the ability to solve practical problems, and its engineering prospect is promising.

Keywords

Fruit fly optimization algorithm numerical optimization fruit fly optimization algorithm of learning study

Preface

Fruit fly optimization algorithm (FOA), which is a new evolutionary global optimizing method, was a creative model proposed by Wen-Tsao Pan^1–3 who was inspired by foraging behavior of drosophila in 2011. The FOA has high value of application and wide prospects in engineering and science, not only because of its simple principle and fast convergence in calculation, but also on account of its good local searching ability in acquiring global optimal value. However, the design variables could be searched in the direction of positive value only by FOA, for its special coding way. And it is easily trapped into a local optimum value during the late stage of iteration, especially for advanced multi-extremum optimum problem, like other intelligent optimization algorithms, such as genetic algorithms (GAs),^4–7 particle swarm algorithm,^8–10 and bees algorithm.¹¹ Because of that, many improved ways have been proposed to improve the performance of algorithms. Hui and Liu¹² put forward a new method based on utilizing chaos mapping and FOA, combining logistic map with FOA, which can improve the precision for improper initial values. Junying and Chengzhong¹³ improved global searching capacity by integrating chaos optimization algorithm and FOA.

Based on traditional FOA, this article puts forward a new algorithm called fruit fly optimization algorithm of learning (FOAL), which improves the code scheme of FOA and introduces the “learning” mechanism, so it can search on a global scale, which makes other drosophila learning to the best one in order to get a better sample with the better fitness. Finally, by comparing some classic test functions and engineering examples, it is confirmed that the new algorithm FOAL is an effective way to improve the algorithm performance with higher precision and faster convergence rate.

FOA

According to the forging behavior of drosophilae, FOA is a new global optimization to search for the best value.^14,15 Drosophilae search for foods by sensitive olfaction and superior vision. They find foods by smelling the taste drifting in the air; higher the taste concentration is, closer they are to the foods and vice versa. In fact, the process drosophilae foraging for foods is according to the concentration of food taste from low to high. On knowing the concentration of food taste is high where some drosophilae are, others will fly to them by vision.^16–18 Applying FOA to solve the optimization problem, abstract the points in solution space from the food source and the procedure of searching optimization by FOA from drosophilae searching for foods when applying the FOA to solve the optimization problem. There are three assumptions as follows:

When searching for food, drosophilae estimate the concentration of food taste, first by smelling, then fly to the drosophila nearest to food by vision;

Drosophilae estimate and get the position of the drosophila whose taste concentration is highest each time;

The population of drosophilae is invariant.

Set min f(x) is the optimization problem to be solved, $x \in S$ , on the premise of the three assumptions, the basic procedures are as follows:

Step 1. The size of population is PopNum, maximum iteration number is MaxI, and the number of design variable is D. Initialize the place of the first drosophila randomly

\begin{matrix} X_{1 j} = φ_{Xj}^{1} \\ Y_{1 j} = φ_{Yj}^{1} \end{matrix}}

(1)

where $X_{1 j}$ and $Y_{1 j} (j = 1, 2, \dots, D)$ are D-dimensional vectors, which represent the initialization coordinate of the first drosophila; $φ_{Xj}^{1} \in [a, b]$ and $φ_{Yj}^{1} \in [a, b]$ are random numbers; and $a$ and $b$ are decided by search space.

Step 2. The drosophila can search the direction and distance of food by smelling. Initialize the population of drosophila

\begin{matrix} X_{ij} = X_{1 j} + φ_{Xj}^{i} \\ Y_{ij} = Y_{1 j} + φ_{Yj}^{i} \end{matrix}}

(2)

where $X_{ij}$ and $Y_{ij}$ represent coordinates of the other drosophilae. $i \in {2, 3, \dots PopNum}$ , $φ_{Xj}^{i} \in [a, b]$ , and $φ_{Yj}^{i} \in [a, b]$ .

Step 3. When the position of food is unknown, calculate the distance of a drosophila to the origin $D_{ij} = \sqrt{X_{ij}^{2} + Y_{ij}^{2}}$ first. Then, confirm the taste concentration discriminant $S_{ij} = 1 / D_{ij}$ , where $S_{ij}$ is a designed variable.

Since $D_{ij} \geq 0$ and $S_{ij} \geq 0$ , this algorithm cannot search the designed variable a along negative orientation. Improving the expression of $S_{ij}$ by equation (3), the algorithm can be searched globally

D_{ij} = \sqrt[3]{X_{ij}^{3} + Y_{ij}^{3}} (i = 1, 2, \dots, PopNum)

(3)

S_{ij} = 1 / D_{ij}

(4)

The FOA mentioned in this article applies to equation (3).

Step 4. Substituting the taste concentrate discriminant value into objective function $f (x)$ (or taste concentrate discriminant function) leads to taste concentrate Smell

Smel l_{i} = f (S_{i 1}, S_{i 2}, \dots, S_{iD})

(5)

Step 5. Find out the best drosophila in taste concentrate

Best Smell = Min (Smel l_{1}, Smel l_{2}, \dots Smel l_{PopNum})

(6)

Step 6. Maintain the best taste concentrate value and the position coordinate correspondingly

\begin{matrix} Smell Best = Best Smell \\ X_{1 j} = X_{Bestj} \\ Y_{1 j} = Y_{Bestj} \end{matrix}}

(7)

Step 7. Get in optimization iterative, execute Steps 2–6 repeatedly, and judge whether the best taste concentrate (population fitness) variance in continuous five generations is less than convergence precision $δ$ ( $δ$ is a little positive real number) or not, or whether the iteration number equals maximum iteration number MaxI or not. If it is, stop iterating and obtain the results.

FOAL

Being in the same population or between different species, one of the main reasons people can dominate the world is that they are capable of learning. With the better ability of learning, the population will evolve to higher ranks. Enlightened by GA and “shake” GA,¹⁹ this article puts forward a FOAL which puts learning into FOA and develops on it. This new algorithm develops the performances of fruit fly algorithm and improves the speed of convergence.

FOAL is described theoretically by the following three aspects:

Learning object. Learning object is necessary for any learning process. For FOA, learning object is the one whose taste concentration is highest.

Learning objective. Getting better food is the objective behind drosophila foraging. FOA abstracts taste concentration from food. So the learning objective of drosophila is to get higher taste concentration value than the highest at present.

Learning method. In order to ensure the best individual’s character can be inherited, other drosophilae should learn from it and become better than it. The essence of FOAL in learning is exchanging the position (coordinate value) of individual, which puts the coordinate of the individual with highest taste concentrate to another one randomly in certain probability

\begin{matrix} X_{ij} = X_{Bestj} \\ Y_{ij} = Y_{Bestj} \end{matrix}}

(8)

where $i \in {2, 3, \dots, PopNum}$ , $j \in {1, 2, \dots, D}$ , and $i$ and $j$ are selected randomly.

Basic procedures of FOAL are shown in Figure 1.

Figure 1.

Basic procedures of FOAL.

Equation (8) shows the learning process: the individual which is not the optimal one is endowed with the value of 1 or a few design variables of the best individual (shown in Figure 2); this ensures that the new distance between the individual fruit flies and the optimal one is closer. The object function value of new individual will be closer and even better than the current optimal value. This is more suitable for searching the local extremum, and it can improve the precision of the algorithm significantly; the way the algorithm generates the new solution by “learning” is similar to the “cross” operation of GA, but it is not the “crossover” operation, because it will affect the current diversity of population by using the searching method which is proposed by this article, and it is not suitable for GA but for FOA. So this article calls the new searching method which is different from the “crossover” of GA “learning.” Learning is the act of acquiring new or modifying and reinforcing existing knowledge, behaviors, skills, values, or preferences. In the space, the best individual is the goal other individuals try to achieve; it has weakness and shortage in some respects, although it is the best one. Other individuals are transferred into new individuals which is clearly similar to the best one through learning. It can be proved that the “learning” finally achieved success when the new one is better than the original best one; conversely, the new one cannot be accepted.

Figure 2.

Substitution method of design variable during “study” procedure.

Performance analysis of FOAL

Simulation and results

To verify that FOAL has many advantages over the traditional FOA, choose four classical test functions and find out the minimum values which are widely used in GA and particle swarm optimization algorithm. Table 1 shows the names, dimensions, math expressions, searching space, and theoretically optimum values of test functions. The simulation parameters are as follows: the size of population PopNum = 100, maximum iteration number MaxI = 5000, convergence precision $δ = 0.000001$ , calculated 20 times with algorithm, respectively, then put the optimal value, poorest value, and average value in Table 2. The evolution curves of taste concentrate (adaptation) of four test functions are shown in Figures 3 –6; when optimizing the same test function with different algorithms, starting point is selected the same for convenience.

Table 1.

Four functions for testing FOAL performance.

Function	Dimension	Expression	Search space	Theoretical optimal value
Sphere	20	$f_{1} (x) = \sum_{i = 1}^{n} x_{i}^{2}$	$- 100 \leq x_{i} \leq 100$	0
Rastrigin	30	$f_{2} (x) = 10 \times n + \sum_{i = 1}^{n} [x_{i}^{2} - 10 \times \cos (2 \times π \times x_{i})]$	$- 500 \leq x_{i} \leq 500$	0
Schaffer	2	$f_{3} (x_{1}, x_{2}) = \frac{\sin^{2} \sqrt{x_{1}^{2} + x_{2}^{2}} - 0.5}{{[1 + 0.001 (x_{1}^{2} + x_{2}^{2}))]}^{2}} - 0.5$	$- 100 \leq x_{1} \leq 100$ $- 100 \leq x_{2} \leq 100$	−1
Six-hump camel back	2	$f_{4} (x_{1}, x_{2}) = (4 - 2.1 x_{1}^{2} + x_{1}^{4} / 3) \times x_{1}^{2} + x_{1} x_{2} + (4 x_{2}^{2} - 4) \times x_{2}^{2}$	$- 3 \leq x_{1} \leq 3$ $- 2 \leq x_{2} \leq 2$	−1.03

FOAL: fruit fly optimization algorithm of learning.

Table 2.

Comparison of results.

Function	Optimum		Worst value		Optimization average value		Average convergence iteration time x
	FOA	FOAL	FOA	FOAL	FOA	FOAL	FOA	FOAL
$f_{1}$	0.001199	0.000282	0.002924	0.000792	0.001872	0.000485	Divergency	2581.45
$f_{2}$	0	0	0.000035	0.000022	0.000008	0.000003	521.7	312.8
$f_{3}$	−1.000000	−1.000000	−0.999999	−1.000000	−0.999999	−1.000000	175.6	26.2
$f_{4}$	−1.031524	−1.031628	−1.030188	−1.030605	−1.030841	−1.031620	29.8	17.9

FOA: fruit fly optimization algorithm; FOAL: fruit fly optimization algorithm of learning. The data in this table are average values with 20 times iteration.

Figure 3.

Convergence curve of test function 1.

Figure 4.

Convergence curve of test function 2.

Figure 5.

Convergence curve of test function 3.

Figure 6.

Convergence curve of test function 4.

$f_{1} (x)$ is a single-peak spherical function, global optimum value is on a valley bottom on a great scale. So it is hard to search the global optimum point. $f_{2} (x)$ is a high dimensional multimodal function; as there are a lot of partial extreme points gathered around global minimum value, so the function is easy to trap in local optimum. $f_{3} (x)$ and $f_{4} (x)$ are two-dimensional multimodal functions, which are easy to concentrate to local optimum.

Data in Table 2 indicate that FOAL has advantages over FOA in the ability of searching, for its learning capability, which can get the better answer with less time of searching. The curves in Figures 3 –6 show that FOA before and after improvement can concentrate in global optimum steadily, and the phenomenon of precocity does not occur. This indicates that FOA can avoid precocity concentration. FOAL not only has the same advantages with FOA, but also has faster concentration than FOA.

Engineering example 1

Deflection calculation model of crane girder was used to verify application value of FOAL; the model is shown in Figure 7. The span S = 25 m, exert concentrated load P₁ = 17,8281 N, P₂ = 178,281 N, and uniform load $q = 9132 N / m$ , then find out maximum deflection on mid-span of girder and coordinates of the position $x_{1}$ , $x_{2}$ of loads corresponding. This function provides bases for checking the main girder static stiffness of crane by traditional way. Equations (9) and (10) show objective function and constraint condition of optimization model. The size of population PopNum = 100 and the maximum iteration number MaxI = 500; the program runs independently 20 times continuously, then list the average optimization results and average iteration times in Table 3. Table 3 also lists data obtained by FOA and traditional GA

\begin{matrix} max ω = \frac{5 q S^{4}}{384 EI} + \frac{P_{1} (\frac{S}{2} - | x_{1} |) [3 S^{2} - 4 {(\frac{S}{2} - | x_{1} |)}^{2}]}{48 EI} \\ + \frac{P_{2} (\frac{S}{2} - | x_{2} |) [3 S^{2} - 4 {(\frac{S}{2} - | x_{2} |)}^{2}]}{48 EI} \end{matrix}

(9)

s . t . {\begin{matrix} 2 \leq a = x_{2} - x_{1} \leq 3.5 \\ x_{1} \geq - \frac{S}{2}, x_{2} \leq \frac{S}{2} \end{matrix}

(10)

where $x_{1}$ and $x_{2}$ are design variables which show the positions of loads; $E = 2.02 \times 10^{11} Pa$ is the young modulus of material; $I = 5.54 \times 10^{10} m m^{4}$ , which is the inertia moment of main girder section of crane; and $ω$ is objective function indicating maximum deflection on mid-span.

Figure 7.

Mechanical model.

Table 3.

Comparison of maximum deflection optimized by three ways.

	$ω$ (m)	$x_{1}$ (m)	$x_{2}$ (m)	Iteration time
FOAL	0.014425380	−0.998200934	1.003182165	77.51
FOA	0.014425364	−1.009689627	1.003732414	325.15
GA	0.014402154	−2.569282205	0.186832179	469.98

GA: genetic algorithm; FOA: fruit fly optimization algorithm; FOAL: fruit fly optimization algorithm of learning.

Based on material mechanics bending deformation theory, the expression of objective function is simplified because the origin of coordinate is located on mid-span of main girder by applying the mechanical model shown in Figure 7, which avoids piecewise objective function and more conditional judgment sentences with origin O located in other places. So the computational efficiency is higher.

Data of FOAL and FOA in Table 3 show that when the distance of loads $x_{1}$ and $x_{2}$ is nearly 2 m, then they are symmetric to the origin of mid-span. The maximum deflection is $ω = 0.01442538 m$ , if the value of objective function indicates proximity, the number of iterations is less, and the efficiency is higher. While the results of GA is far away from them, objective value $ω = 0.014402154 m$ is not the global optimization result for it is trapped in local optimization value obviously, which also proves that FOAL has the strong ability in getting rid of the disturbance of local extremum value. Figure 8 proves that the convergence speed of FOAL is faster than that of FOA and GA.

Figure 8.

The comparison of iteration.

Engineering example 2

The structure optimization model of crane box girder in Lu et al.,²⁰ Guo et al.,²¹ Zhengjia et al.,²² and Guozheng²³ is applied to the math model shown in equation (11), where L = 10,500, P₁ = 120,000, P₂ = 12,000, and X₁, X₂, X₃, and X₄ are the size of cross section of crane box girders 700 ≤ X₁ ≤ 800, 350 ≤ X₂ ≤ 400, 5 ≤ X₃ ≤ 10, and 5 ≤ X₄ ≤ 10, respectively; G(x) is the objective function that represents the weight of box girder per unit length. Set the size of population PopNum = 100 and maximum iteration number MaxI = 1000, and the program runs independently 20 times continuously. The results of the optimal solution, worst solution, and average are listed in Table 4, together with the results in other references for comparing

\begin{array}{l} \min G (x) = x_{1} x_{3} + x_{2} x_{4} \\ s . t . {\begin{matrix} 0.75 L [\frac{P_{1} + 7.8 \times 10^{- 5} (x_{1} x_{3} + x_{2} x_{4}) L}{3 x_{1} x_{2} x_{4} + x_{1}^{2} x_{3}} + \frac{P_{2}}{3 x_{1} x_{2} x_{3} + x_{1}^{2} x_{4}}] \\ - 140 \leq 0 \\ \frac{P_{1} L^{3}}{1.68 \times 10^{6} (3 x_{1}^{2} x_{2} x_{4} + x_{1}^{3} x_{3})} - \frac{L}{700} \leq 0 \\ \frac{x_{2}}{x_{4}} - 60 \leq 0, \frac{x_{1}}{x_{3}} - 160 \leq 0 \end{matrix} \end{array}

(11)

Table 4.

Results of FOAL and other functions.

Name	FOAL runs 20 times independently			Modified differential evolution algorithm²⁰	Chaos-genetic optimal algorithm²¹	Genetic–neural network algorithm²²	Normal way²³
	Optimal results	Worst results	Average
G(x)	5876.302348	5885.429172	5880.089863	5903.3093	6071.6127	6113.396	6430.0
X ₁	739.6525	736.6848	737.2514	772.3285	799.0784	791.968	790.0
X ₂	358.0696	360.1262	359.8650	350.0	350.2652	320.440	310.0
X ₃	5.0021	5.0108	5.0026	5.0	5.0210	5.000	5.0
X ₄	6.0784	6.0923	6.0910	5.833	5.8796	6.627	8.0

FOAL: fruit fly optimization algorithm of learning.

Table 4 indicates that FOAL is the best way to solve engineering problems. The result $G (x) = 5880.089863$ of FOAL is better than those in Lu et al.,²⁰ Guo et al.,²¹ Zhengjia et al.,²² and Guozheng,²³ which suggests that FOAL has a powerful ability to search the global extrema. So FOAL not only improves the traditional FOA, widening its scope of application and improving its optimization speed, but also improves the calculation precision and optimization effect. This algorithm is a new optimization way with a broad prospect in engineering.

Summary

Based on traditional FOA, analyzed its optimization performance, put forward a new algorithm called FOAL, whose efficiency is higher and searching range is wider:

Changing the coding method of traditional FOA $D_{ij} = \sqrt[3]{X_{ij}^{3} + Y_{ij}^{3}}$ leads to the new algorithm that can search overall rather than searching along the position direction;

Introducing the concept “learning” in improved FOA in order to improve the searching efficiency and make the ability of searching more power.

FOAL not only inherits the merits of traditional FOA such as easy to operate, powerful robustness, fast convergence speed, hard to be precocity, but also has wider searching range and powerful adaptation. What is more, FOAL simulates the process of learning by exchanging the position of individual in population in order to make the individuals learn to the best one, then surpass it so as to improve the searching efficiency and precision. It is proved that FOAL is faster in convergence, and higher in computational accuracy and efficiency. By comparing four classical test functions and engineering problems, FOAL is applied to engineering more, which has wide prospects of science researching and provides a new thinking to improve traditional FOA.

Footnotes

Declaration of conflicting interests

The authors declare that there is no conflict of interest.

Funding

This study was supported by National Nature Science Foundation of China (no. 51275329).

Appendix 1

References

Pan

. New evolutionary computation: fruit fly optimization algorithm. Taiwan: CangHai Press, 2011.

Pan

. Using fruit fly optimization algorithm optimized general regression neural network to construct the operating performance of enterprises model. J Taiyuan Univ Tech2011; 29(4): 1–5.

Pan

. A new fruit fly optimization algorithm: taking the financial distress model as an example. Knowl-Based Syst2012; 26: 69–74.

Zhou

Sun

. Genetic algorithm: principle and application. Beijing, China: National Defense Industry Press, 1999.

Bagheri

Bashiri

. A hybrid genetic and imperialist competitive algorithm approach to dynamic cellular manufacturing system. Proc IMechE, Part B: J Engineering Manufacture2013; 228: 458–470.

Yadav

Yadava

. Multi-objective optimization of slotted electrical discharge abrasive grinding of metal matrix composite using artificial neural network and nondominated sorting genetic algorithm. Proc IMechE, Part B: J Engineering Manufacture2013; 227: 1442–1452.

Scedighi

Hadi

. Preform optimization for reduction of forging force using a combination of neural network and genetic algorithm. Proc IMechE, Part B: J Engineering Manufacture2010; 224: 1717–1724.

Karakuzu

. Parameter tuning of fuzzy sliding mode controller using particle swarm optimization. Int J Innov Comput Inform Contr2010; 6(10): 4755–4770.

Modares

Alfi

Naghibi-Sistani

. Parameter estimation of bilinear systems based on an adaptive particle swarm optimization. Eng Appl Artif Intel2007; 23(7): 1105–1111.

10.

Luo

Wang

. An effective self-adapting localization algorithm in wireless sensor networks. J Appl Mech Mat2011; 58: 1013–1017.

11.

Ang

Pham

. Combining the Bees Algorithm and shape grammar to generate branded product concepts. Proc IMechE, Part B: J Engineering Manufacture2013; 227: 1860–1873.

12.

Hui

Liu

. Mixed fruit fly optimization algorithm based on chaotic mapping. Comput Eng2013; 39(5): 218–221.

13.

Junying

Chengzhong

. Fruit fly optimization algorithm based on bacterial chemotaxis. J Comput Appl2013; 33(4): 964–966.

14.

Lin

S-M

. Analysis of service satisfaction in web auction logistics service using a combination of fruit fly optimization algorithm and general regression neural network. Neural Comput Appl2013; 22: 783–791.

15.

Wang

Zou

. FOA-based SVM parameter optimization and its application in ship manoeuvring prediction. J Shanghai Jiao Tong Univ2013; 47(6): 884–888.

16.

Junying

Chengzhong

. Adaptive chaos fruit fly optimization algorithm. J Comput Appl2013; 33(5): 1313–1316.

17.

Wang

Zheng

X-l

Wang

S-y

. A novel binary fruit fly optimization algorithm for solving the multidimensional knapsack problem. Knowl-Based Syst2013; 48: 17–23.

18.

Sheng

Bao

. Fruit fly optimization algorithm based fractional order fuzzy-PID controller for electronic throttle. Nonlinear Dynam2013; 73: 611–619.

19.

Cai

. Improvement of genetic algorithms–shock genetic algorithms. Comput Digit Eng2013; 41(6): 893–895.

20.

Zhang

Wen

. Modified differential evolution and its application. Trans Chin Soc Agric Mach2010; 41(2): 193–197.

21.

Guo

Che

Xiao

. Chaos-genetic optimal algorithm and application in mechanical optimal design. J Mach Des2003; 20(10): 23–25.

22.

Zhengjia

Hongzhong

Xin

. A genetic-neural network algorithm in optimum design. J Southwest Jiaotong Univ2000; 35(1): 67–70.

23.

Guozheng

. Optimization design and application. Beijing, China: People’s Transportation Press, 1992.

A new type bionic global optimization: Construction and application of modified fruit fly optimization algorithm

Abstract

Keywords

Preface

FOA

FOAL

Performance analysis of FOAL

Simulation and results

Engineering example 1

Engineering example 2

Summary

Footnotes

Declaration of conflicting interests

Funding

Appendix 1

References