JZUS - Journal of Zhejiang University SCIENCE

Frontiers of Information Technology & Electronic Engineering 2017 Vol.18 No.10 P.1525-1533

An improved fruit fly optimization algorithm for solving traveling salesman problem

Author(s): Lan Huang, Gui-chao Wang, Tian Bai, Zhe Wang
Affiliation(s): College of Computer Science and Technology, Jilin University, Changchun 130012, China; more
Corresponding email(s): huanglan@jlu.edu.cn, wgc290029@163.com, wz2000@jlu.edu.cn
Key Words: Traveling salesman problem, Fruit fly optimization algorithm, Elimination mechanism, Vision search, Operator

Share this article to： More <<< Previous Article \|Next Article >>>

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 optimization 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.

一种改进的果蝇优化算法及其在旅行商问题求解中的应用

概要：旅行商问题（traveling salesman problem, TSP）是经典的NP（non-deterministic polynomial）难问题，在实际工程中有许多应用。而果蝇优化算法作为一种用于求解TSP问题的新群智能算法，具有易于理解、实现简单等优点。然而，该算法收敛速度慢、易陷入局部最优，从而导致寻优精度不高。为了有效求解TSP问题，本文提出了三种改进方法，以优化果蝇算法在TSP求解中的应用。一是，更加注重果蝇觅食行为中的视觉搜索能力，从而增强果蝇算法的收敛能力；二是，在果蝇优化算法中融入了淘汰机制以增加种群多样性；三是，提出了逆序操作算子和乘法操作算子，并将这两种基本操作算子运用到果蝇算法求解TSP问题上。本文对TSPLIB中的10个算例进行仿真实验，并与其它算法的实验结果进行对比，结果证明该算法不仅收敛速度快，而且寻优精度高。

关键词：旅行商问题；果蝇优化算法；淘汰机制；视觉搜索；操作算子

Reference

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

[2]Clerc, M., 2004. Discrete particle swarm optimization, illustrated by the traveling salesman problem. In: Onwubolu, G.C., Babu, B.V. (Eds.), New Optimization Techniques in Engineering. Springer Berlin Heidelberg, p.219-239.

[3]Croes, G.A., 1958. A method for solving traveling-salesman problems. Oper. Res., 6(6):791-812.

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

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

[6]Dorigo, M., Gambardella, L.M., 1997. Ant colonies for the travelling salesman problem. BioSystems, 43(2):73-81.

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

[8]Geng, X.T., Chen, Z.H., Yang, W., et al., 2011. Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search. Appl. Soft Comput., 11(4):3680-3689.

[9]Grefenstette, J.J., Gopal, R., Rosmaita, B.J., et al., 1985. Genetic 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 traveling salesman problem. Turk. J. Electric. Eng. Comput. Sci., 23(1):103-117.

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

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

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

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

[15]Kirkpatrick, S., 1984. Optimization by simulated annealing: quantitative studies. J. Stat. Phys., 34(5-6):975-986.

[16]Lawler, E.L., Wood, D.E., 1966. Branch-and-bound methods: a survey. Oper. Res., 14(4):699-719.

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

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

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

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

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

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

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

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

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

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

[27]Zhou, Y.Q., Luo, Q.F., Chen, H., et al., 2015. A discrete invasive weed optimization algorithm for solving traveling salesman problem. Neurocomputing, 151:1227-1236.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Similar articles

- Go to

一种改进的果蝇优化算法及其在旅行商问题求解中的应用

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference