Binary Honey Badger Algorithm for 0-1 Knapsack Problem

Öz

Honey Badger Algorithm (HBA) is one of the recently proposed optimization techniques inspired by the foraging behavior of honey badger. Although it has been successfully applied in solving continuous problems, the algorithm cannot be implemented directly in binary problems. A binary version of HBA is proposed in this study for the 0-1 Knapsack Problem (0-1 KP). To adapt the binary version of HBA, V- Shaped, S-Shaped, U-Shaped, T-Shaped, Tangent Sigmoid, O-Shaped, and Z-Shaped transfer functions are used. Each transfer function was tested by computational experiments over 25 instances of 0-1 KP and compared results. According to the results obtained, it was observed that O1 was the best TF among 25 TFs. In addition, the proposed algorithm was compared with three different binary variants, such as BPSO, MBPSO, and NGHS. Experimental results and comparison show that the proposed method is a promising and alternative algorithm for 0-1 KP problems.

Anahtar Kelimeler

• Binary Honey Badger Algorithm
• 0-1 Knapsack Problems
• Transfer Functions
• Binary Optimization

0-1 Sırt Çantası Problemi İçin İkili Bal Porsuğu Algoritması

Öz

Bal Porsuğu Algoritması (HBA), son zamanlarda önerilen optimizasyon tekniklerinden biridir ve bal porsuğunun yiyecek arama davranışından esinlenmiştir. Sürekli problemlerin çözümünde başarılı bir şekilde uygulanmasına rağmen, algoritma doğrudan ikili problemlerde uygulanamaz. Bu çalışmada 0-1 Sırt Çantası Problemi (0-1 KP) için HBA’nın ikili versiyonu önerilmiştir. HBA’nın ikili versiyonunu uyarlamak için V-Şekilli, S-Şekilli, U-Şekilli, T-Şekilli, Tanjant Sigmoid, O-Şekilli, Z-Şekilli transfer fonksiyonları (TF) kullanılmaktadır. Her transfer fonksiyonu 25 0-1 KP problemi için test edilmiş ve sonuçlar karşılaştırılmıştır. Elde edilen sonuçlara göre 25 TF arasından en iyi TF’nin O1 olduğu görülmüştür. Ayrıca bu algoritma BPSO, MBPSO, NGHS gibi üç farklı ikili varyant ile karşılaştırılmıştır. Deneysel sonuçlar ve karşılaştırmalar önerilen yöntemin 0-1 KP problemleri için umut verici ve alternatif bir araç olduğunu göstermektedir.

Anahtar Kelimeler

• İkili Bal Porsuğu Algoritması
• 0-1 Sırt Çantası Problemleri
• Transfer Fonksiyonları
• İkili Optimizasyon

Kaynakça

1. Abdel-Basset, M. et al., 2021. New binary marine predators optimization algorithms for 0-1 knapsack problems. Computers and Industrial Engineering, 151.
2. Abdel-Basset, M., El-Shahat, D. and El-Henawy, I., 2019. Solving 0-1 knapsack problem by binary flower pollination algorithm. Neural Computing and Applications, 31(9), pp. 5477-5495.
3. Abdel-Basset, M., El-Shahat, D. and 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(3), pp. 495-514.
4. Abdel-Basset, M., Mohamed, R. and Mirjalili, S., 2021. A binary equilibrium optimization algorithm for 0-1 knapsack problems. Computers and Industrial Engineering, 151.
5. Abdollahzadeh, B. et al., 2021. An enhanced binary slime mould algorithm for solving the 0-1 knapsack problem. Engineering with Computers.
6. Ali, I.M., Essam, D. and Kasmarik, K., 2021. Novel binary differential evolution algorithm for knapsack problems. Information Sciences, 542, pp. 177-194.
7. Bansal, J.C. and Deep, K., 2012. A modified binary particle swarm optimization for knapsack problems. Applied Mathematics and Computation, 218(22), pp. 11042-11061.
8. Costa, M.F.P. et al., 2014. Heuristic-based firefly algorithm for bound constrained nonlinear binary optimization. Advances in Operations Research, 2014.

9. Çerçevik, A.E. and Avşar, Ö., 2020. Optimization of linear seismic isolation parameters via crow search algorithm. Pamukkale University Journal of Engineering Sciences, 26(3), pp. 440-447.
10. Dantzig, G.B., 1957. Discrete-Variable Extremum Problems, Source: Operations Research.
11. Deng, W., Xu, J. and Zhao, H., 2019. An improved ant colony optimization algorithm based on hybrid strategies for scheduling problem. IEEE Access, 7, pp. 20281-20292.
12. Ezugwu, A.E. et al., 2019. A comparative study of meta-heuristic optimization algorithms for 0-1 knapsack problem: some initial results. IEEE Access, 7, pp. 43979-44001.
13. Feng, Y. et al., 2017. Solving 0-1 knapsack problem by a novel binary monarch butterfly optimization. Neural Computing and Applications, 28(7), pp. 1619-1634.
14. Gherboudj, A., Layeb, A. and Chikhi, S., 2012. Solving 0-1 knapsack problems by a discrete binary version of cuckoo search algorithm. International Journal of Bio-Inspired Computation, 4(4), pp. 229-236.
15. Guo, S.S. et al., 2020. Z-shaped transfer functions for binary particle swarm optimization algorithm. Computational Intelligence and Neuroscience, 2020.
16. Hakli, H., 2019. A new approach for wind turbine placement problem using modified differential evolution algorithm. Turkish Journal of Electrical Engineering and Computer Sciences, 27(6), pp. 4659-4672.
17. Hakli, H., 2020. BinEHO: a new binary variant based on elephant herding optimization algorithm. Neural Computing and Applications, 32(22), pp. 16971-16991.
18. Halat, M. and Ozkan, O., 2021. The optimization of UAV routing problem with a genetic algorithm to observe the damages of possible Istanbul earthquake. Pamukkale University Journal of Engineering Sciences, 27(2), pp. 187-198.
19. Harifi, S., 2022. A binary ancient-inspired Giza pyramids construction metaheuristic algorithm for solving 0-1 knapsack problem. Application of Soft Computing.
20. Hashim, F.A. et al., 2022. Honey Badger Algorithm: New metaheuristic algorithm for solving optimization problems. Mathematics and Computers in Simulation, 192, pp. 84-110.
21. He, Y. et al., 2022. Novel binary differential evolution algorithm based on taper-shaped transfer functions for binary optimization problems. Swarm and Evolutionary Computation, 69.
22. Ismail M. Ali, D.E. and K.K., 2018. An efficient differential evolution algorithm for solving 0-1 knapsack problems. 2018 IEEE Congress on Evolutionary Computation (CEC): 2018 proceedings.
23. J. Kennedy, R.C.E., 1997. Discrete binary version of the particle swarm algorithm. Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, 5 (1997) 4104-4108. IEEE.
24. Kaya, S. et al., 2020. The effects of initial populations in the solution of flow shop scheduling problems by hybrid firefly and particle swarm optimization algorithms. Pamukkale University Journal of Engineering Sciences, 26(1), pp. 140-149.
25. Kulkarni, A.J. and Shabir, H., 2016. Solving 0-1 knapsack problem using cohort intelligence algorithm. International Journal of Machine Learning and Cybernetics, 7(3), pp. 427-441.
26. Liu, K. et al., 2022. A hybrid harmony search algorithm with distribution estimation for solving the 0-1 knapsack problem. Mathematical Problems in Engineering.
27. Mirjalili, S. and Lewis, A., 2013. S-shaped versus V-shaped transfer functions for binary particle swarm optimization. Swarm and Evolutionary Computation, 9, pp. 1-14.
28. Mirjalili, Seyedehzahra et al., 2020. A novel U-shaped transfer function for binary particle swarm optimisation. Advances in Intelligent Systems and Computing. Springer, pp. 241-259.
29. Nguyen, P.H., Wang, D. and Truong, T.K., 2017. A novel binary social spider algorithm for 0-1 knapsack problem. International Journal of Innovative Computing.
30. Pampará, G. and Engelbrecht, A.P., 2011. Binary artificial bee colony optimization. IEEE SSCI 2011- Symposium Series on Computational Intelligence- SIS 2011: 2011 IEEE Symposium on Swarm Intelligence, pp. 170-177.
31. Pavithr, R.S. and Gursaran, 2016. Quantum inspired social evolution (QSE) algorithm for 0-1 knapsack problem. Swarm and Evolutionary Computation, 29, pp. 33-46.
32. Rizk-Allah, R.M. and Hassanien, A.E., 2018. New binary bat algorithm for solving 0-1 knapsack problem. Complex & Intelligent Systems, 4(1), pp. 31-53.
33. Rooderkerk, R.P. and van Heerde, H.J., 2016. Robust optimization of the 0-1 knapsack problem: Balancing risk and return in assortment optimization. European Journal of Operational Research, 250(3), pp. 842-854.
34. Shu, Z. et al., 2022. A modified hybrid rice optimization algorithm for solving 0-1 knapsack problem. Applied Intelligence, 52(5), pp. 5751-5769.
35. Wang, L. et al., 2008. A novel probability binary particle swarm optimization algorithm and its application.
36. Wang, L., Shi, R. and Dong, J., 2021. A hybridization of dragonfly algorithm optimization and angle modulation mechanism for 0‐1 knapsack problems. Entropy, 23(5).
37. Yassien, E. et al., 2017. Grey wolf optimization applied to the 0/1 knapsack problem. International Journal of Computer Applications, 169(5), pp. 11-15.
38. Yonaba, H., Anctil, F. and Fortin, V., 2010. Comparing sigmoid transfer functions for neural network multistep ahead streamflow forecasting. Journal of Hydrologic Engineering, 15(4), pp. 275-283.
39. Zhou, Y., Chen, X. and Zhou, G., 2016. An improved monkey algorithm for a 0-1 knapsack problem. Applied Soft Computing Journal, 38, pp. 817-830.
40. Zhou, Y., Li, L. and Ma, M., 2016. A complex-valued encoding bat algorithm for solving 0-1 knapsack problem. Neural Processing Letters, 44(2), pp. 407-430.
41. Zhu, H. et al., 2017. Discrete differential evolutions for the discounted {0-1} knapsack problem. Chinese Journal of Computers and so on.