In the Salp Swarm Algorithm (SSA), the update mechanism is inspired by the unique chain movement of the salp swarm. Numerous versions of SSA were already put forward to deal with various optimization problems, but there are very few discrete versions among them. d-opt is improved based on the 2-opt algorithm: a decreasing factor d is introduced to control the range of neighborhood search; TPALS are modified by Problem Aware Local Search (PALS) based on the characteristics of Travelling Salesman Problem (TSP); The second leader mechanism increases the randomness of the algorithm and avoids falling into the local optimal solution to a certain extent. We also select six classical crossover operators to experiment and select Subtour Exchange Crossover (SEC) and the above three mechanisms to integrate them into the SSA algorithm framework to form Discrete Salp Swarm Algorithm (DSSA). In addition, DSSA was tested on 23 known TSP instances to verify its performance. Comparative simulation studies with other advanced algorithms are conducted and from the results, it is observed that DSSA satisfactorily solves TSP.
Citation: Peng Chen, Ming Liu, Shihua Zhou. Discrete Salp Swarm Algorithm for symmetric traveling salesman problem[J]. Mathematical Biosciences and Engineering, 2023, 20(5): 8856-8874. doi: 10.3934/mbe.2023389
In the Salp Swarm Algorithm (SSA), the update mechanism is inspired by the unique chain movement of the salp swarm. Numerous versions of SSA were already put forward to deal with various optimization problems, but there are very few discrete versions among them. d-opt is improved based on the 2-opt algorithm: a decreasing factor d is introduced to control the range of neighborhood search; TPALS are modified by Problem Aware Local Search (PALS) based on the characteristics of Travelling Salesman Problem (TSP); The second leader mechanism increases the randomness of the algorithm and avoids falling into the local optimal solution to a certain extent. We also select six classical crossover operators to experiment and select Subtour Exchange Crossover (SEC) and the above three mechanisms to integrate them into the SSA algorithm framework to form Discrete Salp Swarm Algorithm (DSSA). In addition, DSSA was tested on 23 known TSP instances to verify its performance. Comparative simulation studies with other advanced algorithms are conducted and from the results, it is observed that DSSA satisfactorily solves TSP.
| [1] |
R. Sheikhpour, M. A. Sarram, R. Sheikhpour, Particle swarm optimization for bandwidth determination and feature selection of kernel density estimation based classifiers in diagnosis of breast cancer, Appl. Soft Comput., 40 (2016), 113–131. https://doi.org/10.1016/j.eswa.2007.08.088 doi: 10.1016/j.eswa.2007.08.088
|
| [2] | X. M. Zhang, Y. Q. Zhou, H. J. Huang, Q. F. Luo, Enhanced Salp Search Algorithm for Optimization Extreme Learning Machine and Application to Dew Point Temperature Prediction, Int. J. Comput. Intell. Syst., 98 (2022). https://doi.org/10.1007/s44196-022-00160-y |
| [3] |
M. Rostami, K. Berahmand, E. Nasiri, S. Forouzandeh, Review of swarm intelligence-based feature selection methods, Eng. Appl. Artif. Intell., 100 (2021), 104210. https://doi.org/10.1016/j.engappai.2021.104210 doi: 10.1016/j.engappai.2021.104210
|
| [4] |
G. H. Al-Gaphari, R. Al-Amry, A. S. Al-Nuzaili, Discrete crow-inspired algorithms for traveling salesman problem, Eng. Appl. Artif. Intell., 97 (2021), 104006. https://doi.org/10.1016/j.engappai.2020.104006 doi: 10.1016/j.engappai.2020.104006
|
| [5] |
T. Dokeroglu, E. Sevinc, Memetic teaching–learning-based optimization algorithms for large graph coloring problems, Eng. Appl. Artif. Intell., 102 (2021), 104282. https://doi.org/10.1016/j.engappai.2021.104282 doi: 10.1016/j.engappai.2021.104282
|
| [6] |
K. Panwar, K. Deep, Discrete Grey Wolf Optimizer for symmetric travelling salesman problem, Appl. Soft Comput., 105 (2021), 107298. https://doi.org/10.1016/j.asoc.2021.107298 doi: 10.1016/j.asoc.2021.107298
|
| [7] |
S. J. Wang, S. H. Zhou, W. Q. Yan, An enhanced whale optimization algorithm for DNA storage encoding, Math. Biosci. Eng., 19 (2022), 14142–14172. https://doi.org/10.3934/mbe.2022659 doi: 10.3934/mbe.2022659
|
| [8] |
R. M. Karp, On the computational complexity of combinatorial problems, Networks, 5 (1975), 45–68. https://doi.org/10.1002/net.1975.5.1.45 doi: 10.1002/net.1975.5.1.45
|
| [9] |
E. Taillard, A linearithmic heuristic for the travelling salesman problem, European J. Operat. Res., 297 (2022), 442–450. https://doi.org/10.1016/j.ejor.2021.05.034 doi: 10.1016/j.ejor.2021.05.034
|
| [10] |
Uzma, Z. Halim, Optimizing the dna fragment assembly using metaheuristic-based overlap layout consensus approach, App. Soft Comput., 92 (2020), 106256. https://doi.org/10.1016/j.asoc.2020.106256 doi: 10.1016/j.asoc.2020.106256
|
| [11] |
M. Li, D. Lei, An imperialist competitive algorithm with feedback for energy-efficient flexible job shop scheduling with transportation and sequence-dependent setup times, Eng. Appl. Artif. Intell., 103 (2021), 104307. https://doi.org/10.1016/j.engappai.2021.104307 doi: 10.1016/j.engappai.2021.104307
|
| [12] |
J. P. Huang, Q. K. Pan, Z. H. Miao, L. Gao, Effective constructive heuristics and discrete bee colony optimization for distributed flowshop with setup times, Eng. Appl. Artif. Intell., 97 (2021), 104016. https://doi.org/10.1016/j.engappai.2020.104016 doi: 10.1016/j.engappai.2020.104016
|
| [13] |
D. Lei, Z. Cui, M. Li, A dynamical artificial bee colony for vehicle routing problem with drones, Eng. Appl. Artif. Intell., 107 (2022), 104510. https://doi.org/10.1016/j.engappai.2021.104510 doi: 10.1016/j.engappai.2021.104510
|
| [14] |
R. Radharamanan, L. I. Choi, A branch and bound algorithm for the travelling salesman and the transportation routing problems, Comput. Industr. Eng., 11 (1986), 236–240. https://doi.org/10.1016/0360-8352(86)90085-9 doi: 10.1016/0360-8352(86)90085-9
|
| [15] |
Ö. Ergun, J. B. Orlin, A dynamic programming methodology in very large scale neighborhood search applied to the traveling salesman problem, Discrete Optim., 3 (2006), 78–85. https://doi.org/10.1016/j.disopt.2005.10.002 doi: 10.1016/j.disopt.2005.10.002
|
| [16] |
G. Laporte, The traveling salesman problem: An overview of exact and approximate algorithms, European J. Operat. Res., 59 (1992), 231–247. https://doi.org/10.1016/0377-2217(92)90138-Y doi: 10.1016/0377-2217(92)90138-Y
|
| [17] |
X. J. Zhou, D. Y. Gao, C. H. Yang, W. H. Gui, Discrete state transition algorithm for unconstrained integer optimization problems, Neurocomputing, 173(2016), 864–874. https://doi.org/10.1016/j.neucom.2015.08.041 doi: 10.1016/j.neucom.2015.08.041
|
| [18] |
M. Gunduz, M. Aslan, Djaya: A discrete jaya algorithm for solving traveling salesman problem, Appl. Soft Comput., 105 (2021), 107275. https://doi.org/10.1016/j.asoc.2021.107275 doi: 10.1016/j.asoc.2021.107275
|
| [19] |
Y. Huang, X. N. Shen, X. You, A discrete shuffled frog-leaping algorithm based on heuristic information for traveling salesman problem, Appl. Soft Comput., 102 (2021), 107085. https://doi.org/10.1016/j.asoc.2021.107085 doi: 10.1016/j.asoc.2021.107085
|
| [20] |
M. A. H. Akhand, S. I. Ayon, S. A. Shahriyar, N. Siddique, H. Adeli, Discrete spider monkey optimization for travelling salesman problem, Appl. Soft Comput., 86 (2020), 105887. https://doi.org/10.1016/j.asoc.2019.105887 doi: 10.1016/j.asoc.2019.105887
|
| [21] |
A. C. Cinar, S. Korkmaz, M. S. Kiran, A discrete tree-seed algorithm for solving symmetric traveling salesman problem, Eng. Sci. Technol. Int. J., 23 (2020), 879–890. https://doi.org/10.1016/j.jestch.2019.11.005 doi: 10.1016/j.jestch.2019.11.005
|
| [22] |
Y. Q. Zhou, Q. F. Luo, H. Chen, A. P. He, J. Z. Wu, A discrete invasive weed optimization algorithm for solving traveling salesman problem, Neurocomputing, 151 (2015), 1227–1236. https://doi.org/10.1016/j.neucom.2014.01.078 doi: 10.1016/j.neucom.2014.01.078
|
| [23] |
Y. Q. Zhou, R. Wang, C. Y. Zhao, Q. F. Luo, M. A. Metwally, Discrete greedy flower pollination algorithm for spherical traveling salesman problem, Neural Comput. Appl., 31(2019), 2155–2170. https://doi.org/10.1007/s00521-017-3176-4 doi: 10.1007/s00521-017-3176-4
|
| [24] |
S. Mirjalili, A. H. Gandomi, S. Z. Mirjalili, S. Saremi, H. Faris, S. M. Mirjalili, Salp swarm algorithm: A bio-inspired optimizer for engineering design problems, Adv. Eng. Software, 114 (2017), 163–191. https://doi.org/10.1016/j.advengsoft.2017.07.002 doi: 10.1016/j.advengsoft.2017.07.002
|
| [25] | G. A. Croes, A method for solving traveling-salesman problems, Oper. Res., 6 (1958), 791–812. Available from: https://www.jstor.org/stable/167074 |
| [26] | E. Alba, G. Luque, A new local search algorithm for the DNA fragment assembly problem, in European Conference on Evolutionary Computation in Combinatorial Optimization, 4446 (2007), 1–12. https://doi.org/10.1007/978-3-540-71615-0_1 |
| [27] | D. E. Goldberg, R. Lingle, Alleles, loci, and the traveling salesman problem, in Proceedings of an international conference on genetic algorithms and their applications, 1 (1985), 154–159. |
| [28] | L. Davis, Applying adaptive algorithms to epistatic domains, in International Joint Conference on Artificial Intelligence, 1 (1985), 162–164. |
| [29] | G. Syswerda, Scheduling optimization using genetic algorithms, Handbook of genetic algorithms, 1 (1991). |
| [30] |
M. Yamamura, Character-preserving genetic algorithms for traveling salesman problem, J. Japanese Soc. Artif. Intell., 7 (1992), 1049–1049. https://doi.org/10.1007/BF02125403 doi: 10.1007/BF02125403
|
| [31] |
E. Osaba, Y. XinShe, F. Diaz, P. L. Garcia, R. Carballedo, An improved discrete bat algorithm for symmetric and asymmetric traveling salesman problems, Eng. Appl. Artif. Intell., 48 (2016), 59–71. https://doi.org/10.1016/j.engappai.2015.10.006 doi: 10.1016/j.engappai.2015.10.006
|
Peng Chen, Ming Liu, Shihua Zhou. Discrete Salp Swarm Algorithm for symmetric traveling salesman problem[J]. Mathematical Biosciences and Engineering, 2023, 20(5): 8856-8874. doi: 10.3934/mbe.2023389
DownLoad: