Full Text:   <784>

CLC number: TP181

On-line Access: 2017-12-04

Received: 2016-06-22

Revision Accepted: 2017-01-23

Crosschecked: 2017-11-06

Cited: 0

Clicked: 1782

Citations:  Bibtex RefMan EndNote GB/T7714

 ORCID:

Lan Huang

http://orcid.org/0000-0003-3223-3777

-   Go to

Article info.
Open peer comments

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

http://doi.org/10.1631/FITEE.1601364


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


Lan Huang, Gui-chao Wang, Tian Bai, Zhe Wang. An improved fruit fly optimization algorithm for solving traveling salesman problem[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(10): 1525-1533.

@article{title="An improved fruit fly optimization algorithm for solving traveling salesman problem",
author="Lan Huang, Gui-chao Wang, Tian Bai, Zhe Wang",
journal="Frontiers of Information Technology & Electronic Engineering",
volume="18",
number="10",
pages="1525-1533",
year="2017",
publisher="Zhejiang University Press & Springer",
doi="10.1631/FITEE.1601364"
}

%0 Journal Article
%T An improved fruit fly optimization algorithm for solving traveling salesman problem
%A Lan Huang
%A Gui-chao Wang
%A Tian Bai
%A Zhe Wang
%J Frontiers of Information Technology & Electronic Engineering
%V 18
%N 10
%P 1525-1533
%@ 2095-9184
%D 2017
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.1601364

TY - JOUR
T1 - An improved fruit fly optimization algorithm for solving traveling salesman problem
A1 - Lan Huang
A1 - Gui-chao Wang
A1 - Tian Bai
A1 - Zhe Wang
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 18
IS - 10
SP - 1525
EP - 1533
%@ 2095-9184
Y1 - 2017
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.1601364


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个算例进行仿真实验,并与其它算法的实验结果进行对比,结果证明该算法不仅收敛速度快,而且寻优精度高。

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

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

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>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE