Çok boyutlu sırt çantası problemi için adaptif ikili yapay arı kolonisi algoritması (AİYAK)

Durgut, Rafet; Aydin, Mehmet

doi:10.17341/gazimmfd.804858

Çok boyutlu sırt çantası problemi için adaptif ikili yapay arı kolonisi algoritması (AİYAK)

Rafet Durgut, (Karabük Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümü, Karabük, Türkiye)

Mehmet AYDİN (University of the West of England, Computer Science and Creative Technologies, Bristol, UK)

Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi

4 2

Yıl: 2021 Cilt: 36 Sayı: 4 Sayfa Aralığı: 2333 - 2348 Metin Dili: Türkçe DOI: 10.17341/gazimmfd.804858 İndeks Tarihi: 29-07-2022

Çok boyutlu sırt çantası problemi için adaptif ikili yapay arı kolonisi algoritması (AİYAK)

Öz:

Optimizasyon algoritmalarının etkinlik ve verimliliği çözüm uzayında aktif arama/keşif ve hızlı hareket etme kabiliyetlerine bağlıdır. Bir algoritmada “arama” ve “kullanma” kabiliyetleri kullanılan komşuluk operatörleri ile doğrudan ilgilidir. Bu kabiliyetleri arttırmak için birden fazla komşuluk operatörü arama süreci içerisinde dâhil edilebilir. Bu çalışmadan çok boyutlu sırt çantası probleminin çözümü için üç adet komşuluk operatörü içeren adaptif ikili yapay arı kolonisi kullanımı önerilmiştir. Çok boyutlu sırt çantası problemi birçok uygulama alanına sahip olan bir NP-zor problemdir. Özellikle büyük boyutlu problem örneklerinin makul sürelerde çözülmesi oldukça güçtür. Önerilen algoritmaya ait en iyi parametre yapılanmasının belirlenmesi için ilk olarak parametre ayarlama deneysel çalışmaları gerçekleştirilmiştir. Önerilen algoritmanın başarısı ve literatürdeki dört farklı yöntem ile üç farklı problem kümesi üzerinde istatistiksel karşılaştırmaları yapılmıştır. Önerilen algoritmanın literatürdeki diğer yöntemlerden daha başarılı sonuçlar ürettiği gösterilmiştir.

Anahtar Kelime: Adaptif YAK Sırt çantası problemi İkili YAK Yapay Arı Kolonisi

Adaptive binary artificial bee colony for multi-dimensional knapsack problem

Öz:

The efficiency and effectiveness of metaheuristic optimization algorithms is managed with diverse search and fast approximation in the solution space. A balanced "exploration" and "exploitation" capability is required to achieve by the neighborhood operators towards the aimed efficiency. The majority of metaheuristic algorithms use either single operator or limited to genetic operators, which impose serious boundaries upon performance. In order to avoid this limitation, multiple neighborhood operators can be used within the search process orchestrated by a selection scheme. In this study, an adaptive operator selection scheme is studied with multiple binary operators embedded within artificial bee colony algorithm to solve the multidimensional knapsack problem (MKP) as a renown NP-Hard combinatorial problem. It is implemented for modelling and solving many real-world problems, while it is not trivial to offer a good solution within a reasonable timeframe. A parametric study has been conducted for the approach proposed in this study. The success of the proposed approach has been demonstrated and discussed with comparative analysis using three different classes of benchmark problem sets.

Anahtar Kelime:

Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık

1. Fausto, F., Reyna-Orta, A., Cuevas, E., Andrade, Á. G., Perez-Cisneros, M., From ants to whales: metaheuristics for all tastes, Artificial Intelligence Review, 53 (1), 753- 810, 2020.
2. Mirjalili, S., Lewis, A., The whale optimization algorithm, Advances in engineering software, 95, 51-67, 2016.
3. Whitley, D., A genetic algorithm tutorial, Statistics and computing, 4 (2), 65-85, 1994.
4. Kennedy, J., Eberhart, R., Particle swarm optimization. In Proceedings of ICNN'95-International Conference on Neural Networks, 4, 1942-1948,1995.
5. Karaboga, D., Basturk, B., On the performance of artificial bee colony (ABC) algorithm. Applied soft computing, 8 (1), 687-697, 2008.
6. Price, K., Storn, R. M., Lampinen, J. A., Differential evolution: a practical approach to global optimization, Springer Science & Business Media, 2006.
7. Hussain, K., Salleh, M. N. M., Cheng, S., Shi, Y., Metaheuristic research: a comprehensive survey. Artificial Intelligence Review, 52 (4), 2191-2233, 2019.
8. Garip Z , Çimen M., Boz A., Comparative performance analysis on parameter extraction of solar cell models using meta-heuristic algorithms, Journal of the Faculty of Engineering and Architecture of Gazi University, 36 (2), 1133-1144, 2021.
9. Siarry, P., Metaheuristics, Springer International Publishing, 2016.
10. Sergeyev, Y. D., Kvasov, D. E., Mukhametzhanov, M. S., On the efficiency of nature-inspired metaheuristics in expensive global optimization with limited budget. Scientific reports, 8 (1), 1-9, 2018.
11. Morales-Castañeda, B., Zaldivar, D., Cuevas, E., Fausto, F., Rodríguez, A., A better balance in metaheuristic algorithms: Does it exist?. Swarm and Evolutionary Computation, 54, 100671. 2020
12. Karaboga, D., An idea based on honey bee swarm for numerical optimization, Technical report-tr06, Erciyes university, engineering faculty, computer engineering department, 200, 1-10, 2005.
13. Öztürk C., Hançer E., Karaboğa D., Automatic Clustering with Global Best Artificial Bee Colony Algorithm, Journal of the Faculty of Engineering and Architecture of Gazi University, 29 (4), 677-687, 2014.
14. Wang, H., Wang, W., Xiao, S., Cui, Z., Xu, M., Zhou, X. . Improving Artificial Bee Colony Algorithm Using a New Neighborhood Selection Mechanism. Information Sciences, 527, 227-240 2020.
15. Xue, Y., Jiang, J., Zhao, B., Ma, T., A self-adaptive artificial bee colony algorithm based on global best for global optimization. Soft Computing, 22 (9), 2935- 2952, 2018.
16. Yurtkuran, A., Emel, E., An adaptive artificial bee colony algorithm for global optimization. Applied Mathematics and Computation, 271, 1004-1023, 2015.
17. Babaoglu, I., Artificial bee colony algorithm with distribution-based update rule. Applied Soft Computing, 34, 851-861, 2015.
18. Cengiz M., Çomak E., A solution of some commonly used optimization functions by a hybrid BFGS-PSO algorithm, Journal of the Faculty of Engineering and Architecture of Gazi University, 36 (2) , 925-938, 2021.
19. Gao, W., Liu, S., Huang, L., A global best artificial bee colony algorithm for global optimization. Journal of Computational and Applied Mathematics, 236 (11), 2741-2753, 2012.
20. Bansal, J. C., Joshi, S. K., Sharma, H., Modified global best artificial bee colony for constrained optimization problems. Computers & Electrical Engineering, 67, 365-382, 2018.
21. Gao, W., Liu, S., Improved artificial bee colony algorithm for global optimization. Information Processing Letters, 111 (17), 871-882, 2011.
22. Gao, W. F., Liu, S. Y., A modified artificial bee colony algorithm. Computers & Operations Research, 39 (3), 687-697, 2012.
23. Kiran, M. S., Hakli, H., Gunduz, M., Uguz, H., Artificial bee colony algorithm with variable search strategy for continuous optimization. Information Sciences, 300, 140-157, 2015.
24. Durgut, R., Yavuz, İ. B., Aydın, M. E., Küme Birleşimli Sırt Çantası Probleminin Adaptif Yapay Arı Kolonisi Algoritması ile Çözümü, Journal of Intelligent Systems: Theory and Applications, 4 (1), 43-54, 2021.
25. Cui, L., Li, G., Wang, X., Lin, Q., Chen, J., Lu, N., Lu, J., A ranking-based adaptive artificial bee colony algorithm for global numerical optimization. Information Sciences, 417, 169-185, 2017.
26. Li, K., Fialho, A., Kwong, S., Zhang, Q., Adaptive operator selection with bandits for a multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation, 18 (1), 114- 130, 2013.
27. Fialho, Á., Da Costa, L., Schoenauer, M., Sebag, M., Extreme value based adaptive operator selection. In International Conference on Parallel Problem Solving from Nature, Springer, Berlin, Heidelberg, 175-184, 2008.
28. Durgut, R., Aydin, M. E., Adaptive binary artificial bee colony algorithm, Applied Soft Computing, 101, 107054, 2021.
29. Pirkul, H., An integer programming model for the allocation of databases in a distributed computer system. European Journal of Operational Research, 26 (3), 401- 411, 1986.
30. Martello, S., Knapsack problems: algorithms and computer implementations. Wiley-Interscience series in discrete mathematics and optimization, 1990.
31. Kellerer, H., Pferschy, U., Pisinger, D., Multidimensional knapsack problems, Knapsack problems, 235-283, Springer, Berlin, Heidelberg, 2004.
32. Engwall, M., Jerbrant, A., The resource allocation syndrome: the prime challenge of multi-project management?. International journal of project management, 21 (6), 403-409, 2003.
33. Shih, W., A branch and bound method for the multiconstraint zero-one knapsack problem. Journal of the Operational Research Society, 30 (4), 369-378, 1979.
34. Puchinger, J., Raidl, G. R., Pferschy, U., The multidimensional knapsack problem: Structure and algorithms. INFORMS Journal on Computing, 22 (2), 250-265, 2010.
35. Balev, S., Yanev, N., Fréville, A., Andonov, R., A dynamic programming based reduction procedure for the multidimensional 0–1 knapsack problem. European Journal of Operational Research, 186 (1), 63-76, 2008.
36. Vimont, Y., Boussier, S., Vasquez, M., Reduced costs propagation in an efficient implicit enumeration for the 01 multidimensional knapsack problem. Journal of Combinatorial Optimization, 15 (2), 165-178, 2008.
37. Ozturk, C., Hancer, E., Karaboga, D., Dynamic clustering with improved binary artificial bee colony algorithm. Applied Soft Computing, 28, 69-80, 2015.
38. Jia, D., Duan, X., Khan, M. K., Binary Artificial Bee Colony optimization using bitwise operation. Computers & Industrial Engineering, 76, 360-365, 2014.
39. Ozturk, C., Hancer, E., Karaboga, D., A novel binary artificial bee colony algorithm based on genetic operators. Information Sciences, 297, 154-170, 2015.
40. Kashan, M. H., Nahavandi, N., Kashan, A. H., DisABC: A new artificial bee colony algorithm for binary optimization. Applied Soft Computing, 12 (1), 342-352, 2012.
41. He, Y., Xie, H., Wong, T. L., Wang, X., A novel binary artificial bee colony algorithm for the set-union knapsack problem. Future Generation Computer Systems, 78, 77-86, 2018.
42. Kiran, M. S., The continuous artificial bee colony algorithm for binary optimization. Applied Soft Computing, 33, 15-23, 2015.
43. Xiang, W. L., Li, Y. Z., He, R. C., Gao, M. X., An, M. Q., A novel artificial bee colony algorithm based on the cosine similarity. Computers & Industrial Engineering, 115, 54-68, 2018.
44. Kiran, M. S., Gündüz, M., XOR-based artificial bee colony algorithm for binary optimization. Turkish Journal of Electrical Engineering & Computer Sciences, 21 (2), 2307-2328, 2013.
45. Durgut, R., Improved binary artificial bee colony algorithm. arXiv preprint arXiv:2003.11641, 2020.
46. Thierens, D. Adaptive strategies for operator allocation, Parameter setting in evolutionary algorithms,77-90, Springer, Berlin, Heidelberg, 2007.
47. Hitomi, N., Selva, D., A classification and comparison of credit assignment strategies in multiobjective adaptive operator selection. IEEE Transactions on Evolutionary Computation, 21 (2), 294-314, 2016.
48. Fialho, Á., Da Costa, L., Schoenauer, M., Sebag, M., Analyzing bandit-based adaptive operator selection mechanisms. Annals of Mathematics and Artificial Intelligence, 60 (1-2), 25-64, 2010.
49. Ezugwu, A. E., Adeleke, O. J., Akinyelu, A. A., Viriri, S., A conceptual comparison of several metaheuristic algorithms on continuous optimisation problems. Neural Computing and Applications, 32 (10), 6207-6251, 2020.
50. Chu, P. C., Beasley, J. E., A genetic algorithm for the multidimensional knapsack problem. Journal of heuristics, 4 (1), 63-86, 1998.
51. Drake, J. H., Ozcan, E. and Burke, E. K., A Case Study of Controlling Crossover in a Selection Hyper-heuristic Framework using the Multidimensional Knapsack Problem. Evolutionary Computation, 24 (1), 113–141, 2016.
52. Queen Mary University of London, MKP Problem Instances, http://www.eecs.qmul.ac.uk/~jdrake/mkp.html, Erişim tarihi Haziran 10, 2020
53. Lai, X., Hao, J. K., Fu, Z. H., Yue, D., Diversitypreserving quantum particle swarm optimization for the multidimensional knapsack problem. Expert Systems with Applications, 149, 113310, 2020.
54. Laabadi, S., Naimi, M., El Amri, H., Achchab, B. The 0/1 multidimensional knapsack problem and its variants: a survey of practical models and heuristic approaches. American Journal of Operations Research, 8 (05), 395, 2018
55. Glover, F., Kochenberger, G. A. Critical event tabu search for multidimensional knapsack problems. In Meta-heuristics, Springer, Boston, MA, 407-427, 1996.
56. Khemakhem, M., Haddar, B., Chebil, K., Hanafi, S., A filter-and-fan metaheuristic for the 0-1 multidimensional knapsack problem. International Journal of Applied Metaheuristic Computing (IJAMC), 3 (4), 43-63, 2012.
57. Drexl, A., A simulated annealing approach to the multiconstraint zero-one knapsack problem. Computing, 40 (1), 1-8, 1988.
58. Angelelli, E., Mansini, R., Speranza, M.G., Kernel search: A general heuristic for the multi-dimensional knapsack problem, Computers & Operations Research, 37 (11), 2017-2026, 2010.
59. Chih, M., Self-adaptive check and repair operator-based particle swarm optimization for the multidimensional knapsack problem, Applied Soft Computing, 26, 378- 389, 2015.
60. Lin, C. J., Chern, M. S., Chih, M., A binary particle swarm optimization based on the surrogate information with proportional acceleration coefficients for the 0-1 multidimensional knapsack problem, Journal of Industrial and Production Engineering, 33 (2), 77-102, 2016.
61. Drake, J. H., Özcan, E., Burke, E. K., A case study of controlling crossover in a selection hyper-heuristic framework using the multidimensional knapsack problem. Evolutionary computation, 24 (1), 113-141, 2016.
62. Lai, X., Hao, J. K., Glover, F., Lü, Z., A two-phase tabuevolutionary algorithm for the 0–1 multidimensional knapsack problem. Information Sciences, 436, 282-301, 2018.
63. Al-Shihabi, S., Ólafsson, S., A hybrid of nested partition, binary ant system, and linear programming for the multidimensional knapsack problem. Computers & Operations Research, 37 (2), 247-255, 2010.
64. Zhang, B., Pan, Q. K., Zhang, X. L., Duan, P. Y., An effective hybrid harmony search-based algorithm for solving multidimensional knapsack problems. Applied Soft Computing, 29, 288-297, 2015.
65. Wang, L., Zheng, X. L., Wang, S. Y., A novel binary fruit fly optimization algorithm for solving the multidimensional knapsack problem. Knowledge-Based Systems, 48, 17-23, 2013.
66. García, J., Maureira, C., A KNN quantum cuckoo search algorithm applied to the multidimensional knapsack problem. Applied Soft Computing, 102, 107077, 2021.
67. García, J., Lalla-Ruiz, E., Voss, S., Droguett, E. L., Enhancing a machine learning binarization framework by perturbation operators: analysis on the multidimensional knapsack problem. International Journal of Machine Learning and Cybernetics, 1-20, 2020.
68. Garcia, J., Moraga, P., Valenzuela, M., Pinto, H., A dbscan hybrid algorithm: an application to the multidimensional knapsack problem. Mathematics, 8 (4), 507, 2020.
69. Luo, K., Zhao, Q., A binary grey wolf optimizer for the multidimensional knapsack problem. Applied Soft Computing, 83, 105645, 2019.

APA	Durgut R, Aydin M (2021). Çok boyutlu sırt çantası problemi için adaptif ikili yapay arı kolonisi algoritması (AİYAK). , 2333 - 2348. 10.17341/gazimmfd.804858
Chicago	Durgut Rafet,Aydin Mehmet Çok boyutlu sırt çantası problemi için adaptif ikili yapay arı kolonisi algoritması (AİYAK). (2021): 2333 - 2348. 10.17341/gazimmfd.804858
MLA	Durgut Rafet,Aydin Mehmet Çok boyutlu sırt çantası problemi için adaptif ikili yapay arı kolonisi algoritması (AİYAK). , 2021, ss.2333 - 2348. 10.17341/gazimmfd.804858
AMA	Durgut R,Aydin M Çok boyutlu sırt çantası problemi için adaptif ikili yapay arı kolonisi algoritması (AİYAK). . 2021; 2333 - 2348. 10.17341/gazimmfd.804858
Vancouver	Durgut R,Aydin M Çok boyutlu sırt çantası problemi için adaptif ikili yapay arı kolonisi algoritması (AİYAK). . 2021; 2333 - 2348. 10.17341/gazimmfd.804858
IEEE	Durgut R,Aydin M "Çok boyutlu sırt çantası problemi için adaptif ikili yapay arı kolonisi algoritması (AİYAK)." , ss.2333 - 2348, 2021. 10.17341/gazimmfd.804858
ISNAD	Durgut, Rafet - Aydin, Mehmet. "Çok boyutlu sırt çantası problemi için adaptif ikili yapay arı kolonisi algoritması (AİYAK)". (2021), 2333-2348. https://doi.org/10.17341/gazimmfd.804858

APA	Durgut R, Aydin M (2021). Çok boyutlu sırt çantası problemi için adaptif ikili yapay arı kolonisi algoritması (AİYAK). Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 36(4), 2333 - 2348. 10.17341/gazimmfd.804858
Chicago	Durgut Rafet,Aydin Mehmet Çok boyutlu sırt çantası problemi için adaptif ikili yapay arı kolonisi algoritması (AİYAK). Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 36, no.4 (2021): 2333 - 2348. 10.17341/gazimmfd.804858
MLA	Durgut Rafet,Aydin Mehmet Çok boyutlu sırt çantası problemi için adaptif ikili yapay arı kolonisi algoritması (AİYAK). Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, vol.36, no.4, 2021, ss.2333 - 2348. 10.17341/gazimmfd.804858
AMA	Durgut R,Aydin M Çok boyutlu sırt çantası problemi için adaptif ikili yapay arı kolonisi algoritması (AİYAK). Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi. 2021; 36(4): 2333 - 2348. 10.17341/gazimmfd.804858
Vancouver	Durgut R,Aydin M Çok boyutlu sırt çantası problemi için adaptif ikili yapay arı kolonisi algoritması (AİYAK). Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi. 2021; 36(4): 2333 - 2348. 10.17341/gazimmfd.804858
IEEE	Durgut R,Aydin M "Çok boyutlu sırt çantası problemi için adaptif ikili yapay arı kolonisi algoritması (AİYAK)." Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 36, ss.2333 - 2348, 2021. 10.17341/gazimmfd.804858
ISNAD	Durgut, Rafet - Aydin, Mehmet. "Çok boyutlu sırt çantası problemi için adaptif ikili yapay arı kolonisi algoritması (AİYAK)". Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 36/4 (2021), 2333-2348. https://doi.org/10.17341/gazimmfd.804858