Abstract
One of the new population-based optimization algorithms, named sine-cosine algorithm (SCA), is introduced to solve continuous optimization problems. SCA utilizes the sine and cosine functions to recast a set of potential solutions to balance between exploration and exploitation in the search space. Many researchers have developed and introduced a modified version of SCA to solve engineering problems, multi-objective version of SCA to solve multi-objective engineering design problems, and a binary version of SCA to deal with datasets. Our goal from this work to propose discrete SCA (DSCA) to solve the traveling salesman problem (TSP). The TSP is one of the typical NP-hard problems. DSCA works on the basic concepts of exploration and exploitation. To balance the exploration and exploitation in DSCA, it uses two different mathematical expressions to update the solutions in each generation. DSCA is combined with 2-opt local search method to improve exploitation. To enhance the exploration heuristic crossover, it is united with the proposed DSCA. A benchmarks problem selected from TSPLIB is used to test the algorithm, and the results show that the DSCA algorithm proposed in this article is comparable with the other state-of-the-art algorithms over a wide range of TSP.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Mirjalili, S.: SCA: a sine cosine algorithm for solving optimization problems. Knowl.-Based Syst. 96, 120–133 (2016)
Tawhid, M.A.; Savsani, V.: Multi-objective sine-cosine algorithm (MO-SCA) for multi-objective engineering design problems. Neural Comput. Appl. (2017). https://doi.org/10.1007/s00521-017-3049-x
Elaziz, M.A.; Oliva, D.; Xiong, S.: An improved opposition-based sine cosine algorithm for global optimization. Expert Syst. Appl. 90, 484–500 (2017)
Li, S.; Fang, H.; Liu, X.: Parameter optimization of support vector regression based on sine cosine algorithm. Expert Syst. Appl. 91, 63–77 (2018)
Kumar, V.; Kumar, D.: Data clustering using sine cosine algorithm: Data clustering using SCA. In: Hassanien, E., Gaber, T. (eds.) Handbook of Research on Machine Learning Innovations and Trends, pp. 715–726. IGI Global (2017)
Das, S.; Bhattacharya, A.; Chakraborty, A.K.: Solution of short-term hydrothermal scheduling using sine cosine algorithm. Soft Comput. 22(19), 6409–6427 (2018)
Reddy, K.S.; Panwar, L.K.; Panigrahi, B.K.; Kumar, R.: A new binary variant of sine-cosine algorithm: development and application to solve profit-based unit commitment problem. Arab. J. Sci. Eng. 43(8), 4041–4056 (2018)
Zhang, W.; Korf, R.E.: A study of complexity transitions on the asymmetric traveling salesman problem. Artif. Intell. 81(1–2), 223–239 (1996)
Rodríguez, A.; Ruiz, R.: The effect of the asymmetry of road transportation networks on the traveling salesman problem. Comput. Oper. Res. 39(7), 1566–1576 (2012)
Berman, P.; Karpinski, M.: 8/7-approximation algorithm for (1, 2)-TSP. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, pp. 641–648. Society for Industrial and Applied Mathematics (2006)
He, J.; Yan, H.; Qiang, L.; Hong, Y.: Fat computational complexity and heuristic design for the TSP. J. Softw. 20(9), 2344–2351 (2009)
Bellman, R.; Dreyfus, S.E.: Applied Dynamic Programming, vol. 2050. Princeton University Press, Princeton (2015). ISBN 1400874653, 9781400874651
Lawler, E.L.; Wood, D.E.: Branch-and-bound methods: a survey. Oper. Res. 14(4), 699–719 (1966)
Gregor, D.; Lumsdaine, A.: The parallel BGL: a generic library for distributed graph computations. Parallel Object-Oriented Sci. Comput. 2, 1–18 (2005)
Climer, S.; Zhang, W.X.: Cut-and-solve: An iterative search strategy for combinatorial optimization problems. Artif. Intell. 170(8–9), 714–738 (2006)
Johnson, D.S.; McGeoch, L.A.: Experimental analysis of heuristics for the STSP. In: Gutin, G., Punnen, A.P. (eds.) The Traveling Salesman Problem and Its Variations. Combinatorial Optimization, vol. 12, pp. 369–443. Springer, Boston, MA (2007)
Croes, G.A.: A method for solving traveling-salesman problems. Oper. Res. 6(6), 791–812 (1958)
Lin, S.: Computer solutions of the traveling salesman problem. Bell Syst. Techn. J. 44(10), 2245–2269 (1965)
Lin, S.; Kernighan, B.W.: An effective heuristic algorithm for the traveling- salesman problem. Oper. Res. 21(2), 498–516 (1973)
Helsgaun, K.: An effective implementation of the Lin–Kernighan traveling salesman heuristic. Eur. J. Oper. Res. 126(1), 106–130 (2000)
Guo, T.; Michalewicz, Z.: Invor-Over Operator for the TSP-Proceedings of the 5th Parallel Problem Solving from Nature Conference (1998)
Junzhong, J.; Huang, Z.; Chunnian, L.: An ant colony algorithm based on multiple-grain representation for the traveling salesman problems. J. Comput. Res. Dev. 47(3), 434–444 (2010)
Shu, J.L.; Zhao, Z.; Dai, Q.Y.: Genetic algorithm for TSP. Oper. Res. Manag. Sci. 13(1), 17–22 (2004)
Kirkpatrick, S.; Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671–680 (1983)
Kennedy, J.; Eberhart, R.C.: A discrete binary version of the particle swarm algorithm. In: Systems, Man, and Cybernetics, 1997. 1997 IEEE International Conference on, Computational Cybernetics and Simulation, vol. 5, pp. 4104–4108. IEEE (1997)
Chen, W.N.; Zhang, J.; Chung, H.S.; Zhong, W.L.; Wu, W.G.; Shi, Y.H.: A novel set-based particle swarm optimization method for discrete optimization problems. IEEE Trans. Evolut. Comput. 14(2), 278–300 (2010)
Liu, X.; Xiu, C.: A novel hysteretic chaotic neural network and its applications. Neurocomputing 70(13), 2561–2565 (2007)
Han, F.; Ling, Q.H.; Huang, D.S.: An improved approximation approach incorporating particle swarm optimization and a priori information into neural networks. Neural Comput. Appl. 19(2), 255–261 (2010)
Hunt, J.E.; Cooke, D.E.: Learning using an artificial immune system. J. Netw. Comput. Appl. 19(2), 189–212 (1996)
Merz, P.; Freisleben, B.: Genetic local search for the TSP: new results. In: IEEE International Conference on Evolutionary Computation, 1997, pp. 159–164. IEEE (1997)
Bontoux, B.; Artigues, C.; Feillet, D.: A memetic algorithm with a large neighborhood crossover operator for the generalized traveling salesman problem. Comput. Oper. Res. 37(11), 1844–1852 (2010)
Yang, J.; Shi, X.; Marchese, M.; Liang, Y.: An ant colony optimization method for generalized TSP problem. Prog. Nat. Sci. 18(11), 1417–1422 (2008)
Samanlioglu, F.; Ferrell, W.G.; Kurz, M.E.: A memetic random-key genetic Algorithm for a symmetric multi-objective traveling salesman problem. Comput. Ind. Eng. 55(2), 439–449 (2008)
Gang, P.; Iimura, I.; Nakayama, S.: An evolutionary multiple heuristic with genetic local search for solving TSP. Int. J. Inf. Technol. 14(2), 1–11 (2008)
Marinakis, Y.; Marinaki, M.; Dounias, G.: Honey bees mating optimization algorithm for the Euclidean traveling salesman problem. Inf. Sci. 181(20), 4684–4698 (2011)
Zhou, Y.Q.; Huang, Z.X.; Liu, H.X.: Discrete glowworm swarm optimization algorithm for TSP problem. DianziXuebao(Acta Electronica Sinica) 40(6), 1164–1170 (2012)
Ouaarab, A.; Ahiod, B.; Yang, X.S.: Discrete cuckoo search algorithm for the traveling salesman problem. Neural Comput. Appl. 24(7–8), 1659–1669 (2014)
Wang, Y.: The hybrid genetic algorithm with two local optimization strategies for traveling salesman problem. Comput. Ind. Eng. 70, 124–133 (2014)
Liu, W.; Zheng, J.; Wu, M.; Zou, J.: Hybrid crossover operator based on pattern, Seventh International Conference on Natural Computation (ICNC) 2011, vol. 2, pp. 1097–1100 (2011)
Tsai, C.F.; Tsai, C.W.; Tseng, C.C.: A new hybrid heuristic approach for solving large traveling salesman problem. Inf. Sci. 166(1), 67–81 (2004)
Pasti, R.; De Castro, L.N.: A neuro-immune network for solving the traveling salesman problem. In: IJCNN’06. International Joint Conference on Neural Networks, 2006. pp. 3760–3766. IEEE (2006)
Masutti, T.A.; de Castro, L.N.: A self-organizing neural network using ideas from the immune system to solve the traveling salesman problem. Inf. Sci. 179(10), 1454–1468 (2009)
Chen, S.M.; Chien, C.Y.: Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques. Expert Syst. Appl. 38(12), 14439–14450 (2011)
Jun-man, K.; Yi, Z.: Application of an improved ant colony optimization on generalized traveling salesman problem. Energy Procedia 17, 319–325 (2012)
Junqiang, W.; Aijia, O.: A hybrid algorithm of ACO and delete-cross method for TSP. In: 2012 International Conference on Industrial Control and Electronics Engineering (ICICEE), pp. 1694–1696. IEEE (2012)
Dong, G.; Guo, W.W.; Tickle, K.: Solving the traveling salesman problem using cooperative genetic ant systems. Expert Syst. Appl. 39(5), 5006–5011 (2012)
Othman, Z.A.; Srour, A.I.; Hamdan, A.R.; Ling, P.Y.: Performance water flow-like algorithm for TSP by improving its local search. Int. J. Adv. Comput. Technol. 5(14), 126 (2013)
Peker, M.; ŞEN, B.; Kumru, P.Y.: An efficient solving of the traveling salesman problem: the ant colony system having parameters optimized by the Taguchi method. Turk. J. Electr. Eng. Comput. Sci. 21(Sup. 1), 2015–2036 (2013)
Gunduz, M.; Kiran, M.S.; Ozceylan, E.: A hierarchic approach based on swarm intelligence to solve the traveling salesman problem. Turk. J. Electr. Eng. Comput. Sci. 23(1), 103–117 (2015)
Mahi, M.; Baykan, Ö.K.; Kodaz, H.: 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 (2015)
Escario, J.B.; Jimenez, J.F.; Giron-Sierra, J.M.: Ant colony extended: experiments on the traveling salesman problem. Expert Syst. Appl. 42(1), 390–410 (2015)
Yang, J.; Wu, C.; Lee, H.P.; Liang, Y.: Solving traveling salesman problem using generalized chromosome genetic algorithm. Prog. Nat. Sci. 18, 887–892 (2008)
Osaba, E.; Yang, X.S.; Diaz, F.; Lopez-Garcia, P.; Carballedo, R.: An improved discrete bat algorithm for symmetric and asymmetric traveling salesman problems. Eng. Appl. Artif. Intell. 48(1), 59–71 (2016)
Zhou, Y.; Luo, Q.; Chen, H.; He, A.; Wu, J.: A discrete invasive weed optimization algorithm for solving traveling salesman problem. Neurocomputing 151, 1227–1236 (2015)
Toth, P.; Vigo, D. (eds.): Vehicle Routing: Problems, Methods, and Applications. Society for Industrial and Applied Mathematics. SIAM, Philadelphia (2014)
Chen, H.; Zhou, Y.; He, S.; Ouyang, X.; Guo, P.: Invasive weed optimization algorithm for solving permutation flow-shop scheduling problem. J. Comput. Theor. Nanosci. 10(3), 708–713 (2013)
Snyder, L.V.; Daskin, M.S.: A random-key genetic algorithm for the generalized traveling salesman problem. Eur. J. Oper. Res. 174(1), 38–53 (2006)
Ouyang, X.; Zhou, Y.; Luo, Q.; Chen, H.: A novel discrete cuckoo search algorithm for spherical traveling salesman problem. Appl. Math. Inf. Sci. 7(2), 777 (2013)
Choi, I.C.; Kim, S.I.; Kim, H.S.: A genetic algorithm with a mixed region search for the asymmetric traveling salesman problem. Comput. Oper. Res. 30(5), 773–786 (2003)
Cirasella, J.; Johnson, D.S.; McGeoch, L.A.; Zhang, W.: The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests. Algorithm Engineering an Experimentation, pp. 32–59. Springer, Berlin (2001)
Acknowledgements
We would like to thank the reviewers for their thoughtful comments and efforts toward improving our manuscript. Also, we are grateful to Marium Tawhid for editing this paper. The research of the Mohamed A. Tawhid is supported in part by the Natural Sciences and Engineering Research Council of Canada (NSERC). NSERC also supports the postdoctoral fellowship of the Poonam Savsani by NSERC.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Tawhid, M.A., Savsani, P. Discrete Sine-Cosine Algorithm (DSCA) with Local Search for Solving Traveling Salesman Problem. Arab J Sci Eng 44, 3669–3679 (2019). https://doi.org/10.1007/s13369-018-3617-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s13369-018-3617-0