Rješavanje problema dodjeljivanja kodova nad grafovima primjenom metaheuristika

diplomski rad

• Naslov (engleski): Solving Code-Assignment Problem in Graphs Using Metaheuristics
• Autor: Mateo Šimonović
• Mentor: Marko Čupić (mentor)
• Član povjerenstva: Marko Čupić (predsjednik povjerenstva)
• Član povjerenstva: Domagoj Jakobović (član povjerenstva)
• Član povjerenstva: Marin Golub (č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-07-03, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

U radu su predstavljeni problemi dodjele SC i RSI-kodova, koji se javljaju u fazi planiranja bežičnih WCDMA i LTE-mreža. Radi se o problemima koji se svode na diskretni optimizacijski problem bojanja grafova, kojem dodaju određena ograničenja. Problemi su obrađeni teorijski i praktično. U teorijskom dijelu detaljno su analizirani problemi te su objašnjene njihove razlike i ograničenja. U radu su dalje predloženi postupci za rješavanje navedenih problema, koji uključuju korištenje heuristika lokalne pretrage, genetskog algoritma i modela strojnog učenja. Na kraju su prikazani rezultati istraživanja, opisane prednosti i nedostaci pojedinog postupka te predložena poboljšanja.

Sažetak (engleski)

In this master's thesis are presented two problems: the SC code assignment in WCDMA networks and the RSI code assignment in LTE networks. Both of these problems appear as an obstacle in the telecommunication domain in the process of network planning. The presented problems are variants of the graph coloring problem, with added constraints. In this thesis, the problems are observed both theoretically and practically. In the theoretical part, the problems have been studied in detail and their complexities and constraints are analyzed. In the rest of the thesis several algorithms have been proposed for solving the problems including heuristic local search algorithms, the genetic algorithm and machine learning models. In conclusion, the results of this research are shown as well as pros and cons for each proposed algorithm and improvement guidelines.

• Ključne riječi: bojanje grafova; problem dodjeljivanja frekvencija; lokalna pretraga; heuristika; metaheuristika; genetski algoritam; strojno učenje
• Ključne riječi (engleski): graph coloring; frequency assignment problem; local search; heuristics; metaheuristics; genetic algorithm; machine learning
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:250109
• 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-14 01:16:09