Research Article
BibTex RIS Cite
Year 2022, , 58 - 64, 28.12.2022
https://doi.org/10.55195/jscai.1216193

Abstract

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.

Solving Multidimensional Knapsack Problem with Bayesian Multiploid Genetic Algorithm

Year 2022, , 58 - 64, 28.12.2022
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.

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.
There are 22 citations in total.

Details

Primary Language English
Subjects Artificial Intelligence
Journal Section Research Articles
Authors

Emrullah Gazioğlu 0000-0002-7615-305X

Publication Date December 28, 2022
Submission Date December 8, 2022
Published in Issue Year 2022

Cite

APA Gazioğlu, E. (2022). Solving Multidimensional Knapsack Problem with Bayesian Multiploid Genetic Algorithm. Journal of Soft Computing and Artificial Intelligence, 3(2), 58-64. https://doi.org/10.55195/jscai.1216193
AMA Gazioğlu E. Solving Multidimensional Knapsack Problem with Bayesian Multiploid Genetic Algorithm. JSCAI. December 2022;3(2):58-64. doi:10.55195/jscai.1216193
Chicago Gazioğlu, Emrullah. “Solving Multidimensional Knapsack Problem With Bayesian Multiploid Genetic Algorithm”. Journal of Soft Computing and Artificial Intelligence 3, no. 2 (December 2022): 58-64. https://doi.org/10.55195/jscai.1216193.
EndNote Gazioğlu E (December 1, 2022) Solving Multidimensional Knapsack Problem with Bayesian Multiploid Genetic Algorithm. Journal of Soft Computing and Artificial Intelligence 3 2 58–64.
IEEE E. Gazioğlu, “Solving Multidimensional Knapsack Problem with Bayesian Multiploid Genetic Algorithm”, JSCAI, vol. 3, no. 2, pp. 58–64, 2022, doi: 10.55195/jscai.1216193.
ISNAD Gazioğlu, Emrullah. “Solving Multidimensional Knapsack Problem With Bayesian Multiploid Genetic Algorithm”. Journal of Soft Computing and Artificial Intelligence 3/2 (December 2022), 58-64. https://doi.org/10.55195/jscai.1216193.
JAMA Gazioğlu E. Solving Multidimensional Knapsack Problem with Bayesian Multiploid Genetic Algorithm. JSCAI. 2022;3:58–64.
MLA Gazioğlu, Emrullah. “Solving Multidimensional Knapsack Problem With Bayesian Multiploid Genetic Algorithm”. Journal of Soft Computing and Artificial Intelligence, vol. 3, no. 2, 2022, pp. 58-64, doi:10.55195/jscai.1216193.
Vancouver Gazioğlu E. Solving Multidimensional Knapsack Problem with Bayesian Multiploid Genetic Algorithm. JSCAI. 2022;3(2):58-64.