Genetic Algorithm for the 0/1 Multidimensional Knapsack Problem
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.
Code (1)
Tasks
C++ codeSimilar Papers 제목 키워드 기반
Simulated Annealing Algorithm for the Multiple Choice Multidimensional Knapsack Problem
The multiple choice multidimensional knapsack problem (MCMK) is a harder version of the 0/1 knapsack problem, and is ever more complex than the 0/1 multidimensional knapsack problem. In MCMK, there are several groups of …
AllC++ codeMultiple-choiceA Novel Genetic Algorithm using Helper Objectives for the 0-1 Knapsack Problem
The 0-1 knapsack problem is a well-known combinatorial optimisation problem. Approximation algorithms have been designed for solving it and they return provably good solutions within polynomial time. On the other hand, g…
A Denoising Autoencoder that Guides Stochastic Search
An algorithm is described that adaptively learns a non-linear mutation distribution. It works by training a denoising autoencoder (DA) online at each generation of a genetic algorithm to reconstruct a slowly decaying mem…
DenoisingA Weight-coded Evolutionary Algorithm for the Multidimensional Knapsack Problem
A revised weight-coded evolutionary algorithm (RWCEA) is proposed for solving multidimensional knapsack problems. This RWCEA uses a new decoding method and incorporates a heuristic method in initialization. Computational…
Imperialist Competitive Algorithm with Independence and Constrained Assimilation for Solving 0-1 Multidimensional Knapsack Problem
The multidimensional knapsack problem is a well-known constrained optimization problem with many real-world engineering applications. In order to solve this NP-hard problem, a new modified Imperialist Competitive Algorit…
Diversity