An Adaptive Fruit Fly Optimization Algorithm for Optimization Problems

L. Q. Zhang¹, J. Xiong^2*, J. K. Liu²

¹College of Computers and Engineering, Chongqing Three Gorges University, Chongqing, China.
²College of Mathematics and Statistics, Chongqing Three Gorges University, Chongqing, China.

DOI: 10.4236/jamp.2023.1111229                

Abstract

In this paper, we present a new fruit fly optimization algorithm with the adaptive step for solving unconstrained optimization problems, which is able to avoid the slow convergence and the tendency to fall into local optimum of the standard fruit fly optimization algorithm. By using the information of the iteration number and the maximum iteration number, the proposed algorithm uses the floor function to ensure that the fruit fly swarms adopt the large step search during the olfactory search stage which improves the search speed; in the visual search stage, the small step is used to effectively avoid local optimum. Finally, using commonly used benchmark testing functions, the proposed algorithm is compared with the standard fruit fly optimization algorithm with some fixed steps. The simulation experiment results show that the proposed algorithm can quickly approach the optimal solution in the olfactory search stage and accurately search in the visual search stage, demonstrating more effective performance.

Keywords

Swarm Intelligent Optimization Algorithm, Fruit Fly Optimization Algorithm, Adaptive Step, Local Optimum, Convergence Speed

1. Introduction

Swarm intelligent optimization algorithm belongs to bionic optimization algorithm, which originates from the daily survival behavior of all kinds of organisms in nature, such as the ant colony algorithm [1] , the genetic algorithm [2] , the fruit fly optimization algorithm [3] and so on. These swarm intelligence optimization algorithms have been widely used in transportation, network communication, medical security, national defense construction and other fields, and have brought remarkable optimization results.

In this paper, we are interested in the fruit fly optimization algorithm (FOA), which was first proposed by observing and simulating the foraging behavior of fruit flies in [3] . This algorithm is one of global optimization swarm intelligence algorithms, and has a simple structure, fewer parameters and low computational complexity. Recently, this algorithm has been favored by many researchers, and widely used in practical problems. For example, to solve the multidimensional knapsack problem, Wang et al. [4] proposed a new binary fruit fly optimization algorithm including smell-based search process, local vision-based search process and global vision-based search process. Based on the geometric reasoning approach and the standard FOA algorithm, Wang et al. [5] established an effective algorithm to reduce the computer consumption. The results showed that this algorithm is able to decline the expenditure and the time of casting production cycle. Based on a chaotic fly optimization algorithm, Fei et al. [6] presented a new support vector machine optimization method, in which a mutation strategy is used to simultaneously perform parameter setting turning for the support vector machine optimization method and feature selection. Wu and Liu et al. [7] proposed a new fruit fly optimization algorithm with four extra mechanisms for solving engineering optimization problems. Bezdan and Stoean et al. [8] proposed a hybrid fruit fly optimization algorithm to solve the text document clustering.

With the increasingly widespread applications of the FOA algorithm, its shortcomings make it difficult to meet the needs of researchers. This has inspired researchers to adopt new strategies to improve the standard FOA algorithm. For example, based on the standard FOA algorithm and the simulated annealing algorithm, Yang et al. [9] proposed a modified FOA algorithm, and its numerical results are significantly superior to the standard FOA algorithm. By using the Gaussian mutation operator and the chaotic local search strategy, Zhang et al. [10] established a new FOA algorithm which effectively overcame the shortcomings of the standard FOA algorithm. The experimental results showed that the new strategies improved the performance of the algorithm in optimization calculations. In order to effectively solve the clustering parameter problems and the continuous function optimization problems, Han et al. [11] studied a novel FOA algorithm, and its main characteristics has the trend search and co-evolution. Li et al. [12] proposed a new strategy by adding the cat mapping in the standard FOA algorithm to carry out the individual distribution, and established an improved FOA algorithm. The numerical results indicated that the computational performance of the proposed algorithm outperformed that of the other peers. Meng and Pan [13] presented an effect FOA algorithm to solve the classical multidimensional knapsack problem. This approach uses the parallel search which can balance exploitation and exploration of the fruit fly populations. In order to solve the new task scheduling, Aggarwal et al. [14] proposed a self-adaptive FOA algorithm, which is able to complete the workflow completion in an effective way and reduce work costs. Based on the chaotic map, the adaptive DE/best/2mutation operator and the orthogonal learning mechanism, Chandra and Niyogi [15] studied an effective FOA algorithm to solve the web service selection problem. To optimize the execution time and reduce the cost, Qin et al. [16] proposed a new hybrid collaborative multi-objective FOA algorithm based on the reference points-based cluster strategy. Based on the independent variational mode decomposition, Li and Xu [17] established an effective FOA algorithm to deal with the laser cladding operations. Zhu et al. [18] proposed a discrete knowledge-guided learning FOA algorithm to deal with the distributed no-wait flow shop scheduling problem with the due windows. Other relevant research results can be found in references [19] - [29] .

In order to improve the convergence rate and avoid falling into the local extremes, in this paper we propose an adaptive step size fruit fly optimization algorithm (ASFOA) for solving optimization problems by using the information of the iterations. By adjusting the step size, the proposed algorithm can make fruit fly swarm adopt the big step length search in the olfactory search stage, improve the convergence speed, and make fruit fly swarm approach the optimal value quickly. In the visual search stage, small steps are used for precise search to avoid excessive search and falling into local extremes.

The remaining part of the paper is organized as follows. In Section 2, we analyze our algorithm for solving unconstrained optimization problems and provide its specific steps. In Section 3, we give the experimental simulation results. We summarize the whole paper in Section 4.

2. Fundamental Principles

In the standard FOA algorithm, fruit fly individual approaches to the optimal value with a fixed step size, which directly affects its performance. When the fixed step size is set too large, the algorithm is beneficial to improve the convergence speed in the early stage of the iterative process, but it is unable to provide the exact search for local areas in the later stage. This easily leads to the algorithm falling into the local optima. When the fixed step size is too small, the algorithm can perform the exact search for local areas in the later stage, but the algorithm cannot provide fast search speed in the early stage, which results in the slow convergence speed. Thus, the step size selection mechanism has a significant impact on the computational performance and convergence of the standard FOA algorithm.

In this paper, we propose a step size selection mechanism, in which the step size gradually decreases as the number of iterations increases. This can ensure that the algorithm uses large step sizes to quickly approach the optimal solution of the problem in the early stage and uses small step size for the precise search in the later stage, which improves the computational performance and convergence of the algorithm. Based on standard FOA algorithm, we give the specific process of the adaptive step size fruit fly optimization algorithm for solving optimization problems.

Algorithm 2.1 (ASFOA algorithm):

Step 0. Give some parameters, including the population size (sizepop), the maximum number of iterations (maxgen), the problem dimension (dim), the initial position range (LR).

Step 1. Randomly initialize the fruit fly population locations, i.e.,

$x_{axis}=rand\left(LR\right)\mathrm{,}{y}_{axis}=rand\left(LR\right)\mathrm{.}$ (1)

Step 2. Calculate the random direction and distance of fruit fly individual, i.e.

$x_i=x_{axis}+{\alpha }_i\ast rand\left(\mathrm{1,}dim\right)\mathrm{,}$ (2)

$y_i=y_{axis}+{\alpha }_i\ast rand\left(\mathrm{1,}dim\right)\mathrm{,}$ (3)

where $rand\left(\cdot \mathrm{,}\cdot \right)$ is a randomly generated function in Matlab software, ${\alpha }_i=floor\left(maxgen/i\right)$ is the step size in this iteration, which is adjusted according to the number of iterations.

Step 3. Compute

$s_i=1/d_i\mathrm{,}$ (4)

where $d_i=\sqrt{x_i^2+y_i^2}$ is the distance between the i-th fruit fly and the origin point, $s_i$ is the judgment value of smell concentration of the i-th fruit fly.

Step 4. Substitute the judgment value of the smell concentration into the judgment function, namely,

$smel{l}_i=f\left(s_i\right)\mathrm{,}$ (5)

where $f\mathrm{<mo>\; :\; </mo>}{R}^n\to R$ is the objective function, $smel{l}_i$ is the judgment function value of the smell concentration of the i-th fruit fly.

Step 5. In the fruit fly swarm, identify the best smell concentration value (Bestsmell) and its index (Bestindex), i.e.,

$\left[Bestsmell\mathrm{,}Bestindex\right]=min\left(smell\right)\mathrm{.}$ (6)

Step 6. Record the best smell concentration value and the corresponding coordinates x and y. Other fruit flies use their vision to fly towards the optimal individual, i.e.,

$smellBest=Bestsmell\mathrm{,}$ (7)

$x_{axis}=x\left(Bestindex\right)\mathrm{,}$ (8)

$y_{axis}=y\left(Bestindex\right)\mathrm{.}$ (9)

Step 7. Start the optimization iteration: repeat Steps 2-6. Assessment whether the current best concentration value is better than the historical best concentration value, otherwise go to Step 6.

Remark 2.1 The step size ${\alpha }_i=floor\left(maxgen/i\right)$ decreases gradually as the number of iterations increases. This not only meets the large step size needed in the early stage of iterative process, but also meets the small step size needed in the later stage of iterative process. This implies that the ASFOA algorithm can converge quickly in the early stage, and avoid falling into local optimal in the late stage.

3. Simulation Experiment Analysis

In this paper, we carry out some simulation experiments to assess the ASFOA algorithm on some commonly benchmark functions, and compare the ASFOA algorithm with the standard FOA algorithm. The adopted benchmark functions are listed in Table 1. Among these functions, the first two are unimodal functions, and the others are multimodal functions. In the simulation experiment, $maxgen=200$ , $sizepop=30$ , $dim=30$ . The step sizes of the standard FOA algorithm are respectively taken $t=2$ and $t=10$ . The codes of these algorithms are written using MATLAB 7.0 and run on an HP computer with Intel (R) Core (TM) i7-9700 CPU 3.00 GHZ and 8.00 G memory.

In order to make the simulation experiments fairly, we did ten independent experiments on each benchmark function, and took the average values of the maximum value (Max), minimum value (Min), optimized mean value (Mean) and standard deviation (Std) as the evaluation indexes. The detailed results are listed in Table 2. Table 2 shows that the ASFOA algorithm is superior to the standard FOA algorithm for the evaluation indicators except for the Exponential function, but the ASFOA algorithm still outperforms the standard FOA algorithm in "Std" for the Exponential function. This indicates that the ASFOA algorithm has been significantly improved in the optimization accuracy. To more intuitively compare and analyze the characteristics of these algorithms, the

Table 1. The benchmark functions.

Table 2. Experimental Results via ASFOA algorithm and the standard FOA algorithm.

fitness curves of the benchmark functions are shown in Figure 1. It is not difficult to find that the ASFOA algorithm can rapidly decline in the early stage of the iterative process and converge in the later stage. To sum up, the ASFOA algorithm has been significantly improved in the optimization efficiency.

4. Conclusion

Based on the limitations and shortcomings of the standard FOA algorithm, in this paper we use the adaptive step size to establish the ASFOA algorithm, which uses different step sizes in different search stages. The experiment results show that the ASFOA algorithm not only breaks through the limitations and shortcomings of the standard FOA algorithm, but also has some improvements in the

Figure 1. Evolution curves of fitness of these benchmark functions via ASFOA algorithm and FOA algorithm.

convergence speed and optimization accuracy compared to the standard FOA algorithm.

Acknowledgements

This research was partially supported by the Foundation of Intelligent Ecotourism Subject Group of Chongqing Three Gorges University (zhlv20221002, zhlv20221014), Foundation of Chongqing Municipal Key Laboratory of Institutions of Higher Education ([2017]3), Foundation of Chongqing Development and Reform Commission (2017[1007]), Chongqing Research Program of Basic Research and Frontier Technology (Grant number: cstc2021jcyj-msxmX0233). The authors wish to thank the editors and the anonymous referees for providing their valuable suggestions which have significantly improved the quality of our paper.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Dorigo, M. and Stutzle, T. (2004) Ant Colony Optimization for NP-Hard Problems. MIT Press, London.
[2]	Holand, J.H. (1992) Genetic Algorithm. Scientific American, 267, 66-72. https://doi.org/10.1038/scientificamerican0792-66
[3]	Pan, W.T. (2011) Fruit Fly Optimization Algorithm. Tsang Hai Book Publishing Co, Taipei.
[4]	Wang, L., Zheng, X.L., et al. (2013) A Novel Binary Fruit Fly Optimization Algorithm for Solving the Multidimensional Knapsack Problem. Knowledge-Based Systems, 48, 17-28. https://doi.org/10.1016/j.knosys.2013.04.003
[5]	Wang, T., Yin, Y., et al. (2018) Optimal Riser Design Method Based on Geometric Reasoning Method and Fruit Fly Optimization Algorithm in CAD. International Journal of Advanced Manufacturing Technology, 96, 53-65. https://doi.org/10.1007/s00170-017-1496-2
[6]	Fei, Y., Lou, X.Y., et al. (2017) An Improved Chaotic Fruit Fly Optimization Based on a Mutation Strategy for Simultaneous Feature Selection and Parameter Optimization for SVM and Its Applications. PLOS ONE, 12, e0173516. https://doi.org/10.1371/journal.pone.0173516
[7]	Wu, L., Liu, Q., et al. (2018) A New Improved Fruit Fly Optimization Algorithm IAFOA and Its Application to Solve Engineering Optimization Problems. Knowledge-Based Systems, 144, 153-173. https://doi.org/10.1016/j.knosys.2017.12.031
[8]	Bezdan, T., Stoean, C., et al. (2021) Hybrid Fruit-Fly Optimization Algorithm with K-Means for Text Document Clustering. Mathematics, 9, Article No. 1929. https://doi.org/10.3390/math9161929
[9]	Yang, M., Liu, N.B., et al (2017) Image 1D OMP Sparse Decomposition with Modified Fruit-Fly Optimization Algorithm. Cluster Computing, 20, 3015-3022. https://doi.org/10.1007/s10586-017-0966-5
[10]	Zhang, X., Xu, Y.T., et al (2020) Gaussian Mutational Chaotic Fruit Fly-Built Optimization and Feature Selection. Expert System with Application, 141, Article ID: 112976. https://doi.org/10.1016/j.eswa.2019.112976
[11]	Han, X., Liu, Q., et al (2017) Novel Fruit Fly Optimization Algorithm with Trend Search and Co-Evolution. Knowledge-Based Systems, 141, 11-17. https://doi.org/10.1016/j.knosys.2017.11.001
[12]	Li, X., Sun, L., et al. (2018) An Improved Fruit Fly Optimization Algorithm and Its Application in Heat Exchange Fouling Ultrasonic Detection. Mathematical Problems in Engineering, 2018, Article ID: 4365873. https://doi.org/10.1155/2018/4365873
[13]	Meng, T. and Pan, Q.K. (2017) An Improved Fruit Fly Optimization Algorithm for Solving the Multidimensional Knapsack Problem. Mathematics, 50, 79-93. https://doi.org/10.1016/j.asoc.2016.11.023
[14]	Aggarwal, A., Dimri, P., et al. (2021) Self Adaptive Fruit Fly Algorithm for Multiple Workflow Scheduling in Cloud Computing Environment. Mathematics, 50, 1704-1730. https://doi.org/10.1108/K-11-2019-0757
[15]	Chandra, M. and Niyogi, R. (2023) QoS Aware Web Service Selection Using Orthogonal Array Learning on Fruit Fly Optimization Approach. International Journal of Pervasive Computing and Communications, 19, 343-363. https://doi.org/10.1108/IJPCC-08-2020-0101
[16]	Qin, S., Pi, D., et al. (2022) Hybrid Collaborative Multi-Objective Fruit Fly Optimization Algorithm for Scheduling Workflow in Cloud Environment. Swarm and Evolutionary Computation, 68, Article ID: 101008. https://doi.org/10.1016/j.swevo.2021.101008
[17]	Li, Y. and Xu, F. (2023) Acoustic Emission Sources Localization of Laser Cladding Metallic Panels Using Improved Fruit Fly Optimization Algorithm-Based Independent Variational Mode Decomposition. International Journal of Pervasive Computing and Communications, 166, Article ID: 108514. https://doi.org/10.1016/j.ymssp.2021.108514
[18]	Zhu, N., Zhao, F., et al. (2022) A Discrete Learning Fruit Fly Algorithm Based on Knowledge for the Distributed No-Wait Flow Shop Scheduling with Due Windows. Expert Systems with Applications, 198, Article ID: 116921. https://doi.org/10.1016/j.eswa.2022.116921
[19]	Hu, G. and Wang, G. (2021) Forecasting Energy Consumption of Long-Distance Oil Products Pipeline Based on Improved Fruit Fly Optimization Algorithm and Support Vector Regression. Energy, 224, Article ID: 120153. https://doi.org/10.1016/j.energy.2021.120153
[20]	Wu, L., Zuo, C., et al. (2017) Acoustic Emission Sources Localization of Laser Cladding Metallic Panels Using Improved Fruit Fly Optimization Algorithm-Based Independent Variational Mode Decomposition. Soft Computing, 21, 1877-1893. https://doi.org/10.1007/s00500-015-1890-3
[21]	Mousavi, S.M., Tavana, M., et al. (2019) Acoustic Emission Sources Localization of Laser Cladding Metallic Panels Using Improved Fruit Fly Optimization Algorithm-Based Independent Variational Mode Decomposition. Neural Computing and Applications, 31, 873-885. https://doi.org/10.1007/s00521-017-3115-4
[22]	Niu, J., Zhong, W., et al. (2015) Fruit Fly Optimization Algorithm Based on Differential Evolution and Its Application on Gasification Process Operation Optimization. International Journal of Pervasive Computing and Communications, 88, 253-263. https://doi.org/10.1016/j.knosys.2015.07.027
[23]	Wang, T., Xu, J., et al. (2021) A Novel Fruit Fly Optimization Algorithm with Levi Flight and Challenge Probability. Procedia Computer Science, 183, 182-188. https://doi.org/10.1016/j.procs.2021.02.048
[24]	Roselin Kiruba, R. and Sree Sharmila, T. (2021) Secure Data Hiding by Fruit Fly Optimization Improved Hybridized Seeker Algorithm. Multidimensional Systems and Signal Processing, 32, 405-430. https://doi.org/10.1007/s11045-019-00697-w
[25]	Shi, H.S., Ye, S., et al. (2015) An Improved Fruit Fly Optimization Algorithm and Its Application. International Conference on Advances in Mechanical Engineering and Industrial, Zhengzhou, 2015, 497-502.
[26]	Lin, S.M. (2013) Analysis of Service Satisfaction in Web Auction Logistics Service Using a Combination of Fruit Fly Optimization Algorithm and General Regression Neural Network. Neural Computing and Applications, 22, 783-791. https://doi.org/10.1007/s00521-011-0769-1
[27]	Xiao, C.C., Hao, K.G., et al. (2015) An Improved Fruit Fly Optimization Algorithm Inspired From Cell Communication Mechanism. Procedia Computer Science, 2015, Article ID: 492195. https://doi.org/10.1155/2015/492195
[28]	Du, T.S., Ke, X.T., et al. (2015) Improved Fruit Fly Optimization Algorithm for Application to Structural Engineering Design Optimization Problems. Applied Mathematical Modelling, 55, 314-339. https://doi.org/10.1016/j.apm.2017.08.013
[29]	Ding, G., Qiao, Y., et al. (2021) Fruit Fly Optimization Algorithm Based on a Novel Fluctuation Model and Its Application in Band Selection for Hyperspectral Image. Journal of Ambient Intelligence and Humanized Computing, 2015, 1517-1539. https://doi.org/10.1007/s12652-020-02226-1