Solving Multidimensional Knapsack Problem with Bayesian Multiploid Genetic Algorithm

Year 2022, Volume: 3 Issue: 2, 58 - 64, 28.12.2022

Emrullah Gazioğlu

https://doi.org/10.55195/jscai.1216193

Abstract

Solving optimization problems is still a big challenge in the area of optimization algorithms. Many proposed algorithms in the literature don’t consider the relations between the variables of the nature of the problem. However, a recently published algorithm, called “Bayesian Multiploid Genetic Algorithm” exploits the relations between the variables and then solves the given problem. It also uses more than one genotype unlike the simple Genetic Algorithm (GA) and it acts like an implicit memory in order to remember the old but good solutions. In this work, the well-known Multidimensional Knapsack Problem (MKP) is solved by the Bayesian Multiploid Genetic Algorithm. And the results show that exploiting relations between the variables gets a huge advantage in solving the given problem.

Keywords

genetic algorithm, evolutionary computing, multidimensional knapsack problem

References

• P. C. Gilmore ve R. E. Gomory, “The Theory and Computation of Knapsack Functions”, Operations Research, c. 14, sy 6, ss. 1045-1074, Ara. 1966, doi: 10.1287/opre.14.6.1045.
• Y. Li, Y. Tao, ve F. Wang, “A compromised large-scale neighborhood search heuristic for capacitated air cargo loading planning”, European Journal of Operational Research, c. 199, sy 2, ss. 553-560, Ara. 2009, doi: 10.1016/j.ejor.2008.11.033.
• G. B, “Allocation of Databases and Processors in a Distributed Computing System”, Management of Distributed Data Processing, ss. 215-231, 1982.
• M. Engwall ve A. Jerbrant, “The resource allocation syndrome: the prime challenge of multi-project management?”, International Journal of Project Management, c. 21, sy 6, ss. 403-409, Ağu. 2003, doi: 10.1016/S0263-7863(02)00113-8.
• M. Abdel-Basset, R. Mohamed, K. M. Sallam, R. K. Chakrabortty, ve M. J. Ryan, “BSMA: A novel metaheuristic algorithm for multi-dimensional knapsack problems: Method and comprehensive analysis”, Computers & Industrial Engineering, c. 159, s. 107469, Eyl. 2021, doi: 10.1016/j.cie.2021.107469.
• V. Cacchiani, M. Iori, A. Locatelli, ve S. Martello, “Knapsack problems — An overview of recent advances. Part II: Multiple, multidimensional, and quadratic knapsack problems”, Computers & Operations Research, c. 143, s. 105693, Tem. 2022, doi: 10.1016/j.cor.2021.105693.
• S. Gupta, R. Su, ve S. Singh, “Diversified sine–cosine algorithm based on differential evolution for multidimensional knapsack problem”, Applied Soft Computing, c. 130, s. 109682, Kas. 2022, doi: 10.1016/j.asoc.2022.109682.
• A. Rezoug, M. Bader-el-den, ve D. Boughaci, “Application of Supervised Machine Learning Methods on the Multidimensional Knapsack Problem”, Neural Process Lett, c. 54, sy 2, ss. 871-890, Nis. 2022, doi: 10.1007/s11063-021-10662-z.
• F. Wang, Y. Li, A. Zhou, ve K. Tang, “An Estimation of Distribution Algorithm for Mixed-Variable Newsvendor Problems”, IEEE Transactions on Evolutionary Computation, c. 24, sy 3, ss. 479-493, Haz. 2020, doi: 10.1109/TEVC.2019.2932624.
• L. Ma, K. Hu, Y. Zhu, ve H. Chen, “Cooperative artificial bee colony algorithm for multi-objective RFID network planning”, Journal of Network and Computer Applications, c. 42, ss. 143-162, Haz. 2014, doi: 10.1016/j.jnca.2014.02.012.
• B. Zhang, Q.-K. Pan, X.-L. Zhang, ve P.-Y. Duan, “An effective hybrid harmony search-based algorithm for solving multidimensional knapsack problems”, Applied Soft Computing, c. 29, ss. 288-297, Nis. 2015, doi: 10.1016/j.asoc.2015.01.022.
• M. Dorigo ve T. Stützle, “Ant Colony Optimization: Overview and Recent Advances”, içinde Handbook of Metaheuristics, M. Gendreau ve J.-Y. Potvin, Ed. Cham: Springer International Publishing, 2019, ss. 311-351. doi: 10.1007/978-3-319-91086-4_10.
• S. Mirjalili ve A. Lewis, “The Whale Optimization Algorithm”, Advances in Engineering Software, c. 95, ss. 51-67, May. 2016, doi: 10.1016/j.advengsoft.2016.01.008.
• Y. Zhou, L. Li, ve M. Ma, “A Complex-valued Encoding Bat Algorithm for Solving 0–1 Knapsack Problem”, Neural Process Lett, c. 44, sy 2, ss. 407-430, Eki. 2016, doi: 10.1007/s11063-015-9465-y.
• E. Gazioğlu ve A. S. Etaner-Uyar, “Experimental analysis of a statistical multiploid genetic algorithm for dynamic environments”, Engineering Science and Technology, an International Journal, c. 35, s. 101173, Kas. 2022, doi: 10.1016/j.jestch.2022.101173.
• Y. Feng ve G.-G. Wang, “A binary moth search algorithm based on self-learning for multidimensional knapsack problems”, Future Generation Computer Systems, c. 126, ss. 48-64, Oca. 2022, doi: 10.1016/j.future.2021.07.033.
• G.-G. Wang, “Moth search algorithm: a bio-inspired metaheuristic algorithm for global optimization problems”, Memetic Comp., c. 10, sy 2, ss. 151-164, Haz. 2018, doi: 10.1007/s12293-016-0212-3.
• M. Abdel-Basset, D. El-Shahat, H. Faris, ve S. Mirjalili, “A binary multi-verse optimizer for 0-1 multidimensional knapsack problems with application in interactive multimedia systems”, Computers & Industrial Engineering, c. 132, ss. 187-206, Haz. 2019, doi: 10.1016/j.cie.2019.04.025.
• Z. Beheshti, S. M. Shamsuddin, ve S. Hasan, “Memetic binary particle swarm optimization for discrete optimization problems”, Information Sciences, c. 299, ss. 58-84, Nis. 2015, doi: 10.1016/j.ins.2014.12.016.
• R. Poli, J. Kennedy, ve T. Blackwell, “Particle swarm optimization”, Swarm Intell, c. 1, sy 1, ss. 33-57, Haz. 2007, doi: 10.1007/s11721-007-0002-0.
• M. Pelikan, “Bayesian Optimization Algorithm”, içinde Hierarchical Bayesian Optimization Algorithm: Toward a new Generation of Evolutionary Algorithms, M. Pelikan, Ed. Berlin, Heidelberg: Springer, 2005, ss. 31-48. doi: 10.1007/978-3-540-32373-0_3.
• J. E. Beasley, “OR-LIB http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/”, 2005.