INVESTIGATION OF TRANSFER FUNCTIONS ON A NOVEL BINARY DRIVING TRAINING-BASED ALGORITHM

Abstract

Uncapacitated Facility Location Problem (UFLP) is an NP-hard problem that determines the optimal location of facilities. Since UFLP is from the NP-Hard problem group, using exact methods to solve large instances of these problems can be seriously problematic due to the high computation time required to obtain the optimal solution. In this study, the swarm intelligence algorithm was preferred due to the complexity of the problem. Driving training-based (DTBO) algorithm, which is a population-based algorithm developed based on driving training principles in recent years, has been used to solve the UFLP problem. Since the basic version of DTBO deals with the solution of continuous problems, the corresponding algorithm needs to be adapted to the solution of binary problems. For this, the DTBO algorithm was designed in accordance with the solution of binary problems with the help of nine different transfer functions used in the literature. Experimental studies were carried out under equal conditions for fair comparison of transfer functions. In the experimental studies carried out, it is seen that the binary Mode-DTBO algorithm is the most successful algorithm among the nine transfer functions. According to these results, it is seen that the binary Mode-based DTBO algorithm is very successful in all small, medium and large scaled problem sets, both in terms of solution quality and time. In addition, the DTBO algorithm was compared with 3 different transfer functions (Mode, Sigmoid and Tanh) of the IWO (Invasive Weed Optimization) algorithm. When the comparative results were examined, it was seen that the Mode-DTBO approach was much more successful than all 3 different approaches of IWO in 8 of the 12 problems (medium and large-scale problems). On the other hand, it has been observed that both algorithms using the Mode function on 4 small-sized problems achieved the optimal value. As a result, it can be said that the binary Mode-DTBO method will be able to offer a very effective alternative in solving binary problems.

Keywords

• UFLP
• Binary Optimization
• DTBO
• Transfer Function

YENİ BİR İKİLİ SÜRÜŞ EĞİTİM TABANLI ALGORİTMA ÜZERİNDE TRANSFER FONKSİYONLARININ İNCELENMESİ

Abstract

Kapasitesiz Tesis Yerleşim Problemi (UFLP), tesislerin optimal yerleşimini belirleyen NP-zor bir problemdir. UFLP, NP-Zor problem grubundan olduğu için, bu problemlerin büyük örneklerini çözmek için kesin yöntemlerin kullanılması, optimal çözümü elde etmek için gereken yüksek hesaplama süreleri nedeniyle ciddi şekilde sorun teşkil edebilir. Bu çalışmada, problemin karmaşıklığından dolayı sürü zekası algoritması tercih edilmiştir. Son yıllarda sürüş eğitimi ilkelerine dayalı olarak geliştirilen popülasyon tabanlı bir algoritma olan Sürüş eğitim tabanlı (DTBO) algoritması UFLP probleminin çözümünde kullanılmıştır. DTBO’nun temel versiyonu sürekli problemlerin çözümünü ele aldığından söz konusu algoritmanın ikili problemlerin çözümüne uyarlanması gerekmektedir. Bunun için literatürde kullanılan dokuz farklı transfer fonksiyonu yardımıyla DTBO algoritması ikili problemlerin çözümüne uygun olarak tasarlanmıştır. Deneysel çalışmalar transfer fonksiyonlarının adil kıyaslanabilmesi için eşit koşullarda altında gerçekleştirilmiştir. Gerçekleştirilen deneysel çalışmalarda dokuz transfer fonksiyonu içerisinden ikili Mode-DTBO algoritmasının en başarılı algoritma olduğu görülmektedir. Bu sonuçlara göre Mode tabanlı DTBO algoritmasının küçük, orta ve büyük ölçekli tüm problem setlerinde hem çözüm kalitesi açısından hem de zaman açısından çok başarılı olduğu görülmektedir. Ayrıca DTBO algoritması IWO (Yabani Ot Algoritması – Invasive Weed Optimization) algoritmasına ait 3 farklı transfer fonksiyonuyla (Mode, Sigmoid ve Tanh) da kıyaslanmıştır. Karşılaştırmalı sonuçlar incelendiğinde 12 problemin 8’inde (orta ve büyük ölçekli problem) Mode-DTBO yaklaşımının IWO’ya ait 3 farklı yaklaşımın hepsinden çok daha başarılı olduğu görülmüştür. Bununla beraber, küçük boyutlu 4 problem üzerinde ise Mode fonksiyonunu kullanan her iki algoritmanın da optimal değeri yakaladığı görülmüştür. Sonuç olarak, Mode-DTBO yönteminin ikili problemlerin çözümünde çok etkili bir alternatif sunacağı söylenebilir.

Keywords

• UFLP
• İkili Optimizasyon
• DTBO
• Transfer Fonksiyonu

References

1. Abdullahi, I. M., Mu’azu, M. B., Olaniyi, O. M., & Agajo, J., 2020. Pastoralist Optimization Algorithm (POA): A Culture-Inspired Metaheuristic for Uncapacitated Facility Location Problem (UFLP). Paper presented at the International Conference on Hybrid Intelligent Systems.
2. Akan, T., Agahian, S., & Dehkharghani, R., 2022. Battle Royale Optimizer for solving binary optimization problems. Software Impacts, 12, 100274.
3. Alidaee, B., & Wang, H., 2022. Uncapacitated (Facility) Location Problem: A Hybrid Genetic-Tabu Search Approach. IFAC-PapersOnLine, 55(10), 1619-1624.
4. Arafat, M. Y., & Moh, S., 2019. Localization and clustering based on swarm intelligence in UAV networks for emergency communications. IEEE Internet of Things Journal, 6(5), 8958-8976.
5. Aslan, M., Gunduz, M., & Kiran, M. S., 2019. JayaX: Jaya algorithm with xor operator for binary optimization. Applied Soft Computing, 82, 105576.
6. Barcelo, J., Hallefjord, Å., Fernandez, E., & Jörnsten, K., 1990. Lagrangean relaxation and constraint generation procedures for capacitated plant location problems with single sourcing. Operations-Research-Spektrum, 12(2), 79-88.
7. Baş, E., & Ülker, E., 2020. A binary social spider algorithm for uncapacitated facility location problem. Expert Systems with Applications, 161, 113618.
8. Chudak, F. A., & Shmoys, D. B., 2003. Improved approximation algorithms for the uncapacitated facility location problem. SIAM Journal on Computing, 33(1), 1-25.

9. Coniglio, S., Furini, F., & San Segundo, P., 2021. A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts. European Journal of Operational Research, 289(2), 435-455.
10. Dehghani, M., Trojovská, E., & Trojovský, P., 2022. A new human-based metaheuristic algorithm for solving optimization problems on the base of simulation of driving training process. Scientific reports, 12(1), 1-21.
11. Ghosh, D., 2003. Neighborhood search heuristics for the uncapacitated facility location problem. European Journal of Operational Research, 150(1), 150-162.
12. Hakli, H., & Ortacay, Z., 2019. An improved scatter search algorithm for the uncapacitated facility location problem. Computers & Industrial Engineering, 135, 855-867.
13. He, Y., Zhang, F., Mirjalili, S., & Zhang, T., 2022. Novel binary differential evolution algorithm based on Taper-shaped transfer functions for binary optimization problems. Swarm and Evolutionary Computation, 69, 101022.
14. Holmberg, K., 1999. Exact solution methods for uncapacitated location problems with convex transportation costs. European Journal of Operational Research, 114(1), 127-140.
15. Inik, O., Ulker, E., & Koc, I., 2020. B-Spline Curve Approximation by Utilizing Big Bang-Big Crunch Method.
16. Karakoyun, M., & Ozkis, A., 2022. A binary tree seed algorithm with selection-based local search mechanism for huge-sized optimization problems. Applied Soft Computing, 129, 109590.
17. Karakoyun, M., & Özkış, A., 2021, Transfer Fonksiyonları Kullanarak İkili Güve-Alev Optimizasyonu Algoritmalarının Geliştirilmesi ve Performanslarının Karşılaştırılması. Necmettin Erbakan Üniversitesi Fen ve Mühendislik Bilimleri Dergisi, 3(2), 1-10.
18. Kashan, M. H., Nahavandi, N., & Kashan, A. H., 2012. DisABC: a new artificial bee colony algorithm for binary optimization. Applied Soft Computing, 12(1), 342-352.
19. Kaya, E., 2022. BinGSO: galactic swarm optimization powered by binary artificial algae algorithm for solving uncapacitated facility location problems. Neural Computing and Applications, 1-20.
20. Kennedy, J., & Eberhart, R. C., 1997. A discrete binary version of the particle swarm algorithm. Paper presented at the 1997 IEEE International conference on systems, man, and cybernetics. Computational cybernetics and simulation.
21. Koc, I., 2016. Big bang-big crunch optimization algorithm for solving the uncapacitated facility location problem. International Journal of Intelligent Systems and Applications in Engineering, 4(Special Issue-1), 185-189.
22. Koc, I., 2022. A comprehensive analysis of grid-based wind turbine layout using an efficient binary invasive weed optimization algorithm with levy flight. Expert Systems with Applications, 198, 116835.
23. Koc, I., Baykan, O. K., & Babaoglu, I., 2018. Multilevel image thresholding selection based on grey wolf optimizer. Journal Of Polytechnic-Politeknik Dergisi, 21(4), 841-847.
24. Koc, I., Nureddin, R., Babaoglu, I., & Uymaz, S. A., 2017. Binary Invasive Weed Optimization Algorithm Approaches for Binary Optimization.
25. Korkmaz, S., Babalik, A., & Kiran, M. S., 2018. An artificial algae algorithm for solving binary optimization problems. International Journal of Machine Learning and Cybernetics, 9(7), 1233-1247.
26. Lemke, C. E., 1954. The dual method of solving the linear programming problem. Naval Research Logistics Quarterly, 1(1), 36-47.
27. Matos, T., 2021. A Scatter Search Algorithm for the Uncapacitated Facility Location Problem. Paper presented at the International Conference on Intelligent Computing & Optimization.
28. Mirjalili, S., & Lewis, A., 2013. S-shaped versus V-shaped transfer functions for binary particle swarm optimization. Swarm and Evolutionary Computation, 9, 1-14.
29. Prescilla, K., & Selvakumar, A. I., 2013. Modified Binary Particle Swarm optimization algorithm application to real-time task assignment in heterogeneous multiprocessor. Microprocessors and Microsystems, 37(6-7), 583-589.
30. Rashedi, E., Nezamabadi-Pour, H., & Saryazdi, S., 2010. BGSA: binary gravitational search algorithm. Natural computing, 9(3), 727-745.
31. Rizk-Allah, R. M., Hassanien, A. E., Elhoseny, M., & Gunasekaran, M., 2019. A new binary salp swarm algorithm: development and application for optimization tasks. Neural Computing and Applications, 31(5), 1641-1663.
32. Shehu, H., & Olalere, M., 2019. Performance Evaluation of Ant Lion Optimization and Particle Swarm Optimiztion for Uncapacitated Facility Location Problem (UFLP).
33. Sonuç, E., 2021. Binary crow search algorithm for the uncapacitated facility location problem. Neural Computing and Applications, 33(21), 14669-14685.
34. Sudabas, F. T., & Kara, S. S., 2021. Tesis Yeri Seçimi Probleminde Minimum Karbon Emisyonu Yaklaşımı: Bir Üniversitenin Geri Dönüşüm Yönetimi İçin Uygulama. Mühendislik Bilimleri ve Tasarım Dergisi, 9(2), 544-553.
35. Tunç, A., Taşdemir, Ş., & Sağ, T., 2022. Comparison of Heuristic and Metaheuristic Algorithms. Paper presented at the 2022 7th International Conference on Computer Science and Engineering (UBMK).
36. Xiang, W.-l., Li, Y.-z., He, R.-c., & An, M.-q., 2021. Artificial bee colony algorithm with a pure crossover operation for binary optimization. Computers & Industrial Engineering, 152, 107011.
37. Yiğit, V., & Türkbey, O., 2003. Tesis Yerleşim Problemlerine Sezgisel Metotlarla Yaklaşım. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 18(4).
38. Zebari, R., Abdulazeez, A., Zeebaree, D., Zebari, D., & Saeed, J., 2020. A comprehensive review of dimensionality reduction techniques for feature selection and feature extraction. Journal of Applied Science and Technology Trends, 1(2), 56-70.
39. Zhang, F., He, Y., Ouyang, H., & Li, W., 2023. A fast and efficient discrete evolutionary algorithm for the uncapacitated facility location problem. Expert Systems with Applications, 213, 118978.
40. Zhu, K., Ying, S., Zhang, N., & Zhu, D., 2021. Software defect prediction based on enhanced metaheuristic feature selection optimization and a hybrid deep neural network. Journal of Systems and Software, 180, 111026.