A Discrete Flower Pollination Algorithm for Travelling Salesman Problem

doi:10.3969/j.issn.1006-2475.2016.07.008

Abstract

Abstract: In view of the standard Flower Pollination Algorithm(FPA) can not be used to solve combinatorial optimization problem, a Discrete Flower Pollination Algorithm(DFPA) was proposed and then applied to Traveling Salesman Problem(TSP). By redefining the concept of flowers, global search and local search, etc.， and Levy flight will be segmented by a new method, effectively avoiding premature falling into local optimum and enhancing the global search ability of the algorithm. Finally the performance of the proposed is tested against by some typical instances in the internationally commonly used library of TSP(TSPLIB) and compared with Discrete Particle Swarm Optimization（DPSO）， Hybrid Discrete Particle Swarm Optimization(HDPSO)， Discrete Cuckoo Search(DCS)， Genetic Simulated Annealing Ant Colony System with Particle Swarm Optimisation Technique（GSA-ACS-PSOT）. The results of the tests show that DFPA can quickly, accurately find the optimal solution. Under the same experimental conditions, the algorithm reduces the error rate than any other algorithm. The results show that the proposed algorithm has better solving performance.

Key words: , Flower Pollination Algorithm(FPA)； Discrete Flower Pollination Algorithm（DFPA)； Travelling Salesman Problem(TSP)； Levy flight； TSPLIB； percentage deviation

LI Qian1, HE Xing-shi1, YANG Xin-she1,2. A Discrete Flower Pollination Algorithm for Travelling Salesman Problem[J]. Computer and Modernization, 2016, 251(07): 37-43.

References

［1］   Blum C, Roli A. Metaheuristics in combinatorial optimization: Overview and conceptual comparison［J］. ACM Compute Surveys(CSUR), 2003,35(3):268-308.
［2］ Lawler E L, Lenstra J K, Rinnooy Kan A H G, et al. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization［M］. John Wiley & Sons, Incorporated, 1985.
［3］ Papadimitriou C H. Euclidean TSP is NP-complete［J］. Theoretical Computer Science, 1997,4:237-244.
［4］   Zachariasen M, Dam M. Tabu Search on the Geometric Traveling Salesman Problem［M］. Meta-Heuristics, Springer, 1996:571-587.
［5］ Potvin J Y. Genetic algorithms for the traveling salesman problem［J］. Annals of Operations Research, 1996,63(3):337-370. 
［6］ Qu Liangsheng, Sun Ruixiang. A synergetic approach to genetic algorithms for solving traveling salesman problem［J］. Information Sciences, 1999,117(3):267-283.
［7］   Marinakis Y, Migdalas A, Pardalos P M. Expanding neighborhood GRASP for the traveling salesman problem［J］. Computational Optimization and Applications, 2005,32(3):231-257.
［8］ Chen Yong, Zhang Pan. Optimized annealing of traveling salesman problem from the-nearest-neighbor distribution［J］. Physica A: Statistical Mechanics and its Applications, 2006,371(2):627-632.
［9］ Dorigo M, Gambardella L M. Ant colonies for the travelling salesman problem［J］. Biosystems, 1997,43(2):73-81. 
［10］Dorigo M, Gambardella L M. Ant colony system: A cooperative learning approach to the traveling salesman problem［J］. IEEE Transactions on Evolutionary Computation, 1997,1(1):53-66.
［11］Li Xiangyong, Tian Peng, Hua Jing, et al. A hybrid discrete particle swarm optimization for the traveling salesman problem［J］. Lecture Notes in Computer Science, 2006,4247:181-188.
［12］ Goldbarg Elizabeth F G, Goldbarg Marco C, Souza Givanaldo R de. Particle swarm optimization algorithm for the traveling salesman problem［M］// Traveling Salesman Problem. 2008:75-96.
［13］Jati Gilang Kusuma, Suyanto. Evolutionary discrete firefly algorithm for travelling salesman problem［J］. Adaptive and Intelligent Systems, 2011,6943:393-403.
［14］Ouaarab A, Ahiod B, Yang Xin-she. Discrete cuckoo search algorithm for the travelling salesman problem［J］. Neural Computing and Applications, 2014,24(7):1659-1669.
［15］Yang Xin-she. Flower pollination algorithm for global optimization［C］// Proceedings of the 11th International Conference on Unconventional Computation and Natural Computation. 2012,7445:240-249.
［16］Lenstra J K, Rinnooy Kan A H G. Some simple applications of the travelling salesman problem［J］. Operational Research Quarterly, 1975,26(4):717-733.
［17］Reinelt G. The Traveling Salesman: Computational Solutions for TSP Applications［M］. Springer-Verlag, 1994.
［18］Davendra D. Traveling Salesman Problem, Theory and Applications［M］. InTech Publisher, Rijeka, Croatia, 2010.
［19］Pavlyukevich I. Lévy flights, non-local search and simulated annealing ［J］. Journal of Computational Physics, 2007,226(2):1830-1844.
［20］Yang Xin-she, Deb S. Cuckoo search via Levy flights［C］// Proc. of World Congress on Nature & Biologically Inspired Computing(NaBIC 2009). 2009:210-214.
［21］Reinelt G. TSPLIB: A traveling salesman problem library［J］. ORSA Journal on Computing, 1991,3(4):376-384.
［22］Kirils Bibiks, Li Jian-ping, Hu Fun. Discrete flower pollination algorithm for resource constrained project scheduling problem［J］. IJCSIS International Journal of Computer Science and Information Security, 2015,13(7):8-19.
［23］Shi Xiaohu， Liang Y C， Lee H P， et al. Particle swarm optimization based algorithms for TSP and generalized TSP［J］. Information Processing Letters, 2007,103(5):169-176.
［24］Li Xiangyong, Tian Peng, Hua Jing, et al. A hybrid discrete particle swarm optimization for the traveling salesman problem［J］. Lecture Notes in Computer Science, 2006,4247:181-188.
［25］Chen Shyi-ming, Chien Chih-yao Y. Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization technique［J］. Expert Systems with Applications, 2011,38(12):14439-14450.

[1]	HE Sida, CHEN Pinghua. Intent-based Lightweight Self-Attention Network for Sequential Recommendation [J]. Computer and Modernization, 2024, 0(12): 1-9.
[2]	ZHENG Jiuchao, ZHAO Xinyuan. Entity Linking Method Based on Topics and Description Information [J]. Computer and Modernization, 2024, 0(12): 10-14.
[3]	ZHAO Chenyang, XUE Tao, LIU Junhua. Fashion Clothing Pattern Generation Based on Improved Stable Diffusion [J]. Computer and Modernization, 2024, 0(12): 15-23.
[4]	WANG Xiaohang1, LI Yongjie1, YU Lei1, FAN Xiao2. A Method of Using Compound Event Probability Operation to Solve Problem of Negative Information Blocking Maximization [J]. Computer and Modernization, 2024, 0(12): 24-33.
[5]	ZHANG Xiaodong1, BAI Guangzhi1, LI Min1, LI Haoyang2. Oil and Gas Well Production Prediction Model Based on Empirical Wavelet Transform [J]. Computer and Modernization, 2024, 0(12): 53-58.
[6]	LIU Yunhai1, Feng Guang1, WU Xiaoting2, YANG Qun2 . Safety Helmet Wearing Detection Algorithm for Complex Construction Scenes [J]. Computer and Modernization, 2024, 0(12): 66-71.
[7]	LIU Baobao, YANG Jingjing, TAO Lu, WANG Heying . DSMSC Based on Attention Mechanism for Remote Sensing Image Scene Classification [J]. Computer and Modernization, 2024, 0(12): 72-77.
[8]	GU Yue, DENG Songfeng, SHEN Ji, MU Wentao, ZHAO Enqi. SAR Ship Detection Algorithm Based on Improved YOLOv8 [J]. Computer and Modernization, 2024, 0(12): 78-83.
[9]	WU Xiuling1, ZHOU Sheng1, WANG Chunjuan1, YU Cuizhuo2, LIU Hao3. Research Progress in Ultra Short-term Power Load Forecasting Technology [J]. Computer and Modernization, 2024, 0(12): 108-115.
[10]	LI Deyou1, 2, YU Jinsongdi1, 2, WEI Dandan1, 2, LUO Yuan1, 2, TONG Ruiju3. Abstract Tree Model for Gridded Cube Metadata [J]. Computer and Modernization, 2024, 0(11): 1-6.
[11]	GONG Yicheng1, 2, LIU Qing1, 2. Beijing Opera Binary Classification Based on RF-LCE-BiLSTM-Attention-AMSSA Model [J]. Computer and Modernization, 2024, 0(11): 7-12.
[12]	LI Taoying, LI Meng, WU Mengqiao. Taxi Passenger Flow Prediction Based on Heterogeneous Spatiotemporal Graph#br# Convolutional Networks [J]. Computer and Modernization, 2024, 0(11): 13-18.
[13]	ZHANG Tai1, YAN Zihao2, DUAN Jie2, ZHANG Zhihong2. Information Forwarding Strategy of Internet of Vehicles in Named Data Network [J]. Computer and Modernization, 2024, 0(11): 19-27.
[14]	YUAN Qingle, MU Li. Inventory Forecasting Method Based on Improved Elman Neural Network [J]. Computer and Modernization, 2024, 0(11): 28-33.
[15]	DONG Chongchong, ZHAO Cong, WU You, ZHANG Lei, ZHANG Jiawen, LI Zhihao. Zero-trust Dynamic Evaluation Method for IoT Terminals [J]. Computer and Modernization, 2024, 0(11): 41-45.