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

黄岚; 王贵超; 白天; 王喆

doi:10.1631/FITEE.1601364

Your Location：

Home >

Browse articles >

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

常规文章 | Updated：2022-05-19

- 一种改进的果蝇优化算法及其在旅行商问题求解中的应用
- An improved fruit fly optimization algorithm for solving traveling salesman problem
- 信息与电子工程前沿（英文） 2017年18卷第10期页码：1525-1533
- Affiliations：
  
  College of Computer Science and Technology, Jilin University, Changchun 130012, China
  Key Laboratory of Symbolic Computation and Knowledge Engineering (Jilin University), Ministry of Education Changchun 130012, China
- Author bio：
  
  [ "HUANG Lan, E-mail: huanglan@jlu.edu.cn" ]
  [ "WANG Gui-chao, E-mail: wgc290029@163.com" ]
  Zhe WANG, wz2000@jlu.edu.cn
- Funds：
  
  Project supported by the National Natural Science Foundation of China (Nos. 61472159 and 61373051)
- DOI：10.1631/FITEE.1601364
  中图分类号： TP181
- 收稿：2016-06-22，
  
  修回：2017-11-;6，
  
  纸质出版：2017-10
- Accepted：
Scan QR Code
黄岚, 王贵超, 白天, 等. 一种改进的果蝇优化算法及其在旅行商问题求解中的应用[J]. 信息与电子工程前沿（英文）, 2017,18(10):1525-1533.

Lan HUANG, Gui-chao WANG, Tian BAI, et al. An improved fruit fly optimization algorithm for solving traveling salesman problem[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(10): 1525-1533.
黄岚, 王贵超, 白天, 等. 一种改进的果蝇优化算法及其在旅行商问题求解中的应用[J]. 信息与电子工程前沿（英文）, 2017,18(10):1525-1533. DOI： 10.1631/FITEE.1601364.

Lan HUANG, Gui-chao WANG, Tian BAI, et al. An improved fruit fly optimization algorithm for solving traveling salesman problem[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(10): 1525-1533. DOI： 10.1631/FITEE.1601364.

摘要

旅行商问题（traveling salesman problem

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

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.

关键词

Keywords

references

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

M. Clerc . . 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 , , 2004 . . 219 - - 239 . . DOI: 10.1007/978-3-540-39930-8_8 http://doi.org/10.1007/978-3-540-39930-8_8 . .

G.A. Croes . . A method for solving traveling-salesman problems . . Oper. Res. , , 1958 . . 6 ( ( 6 ): ): 791 - - 812 . . DOI: 10.1287/opre.6.6.791 http://doi.org/10.1287/opre.6.6.791 . .

C. Ding , , , Y. Cheng , , , M. He . . Two-level genetic algorithm for clustered traveling salesman problem with application in large-scale TSPs . . Tsinghua Sci. Technol. , , 2007 . . 12 ( ( 4 ): ): 459 - - 465 . . DOI: 10.1016/S1007-0214(07)70068-8 http://doi.org/10.1016/S1007-0214(07)70068-8 . .

G.F. Dong , , , W.W. Guo , , , K. Tickle . . Solving the traveling salesman problem using cooperative genetic ant systems . . Exp. Syst. Appl. , , 2012 . . 39 ( ( 5 ): ): 5006 - - 5011 . . DOI: 10.1016/j.eswa.2011.10.012 http://doi.org/10.1016/j.eswa.2011.10.012 . .

M. Dorigo , , , L.M. Gambardella . . Ant colonies for the travelling salesman problem . . BioSystems , , 1997 . . 43 ( ( 2 ): ): 73 - - 81 . . DOI: 10.1016/S0303-2647(97)01708-5 http://doi.org/10.1016/S0303-2647(97)01708-5 . .

J.B. Escario , , , J.F. Jimenez , , , J.M. Giron-Sierra . . Ant colony extended: experiments on the travelling salesman problem . . Exp. Syst. Appl. , , 2015 . . 42 ( ( 1 ): ): 390 - - 410 . . DOI: 10.1016/j.eswa.2014.07.054 http://doi.org/10.1016/j.eswa.2014.07.054 . .

X.T. Geng , , , Z.H. Chen , , , W. Yang , , , 等 . . Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search . . Appl. Soft Comput. , , 2011 . . 11 ( ( 4 ): ): 3680 - - 3689 . . DOI: 10.1016/j.asoc.2011.01.039 http://doi.org/10.1016/j.asoc.2011.01.039 . .

J.J. Grefenstette , , , R. Gopal , , , B.J. Rosmaita , , , 等 . . Genetic algorithms for the traveling salesman problem . . 1st Int. Conf. on Genetic Algorithms and Their Applications , , 1985 . . 160 - - 168 . . . .

M. Gündüz , , , M.S. Kiran , , , E. zceylan . . A hierarchic approach based on swarm intelligence to solve the traveling salesman problem . . Turk. J. Electric. Eng. Comput. Sci. , , 2015 . . 23 ( ( 1 ): ): 103 - - 117 . . DOI: 10.3906/elk-1210-147 http://doi.org/10.3906/elk-1210-147 . .

T. Hendtlass . . Preserving diversity in particle swarm optimisation . . In : Chung P.W.H., Hinde C., Ali, M. (Eds.), Developments in Applied Artificial Intelligence. Springer Berlin Heidelberg , , 2003 . . 31 - - 40 . . DOI: 10.1007/3-540-45034-3_4 http://doi.org/10.1007/3-540-45034-3_4 . .

M. Hoffmann , , , M. Mühlenthaler , , , S. Helwig , , , 等 . . Discrete particle swarm optimization for TSP: theoretical results and experimental evaluations . . In : Bouchachia, A. (Ed.), Adaptive and Intelligent Systems. Springer Berlin Heidelberg , , 2011 . . 416 - - 427 . . DOI: 10.1007/978-3-642-23857-4_40 http://doi.org/10.1007/978-3-642-23857-4_40 . .

F. Jolai , , , A. Ghanbari . . Integrating data transformation techniques with Hopfield neural networks for solving travelling salesman problem . . Exp. Syst. Appl. , , 2010 . . 37 ( ( 7 ): ): 5331 - - 5335 . . DOI: 10.1016/j.eswa.2010.01.002 http://doi.org/10.1016/j.eswa.2010.01.002 . .

D. Karaboga , , , B. Gorkemli . . A combinatorial artificial bee colony algorithm for traveling salesman problem . . IEEE Int. Symp. on Innovations in Intelligent Systems and Applications , , 2011 . . 50 - - 53 . . DOI: 10.1109/INISTA.2011.5946125 http://doi.org/10.1109/INISTA.2011.5946125 . .

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

E.L. Lawler , , , D.E. Wood . . Branch-and-bound methods: a survey . . Oper. Res. , , 1966 . . 14 ( ( 4 ): ): 699 - - 719 . . DOI: 10.1287/opre.14.4.699 http://doi.org/10.1287/opre.14.4.699 . .

J.D.C. Little , , , K.G. Murty , , , D.W. Sweeney , , , 等 . . An algorithm for the traveling salesman problem . . Oper. Res. , , 1963 . . 11 ( ( 6 ): ): 972 - - 989 . . DOI: 10.1287/opre.11.6.972 http://doi.org/10.1287/opre.11.6.972 . .

F. Liu , , , G.Z. Zeng . . Study of genetic algorithm with reinforcement learning to solve the TSP . . Exp. Syst. Appl. , , 2009 . . 36 ( ( 3 ): ): 6995 - - 7001 . . DOI: 10.1016/j.eswa.2008.08.026 http://doi.org/10.1016/j.eswa.2008.08.026 . .

M. Mahi , , , .K. Baykan , , , H. Kodaz . . A new hybrid method based on particle swarm optimization, ant colony optimization and 3-opt algorithms for traveling salesman problem . . Appl. Soft Comput. , , 2015 . . 30 484 - - 490 . . DOI: 10.1016/j.asoc.2015.01.068 http://doi.org/10.1016/j.asoc.2015.01.068 . .

T.A.S. Masutti , , , L.N. de Castro . . A self-organizing neural network using ideas from the immune system to solve the traveling salesman problem . . Inform. Sci. , , 2009 . . 179 ( ( 10 ): ): 1454 - - 1468 . . DOI: 10.1016/j.ins.2008.12.016 http://doi.org/10.1016/j.ins.2008.12.016 . .

X.X. Ouyang , , , Y.G. Zhou , , , Q.F. Luo , , , 等 . . A novel discrete cuckoo search algorithm for spherical traveling salesman problem . . Appl. Math. Inform. Sci. , , 2013 . . 7 ( ( 2 ): ): 777 - - 784 . . DOI: 10.12785/amis/070248 http://doi.org/10.12785/amis/070248 . .

W.T. Pan . . Fruit Fly Optimization Algorithm . . Tsang Hai Book Publishing Co., Taipei, China , , 2011 . . 221 - - 232 . . . .

W.T. Pan . . A new fruit fly optimization algorithm: taking the financial distress model as an example . . Knowl.-Based Syst. , , 2012 . . 26 69 - - 74 . . DOI: 10.1016/j.knosys.2011.07.001 http://doi.org/10.1016/j.knosys.2011.07.001 . .

R. Pasti , , , L.N. de Castro . . A neuro-immune network for solving the traveling salesman problem . . IEEE Int. Joint Conf. on Neural Network , , 2006 . . 3760 - - 3766 . . DOI: 10.1109/IJCNN.2006.247394 http://doi.org/10.1109/IJCNN.2006.247394 . .

M. Peker , , , B. Şen , , , P.Y. Kumru . . 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. , , 2013 . . 21 ( ( 55 ): ): 2015 - - 2036 . . DOI: 10.3906/elk-1109-44 http://doi.org/10.3906/elk-1109-44 . .

J.Q. Wu , , , A.J. Ouyang . . A hybrid algorithm of ACO and delete-cross method for TSP . . IEEE Int. Conf. on Industrial Control and Electronics Engineering , , 2012 . . 1694 - - 1696 . . DOI: 10.1109/ICICEE.2012.448 http://doi.org/10.1109/ICICEE.2012.448 . .

Y.Q. Zhou , , , Q.F. Luo , , , H. Chen , , , 等 . . A discrete invasive weed optimization algorithm for solving traveling salesman problem . . Neurocomputing , , 2015 . . 151 1227 - - 1236 . . DOI: 10.1016/j.neucom.2014.01.078 http://doi.org/10.1016/j.neucom.2014.01.078 . .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

暂无数据