A Parameters Analysis of Sine Cosine Algorithm on Travelling Salesman Problem

Yıl 2020, Cilt: 7 Sayı: 2, 526 - 535, 31.05.2020

Mehmet Fatih Demiral

https://doi.org/10.31202/ecjse.662864

Öz

Sine Cosine Algorithm (SCA) is a fairly new algorithm developed in 2016 by Mirjalili, likewise Black Hole Algorithm (BHA), Whale Optimization Algorithm (WOA), Artificial Atom Algorithm (A3) and Physarum-Energy Optimization Algorithm (PEO) proposed in 2013, 2016, 2018 and 2019, respectively. Due to new ideas in SCA, a few of publications have been published on SCA. SCA was applied on continuous and discrete optimization problems. In addition, there exist remarkable implementations of SCA in the field of engineering, science and technology. In this work, a parameters analysis of SCA has been done on a classical TSP (Berlin52-CTSP) and randomly generated TSP (RTSP). In order to do parameters analysis, major parameters have been changed gradually. For classical TSP, symmetric data has been taken from TSPLIB (TSP Library in net). The results are given as best, mean, worst solutions, std. deviation and CPU time for CTSP and RTSP. Besides, figures and tables demonstrate the effect of parameters for solving TSP. After adequate experimentation, based on trial-and-error methodology, optimal parameters and best ever solutions have been found. As a result, the findings indicate that major parameters of SCA influence the performance of that algorithm significantly.

Anahtar Kelimeler

Combinatorial Problems, Meta-heuristics, Sine Cosine Algorithm, Travelling Salesman Problem

Teşekkür

This research received no specific grants from any funding agency in public, commercial or non-profit sectors.

Sinüs Kosinüs Algoritmasının Gezgin Satıcı Problemi Üzerinde Parametre Analizi

Öz

Sinüs Kosinüs Algoritması (SCA) 2016 yılında, Mirjalili tarafından geliştirilmiş ve kara delik algoritması (BHA), balina optimizasyon algoritması (WOA), yapay atom algoritması (A3) ve physarum-enerji optimizasyon algoritması (PEO) gibi sırasıyla 2013, 2016, 2018 ve 2019 yıllarında önerilmiş olan oldukça yeni algoritmalardan biridir. SCA’ daki yeni fikirlerle birlikte, SCA üzerine birkaç yayın yayımlanmıştır. SCA sürekli ve kesikli optimizasyon problemleri üzerinde uygulanmıştır. Ek olarak, SCA’ nın mühendislik, bilim ve teknoloji alanında dikkate değer uygulamaları mevcuttur. Bu çalışmada, SCA’nın bir klasik gezgin satıcı problemi (Berlin52-CTSP) ve rassal olarak alınmış TSP verisetinde (RTSP) parametre analizi yapılmaktadır. Parametre analizi yapabilmek için, ana parametreler kademeli olarak değiştirilmiştir. Klasik TSP için, simetrik veri net deki TSPLIB’ den alınmıştır. Sonuçlar, CTSP ve RTSP için en iyi, ortalama, kötü çözümler, standard sapma ve CPU zamanları olarak verilmektedir. Bunun yanında, şekiller ve tablolar TSP’ nin çözümünde parametrelerin etkisini göstermektedir. Yeterli deneme sonucunda, deneme yanılma metodolojisi ile, optimal parametreler ve en iyi çözümler bulunmaktadır. Sonuç olarak, bulgular SCA’ nın ana parametrelerinin algoritma performansı üzerinde önemli derecede etki yaptığını göstermektedir.

Anahtar Kelimeler

Kombinatöryel Problemler, Metasezgiseller, Sinüs Kosinüs Algoritması, Gezgin Satıcı Problemi

Kaynakça

• [1] Mirjalili, S., “A Sine Cosine Algorithm for solving optimization problems”, Knowledge-Based Systems, 2016, 96, 120-133.
• [2] Osaba, E., Ser, J.D., Sadollah, A., Bilbao, M.N., Camacho, D., “A discrete water cycle algorithm for solving the symmetric and asymmetric traveling salesman problem”, Applied Soft Computing, 2018, 71, 277-290.
• [3] Ali, R.S., Alnahwi, F.M., Abdullah, A.S., “A modified camel travelling behavior algorithm for engineering applications”, Australian Journal of Electrical and Electronics Engineering, 2019, 16(3), 176-186, https://doi.org/10.1080/1448837X.2019.1640010.
• [4] Hatamlou, A., “Solving travelling salesman problem using black hole algorithm”, Soft Computing, 2018, 22 (24), 8167-8175, https://doi.org/10.1007/s00500-017-2760-y.
• [5] Ibrahim, M.K., Ali, R.S., “Novel Optimization Algorithm Inspired by Camel Traveling Behavior”, Iraqi Journal for Electrical and Electronic Engineering, 2016, 12(2), 167-177.
• [6] Das, S., Bhattacharya, A., Chakraborty, A.K., “Solution of short-term hydrothermal scheduling using sine cosine algorithm”, Soft Computing, 2018, 22(19), 6409-6427, https://doi.org/10.1007/s00500-017-2695-3.
• [7] Long, W., Wu, T., Liang, X., Xu, S., “Solving high-dimensional global optimization problems using an improved sine cosine algorithm”, Expert Systems with Applications, 2019, 123, 108-126.
• [8] Sindhu, R., Ngadiran, R., Yacob, Y.M., Zahri, N.A.H., Hariharan, M., “Sine-cosine algorithm for feature selection with elitism strategy and new updating mechanism”, Neural Computing and Applications, 2017, 28(10), 2947-2958. https://doi.org/10.1007/s00521-017-2837-7.
• [9] Yildirim, A.E., Karci A., “Applications of artificial atom algorithm to small-scale traveling salesman problems”, Soft Computing, 2018, 22(22), 7619-7631, https://doi.org/10.1007/s00500-017-2735-z.
• [10] Mavrovouniotis, M., Yang, S., “A memetic ant colony optimization algorithm for the dynamic travelling salesman problem”, Soft Computing, 2011, 15(7), 1405-1425, https://doi.org/10.1007/s00500-010-0680-1.
• [11] Xiutang G., Zhihua C., Wei Y., Deqian S., Kai Z., “Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search”, Applied Soft Computing, 2011, 11(4), 3680-3689.
• [12] Jangra, R., Kait, R., “ACO Parameters Analysis of TSP Problem”, International Journal of Computer Science and Mobile Applications, 2017, 5(8), 24-29.
• [13] Tawhid, M.A., Savsani, P., “Discrete Sine-Cosine Algorithm (DSCA) with Local Search for Solving Traveling Salesman Problem”, Arabian Journal for Science and Engineering, 2019, 44(4), 3669-3679.
• [14] Bektas, T., “The multiple traveling salesman problem: an overview of formulations and solution procedures”, Omega, 2006, 34(3), 209-219.
• [15] Zhong, Y., Lin, J., Wang, L., Zhang, H., “Discrete comprehensive learning particle swarm optimization algorithm with Metropolis acceptance criterion for traveling salesman problem”, Swarm and Evolutionary Computation, 2018, 42, 77–88, https://doi.org/10.1016/j.swevo.2018.02.017.
• [16] Kumar S., Datta D., Singh S.K., Black Hole Algorithm and Its Applications. In: Azar A., Vaidyanathan S. (eds) “Computational Intelligence Applications in Modeling and Control”, Studies in Computational Intelligence, vol 575, Springer, Cham, (2015).
• [17] 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”, Arabian Journal for Science and Engineering, 2018, 43(8), 4041–4056, https://doi:10.1007/s13369-017-2790-x.
• [18] Qu, C., Zeng, Z., Dai, J., Yi, Z, He, W., “A Modified Sine-Cosine Algorithm Based on Neighborhood Search and Greedy Levy Mutation”, Computational Intelligence and Neuroscience, 2018, vol. 2018, Article ID 4231647, 19 pages, https://doi.org/10.1155/2018/4231647.
• [19] Ekinci, S., “Optimal design of power system stabilizer using sine cosine algorithm”, Journal of the Faculty of Engineering and Architecture of Gazi University, 2019, 34(3), 1329-1350.
• [20] TSP Library (TSPLIB), 2019. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ (Accessed on 10.12.2019).
• [21] Wei, X., “ Parameters Analysis for Basic Ant Colony Optimization Algorithm in TSP ”, International Journal of u-and e-Service, Science and Technology (IJUNESST), 2014, 7(4), 159-170.
• [22] Shweta, K., Singh, A., “An Effect and Analysis of Parameter on Ant Colony Optimization for Solving Travelling Salesman Problem”, International Journal of Computer Science and Mobile Computing (IJCSMC), 2013, 2(11), 222-229.
• [23] Lin, W.-Y., Lee, W.-Y., Hong, T.-P., “Adapting Crossover and Mutation Rates in Genetic Algorithms”, Journal of Information Science and Engineering, 2003, 19(5), 889-903.