Solving the knapsack problem with a modified genetic algorithm

Author: Sopiko Gogaladze
Keywords: knapsack problem, genetic algorithms
Annotation:

The knapsack problem is the well-known and well-researched problem of discrete optimization. It belongs to the class of NP-hard problems. An intensive study of this problem is important from both a theoretical and practical point of view, because it has applications in cryptography, capital budgeting, cargo loading, utilization of communication channels, logistical problems.Exact and approximate algorithms have been created and updated in last decades. It made possible to solve the problems with large instances, but for a certain class of instances, the problem is still hard to solve. The paper presents modified genetic algorithm to solve 0-1 knapsack problem. Genetic algorithms provide an opportunity to find an approximate solution. One of the disadvantages of genetic algorithms is the likelihood of getting stuck in local maxima early on. In order to avoid this, the modified genetic algorithm presents a new type of initialization and mutation operators. This algorithm improves the solution of the knapsack problem for the certain type of "hard" instances.The method is tested for some instances.