Applicability of the Genetic Algorithm in Solving the Knapsack Problem

Cilj ovog rada je primijeniti genetički algoritam na problem naprtnjače i proučiti utjecaj pojedinih parametara na kvalitetu rješenja. Problem naprtnjače pripada razredu NP-teških optimizacijskih problema. Problem naprtnjače nije moguće riješiti egzaktnim metodama u polinomnom vremenu već je nužno koristiti metaheuristike. Metaheuristike nude mogućnost pronalaska dovoljno dobrog rješenja u razumnom vremenu. Genetički algoritam je metaheuristika inspirirana prirodom i temeljena na populaciji te je čest pristup rješavanju problema naprtnjače.The aim of this paper is to apply genetic algorithm to solve knapsack problem and study the impact of the parameters on the quality of solution. Knapsack problem belongs to the class of NP-hard optimization problems. Knapsack problem can not be solved by exact methods in polynomial time, therefore it is necessary to use metaheuristics. Metaheuristics provide acceptable solutions in a reasonable time. Genetic algorithm is population based metaheuristic inspired by nature and is a common approach to solve knapsack problem