Solving the knapsack problem with evolutionary algorithms

U ovom je radu opisan i definiran problem naprtnjače te mogući načini rješavanja istog. Predstavljeni su evolucijski algoritmi, a detaljnije opisani genetski algoritam i algoritam genetskog kaljenja. Ostvaren je programski sustav za rješavanje problema naprtnjače koristeći radni okvir ECF u programskoj jeziku C++, implementirajući upravo ta dva evolucijska algoritma. Opisane su programske implementacije komponenata algoritama. Analizirani su i predstavljeni rezultati rješenja različitih veličina problema koristeći različite kombinacije parametara. Prikazana je ovisnost kvalitete rješenja o određenim parametrima. Uspoređeni su rezultati s poznatim rezultatima iz literature.This thesis describes and defines the backpack problem and its possible solutions. Evolutionary algorithms are presented, while the genetic algorithm and the genetic annealing algorithm are described in more detail. Software system for solving the knapsack problem was developed using the ECF framework in the programming language C++, implementing those two evolutionary algorithms. Software implementations of the algorithm components are described. The results of solving problems with different sizes using different parameters are analyzed and presented. The quality of the solution is shown to be dependent on certain parameters. The results were compared with known results from previous papers and literatur