prikaz prve stranice dokumenta Rješavanje problema putne torbe algoritmom diferencijalne evolucije
  Download
PDF 1.03 MB
undergraduate thesis
Rješavanje problema putne torbe algoritmom diferencijalne evolucije
2020. urn:nbn:hr:200:937651
Šimić, Zvonimir
Josip Juraj Strossmayer University of Osijek
Faculty of Electrical Engineering, Computer Science and Information Technology Osijek
Department of Software Engineering
Chair of Programming Languages and Systems

Cite this document

Šimić, Z. (2020). Rješavanje problema putne torbe algoritmom diferencijalne evolucije (Undergraduate thesis). Osijek: Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek. Retrieved from https://urn.nsk.hr/urn:nbn:hr:200:937651

Šimić, Zvonimir. "Rješavanje problema putne torbe algoritmom diferencijalne evolucije." Undergraduate thesis, Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek, 2020. https://urn.nsk.hr/urn:nbn:hr:200:937651

Šimić, Zvonimir. "Rješavanje problema putne torbe algoritmom diferencijalne evolucije." Undergraduate thesis, Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek, 2020. https://urn.nsk.hr/urn:nbn:hr:200:937651

Šimić, Z. (2020). 'Rješavanje problema putne torbe algoritmom diferencijalne evolucije', Undergraduate thesis, Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek, accessed 20 November 2024, https://urn.nsk.hr/urn:nbn:hr:200:937651

Šimić Z. Rješavanje problema putne torbe algoritmom diferencijalne evolucije [Undergraduate thesis]. Osijek: Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek; 2020 [cited 2024 November 20] Available at: https://urn.nsk.hr/urn:nbn:hr:200:937651

Z. Šimić, "Rješavanje problema putne torbe algoritmom diferencijalne evolucije", Undergraduate thesis, Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek, Osijek, 2020. Available at: https://urn.nsk.hr/urn:nbn:hr:200:937651

Please login to the repository to save this object to your list.
Metadata
TitleRješavanje problema putne torbe algoritmom diferencijalne evolucije
Title (english)Differential evolution algorithm for the knapsack problem
AuthorZvonimir Šimić
MentorZdravko Krpić (mentor)
MentorDražen Bajer (sumentor)
Committee memberZdravko Krpić (predsjednik povjerenstva)
Committee memberDanijel Topić (član povjerenstva)
Committee memberMirko Köhler (član povjerenstva)
GranterJosip Juraj Strossmayer University of Osijek
Faculty of Electrical Engineering, Computer Science and Information Technology Osijek
(Department of Software Engineering)
(Chair of Programming Languages and Systems)
Osijek
Defense date and country2020-09-25, Croatia
Scientific / art field,
discipline and subdiscipline		TECHNICAL SCIENCES
Computing
Data Processing
Abstract
U ovom se radu predstavlja algoritam diferencijalne evolucije (DE), jedan od najpopularnijih i najučinkovitijih evolucijskih algoritama, za rješavanje problema putne torbe. Navedeni problem predstavlja NP-težak problem kombinatorne optimizacije u kojemu se pokušava povećati ukupna cijena predmeta unutar putne torbe bez premašivanja njezinog kapaciteta. Algoritam diferencijalne evolucije (DE) izvorno je namijenjen za rješavanje problema kontinuirane optimizacije te nije izravno primjenjiv na problem putne torbe. Glavni je razlog za to za nju specifični operator mutacije koji je isključivo prikladan za vektore realnih komponenti. Naime, nužna je ugradnja neke od metoda diskretizacije. One diskretiziraju vektore unutar algoritma DE u svrhu njegovog korištenja u problemima diskretne kombinatorike. U ovom su radu korištene tri različite metode diskretizacije te su se njihove učinkovitosti usporedile u odgovarajućoj eksperimentalnoj analizi koja je obavljena pomoću ostvarenog programskog rješenja. Eksperimentalnom analizom pokazana je važnost odabira metode diskretizacije u svrhu ostvarivanja boljih performansi algoritma DE pri rješavanju diskretnih problema optimizacije.
Abstract (english)
This paper presents the differential evolution algorithm (DE), one of the most popular and most efficient evolutionary algorithms, for the knapsack problem. The knapsack problem is an NP-hard problem in which the goal is to increase the total price of items within the knapsack without exceeding its capacity. The DE algorithm was originally proposed for solving continuous optimization problems and is not directly applicable to the knapsack problem. The main reason for this is the specific mutation operator that is only suitable for real-valued vectors. Namely, it is necessary to incorporate a method for discretization of the real-valued solutions the algorithm operates on. This enables the application of the algorithm to discrete problems. Three different discretization methods were used in this paper and their efficiencies were compared by an experimental analysis. The experimental analysis was performed using the developed software solution. The experimental analysis has proven the importance of choosing a proper discretization method in order to achieve better performance of the differential evolution algorithm.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:200:937651
Study programmeTitle: Undergraduate University Study Programme in Computer Engineering
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 resourceText
File originBorn digital
Access conditionsOpen access
Terms of useLicence In copyright icon
Created on2020-11-17 08:26:37