Research Article
BibTex RIS Cite

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

Year 2021, Volume: 36 Issue: 4, 2333 - 2348, 02.09.2021

Rafet Durgut Mehmet Aydin

https://doi.org/10.17341/gazimmfd.804858
Cited By: 1

Abstract

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.

Keywords

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

References

  • 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.
  • Mirjalili, S., & Lewis, A., The whale optimization algorithm, Advances in engineering software, 95, 51-67, 2016.
  • Whitley, D., A genetic algorithm tutorial, Statistics and computing, 4(2), 65-85, 1994.
  • Kennedy, J., & Eberhart, R., Particle swarm optimization. In Proceedings of ICNN'95-International Conference on Neural Networks, 4, 1942-1948,1995.
  • Karaboga, D., & Basturk, B., On the performance of artificial bee colony (ABC) algorithm. Applied soft computing, 8(1), 687-697, 2008.
  • Price, K., Storn, R. M., & Lampinen, J. A., Differential evolution: a practical approach to global optimization, Springer Science & Business Media, 2006.
  • Hussain, K., Salleh, M. N. M., Cheng, S., & Shi, Y., Metaheuristic research: a comprehensive survey. Artificial Intelligence Review, 52(4), 2191-2233, 2019.
  • Siarry, P., Metaheuristics, Springer International Publishing, 2016.
  • 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.
  • 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
  • Karaboga, D., An idea based on honey bee swarm for numerical optimization (Vol. 200, 1-10). Technical report-tr06, Erciyes university, engineering faculty, computer engineering department, 2005.
  • Özturk, C., Hancer, E., & Karaboga, D., Küresel en iyi yapay ari koloni algoritmasi ile otomatik kümeleme. Journal of the Faculty of Engineering & Architecture of Gazi University, 29(4), 2014.
  • 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.
  • 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.
  • Yurtkuran, A., & Emel, E., An adaptive artificial bee colony algorithm for global optimization. Applied Mathematics and Computation, 271, 1004-1023, 2015.
  • Babaoglu, I., Artificial bee colony algorithm with distribution-based update rule. Applied Soft Computing, 34, 851-861, 2015.
  • 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.
  • 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.
  • Gao, W., & Liu, S., Improved artificial bee colony algorithm for global optimization. Information Processing Letters, 111(17), 871-882, 2011.
  • Gao, W. F., & Liu, S. Y., A modified artificial bee colony algorithm. Computers & Operations Research, 39(3), 687-697, 2012.
  • 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.
  • 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.
  • 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.
  • Fialho, Á., Da Costa, L., Schoenauer, M., & Sebag, M., Extreme value based adaptive operator selection. In International Conference on Parallel Problem Solving from Nature (pp. 175-184). Springer, Berlin, Heidelberg, 2008.
  • 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.
  • Martello, S., Knapsack problems: algorithms and computer implementations. Wiley-Interscience series in discrete mathematics and optimization, 1990.
  • Kellerer, H., Pferschy, U., & Pisinger, D., Multidimensional knapsack problems, Knapsack problems, 235-283, Springer, Berlin, Heidelberg, 2004.
  • 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.
  • 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.
  • Puchinger, J., Raidl, G. R., & Pferschy, U., The multidimensional knapsack problem: Structure and algorithms. INFORMS Journal on Computing, 22(2), 250-265, 2010.
  • 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.
  • 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.
  • Luo, K., & Zhao, Q., A binary grey wolf optimizer for the multidimensional knapsack problem. Applied Soft Computing, 83, 105645, 2019.
  • Ozturk, C., Hancer, E., & Karaboga, D., Dynamic clustering with improved binary artificial bee colony algorithm. Applied Soft Computing, 28, 69-80, 2015.
  • Jia, D., Duan, X., & Khan, M. K., Binary Artificial Bee Colony optimization using bitwise operation. Computers & Industrial Engineering, 76, 360-365, 2014.
  • Ozturk, C., Hancer, E., & Karaboga, D., A novel binary artificial bee colony algorithm based on genetic operators. Information Sciences, 297, 154-170, 2015.
  • 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.
  • 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.
  • Kiran, M. S., The continuous artificial bee colony algorithm for binary optimization. Applied Soft Computing, 33, 15-23, 2015.
  • 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.
  • Kiran, M. S., & Gündüz, M., XOR-based artificial bee colony algorithm for binary optimization. Turkish Journal of Electrical Engineering & Computer Sciences, 21(Sup. 2), 2307-2328, 2013.
  • Durgut, R., Improved binary artificial bee colony algorithm. arXiv preprint arXiv:2003.11641, 2020.
  • Thierens, D. Adaptive strategies for operator allocation, Parameter setting in evolutionary algorithms,77-90, Springer, Berlin, Heidelberg, 2007.
  • 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.
  • 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.
  • 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.
  • Chu, P. C., & Beasley, J. E., A genetic algorithm for the multidimensional knapsack problem. Journal of heuristics, 4(1), 63-86, 1998.
  • 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.
  • Queen Mary University of London, MKP Problem Instances, http://www.eecs.qmul.ac.uk/~jdrake/mkp.html, Erişim tarihi Haziran 10, 2020

Year 2021, Volume: 36 Issue: 4, 2333 - 2348, 02.09.2021

Rafet Durgut Mehmet Aydin

https://doi.org/10.17341/gazimmfd.804858
Cited By: 1

Abstract

References

  • 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.
  • Mirjalili, S., & Lewis, A., The whale optimization algorithm, Advances in engineering software, 95, 51-67, 2016.
  • Whitley, D., A genetic algorithm tutorial, Statistics and computing, 4(2), 65-85, 1994.
  • Kennedy, J., & Eberhart, R., Particle swarm optimization. In Proceedings of ICNN'95-International Conference on Neural Networks, 4, 1942-1948,1995.
  • Karaboga, D., & Basturk, B., On the performance of artificial bee colony (ABC) algorithm. Applied soft computing, 8(1), 687-697, 2008.
  • Price, K., Storn, R. M., & Lampinen, J. A., Differential evolution: a practical approach to global optimization, Springer Science & Business Media, 2006.
  • Hussain, K., Salleh, M. N. M., Cheng, S., & Shi, Y., Metaheuristic research: a comprehensive survey. Artificial Intelligence Review, 52(4), 2191-2233, 2019.
  • Siarry, P., Metaheuristics, Springer International Publishing, 2016.
  • 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.
  • 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
  • Karaboga, D., An idea based on honey bee swarm for numerical optimization (Vol. 200, 1-10). Technical report-tr06, Erciyes university, engineering faculty, computer engineering department, 2005.
  • Özturk, C., Hancer, E., & Karaboga, D., Küresel en iyi yapay ari koloni algoritmasi ile otomatik kümeleme. Journal of the Faculty of Engineering & Architecture of Gazi University, 29(4), 2014.
  • 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.
  • 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.
  • Yurtkuran, A., & Emel, E., An adaptive artificial bee colony algorithm for global optimization. Applied Mathematics and Computation, 271, 1004-1023, 2015.
  • Babaoglu, I., Artificial bee colony algorithm with distribution-based update rule. Applied Soft Computing, 34, 851-861, 2015.
  • 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.
  • 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.
  • Gao, W., & Liu, S., Improved artificial bee colony algorithm for global optimization. Information Processing Letters, 111(17), 871-882, 2011.
  • Gao, W. F., & Liu, S. Y., A modified artificial bee colony algorithm. Computers & Operations Research, 39(3), 687-697, 2012.
  • 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.
  • 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.
  • 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.
  • Fialho, Á., Da Costa, L., Schoenauer, M., & Sebag, M., Extreme value based adaptive operator selection. In International Conference on Parallel Problem Solving from Nature (pp. 175-184). Springer, Berlin, Heidelberg, 2008.
  • 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.
  • Martello, S., Knapsack problems: algorithms and computer implementations. Wiley-Interscience series in discrete mathematics and optimization, 1990.
  • Kellerer, H., Pferschy, U., & Pisinger, D., Multidimensional knapsack problems, Knapsack problems, 235-283, Springer, Berlin, Heidelberg, 2004.
  • 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.
  • 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.
  • Puchinger, J., Raidl, G. R., & Pferschy, U., The multidimensional knapsack problem: Structure and algorithms. INFORMS Journal on Computing, 22(2), 250-265, 2010.
  • 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.
  • 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.
  • Luo, K., & Zhao, Q., A binary grey wolf optimizer for the multidimensional knapsack problem. Applied Soft Computing, 83, 105645, 2019.
  • Ozturk, C., Hancer, E., & Karaboga, D., Dynamic clustering with improved binary artificial bee colony algorithm. Applied Soft Computing, 28, 69-80, 2015.
  • Jia, D., Duan, X., & Khan, M. K., Binary Artificial Bee Colony optimization using bitwise operation. Computers & Industrial Engineering, 76, 360-365, 2014.
  • Ozturk, C., Hancer, E., & Karaboga, D., A novel binary artificial bee colony algorithm based on genetic operators. Information Sciences, 297, 154-170, 2015.
  • 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.
  • 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.
  • Kiran, M. S., The continuous artificial bee colony algorithm for binary optimization. Applied Soft Computing, 33, 15-23, 2015.
  • 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.
  • Kiran, M. S., & Gündüz, M., XOR-based artificial bee colony algorithm for binary optimization. Turkish Journal of Electrical Engineering & Computer Sciences, 21(Sup. 2), 2307-2328, 2013.
  • Durgut, R., Improved binary artificial bee colony algorithm. arXiv preprint arXiv:2003.11641, 2020.
  • Thierens, D. Adaptive strategies for operator allocation, Parameter setting in evolutionary algorithms,77-90, Springer, Berlin, Heidelberg, 2007.
  • 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.
  • 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.
  • 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.
  • Chu, P. C., & Beasley, J. E., A genetic algorithm for the multidimensional knapsack problem. Journal of heuristics, 4(1), 63-86, 1998.
  • 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.
  • Queen Mary University of London, MKP Problem Instances, http://www.eecs.qmul.ac.uk/~jdrake/mkp.html, Erişim tarihi Haziran 10, 2020
There are 49 citations in total.

Details

Primary Language Turkish
Subjects Engineering
Journal Section Makaleler
Authors

Rafet Durgut 0000-0002-6891-5851

Mehmet Aydin 0000-0002-4890-5648

Publication Date September 2, 2021
Submission Date October 4, 2020
Acceptance Date May 1, 2021
Published in Issue Year 2021 Volume: 36 Issue: 4

Cite

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. https://doi.org/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). GUMMFD. September 2021;36(4):2333-2348. doi:10.17341/gazimmfd.804858
Chicago Durgut, Rafet, and Mehmet Aydin. “Ç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 (September 2021): 2333-48. https://doi.org/10.17341/gazimmfd.804858.
EndNote Durgut R, Aydin M (September 1, 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.
IEEE R. Durgut and M. Aydin, “Çok boyutlu sırt çantası problemi için adaptif ikili yapay arı kolonisi algoritması (AİYAK)”, GUMMFD, vol. 36, no. 4, pp. 2333–2348, 2021, doi: 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 (September 2021), 2333-2348. https://doi.org/10.17341/gazimmfd.804858.
JAMA Durgut R, Aydin M. Çok boyutlu sırt çantası problemi için adaptif ikili yapay arı kolonisi algoritması (AİYAK). GUMMFD. 2021;36:2333–2348.
MLA Durgut, Rafet and Mehmet Aydin. “Ç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, pp. 2333-48, doi: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). GUMMFD. 2021;36(4):2333-48.

Cited By

Streamflow forecasting using a hybrid LSTM-PSO approach: the case of Seyhan Basin
Natural Hazards
https://doi.org/10.1007/s11069-023-05877-3