Bojanje grafova prilagodljivim postupcima lokalne pretrage

master's thesis

• Title (english): Graph coloring with adaptive local search heuristics
• Author: Luka Marasović
• Mentor: Domagoj Jakobović (mentor)
• Committee member: Domagoj Jakobović (predsjednik povjerenstva)
• Committee member: Marko Čupić (član povjerenstva)
• Committee member: Stjepan Groš (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2014-07-09, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

U diplomskom radu je proučena primjena metaheuristika na optimizaciju parametara Radio Access Network-a koji je modeliran kao težinski graf. Cilj optimizacije je minimizacija sume konfliktnih bridova uz zadana ograničenja. Za optimizaciju se koriste pohlepni algoritmi te tabu pretraga. Dodatno je istražena mogućnost učenja pohlepnog algoritma uz pomoć neuronske mreže i genetskog algoritma. Eksperimentalno su određeni parametri koji nude najbolje rezultate te je napravljena usporedba s najboljim rezultatima.

Abstract (english)

This thesis deals with the application of metaheuristics to optimize parameters for Radio Access Network which is modeled as a weighted graph. The goal of optimization is to minimize the sum of conflicting edges given the constraints. Greedy algorithms and tabu search are used for optimisation. Possibility of learning new greedy algorithm was explored with the help of neural networks and genetic algorithms. Parameters that provide best results are experimentally determined and comparison is made with the best known results.

• Keywords: bojanje grafova; metaheuristika; pohlepni algoritam; tabu pretraga; genetski algoritam; umjetna neuronska mreža
• Keywords (english): graph coloring; metaheuristics; greedy algorithm; tabu search; genetic algorithm; artificial neural network
• Language: croatian
• URN:NBN: urn:nbn:hr:168:915169
• 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: 2018-02-06 10:23:56