Abstract
The traveling salesman problem (TSP), a typical non-deterministic polynomial (NP) hard problem, has been used in many engineering applications. As a new swarm-intelligence optimization algorithm, the fruit fly optimization algorithm (FOA) is used to solve TSP, since it has the advantages of being easy to understand and having a simple implementation. However, it has problems, including a slow convergence rate for the algorithm, easily falling into the local optimum, and an insufficient optimi-zation precision. To address TSP effectively, three improvements are proposed in this paper to improve FOA. First, the vision search process is reinforced in the foraging behavior of fruit flies to improve the convergence rate of FOA. Second, an elimination mechanism is added to FOA to increase the diversity. Third, a reverse operator and a multiplication operator are proposed. They are performed on the solution sequence in the fruit fly’s smell search and vision search processes, respectively. In the experiment, 10 benchmarks selected from TSPLIB are tested. The results show that the improved FOA outperforms other alternatives in terms of the convergence rate and precision.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bellman, R.E., Dreyfus, S.E., 1962. Applied Dynamic Pro-gramming. Princeton University Press, New Jersey, USA, p.50–68.
Clerc, M., 2004. Discrete particle swarm optimization, illus-trated by the traveling salesman problem. In: Onwubolu, G.C., Babu, B.V. (Eds.), New Optimization Techniques in Engineering. Springer Berlin Heidelberg, p.219–239. https://doi.org/10.1007/978-3-540-39930-8_8
Croes, G.A., 1958. A method for solving traveling-salesman problems. Oper. Res., 6(6): 791–812. https://doi.org/10.1287/opre.6.6.791
Ding, C., Cheng, Y., He, M., 2007. Two-level genetic algorithm for clustered traveling salesman problem with application in large-scale TSPs. Tsinghua Sci. Technol., 12(4): 459–465. https://doi.org/10.1016/S1007-0214(07)70068-8
Dong, G.F., Guo, W.W., Tickle, K., 2012. Solving the traveling salesman problem using cooperative genetic ant systems. Exp. Syst. Appl., 39(5): 5006–5011. https://doi.org/10.1016/j.eswa.2011.10.012
Dorigo, M., Gambardella, L.M., 1997. Ant colonies for the travelling salesman problem. BioSystems, 43(2): 73–81. https://doi.org/10.1016/S0303-2647(97)01708-5
Escario, J.B., Jimenez, J.F., Giron-Sierra, J.M., 2015. Ant colony extended: experiments on the travelling salesman problem. Exp. Syst. Appl., 42(1): 390–410. https://doi.org/10.1016/j.eswa.2014.07.054
Geng, X.T., Chen, Z.H., Yang, W., et al., 2011. Solving the traveling salesman problem based on an adaptive simu-lated annealing algorithm with greedy search. Appl. Soft Comput., 11(4): 3680–3689. https://doi.org/10.1016/j.asoc.2011.01.039
Grefenstette, J.J., Gopal, R., Rosmaita, B.J., et al., 1985. Ge-netic algorithms for the traveling salesman problem. 1st Int. Conf. on Genetic Algorithms and Their Applications, p.160–168.
Gündüz, M., Kiran, M.S., Özceylan, E., 2015. A hierarchic approach based on swarm intelligence to solve the travel-ing salesman problem. Turk. J. Electric. Eng. Comput. Sci., 23(1): 103–117. https://doi.org/10.3906/elk-1210-147
Hendtlass, T., 2003. Preserving diversity in particle swarm optimisation. In: Chung, P.W.H., Hinde, C., Ali, M. (Eds.), Developments in Applied Artificial Intelligence. Springer Berlin Heidelberg, p.31–40. https://doi.org/10.1007/3-540-45034-3_4
Hoffmann, M., Mühlenthaler, M., Helwig, S., et al., 2011. Discrete particle swarm optimization for TSP: theoretical results and experimental evaluations. In: Bouchachia, A. (Ed.), Adaptive and Intelligent Systems. Springer Berlin Heidelberg, p.416–427. https://doi.org/10.1007/978-3-642-23857-4_40
Jolai, F., Ghanbari, A., 2010. Integrating data transformation techniques with Hopfield neural networks for solving travelling salesman problem. Exp. Syst. Appl., 37(7): 5331–5335. https://doi.org/10.1016/j.eswa.2010.01.002
Karaboga, D., Gorkemli, B., 2011. A combinatorial artificial bee colony algorithm for traveling salesman problem. IEEE Int. Symp. on Innovations in Intelligent Systems and Applications, p.50–53. https://doi.org/10.1109/INISTA.2011.5946125
Kirkpatrick, S., 1984. Optimization by simulated annealing: quantitative studies. J. Stat. Phys., 34(5–6): 975–986. https://doi.org/10.1007/BF01009452
Lawler, E.L., Wood, D.E., 1966. Branch-and-bound methods: a survey. Oper. Res., 14(4): 699–719. https://doi.org/10.1287/opre.14.4.699
Little, J.D.C., Murty, K.G., Sweeney, D.W., et al., 1963. An algorithm for the traveling salesman problem. Oper. Res., 11(6): 972–989. https://doi.org/10.1287/opre.11.6.972
Liu, F., Zeng, G.Z., 2009. Study of genetic algorithm with reinforcement learning to solve the TSP. Exp. Syst. Appl., 36(3): 6995–7001. https://doi.org/10.1016/j.eswa.2008.08.026
Mahi, M., Baykan, Ö.K., Kodaz, H., 2015. A new hybrid method based on particle swarm optimization, ant colony optimization and 3-opt algorithms for traveling salesman problem. Appl. Soft Comput., 30: 484–490. https://doi.org/10.1016/j.asoc.2015.01.068
Masutti, T.A.S., de Castro, L.N., 2009. A self-organizing neural network using ideas from the immune system to solve the traveling salesman problem. Inform. Sci., 179(10): 1454–1468. https://doi.org/10.1016/j.ins.2008.12.016
Ouyang, X.X., Zhou, Y.G., Luo, Q.F., et al., 2013. A novel discrete cuckoo search algorithm for spherical traveling salesman problem. Appl. Math. Inform. Sci., 7(2): 777–784. https://doi.org/10.12785/amis/070248
Pan, W.T., 2011. Fruit Fly Optimization Algorithm. Tsang Hai Book Publishing Co., Taipei, China, p.221–232 (in Chi-nese).
Pan, W.T., 2012. A new fruit fly optimization algorithm: taking the financial distress model as an example. Knowl.-Based Syst., 26: 69–74. https://doi.org/10.1016/j.knosys.2011.07.001
Pasti, R., de Castro, L.N., 2006. A neuro-immune network for solving the traveling salesman problem. IEEE Int. Joint Conf. on Neural Network, p.3760–3766. https://doi.org/10.1109/IJCNN.2006.247394
Peker, M., Şen, B., Kumru, P.Y., 2013. An efficient solving of the traveling salesman problem: the ant colony system having parameters optimized by the Taguchi method. Turk. J. Electric. Eng. Comput. Sci., 21(55): 2015–2036. https://doi.org/10.3906/elk-1109-44
Wu, J.Q., Ouyang, A.J., 2012. A hybrid algorithm of ACO and delete-cross method for TSP. IEEE Int. Conf. on Industrial Control and Electronics Engineering, p.1694–1696. https://doi.org/10.1109/ICICEE.2012.448
Zhou, Y.Q., Luo, Q.F., Chen, H., et al., 2015. A discrete inva-sive weed optimization algorithm for solving traveling salesman problem. Neurocomputing, 151: 1227–1236. https://doi.org/10.1016/j.neucom.2014.01.078
Author information
Authors and Affiliations
Corresponding authors
Additional information
Project supported by the National Natural Science Foundation of China (Nos. 61472159 and 61373051)
Rights and permissions
About this article
Cite this article
Huang, L., Wang, Gc., Bai, T. et al. An improved fruit fly optimization algorithm for solving traveling salesman problem. Frontiers Inf Technol Electronic Eng 18, 1525–1533 (2017). https://doi.org/10.1631/FITEE.1601364
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1631/FITEE.1601364
Keywords
- Traveling salesman problem
- Fruit fly optimization algorithm
- Elimination mechanism
- Vision search
- Operator