Genetic Algorithm for the 0/1 Multidimensional Knapsack Problem
From MaRDI portal
Publication:6324000
arXiv1908.08022MaRDI QIDQ6324000
Author name not available (Why is that?)
Publication date: 20 July 2019
Abstract: The 0/1 multidimensional knapsack problem is the 0/1 knapsack problem with m constraints which makes it difficult to solve using traditional methods like dynamic programming or branch and bound algorithms. We present a genetic algorithm for the multidimensional knapsack problem with Java and C++ code that is able to solve publicly available instances in a very short computational duration. Our algorithm uses iteratively computed Lagrangian multipliers as constraint weights to augment the greedy algorithm for the multidimensional knapsack problem and uses that information in a greedy crossover in a genetic algorithm. The algorithm uses several other hyperparameters which can be set in the code to control convergence. Our algorithm improves upon the algorithm by Chu and Beasley in that it converges to optimum or near optimum solutions much faster.
Has companion code repository: https://github.com/shah314/gamultiknapsack
This page was built for publication: Genetic Algorithm for the 0/1 Multidimensional Knapsack Problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6324000)
