Bir Hibrid Deve Gezgin Davranışı Algoritmasının Gezgin Satıcı Problemi için Uygulaması

Abstract

Deve gezgin davranışı algoritması (CA) 2016 yılında Mohammed Khalid Ibrahim ve Ramzy Salim Ali tarafından önerilmiş, doğadan ilham alan bir meta-sezgiseldir. Bilimsel literatürde CA’ nın performansını ölçen birkaç çalışma bulunmaktadır. CA literatürde global optimizasyon ve mühendislik problemlerine uygulanmıştır. CA’ nın global optimizasyonda parçacık sürü optimizasyonu ve genetik algoritmadan daha iyi performans sergilediği gösterilmiştir. Buna karşın, bu algoritma gezgin satıcı probleminde olduğu gibi kombinatoryal optimizasyonda düşük kaliteli çözümler vermektedir. Bunun yanında, değiştirilmiş deve algoritması mühendislik alanında uygulanmıştır ve CS, PSO, CA’ dan daha iyi olduğu ortaya koyulmuştur. Bu sebeple, CA’ nın tur oluşturucu bir sezgiselle (En yakın komşu algoritması-NN) hibrid edilerek iyileştirilmesi ihtiyacı bulunmaktadır. Bu karşılaştırmalı uygulamada, 29-195 arasında değişen boyutlarda şehir içeren 13 küçük ve orta ölçekli veriseti kullanılmıştır. Sonuçlar, hibrid algoritmanın (HA), tabu arama (TS), GA, CA, ve karınca sistemine (AS) göre wi29, eil76, pr76, ve rat99 dışında bütün verisetlerinin %70 inde daha üstün olduğunu göstermektedir. Çalışmada, detaylı bir analiz verilerek en iyi, en kötü, ortalama çözümler, standard sapma, ve ortalama CPU zamanları sunulmaktadır. Metrikler, ayrıca hibrid meta-sezgiselin kabul edilebilir çözümleri bulmada 64% performans sergilediğini vurgulamaktadır. Sonuç olarak, hibrid algoritma küçük ve orta ölçekli verisetlerinde diğer test algoritmalarına kıyasla kesikli problemi daha kısa hesaplama zamanlarında çözmektedir.

Keywords

• Deve Algoritması
• Hibrid Algoritma
• Meta-sezgiseller
• Gezgin Satıcı Problemi

Application of a Hybrid Camel Traveling Behavior Algorithm for Traveling Salesman Problem

Abstract

Camel Traveling Behavior Algorithm (CA) is a nature-inspired meta-heuristic proposed in 2016 by Mohammed Khalid Ibrahim and Ramzy Salim Ali. There exist few publications that measure the performance of the CA on scientific literature. CA was implemented to global optimization and some engineering problems in the literature. It was shown that CA demonstrates better performance than Particle Swarm Optimization (PSO) and Genetic Algorithm (GA) in global optimization. However, it gives poor solutions at combinatorial optimization as well as in traveling salesman problems (TSP). Besides, a modified camel algorithm (MCA) was applied in the field of engineering and was proved that it is better than Cuckoo Search (CS), PSO, and CA. Therefore, it is a need for improvement in CA by hybridizing with a constructive heuristic (Nearest Neighbor Algorithm-NN). A set of thirteen small and medium-scale datasets that have cities scales ranging from 29 to 195 was used in the comparative study. The results show that the hybrid algorithm (HA) outperforms Tabu Search (TS), GA, CA, and Ant system (AS) for 70% of all datasets, excluding wi29, eil76, pr76, and rat99. Also, it was given that a detailed analysis presents the number of best, worst, average solutions, standard deviation, and average CPU time. The metrics also stress that the hybrid meta-heuristic demonstrates 64% performance in finding acceptable solutions. Finally, the hybrid algorithm solves the discrete problem in short computational times when compared to other test algorithms for small and medium-scale datasets.

Keywords

• Camel Algorithm
• Hybrid Algorithm
• Meta-heuristics
• Traveling Salesman Problem

References

1. [1] Rajabioun, R. 2011. Cuckoo optimization algorithm, Applied Soft Computing, 11(8), 5508-5518
2. [2] Mian, T.A., Muhammad, U., Riaz, A. 2012. Jobs scheduling and worker assignment problem to minimize makespan using ant colony optimization metaheuristic, World Academy of Science, Engineering and Technology, 6(12), 2823-2826
3. [3] Tawhid, M.A., Savsani, P. 2019. Discrete Sine-Cosine Algorithm (DSCA) with Local Search for Solving Traveling Salesman Problem, Arabian Journal for Science and Engineering, 44(4), 3669-3679
4. [4] Teeninga, A., Volgenant, A. 2004. Improved Heuristics for the Traveling Purchaser Problem, Computers & Operations Research, 31, 139-150
5. [5] Soylu, B. 2015. A general variable neighborhood search heuristic for multiple traveling salesmen problem, Computers & Industrial Engineering, 90, 390–401
6. [6] Gendreau, M., Hertz, A., Laporte, G., Stan, M. 1998. A generalized insertion heuristic for the traveling sal-esman problem with time windows, Operations Research, 46(3), 330-335
7. [7] Zhang, R., Yun, W. Y., Kopfer, H. 2010. Heuristic-based truck scheduling for inland container transportation, OR Spectrum, 32, 787-808. DOI: 10.1007/s00291-010-0193-4
8. [8] Xinchao, Z. 2011. Simulated annealing algorithm with adaptive neghborhood, Applied Soft Computing, 11(2), 1827-1836

9. [9] Misevicius, A. 2005. A tabu search algorithm for the quadratic assignment problem, Computational Optimization and Applications, 30, 95-111. DOI: 10. 1007/s10589-005-4562-x
10. [10] Laboudi, Z., Chikhi, S. 2012. Comparison of Genetic Algorithm and Quantum Genetic Algorithm, The International Arab Journal of Information Technology, 9(3), 243-249
11. [11] Chaharsooghi, S.K., Kermani, A.H.M. 2008. An effec-tive ant colony optimization algorithm (ACO) for multi-objective resource allocation problem (MORAP), Applied Mathematics and Computation, 200(1), 167-177
12. [12] Woo, Z., Hoon, J., Loganathan, G.V. 2001. A New Heuristic Optimization Algorithm: Harmony Search, Simulation,76(2), 60-68. DOI: 10.1177/0037549701 07600201
13. [13] Farmer, J.D., Packard, N.H., Perelson, A.S. 1986. The Immune System, Adaptation, and Machine Learning, Physica D, 22, 187-204 [14] Storn, R., Price, K. 1997. Differential Evolution – A Simple and Efficient Heuristic for global Optimization over Continuous Spaces, Journal of Global Optimization 11, 341–359. DOI: 10.1023/A:1008202821328
14. [15] Yang, X-S. 2010. Nature-inspired metaheuristic algorithms, 2nd edition. Luniver Press, Frome.
15. [16] Yang, X-S. 2010. A New Meta-heuristic Bat Inspired Algorithm. pp 65-74. Gonzales, J.R., Pelta, D.A., Cruz, C., Terrazas, G., Krasnogor, G., ed. 2010. Nature Inspired Cooperative Strategies for Optimization (NICSO 2010), Springer, Berlin, Heidelberg, 397p.
16. [17] Hatamlou, A. 2018. Solving travelling salesman problem using black hole algorithm, Soft Computing, 22(24), 8167-8175. DOI: 10.1007/s00500-017-2760-y
17. [18] Wang, Z., Geng, X., Shao, Z. 2009. An effective simulated annealing algorithm for solving the travelling salesman problem, Journal of Computational and Theoretical Nanoscience, 6(7), 1680-1686
18. [19] Khanra, A., Maiti, M.K., Maiti, M. 2015. Profit maximization of tsp through a hybrid algorithm, Computers & Industrial Engineering, 88, 229-236. DOI: 10.1016/j.cie.2015.06.018
19. [20] Sahana, S.K. 2019. Hybrid optimizer for the travelling salesman problem, Evolutionary Intelligence, 12, 179-188. DOI: 10.1007/s12065-019-00208-7
20. [21] Ouaaraba, A., Ahioda, B., Yangb, X.-S. 2014. Discrete cuckoo search algorithm for the traveling salesman problem, Neural Computing and Applications, 24(7-8), 1659-1669. DOI: 10.1007/s00521-013-1402-2
21. [22] Chen, S.-M., Chien, C.-Y. 2011. Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques, Expert Systems with Applications 38(12), 14439-14450
22. [23] 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
23. [24] Ali, R.S., Alnahwi, F.M., Abdullah, A.S. 2019. A modified camel travelling behavior algorithm for engineering applications, Australian Journal of Electrical and Electronics Engineering, 16(3),176-186. DOI: 10.1080/1448837X.2-019.1640010
24. [25] Hassan, K.H, Abdulmuttalib, T.R., Jasim, B.H. 2021. Parameters estimation of solar photovoltaic module using camel behavior search algorithm, International Journal of Electrical and Computer Engineering (IJECE), 11(1), 788-793
25. [26] Demiral, M. F. 2021. An application of a modified camel traveling behavior algorithm for traveling salesman problem, Journal of Scientific Reports-A, 047, 88-98. https://dergipark.org.tr/en/pub/jsr-a/issue/6- 7627/901408
26. [27] Alobaidi, A.T., Abdullah, H.S., Ahmed, Z.O. 2017. Camel Herds Algorithm: a New Swarm Intelligent Algorithm to Solve Optimization Problems, International Journal on Perceptive and Cognitive Computing (IJPCC), 3(1), 6-10
27. [28] Ahmed, Z. O., Sadiq, A.T., Abdullah, H.S. 2019. Solving the Traveling Salesman's Problem Using Camels Herd Algorithm, 2nd Scientific Conference of Computer Sciences (SCCS), University of Technology-Iraq, 1-5
28. [29] Fagerholt, K., Christiansen, M. 2000. A traveling salesman problem with allocation, time window, and precedence constraints - an application to ship scheduling, International Transactions in Operational Research, 7, 231-244
29. [30] Nagata, Y., Soler, D. 2012. A new genetic algorithm for the asymmetric traveling salesman problem, Expert Systems with Applications, 39, 8947-8953
30. [31] Yildirim, A.E., Karci, A. 2018. Applications of artificial atom algorithm to small-scale traveling salesman problems, Soft Computing, 22(22):7619-7631. DOI: 10.1007/s00500-017-2735-z
31. [32] Petersen, H. L., Archetti, C., Sprenza, M. G. 2010. Exact solutions to the double travelling salesman problem with multiple stacks, Networks, 56(4), 229-243
32. [33] Yuan, S., Skinner, B., Huang, S., Liu, D. 2013. A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms, European Journal of Operational Research, 228, 72–82
33. [34] Montemanni, R., Mojana, M., Di Caro, G., Gambardella, L.M. 2013. A decomposition-based exact approach for the sequential ordering problem, Journal of Applied Operational Research, 5(1), 2-13
34. [35] Mansini, R., Tocchella, B. 2009. The Traveling Purchaser Problem with Budget Constraint, Computers & Operations Research, 36, p.2263-2274
35. [36] Chandra, A., Naro, A. 2020. A Comparative Study of Capacitated Vehicle Routing Problem Heuristic Model, International Journal of Engineering and Emerging Technology, 5(2), 94-100
36. [37] van Ee, M., Sitters, R. 2018. The A Priori Traveling Repairman Problem, Algorithmica, 80, 2818–2833. DOI: 10.1007/s00453-017-0351-z
37. [38] Burkard, R.E., Deineko, V.G., van Dal, R., van, J.A.A., Veen, der, Woeginger, G.J. 1998. Well-solvable special cases of the traveling salesman problem: a survey, Society for Industrial and Applied Mathematics, 40(3), 496-546. DOI: 10.1137/S0036144596297514
38. [39] 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.
39. [40] Shweta, K., Singh, A. 2013. An Effect and Analysis of Parameter on Ant Colony Optimization for Solving Travelling Salesman Problem, International Journal of Computer Science and Mobile Computing (IJCSMC), 2(11), 222-229.
40. [41] 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.
41. [42] Halim, A.H. and Ismail, I. 2019. Combinatorial optimization: comparison of heuristic algorithms in travelling salesman problem, Archives of Computational Methods in Engineering, 26, 367–380. DOI: 10.1007/s11831-017-9247-y
42. [43] Szeto, W.Y., Yongzhong, W., Ho, S.C. 2011. An artificial bee colony algorithm for the capacitated vehicle routing problem, European Journal of Operational Research, 215(1), 126-135. DOI: 10.1016/j.ejor.2011.06.006
43. [44] Feng, X., Liu, Y., Yu, H., Luo, F. 2019. Physarum-energy optimization algorithm, Soft Computing, 23, 871–888. DOI: 10.1007/s00500-017-2796-z.
44. [45] Demiral, M.F., Işik, A.H. 2020. Simulated annealing algorithm for a medium-sized tsp data. pp. 457-465. Hemanth, D. J., Kose, U., ed. 2020, Artificial Intelligence and Applied Mathematics in Engineering Problems, Springer, Cham, 1081p. DOI: 10.1007/978-3-030-36178-5_35