An improved fruit fly optimization algorithm for solving traveling salesman problem

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.

Keywords

Traveling salesman problem / Fruit fly optimization algorithm / Elimination mechanism / Vision search / Operat

References

[1] Bellman , R.E., Dreyfus , S.E., 1962. Applied Dynamic Pro-gramming. Princeton University Press, New Jersey, USA, p.50–68.

[2] 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

[3] 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

[4] 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

[5] 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

[6] 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

[7] 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

[8] Geng , X.T., Chen , Z.H., Yang , W., , 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

[9] Grefenstette , J.J., Gopal , R., Rosmaita , B.J., , 1985. Ge-netic algorithms for the traveling salesman problem. 1st Int. Conf. on Genetic Algorithms and Their Applications, p.160–168.

[10] 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

[11] 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

[12] Hoffmann , M., Mühlenthaler , M., Helwig , S., , 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

[13] 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

[14] 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

[15] Kirkpatrick , S., 1984. Optimization by simulated annealing: quantitative studies. J. Stat. Phys. , 34(5-6):975–986. https://doi.org/10.1007/BF01009452

[16] 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

[17] Little , J.D.C., Murty , K.G., Sweeney , D.W., , 1963. An algorithm for the traveling salesman problem. Oper. Res. , 11(6):972–989. https://doi.org/10.1287/opre.11.6.972

[18] 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

[19] 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

[20] 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

[21] Ouyang , X.X., Zhou , Y.G., Luo , Q.F., , 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

[22] Pan , W.T., 2011. Fruit Fly Optimization Algorithm. Tsang Hai Book Publishing Co., Taipei, China, p.221–232 (in Chi-nese).

[23] 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

[24] 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

[25] 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

[26] 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

[27] Zhou , Y.Q., Luo , Q.F., Chen , H., , 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

RIGHTS & PERMISSIONS

2017 Zhejiang University and Springer-Verlag GmbH Germany