# Fruit Fly Optimization Algorithm Based on Single-Gene Mutation for High-Dimensional Unconstrained Optimization Problems

Authors: Xiao-dong Guo; Xue-liang Zhang; Li-fang Wang
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

The fruit fly optimization (FFO) algorithm is a new swarm intelligence optimization algorithm. In this study, an adaptive FFO algorithm based on single-gene mutation, named AFFOSM, is designed to aim at inefficiency under all-gene mutation mode when solving the high-dimensional optimization problems. The use of a few adaptive strategies is core to the AFFOSM algorithm, including any given population size, mutation modes chosen by a predefined probability, and variation extents changed with the optimization progress. At first, an offspring individual is reproduced from historical best fruit fly individual, namely, elite reproduction mechanism. And then either uniform mutation or Gauss mutation happens by a predefined probability in a randomly selected gene. Variation extent is dynamically changed with the optimization progress. The simulation results show that AFFOSM algorithm has a better accuracy of convergence and capability of global search than the ESSMER algorithm and several improved versions of the FFO algorithm.


---

## Body

## 1. Introduction

In the recent years, swarm intelligence has become a research focus of optimization design field because of its special advantages, such as simple to operate, quick convergence rate, and powerful ability of global search. New swarm intelligence technologies, such as genetic algorithms (GAs) [1], ant colony optimization (ACO) [2], particle swarm optimization (PSO) [3], artificial fish-swarm optimization (AFSO) [4], artificial bee colony algorithm (ABC) [5], firefly algorithm (FA) [6], FFO [7, 8], biogeography-based optimization (BBO) [9], whale optimization algorithm (WOA) [10], butterfly optimization algorithm (BOA) [11], gaining sharing knowledge-based algorithm (GSK) [12], and their respective improved versions are emerging in endlessly and have been widely applied to the fields of optimization design [13–20].Fruit fly is an insect which eats plants that are decaying, especially fruits. Fruit flies acquire chemical information in their environment through smell and taste receptors on the surface of their bodies and then regulate behaviors, such as foraging, aggregation, mating, and spawning. In these processes, olfactory plays an important role over long distances and shorter ranges.FFO algorithm [7, 8] is proposed by Pan in 2011. FFO simulates the foraging behavior of fruit flies and is a fast, structure-simple, and easily realized algorithm. Therefore, it already attracted broad attention in recent years [21–44] and has been successfully applied to a wide range of practical problems [45–52].Fruit flies have olfactory and visual abilities superior to other species. When foraging, fruit flies first use their own olfactory organs to smell the odor from food source and exchange odor information to the surrounding fruit flies, a process known as the olfactory foraging phase. Then, the flies used their visual organs to find and fly to the locations of the flies that had gathered the best odor information, a process named the vision foraging phase.A series of studies show that some unreasonable algorithmic design makes FFO algorithm ill-equipped to jump out of local extremum and to handle complex, high-dimensional, and nonlinear problems. So with this as the starting point of the paper, a small population, adaptive and improved version of the FFO algorithm, named AFFOSM, is developed based on the single-gene mutation mode, in which the only one gene of an offspring is different from the elite individual.On the contrary to a single-gene mutation mode, all-gene mutation mode is adopted by most of optimization algorithms, such as FFO, PSO, and ABC algorithm, in which each gene of an offspring is different from the elite or parent individual.The efficiency of the AFFOSM algorithm presented in this research is evaluated by solving 6 test problems. Optimization results demonstrate that AFFOSM is very competitive compared to the state-of-the-art single-gene optimization methods.The rest of the paper is structured as follows. Section2 describes the related research work about the further analysis and modification to FFO Algorithm. Section 3 describes the developments of FFO algorithm, from all-gene mutation to single-gene mutation. AFFOSM algorithm developed in this study will be covered in detail in Section 4. Test problems and optimization results are presented and discussed in Sections 5. Section 6 summarizes the main findings of this study and suggests directions for future.


## 2. Related Work

It is worth noting that, in the FFO algorithm, fruit fly individual is represented in its coordinates in a 2D plane, and the corresponding variable value is calculated as the reciprocal of the Euclidean distance between individual and ordinate origin, as illustrated in Figure1.Figure 1
Foraging process of fruit fly.Another noteworthy thing about the FFO algorithm is elitist reproduction strategy. Once a historical best solution is found, fruit fly individuals will fly to it and look for the food resources around it before a newly best solution is found.There are also some disadvantages as follows:(1)
The ability to solve the problem whose theoretical optimal solution is negative is not available.(2)
It is difficult and time-consuming for population initialization when definition domain is far away from ordinate origin.(3)
Obviously, it is not good choice that search range is fixed, compared to dynamic one.(4)
Most of searching behavior happens around ordinate origin due to nonuniform search in definition domain. FFO algorithm is workable to deal with a class of problems, such as quite a lot of test function whose theoretical optimal solution is very close to zero and is poor for most of the optimization problems in practical projects.(5)
Elitist reproduction strategy could make fruit fly swarm easy to fall into local extremum and not capable to solve complex, high-dimensional and nonlinear problems.Given the abovementioned facts, many improvements have been made in recent years.Fu-qiang Xu and Tao [53] presented the G-FFO algorithm with sign processing in a random manner. Inspired by probability estimation for code words in adaptive arithmetic coding, a FFO algorithm with adaptive sign processing (FFOASP) is proposed [54].Wu Lei et al. propose SEDI-FFO algorithm in which more fruit flies would fly in the search direction that was best for finding the optimal solution or at least in a direction close to the optimal direction [34].Based on hybrid location information exchange mechanism, HFFO algorithm is proposed that enables flies to communicate with each other and conduct local search in a swarm-based approach [36].Fan et al. propose WFFO algorithm in which an effective whale-inspired hunting strategy is introduced to replace the random search plan of the original FFO [38].Niu et al. propose an improved FFO algorithm based on differential evolution (DFFO) by modifying the expression of the smell concentration judgment value and by introducing a differential vector to replace the stochastic search [52].CEFFO algorithm is proposed in which trend search is applied to enhance the local searching capability of fruit fly swarm, and coevolution mechanism is employed to avoid the premature convergence and improve the ability of global searching [40].SCA_FFO algorithm [41] is developed by introducing the logic of the sine-cosine algorithm. The fruit fly individual adopts the way to fly outward or inward to find the global optimum.


## 3. FFO: From All-Gene to Single-Gene Mutation

In general, the nonconstrained optimization problem can be formulated as ann-dimensional minimization problem as follows:(1)minfx,s.t.x=x1,x2,…,xn,xj∈lj,uj,j=1,2,…,n,where f is a boundary objective function, x=x1,x2,…,xn is the set of decision variables, n is the dimensionality, and lj and uj are the lower and upper bounds of the decision variable xj, respectively.


### 3.1. FFO Algorithm

In FFO, fruit fly individual is represented in its coordinates in a plane and generated in uniform mutation around historically best solution, also called current population location:(2)Xi=X_axis±σ×rand,Yi=Y_axis±σ×rand,where Xi,Yi, X_axis,Y_axisis the coordinate pair of current individual xi and current population δ,σ is the amplitude of uniform mutation, and rand is the uniformly distributed random numbers between 0 and 1. The value of xi is the reciprocal of the Euclidean distance between fruit fly individual and ordinate origin: (3)xi=1Xi2+Yi2.It can be found that the mechanism of individual representing limits the performance of FFO.


### 3.2. LGMS-FFO Algorithm

Shan et al. [55] use one-dimensional coordinate of fruit fly to denote the individual location, and then, let it be equal to the value of xi, which can be formulated as follows:(4)xi=Xi,δ=X_axis.Based on a new linear generation mechanism of candidate solution, LGMS-FFO algorithm is proposed:(5)ω=ω0×αIter,xi=δ±ω×l+u−l×rand,where ω is a weight factor to tune variation extent, ω0is the initial weight, αis the weight coefficient, and Iter is the current generation.Obviously, all-gene mutation mode is used to generate offspring individuals in FFO and LGMS-FFO algorithms. However, the higher dimensionality the functions to be optimized are, the lower the probability of excellent individuals is. This in turn has caused a low convergence rate for solving high-dimensional functions.


### 3.3. IFFO Algorithm

Different from FFO and LGMS-FFO, single-gene mutation mode is introduced that only one gene is selected randomly to mutate in the IFFO algorithm. It is demonstrated that the single-gene mutation mode is a better choice in performance than the all-gene mutation mode for solving high-dimensional functions.IFFO algorithm is presented in which a control parameterσ is used to tune self-adaptively the search scope in a random direction of current swarm location, and offspring individuals are generated in the single-gene uniform mutation mode [28]:(6)σ⟵σmax×explogσminσmax×IterItermax,xi,d⟵δd±σ×rand,xi,j⟵δj,i=1,2,…,k,j=1,2,…,n,j≠d,where σmax is the maximum radius, σmin is the minimum radius, and d is a random integer between 1 and n.


## 3.1. FFO Algorithm

In FFO, fruit fly individual is represented in its coordinates in a plane and generated in uniform mutation around historically best solution, also called current population location:(2)Xi=X_axis±σ×rand,Yi=Y_axis±σ×rand,where Xi,Yi, X_axis,Y_axisis the coordinate pair of current individual xi and current population δ,σ is the amplitude of uniform mutation, and rand is the uniformly distributed random numbers between 0 and 1. The value of xi is the reciprocal of the Euclidean distance between fruit fly individual and ordinate origin: (3)xi=1Xi2+Yi2.It can be found that the mechanism of individual representing limits the performance of FFO.


## 3.2. LGMS-FFO Algorithm

Shan et al. [55] use one-dimensional coordinate of fruit fly to denote the individual location, and then, let it be equal to the value of xi, which can be formulated as follows:(4)xi=Xi,δ=X_axis.Based on a new linear generation mechanism of candidate solution, LGMS-FFO algorithm is proposed:(5)ω=ω0×αIter,xi=δ±ω×l+u−l×rand,where ω is a weight factor to tune variation extent, ω0is the initial weight, αis the weight coefficient, and Iter is the current generation.Obviously, all-gene mutation mode is used to generate offspring individuals in FFO and LGMS-FFO algorithms. However, the higher dimensionality the functions to be optimized are, the lower the probability of excellent individuals is. This in turn has caused a low convergence rate for solving high-dimensional functions.


## 3.3. IFFO Algorithm

Different from FFO and LGMS-FFO, single-gene mutation mode is introduced that only one gene is selected randomly to mutate in the IFFO algorithm. It is demonstrated that the single-gene mutation mode is a better choice in performance than the all-gene mutation mode for solving high-dimensional functions.IFFO algorithm is presented in which a control parameterσ is used to tune self-adaptively the search scope in a random direction of current swarm location, and offspring individuals are generated in the single-gene uniform mutation mode [28]:(6)σ⟵σmax×explogσminσmax×IterItermax,xi,d⟵δd±σ×rand,xi,j⟵δj,i=1,2,…,k,j=1,2,…,n,j≠d,where σmax is the maximum radius, σmin is the minimum radius, and d is a random integer between 1 and n.


## 4. AFFOSM Algorithm

ESSMER algorithm, an improved evolutionary strategy with single-gene mutation and elite reproduction, is presented for solving high-dimensional function [56]. In the ESSMER algorithm, the best father individual is chosen to generate λ+k offsprings, λ by Gauss mutation, and k by uniform mutation:(7)xi,d=δd+σtN0,1,xi,j=δj,i=1,2,…,λ,j=1,2,…,n,j≠d,xi,d=δd+ld+ud−ldrand,xi,j=δj,i=1,2,…,k,j=1,2,…,n,j≠d,where d is a random integer between 1 andn.σt is a variation extent related to the optimization process, and its initial value σ0 is equal to 2. σt is reduced by a quarter once the stagnant iterations (recorded as flag) reach a default iteration.Inspired by ESSMER, AFFOSM algorithm, an adaptive FFO algorithm based on single-gene mutation, is designed in this article. At first, an offspring individual is reproduced from historical best father individual. And a randomly selected gene is modified by either uniform mutation or Gauss mutation occurring by a predefined probability. Compared with ESSMER, the initial variation extents are entirely dependent on the problems to be optimized. The initial amplitude of uniform variation is equal to the width of the definition domain, a very broad range. The initial amplitude of Gauss mutation is equal to a tenth of the definition domain, a relatively little range.In the process of optimization, the amplitudeσf of uniform variation is cyclically adjusted. At the beginning of each iteration, σf is reduced by a quarter. σf will be reverted to the initial value until a better solution is achieved or a predefined accuracy is reached.The amplitudeσs of Gauss mutation is dynamically changed with the optimization progress. Those continuous stagnant iterations are recorded by a variable namedflag. The amplitude σs remains unchanged as long as flag is less than a predefined value, such as 30. Otherwise, the amplitude σs is reduced successively by a quarter unless flag is not less than 30. Meanwhile, a variable, written as σtemp, is used to save and restore the new amplitude σs once a better solution is found.AFFOSM algorithm mainly includes 3 steps as follows:Step 1.
Initialization.Set population sizeN and maximum iteration itermax. Set σmax⟵u−l, σmin⟵10−7, σf⟵σmax, and σs⟵σmax/10.Step 2.
Osphresis foraging phase.Update the mutation amplitudes.Before a new iteration, the mutation amplitudes are updated as follows:σf⟵σf×0.75ifσf<σmin, then σf⟵σmaxifflag=30, then σs⟵σs×0.75, σtemp⟵σs, flag⟵0Where the variableσtemp is used to guarantee the continuity of the Gauss mutation amplitude.Generate new solutionsFor each individual, the uniform mutation is executed with probability 0.2:(8)xi,d=δd±σfrand,xi,j=δj,j=1,2,…,n,j≠d.The Gauss mutation is executed with probability 0.8:(9)xi,d=δd+σsN0,1,xi,j=δj,j=1,2,…,n,j≠d,whered is a random integer between 1 and n.Step 3.
Vision foraging phase.Evaluate each new solution. If a better solution is discovered, then updateδ and set flag, σf, and σs to be 0, σmax, and σtemp. Otherwise, let flag equal to flag+1 and return Step 2.The computational complexity of AFFOSM is related to the size of populationsN and the number of iterations itermax. The computational complexity of one fruit fly at each iteration is one, and then, the computational complexity of AFFOSM can be summarized as ON×itermax, which is the same as original FFO, IFFO, and ESSMER.


## 5. Test Functions and Results Analysis

To verify the proposed AFFOSM algorithm, a total of 6 benchmark problems with different characteristics are listed in Table1 where n denotes the dimensionality of the functions andfx∗ is the global optimal.Table 1
Test function.
FunctionExpressionDefinition domainfx∗f1fx=∑i=1n−1100xi+1−xi22+1−xi2[−30, 30]0f2fx=∑i=1nxi2[−100, 100]0f3fx=−20exp−0.21/n∑i=1nxi2−exp1/n∑i=1ncos2πxi+20+e[−32, 32]0f4fx=∑i=1nxisinxi+0.1xi[−10, 10]0f5fx=1/4000∑i=1nxi2−∏i=1ncosxi/i+1[−600, 600]0f6fx=∑i=1nxi2−10cos2πxi+10[−5.12, 5.12]0Functionsf1 and f2 are unimodal. Function f1 is the Rosenbrock function, also referred to as the valley or banana function. Its global minimum lies in a narrow, parabolic valley. Function f2 is the sphere function, also referred to as the harmonic function with the only global minimum. Functions f3–f6 are, respectively, Ackley, Alpine, Griewank, and Rastrigin function. They are multimodal, and each of them has a large number of local minima and is difficult to be optimized.As another improved version of FFO algorithm, SFFO [57] adjusts adaptively its search along an appropriate decision variable from its previous experience in generating promising solutions.In the ESSMER algorithm, population sizeN = 10,λ = 8,k = 2, and σ0=2. For IFFO and SFFO algorithms, N = 3 and σmax=u−l/2. For the AFFOSM algorithm, N = 3, σmax=u−l, and σmin=10−7 for all algorithms.These algorithms are coded on Matlab 7.1 and run on Windows 10 operating system and Intel(R) Core(TM) i7-6600U CPU @ 2.60 GHz 2.81 GHz with 8G RAM.Each problem is run 25 times independently. The median/standard deviations over these 25 runs and the average rank of four algorithms on Friedman’s test [58] are reported in Table 2. Comparisons of convergence curves on n = 100 are also presented in Figure 2.Table 2
The performance on test functions withn = 100 and 200.
FunctionESSMERIFFOSFFOAFFOSMf1n = 1001.49E + 021.91E + 021.68E + 021.25E + 02/1.04E + 02/4.08E + 02/6.20E + 02/5.02E + 01n = 2004.31E + 024.46E + 024.59E + 023.31E + 02/4.02E + 02/4.38E + 02/7.01E + 02/3.16E + 02f2n = 1003.98E − 143.97E − 163.66E − 167.43E − 43/4.63E − 14/9.66E − 17/1.12E − 16/6.64E − 42n = 2001.34E − 073.25E − 153.01E − 151.15E − 22/1.69E − 07/6.09E − 16/4.12E − 16/1.61E − 22f3n = 1005.27E − 087.51E − 097.74E − 095.37E − 13/5.15E − 08/7.90E − 10/9.77E − 10/1.91E − 13n = 2006.13E − 051.47E − 081.53E − 081.34E − 12/2.56E − 05/1.17E − 09/1.21E − 09/1.08E − 12f4n = 1001.32E − 071.16E − 071.37E − 074.10E − 14/1.37E − 07/5.39E − 08/4.56E − 08/8.40E − 15n = 2004.53E − 046.63E − 076.73E − 073.84E − 12/1.71E − 04/1.51E − 07/1.23E − 07/2.27E − 12f5n = 1002.14E − 019.90E − 031.23E − 027.40E − 03/1.45E − 01/2.41E − 02/2.21E − 02/2.51E − 02n = 2002.95E − 019.90E − 031.23E − 029.90E − 03/1.76E − 01/2.72E − 02/1.81E − 02/1.22E − 02f6n = 1001.26E − 129.95E − 019.95E − 012.01E − 07/1.28E − 02/7.88E − 01/7.86E − 01/4.96E − 01n = 2003.76E − 061.69E + 011.89E + 012.00E + 00/7.57E − 01/5.38E + 00/3.77E + 00/1.49E + 00Rn = 1003.172.6672.8331.333n = 2003.2642.5562.8191.361Figure 2
Performance comparison on test functions onn = 100.Comparing with the ESSMER algorithm, the AFFOSM algorithm performs better for functionsf1–f5 with both n = 100 and n = 200. AFFOSM algorithm produces a smaller median; the 0, 29, 5, 7, and 2 orders of magnitude reduced with n = 100 and the 0, 15, 7, 8, and 2 orders with n = 200, respectively.Comparing with the IFFO algorithm onn = 100, the AFFOSM algorithm performs better for all test functions. The smaller median is gained with the 0, 27, 4, 7, 0, and 6 orders of magnitude reduced. Comparing with the IFFO algorithm on n = 200, the AFFOSM algorithm performs better for functions f1, f2, f3, and f4. The smaller median is gained with the 0, 7, 4, and 5 orders of magnitude reduced. Meanwhile, the same median value is gained for function f5.Comparing with the SFFO algorithm onn = 100, the AFFOSM algorithm performs better for all test functions. The smaller median is gained with the 0, 27, 4, 7, 1, and 6 orders of magnitude reduced.Comparing with the IFFO algorithm onn = 200, the AFFOSM algorithm performs better for functions f1, f2, f3, f4, and f5. The smaller median is gained with the 0, 7, 4, 5, and 1 orders of magnitude reduced.For test functionsf1, f2, f3, f4, and f5, AFFOSM performs best on both n = 100 and n = 200. ESSMER algorithm, meanwhile, performs the best only for function f6 on both n = 100 and n = 200. The IFFO algorithm performs the best only in the case of function f5 on n = 200. Unfortunately, the SFFO algorithm is the best one in no case.Similarly, the average rankR on Friedman’s test shows the proposed AFFOSM scheme is superior to other ones based on single-gene mutation.


## 6. Conclusion and Future Work

For high-dimensional problems, the algorithms based on single-gene mutation have better performance on convergency and accuracy than those based on all-gene mutation. To overcome the shortage of the FFO to solve the high-dimensional optimization problems, single-gene mutation and adaptive mutation range control technique are introduced into the AFFOSM algorithm proposed in this article. In the AFFOSM algorithm, the main function of Gauss mutation is to search locally around the historic best solution. Uniform mutation not only plays a role to search globally in the whole space but also improves the efficiency of local search when uniform mutation range is significantly smaller than the Gauss mutation range. Unrelated to iterations, mutation range is adjusted by the reference of the optimization progression. Simulations show that the AFFOSM algorithm is better than those based on single-gene mutation, such as ESSMER, IFFO, and SFFO.An interesting topic for future research would be investigating the real impact of some parameters values in AFFOSM to analyze their contributions to the algorithm performance.Another interesting topic for future research would be applying the AFFOSM algorithm to solve constraint or multiobjective optimization problems and practical engineering problems such as benchmark structural optimization problems.



---

*Source: 9676279-2020-11-17.xml*