Rješavanje problema naprtnjače evolucijskim algoritmima

završni rad

• Naslov (engleski): Solving the knapsack problem with evolutionary algorithms
• Autor: Stipe Šuto
• Mentor: Marin Golub (mentor)
• Član povjerenstva: Marin Golub (predsjednik povjerenstva)
• Član povjerenstva: Vjeko Kužina (član povjerenstva)
• Član povjerenstva: Iva Jurković (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2021-09-14, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

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.

Sažetak (engleski)

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

• Ključne riječi: problem naprtnjače; evolucijski algoritmi; genetski algoritam; algoritam genetskog kaljenja; populacija; mutacija
• Ključne riječi (engleski): knapsack problem; evolutionary algorithms; genetic algorithm; genetic annealing algorithm; population; mutation; ECF
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:845141
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-01-13 16:20:42