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

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 Kelimeler:

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

PDF

___

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