İkili Bal Porsuğu Algoritmasının Küme Birleşimli Sırt Çantası Problemine Uygulanması

Abstract

NP-zor problem sınıfından olan küme birleşimli sırt çantası (KBSÇ) problemi, 0-1 sırt çantası probleminin (0-1 KP) genelleştirilmiş halidir. Literatürde bu problem çeşitli sezgisel yaklaşımlar ile çözülmüş olmasına rağmen, çözüm kalitesinin iyileştirilmesi devam etmektedir. Son zamanlarda önerilmiş olan Bal Porsuğu Algoritması (Honey Badger Algorithm (HBA)) sürekli problemleri çözmek için tasarlanmıştır. Bu çalışmada ikili yapıya sahip olan küme birleşimli sırt çantası problemine, transfer fonksiyonları yardımıyla ikili yapıya uyarlanan BPA algoritması uygulanmıştır. Transfer fonksiyonları olarak kullanılan S-şekilli, V-şekilli, U-şekilli, Taper-şekilli transfer fonksiyonları ile elde edilen sonuçlar karşılaştırılmıştır. Çözümlerin iyileştirilmesi için onarım algoritması ve onarım algoritması ile birlikte iyileştirme algoritması kullanılmıştır.

Keywords

• Küme birleşimli sırt çantası problemi
• Bal porsuğu algoritması
• Transfer fonksiyonları
• İkili optimizasyon

References

1. [1] H. Kellerer, U. Pferschy, and D. Pisinger, “Multidimensional knapsack problems,” Knapsack Problems, pp. 235–283, 2004.
2. [2] O. Goldschmidt, D. Nehme, and G. Yu, “Note: on the set‐union knapsack problem,” Naval Research Logistics (NRL), vol. 41, no. 6, pp. 833–842, 1994.
3. [3] A. Arulselvan, “A note on the set union knapsack problem,” Discrete Appl Math, vol. 169, pp. 214–218, 2014.
4. [4] J. C. Bansal and K. Deep, “A modified binary particle swarm optimization for knapsack problems,” Appl Math Comput, vol. 218, no. 22, pp. 11042–11061, Jul. 2012.
5. [5] S. Navathe, S. Ceri, G. Wiederhold, and J. Dou, Vertical Partitioning Algorithms for Database Design, pp. 680–710, 1984.
6. [6] C. S. Tang and E. v. Denardo, “Models arising from a flexible manufacturing machine, part II: minimization of the number of switching instants,” Operations Research, vol. 36, no. 5, pp. 778–784, Oct. 1988.
7. [7] M. Tu and L. Xiao, “System resilience enhancement through modularization for large scale cyber systems,” in 2016 IEEE/CIC International Conference on Communications in China (ICCC Workshops), 2016, pp. 1-6.
8. [8] X. Yang, A. Vernitski, and L. Carrea, “An approximate dynamic programming approach for improving accuracy of lossy data compression by bloom filters,” Eur J Oper Res, vol. 252, no. 3, pp. 985–994, 2016.

9. [9] Y. Feng, H. An, and X. Gao, “The importance of transfer function in solving set-union knapsack problem based on discrete moth search algorithm,” Mathematics, vol. 7, no. 1, 2018.
10. [10] G. Pampara, N. Franken, and A. P. Engelbrecht, “Combining particle swarm optimisation with angle modulation to solve binary problems,” in 2005 IEEE Congress on Evolutionary Computation, IEEE CEC, 2005, vol. 1, pp. 89–96.
11. [11] H. Nezamabadi-Pour, “A quantum-inspired gravitational search algorithm for binary encoded optimization problems,” Eng Appl Artif Intell, vol. 40, pp. 62–75, Apr. 2015.
12. [12] Y. He, H. Xie, T. L. Wong, and X. Wang, “A novel binary artificial bee colony algorithm for the set-union knapsack problem,” Future Generation Computer Systems, vol. 78, pp. 77–86, Jan. 2018.
13. [13] F. B. Ozsoydan and A. Baykasoglu, “A swarm intelligence-based algorithm for the set-union knapsack problem,” Future Generation Computer Systems, vol. 93, pp. 560–569, Apr. 2019.
14. [14] G. Lin, J. Guan, Z. Li, and H. Feng, “A hybrid binary particle swarm optimization with tabu search for the set-union knapsack problem,” Expert Syst Appl, vol. 135, pp. 201–211, Nov. 2019.
15. [15] Z. Wei and J. K. Hao, “Iterated two-phase local search for the set-union knapsack problem,” Future Generation Computer Systems, vol. 101, pp. 1005–1017, Dec. 2019.
16. [16] Y. Feng, J. H. Yi, and G. G. Wang, “Enhanced moth search algorithm for the set-union knapsack problems,” IEEE Access, vol. 7, pp. 173774–173785, 2019.
17. [17] C. Wu and Y. He, “Solving the set-union knapsack problem by a novel hybrid jaya algorithm,” Soft comput, vol. 24, no. 3, pp. 1883–1902, Feb. 2020.
18. [18] Z. Wei and J. K. Hao, “Multistart solution-based tabu search for the set-union knapsack problem,” Appl Soft Comput, vol. 105, Jul. 2021.
19. [19] Y. He and X. Wang, “Group theory-based optimization algorithm for solving knapsack problems,” Knowl Based Syst, vol. 219, May 2021.
20. [20] Z. Wei and J. K. Hao, “Kernel based tabu search for the set-union knapsack problem,” Expert Syst Appl, vol. 165, Mar. 2021.
21. [21] 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,” Math Comput Simul, vol. 192, pp. 84–110, Feb. 2022.
22. [22] S. Mirjalili and A. Lewis, “S-shaped versus v-shaped transfer functions for binary particle swarm optimization,” Swarm Evol Comput, vol. 9, pp. 1–14, Apr. 2013.
23. [23] S. Mirjalili, H. Zhang, S. Mirjalili, S. Chalup, and N. Noman, “A novel u-shaped transfer function for binary particle swarm optimisation,” in Advances in Intelligent Systems and Computing, vol. 1138, pp. 241–259, 2020.
24. [24] Y. He, F. Zhang, S. Mirjalili, and T. Zhang, “Novel binary differential evolution algorithm based on taper-shaped transfer functions for binary optimization problems,” Swarm Evol Comput, vol. 69, Mar. 2022.