Rješavanje problema naprtnjače evolucijskim algoritmima

undergraduate thesis

• Title (english): Solving the knapsack problem with evolutionary algorithms
• Author: Stipe Šuto
• Mentor: Marin Golub (mentor)
• Committee member: Marin Golub (predsjednik povjerenstva)
• Committee member: Vjeko Kužina (član povjerenstva)
• Committee member: Iva Jurković (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2021-09-14, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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 literature

• Keywords: problem naprtnjače; evolucijski algoritmi; genetski algoritam; algoritam genetskog kaljenja; populacija; mutacija
• Keywords (english): knapsack problem; evolutionary algorithms; genetic algorithm; genetic annealing algorithm; population; mutation; ECF
• Language: croatian
• URN:NBN: urn:nbn:hr:168:845141
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-01-13 16:20:42