Rješavanje problema putne torbe algoritmom diferencijalne evolucije

Šimić, Zvonimir

undergraduate thesis

Rješavanje problema putne torbe algoritmom diferencijalne evolucije

Osijek: Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek, 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

Institutional repository: Faculty of Electrical Engineering, Computer Science and Information Technology Osijek

Cite this document

APA 6th Edition

Š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

MLA 8th Edition

Š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

Chicago 17th Edition

Harvard

Š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 29 April 2024, https://urn.nsk.hr/urn:nbn:hr:200:937651

Vancouver

Š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 April 29] Available at: https://urn.nsk.hr/urn:nbn:hr:200:937651

IEEE

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

Cite this item: https://urn.nsk.hr/urn:nbn:hr:200:937651

Metadata

Title	Rješavanje problema putne torbe algoritmom diferencijalne evolucije
Title (english)	Differential evolution algorithm for the knapsack problem
Author	Zvonimir Šimić
Mentor	Zdravko Krpić (mentor)
Mentor	Dražen Bajer (sumentor)
Committee member	Zdravko Krpić (predsjednik povjerenstva)
Committee member	Danijel Topić (član povjerenstva)
Committee member	Mirko Köhler (član povjerenstva)
Granter	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) Osijek
Defense date and country	2020-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)
Language	croatian
URN:NBN	urn:nbn:hr:200:937651
Study programme	Title: 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 resource	Text
File origin	Born digital
Access conditions	Open access
Terms of use
Created on	2020-11-17 08:26:37

Search form