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

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

doi:10.29130/dubited.1205144

TR

İ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] H. Kellerer, U. Pferschy, and D. Pisinger, “Multidimensional knapsack problems,” Knapsack Problems, pp. 235–283, 2004.
[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] A. Arulselvan, “A note on the set union knapsack problem,” Discrete Appl Math, vol. 169, pp. 214–218, 2014.
[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] S. Navathe, S. Ceri, G. Wiederhold, and J. Dou, Vertical Partitioning Algorithms for Database Design, pp. 680–710, 1984.
[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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] Y. He and X. Wang, “Group theory-based optimization algorithm for solving knapsack problems,” Knowl Based Syst, vol. 219, May 2021.
[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] 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] 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] 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] 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.

Details

Primary Language

Turkish

Subjects

Engineering

Journal Section

Research Article

Authors

Gülşen Orucova Büyüköz ^*
0000-0003-0654-5119
Türkiye

Hüseyin Haklı
0000-0001-5019-071X
Türkiye

Publication Date

April 29, 2024

Submission Date

November 18, 2022

Acceptance Date

July 25, 2023

Published in Issue

Year 2024 Volume: 12 Number: 2

DOI

https://doi.org/10.29130/dubited.1205144

IZ

https://izlik.org/JA58EL45GD

APA

Orucova Büyüköz, G., & Haklı, H. (2024). İkili Bal Porsuğu Algoritmasının Küme Birleşimli Sırt Çantası Problemine Uygulanması. Duzce University Journal of Science and Technology, 12(2), 1075-1085. https://doi.org/10.29130/dubited.1205144

AMA

1.Orucova Büyüköz G, Haklı H. İkili Bal Porsuğu Algoritmasının Küme Birleşimli Sırt Çantası Problemine Uygulanması. DUBİTED. 2024;12(2):1075-1085. doi:10.29130/dubited.1205144

Chicago

Orucova Büyüköz, Gülşen, and Hüseyin Haklı. 2024. “İkili Bal Porsuğu Algoritmasının Küme Birleşimli Sırt Çantası Problemine Uygulanması”. Duzce University Journal of Science and Technology 12 (2): 1075-85. https://doi.org/10.29130/dubited.1205144.

EndNote

Orucova Büyüköz G, Haklı H (April 1, 2024) İkili Bal Porsuğu Algoritmasının Küme Birleşimli Sırt Çantası Problemine Uygulanması. Duzce University Journal of Science and Technology 12 2 1075–1085.

IEEE

[1]G. Orucova Büyüköz and H. Haklı, “İkili Bal Porsuğu Algoritmasının Küme Birleşimli Sırt Çantası Problemine Uygulanması”, DUBİTED, vol. 12, no. 2, pp. 1075–1085, Apr. 2024, doi: 10.29130/dubited.1205144.

ISNAD

Orucova Büyüköz, Gülşen - Haklı, Hüseyin. “İkili Bal Porsuğu Algoritmasının Küme Birleşimli Sırt Çantası Problemine Uygulanması”. Duzce University Journal of Science and Technology 12/2 (April 1, 2024): 1075-1085. https://doi.org/10.29130/dubited.1205144.

JAMA

1.Orucova Büyüköz G, Haklı H. İkili Bal Porsuğu Algoritmasının Küme Birleşimli Sırt Çantası Problemine Uygulanması. DUBİTED. 2024;12:1075–1085.

MLA

Orucova Büyüköz, Gülşen, and Hüseyin Haklı. “İkili Bal Porsuğu Algoritmasının Küme Birleşimli Sırt Çantası Problemine Uygulanması”. Duzce University Journal of Science and Technology, vol. 12, no. 2, Apr. 2024, pp. 1075-8, doi:10.29130/dubited.1205144.

Vancouver

1.Gülşen Orucova Büyüköz, Hüseyin Haklı. İkili Bal Porsuğu Algoritmasının Küme Birleşimli Sırt Çantası Problemine Uygulanması. DUBİTED. 2024 Apr. 1;12(2):1075-8. doi:10.29130/dubited.1205144

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

Abstract

Keywords

Abstract

Keywords

References

Details

Primary Language

Subjects

Journal Section

Authors

Publication Date

Submission Date

Acceptance Date

Published in Issue

DOI

IZ

Cite