Hybrid immune algorithm based on greedy algorithm and delete-cross operator for solving TSP

详细信息    查看全文

• 作者：Guo Pan ; Kenli Li ; Aijia Ouyang ; Keqin Li
• 关键词：Delete ; cross operator ; Dynamic mutation ; Greedy algorithm ; Immune algorithm ; TSP
• 刊名：Soft Computing - A Fusion of Foundations, Methodologies and Applications
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：20
• 期：2
• 页码：555-566
• 全文大小：766 KB
• 参考文献：Albayrak M, Allahverdi N (2011) Development a new mutation operator to solve the traveling salesman problem by aid of genetic algorithms. Expert Syst Appl 38(3):1313–1320CrossRef
  Alkaya AF, Duman E (2013) Application of sequence-dependent traveling salesman problem in printed circuit board assembly. IEEE Trans Compon Packag Manuf Technol 3(6):1063–1076
  An HC, Kleinberg R, Shmoys DB (2012) Improving christofides’ algorithm for the st path TSP. In: Proceedings of the 44th symposium on theory of computing, pp 875–886
  Badillo AR, Ruiz JJ, Cotta C, Fernández-Leiva AJ (2013) On user-centric memetic algorithms. Soft Comput 17(2):285–300CrossRef
  Beheshti Z, Shamsuddin SM, Yuhaniz SS (2013) Binary Accelerated Particle Swarm Algorithm (BAPSA) for discrete optimization problems. J Global Optim 57(2):549–573MATH MathSciNet CrossRef
  Carrabs F, Cerulli R, Speranza MG (2013) A branch-and-bound algorithm for the double travelling salesman problem with two stacks. Networks 61(1):58–75MATH MathSciNet CrossRef
  Cecilia JM, García JM, Nisbet A, Amos M, Ujaldón M (2013) Enhancing data parallelism for ant colony optimization on gpus. J Parallel Distrib Comput 73(1):42–51CrossRef
  Chen J, Ding Y, Jin Y, Hao K (2013) A synergetic immune clonal selection algorithm based multi-objective optimization method for carbon fiber drawing process. Fibers Polym 14(10):1722–1730CrossRef
  Cheong T, White CC (2012) Dynamic traveling salesman problem: value of real-time traffic information. IEEE Trans Intell Transp Syst 13(2):619–630CrossRef
  Chun JS (1997) Shape optimization of electro-magnetic devices using immune algorithm. IEEE Trans Magn 33:1876–1879CrossRef
  Clarke G, Wright JW (1964) Scheduling of vehicles from a central depot to a number of delivery points. Oper Res 12(4):568–581CrossRef
  Dasgupta D, Forrest S (1999) Artificial immune systems in industrial applications. In: Proceedings of the 2nd international conference on intelligent processing and manufacturing of materials. IEEE Press, Hawaii, pp 257–267
  De Castro LN, Von Zuben FJ (2002) Learning and optimization using the clonal selection principle. IEEE Trans Evol Comput 6(3):239–251CrossRef
  Deng W, Chen R, He B, Liu Y, Yin L, Guo J (2012) A novel two-stage hybrid swarm intelligence optimization algorithm and application. Soft Comput 16(10):1707–1722CrossRef
  Ding Y, Wang Z, Ye H (2012) Optimal control of a fractional-order HIV-immune system with memory. IEEE Trans Control Syst Technol 20(3):763–769CrossRef
  Gan R, Guo Q, Chang H, Yi Y (2010) Improved ant colony optimization algorithm for the traveling salesman problems. J Syst Eng Electron 21(2):329–333CrossRef
  Guo T, Michalewicz Z (1998) Inver-over operator for the TSP. In: Proceedings of the 5th parallel problem solving from nature. Lecture notes in computer science. Springer, Amsterdam, pp 803–812
  Hassin R, Keinan A (2008) Greedy heuristics with regret, with application to the cheapest insertion algorithm for the TSP. Oper Res Lett 36(2):243–246MATH MathSciNet CrossRef
  Hunt JE, Cooke DE (1995) An adaptive, distributed learning system based on immune system. In: IEEE international conference on system, man and cybernetics. IEEE Press, Vancouver, pp 2494–2499
  Hurkens CA, Woeginger GJ (2004) On the nearest neighbor rule for the traveling salesman problem. Oper Res Lett 32(1):1–4MATH MathSciNet CrossRef
  IEEE801.11 Working Group (2013). http://​grouper.​ieee.​org/​groups/​802/​1/​index.​html
  Kalender M, Kheiri A, Özcan E, Burke EK (2013) A greedy gradient-simulated annealing selection hyper-heuristic. Soft Comput 17(12):2279–2292CrossRef
  Karapetyan D, Gutin G (2011) Lin–Kernighan heuristic adaptations for the generalized traveling salesman problem. Eur J Oper Res 208(3):221–232MATH MathSciNet CrossRef
  Kıran MS, ¡şcan H, Gündüz M (2013) The analysis of discrete artificial bee colony algorithm with neighborhood operator on traveling salesman problem. Neural Comput Appl 23(1):9–21
  Larranaga P, Kuijpers CMH, Murga RH, Inza I, Dizdarevic S (1999) Genetic algorithms for the traveling salesman problem: a review of representations and operators. Artif Intell Rev 13:129–170
  Le Ny J, Feron E, Frazzoli E (2012) On the Dubins traveling salesman problem. IEEE Trans Autom Control 57(1):265–270CrossRef
  Marinakis Y, Marinaki M, Dounias G (2011) Honey bees mating optimization algorithm for the Euclidean traveling salesman problem. Inf Sci 181(20):4684–4698MathSciNet CrossRef
  Mavrovouniotis M, Yang S (2013) Ant colony optimization with immigrants schemes for the dynamic travelling salesman problem with traffic factors. Appl Soft Comput 13(10):4023–4037CrossRef
  Michalewicz Z (2000) How to Solve It: Modern Heuristick. Springer, BerlinCrossRef
  Montiel O, Diaz-Delgadillo FJ, Seplveda R (2013) Combinatorial complexity problem reduction by the use of artificial vaccines. Expert Syst Appl 40(5):1871–1879CrossRef
  Mora AM, García-Sánchez P, Merelo JJ, Castillo PA (2013) Pareto-based multi-colony multi-objective ant colony optimization algorithms: an island model proposal. Soft Comput 17(7):1175–1207CrossRef
  Nagata Y, Soler D (2012) A new genetic algorithm for the asymmetric traveling salesman problem. Expert Syst Appl 39(10):8947–8953CrossRef
  Ouaarab A, Ahiod B, Yang XS (2013) Discrete cuckoo search algorithm for the travelling salesman problem. Neural Comput Appl. doi:10.​1007/​s00521-013-1402-2
  Pedro O, Saldanha R, Camargo R (2013) A tabu search approach for the prize collecting traveling salesman problem. Electron Notes Discret Math 41:261–268CrossRef
  Shi XH, Liang YC, Lee HP, Lu C, Wang QX (2007) Particle swarm optimization-based algorithms for TSP and generalized TSP. Inf Process Lett 103(5):169–176MATH MathSciNet CrossRef
  Shim VA, Tan KC, Cheong CY (2012) A hybrid estimation of distribution algorithm with decomposition for solving the multiobjective multiple traveling salesman problem. IEEE Trans Syst Man Cybern Part C Appl Rev 42(5):682–691CrossRef
  Wang Y, Li J, Gao K, Pan Q (2011) Memetic algorithm based on improved inver-over operator and Lin–Kernighan local search for the Euclidean traveling salesman problem. Comput Math Appl 62(7):2743–2754MATH MathSciNet CrossRef
  Xie X-F, Liu J (2009) Multiagent optimization system for solving the traveling salesman problem (TSP). IEEE Trans Syst Man Cybern Part B Cybern 39(2):489–502CrossRef
  Xu Y, Li K, Hu J, Li K (2014) A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues. Inf Sci 270:255–287
  Yang G, Yi J (2013) Dynamic characteristic of a multiple chaotic neural network and its application. Soft Comput 17(5):783–792CrossRef
  Yuan S, Skinner B, Huang S, Liu D (2013) A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms. Eur J Oper Res 228(1):72–82MathSciNet CrossRef
  Zhang Z, Qian S (2011) Artificial immune system in dynamic environments solving time-varying non-linear constrained multi-objective problems. Soft Comput 15(7):1333–1349CrossRef
  Zhang Z, Yue S, Liao M, Long F (2014) Danger theory based artificial immune system solving dynamic constrained single-objective optimization. Soft Comput 18(1):1–22MATH CrossRef
  
• 作者单位：Guo Pan (1)
  Kenli Li (1)
  Aijia Ouyang (1)
  Keqin Li (1) (2)
  
  1. College of Computer Science and Electronic Engineering, Hunan University, Changsha, 410082, Hunan, China
  2. Department of Computer Science, State University of New York, New Paltz, NY, 12561, USA
  
• 刊物类别：Engineering
• 刊物主题：Numerical and Computational Methods in Engineering
  Theory of Computation
  Computing Methodologies
  Mathematical Logic and Foundations
  Control Engineering
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1433-7479

文摘

This paper first introduces the fundamental principles of immune algorithm (IA), greedy algorithm (GA) and delete-cross operator (DO). Based on these basic algorithms, a hybrid immune algorithm (HIA) is constructed to solve the traveling salesman problem (TSP). HIA employs GA to initialize the routes of TSP and utilizes DO to delete routes of crossover. With dynamic mutation operator (DMO) adopted to improve searching precision, this proposed algorithm can increase the likelihood of global optimum after the hybridization. Experimental results demonstrate that the HIA algorithm is able to yield a better solution than that of other algorithms, which also takes less computation time.