Problemi i algoritmi kombinatoričke optimizacije

diplomski rad

• Naslov (engleski): Combinatorial Optimization Oroblems and Algorithms
• Autor: Marina Krček
• Mentor: Domagoj Jakobović (mentor)
• Član povjerenstva: Domagoj Jakobović (predsjednik povjerenstva)
• Član povjerenstva: Stjepan Groš (član povjerenstva)
• Član povjerenstva: Vlado Sruk (č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: 2017-09-19, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Rad opisuje kombinatoričke optimizacijske probleme i razloge korištenja heurističkih metoda u njihovom rješavanju. Natjecanje CBBOC ponudilo je nekolicinu algoritama koji su se pokazali vrlo uspješnima. S natjecanja su preuzeti generirani problemi i objašnjen je NK model korišten za generiranje problema. Postojeći algoritmi iz ECF okruženja ispitani su nad problemima s natjecanja, u radu su opisani rezultati te je provedena usporedba s rezultatima natjecanja. S obzirom na rezultate na natjecanju, unutar ECF okruženja implementirana su dva algoritma pobjednika – algoritam P3 i CMA-VNS. Oba algoritma su detaljno objašnjena te su napomenute određene prilagodbe za ECF okruženje.

Sažetak (engleski)

This thesis describes combinatorial optimization problems and explains why heuristics are often used for solving them. On a competition named CBBOC there were several algorithms that proved to be very successful in solving this problems. For the competition, combinatorial problems were generated using NK model that is explained in the thesis. Existing algorithms from ECF framework were tested on generated combinatorial problems from the competition. The obtained results are shown in graphs, analyzed and compared to results from the competition. Considering the results of the competition, two winner algorithms are implemented in ECF environment – algorithm P3 and CMA-VNS. Both of the algorithms are explained in the thesis and specific adjustments for the ECF environment are mentioned.

• Ključne riječi: kombinatorički optimizacijski problemi; heurističke metode; NK model; ECF; algoritam P3; algoritam CMA-VNS
• Ključne riječi (engleski): combinatorial optimization problems; heuristics; NK model; ECF; algorithm P3; algorithm CMA-VNS
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:186987
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka računarstva (mag.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2019-03-13 21:56:24