Analysis of a Hybrid Whale Optimization Algorithm for Traveling Salesman Problem

Öz

Whale Optimization Algorithm (WOA) is a fairly new algorithm developed in 2016. WOA was applied to continuous optimization problems and engineering problems in the literature. However, WOA demonstrates lower performance than others in traveling salesman problems. Therefore, in this study, an application of the hybrid algorithm (WOA+NN) has been done in the traveling salesman problem. A set of classical datasets which have cities scale ranged from 51 to 150 was used in the application. The results show that the hybrid algorithm (WOA+NN) outperforms AS (Ant system), WOA, GA, and SA for 50% of all datasets. Ant system (AS) is the second algorithm that is better than other metaheuristics for 40% of all datasets. In addition, it was given that a detailed analysis presents the number of best, worst, average solutions, standard deviation, and the average CPU time concerning meta-heuristics. The metrics stress that the hybrid algorithm (WOA+NN) demonstrates a performance rate over 50% in finding optimal solutions. AS (Ant system) is better at 40% of all optimal solutions. Finally, the hybrid algorithm solves the discrete problem in reasonable times in comparison to other algorithms for medium-scale datasets.

Anahtar Kelimeler

• Hybrid algorithm
• traveling salesman problem
• whale optimization algorithm

Bir Hibrid Balina Optimizasyon Algoritminin Gezgin Satıcı Problemi için Analizi

Öz

Balina optimizasyon algoritması (WOA) 2016 yılında geliştirilmiş olan oldukça yeni bir algoritmadır. Balina optimizasyon algoritması literatürde sürekli optimizasyon problemlerine ve mühendislik problemlerine uygulanmıştır. Buna rağmen, WOA gezgin satıcı probleminde diğer algoritmalardan daha düşük performans sergilemektedir. Bu yüzden, bu çalışmada, hibrid algoritmanın (WOA+NN) gezgin satıcı problem üzerinde bir uygulaması yapılmaktadır. Uygulamada 51-150 arasında ölçekli şehirlerden oluşan bir klasik veriseti kullanılmıştır. Sonuçlar, hibrid algoritmanın (WOA+NN), AS (Karınca sistemi), WOA, GA ve SA’dan tüm verisetlerinin %50’sinde üstün olduğunu göstermektedir. Karınca sistemi ise tüm verisetlerinin %40’ında diğer meta-sezgisellerden daha olumlu sonuç veren ikinci algoritmadır. Çalışmada, detaylı bir analiz verilerek meta-sezgisellere göre en iyi, en kötü, ortalama çözümler, standart sapma ve ortalama CPU zamanı sunulmaktadır. Metrikler, hibrid algoritmanın (WOA+NN) optimal çözümleri bulmada %50’nin üzerinde performans sergilediğini göstermektedir. Karınca sistemi (AS) ise, tüm çözümlerin %40’ında daha iyidir. Sonuç olarak, hibrid algoritma orta ölçekli verisetlerinde diğer algoritmalara kıyasla kesikli problemi kabul edilebilir zamanlarda çözmektedir.

Anahtar Kelimeler

• Hibrid algoritma
• gezgin satıcı problemi
• balina optimizasyon algoritması

Kaynakça

1. Abdel-Basset, M., El-Shahat, D., Sangaiah, A.K. (2019). A modified nature inspired meta-heuristic whale optimization algorithm for solving 0–1 knapsack problem. International Journal of Machine Learning and Cybernetics, 10: 495–514.
2. Ahmed, O. M. A., Kahramanlı, H. (2018). Meta-Heuristic Solution Approaches for Traveling Salesperson Problem. International Journal of Applied Mathematics Electronics and Computers, 6(3): 21-26.
3. Algabalawy, M.A., Abdelaziz, A.Y., Mekhamer, S.F., Abdel Aleem, S.H.E. (2010). Considerations on optimal design of hybrid power generation systems using whale and sine cosine optimization algorithms. Journal of Electrical Systems and Information Technology, 5(3): 312-325.
4. Alp, O., Erkut, E., Drezner, Z. (2003). An Efficient Genetic Algorithm for the P-Median Problem. Annals of Operations Research, 122(1-4): 21-42.
5. Arnaout, J.P. (2014). Worm optimization: A novel optimization algorithm inspired by C. Elegans. Proceedings of the 2014 International Conference on Industrial Engineering and Operations Management, Bali, Indonesia, 2499-2505.
6. Bozorgi, S.M., Yazdani, S. (2019). IWOA: An improved whale optimization algorithm for optimization problems. Journal of Computational Design and Engineering, 6(3): 243–259.
7. Cárdenas-Montes, M. (2018). Creating hard-to-solve instances of travelling salesman problem. Applied Soft Computing, 71: 268-276.
8. Cherkesly, M., Desaulniers, G., Irnich, S., Laporte, G. (2016). Branch-price-and cut algorithms for the pickup and delivery problem with time windows and multiple stacks. European Journal of Operational Research, 250: 782-793.

9. Demiral, M.F., Işik, A.H. (2020). Simulated annealing algorithm for a medium-sized tsp data. In: Artificial Intelligence and Applied Mathematics in Engineering Problems. Hemanth, D.J., Kose, U. (eds.), Springer, Cham, 457-465.
10. Elloumi, W., Abed, H. E., Abraham, A., Alimi, A.M. (2014). A comparative study of the improvement of performance using a PSO modified by ACO applied to TSP. Applied Soft Computing, 25: 234–241.
11. Halim, A.H., Ismail, I. (2019). Combinatorial optimization: comparison of heuristic algorithms in travelling salesman problem. Archives of Computational Methods in Engineering, 26: 367–380.
12. Hatamlou, A. (2018). Solving travelling salesman problem using black hole algorithm. Soft Computing, 22(24): 8167-8175.
13. Hoffman, K.L., Padberg, M., Rinaldi, G. (2013). Traveling salesman problem. Encyclopedia of operations research and management science. Kluwer Academic Publishers, Springer, Berlin.
14. Hussein, A.G., Hassanien, A.E., Houssein, E.H., Amin, M., Azar, A.T. (2019). New binary whale optimization algorithm for discrete optimization problems. Engineering Optimization, 52(6): 945-959.
15. Ibrahim, M.K., Ali, R.S. (2016). Novel optimization algorithm inspired by camel traveling behavior. Iraqi Journal for Electrical and Electronic Engineering, 12(2): 167-177.
16. Jiang, T., Zhang, C., Sun, Q-M. (2019). Green job shop scheduling problem with discrete whale optimization algorithm. IEEE Access, 7: 43153-43166.
17. Kirkpatrick, S., Gelatt, C., Vecchi, M. (1983). Optimization by simulated annealing. Science, 220(4598): 671–680.
18. Kota, L., Jarmai, K. (2015). Mathematical modeling of multiple tour multiple traveling salesman problem using evolutionary programming. Applied Mathematical Modeling, 39: 3410–3433.
19. Lin, W.-Y., Lee, W.-Y., Hong, T.-P. (2003). Adapting Crossover and Mutation Rates in Genetic Algorithms. Journal of Information Science and Engineering, 19(5): 889-903.
20. Lin, Y., Bian, Z., Liu, X. (2016). Developing a dynamic neighborhood structure for an adaptive hybrid simulated annealing - tabu search algorithm to solve the symmetrical traveling salesman problem. Applied Soft Computing, 49: 937-952.
21. Long, W., Wu, T., Liang, X., Xu, S. (2019). Solving high-dimensional global optimization problems using an improved sine cosine algorithm. Expert Systems with Applications, 123: 108-126.
22. Luan, F., Cai, Z., Wu, S., Liu, S.Q., He, Y. (2019). Optimizing the low-carbon flexible job shop scheduling problem with discrete whale optimization algorithm. Mathematics, 7(8), 688; DOI: 10.3390/math7080688
23. Mavrovouniotis, M., Yang, S. (2011). A memetic ant colony optimization algorithm for the dynamic travelling salesman problem. Soft Computing, 15(7): 1405-1425.
24. Mirjalili, S., Lewis, A. (2016). The whale optimization algorithm. Advances in Engineering Software, 95: 51-67.
25. Osaba, E., Yang, X.-S., Diaz, F., Lopez-Garcia, P., Carbelledo, R. (2016). An improved discrete bat algorithm for symmetric and asymmetric traveling salesman problems. Engineering Applications of Artificial Intelligence, 48: 59-71.
26. Parejo, J.A., Ruiz-Cortés, A., Lozano, S., and Fernandez, P. (2012). Metaheuristic optimization frameworks: a survey and benchmarking. Soft Computing, 16: 527–561.
27. Pessin, G., Sales, D.O., Dias, M.A., Klaser, R.L., Wolf, D.F., Ueyama, J., Osório, F.S., Vargas, P.A. (2013). Swarm intelligence and the quest to solve a garbage and recycling collection problem. Soft Computing, 17: 2311–2325.
28. Rajabioun, R. (2011) Cuckoo optimization algorithm. Applied Soft Computing, 11(8):5508–5518.
29. Qinghua, W., Yang, W., Zhipeng, L. (2015). A tabu search based hybrid evolutionary algorithm for the max-cut problem. Applied Soft Computing, 34: 827-837.
30. Szeto, W.Y., Yongzhong, W. and Ho, S.C., (2011). An artificial bee colony algorithm for the capacitated vehicle routing problem. European Journal of Operational Research, 215(1): 126-135.
31. Wei, X. (2014). Parameters Analysis for Basic Ant Colony Optimization Algorithm in TSP. International Journal of u-and e-Service, Science and Technology (IJUNESST), 7(4): 159-170.
32. Yang, X-S. (2010). Nature-inspired metaheuristic algorithms, 2nd edn. Luniver Press, Frome.
33. Yazdani, M., Fariborz, J. (2016). Lion Optimization Algorithm (LOA): A nature-inspired metaheuristic algorithm. Journal of Computational Design and Engineering, 3(1): 24-36.
34. Yildirim, A.E., Karci, A. (2018). Applications of artificial atom algorithm to small-scale traveling salesman problems. Soft Computing, 22(22): 7619-7631.
35. Yin, P.Y., Wang, J.Y. (2006). Ant colony optimization for the nonlinear resource allocation problem. Applied Mathematics and Computation, 174(2): 1438-1453.