Gri Kurt Optimizasyon Algoritmasının P-Medyan Problemlerine Uygulanması

Year 2024, , 166 - 177, 30.04.2024

Gülşen Orucova Büyüköz , Hüseyin Haklı

https://doi.org/10.47112/neufmbd.2024.40

Abstract

Bu çalışmada Np-zor problem sınıfından olan P-Medyan problemi Gri Kurt Optimizasyon (GKO) algoritması ile çözülmeye çalışıldı. GKO algoritmasının sürekli arama uzayı için önerilmesi nedeniyle kombinatoryal yapıya sahip olan P-Medyan problemine doğrudan bu algoritmanın uygulanması mümkün değildir. Bu sebeple GKO algoritmasının ayrık arama uzayında işlem yapabilecek şekilde uyarlanması gerekmektedir. Bu süreçte Diferansiyel Evrim Algoritmasının arama stratejisinden esinlenilerek GKO algoritması ile birlikte çaprazlama tekniği kullanılmıştır. Çalışmada öncelikle tekdüze çaprazlama tekniğinden faydalanılmıştır. Daha sonra GKO algoritmasında bulunan ve iterasyona bağlı olarak değişen parametre dikkate alınarak adaptif tekdüze çaprazlama olarak adlandırdığımız çaprazlama tekniği oluşturulmuştur. Önerilen bu algoritma 40 P-Medyan problemi üzerinde test edilmiştir. Elde edilen çözümler karşılaştırıldığında adaptif çaprazlama tekniğinin 40 problemin tamamında tekdüze çaprazlama tekniğinden daha iyi sonuçlar verdiğini görülmüştür. Ayrıca iki çaprazlama tekniği kullanılarak elde edilen sonuçların sayısal olarak karşılaştırılabilmesi için çözümler arasındaki iyileştirme oranına bakılmıştır. Elde edilen oranlar 40 problemin hepsinde adaptif tekdüze çaprazlama tekniğinin, tekdüze çaprazlama tekniğinde elde edilen çözümleri önemli oranda iyileştirdiği gözlemlenmiştir.

Keywords

NP-zor, Gri Kurt Optimizasyon Algoritması, P-Medyan Problemi, Tekdüze çaprazlama

Implementation of Grey Wolf Optimization Algorithm to P-Median Problems

Abstract

In this study, the P-Median problem, which is in the Np-hard problem class, is tried to be solved with the Gray Wolf Optimization (GWO) algorithm. Since the GWO algorithm is proposed for continuous search space, it is not possible to directly apply this algorithm to the P-Median problem, which has a combinatorial structure. For this reason, the GWO algorithm needs to be adapted to operate in the discrete search space. In this process, inspired by the search strategy of the Differential Evolution Algorithm, the crossover technique was used together with the GWO algorithm. First, the uniform crossover technique was utilized in the study. Then, taking into account the parameter in the GWO algorithm, which varies depending on the iteration, a crossover technique called adaptive uniform crossover was created. This proposed algorithm is tested on 40 P-Median problems. When the solutions obtained are compared, it is seen that the adaptive crossover technique gives better results than the uniform crossover technique in all 40 problems. In addition, in order to compare the results obtained using the two crossover techniques numerically, the improvement ratio between the solutions was analyzed. The obtained ratios show that in all 40 problems, the adaptive uniform crossover technique significantly improves the solutions obtained with the uniform crossover technique.

Keywords

Grey Wolf optimization algorithm, NP-hard, P-Median problem, Uniform crossover

References

• F. A. Hashim, E. H. Houssein, K. Hussain, M. S. Mabrouk, and W. Al-Atabany, Honey badger algorithm: new metaheuristic algorithm for solving optimization problems, Mathematics and Computers in Simulation. 192 (2021), 84–110.
• M. Hacıbeyoğlu, M. Çelik and Ö. Erdaş Çiçek, Energy efficiency estimation in buildings with k nearest neighbor algorithm, Necmettin Erbakan University Journal of Science and Engineering. 5 (2) (2023), 65-74.
• Ö. İnik, E. Ülker, Derin öğrenme ve görüntü analizinde kullanılan derin öğrenme modelleri, Gaziosmanpaşa Bilimsel Araştırma Dergisi (GBAD). 6 (3) (2017), 85-104.
• D. S. Hochbaum, Approximation Algorithms for NP-Hard Problems. PWS Publishing Company, 1997.
• J. Kennedy and R. Eberhart, Particle Swarm Optimization, Proceedings of ICNN'95- International Conference on Neural Networks, Perth, WA, Australia, 1995, 1942-1948.
• Karaboğa Derviş, An ıdea based on honey bee swarm for numerical optimization, Technical Report-tr06. 200 (2005), 1-10.
• A. Pektaş, O. İnan, Application of tree seed algorithm on clustering problems, Necmettin Erbakan University Journal of Science and Engineering. 4 (1) (2022), 1-10.
• S. Mirjalili and A. Lewis, The whale optimization algorithm, Advances in Engineering Software. 95 (2016), 51–67. doi: 10.1016/j.advengsoft.2016.01.008.
• M. Bastı, P-Medyan tesis yeri seçim problemi ve çözüm yaklaşımları, AJIT-e: Online Academic Journal of Information Technology. 3 (7) (2012), 47-75. doi: 10.5824/1309-1581.2012.2.004.x.
• M. Bastı, Kuruluş Yeri Seçimi Probleminin Çözümünde Meta Sezgisel Algoritmalar (Doktora), İstanbul Üniversitesi Sosyal Bilimler Enstitüsü, İşletme Ana Bilim Dalı, İstanbul, 2012.
• M. You, Y. Xiao, S. Zhang, P. Yang, and S. Zhou, Optimal mathematical programming for the warehouse location problem with euclidean distance linearization, Computers & Industrial Engineering. 136, (2019). doi: 10.1016/j.cie.2019.07.020.
• F. B. Özsoydan, T. Saraç, A discrete particle swarm optimization algorithm for bi-criteria warehouse location problem, İstanbul Üniversitesi İktisat Fakültesi Ekonometri ve İstatistik Dergisi. 13 (2011), 114-124.
• A. R. Guner, M. Sevkli, A discrete particle swarm optimization algorithm for uncapacitated facility location problem, Journal of Artificial Evolution and Applications. (2008) doi: 10.1155/2008/861512.
• N. Özçakar, M. Bastı, P-Medyan kuruluş yeri seçim probleminin çözümünde parçacık sürü optimizasyonu algoritması yaklaşımı, İstanbul Üniversitesi İşletme Fakültesi Dergisi. 41 (2) (2012), 241–257.
• A. Kole, P. Chakrabarti, and S. Bhattacharyya, An ant colony optimization algorithm for uncapacitated facility location problem, Artificial Intelligence and Applications. 1 (1) (2014), 55-61.
• E. Baş, E. Ülker, A binary social spider algorithm for uncapacitated facility location problem, Expert Systems with Applications.161 (2020), 1-27.
• M. Karakoyun, A. Özkiş, Development of binary moth-flame optimization algorithms using transfer functions and their performance comparison, Necmettin Erbakan University Journal of Science and Engineering. 3 (2) (2021), 1-10.
• S. L. Hakimi, Optimum distribution of switching centers in a communication network and some related graph theoretic problems, Operations Research. 13 (3) (1965), 462-474.
• O. Kariv and S. L. Hakimi, An Algorithmic approach to network location problems, I: the p-centers, SIAM Journal on Applied Mathematics. 37 (3) (1979), 513-538.
• A. H. B. Anuar, M.F.M. Said, Floyd’s shortest-path algorithm theory, Journal of Advanced Computing Research. 1(1) (2016), 20-21.
• S. Mirjalili, S. M. Mirjalili, and A. Lewis, Grey wolf optimizer, Advances in Engineering Software. 69 (2014), 46–61. doi: 10.1016/j.advengsoft.2013.12.007.