Rješavanje problema dodjeljivanja kodova nad grafovima primjenom metaheuristika

master's thesis

• Title (english): Solving Code-Assignment Problem in Graphs Using Metaheuristics
• Author: Mateo Šimonović
• Mentor: Marko Čupić (mentor)
• Committee member: Marko Čupić (predsjednik povjerenstva)
• Committee member: Domagoj Jakobović (član povjerenstva)
• Committee member: Marin Golub (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2017-07-03, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

• Keywords: bojanje grafova; problem dodjeljivanja frekvencija; lokalna pretraga; heuristika; metaheuristika; genetski algoritam; strojno učenje
• Keywords (english): graph coloring; frequency assignment problem; local search; heuristics; metaheuristics; genetic algorithm; machine learning
• Language: croatian
• URN:NBN: urn:nbn:hr:168:250109
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2019-03-14 01:16:09